Hacker News Reader

Comment by Ar-Curunir | Hacker News Reader

That's not true. OTPs are vulnerable to adaptive chosen-ciphertext attacks, and don't satisfy IND-CCA2. This means the malleability allows learning the contents of the ciphertext.

Recall that IND-CCA2 says "given encryption and decryption oracles, can the adversary figure out the contents of a challenge ciphertext".

In the OTP case, the adversary proceeds as follows. Upon receiving the challenge ciphertext c = b xor r, where r is a random bit, it computes c' = 1 xor c = (1 xor b) xor r. It then asks for a decryption b' of c'. If b' = 1, then the adversary knows that 1 = 1 xor b => b = 0. If b' = 0, then adversary knows that 0 = 1 xor b => b = 1. So it learns the value of b without breaking the security of the OTP.

This assumes that the same random bit r is used to encrypt c' and c, but there's no way for the challenger to force different bits.

View on HN

Yes, OTPs are vulnerable if you do the one thing that you're not supposed to do with a OTP, namely reuse the bits.

The question for OTPs is whether there is an encryption or decryption oracle for a given OTP, not whether OTPs are vulnerable to such oracles.

OTPs are vulnerable if you do the one thing that you're not supposed to do with a OTP, namely reuse the bits.

YES. "One time" means "ONE TIME". Use once and destroy. The one time pad must be random, generated by a true random process. Not pseudorandom. Not generated by an algorithm. Not generated from a shorter key. Not reused. Not generated by humans hammering on typewriters (see Venona).

One time keys are used for some crucial point to point links. Embassy to foreign ministry, higher military headquarters to high command, or spy to HQ.

> One time keys are used for some crucial point to point links. Embassy to foreign ministry, higher military headquarters to high command, or spy to HQ.

I am very skeptical this actually used in practice anywhere. The one-time pad is prone to side-channel attacks, since sharing the secret key(s) is such a nightmare. Putting people on planes flying around the globe with bags full of keys or having long lists of keys lying around is a security nightmare. Using an asymmetric encryption scheme is in practice a lot safer.

Declassified NSA documents describe some of the systems.[1] Early systems used paper tapes for the key. One of the features was a tape slitter, so the tape could only be used one time before it was cut in half. Systems with floppy disks have been advertised. Mils Electronik sold one time key systems from the 1950s until 2017.[2] Early systems used paper tape, later systems were electronic and stored the keying material on PCMCIA cards.

[1] https://www.nsa.gov/portals/75/documents/news-features/decla...

[2] https://cryptomuseum.com/manuf/mils/index.htm

The point is that with OTP in the IND-CCA2 game you can force the challenger to reuse keys

And this translates to any real world scenario too.

If your scenario involves reusing keys then what you are breaking is not a one-time pad.

You're showing that if you implement something vaguely similar to OTP, but lacking the one element that makes OTP secure, it fails the IND-CCA2 game. Which is really pretty obvious when you think about it since OTP minus the critical "one time" element is just repeated XOR with a fixed key, which is barely stronger than ROT-13.

I understand "the point" - the problem is that said "point" isn't gospel/unquestionable.

Forcing a challenger to reuse keys is not possible in every real-world scenario. Or rather, there are real-world scenarios where keys aren't/can't be reused. An evaluation criteria that assumes/requires otherwise is broken.

If we're going to allow any game, then every encryption system is broken in my game, which requires that the keys and method be made available to the challenger.

I guess what I’m trying to say is that the length issues with OTP mean that it can’t be used in any scenario that requires even a weak form of non-malleability. Maybe you could try to do something with universal hashes, but it’s unclear.

You only end up with length issues if you don't use a big enough pad.

Just use a one-time pad that is uncountably infinite in length and require messages to be at most countably infinite in length. Sure you burn infinite bits on each message, but you'll never run out or reuse bits in the pad.

How do you get both sides to have the same infinite random pad?

I thought the whole problem with one time pads was that they had to be distributed to the other side physically and thus were always finite.

Sarcasm...

> How do you get both sides to have the same infinite random pad?

With Quantum Key Distribution both sides have access to identical streams of random bits not available to anyone else.

Without invoking quantum mechanics, you can just treat the portion of the pad you have on hand as a prefix of an infinitely long pad which is being delivered incrementally. If you run out of pad bits you just pause and wait for someone to hand-deliver a new set of identical storage devices to both parties with the next segment of the pad. This is the same principle behind treating physical computers as "Turing complete" when a Turing machine is technically defined to include an infinitely-long tape—you can always extend the system with more storage as needed.

Malleable or not is a function property that doesn't make sense for OTPs. The problem is that while a OTP's outputs are determined by its inputs, a OTP's inputs are always different.

That said, a one time pads are non-malleable if you don't reuse the bits (and the bits are truly random). If you do reuse the bits, it's not a one time pad.

That said, there are no length issues with a One Time Pad.

Or rather, the length issue with one-time-pads is that you can't reuse pad bits, not just within a given message but across all messages that ever use that pad, hence the name ONE TIME Pad.

One time pads are necessarily as large as the data to be encrypted. (You might be able to get away with some fraction of the total number of "to encrypt" bits, but you can't reuse them.) Schemes which reuse "encryption bits" do not have that limit and are much smaller.

One issue wrt malleability is whether/how one can recognize that a cyphertext or a plaintext is "valid".

If you just xor with a OTP (which means that every cryptotext is valid) and every plaintext is valid, the receiver can't look at the cyphertext or the plaintext and recognize whether a MITM modified the message.

However, the same is true of any crypto system where every cryptotext and plaintext is valid.

However, if there's some way to recognize/distinguish valid plaintext, OTPs are non-malleable.

> It then asks for a decryption b' of c'.

If you can do that, why not just ask this "oracle" for a decryption b of c, i.e. to decrypt the original ciphertext? Either way you're basically asking for a copy of the pad since you can trivially derive that from any plaintext/ciphertext pair. The idea that anyone would just give you the decryption of an arbitrary message of your choosing using their supposedly secure one-time pad is a bit bizarre. You've already broken the security rules of the OTP well before you get to the point of calculating b from b'.

I think that is a bit of a stretch, as an OTP isn't maybe a "scheme" in the sense of IND-CCA2 and the attacker cannot force an encryption to happen by design.

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.

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.

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.

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.

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.

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.

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.

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...

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])

It’s not even IND-CCA1 secure. You only need one access to the decryption oracle to determine the key before the challenge ciphertext. Just encrypt all 0 bits.

Reply on news.ycombinator.com