[1292] in bugtraq
Re: Non-PK encryption not vulnerable via low key length?!
daemon@ATHENA.MIT.EDU (Jake Hill)
Fri Mar 17 14:08:48 1995
From: Jake Hill <jhill@srd.bt.co.uk>
Date: Fri, 17 Mar 95 15:13:56 GMT
To: bugtraq@fc.net
der Mouse said
> If you're trying to attack a 1024-bit public RSA key, this is on a par
> with the difficulty of factoring a 1024-bit number. This is much
> easier than brute-forcing a 1024-bit secret key - I don't know how hard
> factoring is nowadays, but I'm quite certain it's a hell of a lot
A systolic multiple polynomial quadratic seive factored the RSA challenge
number in about a month (this is a 110 (decimal)digit number). However,
factoring difficulting increases rapidly with the size of the number, such
that factoring a 60 digit number is about 3000 times as hard as factoring
a 40 digit one.
> [%] DES isn't ideal for various reasons. It is known to have some weak
> keys, there is an attack known that (if memory serves) allows
> breaking it with 2^47 known plaintexts, and another that works with
> 2^47 chosen plaintexts. Still, 2^47 is a lot of work.
Biham and Shamir's differential cryptanalysis was breaking 8 round DES in
a few minutes on a PC back in 1990. This translates to about 2^16 operations.
Note that this is a chosen plaintext attack on the cipher. Linear cryptanalysis
(Matsui) give similarly impresive results (2^21 known plaintexts). There have
been no useful ciphertext only attacks proposed (to my humble knowledge).
> Key size comparisons between cryptosystems should be taken with a large
> handful of salt, at least until you've looked carefully at what
> breaking those keys entails.
Very true, but note that exhaustive searching of small key spaces (say
<2^64 keys) is becoming possible on dedicated hardware. Someone (can't
remember who) proposed a machine for searching the DES keyspace in a few
_days_, which you could build for about $1M. For what it's worth, $1B would
buy you a machine to do it in a few hours.
Anyway, I think we're getting a little bit tangental now...
Regards,
Jake.
Food for thought? Or mindless tripe?
A.A.&.T..I.N.F.O.R.M.A.T.I.O.N..S.Y.S.T.E.M.S
JakeyBaby% mail jhill@srd.bt.co.uk
Techno.Crypto.Emusic
