Week 6

Question 1

What is Probability Distribution?

Answer 1

It is a function that maps events in some universe U to the range 0 to 1 inclusive. The sum of all probabilities is 1.

Question 2

What is a Uniform Distribution?

Answer 2

All elements have equal likelihood of being sampled. The probability of any one item being sampled is 1/|U| –> 1 out of the total number of elements.

Question 3

What is Point Distribution?

Answer 3

You alwatys get a specific x’ when sampling, so the probability of x’ is 1, and the probability of NOT x’ is 0.

An example is if you had a deck of cards made up of only kings. The probability that a king is sampled is 1, and not a king is 0.

Question 4

What type of distribution is this?

The probability that event A happens is equal to the size of elements in A divided by the size of elements in U.

Answer 4

Uniform Distribution

Question 5

Why is it that the probabability of an event A happening is equal to the size of elements in A divided by the size of the elements in U?

Answer 5

Because we basically take the number of elements we have, A, multiply it by tyhe probability of an event A happening, which is 1/|U|. and we get A/|U|.

Question 6

Say again we are sampling a 4-bit binary string. Event A is if we sample a string with the LSB being 1. We also say that each string is equally likely to be sampled.

What is the probability of event A happening?

Answer 6

We know that 8 strings have the LSB of 1, so we get 8/16 or ½.

Question 7

What is Union Bound?

Answer 7

A formula that gives us a way to bound the probability that either one event A1 or another event A2 will happen.

EXAMPLE:

Assume that you want to see if a password is going to be cracked. There are two ways that this could happen. Event A1 is the probability that the password is weak, and event A2 is the probability that the cryptography is broken.

If either event occurs, then there is an issue. Maybe the events are related too. Maybe if cryptography is broken, A1 becomes easier.

So, we give an upper bound by adding the two probabilities together, and when we can get the upper bound down to a reasonable, small probability in our system, then we know that whatever actual complex attempt someone has is bounded by a good number.

Question 8

When do we know if two events A1 and A2 are disjoint?

Answer 8

The probability of their intersection is 0.

Question 9

What is a Random Variable?

Answer 9

These are a function X that maps elements from some space U to some set V. These serve as a way to model things that are based on chance or non-determinism.

EXAMPLE:

Say you are writing a program to encrypt something with a random number. The random number can be described using a random variable.

Question 10

What are Uniform Random Variables?

Answer 10

Random Variables that are uniformly sampled. We use little R symbol on the arrow (as shown here) to indicate this.

These can be viewed as the identity function: X(y) = y for all y in U, the probability that x = y is 1/|U|. IT will always be 1/|U|.

Question 11

What does the formula for a Deterministic Algorithm look like?

How about a Randomized Algorithm?

Answer 11

Question 12

What does it mean to say that two sets A and B are independenty?

Answer 12

It means that they do not affect each other. If A and B are independent, then:

Pr[A intersect B] = Pr[A] * Pr[B]

Essentially, it’s the probability that both A and B happen. This is NOT the same as disjoint.

Question 13

What is Entropy?

Answer 13

The entropy of a variable is the amount of information in a variable.

Entropy is a lower limit, which is different than just the raw data like the number of bits we need to store information of a variable (that is the upper limit).

Consider a coint flip that is biased. Say we know the flip will always be heads. You don’t need sany bits to store this information because if it’s always heads, you can easily just always know it will be heads. HOWEVER, with a fair coin, you need to transmit a bit of information to let someone know what the results will be. There is only a 50% chance of guessing the outcome correctly.

For rolling a die, we need to transmit more bits of information because there is a probability of 1/6 for each outcome.

Question 14

What is Shannon’s Entropy?

Answer 14

The absolute minimum amount of storage/transmission needed to capture the information in some variable.

Question 15

Why do we care about entropy in security?

Answer 15

It is a good measure of how random a variable is. High entropy means higher randomness, which means a password is even harder to guess.

A coin flip has low entropy, it’s easy to guess.

