Re: A5/1 cracking hardware estimate

[Matthew Francey]

>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 the 3 registers must shift per clock, and the probability
of any one shifting is 0.75, so 75+- makes sense.

Is there a reference for this paper?

>Since the shift registers themselves are linear, it's trivial to run
>them backwards a fixed number of clocks.

Yep.

>I think it's also possible to run the state backwards more directly, by
>considering each of the four possible "pre-states" and rejecting those
>for which the clock bits don't match up. Thus, you get a state tree with
>a variable (0..4) branching factor. David Wagner has suggested that
>traversing this tree is a good way to get a handle on how many key bits
>are lost, and maybe giving insight into the relatively short cycles of
>A5/1. This is a great project for someone who has hacking ability and
>wants to contribute to the cryptanalysis knowledge for A5/1.

I started a little exploration in this yesterday, wondering if the
"map" I suggested is actually feasible.  

Re: A5/1 cracking hardware estimate

[Matthew Francey]

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 decreed.
>
>Problems:  cycles in A5/1's output sequence would preclude a single
>search from spanning the entire space.  The search space itself is now
>rather non-linear -- efficiently searching it is itself an interesting
>problem.

Hmmm... even worse would be "splinters":  those states that lead into cycles.

I wonder if the entire A5/1 "valid" states can be quickly mapped out in a
nice way.  This computation would have to be done only once, and would then
be used to dole out searching tasks, a la distributed.net.

-mdf

Re: A5/1 cracking hardware estimate

[Matthew Francey]

>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.
But I don't know how much stuff like this costs to make and such.
Spending other people's money is always easy ... ;-)

>However your analysis does suggest that going to a full 64 bit key would
>not yield a corresponding gain in strength for A5/1.

This might also apply to any simple shift-register based crypto with only
64 bits of state.

>I did think about precomputing the shift register state after part of the
>key is setup and then loading that in parallel, but the extra circuitry
>needed to enable parallel load of the shift registers might eat up most of
>the thruput savings.

Hm.  The "extra circuitry" would be wires and a latch signal.  I can't
see how this would eat into throughput.

>Also if you have 64 circuits running in parallel synchronously, then you
>can't assume they will all fail in two cycles on the average. If you want
>the engines to run asynchronously, then you need a 64-bit counter per
>engine which would increase the footprint by a factor of two or so.

The footprint is already miniscule, especially compared to a DES search
engine.  Or at least I think it would be; I am not deep into VLSI design.

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 decreed.

Problems:  cycles in A5/1's output sequence would preclude a single
search from spanning the entire space.  The search space itself is now
rather non-linear -- efficiently searching it is itself an interesting
problem.

>Finally, it is not clear to me that you can run A5 backwards after the 100
>mixing steps because then the non-linear majority voting circuit is
>operating. I haven't thought that question through.

Actually, it doesn't matter in the end:  as soon as the 64 bits of state
have been found, it is game over for the target.  In this frame of mind,
all of the key setup stuff in the released A5/1 code is just so much
obfuscation.

-mdf