# Why not the one-time pad with pseudo-number generator

I am very new to cryptography (so be kind), but I have a question that may seem silly.

If the one-time pad is the perfect cipher and impossible to crack, why would the following algorithm not be one of the strongest:

To encrypt

• generate a random bit array using a pseudo number generator with the key as the seed
• The generated bit array is the size of the data
• use a simple XOR to encrypt using the generated bit array

To decrypt

• psuedo random number generator will generate the same bit array with the same seed (the key)
• generate bit array the same size of the encrypted data
• run XOR on encrypted data using bit array that's generated

This is very simplified, but you can imagine how for larger encryption you could break down the data into blocks, and in order to ensure that the block bit arrays are random a new seed for each can be derived from the key. So if f(k) is the pseudo random number generator, and b is the block number, you can encrypt each block with f(k+b). (k is key)

Instead of using a psuedo random number generator, you could use some hash algorithm to generate the pad.

Ceteris paribus (assuming you can use equivalently strong keys) would this not be a very strong cipher method? Perhaps it may be strong and heavy on memory since the pad needs to be the size of the data. So during encryptiona and decryption you need to generate a pad that's equivalent to the size of the data.

Is there a flaw in this algorithm or would something like this not be practical and much slower than current standards?

-

It's a good question. As pg1989 said, this is the basis behind stream ciphers, which are very fast in practice.

I thought I'd quickly expand upon your statement that "the one-time pad is the perfect cipher and impossible to crack." This is true, in a sense, but it's worth pointing out that sometimes an attacker wants to do something simpler than "cracking" the encryption scheme in order to recover all plaintexts.

For instance, an attacker may just want to change the message so that the honest recipient decrypts something else. As a simple example, suppose that the attacker knew for sure that the message was either "yes" or "no!" and just wants to change the message to the other value. Note that:

1. This is simple to do for messages encrypted using a one-time pad. The linked Wikipedia page describes why this is true, but it's probably more fun to figure it out for yourself.

2. The attacker can do this without learning the plaintext. Hence, the original claim of a one-time pad being uncrackable is still true.

There are some other issues with a one-time pad construction too, such as the fact that usually some state will be required to make sure that you don't re-use the seed during the next encryption. Hence, while your question is definitely not silly, and stream ciphers are very useful in certain circumstances, they also have their limits.

-
Awesome answer. Thank you. But if the key between the two parties is absolutely secret, how can the attacker change the message? The wiki article dealt with RSA encryption where there is a shared public key in addition to the private keys. I might be missing the connection though. –  dardawk Sep 19 at 13:27
One Time Pads do not provide data integrity. So an attacker can change the message and the receiver won't know that the data has been changed. The attacker cannot recover the plain text, but they can change the cipher text. Mayank's yes/no is an example of this. The attacker can see Yes or No's cipher text and can change this cipher text so the plain text is changed when the receiver decrypts it. I learned this from the class pg1989 recommended. –  l3v Sep 19 at 13:41
Hmm, but if "Yes" is encrypted using the pad, the attacker does not know the message or the pad so if they try to send something else, decrypting an attacker's message with the original pad will surely produce garbage? Of course, this method is useless against a plain-text attack since the user gen infer the pad very easily. Is this what you mean? Again, I'm just at the beginning of the course so perhaps I just need to be patient. :) –  dardawk Sep 19 at 14:35
@dardawk Well, lets imagine that you are sending single-bit yes/no messages that you are encrypting using a one-time pad shared between you and the recipient. By XORing the bit with a shared secret bit, you can ensure that, whatever the message you are sending, nobody listening in on the line will be able to tell whether the message means yes or no. However, by just inverting the message bit, the attacker can derive a valid cryptogram for the opposite value. Then they can send it to the recipient, who will see 'yes' if you sent 'no, and 'no' if you sent 'yes'. –  AJMansfield Sep 19 at 15:03
Let $m \in \left\{ { \text{yes}, \text{no!} } \right\}$, $k$ be a random key, and the ciphertext $c = k \oplus m$. You wish to modify $c$ so that it decrypts to the other possible plaintext. Let $x = \text{yes} \oplus \text{no!}$. Calculate $c^\prime = c \oplus x$. This is your new ciphertext. Note that if $m = \text{yes}$, $c' = k \oplus \text{yes} \oplus \text{yes} \oplus \text{no!} = k \oplus \text{no!}$ and if $m = \text{no!}$, $c' = k \oplus \text{no!} \oplus \text{no!} \oplus \text{yes} = k \oplus \text{yes}$. –  Stephen Touset Sep 19 at 17:35