For a die roll, guessing is comparatively harder (higher entropy).

Question 16

Why is entropy of passwords not as high as it could be?

Answer 16

People typically don’t pick completely random passwords.

Question 17

What happens when passwords are simpler, more standard ones, like “password”?

Answer 17

The intuition is that if a variable is more likely to be a certain value and it’s more likely to guess it without looking at it, the password variable has less information in it and takes fewer bits to transmit.

This means there is less entropy and it’s not a great password.

Question 18

What is the specific formula for Shannon’s Entropy Equation?

Answer 18

Say we have H(X) where X is some random variable, and it is over all the possible outcomes in the universe. So for each x, we have the probability that event x occurs * log₂(1/Pr[x]).

So H(X) is the sum of all the probabilities.

Then we have 1/Pr[x] which is the amount of information in each case (for each x).

Question 19

In Shannon’s Entropy Equation, why do we care about the reciprocal of 1/Pr[x]?

Answer 19

The information is the reciprocal of the probability because of the following. Consider the example below:

Imagine we have a fair coin flip and we get heads or tails. If the result is heads, we can eliminate the uncertainty of two total events (uncertainty of heads or tails). In the case of our coin flip if the probability of x is ½, and the reciprocal of that is 2.

Question 20

Example of using Shannon’s Entropy Equation.

Answer 20

Assume that a fair coin is flipped and has a uniform distribution over the universe of heads and tails.

We have some random variable x and the probability of x being heads or tails is ½.

So, with this information, we look at the Shannon entropy calculation shown below.

We sum both events, and the outcome is 1, which is expected since this is a uniform distribution, so we can’t make it easier to guess on a fair coin flip. It will always be 50/50

Question 21

What would happen if we considered a universe with a biased coin?

Answer 21

We have the same universe of heads and tails, but…

Pr[x=H] = 1/2 + e

where e is some value, and…

Pr[x=T] = 1/2 - e

Then we just plug these probabilities into Shannon’s equation.

Question 22

What does uniform probability do in terms of entropy?

Answer 22

As a general rule, it yields MAXIMUM uncertainty and therefore maximum entropy.

Question 23

What does a graph of Shannon Entropy for an epsilon that grows from 0 to 1/2 look like (when considering our coin flip scenario)?

Answer 23

We see that when e = 0, there is no change in the probabilities of the two sides, and it’s a fair flip with maximum entropy. It’s uniformly distributed.

As we increase epsilon, there is less and less entropy because our coin flip becomes more and more guessible. When e becomes as large as it can be (1/2), there is no uncertainty and no entropy.

Question 24

Why is it important that encryption algorithms are randomized?

Answer 24

Because it means you can encrypt the same msssage with the same key multiple times and get different ciphertexts.

Question 25

Are decryption algorithms deterministic or randomized?

Answer 25

Deterministic. You have to be able to reliably get back the same plaintext every time.

Question 26

When we talk about encryption algorithms and decryption algorithms, what are the common variables we need in our equations?

These are just letters that stand for the part of the encryption process they represent.

Answer 26

Question 27

Describe the outcomes of the XOR truth table:

0 0 =

0 1 =

1 0 =

1 1 =

Answer 27

0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0

Question 28

In one time pads, how do the lengths of the key space, message space, and ciphertext space compare?

Answer 28

They are all the same.

Question 29

How does the One Time Pad work?

Answer 29

1. We select some key K uniformly at random from the key space.
2. The encryption of some message M under the key K is just M XOR K. This returns some ciphertext C.
3. Decryption of C is simply C XOR K. This returns M, the original message.

Below is an example of XOR’ing bit strings.

Question 30

How do we define security for the OTP (short)?

Answer 30

The ciphertext should leave no information at all about the plaintext.

Question 31

In more depth, what does it mean for the OTP to be secure?

Answer 31

