22
$\begingroup$

A (synchronous) stream cipher is an algorithm which maps some fixed-length key to an arbitrary-length key-stream (i.e. a sequence of bits): $C : \{0,1\}^k \to \{0,1\}^{\infty}$.

This key-stream is then XOR-ed with the plain text stream, giving the ciphertext stream. For decrypting, the same key-stream (generated from the key at the receiver side) will be XOR-ed with the ciphertext stream, giving again the key stream.

A One-time pad is an algorithm which takes a key of large size (at least message size), and XORs its start with the plaintext to get the ciphertext. For decryption, we XOR the start of the key with the ciphertext to get back the plaintext.

These look quite similar – could one say that a stream-cipher is a (special way to create/use a) one-time pad, or that the one-time pad is a kind of stream cipher?

Are there any important differences between these two classes of algorithms?

$\endgroup$

7 Answers 7

17
$\begingroup$

There is no universally accepted definition of the expression "stream cipher"; but the one I most often encounter is the following: a stream cipher is a symmetric encryption algorithm which accepts as inputs arbitrary sequences of bits (or bytes) such that:

  • the length of the output is equal to the length of the input (no padding);
  • for any $n$ (possibly any $n$ which is a multiple of 8 if we restrict ourself to bytes), the first $n$ output bits depend only on the key and the first $n$ input bits, regardless of the value of the subsequent input bits.

In that sense, the One-Time Pad is a stream cipher. A block cipher used in CTR mode or CFB mode is also a stream cipher. Note that the latter is not of the kind "XOR with a stream generated from the key independently of the input data". The Wikipedia page you link to talks about "synchronous stream ciphers" and "self-synchronzing stream ciphers".

However, the ultimate security of the One-Time Pad comes from the key size: it is unbreakable because it assumes that the key is as long as the message and was generated by an unpredictable mechanism. If you generate the pad with a more conventional stream cipher, working over a small fixed-size key, then it is no longer a One-Time Pad, just a "regular" stream cipher. The expression "One-Time Pad" refers to, exclusively, the mythical scheme which uses truly random long keys. So while One-Time Pad is a stream ciphers, stream ciphers are not One-Time Pads.

$\endgroup$
8
  • 1
    $\begingroup$ Also note that a computationally unbounded adversary could break a stream cipher (having enough known plaintext) but not a one-time pad. $\endgroup$ Sep 27, 2011 at 19:32
  • 1
    $\begingroup$ Since the one-time-pad was actually used, it is not mythical. For example, the original Moscow–Washington hotline starting in 1967 used a one-time pad. $\endgroup$
    – David Cary
    Oct 17, 2011 at 12:11
  • $\begingroup$ @David: I have no detail on how the pads were generated. The "red phone" had the operational constraints of a one-time pad (namely requiring weekly distribution of large keys on tapes) but unless the pads were generated with a 100% physical RNG, it was not a "true" one-time pad. $\endgroup$ Oct 17, 2011 at 12:50
  • 1
    $\begingroup$ The one-time pad and Venona project articles say that the USSR and a few other organizations heavily used physical pads of random-looking letters called one-time pads. I think it's pretty likely that practically all of those pads were, in fact, generated with a 100% physical RNG, although I don't really have any evidence one way or another. I suspect that we may never know exactly how those pads were generated. $\endgroup$
    – David Cary
    Jul 30, 2012 at 17:25
  • 2
    $\begingroup$ And let's not forget that Numbers Stations also send OTP encrypted messages too. Venona was an effort to decode Cuban Numbers Stations which turned out be reusing pads. That is the only reason they got cracked. That and some agents did not dispose of used pads correctly as well. $\endgroup$
    – WAR10CK
    Feb 24, 2016 at 15:26
8
$\begingroup$

