Arnold G. Reinhold wrote:
Matthew,
Your approach is interesting, but it claims a gain of about 100 in reduced
cycle time, while giving up the ability to use the knowledge that ten key
bits are zero, which is a factor of 1000. So it is not a win in that sense.
However your analysis does
Golic's paper shows how to run the state backwards 100 cycles in 10^4
expected, 10^6 worst case work factor. Briefly, you exhaustively search
the space of how many clocks each of the shift register goes through.
This value is about 75 +/- 4 for each of the three shift registers.
At least 2 of
Your approach is interesting, but it claims a gain of about 100 in reduced
cycle time, while giving up the ability to use the knowledge that ten key
bits are zero, which is a factor of 1000. So it is not a win in that sense.
I'd just build 10x more of the searchers then; they are very simple.
I wrote:
The 64 bit counter can be dispensed with by using the search engine as it's
own "counter". Just start the registers at some known point and let it
loose. Shift the output bits into a plaintext comparison unit -- simple
xor/mask/check for zero combinatoric logic. Stop when a match is
At 6:17 PM + 5/13/99, Matthew Francey wrote:
Your approach is interesting, but it claims a gain of about 100 in reduced
cycle time, while giving up the ability to use the knowledge that ten key
bits are zero, which is a factor of 1000. So it is not a win in that sense.
I'd just build 10x
At 10:58 AM +0200 5/10/99, Lucky Green wrote:
o I would love to read some well-founded estimates on how fast this
algorithm could be made to run on a Pentium class CPU and a low-cost FPGA.
Just so we all know what the upper bounds for a brute force attack are.
Not that I believe brute force to
Brute force keysearch is not the best algorithm for cracking A5/1.
Much better is Jovan Golic's technique for breaking A5 with something
like 2^40 steps. (See ``Cryptanalysis of Alleged A5 Stream Cipher'',
EUROCRYPT'97, and http://jya.com/a5-hack.htm.)
The question, as I see it, is how fast you
