10 ms·
"If they do not, cryptographers have shown, then secure cryptography is impossible." It seems like they're using "secure cryptography" kind of narrowly, as AFA
by frankus 5y ago
"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.
- some_furry 5y agoA 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?
- Rexxar 5y ago> Why are people continuing to downvote this after it was corrected? Because they don't refresh comments every 30s and they see your comment from one hour ago.
- orlp 5y ago> 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.
- some_furry 5y agoAnd 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.
- orlp 5y ago> 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.
- l33t2328 5y agoRecall that in the CCA experiment, the decryption oracle uses the same key as the message in your challenge ciphertext.
- powersnail 5y agoIs it really an OTP if you have an oracle that uses the same key? By definition of OTP, such an oracle should not exist, right?
- l33t2328 5y agoIt’s an oracle, we allow it to exist for the experiment.
- powersnail 5y agoThen it’s not an oracle of OTP, but an oracle of a single-key XOR. 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.
- l33t2328 5y agoAny 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. 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/ https://wiki.soimort.org/crypto/one-time-pad/ Regardless, this is a silly discussion with nothing to be gained by me.
- powersnail 5y agoWell, my bad to have wasted your time with a silly discussion, then. I find it neither silly nor gain-less. I'm sorry that you feel differently.
- Ar-Curunir 5y agoThat'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 agoI 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 agoLet'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 agoYes, 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.
- l33t2328 5y agoIt is vulnerable to chosen cipher text attacks. 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.
- kickling 5y agoAssuming 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.
- l33t2328 5y agoThis 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.
- Robotbeat 5y agoBeing 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.
- l33t2328 5y agoIt 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.
- Robotbeat 5y agoBut the OTP is still secure against that attack because the “key” is never reused. It is literally just noise, no useful information whatsoever.
- deleted 5y ago[deleted]
- Groxx 5y agore 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.
- hedora 5y agoI think they're assuming space efficiency. The article dances around the issue a lot, but doesn't actually say that. After all, you can convert any function to a time bounded one by writing down a table with the inputs and outputs.
- Ar-Curunir 5y agoIt’s hardly narrow if it includes 99% of crypto in deployment.
- _fizz_buzz_ 5y agoThey are talking about asymmetric encryption, which is what you always need when communicated with someone else. Symmetric encryptions like AES also work without one-way functions.
- deleted 5y ago[deleted]
- thiagoharry 5y agoNo, the security of AES assumes that AES is an one-way function. Otherwise, if AES is not one-way, one could decrypt it easily reversing the function. Symmetric encryption usually assumes the existence of one-way functions, but there are indeed some rare exceptions. The one-time pad is a construction with unconditional security and is secure even if one-way functions do not exist. Of course, it requires the assumption that each person will not reuse the key more than once. And without one-way functions, you also would never be able to exchange the keys securely using any computer network.
- _fizz_buzz_ 5y agoBut you can reverse AES! You obviously need the secret key, but it's trivial to reverse the steps of encryption (it's actually a bit tricky to get all the steps correctly, but you can easily google how to do it, tons of example impelentations and lecture notes online). There are a bunch of online tools that demonstrate it such as: https://www.devglan.com/online-tools/aes-encryption-decryption https://www.devglan.com/online-tools/aes-encryption-decrypti...
- rocqua 5y agoAes is a one-way function if you consider the key part of the arguments to the function.
- Aardwolf 5y agoOne requirement for one way functions is to not easily find a preimage. With AES output you could decrypt it with a wrong key, get wrong plaintext, but they're still a valid input combination giving this same AES output
- q-big 5y ago> 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://doi.org/10.1007/BF02620136 > https://link.springer.com/article/10.1007/BF02620136 https://link.springer.com/article/10.1007/BF02620136 (website of paper) > https://link.springer.com/content/pdf/10.1007/BF02620136.pdf https://link.springer.com/content/pdf/10.1007/BF02620136.pdf (PDF)
- kadoban 5y agoIsn't leaking the length pretty harmless? You can make that leak arbitrarily small by adding randomized amounts of padding with various distributions as well, right?
- q-big 5y ago> Isn't leaking the length pretty harmless? 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.
- ganzuul 5y agoToomanysecrets.
- 5y ago