A one-time pad is malleable* and doesn't provide ciphertext integrity guarantees. If you want to add message authentication to a protocol, you still need something more than a one-time-pad.
* EDIT: Correct verbage
EDIT 2: Why are people continuing to downvote this after it was corrected?
> A one-time pad is vulnerable to chosen-ciphertext attacks
No it isn't. A one-time pad in isolation is vulnerable to being malleable since it provides no authentication, but the data it carries is 100% unknowable.
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.
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.
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.
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.
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?
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.
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.
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.
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").
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.
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.
And that malleability can be exploited to send garbage messages in some contexts, which is vaguely classifiable as a "chosen-ciphertext attack" but I've edited my comment to be more precise in verbage.
> which is vaguely classifiable as a "chosen-ciphertext attack"
Only if we interpret the jargon at face value as a layman. But is is jargon, with a specific meaning. A chosen-ciphertext attack isn't just any attack in which you send (modified) ciphertext to your victim, it specifically refers to breaking a cipher (by e.g. deriving the key) using the information gained from getting ciphertexts of your choice decrypted. The only information you can gain this way about a one-time-pad is a random keystream that will never be used again for anything.
The important part being that what makes a one time pad secure from this attack is that it is in fact, one time. If you re-use your keystream, well, it's not a one time pad.
Any encryption scheme may have an oracle by definition of oracle. You’re (possibly intentionally) changing the situation by refusing to allow OTP to be an actual encryption scheme.
Give me a one time pad cipher text c of length n and a decryption oracle Dec(). Then the key k = Dec(0^n) and I can easily tell you that the message is c xor k.
Assuming you have the Decryption oracle is the same as assuming you have the key in your example, so you are just saying a OTP is vulnerable if you have the key. This is true for any encryption scheme that I can think of.
This is not generally true. You can easily imagine a cryptosystem where having a decryption Oracle does not give the key.
The fact that it is so easy to get the key given a decryption oracle for OTP just tells us that it’s really easy to show that it’s not CCA secure. The definition of CCA secure allows a decryption oracle with the same key as the challenge ciphertext.
Being a one-time pad makes it irrelevant if you get the key. So it’s CCA secure because you never reuse the pad. You’ve gathered no useful information, ie you’ve only gathered noise that has no use.
It is not CCA secure because an adversary with access to a decryption oracle may get the key that was used to encrypt a challenge ciphertext via the method I’ve described.
In the CCA experiment, the oracle uses the same key as the challenge ciphertext.
It isn’t secure against the attack because the oracle uses the same key.
The oracle is a tool used to formalize our definition. You’re right that the fact that OTP isn’t CCA secure doesn’t matter in practice because the key is only used for one message so such an oracle doesn’t generally exist.
"The same key" in the context of OTP means the same pad… all the key material shared between the sender and recipient. However, every encryption with that pad must use a different part of the pad or it isn't OTP at all. Not reusing bits from the key material is the defining characteristic of the One-Time Pad.
The only reasonable formulation of IND-CPA, IND-CCA1, or IND-CCA2 for OTP involves the encryption and decryption oracles using a unique subset of the pad for each plaintext. That's part of the cryptosystem definition, much like the selection of unique, random nonce values. When put in those terms, the encryption and decryption oracles can only ever reveal the parts of the pad used to encrypt the adversaries' chosen plaintext, which doesn't provide any information which could be used to decrypt any other ciphertext, so OTP easily passes all three tests.
You’re mistaken. CCA has a formal definition that may not match with your expectation, but in the definition of CCA, the same key that is used to encrypt the challenge message is used for the decryption oracle.
Is there a point to arguing whether a system is CCA secure if the 'formal definition' uses the system in an explicitly wrong way?
Especially if there is a trivial modification of the 'formal definition' that better matches the intention and allows for results that apply to reality?
Of course there is the question of whether the modification is trivial, and whether the modification changes CCA meaningfully for other systems. But argue about that, whether a definition modification changes past results using that definition. Just stating 'that is not the formal definition' if the formal definition gets criticism and an alternative is suggested, is not really good-faith engagement with criticism.
The point is that CCA is not applicable to one time pad. All you're saying is that OTP is not secure if you know the key. It doesn't matter what terms you use to describe it. It just doesn't mean anything beyond that.
I wouldn't go so far as to say that IND-CPA/CCA1/CCA2 aren't applicable. The fundamental error l33t2328 is making lies in mistaking the part of the pad used to encrypt a particular plaintext with the entire "key" which must remain constant. That makes zero sense in the context of a one-time pad, and as you said if the rules are misinterpreted that way it just makes the IND tests meaningless for OTP. Even for other algorithms it's typical to have some element which must be unique for each plaintext (e.g. a nonce or initialization vector) for the system's security properties to hold. For OTP that varying component just happens to be the specific region of the pad used for the encryption. The entire pad is the key. This perfectly satisfies the requirements of the formal definition, as the pad is shared in advance and does not vary, while the portion to be used for a given plaintext is chosen during encryption and does not need to be kept secret.
> The fundamental error l33t2328 is making lies in mistaking the part of the pad used to encrypt a particular plaintext with the entire "key" which must remain constant.
This is no error. The distinction you are making is nonsense. Indeed, given the key k and a message m, the basic correctness requirement of a crypto-system demands that dec_k(enc_k(m)) = m.
How on earth is this decryption to be done under your assumption that only some part of the pad was used?
First, to get this out of the way, there is no meaningful sense in which OTP fails any of these IND-CPA/CCA1/CCA2 games. Depending on how you formulate the preconditions, either the games are simply not applicable to OTP and the result is nonsense, as any implementation which satisfied requirements for encryption and decryption oracles which reuse the same bits of the pad for multiple plaintexts would not be OTP, or OTP passes the tests with flying colors. Personally I don't think the former is worth discussing—as it amounts to an attacker already having a full copy of the pad—so I'll be limiting my response to the version that actually makes sense.
> the basic correctness requirement of a crypto-system demands that dec_k(enc_k(m)) = m
Indeed. For OTP you have a bitstream k which is the entire pad, large enough to provide one bit of pad for every bit of plaintext you might ever want to encrypt. enc_k(m) is defined as taking the next length(m) unused bits from the pad, which I'll call k[m], and calculating the ciphertext (c) as (k[m] XOR m, i) where i is the index of k[m] within the pad. (In some systems the starting index would be implicit but then you can't lose or reorder messages, which isn't really compatible with the concept of oracles.) These bits k[m] are then effectively destroyed in the sender's copy of the pad, never to be used again. dec_k(m) is exactly the same process, including the destruction of the used bits, but using the recipient's copy of the pad.
(Yes, this means enc_k and dec_k carry some extra implicit state and are not simply functions in (k × m) → c; this is a strict requirement to count as an implementation of OTP. If you aren't doing at least this much, especially including the part about never reusing bits from the pad on either the sending or receiving side, you don't have an OTP system.)
So dec_k(enc_k(m)) = m, but k[m] is different for each m—and knowing m and enc_k(m) tells you k[m] for that message, the one supplied by the attacker, but nothing about any other message. The attacker might as well be using their own distinct pad rather than the provided encryption & decryption oracles for all the good this does them.
> The entire pad is the key.
At least we agree on something. The key for which encryption & decryption oracles must be provided is indeed the entire pad, not just the part used for one particular message.
> there is no meaningful sense in which OTP fails any of these IND-CPA/CCA1/CCA2 games
That’s factually wrong. A CCA oracle can easily determine the key.
> enc_k(m) is defined as taking the next length(m) unused bits from the pad
No, it is not. It’s defined as m \xor k.
You are describing another cipher, but not Vernan’s OTP.
> Yes, this means enc_k and dec_k carry some extra implicit state and are not simply functions in (k × m) → c
Then you aren’t describing an encryption and decryption function. Those depend only on k and m.
Someone must be able to have the algorithm and the key and decrypt any message. Your “hidden state” cannot(and indeed should not) be a part of the algorithm as it violates the principle of kerckhoff.
Stepping out of the theoretical for a moment, your proposed scheme also makes no sense in reality. How am I to know what part of the pad you’re using if I’m in a bunker picking up your encrypted signal?
Even if you make this assumption it still wouldn't be a successful attack because OTP makes no security claims if the key is re-used. If there's no security claim there's nothing to attack to begin with.
I can declare that my "brazzy attack" involves an oracle that for any given cipher text gives me the key it was encrypted with. Wow, all modern ciphers are vulnerable to it, the only thing that resists it is keeping the algorithm secret!
Just because you can think of something doesn't mean it makes sense.
I’m not sure what point you were trying to make. I think you accidentally made the opposite point. Indeed your definition would imply that all modern ciphers are not Brazzy-secure. I’m not sure why this matters to you.
No one is saying that the fact that OTP cipher is not CCA secure is practically relevant.
But the fact of the matter is that a cryptosystem being CCA secure is defined as we discussed and the OTP cipher does not meet the requirements.
I think we're largely in agreement then, but I still believe that it makes more sense to say that the definitions of OTP and CCA are incompatible and therefore it's just meaningless to apply one to the other.
re edit 2: a fair number probably loaded the page a while ago and hadn't seen the edit. e.g. I sometimes open a dozen or so tabs at once and then wander through them through the day when I feel like it.
* EDIT: Correct verbage
EDIT 2: Why are people continuing to downvote this after it was corrected?