"If they do not, cryptographers have shown, then secure cryptography is impossible."
It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function.
It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function.
The security of OTP is much more restricted than most cryptography books admit.
OTP's security can be proved in the following cases:
* the set of secrets (plaintexts) is finite,
* the set of secrets (plaintexts) is the uncountable sets of streams, say, N -> {0,1}.
What one is interested in for cryptography is if the set of secrets is a countable domain, say the a set of strings (e.g. {0,1}^*).
Bad news:
"[N]o perfect private-key encryption schemes, over the set of all strings, exist. Stated informally, this means that there is no way to perfectly encrypt all strings without revealing information about their length."
This quote is taken from the abstract of
Chor, B., Kushilevitz, E. Secret sharing over infinite domains. J. Cryptology 6, 87–95 (1993). https://doi.org/10.1007/BF02620136
> https://link.springer.com/article/10.1007/BF02620136 (website of paper)
> https://link.springer.com/content/pdf/10.1007/BF02620136.pdf (PDF)
Whether this is harmless or not is up to a debate. But it is a clear violation of the "information-theoretic security" property that (nearly) every textbook about cryptography mentions or proves for OTP.
Just to be clear: these proofs are correct, they just do not work when OTP is applied to a countable set of secrets - which is actually the situation that "everybody" is interested in.
Most systems have a finite limit to the sizes of the messages they can handle. (If nothing else there are practical limits to both the maximum transfer rate and the operators' patience.) It's inefficient, but you can pad all messages to that length regardless of the size of the plaintext.
Let's say that you have a P2P application for sharing MP3s. There are many millions of MP3s, but if an attacker sees a download of a particular size, then they have a pretty good idea of which MP3 has been downloaded.
After all, you can convert any function to a time bounded one by writing down a table with the inputs and outputs.
There are a bunch of online tools that demonstrate it such as: https://www.devglan.com/online-tools/aes-encryption-decrypti...
I guess it's a one-way function given only the key as input with a fixed ciphertext.
Incidentally if you use AES in a AED mode (like AES gcm) then it would be a one-way function but that is more about the MAC.
* EDIT: Correct verbage
EDIT 2: Why are people continuing to downvote this after it was corrected?
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.
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.
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.
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.
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.
[1] https://www.nsa.gov/portals/75/documents/news-features/decla...
And this translates to any real world scenario too.
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.
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.
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.
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.
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.
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.
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'.
Alice -> Encrypt("RETREAT", Pad[128:7])
Mallory -> XOR(Ciphertext, XOR("RETREAT", "ADVANCE")) -> Bob
Bob -> Decrypt(Cipher2, Pad[128:7])
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.
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.
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.
Something like
Encrypt("RETREAT" + sha256("RETREAT" + SignaturePad[128:7]), KeyPad[128:7])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.
They can still invert the meaning by XORing the cyphertext with XOR("RRRRREEEEETTTTTRRRRREEEEEAAAAATTTTT","AAAAADDDDDVVVVVAAAAANNNNNCCCCCEEEEE").
Is there really no dead simple authentication scheme that is as easy to understand as OTP, which can be used with OTP?
Edit: clarification
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.
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.
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.
If an encryption scheme cannot have an oracle by definition, then it automatically passes all tests which requires the attacker to access an oracle.
Just like my wooden pencil is not vulnerable to stack overflow attacks.
Here is a blog post that summarizes some facts about Vernan’s OTP as it is defined in cryptography: https://wiki.soimort.org/crypto/one-time-pad/
Regardless, this is a silly discussion with nothing to be gained by me.
Although if you were previously unfamiliar with the definitions at play I apologize for calling an informative discussion gain-less.
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.
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.
In the CCA experiment, the oracle uses the same key as the challenge ciphertext.
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 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.
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.
It may be secure under whatever alternative notions you’re proposing, but they’re not standard.
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?
The entire pad is the key.
> 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.
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?
In the CCA experiment, an attacker is given access to a decryption oracle that has used the same key as the challenge message.
You can make an oracle for whatever you want. That’s why it’s an oracle.
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.
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.
> Why are people continuing to downvote this after it was corrected?