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 tridimensional
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* Let us deep a little in these
n products of a transition matrix by vectors that only have a meaningful
component (0 or 1) in its last position. In fact for any C^(nh)*Kh, for instance C^3K1, the n size vectors components result
from the product of the coefficients of the last column by Kc(j).
For our example we have:
We appreciate that product of
matrices by keyword bits vectors K are reduced to a match between the last
column of matrices that with their 1’s signal where to insert the corresponding
bit kj of Kc(j). The states are then computed as a result of XORing the following 4 (n) vectors:
And in the general case the XORing of n vectors of n bits each. Algebraically the
linear combinations are as follows: For n=4: First Vector: [C3(1 4).k1,
C3(2 4).k1, C3(3 4).k1, C3(4 4).k1] Second Vector: [C2(1 4).k2, C2(2
4).k2, C2(3 4).k2, C2(4 4).k2] Third Vector: [C1(1 4).k3,
C1(2 4).k3, C1(3 4).k3, C1(4 4).k3] Fourth Vector: [C0(1 4).k4, C0(2
4).k4, C0(3 4).k4, C0(4 4).k4] Where the C0´s are all zeroes, except C0(n n) = 1. As we XOR them column by column we have the
following expressions for state S(n): S(4,
1) = C3(1 4).k1 + C2(1 4).k2 + C1(1 4).k3 + 0 S(4,
2) = C3(2 4).k1 + C2(2 4).k2 + C1(2 4).k3 + 0 S(4,
3) = C3(3 4).k1 + C2(3 4).k2 + C1(3 4).k3 + 0 S(4,
4) = C3(4 4).k1 + C2(4 4).k2
+ C1(4 4).k3 + k4 And in general: S(64,
j) = C63(j 64).k1 + C62(j 64).k2 + C61(j 64).k3 + ……+ C1(j 64). k63 + k64 This could be synthesized by the expression: S(n)
= C64*K Where C64 is the matrix formed by the last columns of the (n1) matrices
from C^1 to C^(n1) with its right most column the
unity vector [0 0 …….01], and K = Kc.
Now knowing S(n) we may unveil K by inverting C64: K = C64´*S(n) C64 and C64´ have 4096 coefficients but is a sparse matrix, plenty of
zeroes. Transition Matrices for A5/1
Algorithm Our aim now is to show how
this matrix approach works for states defined via concatenation of several
Shift Registers complicated by mixing Tap bits XORing
with exogenous bits, for instance entering in parallel, bitwise two strings
corresponding to a private and a public key. We are going to see how it works in
a simplified scheme of three small registers: R1
[b3 b2 b1 b0]; R2
[b2 b1 b0]; R3
[b1 b0] S(t):
R1(t)OR2(t)OR3(t) ó
[b31(t) b21(t) b11(t) b01(t) b22(t) b12(t) b02(t) b13(t) b03(t)] That is we may deal with
registers as separate entities only linked to generate “output” bits by XORing bits coming out from most significant bits of three
registers in the next cycle, namely: y(t+1) = u1(t) + u2(t) +
u3(t) Where u1(t) = b31(t); u2(t) = b22(t); u3(t) =
b13(t), are the Shift Registers outputs respectively. Note: The (+) symbol refers to XOR binary operation
that “adds” two members at a time, no matter the order because this operator is
fully associative. For three members (u1, u2, u3) its
equivalent “Truth Table” is as follows:
We initiate the process
zeroing registers as A5/1 does for each frame. We are going to analyze this
sample for K = [1 0 1 1 0 1 1
0 1], generating transitions from S(0) to S(9) instead of transitions S(0) to
S(64) in the A5/1 case using a private key K of 64 bits. Note: As we will see later, “Initial States”, are
those states S(86) after finishing stages one and two,
traversing 64 + 22 states, 64 to mix registers with the private key and last 22
to mix registers with the 22 bits Frame counter respectively.
States transitions from S(0)
= [0 0 0 0 0 0 0 0 0]
to [0 0 1 0 1 1 0 1 0] via
the Private Key K = [1 0 1 1 0 1 1 0 1] As we have
demonstrated any partial state transition could be seen as the following
iterative process: Si(1)
= Ci(1)*Si(0) + K1 Si(2)
= Ci(1)*Si(1) + ………………….. Si(t) (3)= Ci(1)*Si(t1) + Kt Where Kj stands for a vector
of size n (in this case n=9) with Kj(n) = K(n) and Kj(h) =0, for h=1,
2,…, (n1). We use here the notation from 1 to n for bits because it looks
easier for the iteration understanding. If (t) is limited to n steps as it is
the case we have a sequence from S(0) to S(9). Really
there is no limitation in t if we want to go farther because we may either stop
entering bits of K or start to reenter them cyclically. The Kj series looks like: K1: [0 0 0 0 0 0 0 0 K(1)] …………………………… Kn:
[0 0 0 0
0 0 0
0 K(n)] Let’s deep a
little on the nature of each iteration expression: Note: Ci(0) are states transition matrices to traverse only one
step, for instance from state 0 to state 1 and from state j to (j+1) state.
Then we have a product of a nxn
C matrix by a n size S vector and then XORing the
result with vectors Kj. If we want to jump directly from S(0)
to S(n) we have: Si(9) = Ci(1)^8*Si(0) + Ci(1)^8*K1
+ Ci(1)^7*K2 + ……. + Ci(1)^1*K8 + K9 If we make S(0) = 0 the first
term disappear. The mechanic of this process is very systematic because the Ci(h)
matrices cycle throughout (2^ri – 1) different types, being ri
the order of the registers, 19, 22 and 23 in the A5/1 case, and 4, 3, and 2 in
our small example. This allow us to jump from any non zero state j to any state
(j+h) throughout Ci(1)^h matrices. To make
things easy we use the following notation: Ci(1)^h
= Ci(h) For our example we have then: Ci(1), Ci(2), Ci(3),
……, Ci(2^n – 1), being these last matrices shifted
Unity matrices because they start new cycles. Let’s see the series for our
example: C1 Matrices
Note: we have omitted matrices C1(9)
to C1(14). C2 Matrices
C3 Matrices
