Cyrptography Theory Notes based on Workshop by Frank Wang

In the schemes discussed below, the only thing that’s secret is the secret key
If your security is based on the algorithm or a fixed value, somebody can always break that

One-Time Pad – Perfect Security

Gen(.) – Generate key phase.  Pick a random key k.
k has to be length of message m

Encyrpt(k, m): k Xor m, outputs
XOR(a,b) = a^ b
if a, b = 0 -> 0
if a, b = 1 -> 0
if a= 0, b= 1 -> 1
if a =1, b=0 -> 1
Basically it’s a way of talking about binary notation
The point of it in the context of Crypto is that it’s random

Decrypt(k, c): c Xor k = Xor Message Xor –
Key & Cipher Text

Pr[C=c | M=m] = 1/2^l
Given this key, what’s the probability of creating any given cipher text
if m has length l, there’s only one possible message/cipher text combo

Shannon’s Theorem – In order to achieve perfect security, the size of the message has to equal the size of the key & the size of the cipher
|M| = |K| = |C|
Unuseable in the real world – not practical
In real world |K| < |M|

Computational Security:
1.  Security is only preserved against efficient adversaries that run in a feasible amount of time
We assume they have a limited amount of power, based on computational power that exists in the world.
Usually 2^80 or 2^128 – Really high orders of magnitude
2.  Adversaries can potentially succeed with some very small probability.
Smaller probability than getting struck by lightning 100 times

Usually looking at security proofs, there’s usually a Security Parameter.
Usually denoted as L
Describes how powerful the adversary is

If you assume some Math property A can’t be solved (efficiently), then B is secure

Prove the Contrapositive – Assume B is insecure & can be broken by A, and prove what the case is

Pseudo-Random Generator – Generator G that outputs L.
L(n) – Length is Polynomial
D = Distinguisher
Has to expand
Length of the output must be greater than what you seed it with
You seed it with something random, and then it creates something longer & more random.
Trick an adversary into thinking you have infinite number of bits
|Pr(D(r)) = [] – Pr(D(G(s))) = [] | 1 <= neg |(n)
Essentially if you give them random bits, and they can’t tell where the source is with negative probability, then you’re fine.

One-Time Pad:
We can create a computationally secure thing
Gen: k
Enc: G(k) Xor m
Dec: G(k) Xor c

Security Models:
Chosen Plaintext Attack (CPA/Semantic Security):
Games you play & Adversary wins with some low probability
1.  Generate Key unknown to adversary
2.  Adversary can Encrypt
Same as giving them access to the encryption function that’s already been keyed
They don’t know what the key is
A creates m0, m1
3.  Challenger chooses m0 or m1 and sends Enc(k,Mb) back to a
B is the encrypted bit
A still has access to the Encryption Oracle – Enc(k)
Can choose to ask for more encryptions if it wants
Then it has to output b to try to figure out the original message

Chosen Cypher Text Attack (CCA1 & CCA2):
CCA1 & 2- They also have access to a Decryption Oracle
decrypt messages at different points
Homorphic Encryption can never be CCA2 secure
Encrypted value under some key x
Can apply some function to it w/out looking at encrypted vale
Output is equal to the Encrypted value
F(E(k,x)) = E(k,f(x))
Can just apply a function to it, and this makes it more possible to break the message

Pseudo-Random Functions:
PRFs are a distribution of functions
For a given domain, you can’t tell what function was applied to the input
PRF simulates the idea that 2^x possible functions that you can pick

Security for PRFs is that we don’t know whether we are interacting with a PRF of f chosen from a set of All Functions

Pseudo-Random Function Encryption:
PRF Encryption
Similar to PRG encryption
PRG – can assume output is random – permutes 128 bits
PRF – is random b/c the function itself is chosen randomly
Gen: k,f
Enc: <r, Fk(r) Xor M>
Dec: M = Fk(r) Xor C
No restriction on Output length

Advanced Encryption Security (AES):
A function/block cipher:
Takes in a Key & permutates a value y
K * x = Y
128 or 256 Bits, 128 Bits, 128 Bits

Has initialization vector (similar to salt)
Outputs Directly
Xor w/ message
Feed into AES
Take output of that feed & Xor with the next block of the message
Repeat until all messages are fulfilled
Problem with it is that it’s not parallizable
Must be done sequentially
You need padding to make it secure
Will not work for small messages
Won’t work if you don’t have a Multiple of 128

Counter Mode:
Start off with random counter
Output Counter
Increment Counter
Encrypt Counter
Xor with Message
Output result
Only requires AES encryption block for Encryption & Decryption

Any of the above functions can use AES or PRF – Either fine
PRF: Salsa20
Much faster & supposed to be easier to understand

Message Authentication Code (MAC):
Though doesn’t necessarily imply Confidentiality
Adversary could flip bits for fun & give you a bad message
Or create a new message

Usually has 3 Functions:
Key Generation
Tag – Run the MAC over whatever you want to prevent tampering with
Verify – Verifies integrity of the Tag

MAC Threat or Security Game:
Slightly Stronger
Essential Idea: Can’t create a tag with the same message that’s different than the original Tag
1.  Choose a Random Key unknown by Adversary
2.  Adversary has access to the Tagging Function MAC(.) A
Eventually outputs (m, t) – Message, Time
3.  A wins if Verify(m,t) = True

Hash Functions:
SHA Family:

Input can be arbitrarily wrong & output is based on it
Involves some compression
For distinct Xprime:
Adversary can not find Distinct
x, xprime s.t. H(x) = H(xprime)
One-Way Function
F(x) = y – given F of X, you are unable to solve for y
***Did I maybe get that backwards???***

Symmetric Key Encryption:
How To Encrypt and MAC:
1.  Encrypt MAC separately:
Bad because:
MACk1(m) = (m, MACk(m)) – Breakable, no privacy requirement

2.  MAC then encrypt
SSL does this
t <– Mack2(m), then m||t is encrypted
Problem because:
Transform (m) – using this function, you can learn what the message is
Before we Encrypt, we transform the message first
Counter Mode w/ PRF
If I’m an attacker, I get Cprime & start Flipping Bits
If Flipped Bit & Message is still valid:

1.  Encrypt then MAC – This is the correct way to do things

Key Management:
Public Key Encryption:
Two Keys – One is Public & One is Private
PGP is an example of this
RSA, El Gamal

Usually uses public key encryption w/ hybrid encryption
Encpk(kAES) -> C1
Enck1AES(data) -> C2

Public Key MACs
Two Keys – 1 public, 1 private
Sign with Private Key & Someone Verifies with Public Key
This is how SSL Works
SSL Certificates/Authorities are the Verification method of the Public Key

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s