[RC5] My contribution to RC5
gindrup at okway.okstate.edu
gindrup at okway.okstate.edu
Fri Apr 3 14:27:22 EST 1998
It is not unreasonable to assume that a concerted "real" crack
against a ciphertext has the following information about the
1) What cipher was used to encrypt
2) What the keylength is
3) What headers were used to encode (wrapped) the plaintext
4) Who sent it
5) Who was to receive it
6) What (classification, not detail) the message contains
For most real communication, the important one of those is 3. Since
most headers have a well-defined format, non-compliant trial
ciphertexts generated in brute-force decryption efforts indicate a
failed attempt. 4 and 5 can also help you narrow down the legal
character set for the plaintext. 6 gives keywords to search for in
the trial plaintext.
Thus, 1 and 2 permit a brute-force attempt. 3 permits one to do
one-block decrypts that eliminate most trial plaintexts. 4, 5, and
6 can do "sanity checks" on the bytestream contained in the trial
ciphertext. The result is that *very* few trial plaintexts fall
through the automated procedure and so require human inspection.
Declassified material on the attempt to cryptanalyze Enigma during
WWII indicate that 3 through 6 were used in automated tools to
attempt decrypts and the few remaining "sane" trial plaintexts were
multiplexed to small armies of humans to categorize as "keep" or
This still applies to decryption attempts against encrypted data
today. All the known prefix is giving us is the "well-known header"
that normal transmitted data would have, e.g. IP and TCP headers.
Let's say we didn't know what it was, but we knew the plaintext was
ASCII (which means it's 7-bit clean). This means that there are 8
bits in the first (64-bit) block that must be 0 (the MSb in each
byte). Only one decrypted block in 256 will have this property.
Similarly, of the keys that "sanely" decrypt the first block, only 1
in 256 will sanely decrypt the second block. After 8 blocks, the
likelihood that the so-far-successful key is the correct key is the
same as what we have now with "probable" keys: 2^64 - 1 in 2^64.
We can compute the amount of effort for this attack as follows:
255/256 of the time a trial key is defeated in the first block.
of the 1/256 of the keys that are left,
255/256 of the keys are defeated in the second block
of the 1/256 of those keys that are left...
So, we want the sum of
255/256 * 1 + //most keys take one decrypt to toss
1/256 * 255/256 * 2 + //most that are left require one more
1/2^16 * 255/256 * 3 + //ditto
1/2^24 * 255/256 * 4 + ...
1/2^72 * 255/256 * 8
This means that one has to do about 1.004 trial decrypts per key to
use this decryption method to achieve the same amount of "thinning"
of the keyspace as the current method, 1 trial decrypts per key,
where we know the first block of plaintext.
Therefore, knowing the form of the header but not its content does
not terribly increase the amount of effort expended in the cracking
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: Re: [RC5] My contribution to RC5
Author: <rc5 at llamas.net> at SMTP
Date: 3/31/98 11:45 PM
Another thing to think about is we have a distinct advantage over a hacker...
We know what the first few bytes of the message is...
Ed Wensell III
Systems and Operations Support, Pellissippi State
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5