Some cipher, defined by the encryption algorithm E and the decryption algorithm D over spaces K, M, and C has perfect secrecy if for all messages M1 and M2 in the message space that are the same size and for all ciphertext C in the ciphertext space, the probability that the encryption of the first message M1 under key k mapped to ciphertext C is equal to the probability that the encryption message 2 under the same key maps to C.

This means, all plaintexts are equally likely to produce any ciphertext.

Question 32

Is the OTP considered secure? Why or why not?

Answer 32

YES! It is perfectly secret.

The reason is because we know that our key k is a uniform random variable. We just need to make sure the xor transformation preserves that uniform randomness and the result of the xor with a variable that is not uniform results in ciphertext that is uniformly random because we need our ciphertext to be indistinguishable for any plaintext and key.

So, this message says that if X is a random variable drawn from the space of all binary strings length n, and Y is independent from X and drawn from the same space, then the xor of them is also a uniform random variable.

Question 33

State the proof of OTP’s perfect secrecy where N = 1.

Answer 33

X is 0 or 1, and Y is 0 or 1.

The probability that Z = 0 is the probability that either x = 0 and y = 0 OR y = 1 and x = 1.

Question 34

What are the drawbacks of the OTP?

Answer 34

1. Perfectly secret implies the key length is >= the message length. If we have this, it implies that it must be equally likely that any message block from the plaintext could map to a ciphertext c’. This is a bad property because you don’t want to need a key that long. You have to distribute your keys and if you have a secure way to distribute them, you might as well use that same way for sending the message.
2. The keys can only be used once. You can’t just send everyone a key once. You need to send them a new key every time. This is because if an attacker saw two messages with two separate ciphertexts, the adversary could see both messages, xor them together, and then there is not a uniform random k value padding the messages, so we can no longer guarantee that M1 xor’d with M2 is a uniform random variable. The adversary could learn something about the distributions. See image below.

Question 35

Why do we learn about the OTP?

Answer 35

While it isn’t used much in practice due to its unreasonable restrictions, it’s still a great illustration of how randomness and probability work with ciphers.

Question 36

Does OTP have integrity?

Answer 36

NO!

Say Alice and Bob both share the key k, and Alice encrypts a message with a OTP. She sends it to Bob, but say the adversary intercepts the message.

What he can do is take the ciphertext, and then compute the xor by zoring it with something else, creating c’.

When he does this, he compromises the integrity of what is being sent to Bob, and Bob gets the wrong message.

Question 37

What do Stream Ciphers aim to address?

Answer 37

The aim to address the main drawback of the OTP, which is that the key needs to be as long as the message. It aims to take the idea of the OTP and make it practical by introducing some assumptions.

Question 38

What are the assumptions made when using the Stream Cipher?

Answer 38

The assumption is that we replace the random key in OTP with a pseudorandom key.

Question 39

What is a Pseudorandom Generator (PRG)?

Answer 39

G: {0,1}^s –> {0,1}ⁿ n >> s

It is a function that takes a random seed and produces a sequence of pseudorandom bits.

Example, take a seed that’s 256-bits and expand it into a million bits. In short, s (the cardinality of the seed set) must be much smaller than n (the cardinality of the possible outputs).

In short, given a small random seed, the PRG can produce the output efficiently and should be deterministically calculated.

The only random part is the pick of the seed. The output will then look random.

Question 40

How do Stream Ciphers work?

Answer 40

We have a PRG. We start with our key. We apply the PRG to the key. Imagine the small blue box below represents the key.

The PRG takes the key and generates many more random bits, G(k). We then XOR this sequence with the message to create our ciphertext c.

This is the same as the OTP with the exception that is uses a small truly random key to make a big key using the PRG.

Question 41

The Stream Cipher not only lets us encrypt a big message with a small key, but also…

Answer 41

Allows us to encryprt many messages with the same key.

For example, we take the small key, create our G(k), and then we use different chunks of G(k) to create our ciphertext by xoring each chunk with the chunks of the message/different messages.

Think of PRGs as generating all of the output at once like in the image below.

Question 42

