|
Matrix GF2 Algebra On A5/1 Explained III By Juan Chamero, juan.chamero@intag.org, as of April 2006 How to Get the Keyword once
known one Another
A5/1 weakness provides a statistical attack shortcut Registers R1, R2, and R3 shift
at random, anyhow in a statistically regular fashion. For example when mixing
100 time steps in the average each one shifts 75 times and stops 25. If each Ri shifts around its mean with dispersion Sigma (i) we may select n(i) at random
alternatives for each shift value having n^3 possible states along 100 steps
for n=n(1)=n(2)=n(3). Not too much if we compute backwards along trees. The
idea is to use matrices alternatively: State Transition Matrices Ci(j=>k)
that transform State Si(j) in Sate Si(k) as follows: Ci(j=>k)*Si(j) = Si(k), for k>j, and
conversely with its inverse C´ C´(k=>j)*S(k)
= Si(j) Let’s be then [72 73, 74, 75,
76, 77, 78] the spectrum interval of possible random shifts summa values [d1 d2
d3] for registers R1, R2, and R3. Being
all shift counts equally probable we may go forward “via matrices” from a given
state, for instance S(86), through all the 7^3 Cartesian
Product shift triads to their corresponding 7^3 S(186) states. With a high
probability one of these states will match the one that corresponds to that
state S(86) running 100 time steps throughout the A5/1
algorithm. The same will apply for going
backwards from a given S(186) state. How such those
matrices C look like? They are rather simple
structured. The basic shift operates in two “virtual steps”, first shifts to
its left, from lsb to mlb
one position that represents a multiplication by 2 modulo 2^n, in this case 2^19,
2^22, and 2^23 for registers R1, R2, and R3 respectively. Second inserts as lsb the XOR of their corresponding Tab bits: Warning: We say “virtual steps” because both
operations, the shift and the feedback computation and insertion are
simultaneous. Si(j
+ 1) = Ci*Si(j) With Ci
stands for r(i)xr(i) matrices being r(i) their respective registers’ range. In our A5/1 case C1
(19x19), C2 (22x22), and C3 (23x23). As tab bits are 18, 17, 16, and 13 for R1
its C1 matrix would be: 0
1 0 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 1 1 0 0 1 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 1 0 0 0 0 1 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 1 0 0 0 0 1
0 0 0 0
0 0 0
0 0 0
0 0 0
0 1 0 0 0 0 0 0 1 0 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0
0 0 0
0 0 0
0 0 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0
0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0
0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0
0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Note: Each row except last is a mask to catch a bit at
a time virtually multiplying its “position value” by module 2^19 The powers of these matrices
will traverse as many states as its power index. So Ci^3 applied to Si(11)
will drive us to state Si(14). In the general case to
jump k states starting from any known state could be performed by matrices. As
we are working in GF2 and any number k could be expressed in this base, to create
any C^k matrix we only need k components, namely: k
= 21 ó
1 0 1 0 1 ó
C^21 = C^16*C^4*C^0 For our needs in this analysis
(up to 100 state transformations) we only need to have pre computed the
following basic module 2 matrices for each register: C C^2
C^4 C^8 C^16
C^32 C^64 Enough computing math resources
to cover jumps of up to 127 steps!. No problem with 2^n steps: the iterative
process C <= C^2, executed n times. Algorithm to
Generate C basic powers Define the tri-dimensional
array C(i, j, h) /in C(i, j, 0) we define the First State Transition Matrix/ /in C(i, j, h) we define the (h – 1) Transition Matrices/ h = 0, /h from 1 to H,
maximum programmed jump (177) between states/ Do while h<=H, h++ i
= 0 Do while i<=n, i++ j = 0 Do while j<=n, j++ C(i, j, h + 1) = 0 k=0 Do while k<n, k++ C(i, j, h + 1) = C(i, j, h+1) + C(i, k, h)*C(k, j, h) /Optionally list below/ List all h planes /List C matrices corresponding
to powers: 2^0, 2^2, 2^2, 2^3, , …, 2^H/ DATA INPUT: C1(0):
[010………0], [001……………0], …….., [000……………1]; [1110010000000000000] being 19x19 C2(0):
[010………0], [001……………0],………. [000…………
1]; [1100000000000000000000] being 22x22 C3(0):
[010………0], [001……………0],………. [000…………
1]; [11100000000000010000000] being 23x23 Standard and non standard
Shift Registers Logic We have found the logic of our
shift registers working at standard mode, meaning in two virtual steps to
complete each iteration as follows: Si(j + 1) = Ci*Si(j) that in fact implies two things: shift one position
to the left, leaving the lsb of Register Ri “vacant”, to be filled with the Tap bits XORed enabling
the whole pseudo random cycle. We are going to check all this reasoning for a 4
position shift register to see what we mean saying standard mode in order to
introduce the algebra of a more complex mode as used in the first 86 steps of
A5/1 algorithm. n = 4 Cycle: 2^4 –
1 = 15 Seed: 0001 1
0001 2
0010 3
0100 4
1001 5
0011 6
0110 7
1101 8
1010 9
0101 10
1011 11
0111 12
1111 13
1110 14
1100 15
1000 16 0001 17 ……. The corresponding 4
“Characteristic” matrices are:
Si(11)
= (C^4)*Si(7) =>
Warning: In this algebra the multiplication of bits
(represented either by (.) or (*)) corresponds to the “logic product” (AND)
meanwhile the SUM corresponds to the XOR operator (represented either by (+) or
same symbol within a circle). For both operators are valid the associative
property: C^k*(C^h*S(j) + K) = C^*(k + h)S(j) + C^k*K As explained we may combine positional
characteristic matrices in order to obtain any “jump” in distance between any
pair of states. For example the operator C^11 could be obtained by multiplying
C^8*C^2*C^1 giving the jump [1011] obtained by the corresponding truth values (C^8
(True), C^4(False), C^2(True), C^1(True)). Unconventional
Use of Shift Registers A5/1 uses Shift Registers in
several modes. In the beginning registers are XORed bit per bit, in parallel,
from Kc first and then from Frames counter. This is
equivalent to insert a random Tap bit with an unknown content that is equivalent
to an exogenous intrusion. Let’s try to unveil the algebra of this mode. We are going to compute “by
hand” all the possible outputs when triggered by an arbitrary Kc, for example [0001]. We have to take into account that
initially registers are zeroed. Kc: 0001 S(0): 0000 S(1): 0001 S(2): 0010 S(3): 0100 S(4): 1001 Kc: 1101 S(0): 0000 S(1): 0001 S(2): 0010 S(3): 0101 S(4): 1010 Once understood the procedure XORing the designed tap bits with the bits from Kc, one at a time, we may generate the following
correspondences:
Recursively we may obtain this
series performing the following recursion: S(0)
= 0 S(1)
= C*0 + K1 S(2)
= C*S(1) + S(3)
= C*S(2) + K3 S(4)
= C*S(3) + K4 Where the Kj
are n size vectors (for our example n = 4) with all zeroes except the lsb that is the Kc(j) bit, from right (lsb) to left.
In our example: K1: [0 0 0 Kc(1)] first bit from right
side K3: [0 0 0 Kc(3)] third bit from right
side K4: [0 0 0 Kc(4)] fourth bit from right
side S(4) = C*(C*S(2) + K3) +
K4 => C*(C*(C*S(1) + C*(C*(C*(0
+ K1) S(4) = C^3*K1 + C^2* And in general for n = 64 S(64) = C^63*K1 + C^62* Let’s now go back to our
example: S(4) = C^3*K1 + C^2* | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||