Cryptography CS 555 Topic 3: One-time Pad and Perfect Secrecy CS555

Cryptography CS 555 Topic 3: One-time Pad and Perfect Secrecy CS555 Spring 2012/Topic 3 1

Outline and Readings Outline One-time pad Perfect secrecy Limitation of perfect secrecy Usages of one-time pad Readings: Katz and Lindell: Chapter 2 CS555 Spring 2012/Topic 3 2

One-Time Pad Fix the vulnerability of the Vigenere cipher by using very long keys Key is a random string that is at least as long as the plaintext Encryption is similar to shift cipher Invented by Vernam in the 1920s CS555 Spring 2012/Topic 3 3

One-Time Pad Let Zm {0,1, ,m-1} be the alphabet. Plaintext space Ciphtertext space Key space (Zm)n The key is chosen uniformly randomly Plaintext X (x1 x2 xn) Key K (k1 k2 kn) Ciphertext Y (y1 y2 yn) ek(X) (x1 k1 x2 k2 xn kn) mod m dk(Y) (y1-k1 y2-k2 yn-kn) mod m CS555 Spring 2012/Topic 3 4

The Binary Version of One-Time Pad Plaintext space Ciphtertext space Keyspace {0,1}n Key is chosen randomly For example: Plaintext is 11011011 Key is 01101001 Then ciphertext is 10110010 CS555 Spring 2012/Topic 3 5

Bit Operators Bit AND 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 Bit OR 0 0 0 Addition mod 2 (also known as Bit XOR) 0 0 0 0 1 1 1 0 1 1 1 0 Can we use operators other than Bit XOR for binary version of One-Time Pad? CS555 Spring 2012/Topic 3 6

How Good is One-Time Pad? Intuitively, it is secure – The key is random, so the ciphertext is completely random How to formalize the confidentiality requirement? – Want to say “certain thing” is not learnable by the adversary (who sees the ciphertext). But what is the “certain thing”? Which (if any) of the following is the correct answer? – – – – CS555 The key. The plaintext. Any bit of the plaintext. Any information about the plaintext. E.g., the first bit is 1, the parity is 0, or that the plaintext is not “aaaa”, and so on Spring 2012/Topic 3 7

Perfect Secrecy: Shannon (Information-Theoretic) Security Basic Idea: Ciphertext should provide no “information” about Plaintext Have several equivalent formulations: – The two random variables M and C are independent – Observing what values C takes does not change what one believes the distribution M is – Knowing what is value of M does not change the distribution of C – Encrypting two different messages m0 and m1 results in exactly the same distribution. CS555 Spring 2012/Topic 3 8

Perfect Secrecy Definition 1 Definition 2.1 (From textbook). (Gen,Enc,Dec) over a message space M is perfectly secure if probability distribution over M message m M ciphertext c C for which Pr[C c] 0 We have Pr [M m C c] Pr [M m]. CS555 Spring 2012/Topic 3 9

Perfect Secrecy Definition 0 Definition. (Gen,Enc,Dec) over a message space M is perfectly secure if probability distribution over M The random variables M and C are independent. That is, message m M ciphertext c C Pr [M m C c] Pr [M m] Pr [C c] CS555 Spring 2012/Topic 3 10

Definition 0 equiv. Definition 1 Definition 0 implies Definition 1 – Idea: Given Pr [M m C c] Pr [M m] Pr [C c], for any c such that Pr [C c] 0, divide both sides of the above with Pr [C c], we have Pr [M m C c] Pr [M m]. Definition 1 implies Definition 0 – Idea: c C s.t. Pr[C c] 0 Pr [M m C c] Pr [M m], multiple both side by Pr[C c], obtain Pr [M m C c] Pr [M m] Pr [C c] c C s.t. Pr[C c] 0 we have Pr [M m C c] 0 Pr [M m] Pr[C c] CS555 Spring 2012/Topic 3 11

Perfect Secrecy. Definition 2. Definition in Lemma 2.2. (Gen,Enc,Dec) over a message space M is perfectly secure if probability distribution over M message m M (assuming Pr[M m] 0) ciphertext c C We have Pr [C c M m] Pr [C c]. Equivalence with Definition 0 straightforward. CS555 Spring 2012/Topic 3 12

Perfect Indistinguishability Definition in Lemma 2.3. (Gen,Enc,Dec) over a message space M is perfectly secure if probability distribution over M messages m0,m1 M ciphertext c C We have Pr [C c M m0] Pr [C c M m1] To prove that this definition implies Definition 0, consider Pr [C c]. CS555 Spring 2012/Topic 3 13

Adversarial Indistinguishability Define an experiment called PrivKeav: – Involving an Adversary and a Challenger – Instantiated with an Adv algorithm A, and an encryption scheme (Gen, Enc, Dec) Challenger k Gen() b R {0,1} Adversary chooses m0, m1 M m0, m1 C Ek[mb] b’ {0,1} PrivKeav 1 if b b’, and PrivKeav 0 if b b’ CS555 Spring 2012/Topic 3 14

Adversarial Indistinguishability (con’d) Definition 2.4. (Gen,Enc,Dec) over a message space M is perfectly secure if adversary A it holds that Pr[PrivKeavA, 1] ½ Proposition 2.5. Definition 2.1 is equivalent to Definition 2.4. CS555 Spring 2012/Topic 3 15

Perfect Secrecy Fact: When keys are uniformly chosen in a cipher, a deterministic cipher has Shannon security iff. the number of keys encrypting m to c is the same for any pair of (m,c) One-time pad has perfect secrecy (Proof?) – In textbook CS555 Spring 2012/Topic 3 16

The “Bad News” Theorem for Perfect Secrecy Plaintext space Cipherttext space Question: OTP requires key as long as messages, is this an inherent requirement for achieving perfect secrecy? Answer. Yes. Perfect secrecy implies that key-length msg-length Proof: Implication: Perfect secrecy difficult to achieve in practice CS555 Spring 2012/Topic 3 17

Key Randomness in One-Time Pad One-Time Pad uses a very long key, what if the key is not chosen randomly, instead, texts from, e.g., a book are used as keys. – – – – this is not One-Time Pad anymore this does not have perfect secrecy this can be broken How? The key in One-Time Pad should never be reused. – If it is reused, it is Two-Time Pad, and is insecure! – Why? CS555 Spring 2012/Topic 3 18

Usage of One-Time Pad To use one-time pad, one must have keys as long as the messages. To send messages totaling certain size, sender and receiver must agree on a shared secret key of that size. – typically by sending the key over a secure channel This is difficult to do in practice. Can’t one use the channel for send the key to send the messages instead? Why is OTP still useful, even though difficult to use? CS555 Spring 2012/Topic 3 19

Usage of One-Time Pad The channel for distributing keys may exist at a different time from when one has messages to send. The channel for distributing keys may have the property that keys can be leaked, but such leakage will be detected – Such as in Quantum cryptography CS555 Spring 2012/Topic 3 20

Coming Attractions Cryptography: Block ciphers, encryption modes, cryptographic functions CS555 Spring 2012/Topic 3 21