[1064] in cryptography@c2.net mail archive
Thoughts on the next target.
daemon@ATHENA.MIT.EDU (Peter Trei)
Mon Jun 23 18:36:26 1997
From: "Peter Trei" <trei@process.com>
To: coderpunks@toad.com, cryptography@c2.net
Date: Mon, 23 Jun 1997 15:46:47 -6
Reply-to: trei@process.com
CC: trei@process.com
I've been doing a bit of research on things that could be 'the
next target', and I thought I'd share them with you.
My estimate of the cpu expended in the DES Challenge - adding up
the centralized efforts and pretending that they are all using 32
bit, non-bitsliced algorithms, is around 450,000 MIPS years.
Four things come to mind as a 'next target'.
1. RC5-56
2. RSA-140 (140 decimal digits, about 465 bits)
3. RSA-155 (about 512 bits)
4. Inadequately encrypting commercial software.
RC5-56.
There is already an effort underway to do this, and many of the
people involved in the DES Challenge have moved over to it. It
seems less attractive to me for two reasons:
i. RC5 is nowhere near as widely used as DES.
ii. There's a certain sense of 'been there, done that' about it.
Two RC5 challenges have already been met - the 40 and 48 bit
tests. From these, we know that (a) the software works, and
(b) it's 4-5 times slower than DES clients. Given that we
might not be as lucky as we were in DES (where we hit the
key at about the 1/2 way mark), I'm not sure we can sustain
the effort needed to get the key.
iii.The political impact of cracking RC5-56 is far less than
that of cracking DES, though it does show that 56 bit
encryption in general is weak, not just DES.
RSA factorizations.
[Below, references to 'RSA-512' actually apply to RSA-155 -
512 BITS is roughly 155 DECIMAL DIGITS]
In an earlier post, I speculated about factoring RSA-135. It
turns out that the RSA challenges go up in steps of 10; RSA-140
is the next one. There are a few special cases, such as RSA-155,
which corrospond to popular modulus lengths.
Bruce Schneier estimates that factoring a 512 bit modulus using
the General Number Field Sieve (GNFS) would take about 28,000
MIPS years, far less than we took for DES. Lenstra, in his
paper "The Magic Words Are Squeamish Ossifrage", which reports
the factorization of RSA-129 using the Quadratic Sieve (QS),
estimates that factoring RSA-512 using QS would take 500,000
MIPS years.
Fine and dandy, it looks like we can easily kill RSA 512 using
GNFS, right?
Wrong.
I've been researching this with the help of my contacts at RSA,
and email with Arjen Lenstra. It turns out that we probably
can't use GNFS for RSA 512, and QS would involve a lot more
cpu time then it looks.
Both techniques use 'sieving', in which the clients have to
access, more or less randomly, a huge array of data. This
sets a lower bound on the memory size of each client. In
RSA-129 with QS, that limit was 8M. Lenstra estimates that
while 500,000 MIPS years in GNFS would, in principle, be able
to factor a 600 bit modulus (about RSA-180), the memory required
would be around 128M, *per-client*. There just aren't that
many 128M machines around yet. I suspect that the number of
machines available drops off very rapidly above 16M.
Secondly, even if the memory is available, performance would
be much less than in the DES Challenge. For DES, the entire
search engine could fit in the L1 cache of a Pentium, and the
task never had to go off-chip to the L2 cache or main memory.
This is not the case in QS or GNFS, and the task would be
bogged down by cache misses and memory access.
Thirdly, both techniques require a final matrix reduction
step in which all the data from all of the clients must be
correlated. This requires a huge-memory supercomputer. Lenstra
suspects that the processing power neccesary to do this step for
the GNFS technique is simply not available.
In principle, we could factor RSA-512 with QS - the memory
requirements for both the sieving and matrix steps are much
gentler than GNFS, but the number of cpu-hours required would
exceed that used by the DES Challenge by a non-trivial factor.
Finally, with QS and GNFS there is not clear way to identify a
given client as having 'found the magic key', the prize money
goes to the entire effort, rather than to an individual. The
kitty currently stands at a little under $18,000.
Inadequately encrypting commercial software.
We got a lot of bang out of brute-forcing 40-bit RC4 in the
export version of 'Netscape Navigator' a couple years ago,
partly because there was an identifiable and well known
target which *had* to respond to the crack (which Netscape
did with speed and grace). We could do this again.
I recently had cause to investigate the cryptography used in
one of the applications of a very popular office suite, released
this year. A password recovery specialist I spoke to claimed that
the crypto used was 40-bit RC4! If this is true, it may apply to
all of the applications of that suite, and thus the apps are
susceptible to brute force attacks of quite modest scale - ones
which may be undertaken in a small office in a relatively short
time.
Producing key search apps which can brute the crypto in this
suite would force the manufacturer to answer as to why it chose
such poor cryptography, and produce a stronger (albeit currently
unexportable) version. It would also light a fire under the
manufacturer to lend it's not inconsiderable weight in the
export battle.
The above are my personal thoughts which do not neccesarily
represent those of any other person or any organization. I'd
appreciate comments.
Peter Trei
