Week 4
IND-CPA security for Symmetric Encryption
Doesn’t model integrity among other things.
PRP-PRF Switching Lemma
This is PRP security:
PRF security: distinguish between random key and a random function.
PRP security: distinguis between random key and random permutaiton.
A function is not a permutation, but a permutation is a function.
This is PRF security:
If the input is the same as from previous values, then output the same as then, if not then choose new function. Did not get this fully.
Lemma:
The absolute difference between these definitions is q2/2n+2.
(The “+2” is from the advantage definition to normalize so it goes from 0 to 1)
Pr[b=0] = 1/2
Pr[b=1] = 1/2
Pr[b’=1|b=0] = probability that b’=1, given that b=0
Proof of PRF switching lemma:
Both games together: (Always the same except a repeated value occurs in G2 as Yi)
Difference Lemma
Complete the switching lemma proof
These 2 lemmas occur again and again and again so try to understand it.
Proof of Security for CTR mode
IND-CPA security for CTR mode: G0
IND-CPA security for CTR mode: G1
This is no longer using a block cipher, he is using a random permutation. The adversary can’t tell a difference between game G0 and G1. Any adversary that could, he could then distinguish the block cipher from a random permutation, that would break the security, that is not possible.
IND-CPA security for CTR mode: G2
Here we change the random permutation with a random function.
IND-CPA security for CTR mode: G3
Here the advantage of the adversary is 0. This is essentially a one-time pad.
As long as there is no repeating counter value between G2 and G3, then they are equal (can’t tell them apart).
Intuition of the images:
-
The proof involves a sequence of games G 0 , … , G 3 .
-
Each game is played between a fixed IND-CPA adversary A and a challenger.
-
We change the operation of the challenger slightly as we transition between different pairs of games.
-
In G 0 , the challenger is just the normal IND-CPA challenger for CTR mode.
-
In G 3 , the challenger uses one-time pad encryption, so A’s advantage is zero.
-
We show that in each transition, A’s advantage cannot change much.
-
Since the advantage is zero in G 3 , the advantage in G 0 must be small.
-
We will formalise this intuition and be concrete about “small”.
Formal proof
bounding |p0 - p1|
The IND-CPA challenger outsources the ciphertext it needs to encrypt a message to the PRP challenger C.
If d = 1 in the PRP challenger, then its the same game as G1. Because it just does a random permutation.
The challenger doesn’t use its key. The keyGen is in the Challenger C, it isn’t on the slides but it should be there.
He uses the key for the encryption.
Bounding |p1 - p2|
Bounding |p2 - p3|
When d is 0, we are in game G2. When d is 1, we are in game G3.
The probability of Z is very small, the counter values are chosen uniformly at random. So to get a value twice is very unlikely.
Combining everything
Lecture 10
-
Padding and padding oreacle attacks
-
Attacks on CBC mode with non-random IV
Padding
Applies an injective map pad() to messages prior to CBC mode encryption, remove padding after decryption.
If the message was already block length. We need to add a complete block that is only padding. That block is 16 copies of OXOF. 16 because the block size in AES is 128 bits which is 16 bytes.
If the padding would be wrong, then the server could send a error message “bad padding”. The padding could be incorrectly formated because an adversary changes something.
That opens the door to a padding oracle attack.
The target block could be any block from the ciphertext. Doesn’t necessarily have to be the last block. C(t) does not have to be the last block in the ciphertext.
We need to get 0x00, that means padding is valid. By chance we could also hit 0x01, 0x01 in the last 2 or 0x02, 0x02, 0x02 in the last three. But that is highly unlikely and we could check that with one more query.
Then we continue from there, set the last byte to 0x01 and change the second last byte until you get “valid”, which means you have recovered 2 bytes.
Worst case cost of this attack: 256 queries to the oracle for each byte you want to recover.
This is a plaintext recovery attack, not a key recovery attack.