Project

General

Profile

KeystreamSpace » History » Version 3

Sascha, 07/13/2012 04:50 PM

1 1 Sascha
h1. KeystreamSpaceState and keystream space determined through backclocking random states
2
3
As discussed in Backclocking A5/1, not all A5/1 states can exist after 100 rounds of majority clocking.
4
5
Since the A5/1 state is 64 bits wide, the number of possible states is 264. Not every state can be clocked back. The following table gives the number of illegal states when considering backclocking.
6 2 Sascha
|16 back	|57% illegal states|
7
|32 back	|68% illegal states|
8
|48 back	|74% illegal states|
9
|64 back	|78% illegal states|
10
|80 back	|82% illegal states|
11
|96 back	|84% illegal states|
12 1 Sascha
13
This means that only 16% of states can actually exist after clocking forward 100 times.
14
15
This also implies that only 16% of possible 64 bit keystreams can exist. Since we take 64 bits of keystream as the next state in chain generation, we have to make sure that we map the reduced keystream space into the 264 size 64 bit space again, by using enough suitable round functions.
16
17
h1. State and keystream space determined through forward and backclocking random states
18
19
When considering forward clocking a random state 100 times, and then clocking back, we generally arrive at between 1 and 100 states. The following chart shows the frequency of the number of sibling states when forward/backward clocking 100 times, based on evaluating one million random states. The number of ancestor states of a random state clocked back 100 times is shown as well (with the data point showing that 848000 of 1m states have no ancestors removed)
20 2 Sascha
21 3 Sascha
!Picture1.png!
22 2 Sascha
23 1 Sascha
24
The weighed average for F/B clocking is 13.04, and for B clocking 1.00.
25
26
The peak is around 6. A uniform distribution from 264 sized initial state space to 16% of that space, would indeed lead one to expect that every valid state has 6 ancestors.
27
28
However, these numbers seem to indicate that A5/1 converges to a smaller group of favored states, since the weighed average is twice as high. In other words: we see 1m states that have 13m ancestors. This figure illustrates what happens:
29
30 3 Sascha
!Picture2.png!
31
32 1 Sascha
(based on clocking 100m random states F/B 100 times, as well as clocking 100m random states B 100 times, which gives perfectly matching data)
33
34
The two dashed lines show that:
35
36
    half the actual keystreams find their origin in some 82% of initial states
37
    10% of actual keystreams find their origin in 30% of initial states 
38
39
The figures below give more detailed data on group size distribution.
40
41 3 Sascha
!Picture3.png!
42
43 1 Sascha
(Explanation: of all ancestors of 100m random states clocked forward 100 times, 20m out of 100m are in groups bigger than 19. There is a 20m/100m = 20% chance of hitting such a state.)
44 3 Sascha
45
!Picture4.png!
46 1 Sascha
47
(Explanation: same as the above but in % of total.)
48
49
This figure clearly shows that (ceteris paribus) only using valid states will increase the amount of mergers.