3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You can pair a one-time-pad with a universal hashing based MAC, which is secure against computationally unbounded adversaries. $\endgroup$
    – CodesInChaos
    Commented Jan 15, 2018 at 20:33

4 Answers 4

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bipman
    Commented Jan 15, 2018 at 20:38
  • 6
    $\begingroup$ @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. $\endgroup$
    – Ella Rose
    Commented Jan 15, 2018 at 21:16
  • $\begingroup$ @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. $\endgroup$
    – Peteris
    Commented Jan 16, 2018 at 9:00
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. ;) $\endgroup$
    – e-sushi
    Commented Jan 16, 2018 at 7:13
  • $\begingroup$ 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. $\endgroup$
    – Rob
    Commented Jan 17, 2018 at 3:08
1
$\begingroup$

The examples given of the 'Heil Hitler' -ending messages and the simplistic 'yes/no' messages have no real world applications, as you might have guessed, and are given as scholarly examples to demonstrate the concept of malleability and 'attack-ability'. In addition although the xor function is the one mostly used, it isn't the only one. Anyway, again in real-world examples, the attacker will have to be truly extremely lucky to tamper with the OTP encrypted message while maintaining its logic/integrity that could in a way result in the receiver not actually doubting that tampering had occurred. In any case, that being said, combining it with MAC always provides an additional level of security.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is incorrect, real bit flip attacks have happened. Example: efail.de In that case the encrypted material was emails, and these have a predictable header. Bit flips can be used to inject scripting attacks into known portions of the header. $\endgroup$
    – Drew
    Commented Mar 14 at 23:47

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.