Re: Comparing Cryptographic Key Sizes

Peter Trei <trei@process.com> writes:
> Adam Back <aba@dcs.ex.ac.uk> writes.
> > 56 bit DES is probably roughly similar to 512 bit RSA in hardness to
> > break.
> 
> This is way off. We used ~457,000 MIPS years to search half of the 
> DES keyspace. Factoring a 512 bit modulus using the General Number
> Field Sieve (GNFS) would take about 28,000 MIPS years (see Schneier
> for the exact number - I don't have AC2 at hand)
> 
> Lenstra has estimated that with 500,000 MIPS years, you should be
> able to factor a 600 bit modulus using GNFS, if your workstations 
> had enough memory.

Ah yes.  Well I did read your post on coderpunks where you described
the results of asking Lenstra and looking for ideas for what to break
next, how hard 512 bits was etc.

So... 28,000 MIPs years you say... but that neglects memory.
Lenstra's conclusion was that even 512 bits couldn't be done, from
your post.  So by that measure it is harder (due to memory overhead)
than DES even though theoretically taking less MIPS with 64 mb
workstations.  Also he was unsure about the availability of a large
enough supercomputer to reduce the final matrix.

So any suggestetions of how to summarise the "hardness" of a problem
when it includes memory and cpu costs in as simple terms as possible.
(Bearing in mind the reader in most cases hasn't grasped the
difference between public key crypto and symmetric key, and is
comparing 1024 bit keys to 56 bit keys and probably thinks that it is
1024/56 times harder.)

> > About 10 years ago now Michael Wiener made a design for such a DES
> > breaking machine.  He estimated it would cost $10,000,000 to build a
> > machine which would break a 56 bit DES encrypted message a few hours.
> > His machine was scalable, pay more money, break the key faster, pay
> > less take longer.  The estimate was that could build one with enough
> > DES key searching units to break it in a day for $1,000,000.  That was
> > 10 years ago.  10 years is a long time in the computer industry.
> > Nowadays you build the machine more cheaply as chip technology has
> > progressed, and computers are much faster per $.  Estimates are around
> > $100,000 to build the machine (neglecting hardware engineers
> > consultancy fees).
> 
> Go back and check the numbers - if you don't the journalists will. 
> (I don't have this paper to hand either :-( ) The Wiener paper is 
> much more recent (93?) , and the cost much lower (I think it was 
> about $1M for HW and $500K for development costs, for a 3.5 hour 
> machine).

I think I have his paper as a postscript file, will look.

But what do you think of the extrapolation to todays prices?  $100k?
(Ignoring consultancy fees).

Thanks for the criticisms, more please on readability and
understandability to neophytes!

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

On Tue, 24 Jun 1997, Adam Back wrote:

> (Bearing in mind the reader in most cases hasn't grasped the
> difference between public key crypto and symmetric key, and is
> comparing 1024 bit keys to 56 bit keys and probably thinks that it is
> 1024/56 times harder.)

Well i guess i'll look stupid for asking but someone has to but what is 
the diffrence ?? I dont know either, i'm on this list to learn things 
like this. I'm still very new to all of this. I was aware that they 
weren't 1024/56 times harder though.

jason =8-]

On Wed, 25 Jun 1997, Jason William RENNIE wrote:

My first suggestion is to get hold of "Applied Cryptography" by Bruse
Schneier, my second suggestion is to find out if your uni runs causes in
infomation securaty (sounds something like that) and get into it via an
elective.

[...]

> Well i guess i'll look stupid for asking but someone has to but what is 
> the diffrence ??

A symtiric cryptosystem is one where the encrption key is the same as the
decryption key.  A nonsytric cryptosystem is one where the encryption key
is diffrent but realted to the decrytion key.

Non-symtric keys are normal weeker because there has to be that realtion
between the keys.

Please excuse my spelling as I suffer from agraphia see the url in my header. 
Never trust a country with more peaple then sheep.  Buy easter bilbies.
Save the ABC Is $0.08 per day too much to pay?  ex-net.scum and prouud     
I'm sorry but I just don't consider 'because its yukky' a convinceing argument

Jason William RENNIE <jrennie@hardy.ocs.mq.edu.au>
> On Tue, 24 Jun 1997, Adam Back wrote:
> 
> > (Bearing in mind the reader in most cases hasn't grasped the
> > difference between public key crypto and symmetric key, and is
> > comparing 1024 bit keys to 56 bit keys and probably thinks that it is
> > 1024/56 times harder.)
> 
> Well i guess i'll look stupid for asking but someone has to but what is 
> the diffrence ?? I dont know either, i'm on this list to learn things 
> like this. I'm still very new to all of this. I was aware that they 
> weren't 1024/56 times harder though.

They have very different properties.  Public key systems have really
nifty key management properties.

With symmetric key crypto (as ever) things are simple and intuitive.
You have some data, you have a key, and you can scramble the data with
the key, you get out gibberish.  Some jargon, the three parts are
called: your data = plaintext, scrambled gibberish you get out is
called ciphertext, and the key is the cryptographic key which enables
to be decrypted (de-scrambled, turned back into plaintext, that you
can read again).  To unscramble the data you'll need the key again.
If you send the message to someone, that someone also has to know the
key.

Big problem: how do you get the key to them?

Phone them up?  (Painful).  If you can contact them securely why
bother with crypto in the first place.  Just tell them what it is you
want to tell them over the phone.  (Not that phones are secure, of
course).

Then Whitfield Diffie and Martin Hellman invented the first practical
public key crypto system (1976).  With public key systems you have two
keys.  One is called the public key, you give this to everyone.  The
other is the private (or secret) key which you tell no-one.

Anything encrypted with the public key can be decrypted with the
secret key.  As you can tell anyone the public key you can list it in
a directory service much like you list your phone number in the phone
book.  PGP keyservers are examples of such electronic directories of
public keys.

Now anyone who wants to send you a message just gets your public key
(from you, or from a keyserver), encrypts it to you, and sends you the
encrypted message.  So now a perfect stranger half way around the
world can encrypt a message to you, safe in the knowledge that no-one
but you can read it, not even the NSA.

Everything is beautiful and rosy.  (Well everyone except the NSA, who
thinks everything has gone all dark and horrid, 'cause they used to
have fun reading all our comms, but it's too late anyway, because we
all know how to do it now.  And folks like Tim May enthuse about the
possibilites of crypto anarchy, where we can be free from our
respective governmental leeches, by avoiding 50% tax rates, as
information workers working for cypherspace corporations situated in
off-shore tax-havens, or even situated no-where except cypherspace.
Cypherpunks dream.  NSA nightmare, government leech nightmare, spook
and leech job losses, plumetting tax revenues, lay-offs, radical loss
of government power and significance etc, etc.  You ought to read Tim
May's cyphernomicon at this point.)

Returning to technical matters, there is a minor fly in the
ointment... the man in the middle attack... so now we need
authentication.  We need digital signatures.  And things just got a
bit more complex in the key management area.

(We'll save those for lesson 2.  Someone else?)

Should this go in the comparing keys document?  Or is it going to
suffer bloat turning into another introduction to crypto?

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`