bancfc@xxxxxxxxxxxxxxx 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.
[0]: http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
[1]: http://pqcrypto.eu.org/docs/initial-recommendations.pdf
[2]:
https://lists.torproject.org/pipermail/tor-dev/2016-May/010952.html
[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,