permutation f Permn Even if attacker can query the function and its inverse Note For large enough n, a random permutation is indistinguishable from a random function So in practice, PRPs are also good PRFs Do PRFs/PRPs exist?
They are a stronger primitive than PRGs though they can be built from PRGs In practice, block ciphers are used Will discuss extensively later Block ciphers Block ciphers are practical constructions of pseudorandom permutations
No asymptotics: F: {0,1}n x {0,1}m {0,1}m n = key length m = block length Hard to distinguish Fk from uniform f Permm even for attackers running in time 2n AES Advanced encryption standard (AES) Key length = 128, 192, or 256 bits
Block length = 128 bits Will discuss details later in the course Available in standard crypto libraries No real reason to use anything else CPA-security Fix , A Define a randomized expt PrivKCPAA,(n):
1. k Gen(1n) 2. A(1n) interacts with an encryption oracle Enck(), and then outputs m0, m1 of the same length 3. b {0,1}, c Enck(mb), give c to A 4. A can continue to interact with Enck() 5. A outputs b; A succeeds if b = b, and experiment evaluates to 1 in this case CPA-security
is secure against chosen-plaintext attacks (CPA-secure) if for all PPT attackers A, there is a negligible function such that Pr[PrivKCPAA,(n) = 1] + (n) CPA-secure encryption Let F be a length-preserving, keyed function Gen(1n): choose a uniform key k {0, 1}n Enck(m), where|m| = |k| = n:
Choose uniform r {0, 1}n (nonce/initialization vector) Output ciphertext < r, Fk(r) m > Deck(c1, c2): output c2 Fk(c1) Correctness is immediate r key
F ciphertext message pseudorandom
Security? Theorem: if F is a pseudorandom function, then this scheme is CPA-secure Note The key is as long as the message but the same key can be used to securely encrypt multiple messages
Security? Theorem: if F is a pseudorandom function, then this scheme is CPA-secure Proof by reduction See book for formal proof Here: high-level intuition m r {0,1}n
r, Fk(r) m m0 , m 1 b {0,1} r* {0,1}n r* , Fk(r*) m Analysis Since F is a pseudorandom function, we can
replace Fk with a truly random function f See book for details Analysis What is the success probability of A when the experimentuses a random function f? There are two sub-cases r* was used for some other ciphertext (call this event Repeat)
r* was not used for some other ciphertext Let q(n) be a bound on the number of encryption queries made by A Analysis Pr[success] Pr[success|Repeat] + Pr[Repeat] Pr[Repeat] q(n)/2n Why?
Pr[ success | Repeat] = Analogous to the one-time pad in this case, since f(r*) is uniform and independent of everything else Pr[A succeeds] + q(n)/2n I.e., the scheme is secure! Real-world security? The security bound we proved is tight
What happens if a nonce r is ever reused? What happens to the bound if the nonce is chosen non-uniformly? Attacks? If r repeats, security fails Exactly analogous to multiple encryptions using the (pseudo)one-time pad scheme
When r is a uniform, n-bit string, the probability of a repeat is negligible If r is too short, or is chosen from another distribution, repeats may happen! May make scheme insecure