Conventional Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 49

b = R 2 [20] ⊕ R 2 [21] .

R 3 has 23 bits R 3 [0] ,..., R 3 [22]. When R 3 is clocked, it is similarly shifted by inserting

a new bit

b = R 3 [7] ⊕ R 3 [20] ⊕ R 3 [21] ⊕ R 3 [22] .

In order to determine which registers to clock, we use three special bits called
“clocking taps” from every register, namely R 1 [8], R 2 [10], and R 3 [10]. We compute
the majority bit among those three bits, and registers whose clocking tap agree with
the majority are clocked. Consequently, we are ensured that at least two registers are
clocked. All registers are clocked if the three clocking taps agree on the same bit.

Every time unit, a bit is output from this scheme. This output bit is the XOR of
the leading bits, namely

R 1 [18] ⊕ R 2 [21] ⊕ R 3 [22] .

We use the generated key stream as in the one-time pad.

A5/1 also includes an initialization which generates the initial internal state from
an encryption key and some GSM parameters. It is required that a new key is set up
for any new frame of 114 bits. More precisely, the key is set up from a 64-bit secret
key KC and a 22-bit frame number Count. This is indeed a kind of CTR mode. The
usage of a secret key KC is thus limited. Because of the structure of the frame number
in the GSM standard we can have at most 2 7 million frames for a single key, which

corresponds to 4 hours of GSM communication.

.

The A5/1 initialization works as follows. The three registers are first set to zero.
Then every bit of KC is processed in 64 clock cycles by XORing them to the first
register cells and stepping all registers (i.e. the clock control is disabled). Every bit
of the frame number Count is then processed in a similar way and the A5/1 automa-
ton is run for 100 clock cycles with its clock control enabled (but output bits are
discarded).

1: set all registers to zero
2: for i = 0to63 do

3: R 1 [0] ← R 1 [0] ⊕ KC[ i ]

4: R 2 [0] ← R 2 [0] ⊕ KC[ i ]

5: R 3 [0] ← R 3 [0] ⊕ KC[ i ]

6: clock all registers
7: end for
8: for i

= 0to21 do

9: R 1 [0] ← R 1 [0] ⊕ Count[ i ]

10: R 2 [0] ← R 2 [0] ⊕ Count[ i ]