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 be the most efficient means of attack.
>
Here is a back of the envelope estimate based on the same technology used
in Michael Wiener's "Efficient DES Key Search paper. I assumed multiple
A5/1 engines on a single chip. A central control provides setup bits for
the frame number and key (except for the low order key bits which differs
for each engine) and provides comparison bits with the known good output.
All the engines would be clocked together and at the appropriate point,
their outputs would be compared, one bit at a time, with the known good
bit. If a potential match occurred, the number of the engine that passed
would be reported to a central computer which would then verify the entire
output string.
I used the same cell library as Wiener so I could compare my A5/1 hardware
concept with his DES design. Weiner estimated chip area required based on
the number of "sites" per library device. Here is my estimate for A5/1:
Circuit Qty Device Sites ea. Total sites
Low order key bit store 6 FF 10 60
6 Gate 6 36
Shift Register Stages 64 FF 10 640
Taps 13 XOR 5 65
2 ot of 3 "majority" ckt 3 AND 4 12
1 4 in OR 6 6
Output Compare 1 FF 10 10
2 Gates 6 12
Raw total 841
Fudge factor 1.4
Estimated sites per A5/1 engine 1178
Sites in Michael Weiner's DES engine 78257
Number of A5/1 engines per DES engine 66
The fudge factor accounts for the central control and I/O circuitry, as
well as all the stuff I ignored 'cause I am just a programmer, not a
hardware engineer. I round the result down to 64, since one would want a
power of two for low order key bit generation. So I conclude that one could
fit 64 A5/1 search engines on a chip that could hold a single Wiener DES
engine.
The bad news is that Weiner's engine could do one key comparison per clock.
Here is an estimate of the number of clocks required to check an A5/1 key:
Key load 64
Frame Number load 22
Setup mix 100
Output compare 24
Reset 2
Total 212
Performance ratio: 212/64 = 3.3 times worse than the Wiener DES search design.
This design checks the first 24 bits of output and then reports any
potential match for off-chip verification. Here I am assuming that we can
check the know plaintext portion (the first .1 sec of zeros) using just the
A->B frame, which comes out first if I understand thing correctly. If it
is necessary to check the B->A output, one would need an additional 114
clocks. The performance ratio then becomes 5.1 times worse than the Wiener
DES search design.
At best this is a very rough estimate. Since the engines are much simpler,
it might be possible to clock the A5/1 chip at a faster speed than the
Weiner engine for the same technology. But since most of my design real
estate is just the A5/1 engine itself, it would seem that key search in
hardware of A5/1 is likely to be less efficient that the same attack on DES.
Arnold Reinhold
