Flaw in encryption through pseudorandom number stream (from PGP documentation)

Question

I was reading PGP docs and came upon a part written by Phil Zimmermann (PGP's creator) that piqued my curiosity:

When I was in college in the early 70s, I devised what I believed was a brilliant encryption scheme. A simple pseudorandom number stream was added to the plaintext stream to create ciphertext. This would seemingly thwart any frequency analysis of the ciphertext, and would be uncrackable even to the most resourceful government intelligence agencies. I felt so smug about my achievement.

Years later, I discovered this same scheme in several introductory cryptography texts and tutorial papers. How nice. Other cryptographers had thought of the same scheme. Unfortunately, the scheme was presented as a simple homework assignment on how to use elementary cryptanalytic techniques to trivially crack it. So much for my brilliant scheme. From this humbling experience I learned how easy it is to fall into a false sense of security when devising an encryption algorithm.

What techniques would be able to trivially decrypt text encoded in this way? It seems nearly equivalent to a one-time pad (which is unbreakable without the pad), provided that the pseudo-RNG is complicated enough (period much longer than encrypted text; mean size added to each character significantly larger than size of chars) and a suitably complicated seed (so you can't brute force every seed).

E.g., using a Mersenne-Twister (with a period of 2^19937 -1 ~ 4.3x10^6001 ) and a passphrase that generates a random 256 bit seed; it seems uncrackable without being given the seed.

Or did they generate simple random number generator with a period of 2^32 - 1 ~ 4.3 billion (it was the 70s; the Mersenne Twister wasn't even invented until the mid-1990s); where you could brute force try each of the 4.3 billion random seeds with a quick check of the cipher text to see if dictionary words appear or simple frequency analysis (lots of spaces and e)?

Answer 1

A PRNG being "good" (having strong statistical randomness guarantees, say, plus having a long period) says nothing about its security. See e.g. discussion in this thread.

The thread discusses the difference between:

• one time pads (unbreakable in principle as long as they are neither leaked nor re-used, but usually impractical)
• stream ciphers (which can be made as secure as necessary, and can be quite practical)
• PRNGs (that weren't designed to be cryptographically secure) used as stream ciphers (typically easily broken)

What Phil should have used was a stream cipher not just any old PRNG. MT (and earlier PRNGs) are not suitable for use as a stream cipher. Salsa20/ChaCha (by Dan Bernstein) and ISAAC are two specific stream ciphers. ISAAC is used by shred. Salsa20 is part of the EU eSTREAM/ECRYPT programme. Of course, Phil can be forgiven for not using a stream cipher: RC4 (which is considered broken -- its weakness are part of what makes WEP insecure -- but which is the basis for ISAAC) was only invented in 1987.

The cryptographic weaknesses of normal PRNGs (including MT and Wichmann-Hill) has lead to vulnerabilities in e.g. TCP sequence number attacks. Those vulnerabilities are sometimes addressed using a different sort of CSPRNG, which gathers entropy "as it goes" (e.g. from mouse/timing jitter). To be suitable for use as a stream cipher, a CSPRNGs must have all the input entropy available at the start, rather than gathering it as it goes. See the wikipedia pages on CSPRNGs and on /dev/[u]random.

Answer 2

I have no idea what the method Phil Zimmerman originally used for his encryption, so I can't really say anything about that.

However, Mersenne-Twister can be made in to a "secure" stream cipher, for example CryptMT. CryptMT was was subsequently broken, though: Distinguishing Attack on CryptMT. Reading that paper probably gives a pretty good idea on how to attack Mersenne-Twister and its ilk.

---

Actually, I did some more investigation. First of all, the paper I quoted has been subsequently redacted by the authors, see discussion here, and it was against CryptMTv1, not CryptMTv3 that is the current version. There are no known attacks against CryptMTv3. The closest to an attack I've found is On the Security of Stream Cipher CryptMT v3, which explicitly says:

However, we have not found any non-randomness about the keystream output.

Also, the eSTREAM final report for CryptMT says:

CryptMT v3. The cipher CryptMT has a very unusual design which delivers very reasonable performance. While there have been no negative cryptanalytic results against the cipher in the last phase of eSTREAM, we are somewhat concerned that the security of the cipher, in particular the non-linear filter component, might not yet be as well-understood as some of the other finalists. We anticipate that elements of CryptMT will continue to be of interest to the cryptographic community, and we hope that the full advantages of the approach embodied in CryptMT v3 can be evaluated. However, we are currently not sufficiently confident in the design and security of this algorithm for us to include it in the final portfolio.

Hardly a negative merit!

Also, looking at the "very reasonable performance" mentioned above at eBASH, it seems that CryptMTv3 offers amazing performance for long messages (for example, 1.82 cycles per byte for long messages), often only bested by Salsa20/8, where as Salsa20/8 has already been broken (barely, and Salsa20/12 is still very secure).

So I would say CryptMT is definitely a contender in stream ciphers even if it hasn't been analyzed enough yet!

Answer 3

Any simple XOR/PRNG cipher where the key is used to initialize the PRNG is vulnerable to a known-plaintext attack with complexity 1:

1. Encrypt a plaintext at least as long as the unknown ciphertext.
2. XOR the known plaintext with its ciphertext. This gives you the keystream.
3. XOR the keystream with the unknown ciphertext: this gives you the original plaintext.

If you can encrypt a plaintext consisting of all "0"s, you can skip step 2: the output of the encryption process is the keystream.

It doesn't matter what PRNG you're using: everything from RANDU to Fortuna is vulnerable to this sort of keystream-recovery attack.

Note that there are ciphers that use "XOR the plaintext with the keystream" as the core of their operation. However, they take precautions to prevent this attack: one-time pads never re-use the password, stream ciphers either require single-use keys or single-use values called nonces, and output feedback and counter block-cipher modes of operation use both the key and a second single-use value called an initialization vector to ensure the RNG is never seeded the same way twice.

Answer 4

I think the best way to approach this question as a cryptographic layperson is to step away from the modern cryptography and consider instead classical, paper-and-pencil ciphers. In this case, probably the best example to consider is the running key cipher:

In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream.

Basically, such a cipher takes a plaintext and an equally long natural-language text (e.g., a passage from a novel), and encrypts each letter of the plaintext by shifting it by an amount that depends on its corresponding keystream letter.

Such ciphers are easily breakable:

[I]f (as usual) the running key is a block of text in a natural language, security actually becomes fairly poor, since that text will have non-random characteristics which can be used to aid cryptanalysis. As a result, the entropy per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a cryptanalyst runs guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext - which can in turn be extended, and so on. Eventually it is likely that the source of the running key will be identified, and the jig is up.

The reason such attacks work is because:

1. The attacker normally has some partial information about the plaintext. In classical cryptography this would be the likely plaintext languages and topics (which imply letter and word frequencies and dependencies between consecutive letters and words). In modern cryptography, this would be things like the communications protocol that's being encrypted (e.g., HTTP over SSL), the endpoints of the connection (e.g., Google), etc.
2. A natural language keystream has patterns such that, given a few letters from the keystream, you to guess the next few letters with very high probability. Now the key thing to observe is that non-cryptographic PRNGs have this property as well, and therefore they admit of similar attacks.

This blog series describes how to break simple linear congruential RNGs and the Mersenne Twister. For the java.util.Random RNG, if you have two consecutive ints output from the PRNG, that's enough to reconstruct its state and predict the rest of the pseudorandom stream (both forwards and backwards). Therefore, if you used that PRNG to generate your keystream, an attacker who knows or guesses any eight consecutive bytes of the ciphertext can then apply a variant of the running cipher attack and the blog series' PRNG-cracking techniques to decipher the rest of the message.

Part 3 of the blog series describes how you can similarly predict the output a Mersenne Twister if you can get 624 consecutive output words. So it's harder than the linear congruential generator, but still vulnerable.