Notes on block ciphers:

For large enough n, random permutation is indistinguishable from random functions, therefore, block ciphers are good pseudo-random functions, Assuming you have a n-bit key k that you put into a block cipher, you can encrypt a n-bit message m. This is the same as the One Time Pad; the benefit here is that because the block cipher is pseudo-random, you can encrypt multiple messages with the same key. **

Currently the trouble with this encryption scheme is that encrypting an n-bit string results in a 2n-bit cipher text:

an n-bit R and n-bit key are plugged into the block cipher the pseudo-random output of the block cipher is XOR’d with m R & the output of the XOR are sent as the 2n-bit ciphertext *** You can mitigate this in several ways; the first step is to break the message into many small blocks to allow for an arbitrary length of message. ***

Modes of Operation:

Stream Ciphers (not covered in this course): Synchronized and Unsynchronized

Block ciphers:

Counter Mode, or CTR: I have a bunch of n-bit blocks Define an n-bit number c0 (First block in cipher text) c0+i is used as input for pseudo-random, where i is the # of the block in the message so final message is original message+n bits long

Cipher Block Chaining, or CBC mode: Define an n-bit number c0(first block in cipher text) XOR with m1 Xor c1 with m2 -> c2, c2 with m3 ->c3, and so on

Never use Electronic Code book, EBC mode: Was defined before true security notions were understood use m1 to encrypt m2 and so forth if two blocks are the same in a long plaintext, it won’t work because in long amounts there will be repeated ciphertext

F is a pseudorandom function if Fk, for a uniform key k which is an element {0,1}^n, is indistinguishable from a uniform function Func_n.

Let F be a length preserving, keyed function:

F is a keyed permutation iff: F_k is a bijection for every k F_k^-1 is efficiently computable

F is a psuedorandom permutation if F_k, for a uniform key which is an element {0,1}^n, is indistinguishable from a uniform permutation.

Block Cipher: Practical Construction of pseudorandom permutation

No asypmptotic, and hard to distinguish f_k from a uniform f element perm even for attackers running in time = 2^n

AES is a standardized block cipher block length: 128 bit key length: 128,192, and 256 bit (2^x security so even a key length of 128 is fine)

Recall the 2 limitations of perfect security:

Key must be as long as the message Key can only be used once

The One Time Pad meets both of these limitations, but is clearly super inconvenient

Computer Security:

We lose the first limit of perfect security by going to compsec, which leads to the pseudo OTP, a long message with a short key.

How do we lose the second limitation? Develop a security definition where multiple messages encrypt the same key The minimum for modern cryptography is security against chosen plaintext attacks (CPA)

Encryption Scheme : pi Key gen : k Attacker: A A submits m, gets back Cm encrypted with k by Oracle Oracle outputs m0 and m1 Oracle encrypts 0 and 1 and outputs to A Attacker tests Oracle somemore A outputs 0 or 1 : this is a guess that m0 or m1 was encrypted

If the probability that this guess is right is 50 percent or less (ie a random guess) then that means the encryption scheme is secure

CPA security is impossible to achieve using deterministic encryption schemes; it needs to be randomized

Randomness is not a property of a string, but a property of the set of strings Distribution of strings that assign probability to each string A particular string is pseudorandom iff it can’t be distinguished from a uniform or a random string

BUT this doesnt make sense, you need psuedorandomNESS, a property of a distribution on strings

Historically: Fix D on Nbit Strings D is considered pseudorandom iff it passed statistical tests, essentially, when we sample X according to D, first bit of X should be 1 half the time

However, lets say the attacker chooses a different statistical test then whats in our battery of tests, one that CAN differentiate. In that case, its no longer secure.

The cryptography definition : Pseudorandomness iff passes all efficient statistical tests

Therefore: For every value of security parameter n: We’re looking at distributions over string of length, over strings of length p(n)

for now, p(n)=n, but n^2 is better for future lectures

Pseudorandom Generators: PRG

G= efficient deterministic algorithm that expands a short, uniform seed or input into a longer pseudorandom output. Essentially: Given short input, convert to longer output that has properties of pseudorandomness.

useful if small amount of random bits but want lots of super random looking bits

G naturally defines a sequence of distributions

What this means is that for all A(PPT attackers), theres a negligible E such that “Given G(x), A cannot distinguish if it is G(x) or a uniform string y! |Difference| < E

The PsuedoRandom One-Time Pad

Key of Length N Plug into G Get out P (Longer then N) Use P as the Key

Until now: Perfect Secrecy in face of Unlimited Computational power

Relax certain parameters to get a more realistic version, known as Computational Secrecy Parameters that are weakened are:

Allow Security to fail with some tiny probability (leak the plaintext) ex. 2^60 chance of failing, which would be once in a 100 billion years

Attackers have a limit on computer power (efficiency) ex. say 1 test of a key per a clock cycle of a processor (Which is very optimistic) then desktop: searches 2^57 keys/year supercomputer: searches 2^80 keys/year a supercomputer thats been searching since big bang : 2^112 keys so far

Therefore restrict key space to 2^128

Define Security as Perfect Indistinguishability:

Encryption Scheme &&& m0 m1 choose either encrypt with k to get C give C to attacker, ask if it m0 or m1 orginally

If attacker can guess right only 1/2 of the time (has to take random guess) , then perfectly indistinguishable , which is an alternate way to define perfect secrecy

Computer Secrecy:

Pr[Privka&&& =1]<0.5+E You restrict the scheme to the time, and the chance to E VERY sensitive to the type of computer being used Asymptotic notion of security

Security can fail at most with the probability Epsilon

time is at most t Introduce n, a new security parameter View it as allowing parties to choose a level of security for now, just look at n as a keylength

Now assume attacker knows N Check runtimes of all parties and success probability of attacker, in terms of n How does the runtime change as n changes?

All these different equations are polynomially bounded, but not necessarily polynomials themselves

For the success value of the attacker, f is negligible iff for every p, there is a bound to N such that f(n)< 1/p(n) for all n larger then current

F is negligible if its asymptotically smaller then any inverse poly ex poly n * 2^-cn

Notion of equations of efficient attackers with probabilistic polynomial time algorithms (PPT) comes from complexity theory

Problems that can be solved efficiently can be solved in polynomial times

Therefore scheme is secure if any poly function is bounded by 1/2 + negligible function

encryption doesn’t hide plaintext length!