A5/1 not cracked?

From: Frank Jansen (fjansgmxnet_at_yahoo.co.uk)
Date: 02/28/05 

Date: 28 Feb 2005 02:50:03 -0800

Hello

Recently I read the paper "Real Time Cryptanalysis of A5/1 on a PC"
from Alex Biryukov, Adi Shamir and David Wagner.

They proposed a biased birthday attack for which they need 4x73GB
harddisk space and about 2 minutes known plaintext to find Ki nearly
immediately. Well, nice tricks, but 2 minutes known plaintext is very
unrealistic, if you don't want to call every target for 2 minutes
(hopping the A5 key will not change) before you could eavesdrop the
target ;-)

They additionally proposed a random subgraph attack with 4x73GB
harddisk space for which they need 2 seconds known plaintext to find
the key in 4 minutes. It looks intersting, because if you take 2x300GB
(for 2x179Euros) you only need 1 second known plaintext, which is
probably realistic at the early beginning of a call.

But I have a serious problem with the discription of their second
attack.

In the first attack they write in chapter 5.3 they need approximate 48
bits to specify a single red state by specifying the 41 bits of the
partial state and the approximate 7 choice bits in the sampling
procedure. This looks ok and is no problem in this attack because they
are storing only 40 bits of the red states on disk and they have to
try every possible combination in the attack phase.

But in the second attack they take red states defined by fixed 48 bits
to compute sequences of red states by repeatedly applying A5/1. This
is the core operation of the preparing and of the attack phase.

Strictly spoken: The logical outcome of their paper is that their
second approach will !not! work! Where is the solution?

Is there a possibility to define red states with exact 48 bits?

Could we add well defined bits to red states specified with less than
48 bits and cut bits for red states specified with more than 48 bits
in the A5 iterations without destroying the statistical base of the
random subgraph attack?

How do we store the bright red state starting points in a efficient
way, if the lenght is not fixed 36 bits, but between 29 and 45 bits?

Any clues are appreciated.
 
Best regards,
               Frank

Relevant Pages

  • A5/1 not cracked?
    ... Recently I read the paper "Real Time Cryptanalysis of A5/1 on a PC" ... They proposed a biased birthday attack for which they need 4x73GB ... Well, nice tricks, but 2 minutes known plaintext is very ... But in the second attack they take red states defined by fixed 48 bits ...
    (sci.crypt)
  • Re: A5/1 not cracked?
    ... >But in the second attack they take red states defined by fixed 48 bits ... >to compute sequences of red states by repeatedly applying A5/1. ... >is the core operation of the preparing and of the attack phase. ... There has been more recent work on GSM security. ...
    (sci.crypt)
  • Re: Countering chosen-plaintext attacks
    ... > If one passes the same plaintext to a encryptor X times, ... > means that we now have X ciphertexts that all decrypt to the same ... plaintext attack. ... "Her failure to do so meant that she was masking her Midway preparation ...
    (sci.crypt)
  • Re: A basic cryptanalysis question
    ... >> appear out of his attack, he assumes he's recovered the plaintext. ... >include the keys in your construction. ... such a function look at my second order bijective compression of english ...
    (sci.crypt)
  • Re: Matrixview SWISH almost two times better compression then GZIP and much faster
    ... like open source, chosen plaintext, lots of computing power. ... the ciphertext was encrypted with ME6 -- or simply encrypt the ME6 ... computing power and lots of crypto experts to help. ... If ME6 can't withstand such an attack, ...
    (comp.compression)