When is a Stream Cipher secure?

Answer 42

ONLY when the PRG producing the random key is secure.

Question 43

What makes a cryptographic PRG secure?

Answer 43

The output of a PRG needs to be hard to predict having seen one of its previous outputs. The adversary should not be able to predict the next bit.

Question 44

When is a PRG G predictable?

Answer 44

If there exists an integer i and an efficient algorithm A such that if we give a prefix to the output, G(k)_1,…i then A can predict the remaining bits.

For example, if an algorithm A knows the orange portion below, it can then predict the remaining blue portion.

Question 45

State the proof that if a PRG is predictable, then the Stream Cipher is NOT secure.

Answer 45

This is a proof by contradiction.

Assume the PRG is predictable and the Stream Cipher IS secure. Say an attacker knows a small part of the message - the header.

In this case, the attacker can just do an XOR of the portion of the message they have and the key. Now we assume that the PRG is predictable. In this case, the attacker can determine the next bits of the key, and uncover the rest of the message. Therefore, the message is NOT secure if the PRG is predictable. This is a contradiction.

Question 46

What is the mathematical explanation of the proof that if a PRG is predictable, the Stream Cipher is not secure?

Answer 46

The adversart knows the prefix of the message m₁…m_i as well as the corresponding ciphertext for that portion.

The adversary computes the prefix G(k)_1…i by XORing the message prefix with the ciphertext prefix.

Since G(k) is predictable, the adversary uses the efficient algorithm A to compute the remaining bits of G(k)_i…n.

Given the remaining bits of the PRG key, the adversary can XOR them with the ciphertext to get the rest of the message.

Question 47

What is the formal definition of Predictability?

Answer 47

We say that a PRG G that takes a key as input and outputs some random bit string is predictable if there exists an efficient algorithm (polynomial time) and there exists an i > 1 and <= n - 1, such that given we sample a key uniformly from the key space, the probability that the algorithm generates the correct next bit is >= ½ + ∈ for some non-negligible value of ∈.

Question 48

What is an “advantage” when predicting the next bit?

Answer 48

The advantage is the non-negligible value ∈ over 1/2 that increases our chances of guessing the next bit.

Question 49

How do we define Unpredictability for a PRG?

Answer 49

It is the reverse of predictable. If the adversary does not have a non-negligible advantage ∈ when predicting the next bit, then they are essentially guessing the next bit at a rate of 1/2 and that is unpredictable.

Question 50

What is the definition of negligible/non-negligible advantage, ∈, in practice and in theory?

Answer 50

In practice, think of ∈ as a scalar.

In theory, ∈ is not a scalar. It is a function of a security parameter.

When we have a cryptosystem, there is a parameter that influences things, like how big a key needs to be. For example, in a PRG, the security parameter influences how big the input seed needs to be for the PRG to be secure. It won’t be secure if the input seed is only 1 bit, but it might be if it’s 1,000 bits.

The ∈ helps us capture how big the input key needs to be for the PRG to be secure or the steam cipher to be secure.

Question 51

When do we consider the advantage ∈ to be negligible?

Answer 51

We consider ∈ to be negligible when, as N tends toward infinity, the advantage goes to 0 faster than any polynomial function.

For example:

1/2ⁿ is negligible

1/2^sqrt(n) is negligible

1/n^log(n) is negligible

A function is otherwise non-negligible.

Question 52

Is f(n) = 1/x¹⁰⁰⁰ negligible?

Answer 52

No. It is non-negligible.

Question 53

Why do we draw the line at polynomials for advantage?

Answer 53

This is because in cryptography, we assume adversaries are computationally bound, meaning they can’t use infinite compute power and can only run algorithms in polynomial time. Exponential functions are too inefficient.

Question 54

What is the big difference between the OTP and Stream Cipher?

Answer 54

The OTP holds against all adversaries, even those with infinite compute power. But, the Stream Cipher could be broken by a negligible ∈ if the adversary had infinite compute power.