exaexa
commented
7 years ago I should probably fix the attacks anyway. Well, there are two:
The original timing attack
This one is common to almost all versions of McEliece; if decoding algorithm fails because it's not able to recover all errors, it usually takes a bit different time than when everything goes okay. In case of original McE this kind of failure was a bit faster because the padding etc. was not computed after a failure (it is in codecrypt), so that thing is mostly avoided.
In MDPC case, the decoder is mostly probabilistic, and instead of failing faster, it is left with trying random steps significantly longer. Implications are the same.
Best countermeasure is either to fuzz up the reply timings so that the attacker can't dig anything usuable from his measurements; or create a constant-time decoder. I'm aware of some work in that direction (by DJB and co.), result here: https://www.win.tue.nl/~tchou/qcbits/ . Haven't had enough time to look deeply into it yet.
The key-recovery
Because the probabilistic decoder fails sometimes even on a key with a sub-critical count of errors, when there's a decryption yes/no oracle, attackers are able to forge a set of keys that, upon having them "tested" by the oracle, they can use to actually reconstruct the parity check matrix and effectively the private key. Attack method presented here http://eprint.iacr.org/2016/858.pdf is not very avoidable, as it is basically a scanning through valid ciphertexts. Countermeasures include designing the key in such a way so that decryption does not fail; or fails deterministically on some randomly sampled inputs, so that the attacker cannot determine which failed attempts were caused by actual decoding, and which were intentional.
Conclusion
I supposed that the issues here don't generally affect codecrypt; even a mildly-witted user will get some doubt after clicking "decrypt" button and failing on more than 100 messages. Fixing the issues would be better though.
The constants (block sizes, error counts) used in codecrypt are taken from the original MDPC paper. With some tuning, we can make the numbers such that algorithm fails on "expected" error count only in cryptographically small number of cases, and any higher error count is always caught by CCA2.
Anyway, I'd like to know how they sample CCA2-able ciphertexts in the paper. Codecrypt uses a deterministic CRHF-based derivation of the error pattern, having an error vector with features like "only 1's with d bits in between" and "second half of error vector is zero" is equivalent to almost-preimage attack, or at least to bitcoin mining. If anyone read the paper, would you mind sharing an opinion on what are the exact requirements on the error vectors when they are gathered from the random sampling in the CCA case?
HulaHoopWhonix
ghost
Is the caveat about the crypto not being intended for online use have anything to do with this write-up? Has the author contacted you about this?
https://grocid.net/2016/04/14/a-timing-attack-on-codecrypt/