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

Hi Peter, > That's great news! Any thoughts on the license? Can you place it into > public domain? I am not 100% sure but I think it will be the same as the current NTRU implementation. > Did the attachment get lost? Sorry. Here are the data extracted from our paper. The final version will be

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

Zhenfei Zhang wrote: > Hi Peter, Hi Zhenfei, hi all, > We are working on a constant-time implementation of NTRU. We expect to > release the source code this summer. That's great news! Any thoughts on the license? Can you place it into public domain? > However,

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

Hi Peter, Thanks for such a nice overview of current discussions. Just want to give a quick update on the NTRU. > - NTRU is around for the longest time and has, even with high-security > parameters, fairly short messages. However, existing software > implementations (at least the ones in

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

ban...@openmailbox.org wrote: Hi all, > Some great developments in lattice-based crypto. DJB just released a paper > on NTRU Prime: Let me just also throw in my 2 cents: As far as I can tell, there are now 5 approaches to post-quantum key exchange that are discussed (or at least have surfaced)

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

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

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

Granted that this is an experimental implementation (as acknowleged by the Boring devs) in a very different protocol with different tradeoffs. On Thu, May 19, 2016 at 2:42 PM Yawning Angel wrote: > On Thu, 19 May 2016 17:21:47 + > Deirdre Connolly

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

ban...@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

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

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

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

Yawning Angel writes: > > Implementing the infrastructure to allow runtime selection of a PQ > handshake, and actually doing any PQ handshake are required to really > investigate these sort of issues instead of arguing over algorithms... > Right. It's probably too premature to

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

Just a a couple questions : Is SIDH costing 100 times the CPU such a big deal, assuming it's running on another thread? Can it be abused for DOS attacks for example? Is that CPU time needed for symmetric crypto? etc. If so, is it worth restricting to your guard node? Is New Hope's 3+ times

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

Yawning Angel wrote: Hi Yawning, Thanks for the more detailed description; I think I understand now what you're saying. I also agree that the cost is small (only some extra symmetric stuff happening). I don't like the use of AES-GCM as an authenticated-encryption

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

On Thu, 12 May 2016 11:58:56 +0200 Jeff Burdges wrote: > On Thu, 2016-05-12 at 05:29 +, Yawning Angel wrote: > > and move the handshake > > identifier into the encrypted envelope) so that only the recipient > > can see which algorithm we're using as well (So: Bad guys must

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

On Thu, 2016-05-12 at 05:29 +, Yawning Angel wrote: > and move the handshake > identifier into the encrypted envelope) so that only the recipient > can see which algorithm we're using as well (So: Bad guys must have > a quantum computer and calculate `z` to figure out which post quantum >

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

eik...@sigaint.org transcribed 0.6K bytes: > isis wrote: > > eik...@sigaint.org transcribed 1.1K bytes: > >> Typos: > > > > Thanks! Fixed: > > > > https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope=5c115905 > > You skipped 2: > > - public keys already being in included

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

Tim Wilson-Brown - teor transcribed 3.7K bytes: > > > On 7 May 2016, at 05:17, isis wrote: > > > > ... > > > > Let `ID` be a router's identity key taken from the router microdescriptor. > > In the case for relays possessing Ed25519 identity keys (c.f. Tor proposal > >

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

eik...@sigaint.org transcribed 1.1K bytes: > Typos: Thanks! Fixed: https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope=5c115905 -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35

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

Yawning Angel transcribed 4.3K bytes: > On Sat, 7 May 2016 19:41:59 + (UTC) lukep wrote: > > Thanks isis for this, it looks really good, I look forward to seeing a > > similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !) > > When there is a sufficiently fast SIDH

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

Jeff Burdges transcribed 2.6K bytes: > On Sat, 2016-05-07 at 19:41 +, lukep wrote: > > It's hard to guarantee that any fixed, finite amount of SHAKE > > output will be sufficient for any rejection sampling method > > like gen_a. > > Isn't some small multiple usually enough? I think 1024 is

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