Yes, this is a widely-used cryptographic construction called a stream cipher. For more information about this and other encryption schemes, Coursera's cryptography class is a good resource.

-
Thanks! I enrolled in that course. –  dardawk Sep 19 at 13:23

If using a cryptographically-secure random number generator then the result is a stream cipher. If using actual random numbers, then it's a one-time pad.

Any output you get from a random source needs to be run through a randomness extractor anyway in a 2:1 ratio (2 bits in, 1 bit out).

Don't forget to provide a MAC along with the ciphertext to prevent an attacker altering the message.

If you want to use CSPRNG don't use just one algorithm. There's potential for a powerful attacker to determine a pattern from it. Generate a few separate keys with quality randomness of 512 bits+ length each. Then with each key generate a separate key stream using a different algorithm. Then combine/mix the streams together, perhaps with XOR.

Don't forget you need a way to keep in sync with the other person even in network failure so you don't re-use part of the stream/pad.

-

Congratulations you just reinvented the stream cipher.

The main strength of the one-time pad is that the key space is as large as the message space. This means that any cipher-text only attacks always fail because all plaintexts are valid.

This automatically means that any construct that decreases the key space (like using a seed for a PRNG) severely weakens the one-time pad.

Besides this a one-time pad (and the XOR based stream cipher) is very vulnerable to repeated-key attacks while there are other ciphers which are (more) secure against it.

-

From what I understand from your question, you are describing a stream cipher.

If the one-time pad is the perfect cipher and impossible to crack, why would the following algorithm not be one of the strongest ...

You're on the right track; a one-time pad is essentially a perfect (unbreakable) stream cipher.

Without going into (any) mathematical details, the main difference between your average stream cipher and a one-time pad (OTP) is that an ideal OTP requires a random key at least as long as the plaintext, whereas your average stream cipher requires a key length of only N, regardless of plaintext size. (Assuming keys for both cases are completely random).

In a perfect universe, your stream cipher would use a short key size to come up with an unguessable, unpredictable, completely random number of length equal to the plaintext, and XOR the two together.

What, however, would be the purpose of that? If the end result of the cipher is nondeterministic, there would be no way, given only the key, to recover the original message.

What we need then is a deterministic mathematical function where we can create a long string of predetermined digits given a particular input (the key), which are otherwise (very) unlikely to be guessed without the key.

Our system's security is now defined by the weaker of either our key size, or the flaws in our mathematical function.

-
Right. What I meant by the pseudo random number generator is the deterministic f'n that would output a long string unique to the key. I used the pseudo random number generator just because it was fresh in my mind. Thanks for your answer! –  dardawk Sep 19 at 13:31

This is indeed a good question; let me try to make it a bit more precise. Suppose:

• Alice has a plaintext message of some number of bits, call it p.
• Alice and Bob share a crypto-strength random number generator that generates n truly random bits.
• Alice and Bob share a pseudo-random number generator that can take a seed of size n and produce one of 2n sequences of p bits.
• Alice and Bob have an insecure channel and a secure channel.
• Alice (or Bob) creates a truly random key KEY of size n and sends it to Bob (or Alice) over the secure channel.
• Alice creates a pseudo-random sequence SEQ of size p and xors it with the plaintext to produce a ciphertext of size p
• Alice sends the ciphertext to Bob over the insecure channel.
• Bob decrypts the ciphertext in the obvious way.
• Details of the system are not part of the key. That is, the attacker should be presumed to know precisely how the PRNG works.

