On 2016-05-16 18:53, isis agora lovecruft wrote:
Hello,
I am similarly excited to see a more comprehensive write up on the NTRU Prime idea from Dan's blog post several years ago on the idea for a subfield-logarithm attack on ideal-lattice-based cryptography. [0] The idea to remove some of the ideal structure from the lattice, while still aiming to keep a similarly high, estimated minimum, post-quantum security strength as Newhope (~2^128 bits post-quantum security and ~2^215 classical for NTRU Prime, versus ~2^206 bits post-quantum and ~2^229 classical for Newhope) and speed efficiencies competitive with NewHope, [1] by altering the original NTRU parameters is very exciting, and I'm looking forward to more research w.r.t. to the ideas of the original blog post (particularly the exploitation of the ideal structure). Additionally, the Toom6 decomposition of the "medium-sized" 768-degree polynomial in NTRU Prime in order to apply Karatsuba is quite elegant. Also, I'm glad to see that my earlier idea [2] to apply a stable sorting network in order to generate valid polynomial coefficients in constant-time is also suggested within the NTRU Prime paper.
However, from the original NTRU Prime blog post, Dan mentioned towards the end: "I don't recommend actually using NTRU Prime unless and until it survives years of serious cryptanalytic attention, including quantitative evaluation of specific parameter choices." Léo Ducas, one of the NewHope authors, has responded to the NTRU Prime paper with a casual cryptanalysis of its security claims, [3] mentioning that "A quick counter-analysis suggests the security of the proposal is overestimated by about 75 bits" bringing NTRU Prime down to ~2^140 classical security.
As you say, I think the security reduction is a bit steep but not catastrophic. However when I saw the NTRU Prime blog post before I interpreted to mean "its very likely that the powerful attack against the Smart–Vercauteren system can be extended against Lattice-based cryptosystems in general, that would completely break them". [0] 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. How prohibitive are McEliece key sizes that they can never make it into Tor? 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). 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). With the averge webpage being 2 MBs in size, larger keys may not be that bad? Another interesting strategy for performance/efficiency is public key slicing and communicating them parallel. [2]
Current estimates on a hybrid BKZ+sieving attack combined with Dan's subfield-logarithm attack, *if* it proves successful someday (which it's uncertain yet if it will be), would (being quite generous towards the attacker) roughly halve the pre-quantum security bits for n=1024 (since the embedded subfield tricks are probably not viable), bringing NewHope down to 103/114 bits. For the case of the hybrid handshake in this proposal, it still doesn't matter, because the attacker would still also need to break X25519, which still keeps its 2^128 bits of security. (Not to mention that 103-bits post-quantum security is not terrible, considering that the attacker still needs to do 2^103 computations for each and every Tor handshake she wants to break because keys are not reused.)
Please feel free to correct me if I've misunderstood something. IANAC and all that.
Further, there are other problems in the NTRU Prime paper:
- Defining PFS as "the server erases its key every 60 seconds" seems arbitrary and a bit strange. It also makes the claims hard to
analyse in comparison with the NTRU literature (where, as far as I know, it's never stated whether or not keys may be reused, and what downsides might come with that) as well as with NewHope (where it's explicitly stated that keys should not be reused).
- In Fig. 1.2, the number of bytes sent by a NewHope client is 1792,
not 2048. (To be fair, it was 2048 bytes in an earlier version.)
- The bandwidth estimates for NTRU Prime do not take into account
that, due to providing a key-encapsulation mechanism rather than a key exchange, the client must already know the server's long-term public encryption key, in order that the client may encrypt its public key to the server in the first round of the handshake.
Further, and more specifically in the context of Tor handshakes,this requires that Tor either add a second round to the handshake (which we currently have no mechanism, nor proposed mechanism, for), or else that we add the server's NTRU Prime key to the server's (micro)descriptor, increasing descriptor size by 1232 bytes per relay. For the case of adding these keys to microdescriptors, where the average microdescriptor size is currently 416 bytes [4] and ~1 Gb/s is spent on requests to the directories for descriptors, [5] increasing the average microdescriptor size to 1648 bytes would roughly quadruple the amount of network traffic used by directories to respond to fetches (and then double that number again because additional bandwidth is used through the client's guard relay, since most directory fetches are tunneled). This means that any relay providing < ~1.142 Mb/s bandwidth would be using up more network bandwidth to tell everything else in the network about its existence and keys than the relay itself actually provides. This means that 3840 out of the current 7100 become a burden on the network. This might be doable, [6] but I just wanted to point out how much it matters for us to not need to add giant keys to descriptors.
[6]: As an aside, I'd be super happy to kick the crap relays out of the network:
https://lists.torproject.org/pipermail/tor-dev/2014-September/007558.html
Best Regards,
[0] https://blog.cr.yp.to/20140213-ideal.html
[1] https://binary.cr.yp.to/mcbits-20130616.pdf
[2] https://cr.yp.to/talks/2016.02.24/slides-djb-20160224-a4.pdf