[1074] in cryptography@c2.net mail archive
Re: Thoughts on the next target.
daemon@ATHENA.MIT.EDU (Paul Bradley)
Tue Jun 24 12:57:27 1997
Date: Tue, 24 Jun 1997 14:43:38 +0000 ( )
From: Paul Bradley <paul@fatmans.demon.co.uk>
To: Peter Trei <trei@process.com>
cc: coderpunks@toad.com, cryptography@c2.net, trei@process.com
In-Reply-To: <199706231946.MAA00236@toad.com>
> 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.
I would estimate that the number of machines drops of more rapidly around
8MB, most new PCs are still only sold with 16MB (ugh!).
I cannot comment on the memory requirements for GNFS (far be it from me
to question lenstra </action bows down and worships ;-)> but can`t matrix
methods bring this down? Isn`t there some way to re-combine witnesses to
possible factors for the GNFS, rather like the Gaussian matrix
re-combination done with QS? Can a different form of matrix reduction
lower the individual workstation RAM requirements at the expense of
needing a beefier machine to recombine at the end? What about the Double
Large prime variation, isn`t that significantly quicker than vanilla QS?
> 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.
This is a major problem... I would guess most people who did run the DES
software did so because of the free crack at $10000 just for burning idle
cycles.
> 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.
Pros:
No actual large distributed search needed, just a couple of coders and a
few days on a couple of average PCs
Would attack common software, Joe Public doesn`t really know what DES is,
if he owns a PC he probably knows what Micro$oft office, for example, is.
More good PR for strong crypto.
Cons:
Encouraging more manufacturers to write two versions of products, one for
domestic use and one for export, tends to lend more credibility to export
controls in the eye of Joe Public.
Would not be technically impressive, just another good PR stunt and a
chance to gloat at stupid manufacturers who use proprietary algorithms or
small key sizes.
A nice attack, although more likely to get someone into trouble, may be
to attack a real online banking system which allows 40 bit SSL sessions,
then post the customers balance all over the place (real name, address etc.
removed for obvious reasons of course). The sqeamish ossifrage 40 bit SSL
crack was good, this would be even better because it would make the
public sit up and listen, non-technical people hate losing money just as
much as anyone else.
As I see it banking is the system to attack, as it is the real public
"killer-app" of cryptography at present, and gives a real quantifiable
cost of a key break.
Datacomms Technologies data security
Paul Bradley, Paul@fatmans.demon.co.uk
Paul@crypto.uk.eu.org, Paul@cryptography.uk.eu.org
Http://www.cryptography.home.ml.org/
Email for PGP public key, ID: FC76DA85
"Don`t forget to mount a scratch monkey"
