22-03-2011, 09:56 AM
presented by:
Gregory Greenman
[attachment=10702]
LFSR structure
Purpose - to produce pseudo random bit sequence
Consists of two parts :
shift register – bit sequence
feedback function
Tap Sequence :
bits that are input to the feedback function
LFSR Features
LFSR Period – the length of the output sequence before it starts repeating itself.
n-bit LFSR can be in 2n-1 internal states è the maximal period is also 2n-1
the tap sequence determines the period
the polynomial formed by a tap sequence plus 1 must be a primitive polynomial (mod 2)
A5/1 Overview
A5/1 is a stream cipher, which is initialized all over again for every frame sent.
Consists of 3 LFSRs of 19,22,23 bits length.
The 3 registers are clocked in a stop/go fashion using the majority rule.
A5/1 : Operation
All 3 registers are zeroed
64 cycles (without the stop/go clock) :
Each bit of K (lsb to msb) is XOR'ed in parallel into the lsb's of the registers
22 cycles (without the stop/go clock) :
Each bit of Fn (lsb to msb) is XOR'ed in parallel into the lsb's of the registers
100 cycles with the stop/go clock control, discarding the output
228 cycles with the stop/go clock control which produce the output bit sequen
The Model
The internal state of A5/1 generator is the state of all 64 bits in the 3 registers, so there are 264-1 states.
The operation of A5/1 can be viewed as a state transition :
Standard attack assumes the knowledge of about 64 output bits (64 bits →264 different sequences).
Space/Time Trade-Off Attack I
Get keystream bits k1,k2,…,kM+n and prepare M subsequences :
Select R random states S1,..,SR and for each state generate an n-bit keystream
Shamir/Biryukov Attack Outline
2 disks (73 GB) and 2 first minutes of the conversation are needed. Can find the key in less than a second.
This attack based on the second variation of the space/time tradeoff.
There are n = 264 total states
A – the set of prepared states (and relevant prefixes)
B – the set of states through which the algo. proceeds
The main idea :
Find state s in A∩ B (the states are identified by prefix)
Run the algorithm in the reverse direction
Biased Birthday Attack
Birthday paradox : A ∩ B ≠ o if |A| ∙ |B| ≈ n
Each state is chosen for A with probability PA(s) and for B with probability PB(s). Then, the intersection will not be empty if Σs PA(s) ∙ PB(s) ≈ 1
The idea is to choose the states from A and B with 2 non-uniform distributions that have correlation between them
Special States
Disk access is very time-consuming!
Keep on disk (set A) only those states, which produce a sequence that starts with a certain pattern α, | α| = k
Access the disk only when α is encountered
2k prefixes can start with α, so we reduce the number of total possible states (n) by 2k and the number of disk access times by 2k. The size of A, however, is unchanged, and we only insert the states that satisfy the condition there. Thus, we don't miss intersections.
Gregory Greenman
[attachment=10702]
LFSR structure
Purpose - to produce pseudo random bit sequence
Consists of two parts :
shift register – bit sequence
feedback function
Tap Sequence :
bits that are input to the feedback function
LFSR Features
LFSR Period – the length of the output sequence before it starts repeating itself.
n-bit LFSR can be in 2n-1 internal states è the maximal period is also 2n-1
the tap sequence determines the period
the polynomial formed by a tap sequence plus 1 must be a primitive polynomial (mod 2)
A5/1 Overview
A5/1 is a stream cipher, which is initialized all over again for every frame sent.
Consists of 3 LFSRs of 19,22,23 bits length.
The 3 registers are clocked in a stop/go fashion using the majority rule.
A5/1 : Operation
All 3 registers are zeroed
64 cycles (without the stop/go clock) :
Each bit of K (lsb to msb) is XOR'ed in parallel into the lsb's of the registers
22 cycles (without the stop/go clock) :
Each bit of Fn (lsb to msb) is XOR'ed in parallel into the lsb's of the registers
100 cycles with the stop/go clock control, discarding the output
228 cycles with the stop/go clock control which produce the output bit sequen
The Model
The internal state of A5/1 generator is the state of all 64 bits in the 3 registers, so there are 264-1 states.
The operation of A5/1 can be viewed as a state transition :
Standard attack assumes the knowledge of about 64 output bits (64 bits →264 different sequences).
Space/Time Trade-Off Attack I
Get keystream bits k1,k2,…,kM+n and prepare M subsequences :
Select R random states S1,..,SR and for each state generate an n-bit keystream
Shamir/Biryukov Attack Outline
2 disks (73 GB) and 2 first minutes of the conversation are needed. Can find the key in less than a second.
This attack based on the second variation of the space/time tradeoff.
There are n = 264 total states
A – the set of prepared states (and relevant prefixes)
B – the set of states through which the algo. proceeds
The main idea :
Find state s in A∩ B (the states are identified by prefix)
Run the algorithm in the reverse direction
Biased Birthday Attack
Birthday paradox : A ∩ B ≠ o if |A| ∙ |B| ≈ n
Each state is chosen for A with probability PA(s) and for B with probability PB(s). Then, the intersection will not be empty if Σs PA(s) ∙ PB(s) ≈ 1
The idea is to choose the states from A and B with 2 non-uniform distributions that have correlation between them
Special States
Disk access is very time-consuming!
Keep on disk (set A) only those states, which produce a sequence that starts with a certain pattern α, | α| = k
Access the disk only when α is encountered
2k prefixes can start with α, so we reduce the number of total possible states (n) by 2k and the number of disk access times by 2k. The size of A, however, is unchanged, and we only insert the states that satisfy the condition there. Thus, we don't miss intersections.
