Re: Non-PK encryption not vulnerable via low key length?!

[jhill () srd bt co uk (Jake Hill)]

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