Would A5/1 with a much larger state be a good choice of stream cipher for hardware? Assume that a reasonable choice of MAC is made such as GMAC, with the first 128 bits of the stream cipher output used as $H$ and the next 128 bits used to encrypt the auth tag.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Anything speaking against SPECK running in CTR mode? $\endgroup$– SEJPMApr 17, 2016 at 21:28
-
$\begingroup$ If I look at the Wikipedia article there seem to be a lot of attacks on A5/1. You'd have to dispel all of them and then hope that there aren't any others I suppose. It seems more logical to go for a more modern stream cipher $\endgroup$– Maarten Bodewes ♦Apr 17, 2016 at 22:53
-
$\begingroup$ @MaartenBodewes A5/1 provides 2n/3 bits of security -- its state is just too small, hence this question. $\endgroup$– DemiApr 18, 2016 at 0:26
-
$\begingroup$ @SEJPM Simon would be a better hardware choice $\endgroup$– DemiApr 18, 2016 at 0:26
-
$\begingroup$ Define "good choice". Thomas Pornin's answer adresses cryptoanalytic security. But if very high speed is a must, producing more than 1 bit per clock with A5/1 is embarrassingly difficult; Trivium and others solve this. Other criteria (power consumption, silicon area, resistance to side channels..) exist. $\endgroup$– fgrieu ♦Apr 19, 2016 at 5:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
I have argued so 15 years ago, and not been proven wrong since. Basically, A5/1, with a $n$-bit state, offers a resistance of roughly $2n/3$ bits of security. With $n = 64$, the resistance is very low, thus amenable to not only direct breaking, but also all kinds of trade-offs.
All the attacks published so far are dances around that resistance level of about 43 bits, the point being to make it so that actual instances can be broken "in real time": a 43-bit brute force can be done in relatively little time with a modern PC (in a matter of hours), but if you want to indulge in actual GSM spying you need a much faster break so that you can follow the target phone while it hops frequencies. Various methods have been proposed, that combine some possibly large precomputations with a wait for the algorithm to be in a state that is part of that precomputation; this is the idea in the original attack by Biryukov, Shamir and Wagner. Depending on the writing skills of whoever describes an attack, it is often possible to play between elementary operations, bit operations, CPU opcodes and other measures to get the complexity figure as low as possible, e.g. down to $2^{40}$ for A5/1, but that's just marketing.
At its core, there is always the brute force on the clocking sequence: you need to guess two clocking bits, one way or another, to inject one bit of known output.
As such, an A5/1-like design boosted to a 192-bit internal state ought to offer a resistance of about "128 bits" and, to my knowledge, would not be substantially broken -- as far as we know. One might need to expand the size a bit (say, to 210 bits) to avoid academic trickeries resulting in attacks in cost $2^{126.3}$ or similar nitpicking. How many "blank rounds" should be run after injecting the key is an open question (the original A5/1 runs 100 blank rounds).
Though an "extended A5/1" would be implementable in hardware with very few gates, it would not have been extensively reviewed, and experience shows that extensive review is not optional in the design of cryptographic algorithms. As such, it cannot be recommended "as is". I suggest that you consider instead using one of the eSTREAM portfolio algorithms, especially those that follow the "hardware profile". In particular, MICKEY 2.0 has a variant with a 128-bit key.
answered Apr 19, 2016 at 2:16
-
$\begingroup$ What property limits A5/1's security to two-thirds of $n$? $\endgroup$– MelabDec 14, 2017 at 20:04
-
$\begingroup$ @Melab: At each clock cycle, there are four ways for the LFSR to move (at least two move each cycle, possibly all three). If you guess how registers move, then reconstruction of the internal state from the output is a matter of simple linear algebra. You get one bit of output at every clock cycle, and the guess on the LFSR move implies about 2 bits of information as well. Thus, for two bits of guessing, you get a third one from linear algebra. If you guess 2/3rd of the bits, algebra yields the remaining 1/3rd. In all of this, "guessing" means "exhaustive search", as usual. $\endgroup$ Dec 15, 2017 at 15:12
-
$\begingroup$ is this bound applicable to all shift register-based stream ciphers? SNOW 3G? ZUC? E0? Grain? Trivium? $\endgroup$– MelabDec 20, 2017 at 2:29
-
$\begingroup$ @Melab: No. It is very specific to how A5/1 is defined, specifically to how the algorithm decides which registers should be shifted at each clock cycle. $\endgroup$ Dec 20, 2017 at 15:18
-
$\begingroup$ So the inclusion of that mechanism makes the stream cipher weaker? $\endgroup$– MelabDec 21, 2017 at 20:40