Ok, so first of all, the obvious criticism is: if Alice and Bob have a secure channel then why are they messing with encryption at all? And the answer is: the secure channel may be more expensive or only available at inconvenient times.

The second obvious criticism is: if Alice and Bob have a device that can generate n truly random bits then why not use it to generate p truly random bits in the first place, and get the pseudo-random number generator out of the picture? And the answer is: because sending p bits over the secure channel may be too expensive.

So what attacks could be mounted against this system?

The accepted answer points out that this system only defends against one attack, namely, it makes it very hard for Eve to decrypt the intercepted ciphertext. It does not provide any mechanism for Bob to verify that the ciphertext received was actually produced by Alice. If bits of that ciphertext are flipped, they'll be flipped in the plaintext too and Bob has no way of knowing that.

Another attack is: suppose n is a relatively small number, say, 32. That means there are only four billion possible values for KEY and therefore only that many pseudo-random bit sequences SEQ. Eve can obtain the ciphertext and simply try all of them until one of them decrypts it into something sensible. This implies that n had better be pretty large; large enough that this brute-force attack is infeasible. (And of course, if n has to be so large to prevent this attack that it is a significant fraction of p, then again, take the PRGN out of the picture and just generate as many truly random bits as there are bits in the plaintext.)

And yet another attack is: suppose the attacker manages to obtain the whole ciphertext -- easy -- and manages to obtain or guess k bits of the plaintext. This is not as hard as you might think; lots of messages have common patterns in them. (WWII era allied codebreakers made good progress by assuming that a significant fraction of messages would end in a greeting to the Führer; and they were right.) If k bits of the plaintext and all of the ciphertext are known then k bits of SEQ are known. Now the question is: Can the attacker make a good guess as to the value of KEY given k bits of SEQ and knowledge of the internals of the PRNG? If they can then the task of generating SEQ just got a lot easier for the attacker. The PRNG had better be carefully designed to make this kind of key recovery infeasible.

-

I also want to throw in a bit more on this - as why you would not want to do that. To use the analogy of sending secret message from a capitol to a diplomatic embassy, it is a great and secure, somewhat "foolproof" encryption method - but the practical use has some drawbacks:

• You would need as much random data (i.e. the "codebook") as you would ever want to transmit. If you sent enough messages with sufficient size, you have exhausted your random pool. You cannot re-use the same random numbers ("codes") or it would be insecure.
• You would now need a secure and reliable way to hand the codebook over. If there were any eavesdroppers, you couldn't do this. This means that you can't just email your key over to someone, you'd need to transport it in something akin to a locked attache case handcuffed to your wrist with a tamper proof (or tamper evident) seal.
• Your local embassy has the codebook. Therefore, it is possible that a spy inside the embassy could use it to forge a message to the embassy, pretending it was from the capitol. (i.e. it is a symmetric cypher, the codebook can be used two-ways).

So when your random data pool ran out, you'd need to send out a new attache, and could not use encryption until this was done.

With other methods, a public key can be sent in the clear - if an eavesdropper were to receive it, it would do them little good, and there is no "pool" of random data that would be exhausted.

As awkward and restrictive as it is however, I still believe there are HIGH SECURITY applications in which this may provide the strongest encryption.

-
Brad, that's why I mention the pseudo-random-number generator (which I should have called a deterministic f'n that generates a long unique string--the pad--based on a much shorter input key). The keys still need to be agreed upon and the "spy" can get at they key just as they could at any (non RSA\public-key) cipher. Of course, I see your point that the one-time pad would not be useful if you want to re-use the key. I just wanted to compare this simple algorithm against against other private key ciphers: AES, serpent, twofish, etc. ... –  dardawk Sep 19 at 14:41
Ah, then yes - I concur with the comments about "reinventing the stream cipher" ;-) The big keypoint (that I was going to say but thought it might be too obvious) was that the "security is only as good as the uncrackable randomness of your "codebook" data. –  Brad Sep 20 at 15:09