# Non-malleability of One Time Pad Encryption

Can anyone explain to me what the following means in relation to one time pad security? It's from the book 'Serious Cryptography: A Practical Introduction' and my logic knowledge seems to have lost me here so I'm struggling :-

Given a ciphertext $C_1 = E(K, P_1)$, it should be impossible to create another ciphertext, $C_2$, whose corresponding plaintext, $P_2$, is related to $P_1$ in a meaningful way (for example, to create a $P_2$ that is equal to $P_1 \oplus 1$ or to $P_1 \oplus X$ for some known value $X$). Surprisingly, the one-time pad is malleable: given a ciphertext $C_1 = P_1 ⊕ K$, you can define $C_2 = C_1 \oplus 1$, which is a valid ciphertext of $P_2 = P_1 ⊕ 1$ under the same key $K$. Oops, so much for our perfect cipher.

• You can pair a one-time-pad with a universal hashing based MAC, which is secure against computationally unbounded adversaries. Jan 15 '18 at 20:33

## The Problem

The One-Time Pad offers perfect secrecy. However, it does not protect the integrity or authenticity of the message - An adversary can flip bits of the ciphertext, and the receiver will have no way of detecting the manipulation.

Consider the case where a single bit is sent encrypted with a One-Time Pad, used to indicate a "yes/no" value as to whether or not Alice wants to have lunch with Bob. If Mallory intercepts the message $C$ and computes $C \oplus 1$ and then sends that value to Bob instead, Bob will receive the opposite of Alice's intended message - and he will have no way of knowing that it has been tampered with.

## The solution

Use a MAC to ensure the integrity and authenticity of the message.

• But a general message would be much longer than 1 bit and hence once the un-encryption had been done, the message would obviously have some errors i.e. Mallory would have no idea what the bits being flipped would mean in the original message. Jan 15 '18 at 20:38
• @Bipman Exclusive-or is a bitwise operation, and only operates on 1 bit at a time. If you're using exclusive-or as the combining function then no error propagation occurs. Hoping that Mallory doesn't know which bits to flip is not cryptography. Utilizing a MAC to ensure the integrity of your message provides a quantitative guarantee of the messages integrity/authenticity, regardless of what Mallory knows about it. Jan 15 '18 at 21:16
• @Bipman in many real-world scenarios Mallory could know (or guess) the structure of the messages being sent even if she can't read the particular single message. For example, if financial messages were being transferred and Mallory could guess that bytes 32-33 contain the amount of the payment, Mallory might flip the most significant bit (with the expectation that it's exceedingly likely to be 0, as most payments are small) to increase the payment amount in a MITM attack. Jan 16 '18 at 9:00

The one-time pad has the property that (as long as one key is only used for one encryption) the ciphertext contains (information theoretically) no information about the plaintext.

However, this is something which does not exclude any form of malleability. Non-malleability is a property which is often required in protocol design, because ciphertext malleability may allow non-intuitive attacks (e.g., Bleichenbacher's padding oracle attack on RSA). So essentially this means that the one-time pad can not be used in protocols which require non-malleability of the ciphertexts.

A quite realistic example: Presume that you are listening to German messages during WWII, and intercept messages that you think are for a one-time-pad. You know that every message ends in "Heil Hitler". So, the last 11 characters can be simply presumed. So, you badMsg=xor("Heil Hitler", "Retreat now"). Then when a message comes by, xor the last 11 characters of this message with badMsg. xor(badMsg,realMsg) = (hh xor rn xor hh xor otp). The hh messages cancel, and you are left with (rn xor otp). So, when the one time pad is decrypted, the last bit reads "Retreat now".

You can do this kind of edit to messages without decrypting them. Using traffic analysis, you can find opportune times to make such replacements.

• Yeah, but since it doesn't end with "Heil…" anymore (remember you wrote every message ends in), the modified message can clearly be identified as non authenticated — which kinda spoils the effectiveness of the attack in your theoretical scenario. ;) Jan 16 '18 at 7:13
• in the Turing biography, it was these sorts of patterns in the encrypted data that gave them the foothold to start breaking it. standard headers and standard footers. anywhere you can make an educated guess about what is in the plaintext, you could replace that part if it is an unauthenticated one time pad.
– Rob
Jan 17 '18 at 3:08