lukep transcribed 3.1K bytes: > I look forward to seeing a similar protocol for SIDH! (and > X25519+NEWHOPE+SIDH !) What benefit would SIDH be providing in an X25519+NewHope+SIDH construction which is not already part of the X25519+NewHope construction? (Other than putting us pretty solidly

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

Jeff Burdges transcribed 3.1K bytes: > On Fri, 2016-05-06 at 19:17 +, isis wrote: > > > --- Description of the Newhope internal functions --- > > > > gen_a(SEED seed) receives as input a 32-byte (public) seed. It expands > > this seed through SHAKE-128 from the FIPS202 standard. The

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

On Sun, 08 May 2016 02:00:51 +0200 Jeff Burdges wrote: > On Sat, 2016-05-07 at 22:01 +, Yawning Angel wrote: > > how an adversary will be limited to just this information, and not > > things that enable a strong attack on it's own like packet timing > > escapes me > >

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

On Sat, 07 May 2016 23:46:28 +0200 Jeff Burdges wrote: > On Sat, 2016-05-07 at 13:14 -0700, Watson Ladd wrote: > > I'm not sure I understand the concern here. An attacker sees that we > > got unlucky: that doesn't help them with recovering SEED under mild > > assumptions we

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

On Sat, 7 May 2016 19:41:59 + (UTC) lukep wrote: > Thanks isis for this, it looks really good, I look forward to seeing a > similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !) When there is a sufficiently fast SIDH implementation, it might be worth considering (MS

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

On Sat, 2016-05-07 at 13:14 -0700, Watson Ladd wrote: > I'm not sure I understand the concern here. An attacker sees that we > got unlucky: that doesn't help them with recovering SEED under mild > assumptions we need anyway about SHAKE indistinguishability. We're assuming the adversary controls a

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

On Sat, May 7, 2016 at 12:41 PM, lukep wrote: > Jeff Burdges writes: > >> >> On Fri, 2016-05-06 at 19:17 +, isis wrote: >> >> > --- Description of the Newhope internal functions --- >> > >> > gen_a(SEED seed) receives as input a 32-byte (public) seed. It

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

Jeff Burdges writes: > > On Fri, 2016-05-06 at 19:17 +, isis wrote: > > > --- Description of the Newhope internal functions --- > > > > gen_a(SEED seed) receives as input a 32-byte (public) seed. It expands > > this seed through SHAKE-128 from the FIPS202 standard. The

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

> On 7 May 2016, at 05:17, isis wrote: > > ... > > Let `ID` be a router's identity key taken from the router microdescriptor. > In the case for relays possessing Ed25519 identity keys (c.f. Tor proposal > #220), this is a 32-byte string representing the public Ed25519

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

Just a brief aside about post-quantum handshake approaches that seemingly do not work. I suppose Tor folk remember the article Using Sphinx to Improve Onion Routing Circuit Construction by Aniket Kate and Ian Goldberg. As key sizes are a main obstacle to a post-quantum key exchange, one

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

On Fri, 2016-05-06 at 19:17 +, isis wrote: > --- Description of the Newhope internal functions --- > > gen_a(SEED seed) receives as input a 32-byte (public) seed. It expands > this seed through SHAKE-128 from the FIPS202 standard. The output of > SHAKE-128 > is considered a

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

On Fri, 6 May 2016 19:17:11 + isis wrote: > [XXX We think we want to omit the final hashing in the production > of NTOR_KEY here, and instead put all the inputs through SHAKE-256. > --isis, peter] > > [XXX We probably want to remove ID and B from the input to the >

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

Hello, Peter (in CC) and I have recently composed a draft proposal for a new Tor handshake. It's a hybrid handshake combining Tor's current X25519-based NTor handshake with the NewHope lattice-based key exchange, in order to protect the secrecy of Tor connections today from an attacker with a