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

Probability

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-Randomness:

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

CBC:

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):

Integrity

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:

SHA1

SHA256

SHA512

SHA3

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:

Incorrect:

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

Enck1(m||MACk2(m))

Problem because:

Transform (m) – using this function, you can learn what the message is

Before we Encrypt, we transform the message first

Enck(Transform(m))

Counter Mode w/ PRF

If I’m an attacker, I get Cprime & start Flipping Bits

If Flipped Bit & Message is still valid:

Correct:

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

Signatures:

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