Most important threat model for the class is CPA ( Chosen Plaintext Attack ) Eve can trick alice into encrypting arbitrary messages of eve’s choice we can adapt our experiment to account for this threat model
definition of confidentiality: even if eve is able to trick alice into encrypting messages, eve can still only guess what messages alice sent with a probability of 1/2
That definition is called IND-CPA ( indistinguishability under chosen plaintext attack )
Eve may choose plaintexts to send to alice and receives their ciphertexts
Enc(K, M) Key is K M is plaintext message
Eve issues a pair of plaintexts M0 and M1 to alice alice randomly chooses either M0 or M1 to encrypt and sends the ciphertext back alice does not tell eve which one was encrypted eve may again choose plaintexts to send to alice and receives their ciphertexts. eventually, eve outputs a guess as to whether alice encrypted M0 or M1
How does eve guess whether M0 or M1 was encrypted? what strategy does she use? EASILY she guesses ts and i predicted it from the MOMENT he showed that slide. assuming same key every time, on a deterministic algorithm, of course. deterministic algorithms cannot satisfy ind-cpa.
proving security: for all attackers / eve-s the probability of winning the ind-cpa game is at most 1/2
cryptographic schemes are usually allowed to leak the length of the message to hide length: all messages must always be the same length: if you have a 16 byte message vs 1gb message, we dont want to send a 1gb thing for a 16 byte message, and we dont want to chunk 1gb into 16 byte segments, so length hiding is unpractical
in the ind-cpa game, m0 and m1 must be the same length in engima: no rotor maps a letter to itself the reflector never maps a letter to itself this property is ncessary for enigma’s mechanical system to work if there are no ‘A’ characters, it was M0 if there are no ‘B’ characters, it was M1
one time pads are the first symmetric key encryption algorithm we will cover
one time pads are keys that only get used once per message
stream ciphers are in common libraries
one time pads are theoretically secure, and proven secure. practically no one is using them.
xor, if your inputs are the same, you get 0, if your inputs are different, you get 1.
x xor 0 = x x xor x = 0 x xor y = y xor x (x xor y) xor z = x xor ( y xor z ) (x xor y ) xor x = y so, if you x xor y you have a ciphertext and then you xor x again and you have decrypted it
one time pads: key gen
key k is randomly hosen bitstring plaintext m is bitstring you want to encrypt
problems with one time pads:
- key gen, for security o hold keys must be randomly generated for every message, and randomness is expensive, for a 1gb message you need a 1gb key to xor with
- key distribution, to communicate an n bit messsage, you need to securely communicate the key first, but if we had a way to securely communicate the key, we could have sent the message directly