Greg told me that this method is insecure, but I still don't understand why.
In academic cryptography you want well-defined security against arbitrary adversaries with well-defined powers. To make these useful in the real world, we try to make the definition of "security" as strong as possible: typically you want "indistinguishability", meaning that if the attacker gives you two messages of his choosing, and you reply with the encryption of one, he cannot tell which one with probability significantly different from 1/2. Here "significantly different" roughly means "goes to zero very quickly as you increase the bit security of the cryptosystem".
Two standard sets of adversary powers are
- Chosen plaintext adversary (CPA, "semantic security", "passive attacker"): The attacker has access to all the public parameters and public keys. He can therefore encrypt whatever he likes before and after submitting his two messages for encryption.
- Chosen ciphertext adversary (CCA, "active attacker"). The attacker also has access to a decryption oracle. Here before and after submitting two messages for encryption, he can also submit arbitrary ciphertexts for decryption to see what he gets back. The only rule is, after receiving the challenge encryption, he can't submit this to the decryption oracle!
These are deliberately very general. If you are arguing security along the lines of "oh, well, as long as the user only does this, or the attacker can only do that, or..." then you've got two problems. The first is that it's probably really hard to argue security rigorously under such an ad hoc definition. The second is that the security of your system now depends on exactly the way that it's used. This means that every change to the surrounding context of your system (e.g. how is the message transmitted, which messages are legal, who has access to what keys, etc., etc.) is now potentially a security bug. Nobody can do this kind of analysis continuously so you are screwed. A classic example of this sort of problem is
the crazy mess that is TLS. That blog post also talks about encrypt-then-authenticate vs authenticate-then-encrypt, which is actually a instance of this CPA security being used where CCA security is needed.
Roughly, what CCA security means is that given a ciphertext, there is somehow a way to prove that it is a "real" ciphertext. (Not a way to prove that the ciphertext came from the right person, mind you, that is what Crowex is talking about. Just that it's not deliberately mangled in an effort to learn about its contents. As a simple example, suppose your cryptosystem was "derive an ephemeral shared secret C, then coerce the message M to a curvepoint and the encryption is CM". Believe it or not, simple multiplication like this is the basis for most CPA-secure systems --- you can see, if C is random to the attacker, then CM will be too, so the attacker sees the encryption as random data, and therefore cannot learn about the message well enough to tell one from the other with probability different from 1/2. But in the CCA game, this is easily broken. As the attacker, this is what I do: submit two messages M, M' and receive an encryption C. Submit 2C to the decryption oracle and receive a decryption P. Then P/2 was the original message.
What's interesting is that given a CPA-secure encryption system it is basically always possible to "bootstrap" this into a CCA-secure system. For example the Naor-Yung system (
gzipped postscript --- anyone have a PDF link?. Maybe try
Naor's website which has a link at "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", but this is broken for me.) works by encrypting the same message twice using different public keys, and providing a zero-knowledge proof that they are the same message. The trick is that the zero-knowledge proof requires knowledge of the shared secret (more specifically, knowledge of the random nonce used in the encryption --- it is not relevant to Naor-Yung that this randomness is used to generate an ephemeral shared secret). So when I try to do something sneaky like taking a ciphertext C and submitting 2C, I won't be able to make a new zero-knowledge proof, and the decryption oracle will simply reject the ciphertext.
This is cool: it means that CPA-secure systems are still interesting, even if their direct use is limited to pre-authenticated channels. So a good exercise is to head to
IACR's eprint archive, find some CPA-secure systems, and try to break them in the CCA game. This is almost always possible --- sometimes as easily as I described above, sometimes not.
So here's your problem: with an unauthenticated channel (like broadcasting encryptions) you need CCA security. Otherwise an attacker can submit arbitrary ciphertexts, and depending on the details of the system (remember, this dependence is deadly!), will be able to get some sort of decryption oracle. Maybe this is simply "output an error if the message is not well-formed, or its padding is not well-formed, or whatever". No matter how weak the oracle is, it's still outside of the CPA security game under which the cryptosystem was proven secure. (In fact, error messages are exactly how the original TLS timing attack I linked earlier worked!) In any case, the result is that the security of your system is basically an accident of the exact way you set it up and the exact way your users use it. So in the future, they will do something weird, and the system will be broken as a consequence.
I hope this helps clarify the original message.
