4 ms·

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

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.

RandomLensman 5y ago
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.
- some_furry 5y ago
  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.
  - RandomLensman 5y ago
    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.
    - some_furry 5y ago
      > 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.
  - mrob 5y ago
    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.
    - ttybird2 5y ago
      At that point you might as well use a MAC.
      - Dylan16807 5y ago
        You have to trust a hash function to do that, which doesn't seem likely if you require a one time pad.
    - nybble41 5y ago
      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.
l33t2328 5y ago
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.
- deleted 5y ago
  [deleted]
anamax 5y ago
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.
- Animats 5y ago
  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.
  - _fizz_buzz_ 5y ago
    > 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.
    - Animats 5y ago
      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/declassified-documents/friedman-documents/patent-equipment/FOLDER_425/41774259081336.pdf https://www.nsa.gov/portals/75/documents/news-features/decla... [2] https://cryptomuseum.com/manuf/mils/index.htm https://cryptomuseum.com/manuf/mils/index.htm
nybble41 5y ago
> 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'.

RandomLensman 5y ago

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.

some_furry 5y ago
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.
- RandomLensman 5y ago
  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.
  - some_furry 5y ago
    > 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.
- mrob 5y ago
  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.
  - ttybird2 5y ago
    At that point you might as well use a MAC.
    - Dylan16807 5y ago
      You have to trust a hash function to do that, which doesn't seem likely if you require a one time pad.
  - nybble41 5y ago
    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.

l33t2328 5y ago

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.

deleted 5y ago
[deleted]

anamax 5y ago

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.

Animats 5y ago
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.
- _fizz_buzz_ 5y ago
  > 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.
  - Animats 5y ago
    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/declassified-documents/friedman-documents/patent-equipment/FOLDER_425/41774259081336.pdf https://www.nsa.gov/portals/75/documents/news-features/decla... [2] https://cryptomuseum.com/manuf/mils/index.htm https://cryptomuseum.com/manuf/mils/index.htm

nybble41 5y ago

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