One Time Pads and "Bit Flip" Attacks

Question

One Time Pads and Vulnerability to "Bit-Flip" Attacks:

I've seen it in this group, and apparently there are a (small) number of voices on the 'net opining that those relying on OTP are essentially "amateurs" (or otherwise oblivious) to the possibility of "bit-flip" being a fatal flaw in OTP and they should NOT be used. Given my own professional experience using One Time Pads, I found these claims astonishing and was interested in learning if there was chink in the OTP armor rendering it an insecure system to protect data secrecy.

"Bit Flip" in the context of these claims being that the OTP message can be tampered with in transit- that there's no validation the recipient has received exactly the message that was originally sent. But even tampering doesn't imply that the attacker can read the text they tampered with sans a key. So as far as I can see at this point, the secrets still remain protected.

Further, in order to tamper with the contents of the OTP encrypted message would imply that the attacker knew exactly "when", "where", "how" and most importantly "who" the message was being transmitted to. Those decrying One Time Pads as an insecure, flawed system are thin on details how an attacker would obtain this key these key pieces of data.

Such a claim is bold and it contravenes accepted wisdom that OTP encrypted messages are secure & unbreakable- if the system is operated correctly of course. Am I missing something here?

Answer 1

accepted wisdom that OTP encrypted messages are secure & unbreakable

OTP encrypted messages are secure & unbreakable assuming the pad is secret, uniformly random, and not reused... and the message does not otherwise leak! The last point is where the "Bit Flip" attack comes to play.

Imagine the message is conventionally a digit send in ASCII, and parsed as such by the receiver after decryption; and that the context tells the adversary that a particular message is 1 or 2, that is the bitstring 00110001 or 00110010. With the OTP (or a stream cipher), the adversary can flip the 5^th bit of ciphertext, and know that changes the plaintext to 00111001 or 00111010, that is the character 9 or :. Now if the adversary can sense whether the receiving system accepts the result as a digit, or rejects it, the confidentiality is lost!

More generally, when users of cryptography need encryption for confidentialitty, they tend to additionally need assurance of integrity and origin. The OTP only gives confidentiality, and as illustrated not unconditionally in some quite practical cases.

However, assurance of integrity can be obtained with an information-theoretic substitude to a MAC, or universal hash, such as Carter-Wegman; and when the OTP is shared among only two parties that gives assurance of origin. That consumes some of the OTP, but manageably so. And it can help mitigate the above attack (an altered message will be rejected before it is tested that it is decimal).

There remains two reasons making the OTP impractical:

• It is easy for an adversary to mount a denial of service attack that de-synchronize sender and receiver (that can be solved to a degree, but is not trivial)
• The random pad must be sent in advance by secure means, and kept secret on both sides.

Answer 2

There are different objectives when it comes to security. One objective is to make messages confidential. An OTP provides this in an information-theoretical secure way. Of course, the premise of OTP is that the key stream is fully random, which is hard to prove conclusively.

Other security goals could be maintaining message integrity: making sure that the message isn't tampered with or otherwise altered and message authenticity: making sure that the message that is received is the message that the sender wanted to send to the receiver. These goals are not covered by an OTP, as a message can be tampered with during transit or when in storage.

If an adversary can only listen and can not interfere with the message then we talk about an eavesdropper. As no interference is possible, it is generally not needed to secure the message to achieve integrity / authenticity. In that case an OTP is sufficient to protect the message, as it provides the confidentiality required. Trying to decipher a confidential message without changing the transport of the message itself or performing any actions involving the participants is called a passive attack.

However, for most systems, we have to assume that active attacks - such as man-in-the-middle attacks - are possible. In that case the attacker may try to tamper the message in transit, or send messages of his own to the receiver. If any invalid message is accepted then integrity and authenticity of the messages is obviously not achieved. One method of changing the messages is a bit flip attack, but it would also be possible to change the size of the message or tamper it in any other way. The bitflip attack is however powerful because it allows an attacker to flip any specific bit of the plaintext.

---

I've seen it in this group, and apparently there are a (small) number of voices on the 'net opining that those relying on OTP are essentially "amateurs" (or otherwise oblivious) to the possibility of "bit-flip" being a fatal flaw in OTP and they should NOT be used. I found these claims astonishing and was interested in learning more.

