3 ms·

Someone should hold a backdoored blockcipher or hash function competition. The structure would be that submitters are intended to submit proposals which are st

by nullc 8y ago

Someone should hold a backdoored blockcipher or hash function competition. The structure would be that submitters are intended to submit proposals which are structurally like those of normal cipher competitions, e.g. make the same security arguments, etc. To focus efforts most usefully, they could be required to not just lie about the properties they claim (not a restriction on real attackers, but we already know that if people make claims that people accept and no one checks that this can allow backdoors-- and due to the risk of being caught real attackers would probably avoid outright lies). But every entry is required to contain an exploitable algorithmic backdoor, not just a certificational weakness. The process continues like a normal cipher competition, and the winner is selected based on no one being able to break their scheme. Then the backdoors are disclosed. (Perhaps some escrow process could be used to make sure that they're really back doored, or a ZKP to that proves they could break a nothing-up-my-sleeve instance could be required along with the submission) I think from such a process we could learn a lot about what submission norms are actually useful for protecting against cleverly constructed back doors, and something about the submission norms that we're missing. Alternatively, it might be useful for normal competitions to allow secretly backdoored contributions. E.g. every submitter submits a commitment at the beginning, and then at the end everyone reveals their commitment (to avoid the case of a bad submission being revealed as "white hat" selectively only if its caught). ... but I fear that the result of such efforts would do more to erode our trust in the process (because it would fail to find the backdoors) than it would educate us about making things more secure. It would, however, make cryptanalysis of proposals more attractive, because it would increase confidence that there are discoverable weaknesses in at least some of the proposals.

baby 8y ago
https://underhandedcrypto.com/ https://underhandedcrypto.com/
lucb1e 8y ago
> some escrow process could be used to make sure that they're really back doored Or the judges ask the teams to provide a working implementation, encrypt some text with each implementation (a random sentence, perhaps), and return the ciphertexts. Each team can then prove it is backdoored by providing (a significant part of) the plaintext.
- nullc 8y ago
  A more realistic test would require, e.g. encrypting a large number of potentially somewhat structured inputs... and then decoding some of them. Weaknesses like that can be translated to real exploits in usage. Unfortunately, doing that would leak information the structure of the backdoor based on which texts could be decoded ... so you'd want to isolate that knowledge.
- bcaa7f3a8bbc 8y ago
  > Each team can then prove it is backdoored by providing (a significant part of) the plaintext. Some backdoors are asymmetric backdoor, so the original designers can decrypt anything at will. But some others only hide a trick that reduces the computation complexity to, say, 2^80. Unless you are a nation-state, you cannot use the backdoor. And the other type of backdoor only increases the susceptibility to implementation vulnerabilities (cache-timing attacks, invalid curve attacks), mathematically speaking they're still secure, but too difficult for most people to implement it perfectly. A escrow process would be better.
  - throwawaymath 8y ago
    > But some others only hide a trick that reduces the computation complexity to, say, 2^80. Unless you are a nation-state, you cannot use the backdoor. That's not an issue - you just publish the backdoor. You don't need to demonstrate the complexity reduction, you just need to prove it exists.
  - lucb1e 8y ago
    If it can be 2^80, then with smaller parameters it can almost certainly be less as well. If it's so close to the real strength (e.g. 96 bits effective strength with 128 bits claimed), it's not really a practical backdoor anyway. That said, I see your point. I'm a fan of autograders and automation, but this can totally be solved by just submitting the solution, to be checked by people not in the jury.

by nullc 8y ago

baby 8y ago

https://underhandedcrypto.com/ https://underhandedcrypto.com/

lucb1e 8y ago

> some escrow process could be used to make sure that they're really back doored Or the judges ask the teams to provide a working implementation, encrypt some text with each implementation (a random sentence, perhaps), and return the ciphertexts. Each team can then prove it is backdoored by providing (a significant part of) the plaintext.

nullc 8y ago
A more realistic test would require, e.g. encrypting a large number of potentially somewhat structured inputs... and then decoding some of them. Weaknesses like that can be translated to real exploits in usage. Unfortunately, doing that would leak information the structure of the backdoor based on which texts could be decoded ... so you'd want to isolate that knowledge.
bcaa7f3a8bbc 8y ago
> Each team can then prove it is backdoored by providing (a significant part of) the plaintext. Some backdoors are asymmetric backdoor, so the original designers can decrypt anything at will. But some others only hide a trick that reduces the computation complexity to, say, 2^80. Unless you are a nation-state, you cannot use the backdoor. And the other type of backdoor only increases the susceptibility to implementation vulnerabilities (cache-timing attacks, invalid curve attacks), mathematically speaking they're still secure, but too difficult for most people to implement it perfectly. A escrow process would be better.
- throwawaymath 8y ago
  > But some others only hide a trick that reduces the computation complexity to, say, 2^80. Unless you are a nation-state, you cannot use the backdoor. That's not an issue - you just publish the backdoor. You don't need to demonstrate the complexity reduction, you just need to prove it exists.
- lucb1e 8y ago
  If it can be 2^80, then with smaller parameters it can almost certainly be less as well. If it's so close to the real strength (e.g. 96 bits effective strength with 128 bits claimed), it's not really a practical backdoor anyway. That said, I see your point. I'm a fan of autograders and automation, but this can totally be solved by just submitting the solution, to be checked by people not in the jury.