[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[isis agora lovecruft]

bancfc at 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.


[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,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160519/34f87086/attachment.sig>