I don't see that in the articles you posted to. Yes, the articles pointed out the flaws of schemes that uses OTP's and the drawbacks of OTP's, but I don't see any name calling (calling somebody an "amateur" would be a strange way of name calling, a good amateur can be better than many professionals out there, if we take the terms by their literal meaning).

"Bit Flip" in the context of these claims being that the OTP message can be tampered with in transit- that there's no validation the recipient has received exactly the message that was originally sent. But even tampering doesn't imply that the attacker can read the text they tampered with sans a key. So as far as I can see at this point, the secrets still remain protected.

Correct. OTP's provide perfect confidentiality (well, except for the message length or timing, never forget that), so no attack can change that. Note that the system may still leak information about a tampered message though. For instance, if computation based on the received message may trigger specific errors, and those errors can be detected by an adversary, then plaintext oracle attacks may leak information about the contents of the message (any action that depends on the plaintext message may do that, of course).

Further, in order to tamper with the contents of the OTP encrypted message would imply that the attacker knew exactly "when", "where", "how" and most importantly "who" the message was being transmitted to. Those decrying One Time Pads as an insecure, flawed system are thin on details how an attacker would obtain this key these key pieces of data.

Of course they are; they must be thin on details as the methods of altering a ciphertext message in transit depend fully on the system. Unfortunately, there are many ways that active attacks are possible, and you ignore them at your peril.

Such a claim is bold and it contravenes accepted wisdom that OTP encrypted messages are secure & unbreakable- if the system is operated correctly of course. Am I missing something here?

I think you are naive if you think that it is easy to detect tampered messages without leaking data. Similarly, I think you incorrectly assume that active attacks are commonly not possible. These are serious issues and it is unwise to ignore them in the best of cases.

---

In the end, key management with one-time-pads is awkward at best and outright impractical and dangerous at worst. We've got secure schemes such as authenticated cipher modes (ChaCha20/Poly1305 and AES/GCM, for instance) that provide symmetric encryption that include small key sizes as well as integrity / authenticity of the message. These are more secure to use for most systems, certainly compared to schemes that just use an OTP (rather than an OTP combined with a MAC authentication tag, for instance).

Sure, it may be possible that some schemes are better off using an OTP. Those are however so uncommon that OTP should be considered a red flag when it comes to cryptography. It commonly means that the designer of the scheme doesn't know about or severely underestimates the limitations and drawbacks of OTP's.

The fact is that an OTP protects you against breaking of other symmetric cipher algorithms / implementations. That's currently not much of an issue for most ciphers. If you can make a conscious, well founded decision that an OTP is required to protect you against such attacks then go for it. But please be aware of the listed limitations and drawbacks of OTPs.

Answer 3

One way to address this question is to give an example of a real-world attack that relies on being able to modify a ciphertext in a way that alters the resulting plaintext in a predictable, attacker-controllable manner. And there's a very notable example from last year: 2018's EFAIL attack on encrypted email clients:

The EFAIL attacks exploit vulnerabilities in the OpenPGP and S/MIME standards to reveal the plaintext of encrypted emails. In a nutshell, EFAIL abuses active content of HTML emails, for example externally loaded images or styles, to exfiltrate plaintext through requested URLs. To create these exfiltration channels, the attacker first needs access to the encrypted emails, for example, by eavesdropping on network traffic, compromising email accounts, email servers, backup systems or client computers. The emails could even have been collected years ago.

The attacker changes an encrypted email in a particular way and sends this changed encrypted email to the victim. The victim's email client decrypts the email and loads any external content, thus exfiltrating the plaintext to the attacker.

And further down, describing one of the variants of the attack, note the two sentences I've boldfaced:

