W3 Flashcards
Given two sequences {s_i}i and {t_i}i from LFSRs with characteristic polynomials P(x), Q(x), does there exist an LFSR with output matching {s_i + t_i}_i?
What is its characteristic polynomial?
Yes
LCM(P(x), Q(x))
If P(x) is the characteristic polynomial of an LFSR with degree n, and P(x) is irreducible and of order l, what is the period of all non-zero starting states?
The period is l itself.
What is the reciprocal of a function f(x)?
f^*(x) = x^n * f(1/x), where n is the degree of the polynomial
What is the generating function of a sequence {s_i}?
The generating function S(x) is defined as:
S(x) = sum from i=0 to i=infty of s_i * x^i
where s_i are the terms of the sequence and x is a placeholder variable
What is a condition on deg(P^*(x) S(x) for P(x) characteristic polynomial and state size n?
deg(P^*(x) S(x)) < n
What is an alternative definition of the characteristic polynomial?
Polynomial P of degree n such that when one multiplies the generating function by the reciprocal of P, one obtains a polynomial of degree less than n.
How is F(x) defined?
F(x) captures the first n terms of the sequence:
F(x)=s_0 + s_1 x + s_2 x^2 + ⋯ + s_(n−1) x^(n−1).
where (s_0,s_1,…,s_n) is the initial state
How does the A5/1 stream cipher work?
Three LFSRs with primitive characteristic polynomials that achieve some non-linearity by:
checking the values of s_12, t_11, v_10 and advancing only the LFSRs for which these check bits agree with the majority of check bits
by advancing, it means that the register’s internal state shifts by one position, and the output of the LFSR changes based on its feedback function
thus, at least 2 LFSRs advance per step
How does A5/2 differ from A5/1 in terms of security, nr of LFSRs, majority function and purpose?
Weakened Security: A5/2 was designed for export control and is weaker than A5/1. It can be broken instantly by certain algorithms.
Extra LFSR: A5/2 uses a fourth LFSR to clock the other three registers, introducing additional dependencies.
Majority Function: A5/2 incorporates extra inputs into the output sum, which are computed using the majority function of specific bits from the registers.
Purpose: A5/2 was specifically created for use in export markets, whereas A5/1 was intended for domestic use with stronger encryption.
What does it mean for one LFSR to clock other LFSRs?
When one LFSR clocks other LFSRs, it means the controlling LFSR determines when and whether the other LFSRs shift their bits during each clock cycle
Do LFSRs require some non-linear component to be secure?
Yes
How does RC4 work?
- Create a state array S of size 256, where S[i]=i for i=0 to 255
- Mix the key k (of length l) into S:
j=0
For i=0 to 255:
j = (j + S[i]+ k[i mod l]) mod 256
Swap S[i] and S[j] - Generate keystream:
Initialise i,j=0
For each keystream byte k:
Increment i: i=i+1 mod 256
Update j: j=j+S[i] mod 256
Swap S[i], S[j]
Generate the keystream byte as output = S[(S[i] + S[j]) mod 257]
What is the probability of a starting state in RC4 having S[2]=0?
What happens in RC4 when S[2]=0?
What is the probability of RC4 outputting a specific value v (not biased)?
Why does RC4 output 000 with a higher probability than expected?
1/256
If S[2]=0, the output will be 0 with a probability of 254/256. The only time when this is not the case is when S[1] is swapped with S[2].
For any other starting state, the probability of outputting v is 1/256.
The probability of outputting 0 is:
(1/256 * 254/256) + (255/256 * 1/256)
What is the first output byte biased on?
What danger does this bring?
The first key byte
If the plaintext has predictable formatting (i.e., starts with known characters), the attacker can deduce the first key byte by analsying ciphertexts
How is the sum of the third output byte and the first four key bytes biased?
How can this be harmful in Wired Equivalent Privacy (WEP)?
Biased towards 253
In WEP, the key is structured with the first three bytes being the Initialization Vector (IV) and the remaining bytes being the actual key.
Since the IV is known, the attacker can isolate and analyze biases in the fixed key portion (starting from the 4th byte)
What is Wired Equivalent Privacy (WEP)?
deprecated security protocol designed to provide data confidentiality for wireless local area networks (WLANs)
