module 6

Question 1

entropy

Answer 1

amount of information in the variable

shannon’s entropy: the absolute minimum amount of storage / transmission needed to capture the information in some variable

entropy is a good measure of how “random” (strong) a password is

Question 2

How does the one time pad work?

Answer 2

• you have a message M made up of n bits
• you have a key made up of n bits, distributed uniformly at random
• you encrypt your message by XORing it with the key
• you decrypt by XORing the encrypted message with the key

Question 3

What is Shannon’s information theoretic security?

Answer 3

ciphertext should leak no information about the plaintext

A cipher (E,D) over (K,M,C) has perfect secrecy if:

For all messages m1, m2 in the message space that are the same size and all ciphertexts c in the ciphertext space: the probability that the encryption of m1 to ciphertext c is the same as the probability that the encryption of m2 to ciphertext c, where the key k i selected uniformly at random

Question 4

Explain why OTP is perfectly secret.

Answer 4

Lemma: If X is a random variable on {0,1}^n and Y is an independent uniform random variable on {0,1}^2 then Z=X XOR Y is a uniform random variable on {0,1}^n

Question 5

What are the issues with OTP?

Answer 5

1. perfect secrecy implies that key length >= message length: you don’t want to have a key that is the same length as your message
2. keys only work once. else,

Question 6

What does it mean that OTP has no integrity?

Answer 6

an adversary can intercept and corrupt the message

Question 7

what is a stream cipher?

Answer 7

any cipher that has perfect secrecy must have really long keys…

proposed solution: take idea of OTP and make it practical by introducing some assumptions that we believe hold in practice

key idea: replace random key in OTP by pseudorandom key

Question 8

PRG: pseudorandom generator

Answer 8

a PRG is a function that takes a random seed and generates pseudorandom bits

G: {0,1}^s –> {0,1}^n, where n&raquo_space; s

Question 9

key property of PRG:

Answer 9

1. given a small random seed, one can compute output of PRG efficiently with a deterministic algorithm
2. the output of PRG looks random (we will revisit later)

**only the seed (or input) to the function is actually random

Question 10

can stream ciphers guarantee perfect secrecy?

Answer 10

no.
perfect secrecy implies that your keys need to be as long as the message. this will not be the case with a stream cipher.

Question 11

we know that a stream cipher is secure if PRG is secure. so, what is a good definition for a secure cryptographic PRG?

Answer 11

very important property:
unpredictability

adversary cannot predict the next bit

informally: a PRG is predictable if there exists an integer i and an efficient algorithm A such that the given the prefix of the output an algorithm can predict the rest
G(k)_i,…,i – A –> G(k)_i,…,n

if G is predictable, stream cipher is not secure

Question 12

high level proof for:

if G is predictable, stream cipher is not secure

Answer 12

1. suppose PRG G is predictable and stream cipher is secure
2. suppose the attacker knows a small part of the message
   - -> common for many protocols (e.g. Web protocols have common headers)
3. attacker can use knowledge of small part of message and ciphertext c to deriver output of G for that part of the message (via message), this is the same as saying that the attacker knows the prefix of the output of the pseudorandom generator
4. since G is predictable, attacker can determine the next bit and recover the rest of the message.

THEREFORE, stream cipher is not secure. Which is a contradiction.

Question 13

define predictability formally.

Answer 13

if an algorithm is even a tiny tiny bit better than predicting the next bit correctly half the time
so 1/2 plus some epsilon

Question 14

when is a PRG unpredictable?

Answer 14

for all i, no “efficient” algorithm can predict bit i + 1 with non negligible E.

Question 15

informal definition of negligible vs. non negligible

Answer 15

Question 16

theoretical definition of E

Answer 16

epsilon is a function of a security parameter (e.g. length of the key)

a function is negligble f(n): is a function that not only tends toward 0 as n appropaches infinity but does so faster than the inverse of any polynomial (1/poly(n))

examples of negligible functions: 1/2^n, 1/2^sqrt n, 1/n^log(n)

Question 17

are the following negligible?

Answer 17

Question 18

why do we draw the line at polynomial?

Answer 18

because modern cryptography assumes computation adversaries

• -bounded computational power
• -such adversaries can only run efficient (i.e., polynomial) algorithms

big difference between OTP and stream cipher

• -OTP is secure against a computationally unbounded adversary
• -stream cipher is secure only against a computationally bounded adversary

Question 19

Kerckhoff’s principle

Answer 19

it is desirable that both the encryption and decryption functions are public knowledge and that the secrecy of the message, given the ciphertext, depends totally on the secrecy of the secret key, k.

Question 20

symmetric key system

Answer 20

both parties need access to the secret key

Question 21

why should the key be at least 80 bits to avoid exhaustive search by the attacker?

Answer 21

it is commonly assumed that a computation taking 2^80 steps will be infeasible for a number of years to come, hence the key space size should be at least 80 bits to avoid exhaustive search