Week 2 Part 1 Flashcards
Explain what perfect secrecy is? and what’s another name for it?
Information-Theoretic Secrecy
- No matter how powerful the attacker can be, secrecy holds!
- Perfect Secrecy is achievable but very expensive and not practical
- The ciphertext does not reveal any new information about the message
What is one of the simplest ciphers that gives you perfect secrecy?
One-Time Pad (Vernam) Cipher.
What are the pros and cons of the one-time pad (vernam) cipher?
Pros:
- ciphertext reveals no information about the plaintext (perfect secrecy)
Cons:
-key has to be as long as the plaintext and truly random
- Insecure against two-time pad (if same key used twice)
How can you prove that the one time pad (vernam) cipher is secure?
Bayess theorem
Encryption and Decryption of onetime pad vernam cipher?
- Encryption: Enck(m) = m ⊕ k
- Decryption: m = Deck(c) = c ⊕ k
(you just XOR)
What are the limitations of perfect secrecy?
- The key has to be truly random
- We must have |K| ≥ |M|
- Each key can only be used once
What is computational secrecy?
- allow a very small (negligible) probability of security failure
- protect against “efficient” adversaries (not unrestrictedly powerful)
What do modern ciphers use to overcome a two-time pad attack?
Nonce (- A non-repeating value for a given key)
What is a pseudo-random generator?
PRG is an efficient deterministic algorithm that expands random n-bit strings into random-looking (pseudo-random) p(n)-bit strings
What is one way to obtain a Pseudo-random generator?
Linear Feedback Shift Register (LFSR)
How does a Linear Feedback Shift Register (LFSR) work?
- xoring different bits and the last bit looks random without the other bits
For an l - bit LFSR, what is the maximal period we can hope for?
2^l -1 (2 to the power of l minus 1)
Assuming we start from the state 0100, what is the state after 3 ticks?
0010
After some ticks, an LFSR’s previous state will re-occur ⇒ the same bit stream (output) will repeat, when does 0010 start repeating?
After the 5th tick
What are the limitations for LFSR?
- If the coefficient of the LFSR are known, by knowing 1st n-bits of the output, one can recover the starting state
- if the coefficient of the LFSR are not known, by knowing 1st 2n bits of the output, one can recover the starting state and the coefficients using (Linear Algebra powerful against linear functions)
How to make an LFSR secure?
A number of LFSRs are combined using a non-linear function
A sender has encrypted the character“C”(ASCII code: 67) using a stream cipher. In transit, an attacker (who does not know the used key) has XORed the ciphertext with the integer number 2. What character will the recipient get when they perform decryption on this altered ciphertext?
A. because a stream cipher encrypts with the equation c = m ⊕ PRG(k), if we substitute 67 for m we get: c= 67 ⊕ PRG(k). The attacker XOR this message with 2 so he gets c= (67 ⊕ PRG(k)) ⊕ 2. The equation to decrypt is m = c ⊕ PRG(k) . If we substitute the equation we got for c we get m = ((67 ⊕ PRG(k)) ⊕ 2)⊕ PRG(k). By using the commutative and associative property, we can simplify this expression to get m= 67 ⊕ 2, m= 65. The corresponding letter for that ASCII code is A
Assume that in the one-time pad (Vernam) cipher we have replaced the XOR operation with the Boolean OR operation. If the probability of the plaintext bit being 0 is 0.3, i.e. Pr[M=0]=0.3, what is the probability of the ciphertext bit being 1, i.e. Pr[C=1]?
According to the boolean OR, the ciphertext is 1 if there is 1 in the plaintext or the key or both. so Pr[C=1] = Pr[M=1] + Pr[K=1] - Pr[M=1]*Pr[K=1] .
if we substitute in the values: Pr[C=1] = 0.7 + 0.5 - 0.7*0.5 =0.85. How I got the values: Pr[M=0] = 0.3 then Pr[M=1] = 0.7 as per the rule Pr[M=0] + Pr[M=1] = 1
Pr[K=1] = 0.5 because its equally likely to be any
A 4-bit LFSR has the connection polynomial X^4+ X^3+ 1, what is the period of this LFSR? And how do u calculate
15, either manually by hand see how long it takes to repeat or code:
P.<x> = GF(2)[ ]</x>
c = x^4 + x^3 + 1
for i in range (4,16):
if c.divides(x^i + 1):
print(“The period is: “, i)
break
An LFSR has a connection polynomial which is irreducible and is of degree 6, which of the following cannot be the period of this LFSR? 5, 63 , 7
The period of an irreducible polynomial C(X) of degree n divides 2^n − 1. 2^6-1 is 63. 7 and 63 divide 63 but 5 does not. so the answer is 5.
When is a polynomial irreducible
A polynomial is irreducible if it cannot be factored
C(X) = X4 + X2 + 1 is this polynomial irreducible and/or primitive (why or why not)?
C(X) here is reducible (hence cannot be primitive) since we can factor it since X4 + X2 + 1 = (X2 + X + 1)(X2 + X + 1)
What are pros and cons of stream ciphers?
Pros;
- Efficient & can be easily implemented in hardware (Involve cheap operations, e.g. XORing, bit shifting)
- No need to buffer data before applying stream ciphers (e.g. useful when the plaintext length is not known beforehand)
- Low error propagation (An error in a ciphertext symbol affects one symbol of plaintext)
Cons:
- Does not offer integrity (Adversary can alter the underlying plaintext by altering ciphertext)
- Low Diffusion (One symbol in plaintext is mapped to one symbol in ciphertext)
Can stream ciphers be used for cryptographic purposes?
NO, theyre not secure
Whats the encryption and decyrption formula for a stream cipher
- Encryption: c = m ⊕ PRG(k)
- Decryption: m = c ⊕ PRG(k)
(XOR 3 & 4th) for a bit LFSR.
If the starting state is 1000, what is the bit stream produced by the above LFSR after 6 clock ticks? You also need to show the state of the LFSR at each tick.
0100 0
0010 0
1001 0
1100 1
0110 0
1011 0
Output bit stream:
000100
X^4 + X^3 + 1 What is the period (i.e. how many clock ticks before it cycles) of this LFSR?
The period of the LFSR is that of its connection polynomial. Since the degree of the polynomial in this case is irreducible and primitive, it will have a maximal period, i.e. 2^4 − 1 = 15