One important difference between the one-time pad and a stream cipher is the proof of security of the one-time pad. Shannon proved that the one-time pad provides perfect secrecy. He also provided another proof that is interesting to this dicussion. His proof was that no cipher can provide perfect secrecy unless the key is at least a long as the message. Therefore, we know that no stream cipher can provide perfect secrecy unless it meets that requirement. But, just because it meets that requirement does not mean that it automatically provides perfect secrecy.

Now, as to whether or not they are the same, the answer is no. The one-time pad uses a fixed length key (where the length is at least a long as the message among other requirements) and the xor operation, period (i.e., there is no key expanion/stream generation).

$\endgroup$
4
$\begingroup$

Mathematically speaking. The entropy of a stream cipher is upper-bounded by the key size.

The entropy of a one time pad, on the other hand is upper-bounded by the plaintext size.

For true one-time pads and good stream ciphers, this bound is tight.

$\endgroup$
1
  • $\begingroup$ How is the term "entropy" defined for a cipher (i.e. an algorithm)? (I only know it as a measure of randomness for data, apart from the termodynamic meaning.) $\endgroup$ Jul 6, 2013 at 21:06
3
$\begingroup$

Quoting Cryptography and Network Security (William Stallings, Section 7.4) and other sources (e.g., https://www.fourmilab.ch/hotbits/)

the stream cipher is similar to the one-time pad but exact difference is that

one-time pad uses a genuine random number stream, whereas a stream cipher uses a pseudorandom number stream

pseudorandom numbers calculated by a computer through a deterministic process, cannot, by definition, be random. Given knowledge of the algorithm used to create the numbers and its internal state, you can predict all the numbers returned by subsequent calls to the algorithm, whereas with genuinely random numbers, knowledge of one number or an arbitrarily long sequence of numbers is of no use whatsoever in predicting the next number to be generated.

$\endgroup$
2
  • $\begingroup$ This appears to be copied word-for-word from Cryptography and Network Security (William Stallings, Section 7.4) and other sources (e.g., fourmilab.ch/hotbits), without attribution. Plagiarism is not cool. $\endgroup$
    – D.W.
    May 21, 2017 at 16:37
  • $\begingroup$ @D.W. I've send an according system email message related to the plagiarism problem, and added origin of quote via edit. $\endgroup$
    – e-sushi
    May 21, 2017 at 16:58
0
$\begingroup$

More importantly a stream cipher can only produce a single plaintext regardless of what number of different keystreams you use. So even if you implemented a stream cipher machine with a true RNG and a non-stop stream of bits being fed into it, a brute force attack will still be possible because you just keep trying until you get something that makes sense.

A One-Time Pad can produce any plaintext of the same size as the ciphertext depending on what different keystreams you use. Meaning you can keep trying but get multiple things that make sense.

So unless you have the exact pad used to decode the message, you will never know which of the possible plaintexts you will stumble upon is the correct one or even if you have found the correct one yet.

That is perfect secrecy. When you can never even tell if you already cracked the message or not.

$\endgroup$
3
  • $\begingroup$ "a stream cipher can only produce a single plaintext", "a brute force attack will still be possible because you just keep trying until you get something that makes sense." Just No. Most of stream ciphers are implemented from symmetric crypto with CTR mode or hash-functions. And you will certainly get readable messages from a brute force attack, but you won't be able to know which one is the right one. $\endgroup$
    – Biv
    Feb 24, 2016 at 15:28
  • $\begingroup$ So you are saying if I actually do create a machine using RC4 or AES-CTR and have a TRNG continually feed it a constant steady stream of random bits, it will meet the perfect secrecy requirement for a OTP? Provided that the stream of bits is purged after every message? $\endgroup$
    – WAR10CK
    Feb 24, 2016 at 17:54
  • $\begingroup$ See : crypto.stackexchange.com/questions/33100 I will probably get down voted, but this is better in order to get an answer that might be even better than mine. :) $\endgroup$
    – Biv
    Feb 24, 2016 at 18:47
0
$\begingroup$

