9 December 1999
Source: Postscript file from Adi Shamir:
http://cryptome.org/a5.ps (292K;
hardcopy of 18 pages.)
Check equations with Postscript original. Errors to a51@cryptome.org
* Computer Science department The Weizmann Institute Rehovot 76100, Israel.
December 9, 1999
Abstract
A5/1 is the strong version of the encryption algorithm used by about 100 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 240 and 245 steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers.
In this paper we describe a new attack on A5/1, which is based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. The attack can find the key in less than a second on a single PC with 128 MB RAM and two 73 GB hard disks, by analysing the output of the A5/1 algorithm in the first two minutes of the conversation. The attack requires a one time parallelizable data preparation stage whose complexity can be traded-off between 238 and 248 steps. The attack was verified with an actual implementation, except for the preprocessing stage which was extensively sampled rather than completely executed.
DISCLAIMER: This paper considers the narrow issue of the cryptographic strength of A5/1, and not the broader issue of the practical security of fielded systems, about which we make no claims. We base our attack on the unofficial version of the algorithm which was derived by reverse engineering actual GSM SIM cards and published at http://www.scard.org, and use the term A5/1 to refer to this particular version. Any discrepancies between this version and the real algorithm used in GSM telephones may affect the validity or performance of our attack.
The over-the-air privacy of GSM telephone conversations is protected by the A5 stream cipher. This algorithm has two main variants: The stronger A5/1 version is used by about 100 million customers in Europe, while the weaker A5/2 version is used by another 100 million customers in other markets.
The approximate design of A5/1 was leaked in 1994, and the exact design of both A5/1 and A5/2 was reverse engineered by Briceno from actual GSM smart cards in 1999 and confirmed against official test vectors (see [2]). In this paper we assume that these unofficial descriptions of the algorithm and protocol are accurate.
In this paper we describe a cryptanalytic attack on A5/1, in which a single PC can extract the conversation key in less than a second from the output produced by the algorithm in the first two minutes. Many of the ideas are applicable to other stream ciphers as well, and define new measures of strength.
The paper is organized in the following way: Section 2 contains a full description of the A5/1 algorithm. Previous attacks on A5/1 are surveyed in Section 3, and an informal description of the new attack is contained in Section 4. Finally, Section 5 contains various implementation details and an analysis of the expected success rate of the attack, based on large scale sampling with an actual implementation.
A GSM conversation is sent as a sequence of frames. Each frame contains 114 bits representing the digitized A to B communication, and 114 bits representing the digitized B to A communication. A new frame is sent every 4.6 milliseconds, and each frame has a publicly known 22 bit frame counter Fn which cycles every 222 frames (i.e., a few hours).
Each GSM phone conversation can be encrypted by a new session key K, which is derived in a noninvertible way from the user's master key and a random value by another algorithm known as A8. For each frame, K is mixed with the frame counter Fn , and the result serves as the initial state of a generator which produces 228 pseudo random bits. These bits are XOR'ed with the 228 bits of the plaintext to produce the 228 bits of the ciphertext.
A5/1 is built from three short linear feedback shift registers (LFSR) of
lengths 19, 22, and 23 bits, which are denoted by R1, R2 and
R3 respectively. The rightmost bit in each register is labelled as
bit zero. The taps of R1 are at bit positions 13, 16, 17, 18; the
taps of R2 are at bit positions 20, 21; and the taps of R3
are at bit positions 7, 20, 21, 22 (see Figure 1). When a register is clocked,
its taps are XORed together, and the result is stored in the rightmost bit
of the left-shifted register. The three registers are clocked in a stop/go
fashion using the following majority rule: Each register has a single "clocking"
tap (bit 8 for R1, bit 10 for R2, and bit 10 for for
R3); each clock cycle, the majority function of the clocking taps
is calculated and only those registers whose clocking taps agree with the
majority bit are actually clocked. Note that at each step either two or three
registers are clocked, and that each register moves with probability 3/4
and stops with probability 1/4.
The process of generating pseudo random bits from the session key K and the frame counter Fn is carried out in four steps:
The attacker is assumed to know some pseudo random bits generated by A5/1 in some of the frames. This is the standard cryptanalytic assumption in stream ciphers, and we do not consider in this paper the crucial issue of how one can obtain these bits in fielded GSM systems. For the sake of simplicity, we assume that the attacker has complete knowledge of the outputs of the A5/1 algorithm for the first two minutes of the conversation, and his goal is to find the key in order to decrypt the remaining part of the conversation, or to use such keys in order to attack the user's master key. Since GSM telephones send a new frame every 4.6 milliseconds, the first two minutes of the conversation contain 120 * 1000/4:6 equals approx. 215 frames.
At the rump session of Crypto 99, David Wagner announced an attack on A5/2 which requires very few pseudo random bits and just O(216 ) steps. This demonstrated that the "export version" A5/2 is totally insecure.
The security of the A5/1 encryption algorithm was analyzed in several papers. Some of them are based on the early imprecise description of this algorithm, and thus their details have to be slightly modified. The known attacks can be summarized in the following way:
We start with an executive summary of the key ideas of the new attack. More technical descriptions of the various steps will be provided in the next section.
Key idea 1: Use a time-memory tradeoff attack.
The starting point for the new attack is the time-memory tradeoff described in Golic[3], which is itself an adaptation of the time-memory tradeoff developed by Hellman for block ciphers. Such attacks can be applied to almost any cryptosystem, but they are practical only when the number of internal states is relatively small. A5/1 has this weakness, since its state at any given time is defined by the 19+22+23 bits in its three shift registers, and thus it has exactly n = 264 possible states. The basic idea of the time-memory tradeoff is to keep a large set A of precomputed states on a hard disk, and to consider the large set B of states through which the algorithm progresses during the actual generation of output bits. Any intersection between A and B will enable us to identify an actual state of the algorithm from stored information.
Key idea 2: Identify states by prefixes of their output sequences.
Each state defines an infinite sequence of output bits produced when we start clocking the algorithm from that state. We can look for equality between unknown states by comparing their output sequences. In fact, it usually suffices to compare the log(n) initial bits in the output sequences in order to make a correct decision. The mapping from states to prefixes is easy to compute and deterministic, whereas the mapping from prefixes to states is difficult to compute and may yield 0, 1, or several possible results. To choose the set A during precomputation, pick a subset of states, compute their output prefixes, and store the (prefix, state) pairs sorted into increasing prefix values. Given actual outputs of the A5/1 algorithm, extract all their (partially overlapping) prefixes, and define B as the set of their corresponding (unknown) states. Searching for common states in A and B can be efficiently done by probing the sorted data A on the hard disk with prefix queries from B.
Key idea 3: A5/1 can be efficiently inverted.
As observed by Golic, the state transition function of A5/1 is not uniquely invertible: The majority clock control rule implies that up to 4 states can converge to a common state in one clock cycle, and some states have no predecessors. However, we can run A5/1 backwards by exploring the tree of possible predecessor states, and backtracking from dead ends. This process is modeled as a branching process, in which each vertex independently chooses the number of its sons according to some common probability distribution. The branching process is critical in the sense that the average number of sons of each vertex is exactly 1. Critical branching processes are known to produce trees in which the expected number of vertices in the first k levels grows only linearly in k. As a result, if we find a common state in the disk and data, we can efficiently run the algorithm backwards (at most 328 steps) to obtain a small number of candidates for the initial state of the frame. The weakness we exploit here is not the unavoidable fact that the branching process is critical, but the fact that due to the frequent reinitializations there is a very short distance from intermediate states to initial states.
Key idea 4: The key can be extracted from the initial state of any frame.
Here we exploit the weakness of the A5/1 key setup routine. Assume that we know the state of A5/1 immediately after the key and frame counter were used, and before the 100 mixing steps. Since the clock control is disabled before this stage, we can run the linear registers backwards in a unique way, and reverse the effect of the known frame counter. The result is a vector of linear forms in the key bits, from which we can extract the actual key via matrix multiplication by a precomputed 64 x 64 binary matrix. Since the previous step may suggest several starting states, we can choose the correct key by mixing it with the next frame counter, running A5/1 forward for more than 100 steps, and comparing the results with the actual data in the next frame.
Key idea 5: The Golic birthday attack on A5/1 is marginally impractical.
By the well known birthday paradox, A and B are likely to have a common state when their sizes a and b satisfy a * b equals approx. n. We would like a to be bounded by the size of commercially available PC hard disks, and b to be bounded by the number of overlapping prefixes in a typical GSM telephone conversation. Reasonable bounds on these values (justified later in this paper) are a equals approx. 235 and b equals approx. 222 . Their product is 257, which is about 100 times smaller than n = 264 . To make the intersection likely, we either have to increase the storage requirement from a hundred gigabytes to ten terabytes, or to increase the length of the conversation from two minutes to three hours. Neither approach seems to be practical, but the gap is not huge and a relatively modest improvement by two orders of magnitude is all we need to make it practical.
Key idea 6: Use biased birthday attacks.
One of the main ideas in the improved attack is to consider sets A and B which are not chosen with uniform probability distribution among all the possible states. Assume that each state s is chosen for A with probability PA (s), and is chosen for B with probability PB (s). If the means of these probability distributions are a/n and b/n, respectively, then the expected size of A is a, and the expected size of B is b.
The birthday threshold happens when Sigmas PA (s)PB (s) equals approx. 1. For independent uniform distributions, this evaluates to the standard condition a * b equals approx. n. However, when the probability distributions are correlated the results can be dramatically different: When A consists of the n/2 states that start with 0 and B consists of the n/2 states that start with one, the two sets are disjoint in spite of their size, while if all the probabilities are concentrated on one common string, the two sets intersect even though their sizes are 1.
In the new attack, we choose states for the disk and states in the data with two non-uniform probability distributions which have very strong positive correlation. This makes our time memory tradeoff much more efficient than the one used by Golic. This is made possible by the fact that in A5/1, the initial state of each new frame is rerandomized very frequently with different frame counters.
Key idea 7: Use special states.
A major problem in implementing time-memory tradeoff attacks is that access to disk is about a million time slower than a computational step, and thus it is crucial to minimize the number of times we look for data in the hard disk. An idea due to Ron Rivest (in the context of time memory tradeoffs of block ciphers) is to keep on the disk only special states which are guaranteed to produce output bits starting with a particular pattern alpha of length k. When we scan the data, we access the disk only when we encounter such a prefix. Clearly, we do not miss any intersections by skipping the other prefixes in the actual data, while reducing the number b of disk probes by a factor of about 2k . The number of points a we have to memorize remains unchanged, since in the formula a * b equals approx. n both b and n are reduced by the same factor 2k . The downside is that we have to work 2k times harder during the preprocessing stage, since only 2-k of the random states we try produce outputs with such a k bit prefix. If we try to reduce the number of disk access steps in the time memory attack on A5/1 from 222 to 100, we have to increase the preprocessing time by a factor of about 40,000, which makes it impractically long.
Key idea 8: Special states can be efficiently sampled in A5/1.
One of the specific weaknesses of A5/1 which we exploit in our attack is that we can easily generate all the states which produce output sequences that start with a particular k-bit pattern alpha with k = 16 without trying and discarding other states. This is due to a poor choice of the clocking taps, which makes the register bits that affect the clock control and the register bits that affect the output unrelated for about 16 clock cycles, so we can choose them independently. This easy access to special states does not happen in good block ciphers, but can happen in stream ciphers due to their simpler transition functions. In fact, the maximal value of k for which special states can be sampled without trial and error can serve as a new security measure for stream ciphers, which we call its sampling resistance. As demonstrated in this paper, high values of k can have a major impact on the efficiency of time-memory tradeoff attacks on such cryptosystems.
Key idea 9: A5/1 is very efficient on a PC.
The A5/1 algorithm was designed to be efficient in hardware, and its straight-forward software implementation is quite slow. To execute the preprocessing stage, we have to run it on a distributed network of PC's up to 248 times, and thus we need an extremely efficient way to compute the effect of one clock cycle on the three registers.
We exploit the following weakness in the design of A5/1: Each one of the
three shift registers is so small that we can precompute all its possible
states, and keep them in three cyclic arrays where successive locations in
each array represent successive states of the corresponding shift register.
In fact, we don't have to keep the full states in the arrays, since the only
information we have to know about a state is its clocking tap and its output
tap. A state can thus be viewed as a triplet of indices (i, j,
k) into three large arrays whose entries are pairs of bits (see Figure
2). Since there is no mixing of the values of the three registers, their
only interaction is in determining which of the three indices should be
incremented by 1. This can be determined by a precomputed table with three
input bits (the clocking taps) and three output bits (the increments of the
three registers). When we clock A5/1 in our software implementation, we don't
shift registers or compute feedbacks - we just add a 0/1 vector to the current
triplet of indices. A typical two dimensional variant of such movement vectors
in triplet space is described in Figure 3. Note the local tree structure
determined by the deterministic forward evaluation and the nondeterministic
backward exploration in this triplet representation.
Since the increment table is so small, we can expand it to a large precomputed table with 224 entries, whose inputs are the three bytes to the right of the clocking taps in the three registers, and outputs are the three increments to the indices which allow us to jump directly to the state which is 8 clock cycles away. The total amount of RAM needed for the state arrays and precomputed movement tables is less than 128 MB, and the total cost of advancing the three registers for 8 clock cycles is one table lookup and three integer additions! A similar table lookup technique can be used to compute in a single step out put bytes instead of output bits, and to speed up the process of running A5/1 backwards.
In this section we fill in the missing details, and analyse the success rate of the new attack.
5.1 Efficient Sampling of Special States
Let alpha be any 16 bit pattern of bits. To simplify the analysis, we prefer to use an alpha which does not coincide with shifted versions of itself (such as alpha = 1000 ... 0) since this makes it very unlikely that a single 228-bit frame contains more than one occurrence of alpha.
The total number of states which generate an output prefix of alpha is about 264 * 2-16 = 248. We would like to generate all of them in a (barely doable) 248 preprocessing stage, without trying all the 264 possible states and discarding the vast majority which fail the test. The low sampling resistance of A5/1 is made possible by several flaws in its design, which are exploited in the following algorithm:
5.2 Efficient Disk Probing
To leave room for a sufficiently long identifying prefix of 35 bits after the 16-bit alpha, we allow it to start only at bit positions 1 to 177 in each one of the given frames (i.e., at a distance of 101 to 277 from the initial state). The expected number of occurrences of alpha in the data produced by A5/1 during a two minute conversation is thus 2-16 * 177 * 120 * 1000/4:6 equals approx. 71. This is the expected number of times b we access the hard disk. Since each random access takes about 6 milliseconds, the total disk access time becomes negligible (about 0.4 seconds).
5.3 Efficient Disk Storage
The data items we store on the disk are (prefix, state) pairs. The state of A5/1 contains 64 bits, but we keep only special states and thus we can easily encode them in 48 bits, by specifying all the decisions made during the efficient sampling procedure. We can further reduce the state to less than 40 bits (5 bytes) by leaving some of these bits unspecified. This saves a considerable fraction of the disk space prepared during preprocessing, and the only penalty is that we have to try a small number of candidate states instead of one candidate state for each one of the 71 relevant frames. Since this part is so fast, even in its slowed down version it takes less than a second.
The prefix produced from each special state is nominally of length 16 + 35 = 51 bits. However, the first bits are always the constant alpha , and the next 35 bits are stored in sorted order on the disk. We can thus store the full value of these 35 bits only once per sector, and encode on the disk only their small increments (with a default value of 1). Other possible implementations are to use the top parts of the prefixes as direct sector addresses or as file names. With these optimizations, we can store each one of the sorted (prefix, state) pairs in just 5 bytes. The largest commercially available PC hard disks (such as IBM Ultrastar 72 ZX or Seagate Cheetah 73) have 73 gigabytes. By using two such disks, we can store 146 * 230/5 equals approx. 235 pairs during the preprocessing stage, and characterize each one of them by its (usually unique) 35-bit prefix.
5.4 Efficient Tree Exploration
The forward state-transition function of A5/1 is deterministic, but in the reverse direction we have to consider four possible predecessors. About 3/8 of the states have no predecessors, 13/32 of the states have one predecessor, 3/32 of the states have two predecessors, 3/32 of the states have three predecessors, and 1/32 of the states have four predecessors.
Since the average number of predecessors is 1, Golic assumed that the critical branching process will provide a good model for the generated trees of predecessors. We were surprised to discover that in the case of A5/1, there was a very significant difference between the predictions of the model and our experimental data. For example, the theory predicted that only 2% of the states would have some predecessor at depth 100, whereas in a large sample of 100,000,000 trees we generated from random A5/1 states the percentage was close to 15%. Another major difference was found in the tail distributions of the number of sons at depth 100: Theory predicted that in our sample we should see some cases with close to 1000 sons, whereas in our sample we never saw trees with more than 120 sons at depth 100.
5.5 The Biased Birthday Attack.
To analyse the performance of our biased birthday attack, we introduce the following notation:
Definition 1 A state s is coloured red, if the sequence of output bits produced from state s starts with alpha (i.e., it is a special state). The subspace of all the red states is denoted by R.
Definition 2 A state is coloured green, if the sequence of output bits produced from state s contains an occurrence of alpha which starts somewhere between bit positions 101 and 277. The subspace of all the green states is denoted by G.
The red states are the states that we keep in the disk, look for in the data, and try to collide by comparing their prefixes. The green states are all the states that could serve as initial states in frames that contain alpha. Non-green initial states are of no interest to us, since we discard the frames they generate from the actual data.
The size of R is approximately 248 , since there are 264 possible states, and the probability that alpha occurs right at the beginning of the output sequence is 2-16. Since the redness of a state is not directly related to its separate coordinates i, j, k in the triplet space, the red states can be viewed as randomly and sparsely located in this representation. The size of G is approximately 177 * 2-48 (which is still a small fraction of the state space) since alpha has 177 opportunities to occur along the output sequence.
Since a short path of length 277 in the output sequence is very unlikely
to contain two occurrences of alpha, the relationship between green
and red states is essentially many to one: The set of all the relevant states
we consider can be viewed as a collection of disjoint trees of various sizes,
where each tree has a red state as its root and a "belt" of green states
at levels 101 to 277 below it (see Figure 4). The weight W (s)
of a tree whose root is the red state s is defined as the number of green
states in its belt, and s is called k-heavy if W
(s) > k.
The crucial observation which makes our biased birthday attack efficient is that in A5/1 there is a huge variance in the weights of the various red states. We ran the tree exploration algorithm on 100,000,000 random states and computed their weights. We found out that the weight of about 85% of the states was zero, because their trees died out before reaching depth 100. Other weights ranged all the way from 1 to more than 26,000.
Figure 5 describes for each x which is a multiple of 100 the value
y which is the total weight of all the trees whose weights were between
x and x + 100. The total area under the graph to the right of x
= k represents the total number of green states in all the
k-heavy trees in our sample.
The initial mixing of the key and frame number, which ignores the usual clock control and flips the least significant bits of the registers about half the time before shifting them, can be viewed as random jumps with uniform probability distribution into new initial states: even consecutive frame counters can lead to far away initial states in the triplet space. When we restrict our attention to the frames that contain alpha, we get a uniform probability distribution over the green states, since only green states can serve as initial states in such frames.
The red states, on the other hand, are not encountered with uniform probability distribution in the actual data. For example, a red state whose tree has no green belt will never be seen in the data. On the other hand, a red state with a huge green belt has a huge number of chances to be reached when the green initial state is chosen with uniform probability distribution. In fact the probability of encountering a particular red state s in a particular frame which is known to contain alpha is the ratio of its weight W (s) and the total number of green states 177 * 248 , and the probability of encountering it in one of the 71 relevant frames is PB (s) = 71 * W (s)/(177 * 248).
Since PB (s) has a huge variance, we can maximize the expected number of collisions Sigmas PA (s) * PB (s) by choosing red points for the hard disk not with uniform probability distribution, but with a biased probability PA (s) which maximizes the correlation between these distributions, while minimizing the expected size of A. The best way to do this is to keep on the disk only the heaviest trees. In other words, we choose a threshold number k, and define PA (s) = 0 if W (s) < k, and PA (s) = 1 if W (s) > k. We can now easily compute the expected number of collisions by the formula:
which is just the number of red states we keep on the disk, times the average weight of their trees, times 71/(177 * 248 ).
In our actual attack, we keep 235 red states on the disk. This is a 2-13 fraction of the 248 red states. With such a tiny fraction, we can choose particularly heavy trees with an average weight of 12,500. The expected number of colliding red states in the disk and the actual data is 235 * 12,500 * 71/(177 * 248) equals approx. 0.61. This expected value makes it quite likely that a collision will actually exist.2
____________________
2 Note that in time memory tradeoff attacks, it becomes increasingly expensive to push this probability towards 1, since the only way to guarantee success is to memorize the whole state space.
The intuition behind the biased time memory tradeoff attack is very simple. We store red states, but what we really want to collide are the green states in their belts (which are accessible from the red roots by an easy computation). The 71 green states in the actual data are uniformly distributed, and thus we want to cover about 1% of the green area under the curve in Figure 5. Standard time memory tradeoff attacks store random red states, but each stored state increases the coverage by just 177 green states on average. With our optimized choice in the preprocessing stage, each stored state increases the coverage by 12,500 green states on average, which improves the efficiency of the attack by almost two orders of magnitude.
5.6 Efficient Determination of Initial States
One possible disadvantage of storing heavy trees is that once we find a collision, we have to try a large number of candidate states in the green belt of the colliding red state. Since each green state is only partially specified in our compact 5-byte representation, the total number of candidate green states can be hundreds of thousands, and the real time part of the attack can be relatively slow.
However, this simple estimate is misleading. The parasitic red states obtained from the partial specification can be quickly discarded by evaluating their outputs beyond the guaranteed occurrence of alpha and comparing it to the bits in the given frame. In addition, we know the exact location of alpha in this frame, and thus we know the exact depth of the initial state we are interested in within the green belt. As a result, we have to try only about 70 states in a cut through the green belt, and not the 12,500 states in the full belt.
5.7 Reducing the Time Complexity of Preprocessing
The 248 complexity of the preprocessing stage can make it too time consuming for a small network of PC's. In this section we show how to reduce this complexity by any factor of up to 1000, by slightly increasing either the space complexity or the length of the attacked conversation.
The efficient sampling procedure makes it possible to generate any number c < 248 of random red states in time proportional to c. To store the same number of states in the disk, we have to choose a larger fraction of the tested trees, which have a lower average weight, and thus a less efficient coverage of the green states. Table 1 describes the average weight of the heaviest trees for various fractions of the red states, which was experimentally derived from our sample of 100,000,000 A5/1 trees. The implied tradeoff is very favorable: If we increase the fraction from 2 the number of hard disks from 2 to 4. The extreme point in this tradeoff is to store in the disk all the sampled red states with nonzero weights (the other sampled red states are just a waste of space, since they will never be seen in the actual data). In A5/1 about 15% of the red states have nonzero weights, and thus we have to sample about 238 red states in the preprocessing stage in order to find the 15% among them (about 235 states) which we want to store, with an average tree weight of 1180. To keep the same probability of success, we have to attack conversations which last about half an hour.
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 |
||
|
|
|||||||
Table 1: The average weight of the heaviest trees for various functions of
R.
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 were very similar to the majority-like
hashing case, and very different from the real majority case (see Figure
6). 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 1, which we
call the tail coverage of the cryptosystem, can serve as a new security measure
for stream ciphers with noninvertible state transition functions.
We would like to thank Ross Anderson, Mike Roe, Jovan Golic, Marc Briceno, Ian Goldberg, and David Wagner for their pioneering contributions to the analysis of A5/1, which made this paper possible.
[1] R. Anderson, M. Roe, A5, http://jya.com/crack-a5.htm, 1994.
[2] M. Briceno, I. Goldberg, D. Wagner, A pedagogical implementation of A5/1, http://www.scard.org, May 1999.
[3] J. Golic, Cryptanalysis of Alleged A5 Stream Cipher, proceedings of EUROCRYPT'97, LNCS 1233, pp. 239-255, Springer-Verlag 1997.
Transcription and HTML by Cryptome.