[rc5] RC64 keyspace

Ryan Dumperth woodie at indy.net
Mon Oct 27 18:23:51 EST 1997


>>So the best way we have to break the encryption is to use brute-force.
>>Unless you know something we all don't.  ;-)
>
>This is not true.  All encryption techniques have flaws.  There are
>mathematical ways to elimate portions of the keyspace.  This depends on
>the encryption method and your knowledge of the problem:  known
>plaintext, unknown plaintext, etc.  Now, we have an easier one:  known
>plaintext--we know a portion of the plaintext!
>
>I don't remember specifically the flaws in RC5.  Does anybody have
>Applied Cryptography handy?  It will probably show how to eliminate parts
>of the keyspace.

>From Applied Cryptography pp.345-346:

"RC5 is new, but RSA Laboratories has spent considerable time analyzing it
with a 64-bit block. After 5 rounds, the statistics look very good. After 8
rounds, every plaintext bit affects at least one rotation. There is a
differential attack that requires 2^24 chosen plaintexts for 5 rounds, 2^45
for 10 rounds, 2^53 for 12 rounds, and 2^68 for 15 rounds. Of course, there
are only 2^64 possible chosen plaintexts, so this attack won't work for 15
or more rounds. Linear cryptanalysis estimates indicate that it is secure
after 6 rounds. Rivest recommends at least 12 rounds, and possibly 16. This
number may change."

This is Applied Cryptography's description of the chosen plaintext attack
(p.6):

"The cryptanalyst not only has access to the ciphertext and associated
plaintext for several messages, but he also chooses the plaintexts
encrypted. This is more powerful than a known-plaintext attack, because the
cryptanalyst can choose specific plaintext blocks to encrypt, ones that
might yield more information about the key. His job is to deduce the key
(or keys) used to encrypt the messages or an algorithm to decrypt any new
messages encrypted with the same key (or keys)."

Although the ciphertext we are tackling was encrypted with 12 rounds
(RC5-32/12/8), we have only one message encrypted with the key we need to
find, not several as this definition stipulates. I believe this rules out
the possibility of a chosen plaintext attack on this key, although my
knowledge is minimal. Additionally, a chosen plaintext attack requires
large amounts of memory, and I don't know that its implementation would be
as conducive to a distributed effort as the brute force attack we are
waging.

-================================================-
Public Key: http://keys.pgp.com:11371/pks/lookup?op=get&search=0x8D98E677
PGP Key Fingerprint: 4913 67E3 BCA8 6326 F404  6005 6C1B D2D8 8D98 E677
PGP, use it or lose it.


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list