[rc5] Some (Not So) Deep (Frequently Asked) questions

andrew meggs insect at antennahead.com
Mon Aug 18 16:14:59 EDT 1997

>Specifically, how are the results checked?  What knows
>when we've hit the right key?  Does the client, do the
>servers?  And how do they know it?  I understand there is
>a known string in the message.  If the clients or severs
>simply try a key, then test for this known string, that's
>not very realistic.

They do test for the specific string, and it IS very realistic. Most data
formats contain some known bytes so they can be recognized. A GIF file
begins with the string "GIF89a", for example. If you can't guess the
filetype, strings of zeros are always a good indication that you've found
computer data. At an extreme end, you can use information theory to measure
the redundancy in the resulting data -- people (and programs written by
them) generally express information in a form that emphasizes ease of use
over compactness.

If you think the resulting data is going to consist of printable ASCII
characters, then you'll be able to throw out 99.9619% of the keys just from
decrypting a single block, because only 0.0391% of all possible sets of 8
bytes are free from any non-printing characters. And if you decrypt five
blocks, then statistically speaking fewer than 1 in 2^56 keys will produce
40 bytes of printable text, so if you get that much text you've almost
certainly found your key. Using a more sophisticated detection method that
accepts only English-like text rather than any ASCII text (including
strings like "^bn#mnQ"), you'd be able reject keys after even fewer blocks,
although you'd have to measure the cost of this test against the cost of
doing more decryptions -- RC5 decryption is pretty fast once you've done
the setup for a particular key.

>Suppose I type up a letter and encrypt it.  Now
>somebody wants to break it.  Since they don't know what is in
>the letter, they probably can't do string matches for certain
>words.  Maybe they could look for words like "the" "is" etc.
>But what if my letter doesn't contain those strings?  Suppose
>before encrypting it, I do a simple ASCII+1 to every character.

So what if they did something else to the plaintext before they ran it
through RC5? Like compressing it to eliminate our beloved redundancy, or
another two RC5 encryptions (for various reasons just one extra encryption
isn't significantly more secure than a single encryption), or a ROT-13, or
even a simple XOR with $FF? Simple...we decrypt and then undo whatever they
did before they encrypted. If they did gzip -c | encrypt, we do decrypt |
gunzip -c, and then do our tests on that (assuming we weren't smart enough
to just look for the header in gzip files!).

You're probably going to say, "How do we know what they might have done
before they used RC5?" That's missing the big picture -- the answer to that
is, "How do YOU know they even used RC5?" They could have easily used RC5
with a different number of rounds, or even DES or IDEA or RC4 or RC2 or any
of the literally thousands of cyphers out there. The assumption in a
decryption attempt is always that you know what mechanism is being used,
just not the key for that mechanism. One can always disassemble code or a
machine, and finding or steal or buying a computer or radio or phone to
take part isn't that hard. It's the knowledge that's carried only inside
the heads of people who walk around with cyanide pills so they'll die
before you can torture the key out of them that we're trying to replicate.

>2.  Now a second deep theoretical question...
>Suppose I use the same algorithm to encrypt a message twice
>with two different keys.  It would not surprise me if
>this double encryption could be solved by a third unique
>key; like the third side of a triangle will get you to
>the same point.  Is this true?

In algebraic terms, you're asking if the set of RC5 keys is a group. I'm
not sure; I don't think anybody is. It's a new algorithm and hasn't been
studied extensively yet. The reason the RC5 clients run more slowly than
the deschall clients isn't that RC5 involves more work (it doesn't!), but
that DES has been studied extensively and we know ways to short-circuit
parts of the work if we're interested in checking a lot of keys in sequence
rather than doing actual decryption. We know (or at least believe) DES
isn't a group. There are (2^64)! ways to map a set of 64-bit plaintext
blocks onto a set of 64-bit cyphertext blocks, but only 2^56 keys, so
there's certainly plenty of room for RC5 to not be a group either.

[For the non-numeric, the ! means factorial, not an exclamation about the
size of 2^64. (2^64)! means (2^64 * (2^64 - 1) * (2^64 - 2) * (2^64 - 3) *
... * 4 * 3 * 2 * 1), and it's an incomprehensibly huge number.]

On a more general note, even if RC5 isn't a group, there's a time-space
tradeoff that would allow you to break a double encryption in only twice as
many operations as a single one. Since the key size in RC5 is variable,
you'd do better to just use one 112-bit key than two 56-bit keys.

Andrew Meggs, content provider                  Antennahead Industries, Inc.
<mailto:insect at antennahead.com>                 <http://www.antennahead.com>

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

More information about the rc5 mailing list