1
$\begingroup$

For message $ m $ and key $ k $ I get encrypted message $ c $ ($ m \oplus k = c $) where $ length(k) < length(m) $. Additionally I know that message $ m $ is English text. Instead of using pure brute force method, I want to narrow possible keys, by estimating key length using language pattern like “relative frequencies ordered by frequency” Letter frequency. So for example, for key with length 3, I should get three sets: $ \{c_0, c_{0+3}, c_{0+6}, …\}; \{c_1, c_{1+3}, c_{1+6}, …\}; \{c_2, c_{2+3}, c_{2+6}, …\} $, and each of this sets should somehow be compared with relative frequencies pattern. What is the best method (statistical?) to compare this sets with pattern, and final score for each key length, with scores for other keys length?

$\endgroup$
2
$\begingroup$

I am basing my answer on Cryptopals.

The basic idea is that as {c0,c0+3,c0+6,…} have all been xor-ed with the same byte, the number of differing bits between c0 and c3 is the same as between p0 and p3. (this number is called the Hamming distance between two characters.

Furthermore, the distance between [c0 c1 c2] and [c3 c4 c5] is the same as between [p0 p1 p2] and [p3 p4 p5], assuming the key length is 3. In regular English text, the hamming distance between two blocks of plaintext should be small, as the letters actually used occupy a highly ordered small fraction of the total ASCII range.

However, the distance between [c0 c1 c2 c3] and [c4 c5 c6 c7] would be ~50% of the total number of bits, because the xored key does not "cancel itself out".

So iterate over a range of possible keysizes, and compute the hamming distance between the first two blocks. Then normalize this result by the keysize.

The lowest value should correspond to the keylength.

Now you have a many time pad, where many = len(m)/keylength.
Each message is [c0 c1 c2] or [c3 c4 c5] or [c6 c7 c8]

Once you know this, then apply frequency analysis to {c0,c0+3,c0+6,…};{c1,c1+3,c1+6,…};{c2,c2+3,c2+6,…} independently to find each key byte.

You could also apply crib dragging. This is basically where you guess that a word is in a certain spot

There is also a cool attack that relies on a quirk of ASCII: 'a' ^ ' ' = 'A'. That is, xor-ing an English letter with a space simply flips the sign.
Helpfully, spaces are statistically the most common "letter" in English text.

If you take {c3,c6,c9,c12,…} and xor each byte with c0, you get {p3^p0, p6^p0, p9^p0,...}.
If this resulting sequence is mostly (~70%) in the range of "a-z" union "A-Z", then 9/10 times, p0 is a space.

You can of course instead xor the sequence with p3 or p6 or ... to check if that character is a space. Given a long enough message, one of the plaintext characters WILL be a space, and then you can instantly get every other plaintext characters which were xor-ed with the same key byte!

As a rule of thumb for attacking N-time pads:

  • Frequency analysis works once N =~ 6 and is a joke below that
  • Crib dragging becomes slow past N =~ 8, but is your best bet for small N.
  • Finding spaces works better than frequency analysis at ALL message sizes. It works even on 2-time pads.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.