ANTICHAT — форум по информационной безопасности, OSINT и технологиям

Average Weights

--------------------------------------------------------------------------------

2-4
2432
2-5
3624 2-6
4719
2-7
5813

2-8
6910
2-9
7991
2-10 9181
2-11 10277

2-12 11369
2-13 12456
2-14 13471
2-15 14581

--------------------------------------------------------------------------------

2-16 15686
2-17 16839
2-18 17925
2-19 19012

2-20 20152
2-21 21227
2-22 22209
2-23 23515
2-24 24597
2-25 25690
2-26 26234

--------------------------------------------------------------------------------

A further reduction in the complexity of the preprocessing stage can be obtained by the early abort strategy: Explore each red state to a shallow depth, and continue to explore only the most promising candidates which have a large number of sons at that depth. This heuristic does not guarantee the existence of a large belt, but there is a clear correlation between these events.

To check whether the efficiency of our biased birthday attack depends on the details of the stream cipher, we ran several experiments with modified variants of A5/1. In particular, we concentrated on the effect of the clock control rule, which determines the noninvertibility of the model. For example, we hashed the full state of the three registers and used the result to choose among the four possible majority-like movements (+1,+1,+1), (+1,+1,0), (+1,0,+1), (0,+1,+1) in the triplet space. The results were very different from the real majority rule. We then replaced the majority rule by a minority rule (if all the clocking taps agree, all the registers move, otherwise only the minority register moves). The results of this minority rule were very similar to the majority-like hashing case, and very different from the real majority case (see Figure 5). It turns out that in this sense A5/1 is actually stronger than its modified versions, but we do not currently understand the reason for this strikingly different behavior. We believe that the type of data in Table 2, which we call the tail coverage of the cryptosystem, can serve as a new security measure for stream ciphers with noninvertible state transition functions.

Fig. 5. Weight distributions. The graph on the left shows weight distributions for the majority function; the graph on the right compares the weight distributions of several clock-control functions.

5.8 Extracting the Key From a Single Red State

The biased birthday attack was based on a direct collision between a state in the disk and a state in the data, and required approx = 71 red states from a relatively long (approx = 2 minute) prefix of the conversation. In the random subgraph attack we use indirect collisions, which make it possible to find the key with reasonable probability from the very first red state we encounter in the data, even though it is unlikely to be stored in the disk. This makes it possible to attack A5/1 with less than two seconds of available data. The actual attack requires several minutes instead of one second, but this is still a real time attack on normal telephone conversations.

The attack is based on Hellman's original time-memory tradeoff for block ciphers, described in [4]. Let E be an arbitrary block cipher, and let P be some fixed plaintext. Define the function f from keys K to ciphertexts C by f(K) = EK (P ). Assuming that all the plaintexts, ciphertexts and keys have the same binary size, we can consider f as a random function (which is not necessarily one-to-one) over a common space U . This function is easy to evaluate and to iterate but difficult to invert, since computing the key K from the ciphertext f(K) = EK (P ) is essentially the problem of chosen message cryptanalysis.

Hellman's idea was to perform a precomputation in which we choose a large number m of random start points in U , and iterate f on each one of them t times. We store the m (start point, end point) pairs on a large disk, sorted into increasing endpoint order. If we are given f(K) for some unknown K which is located somewhere along one of the covered paths, we can recover K by repeatedly applying f in the easy forward direction until we hit a stored end point, jump to its corresponding start point, and continue to apply f from there. The last point before we hit f(K) again is likely to be the key K which corresponds to the given ciphertext f(K).

Since it is difficult to cover a random graph with random paths in an efficient way, Hellman proposed a rerandomization technique which creates multiple variants of f (e.g., by permuting the order of the output bits of f ). We use t variants fi , and iterate each one of them t times on m random start points to get m corresponding end points. If the parameters m and t satisfy mt2 = |U|, then each state is likely to be covered by one of the variants of f. Since we have to handle each variant separately (both in the preprocessing and in the actual attack), the total memory becomes M = mt and the total running time becomes T = t2 , where M and T can be anywhere along the tradeoff curve M square root T = |U|. In particular, Hellman suggests using M = T = |U|2/3.

A straightforward application of this M square root T = |U| tradeoff to the |U| = 264 states of A5/1 with the maximal memory M = 236 requires time T = 256, which is much worse than previously known attacks. The basic idea of the new random subgraph attack is to apply the time-memory tradeoff to the subspace R of 248 red states, which is made possible by the fact that it can be efficiently sampled. Since T occurs in the tradeoff formula M square root T = |U| with a square root, reducing the size of the graph by a modest 216 (from |U| = 264 to |R| = 248 ) and using the same memory (M = 236), reduces the time by a huge factor of 232 (from T = 256 to just T = 224 ). This number of steps can be carried out in several minutes on a fast PC.

What is left is to design a random function f over R whose output-permuted variants are easy to evaluate, and for which the inversion of any variant yields the desired key. Each state has a "full name" of 64 bits which describes the contents of its three registers. However, our efficient sampling technique enables us to give each red state a "short name" of 48 bits (which consists of the partial contents of the registers and the random choices made during the sampling process), and to quickly translate short names to full names. In addition, red states are characterized (almost uniquely) by their "output names" defined as the 48 bits which occur after alpha in their output sequences. We can now define the desired function f over 48-bit strings as the mapping from short names to output names of red states: Given a 48-bit short name x, we expand it to the full name of a red state, clock this state 64 times, delete the initial 16-bit alpha, and define f(x) as the remaining 48 output bits. The computation of f(x) from x can be efficiently done by using the previously described precomputed tables, but the computation of x from f(x) is exactly the problem of computing the (short) name of an unknown red state from the 48 output bits it produces after alpha. When we consider some output-permuted variant fi of f, we obviously have to apply the same permutation to the given output sequence before we try to invert fi over it.

The recommended preprocessing stage stores 212 tables on the hard disk. Each table is defined by iterating one of the variants fi 212 times on 224 randomly chosen 48-bit strings. Each table contains 224 (start point, end point) pairs, but implicitly covers about 236 intermediate states. The collection of all the 212 tables requires 236 disk space, but implicitly covers about 248 red states.

The simplest implementation of the actual attack iterates each one of the 212 variants of f separately 212 times on appropriately permuted versions of the single red state we expect to find in the 2 seconds of data. After each step we have to check whether the result is recorded as an end point in the corresponding table, and thus we need T = 224 probes to random disk locations. At 6 ms per probe, this requires more than a day. However, we can again use Rivest's idea of special points: We say that a red state is bright if the first 28 bits of its output sequence contain the 16-bit alpha extended by 12 additional zero bits. During preprocessing, we pick a random red start point, and use fi to quickly jump from one red state to another. After approximately 212 jumps, we expect to encounter another bright red state, at which we stop and store the pair of (start point, end point) in the hard disk. In fact, each end point consists of a 28 bit fixed prefix followed by 36 additional bits. As explained in the previous attack, we do not have to store either the prefix (which is predictable) or the suffix (which is used as an index) on the hard disk, and thus we need only half the expected storage. We can further reduce the required storage by using the fact that the bright red states have even shorter short names than red states (36 instead of 48 bits), and thus we can save 25% of the space by using bright red instead of red start points in the table.6 During the actual attack, we find the first red state in the data, iterate each one of the 212 variants of f over it until we encounter a bright red state, and only then search this state among the pairs stored in the disk. We thus have to probe the disk only once in each one of the t = 212 tables, and the total probing time is reduced to 24 seconds.