At 6:17 PM +0000 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 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 ... ;-)
To get an expected search time on the order of an hour with my design, we
are talking about 1 million search engines. For real time performance, a
billion. A factor of ten is not trivial at that scale.
>
>>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.
By thruput I mean the number of keys checked per second per chip. With the
cell library I was using, you'd need an additional gate per flip-flop which
adds 384 sites to my original 1178 or 32%. Also you would increase the
number of lines that have to go to each engine by a factor of ten, and that
has got to cost you real estate. You might save 48 out of 212 cycles or
22%. Not a great trade.
>
>>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 footprint is miniscule, but we make it up in volume!
>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.
It might be enough to show that you would search most of the key space this
way. If you are screening calls en masse, then you can afford to let a few
get thru undecrypted.
>
>>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.
Good point.
>In this frame of mind,
>all of the key setup stuff in the released A5/1 code is just so much
>obfuscation.
But if the designer knew that only a 54 bit key space was permitted, then
the A5/1 key setup approach may make sense as a key strecher, gaining back
some of the workfactor that was lost by keeping the keys short.
Arnold Reinhold
