Why do one-time pads not provide message authentication?

Question

It is often said that one-time pads do not provide message authentication. But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication? The probability of you getting a non-gibberish message is, I would have to spam you a noticeable quantity of messages to get one that decodes to something resembling what you expect to get.

Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.

Answer 1

But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?

The informal criterion of "not complete gibberish" that you are applying here has two problems:

• Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";
• Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability

This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to. One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:

• If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."

In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext. But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages. And we don't want them to be able to exploit this to modify that skeleton.

Computers are dumb

The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means. Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted. We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.

Example: EFail attack

One recent real-life example that combines these two motifs is the EFail attack on encrypted email. It exploits:

• Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;
• Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.

Answer 2

The OTP does not provide message integrity, wasn't designed too and almost certainly can't. The OTP is a model that formalizes the notion of confidentiality.

A System providing integrity should to do so for every correct instantiation of such system. It is however trivial to show correct instantiations of OTP that do not provide integrity.

A remark on your threat model. You said:

Update: I was mostly considering attacks where ciphertext is not known, but the recipient is known. In that case, to try and guess what to send them is impossible, and the message seems like it is inherently authenticated. An attacker intercepting the ciphertext could, like the answers say, alter a bit here or there, maybe it could be good to have a message authentication hash as well.

Observe that if you have such a channel so that you can send a message secretly to a remote party in a way that the adversary cannot see it, then you actually don't need encryption at all... All you need is to make sure that the probability that the adversary intercepts your messages is really small. But this is not a "real world" scenario and by real I even consider quantum computers etc...

So from now on we will assume that the attacker always sees the messages that you are sending.

Informal discussion

As repeated multiple times in the comments, the OTP breaks with respect to integrity whenever the adversary can make so good "guesses". We can formalize this later. But for now what does it mean to make a good guess? It doesn't mean to guess the message in itself, but something about the message, e.g the "structure" of the message. How and why?

Example

Suppose that an IoT devices is installed in a network to perform intrusion detection, the devices sends it's logs over the network to a central sever using OTP. Furthermore, IoT and Server use Quantum Key distribution to generate an OTP key(This construction doesn't have a strong theoretical security basis). It is not unreasonable to assume that the messages will probably have a format with some key-value fields of fixed length. Maybe the $i^{th}$ pair is the date with a format $dd-mm-yyyy$. This is where a flipping attack might occur whenever the adversary

In general for any encryption system we assume that the adversary knows the message space $M$ and making a guess can also be guessing an approximation of the distribution that the sender(Alice assigns) to the message space $Pr^A[m \in M]$.

A slightly more formal discussion

The OTP can be defined over more general things than just bits and xor. Let's look at the following definition:Given a group $(G,∗)$ the one-time pad over $G$ is defined as: on input $m \in G$, key-generation $k \xleftarrow{$} G$ encryption $c=m∗k$.

Now given $c$ and adversary easily breaks integrity by computing $c = c*\delta$. This will decrypt to $m*\delta$. Which is a valid message from the message space. Observe further that $c$ is actually not needed, any $c'$ the adversary sends will decrypt to $c'*k$.

So the conclusion here is that the OTP is never used to provide integrity. In some instantiation, it might be more resilient to trivial manipulation that the OTP can almost always be manipulated meaningfully. And as you mention at end of the update, the OTP can be modeled a a component in building a secure channel. i.e

Given a key and an authenticated channel the OTP constructs a secure channel.

Answer 3

get one that decodes to something resembling what you expect to get.

You don't always expect the exact detail though. You might transmit "Buy 1 million shares in ...", but the other end might receive "Buy 5 million shares in ..." due to malice or a noisy channel. One altered/corrupted bit might easily decode to something entirely sensible as I've shown. That depends on the mapping function in the decoding part of the cipher. $\text{Decode}(c_i, k_i)$ may easily produce convincing output with a single bit's hamming distance between any two $c_i$ characters. 1 and 5 may very well be adjacent mappings within the $\text{Decode}$ function.

It's not this is that likely though as you suggest. It's that this is statistically possible within the bounds of secure communication. It's called malleability in that the message can be 'shaped' to something else, either by accident or design. Thus some form of authentication mechanism (MAC) is warranted.

Answer 4

There are many assumptions in your question, and most of them are often not correct.

The messages cannot be intercepted.

If this is true then you simply don't need cryptography at all, your communication is already secure. You use cryptography when you're not sure that it is already secure.

The messages cannot be altered

If this is true then you don't need a MAC. However, generally, if messages can be eavesdropped then they can also be altered. This is called a man-in-the-middle attack. These kinds of attack are for instance very feasible if you connect to a public Wifi network, as there is little to no authentication of the access point.

The message content is fully secret

Generally, it is not. We often have a good idea about the structure of a message, and we can often guess where the data is.

We can generally see when a message is altered

This is often not the case. If the message is altered at a point that doesn't generate an error then it will likely be ignored and passed as regular data.

Even if we can detect it at some point, we generally would like it at an earlier stage, when receiving the message. Imagine you get a complex message that needs to be parsed after it is received received. Now the parser throws an exception somewhere deep down the tree. What did just happen? Was the message generated incorrectly, is there an error in the parser or was there some attack? It will be tricky at best to distinguish one from the other.

---

All the above points really have nothing to do with an OTP. They are equally valid for any unauthenticated cipher. The fact that OTP provides perfect confidentiality has precisely no influence whatsoever.

---

Generally we want our cryptographic schemes to detect any error in any message. In other words, the chance that a bad message gets through should be negligible. For that, you need at least 128 bits of security. It is unlikely that you can get that kind of security by just looking at the contents of the message.

---

Generic encryption schemes try to achieve security for any kind of message. So lets see what happens if we simply generate an example of a single bit message.

The contents of this message can certainly be confidential, using just one bit of key stream. However, anybody can see that flipping the bit of resulting ciphertext will result in a message with exactly the wrong content after decryption. Therefore an OTP will provide exactly zero bits of security when it comes to integrity/authenticity.

Even if you hash that single bit with SHA-512 and include the hash then an attacker can flip exactly those bits required to get a flipped bit with still a correct hash when parsed. This is why a MAC requires a key to be used.