Hacker News Reader

Comment by some_furry | Hacker News Reader

Let's assume a game where Alice and Bob are two military generals using One-Time Pads to encrypt a message and Mallory wants to confuse them.

  Alice -> Encrypt("RETREAT", Pad[128:7])

You intercept this message and you're not sure if it means "RETREAT" or "ADVANCE". But contextually, you know it's one of the two, and you want to sew confusion.

  Mallory -> XOR(Ciphertext, XOR("RETREAT", "ADVANCE")) -> Bob

And then Bob reads this message as the opposite of what Alice sent.

  Bob -> Decrypt(Cipher2, Pad[128:7])

Thus, the lack of ciphertext integrity allowed Mallory to gain an advantage in her goal as an attacker to sew confusion between two generals. If Alice advances, Bob retreats, and vice versa.

It doesn't really matter, to this security game, if you learn anything about the key from the malleability. You chose the ciphertext, and thus you succeeded in dividing their military force.

View on HN

Yes, but it also means you knew a lot about the clear text to do this.

I don't think that there is dispute that malleability is an issue in OTPs. What is also not in dispute is that the message itself is secure against decryption absent other knowledge.

The point that is made (and in other posts) is that on its own, OTP isn't enough in most situations - and I agree with that.

> The point that is made (and in other posts) is that on its own, OTP isn't enough in most situations - and I agree with that.

Yes, and that's all I'm saying here.

I deal with real-world cryptography. I'm not a theoretical or academic cryptographer. If someone deployed an OTP in a system I'm responsible for, I'd escalate until they use an AEAD instead.

If you combine that with a one-time-signature, and add the overall sha256 to the end of the message, will that be secure against such manipulation?

Something like

    Encrypt("RETREAT" + sha256("RETREAT" + SignaturePad[128:7]), KeyPad[128:7])

Hm... wouldn't the dead simple pattern of "RRRRREEEEETTTTTRRRRREEEEEAAAAATTTTT" in the message defeat the attempt to sow confusion?

To be clear-- the parties agree ahead of time that each message will consist of repeating each desired letter in the message N times (before encrypting). If there's a letter that doesn't repeat N times in the received message then the message isn't authentic.

Surely a cryptographer could figure out the math to make N large enough that the probability of defeating the authentication is practically equivalent to guessing the message itself.

This doesn't work if the attacker knows the repeating pattern is going to be used, and if they know it's going to be either "ADVANCE" or "RETREAT" then it seems likely they will also know about the repeating pattern.

They can still invert the meaning by XORing the cyphertext with XOR("RRRRREEEEETTTTTRRRRREEEEEAAAAATTTTT","AAAAADDDDDVVVVVAAAAANNNNNCCCCCEEEEE").

Thanks, I just realized that in my comment below. See additional question there...

Hm... I guess if the attacker knows N=5 they could just send truncated text.

Is there really no dead simple authentication scheme that is as easy to understand as OTP, which can be used with OTP?

Edit: clarification

Would you be a bit better off if N is to be inferred from the decrypted text, and Alice rolls a die to pick it?

I'm just surprised that there isn't some bog standard authentication puzzle piece that goes with learning OTPs.

Couldn't Alice just repeat the plaintext many times (number agreed in advance when she shared the OTP), split it into bits, label each bit with a sequence number, shuffle all the labelled bits, then encrypt?

Then Bob can decrypt, split the message into labelled bits, and sort by sequence number. If any any of the repetitions of the message differ then it was tampered with.

A variation on this would be: For each bit of the message take the next bit from the pad. If the bit is 0 then take a second bit from the pad and send it, then take a third bit, XOR it with the message, and send that. If the first bit is 1 then swap the order: take a second bit from the pad, XOR it with the message, and send that, then take a third bit from the pad and send it verbatim. The first bit is not transmitted. For decryption you do the same in reverse, checking that the verbatim pad bits match your copy of the pad.

This requires three times as much pad as regular OTP for the same plaintext, and the ciphertext is also twice as large, but it doesn't depend on any hash functions, all bits remain independent, and an attacker has no way to know which half of the ciphertext makes up the message. Any N-bit change in the ciphertext will have a ((2*N)-1)/(2*N) chance of being detected on the receiving side (50% for one bit, 75% for two bits, …).

Of course, if you are willing to trust message authentication codes something like OTP(pad1, message + MAC(pad2, message)) will be more efficient and has a higher chance of detecting tampering, especially for smaller numbers of bits.

At that point you might as well use a MAC.

You have to trust a hash function to do that, which doesn't seem likely if you require a one time pad.

Reply on news.ycombinator.com