Breaking misused stream ciphers

Encryption algorithms can be classified in a couple of different ways.  A top-level distinction is between symmetric encryption algorithms (which use the same keys for encryption and decryption) and asymmetric cryptography (which uses different but related public and private keys).

Within the symmetric encryption category, another distinction is between block ciphers (which encrypt data in fixed-size chunks) and stream ciphers.  Stream ciphers generate a string of bits, which the plaintext is exclusive-ored (XORed) with.  This makes stream ciphers a less secure but more usable variation of the one-time pad.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Stream cipher use and abuse

Stream ciphers, like the one-time pad, are designed to use a distinct encryption key for each plaintext/session or to maintain state between sessions (i.e. don’t start over each time).  The reason for this is that, when using the same encryption key for multiple sessions, starting at the beginning for each session results in all plaintexts being exclusive-ored with the same string of bits.

If this occurs, the stream cipher is vulnerable to the same potential attack as a one-time pad with key reuse.  Exclusive or-ing two ciphertexts encrypted using the same bit stream results in the XOR of the two plaintexts.  This is because 

(P1 XOR K) XOR (P2 XOR K) 

= (P1 XOR P2) XOR (K XOR K) 

= (P1 XOR P2) XOR 0 

= (P1 XOR P2)

While this may not be a big deal for some messages, the way that text is encoded on a computer can make a misused stream cipher vulnerable.

Attacking stream ciphers

On a computer, text needs to be represented as a binary number in some way.  The most common way to do so is by using ASCII.

The image above shows a table of ASCII characters.  A fully textual message would likely mainly consist of letters (0x42-0x5A and 0x97-0x7A).

Notice that the uppercase and lowercase versions of each letter are lined up with each other in the table.  This is because the table is organized into 0x20 (32) rows and each pair of the same letter is represented by values 0x20 apart.

This becomes significant because of the value that is represented as 0x20 in ASCII: a space.  When a one-time pad or stream cipher is misused, XORing the ciphertexts is equivalent to XORing the plaintexts.  This means that any space characters in the text only serve to flip the capitalization of the corresponding character in the other plaintext.

For example, consider the plaintexts “Do not misuse stream ciphers” and “It messes up confidentiality”.  In ASCII, the XOR of their ciphertexts (with a misused stream cipher) would be 0d 1b 00 03 0a 07 53 08 1a 53 00 03 45 43 1c 1a 14 0c 05 08 4e 17 00 11 04 0c 06 0a.

Looking at this, we can learn a few things:

• Any zero byte has the same character in both locations (true for three characters)
• Anything that maps to a capital letter in hexadecimal is likely that letter in one string and a space in the other (true for five characters)

As a result, we learn a few characters:

0d 1c

1b 1a

00 Same 14

03 0c

0a 05

07 08

53 Space and s 4e Space and n

08 17

1a 00 Same

53 Space and s 11

00 Same 04

03 0c

45 Space and e 06

43 Space and c 0a

While this isn’t a full decryption, it’s a good starting point.  From this, it is possible to make some guesses.  For example, if the third character is a space, the first two are two two-letter words whose characters differ by 0d and 1b.  Working through the options would reveal Do and It as options.

A brute force search on a computer using the character differences and an English wordlist as a guide would eventually crack the entire message.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Conclusion

Stream ciphers can be an effective and secure option for encryption.  However, if they are misused, it is possible to crack the encryption.  This is why two plaintexts should never be encrypted with the same bitstream from a stream cipher.

Sources

XOR

One-Time Pad Cipher

ASCII Table