Second, we describe the novel CBC/CFB gadget attacks which abuse vulnerabilities in the specification of OpenPGP and S/MIME to exfiltrate the plaintext. The diagram below describes the idea of CBC gadgets in S/MIME. Because of the specifics of the CBC mode of operation, an attacker can precisely modify plaintext blocks if she knows the plaintext. S/MIME encrypted emails usually start with "Content-type: multipart/signed" so the attacker knows at least one full block of plaintext as shown in (a). She can then form a canonical plaintext block whose content is all zeros as shown in (b). We call the block pair X and C0 a CBC gadget. In step (c), she then repeatedly appends CBC gadgets to inject an image tag into the encrypted plaintext. This creates a single encrypted body part that exfiltrates its own plaintext when the user opens the attacker email.

This is a little bit dense, but the idea behind the "exfiltration" is tricking the email client into decrypting a modified message that will have the original plaintext inside a URL inside an HTML img tag, so that the email client will request that URL when the user opens the email. The attacker points that URL at their own servers, and monitors their access logs to learn the plaintexts.

---

I'll close with some informal remarks that might help you:

• Most classical cryptography existed in a world where there were no computers. Humans decrypted messages and interpreted their content using common sense.
• Modern cryptography exists in a world where computers are ubiquitous. Messages are decrypted by computers that blindly perform automated actions on the decrypted content.

Therefore, while classical cryptography often cared only about whether encryption provided confidentiality for messages, modern cryptography cares just as much about providing message authenticity—it's not enough that a passive eavesdropper be unable to learn anything new about the plaintext from its ciphertext, we also need to prevent an active attacker who has partial knowledge about the plaintext (e.g., the email format headers) from leveraging that to modify ciphertexts in ways that produce controllable changes in plaintext that the recipient (a computer, not a person!) will admit as authentic.

So the modern standard that encryption algorithms are expected to live up to is authenticated encryption. One-time pads guarantee perfect confidentiality, but don't guarantee message authenticity at all.

Answer 4

"Bit Flip" in the context of these claims being that the OTP message can be tampered with in transit- that there's no validation the recipient has received exactly the message that was originally sent.

The pillars of information security are confidentiality, integrity, and availability. (integrity and authenticity are sometimes used interchangeably).

Encryption is a tool for providing confidentiality. It does not by itself provide integrity.

Integrity is provided by a MAC, digital signature, or authenticated encryption scheme.

An adversaries ability to modify ciphertexts is a problem that is inherent to encryption schemes in general and is not specific to OTPs.

The question "Why should I use Authenticated Encryption instead of just encryption" covers this pretty thoroughly and fgrieu's answer provides another example.

Further, in order to tamper with the contents of the OTP encrypted message would imply that the attacker knew exactly "when", "where", "how" and most importantly "who" the message was being transmitted to.

OTPs offer perfect secrecy, which means that given a ciphertext an adversary cannot learn anything more about the plaintext than they already knew. This last part is key: A OTP does not mean that an adversary knows nothing about the plaintext already, it means that they cannot use a ciphertext to learn more than they already knew.

The security models for confidentiality consider the following scenarios:

• Ciphertext only attack
• Known plaintext attack
• Chosen plaintext attack
  • e.g. the adversary has access to an encryption oracle
• Chosen ciphertext attack
  • e.g. the adversary has access to a decryption oracle

The ciphertext only attack model cannot in general be relied upon. Typically at least a known-plaintext attack model needs to be considered.

The reason for this is because messages are not (generally) strings of uniformly random bits. This means that the plaintext consists of less than 1 bit of entropy (uncertainty) per bit of message. This means that an adversary knows or can guess some of the contents of the message.

This is actually not as unreasonable as it may seem at first: Most real-world communications possess structure that is probably known to the adversary. For example, an HTTP request has certain fields that are always and/or commonly present, and the values of those fields are typically structured as well.

OTP encrypted messages are secure & unbreakable- if the system is operated correctly of course.

This is a big "if". There are a lot of prerequisites, and it is easy to fail at them even when the stakes are very high.

The main problem that modern cryptographic techniques solve is not symmetric encryption to secure messages (which is relatively easy), but key management.

Key management for OTPs is maximumly difficult. For the modern world (e,g. the internet), it is prohibitively so.

This is why the apparently easy, fast, and obvious solution of using OTPs is not supported by modern protocols or standardized for use (unlike algorithms such as AES or Salsa20, which do have official standards and a specification).

The reason why people advocate against OTPs is not because they are insecure, but because they are practically unusable.