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

[mouse () Collatz McRCIM McGill EDU (der Mouse)]

> > Correct me if I am wrong - RC2 and RC4 are not public key
> > cyrptosystems, and hence are not "prone" to the problems with low
> > moduli.
> You are wrong.

They _are_ public-key cryptosystems??

> If the key is only 128-bit, that's a much smaller keyspace to
> brute-force attack than a 1024-bit key.

True as far as it goes...but I think you're missing the point.

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
easier than just making random guesses.  A good private-key cipher
presents essentially that problem: guessing a private value with no
information to go on.  Thus, if DES were ideal in this respect[%],
there would be no better way to crack it than trying one 56-bit key
after another until you find the one that produces sense rather than
nonsense upon decryption of the message[$].  Expected work: 2^55
attempts.  If we assume RC4 is ideal[#], the expected work to crack it
in this use (ie, 128-bit key) is 2^127 encryptions.

[%] 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.

[$] Telling sense from nonsense is another problem entirely, and is one
    reason why it's always a good idea to compress your data before
    encrypting it.

[#] I have no idea how close to true this is, and given RC4's recency
    in the public world, I doubt anyone else who can talk does either.

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.

                                        der Mouse

                            mouse () collatz mcrcim mcgill edu