On 2016-05-19 15:28, isis agora lovecruft wrote:
bancfc@openmailbox.org transcribed 7.3K bytes:
This brings up another point that digresses from the discussion:
Dan and Tanja support more conservative systems like McEliece because it survived decades of attacks. In the event that cryptanalysis eliminates Lattice crypto, McEliece will remain the only viable and well studied alternative.
First, it's not viable (for Tor's use case). I'll show that in a second. Second, there are other bases for contruction of post-quantum secure cryptosystems — not just some lattice problems or problems from coding theory.
How prohibitive are McEliece key sizes that they can never make it into Tor?
Extremely prohibitive. McEliece (using the original scheme proposed by McEliece in 1978 [0] but with the recommended post-quantum secure parameters of n=6960 k=5413 t=119) keys are 1 MB in size. [1]
Plugging this number into my previous email [2] in this thread:
- average microdescriptor size would be ~1048992 bytes (252161%
larger!)
- the network would use 5043 Gb/s for directory fetches (this is
roughly 33 times the current total estimated capacity of the network)
Result: no more Tor Network.
Can the size problem be balanced against longer re-keying times for PFS - say once every 6 hours or more instead of every connection (there are probably many other changes needed to accomodate it).
No.
Further, there are known attacks on McEliece resulting from ciphertext malleability, i.e. adding codewords to a valid ciphertext yields another valid ciphertext. [3] This results in a trivial CCA2 attack where the adversary can add a second message m' to a ciphertext c with c' = c ⊕ m'Gpub, where Gpub is dot product of matrices G, the generating set of vectors, and P, the permutation matrix. One consequence of this ciphertext malleability is that an attacker may use the relation between two different messages encrypted to the same McEliece key to recover error bits, leading to the attacker being able to recover the plaintext. [4] Were we to use Shoup's KEM+DEM approach for transforming a public-key encryption scheme into a mechanism for deriving a shared secret (as is done in the NTRU Prime paper), this plaintext recovery attack would result in the attacker learning the shared secret, meaning that all authentication and secrecy in the handshake are lost completely. There are possible workarounds to the CCA2 attacks (e.g. Kobara-Imai Gamma Conversion) which generally increase both the implementational complexity of the scheme and increase the number of bytes required to be sent in each direction (by introducing redundancy into the codewords and uniformly-disbursed randomness to ciphertexts), however these are inelegant, kludgey fixes for a system not worth saving because ITS KEYS TAKE UP AN ENTIRE MEGABYTE.
They've worked on making tradeoffs of longer decryption times to get smaller keys in their McBits implementation [1] but they still are no where near Lattice ones (McEliece has very fast encoding/decoding so it works out).
Yes, I'm aware. Also, Peter (in CC and working with me on this proposal) is the other author of the McBits paper. If Peter thought McBits was more suitable than NewHope for a Tor handshake, then I hope he'd have mentioned that by now. :)
Also, for a minimum security of 128 bits, the smallest McBits keysize available is 65 KB; that's still not doable for Tor. (In fact, that would result in 320 Gb/s being used for directory fetches — more than double the current estimated total bandwidth capacity of the network — so thus again there would be no Tor Network.)
With the averge webpage being 2 MBs in size, larger keys may not be that bad?
Hopefully, everyone is now convinced with the arguments above that, yes, larger keys are that bad.
[3]: Overbeck, R., Sendrier, N. (2009). "Code-Based Cryptography". in Berstein, D.J., Buchmann, J., Dahmen, E. (Eds.), Post-Quantum Cryptography (pp. 134-136). Berlin: Springer Verlag. https://www.springer.com/us/book/9783540887010 [4]: http://link.springer.com/content/pdf/10.1007%2FBFb0052237.pdf
Best Regards,
Thanks for explaining Isis and hats off to you, Yawning and Peter for leading the PQ transition.