How to beat a substitution cipher when adding a pseudo-random number stream?

Question

From view-source:https://web.archive.org/web/19990224060310if_/http://www.cl.cam.ac.uk:80/PGP/pgpdoc1/pgpdoc1_29.html:

When I was in college in the early seventies, 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. So cock-sure.

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.

By Philip Zimmermann, according to the about page of that same website. Emphasis mine.

The crux of it is "A simple pseudorandom number stream was added to the plaintext stream to create ciphertext." This can be read multiple ways:

• it is added to the end (unlikely)
• it is interjected as in "h4e7l2l5o" (also unlikely, unless he meant the numbers are turned into letters, in which case I find it somewhat unlikely)
• the numbers are added to each character

The latter seems like the only sensical option to me. But as far as I know, adding (equivalent to xor, security-wise) random numbers to each position is actually secure, assuming a good source of randomness. But it sounds like the scheme is broken using "elementary cryptanalytic techniques", not the underlying RNG. And of course the RNG (which has to qualify as CSPRNG) is the crux of such an algorithm, not the way of mixing its output with the plaintext.

The only thing I can think of is that it is unauthenticated, but that's rather a flaw in bad usage and not in this primitive itself. Does anyone know what "elementary cryptanalytic techniques" Phil is talking about? He makes it sound as though any basic cryptographer should have come across it and would know what it means (and how to break it), but I don't.

Answer 1

Phil Zimmermann here. Yes, it was modulo addition of bytes from the pseudorandom number generator, and subtraction at the receiver end. Essentially a stream cipher. The fatal weakness was that I used a linear congruential generator, seeded by the key. As weak as an LFSR. I knew nothing at that time about the weakness of linear generators. It was 1973. I was clueless. There were no crypto courses available in the university in that era.

This was not the last time I attempted home-grown crypto algorithms. Later, in PGP version 1.0, I developed my own block cipher design called Bassomatic, a cautionary story I have told elsewhere. From this humiliating experience I learned to only use extensively peer-reviewed algorithms.

-prz

Answer 2

I think that your assumption that the "pseudorandom number stream" qualified as a CSPRNG is likely not correct.

You are correct in the idea that modular addition can be as secure as using XOR to create a one-time-pad. However, one-time-pads are not secure if the key stream is not secure. The other options you mention for adding the pseudorandom number stream cannot even be called obfuscation, so I sincerely doubt that they apply.

And that's about all we can tell, because this is just brought as an anecdote to start the rest of the chapter about snake oil products by Phil Zimmermann. But hey, we live in the golden age where most of our hero's are still alive. Why not contact him and ask?