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

[bancfc at openmailbox.org]

On 2016-05-19 15:28, isis agora lovecruft wrote:
> 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,

Thanks for explaining Isis and hats off to you, Yawning and Peter for 
leading the PQ transition.