Thomas Pornin's last paragraph is right on, but this concept is still so frequently misunderstood that I wanted to add my 2 cents.

From a layman's perspective, If you really had something that implemented a one-time-pad, what would it look like? It would necessarily have to involve a physical machine that generates a truly random key stream. That machine would not take as input any passwords, keys, or seeds -- instead it would generate truly random bits using properties of physics assuming physics is correct in the existence of true randomness. Note that because these bits are truly randomly generated, they cannot be derived again, which implies that the machine would also have to output those key stream bits so you can physically deliver them to the intended recipient, allowing him to decrypt the ciphertext. By the way, when I say "physically deliver", that means getting on plane or in a car, going to your destination, and handing over the bits to the recipient. Why not use public key exchange instead? Well, you could, but that comes at the cost of losing perfect secrecy, so doing so would defeat the entire purpose of using a one-time-pad in the first place.

At this point, you may be thinking this is crazy, and if so, congratulations: now you understand why it is a theoretical construct only, and unlikely to be realised in practice. Instead, what we use today is cryptography that depends upon complexity theory, which is practical.

A stream cipher, from a layman's perspective is an attempt at a practical construct that "feels like" a one-time-pad, except lacking in the perfect secrecy property. It does not need a physical machine to realise it. Instead of true randomness, it takes input a password, key, or seed, and expands that to a long string of bits, which are derived from that input. Those same bits can be derived over and over again by using the same password/key/seed, so in order for the recipient to decrypt, they only need to get that input. And because it does not have the perfect secrecy property and instead only depends upon complexity theory, you are losing nothing when you exchange that key using public key cryptography.

The take-away: just about everything you will ever see in practice that "feels like" a one-time-pad is not really a one-time-pad. It is a stream cipher. People should not label an arbitrary stream cipher as a one-time-pad because they are entirely missing the point. One-time-pads are theoretical concepts, stream ciphers are practical imitations but lacking in the security properties that make one-time-pads what they are.

$\endgroup$
2
  • 1
    $\begingroup$ Actually, the one-time pad is quite usable in practice if you can manage to deliver the key ahead-of-time. And it was used in history before the development of modern cryptography, e.g. for secure communications between Moscow and Washington during the cold war. $\endgroup$ Jun 6, 2016 at 13:02
  • $\begingroup$ @PaŭloEbermann, agree with your claims, but also worth mentioning that mistakes were made: keys were re-used, resulting in no longer being secure. It is not difficult to break cipher texts when this happens. $\endgroup$ Jun 6, 2016 at 19:44
0
$\begingroup$

The most important difference is in their security level. OTP has a perfect secrecy but stream ciphers have computational secrecy. The other difference is about their Use in the real world. Using stream ciphers are possible to use in our real world because of their own structure and key length but about OTP cipher, producing a One Time Pad and use this pad for only one time, is so difficult (for many cases impossible) and having a pad that the size of that is larger or the same length of plaintext, causes using this cipher impractical in the real world. We can say in Other words, stream ciphers are a weak model of OTP that made OTP practical in the real world.

$\endgroup$
3
  • $\begingroup$ There is no bound for message length in the real world. Any length is possible. $\endgroup$ Aug 18, 2018 at 7:35
  • $\begingroup$ So if my plaintexts were Tweet sized, do you think that a OTP might be practical in the real world? Considering that a 2GB £3 flash drive would hold enough key material for 10 million Tweets? $\endgroup$
    – Paul Uszak
    Aug 18, 2018 at 9:49
  • 1
    $\begingroup$ The case that OTP can be practical that you and the partner, have shared the same copy of the Pad before starting any communication and never use this Pad for enciphering a message the second time. In the example of the navy, before navy going to Pacific ocean, you gave 2 Gb pad to him and then every time he wants to send a secret message, uses a part of this Pad and when the Pad finished, he could not send any secret message. and Think about how to keep this long Pad safe and Secret??? $\endgroup$ Aug 18, 2018 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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