[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 quantum computer in the future. I have not given the proposal a number. It is available in my `drafts/newhope` branch of my torspec repository: https://gitweb.torproject.org/user/isis/torspec.git/tree/proposals/XXX-newhope-hybrid-handshake.txt?h=draft/newhope For purposes of facilitating discussion, it is also included here inline. Review and comments are very appreciated. __ Filename: XXX-newhope-hybrid-handshake.txt Title: Post-Quantum Secure Hybrid Handshake Based on NewHope Author: Isis Lovecruft, Peter Schwabe Created: 16 Apr 2016 Updated: 4 May 2016 Status: Draft Depends: prop#220 prop#249 prop#264 §0. Introduction NewHope is a post-quantum-secure lattice-based key-exchange protocol based on the ring-learning-with-errors (Ring-LWE) problem. We propose a hybrid handshake for Tor, based on a combination of Tor's current NTor handshake and a shared key derived through a NewHope ephemeral key exchange. For further details on the NewHope key exchange, the reader is referred to "Post-quantum key exchange - a new hope" by Alkim, Ducas, Pöppelmann, and Schwabe [0][1]. For the purposes of brevity, we consider that NTor is currently the only handshake protocol in Tor; the older TAP protocol is ignored completely, due to the fact that it is currently deprecated and nearly entirely unused. §1. Motivation An attacker currently monitoring and storing circuit-layer NTor handshakes who later has the ability to run Shor's algorithm on a quantum computer will be able to break Tor's current handshake protocol and decrypt previous communications. It is unclear if and when such attackers equipped with large quantum computers will exist, but various estimates by researchers in quantum physics and quantum engineering give estimates of only 1 to 2 decades. Clearly, the security requirements of many Tor users include secrecy of their messages beyond this time span, which means that Tor needs to update the key exchange to protect against such attackers as soon as possible. §2. Design An initiator and responder, in parallel, conduct two handshakes: - An X25519 key exchange, as described in the description of the NTor handshake in Tor proposal #216. - A NewHope key exchange. The shared keys derived from these two handshakes are then concatenated and used as input to the SHAKE-256 extendable output function (XOF), as decribed in FIPS-PUB-202 [2], in order to produce a shared key of the desired length. The testvectors in §C assume that this key has a length of 32 bytes, but the use of a XOF allows arbitrary lengths to easily support future updates of the symmetric primitives using the key. See also §3.3.1. §3. Specification §3.1. Notation Let `a || b` be the concatenation of a with b. Let `a^b` denote the exponentiation of a to the bth power. Let `a == b` denote the equality of a with b, and vice versa. Let `a := b` be the assignment of the value of b to the variable a. Let `H(x)` be 32-bytes of output of the SHAKE-256 XOF (as described in FIPS-PUB-202) applied to message x. Let X25519 refer to the curve25519-based key agreement protocol described in RFC7748 §6.1. [3] Let `EXP(a, b) == X25519(., b, a)` with `g == 9`. Let X25519_KEYGEN() do the appropriate manipulations when generating the secret key (clearing the low bits, twidding the high bits). [XXX match RFC7748 notation more. --isis] Let `X25519_KEYID(B) == B` where B is a valid X25519 public key. When representing an element of the Curve25519 subgroup as a byte string, use the standard (32-byte, little-endian, x-coordinate-only) representation for Curve25519 points. 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 identity key. For backwards and forwards compatibility with routers which do not possess Ed25519 identity keys, this is a 32-byte string created via the output of H(ID). We refer to the router as the handshake "responder", and the client (which may be an OR or an OP) as the "initiator". ID_LENGTH [32 bytes] H_LENGTH [32 bytes] G_LENGTH [32 bytes] PROTOID :="pqtor-x25519-newhope-shake256-1" T_MAC:=PROTOID || ":mac" T_KEY:=PROTOID || ":key_extract" T_VERIFY :=PROTOID || ":verify" (X25519_SK, X25519_PK) := X25519_KEYGEN() §3.2. Protocol |
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Fri, 6 May 2016 19:17:11 + isis wrote: > Both parties check that none of the EXP() operations produced the > point at infinity. [NOTE: This is an adequate replacement for > checking Y for group membership, if the group is Curve25519.] > > [XXX: This doesn't sound exactly right. You need the scalar > tweaking of X25519 for this to work and also, the point at infinity > is obviously an element of the group --isis, peter] Maybe reword this to specify that EXP() MUST include the check for all zero output as specified in RFC 7748. It's what our current ntor implementation does here. Regards, -- Yawning Angel pgplgD63yqxD3.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 > shared key material, since they serve for authentication but, as > pre-established "prologue" material to the handshake, they should not > be used in attempts to strengthen the cryptographic suitability of > the shared key. Also, their inclusion is implicit in the DH > exponentiations. I should probably ask Ian about the reasoning for > the original design choice. --isis] Oh I missed this. B at a minimum needs to be part of `auth_input`, though probably does not need to be part of `secret_input`. Per RFC 7748: Designers using these curves should be aware that for each public key, there are several publicly computable public keys that are equivalent to it, i.e., they produce the same shared secrets. Thus using a public key as an identifier and knowledge of a shared secret as proof of ownership (without including the public keys in the key derivation) might lead to subtle vulnerabilities. Regards, -- Yawning Angel pgpwL77iPpQGl.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 sequence of 16-bit little-endian integers. This sequence is > used to initialize the coefficients of the returned polynomial from the > least > significant (coefficient of X^0) to the most significant (coefficient of > X^1023) coefficient. For each of the 16-bit integers first eliminate the > highest two bits (to make it a 14-bit integer) and then use it as the next > coefficient if it is smaller than q=12289. > Note that the amount of output required from SHAKE to initialize all 1024 > coefficients of the polynomial varies depending on the input seed. > Note further that this function does not process any secret data and thus > does > not need any timing-attack protection. Aren't the seed and polynomial a actually secret for negotiation with any node after your guard? An adversary who can do a timing attack on a user's tor process would gain some deanonymizing information from knowing which a elements get skipped. I suppose this adversary has already nailed the user via correlation attack, but maybe worth rewording at least. And maybe an adversary could employ different attack infrastructure if they can learn some skipped elements of a. Best, Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 might explore using a Sphinx-like key mutation trick to save
bandwidth.
I doubt SIDH could support anything like the key mutation trick in
Sphinx because the public key is much too far removed from the private
key.
There are key mutation tricks for Ring-LWE key exchanges though. As an
example, the article Lattice Based Mix Network for Location Privacy in
Mobile System by Kunwar Singh, Pandu Rangan, and A. K. Banerjee
describes a primitive similar to universal reencryption.
It's likely that key mutation requires fixing the polynomial a in
advance. If a must change, then maybe it could be seeded by Tor's
collaborative random number generator, so that's actually okay.
Now, a Sphinx-like route building packet could consist of :
(1) a polynomial u_i = s_i a + e_i,
along with an onion encrypted packet that gives each server
(3) maybe their reconciliation data r_i, and
(3) a transformation x_i : u_i -> u_{i+1} = s_{i+1} a + e_{i+1},
where i is the node's index along the path.
Any proposal for this transformation x_i needs a proof of security.
About the best you're going to do here is reducing its security to
existing Ring-LWE assumptions. If say x_i means add s' a + e' so that
s_{i+1} = s_i + s' and e_{i+1} = e_i + e', then you're depending upon
the Ring-LWE assumptions to know that s' a + e' looks like a random
polynomial.
As a result, your hybrid protocol is unlikely to provably offer stronger
_anonymity_ properties than a pure Ring-LWE key exchange, even if its
_cryptography_ is as strong as the stronger of Ring-LWE and ECDH.
I could say more about why say the choice of s' and e' might leak
information about s_i and e_i, but I wanted to keep this brief. And the
essence of the observation is that any sort of the Sphinx-like key
mutation trick requires assumptions not required in a group.
I found this an interesting apparent limit on making hybrids more
efficient than what Isis and Peter have proposed.
Best,
Jeff
signature.asc
Description: This is a digitally signed message part
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 identity key. > For backwards and forwards compatibility with routers which do not possess > Ed25519 identity keys, this is a 32-byte string created via the output of > H(ID). I don't understand why we do this backwards and forwards compatibility for ID, when the proposal only works for relays with an ed25519 key in their descriptor. I'm sure I'm missing something basic - I'm still learning how to read crypto papers and specifications. > ... > The function CVPD4 does the following: > > CVPD4(y0,y1,y2,y3): > v00 = round(y0/2q) > v01 = round(y1/2q) > v02 = round(y2/2q) > v03 = round(y3/2q) > v10 = round((y0-1)/2q) > v11 = round((y1-1)/2q) > v12 = round((y2-1)/2q) > v13 = round((y3-1)/2q) > t = abs(y0 - 2q*v00) > t += abs(y1 - 2q*v01) > t += abs(y2 - 2q*v02) > t += abs(y3 - 2q*v03) > if(t < 2q): > v0 = v00 > v1 = v01 > v2 = v02 > v3 = v03 > k = 0 > else > v0 = v10 > v1 = v11 > v2 = v12 > v3 = v13 > r = 1 > return (v0-v3,v1-v3,v2-v3,k+2*v3) > > In this description, round() returns the closest integer and abs() returns the > absolute value. > Note that all computations involved in helprec operate on secret data and must > be protected against timing attacks. round() is underspecified here: does 0.5 round to 0 or 1? Or is it not possible to get answers that are exactly halfway between two integers? Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B ricochet:ekmygaiu4rzgsk6n signature.asc Description: Message signed with OpenPGP using GPGMail ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 output of SHAKE-128 > > is considered a sequence of 16-bit little-endian integers. This sequence is > > used to initialize the coefficients of the returned polynomial from the least > > significant (coefficient of X^0) to the most significant (coefficient of > > X^1023) coefficient. For each of the 16-bit integers first eliminate the > > highest two bits (to make it a 14-bit integer) and then use it as the next > > coefficient if it is smaller than q=12289. > > Note that the amount of output required from SHAKE to initialize all 1024 > > coefficients of the polynomial varies depending on the input seed. > > Note further that this function does not process any secret data and thus does > > not need any timing-attack protection. > > Aren't the seed and polynomial a actually secret for negotiation with > any node after your guard? > > An adversary who can do a timing attack on a user's tor process would > gain some deanonymizing information from knowing which a elements get > skipped. I suppose this adversary has already nailed the user via > correlation attack, but maybe worth rewording at least. > > And maybe an adversary could employ different attack infrastructure if > they can learn some skipped elements of a. I agree with Jeff: usually in Ring-LWE, a isn't a secret value, so timing attacks don't matter. But when the value of a is shared only between Alice and Bob, then it is identifying information which could be used in a deanonymyzation attack, so it should be viewed as secret. So it's generation should be secure against timing attacks - the same amount of SHAKE output should be consumed every time. It's hard to guarantee that any fixed, finite amount of SHAKE output will be sufficient for any rejection sampling method like gen_a. So maybe an arithmetic coding like scheme could be used? That would get much closer to log_2(12289) bits being used for each coefficient. Or let a be a system-wide parameter changing say on a daily basis? (Cuts down marginally on bandwidth and computation time at the expense of a many-for-the-price-of-one attack so as others have observed probably not a good idea). rec(poly f, NEWHOPE_REC r) / Decode(v0,v1,v2,v3): This function operates on secret data - the values of t0,t1,t2,t3 must be kept secret, so must also be timing-attack-resistant. Also the calculation of t is incorrect as stated (copy-and-paste error; needs to be a function of v1,v2,v3,t1,t2,t3 etc.) If I ever get chance to play with the code I'd like to have a go a producing some test vectors. Thanks isis for this, it looks really good, I look forward to seeing a similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !) -- lukep ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 expands >> > this seed through SHAKE-128 from the FIPS202 standard. The output of > SHAKE-128 >> > is considered a sequence of 16-bit little-endian integers. This > sequence is >> > used to initialize the coefficients of the returned polynomial from > the least >> > significant (coefficient of X^0) to the most significant (coefficient of >> > X^1023) coefficient. For each of the 16-bit integers first eliminate the >> > highest two bits (to make it a 14-bit integer) and then use it as the >> > next >> > coefficient if it is smaller than q=12289. >> > Note that the amount of output required from SHAKE to initialize all 1024 >> > coefficients of the polynomial varies depending on the input seed. >> > Note further that this function does not process any secret data and > thus does >> > not need any timing-attack protection. >> >> Aren't the seed and polynomial a actually secret for negotiation with >> any node after your guard? >> >> An adversary who can do a timing attack on a user's tor process would >> gain some deanonymizing information from knowing which a elements get >> skipped. I suppose this adversary has already nailed the user via >> correlation attack, but maybe worth rewording at least. >> >> And maybe an adversary could employ different attack infrastructure if >> they can learn some skipped elements of a. > > I agree with Jeff: usually in Ring-LWE, a isn't a secret value, so timing > attacks don't matter. But when the value of a is shared only between Alice > and Bob, then it is identifying information which could be used in a > deanonymyzation attack, so it should be viewed as secret. So it's generation > should be secure against timing attacks - the same amount of SHAKE output > should be consumed every time. 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. > > It's hard to guarantee that any fixed, finite amount of SHAKE output will be > sufficient for any rejection sampling method like gen_a. So maybe an > arithmetic coding like scheme could be used? That would get much closer to > log_2(12289) bits being used for each coefficient. Or let a be a system-wide > parameter changing say on a daily basis? (Cuts down marginally on bandwidth > and computation time at the expense of a many-for-the-price-of-one attack so > as others have observed probably not a good idea). > > rec(poly f, NEWHOPE_REC r) / Decode(v0,v1,v2,v3): > This function operates on secret data - the values of t0,t1,t2,t3 must be > kept secret, so must also be timing-attack-resistant. Also the calculation > of t is incorrect as stated (copy-and-paste error; needs to be a function of > v1,v2,v3,t1,t2,t3 etc.) > > If I ever get chance to play with the code I'd like to have a go a producing > some test vectors. > > Thanks isis for this, it looks really good, I look forward to seeing a > similar protocol for SIDH! (and X25519+NEWHOPE+SIDH !) > > -- lukep > > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev -- "Man is born free, but everywhere he is in chains". --Rousseau. ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
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 large enough to tend towards the expected 42%ish failures. Also, can't one simply start the sampling over from the beginning if one runs out? I've no idea if an maybe an arithmetic coding scheme would be more efficient. > Or let a be a system-wide parameter changing say on a daily basis? I mentioned using the Tor collaborative random number generator for a in my other message, but only as feint to get to the meat of my argument that Isis and Peter's proposal sounds optimal. I think rotating a network wide a would get messy and dangerous in practice. If bandwidth is an issue, then a could be derived from the ECDH handshake, thereby making it zero cost. Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 node in your circuit and hence sees your seed later. You get unlucky like over 400 times, so, if they can record enough of the failure pattern, then their node can recognize you from your seed. Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 Research's is less slow than prior attempts at this, but misses the mark). On Sat, 07 May 2016 22:51:27 +0200 Jeff Burdges wrote: > 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. I think that being in the position to gather the timing information required on the client side means the adversary has won already, so I'm not seeing the issue here apart from an abstract theoretical sense. > Isn't some small multiple usually enough? I think 1024 is large > enough to tend towards the expected 42%ish failures. > > Also, can't one simply start the sampling over from the beginning if > one runs out? For clarity regarding what the code does now: The reference code generates excess output from the initial SHAKE call, and samples from that, and incrementally squeezes out an additional block one at a time as required (Enough for 1344 elements, with each additional squeeze providing 21 elements). (The rejection sampling algorithm is somewhat wasteful since it discards 2 bits of input per sample as well, but what's done now is easier to implement.) > I've no idea if an maybe an arithmetic coding scheme would be more > efficient. > > > Or let a be a system-wide parameter changing say on a daily basis? > > I mentioned using the Tor collaborative random number generator for a > in my other message, but only as feint to get to the meat of my > argument that Isis and Peter's proposal sounds optimal. I think > rotating a network wide a would get messy and dangerous in practice. > > If bandwidth is an issue, then a could be derived from the ECDH > handshake, thereby making it zero cost. Err. I'm not sure how that will work without rejection sampling that exposes timing information, maybe I'm missing something. I had a brief discussion with Dr. Schwabe regarding using deterministic `a` generation for unrelated reasons, with something time based being tossed around, but requiring a global clock isn't that great, and leaks clock skew information (Though I would use something like H(tweak | unixTime / 3600), which is rather coarse...), and as a peace of mind thing, I do prefer randomizing `a` on a per-connection basis. But anyway like I said, I don't think this is an issue. Regards, -- Yawning Angel pgpNMRQIf9EPO.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 need anyway about SHAKE indistinguishability. > > We're assuming the adversary controls a node in your circuit and hence > sees your seed later. You get unlucky like over 400 times, so, if > they can record enough of the failure pattern, then their node can > recognize you from your seed. Hmm? The timing information that's available to a local attacker (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) would be the total time taken for `a` generation. So. the evil observer on Alice's side gets: * The total number of samples (N). Bob (or Eve) gets: * The seed, which may correspond to something that required N samples. I don't think there's much pattern information available to the attacker on Alice's side, but I may be missing something... Regards, -- Yawning Angel pgpKwAhU3ejBu.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
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 Yes, it's clear that an adversary who can get CPU timing can get packet timing. It's not clear if some adversary might prefer information about the seed to simplify their larger infrastructure, like say by not needing to worry about clock skew on their exit nodes, or even choosing to compromise exit nodes soon after the fact. > Hmm? The timing information that's available to a local attacker > would be the total time taken for `a` generation. Really? I know nothing about the limits of timing attacks. I just naively imagined they learn from the timing of CPU work vs memory writes or something. Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 > > Yes, it's clear that an adversary who can get CPU timing can get > packet timing. > > It's not clear if some adversary might prefer information about the > seed to simplify their larger infrastructure, like say by not needing > to worry about clock skew on their exit nodes, or even choosing to > compromise exit nodes soon after the fact. The ultimate simplification would be "snoop the loopback interface and see all the cleartext instead of messing with this timing attack nonsense". :P > > Hmm? The timing information that's available to a local attacker > > would be the total time taken for `a` generation. > > Really? I know nothing about the limits of timing attacks. I just > naively imagined they learn from the timing of CPU work vs memory > writes or something. What's there to derive key generation timing information from that isn't "observe traffic to the SocksPort, along with traffic upstream and compare times". There might be better ways, that somehow don't involve totally pwning the box, but it's not immediately obvious to me. If we're going to talk about improving `a` generation overall, rejecting samples only if they are > 5 * q (and using `% q` per sample) is probably a net win since it lowers the rejection rate by a factor of ~4x... Regards, -- Yawning Angel pgp8OzmUl7Hra.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Typos: > used as input to the SHAKE-256 extendable output function (XOF), as decribed deScribed > In the case for relays possessing Ed25519 identity keys (c.f. Tor proposal > ... > descriptor (c.f. Tor proposal #264) advertises support for the "Relay" > ... > (c.f. Tor proposal #249). > ... > We introduce a new sub-protocol number, "Relay=3", (c.f. Tor proposal #264 confer, cf., it's a single flying word > public keys already being in included within the "ntor-onion-key" entry. s/in included/included/ > poly_getnoise() first generates 4096 Bytes of uniformly random data. This can s/Bytes/bytes/ > mode). The output of the PRG is considered an array of 2048 16-bit integers > ... > Note further that the output of this function is secret; the PRG (and the PRnG was used previously > pseudocode description of a very naive inplace transformation of an input > ... > [0]; a pseudocode description of a very naive inplace transformation of an s/inplace/in-place/g ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 output of > > SHAKE-128 > > is considered a sequence of 16-bit little-endian integers. This sequence > > is > > used to initialize the coefficients of the returned polynomial from the > > least > > significant (coefficient of X^0) to the most significant (coefficient of > > X^1023) coefficient. For each of the 16-bit integers first eliminate the > > highest two bits (to make it a 14-bit integer) and then use it as the next > > coefficient if it is smaller than q=12289. > > Note that the amount of output required from SHAKE to initialize all 1024 > > coefficients of the polynomial varies depending on the input seed. > > Note further that this function does not process any secret data and thus > > does > > not need any timing-attack protection. > > Aren't the seed and polynomial a actually secret for negotiation with > any node after your guard? > > An adversary who can do a timing attack on a user's tor process would > gain some deanonymizing information from knowing which a elements get > skipped. I suppose this adversary has already nailed the user via > correlation attack, but maybe worth rewording at least. > > And maybe an adversary could employ different attack infrastructure if > they can learn some skipped elements of a. Hey Jeff, At first, I wasn't convinced that guarding against an adversary who is both capable to run a spy process on a client machine, as well as be the middle/exit relay in the client's circuit, was within Tor's threat model. However, if it isn't within our threat model, it should be, because e.g. who knows what crap JS a browser is executing. Let's just assume this is within the model. I haven't given it much thought yet, but the performance cost to making polynomial initialisation constant time may not actually be so bad. My naïve, I'm-still-finishing-my-breakfast solution would be to oversample (say 2048 uint16_ts) from SHAKE-128, shove them into a stable sorting network with a comparator which says "not equal" for x[i]>q and "equal" otherwise. -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
isis wrote: Hi all, > I haven't given it much thought yet, but the performance cost to making > polynomial initialisation constant time may not actually be so bad. My naïve, > I'm-still-finishing-my-breakfast solution would be to oversample (say 2048 > uint16_ts) from SHAKE-128, shove them into a stable sorting network with a > comparator which says "not equal" for x[i]>q and "equal" otherwise. My (hopefully) slightly improved variant of this one is to take three "sqeezes" from SHAKE-128 to obtain 252 16-bit integers, pad to 256, use Batcher's odd-even merge sort to move all the entries >= 5q (using Yawning's idea to lower the rejection probability) to the end of the array with the comparison that Isis described and then take the low 205, which are all smaller than 5q with overwhelmingly large (still need to do the math here) probability. Do this 5 times and you have enough coefficients for the polynomial. Should you run into one of the rare cases where you don't have 205 good entries, simply pick a new seed. The nice thing is that you can easily vectorize this; a 16x vectorized version (producing more than enough output for 3 handshakes) takes <53000 cycles on Haswell; the code is checked into the newhope-tor-testvectors directory in the discard subdirectory. This does not include reduction mod q, but that's also not required inside the computation of NewHope. Cheers, Peter signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 aboard the Slow Crypto Train…) Best, -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 large enough > to tend towards the expected 42%ish failures. > > Also, can't one simply start the sampling over from the beginning if one > runs out? Yes, you can safely start the sampling over from the beginning without giving anything away, other than "the seed was bad". > > Or let a be a system-wide parameter changing say on a daily basis? > > I mentioned using the Tor collaborative random number generator for a in > my other message, but only as feint to get to the meat of my argument > that Isis and Peter's proposal sounds optimal. I think rotating a > network wide a would get messy and dangerous in practice. Peter and I also discussed generating `a` from the Tor shared randomness, but ultimately I feel squeamish about the potential anonymity-set segregations. > If bandwidth is an issue, then a could be derived from the ECDH > handshake, thereby making it zero cost. That would add an extra RT to the handshake, since the handshakes could no longer happen in parallel (in my construction, they're actually literally side-by-side, in the same CREATE2V cell). Separating the handshake would also mean we'd need some new cell types to handle the fact that the handshake would take 2 RTs, since Tor's design now assumes ---CREATE*--> then <---CREATED*---. Also, deriving `a` "somehow" from the shared X25519 secret is a bit scary (c.f. the §3 "Backdoors" part of the NewHope paper, or Yawning's PoC of a backdoored NewHope handshake [0]). [0]: https://git.schwanenlied.me/yawning/newhope/src/nobus/newhope_nobus.go Best, -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 implementation, it might be worth > considering (MS Research's is less slow than prior attempts at this, > but misses the mark). When there is also sufficient cryptanalysis of curve-isogeny-based cryptosystems… Also, I'm not understanding what SIDH would provide in an X25519+NewHope+SIDH construction which is not already provided in the X25519+NewHope construction, unless someday there are SIDH-based signatures. > On Sat, 07 May 2016 22:51:27 +0200 > Jeff Burdges wrote: > > 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. > > I think that being in the position to gather the timing information > required on the client side means the adversary has won already, so I'm > not seeing the issue here apart from an abstract theoretical sense. Your point that an adversary with native-code execution on the client's machine is capable to do worse makes sense. However, given that there are browser-based cache timing attacks (e.g. RowhammerJS) which give cache eviction rates only negligably different to those of native-code exploits, I would argue that Jeff's original concern that the timing attack presents a distinguisher is actually a valid concern. > > I've no idea if an maybe an arithmetic coding scheme would be more > > efficient. > > > > > Or let a be a system-wide parameter changing say on a daily basis? > > > > I mentioned using the Tor collaborative random number generator for a > > in my other message, but only as feint to get to the meat of my > > argument that Isis and Peter's proposal sounds optimal. I think > > rotating a network wide a would get messy and dangerous in practice. > > > > If bandwidth is an issue, then a could be derived from the ECDH > > handshake, thereby making it zero cost. > > Err. I'm not sure how that will work without rejection sampling that > exposes timing information, maybe I'm missing something. Nope, it would still not work to fix the timing attack. Although, luckily, we already wrote some constant time code for my sorting-network idea, and then, with some coffee, Peter made it faster. (Give us something stronger to drink, and we'll probably come up with a way to get it even faster.) Best, -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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&id=5c115905 -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
isis wrote: Hi all, > Nope, it would still not work to fix the timing attack. Although, luckily, we > already wrote some constant time code for my sorting-network idea, and then, > with some coffee, Peter made it faster. (Give us something stronger to drink, > and we'll probably come up with a way to get it even faster.) Still on coffee and with a size-84 Batcher sort and Yawning's 5q trick I now have an AVX2 implementation of NewHope that is faster than the original and does sampling of the polynomial a in constant time. Now I'm up for some stronger drinks... Cheers, Peter signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Yawning Angel transcribed 2.2K bytes: > On Fri, 6 May 2016 19:17:11 + > isis wrote: > > Both parties check that none of the EXP() operations produced the > > point at infinity. [NOTE: This is an adequate replacement for > > checking Y for group membership, if the group is Curve25519.] > > > > [XXX: This doesn't sound exactly right. You need the scalar > > tweaking of X25519 for this to work and also, the point at infinity > > is obviously an element of the group --isis, peter] > > Maybe reword this to specify that EXP() MUST include the check for all > zero output as specified in RFC 7748. It's what our current ntor > implementation does here. Thanks, good suggestion. I've added it here: https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=bcf8c60a And removed the odd description w.r.t. "the Curve25519 group" here: https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=d04f771f FWIW, the original "Both parties check that none of the EXP() […] group is Curve25519" sentence comes directly from the original NTor specification in proposal #216, so we might consider making this change there: https://gitweb.torproject.org/torspec.git/tree/proposals/216-ntor-handshake.txt#n99 -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Sun, 2016-05-08 at 13:15 +, isis wrote: > Also, deriving `a` "somehow" from the shared X25519 secret is a bit > scary > (c.f. the §3 "Backdoors" part of the NewHope paper, Oh wow. That one is nasty. > or Yawning's PoC of a > backdoored NewHope handshake [0]). > > [0]: > https://git.schwanenlied.me/yawning/newhope/src/nobus/newhope_nobus.go I see. The point is that being ambiguous about the security requirements of the seed for a lets you sneak in a bad usage of it elsewhere. In some cases, I suppose both sides contributing to a might help them know the other side is not backdoored, but that's not so relevant for Tor. Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
isis wrote: > eik...@sigaint.org transcribed 1.1K bytes: >> Typos: > > Thanks! Fixed: > > https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=5c115905 You skipped 2: - public keys already being in included within the "ntor-onion-key" entry. + public keys already being included within the "ntor-onion-key" entry. - [0]; a pseudocode description of a very naive inplace transformation of an + [0]; a pseudocode description of a very naive in-place transformation of an ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 > > #220), this is a 32-byte string representing the public Ed25519 identity > > key. > > For backwards and forwards compatibility with routers which do not possess > > Ed25519 identity keys, this is a 32-byte string created via the output of > > H(ID). > > I don't understand why we do this backwards and forwards compatibility for > ID, when the proposal only works for relays with an ed25519 key in their > descriptor. Relays have a Curve25519 "ntor-onion-key" in their microdescriptors, is that what you meant? By "router's identity key from the microdescriptor", I was referring to either the RSA-1024 identity key which is in the "id rsa1024" lines, [0] or (whenever prop#220 features are fully available) the "id ed25519" lines (see prop#220 §3.2). [1] I was mostly concerned about the backwards-/forwards- compatibility because otherwise there would be an annoying length difference that would make things messy. > round() is underspecified here: does 0.5 round to 0 or 1? > Or is it not possible to get answers that are exactly halfway between two > integers? Yes, that is under-specified. Peter fixed it in this commit. [2] [0]: https://collector.torproject.org/recent/relay-descriptors/microdescs/micro/2016-05-08-16-05-31-micro [1]: https://gitweb.torproject.org/torspec.git/tree/proposals/220-ecc-id-keys.txt#n307 [2]: https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=28181cc7 -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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&id=5c115905 > > You skipped 2: > > - public keys already being in included within the "ntor-onion-key" entry. > + public keys already being included within the "ntor-onion-key" entry. > > - [0]; a pseudocode description of a very naive inplace transformation of an > + [0]; a pseudocode description of a very naive in-place transformation of an Oops! Thanks again. Peter fixed those in this commit: https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=28181cc7 -- ♥Ⓐ isis agora lovecruft _ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Hi all, If I understand it properly, in the proposal the client need to send the whole matrix A during the first initiation message. I draw this conclusion from the datagram: | a, A := NEWHOPE_KEYGEN(SEED) | | CLIENT_HDATA := ID || Z || X || A | | | | --- CLIENT_HDATA ---> May I ask why? Is it because the keypair generation is modularized, and hence a and A are connected from a protocol point of view? However, in the original construction of new hope, or other R-LWE based schemes, a and A are sampled independently, giving out the seed of A will not leak information on a. So how about the following: | A:= NEWHOPE_PK_KEYGEN(SEED1) | | a:= NEWHOPE_SK_KEYGEN(SEED2) | | CLIENT_HDATA := ID || Z || X || SEED1 | | | | --- CLIENT_HDATA ---> This will save significant data for the first transmission: over 1 KB of A compared to 32 bits of SEED1. The server will be able to recover A from NEWHOPE_PK_KEYGEN which will be a public function. Cheers, Zhenfei On Mon, May 9, 2016 at 12:07 PM, isis wrote: > 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&id=5c115905 > > > > You skipped 2: > > > > - public keys already being in included within the "ntor-onion-key" > entry. > > + public keys already being included within the "ntor-onion-key" entry. > > > > - [0]; a pseudocode description of a very naive inplace transformation > of an > > + [0]; a pseudocode description of a very naive in-place transformation > of an > > Oops! Thanks again. Peter fixed those in this commit: > > https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=28181cc7 > > -- > ♥Ⓐ isis agora lovecruft > _ > OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 > Current Keys: https://fyb.patternsinthevoid.net/isis.txt > > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > > ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Sorry, my bad. Please ignore my previous email. I just noticed that here A
is
not the public polynomial \hat{a} in the R-LWE setting, but the
concatenation
of a seed that generates \hat{a}, and client's side of secret \hat{b} =
\hat{a} s+e
Zhenfei
On Mon, May 9, 2016 at 2:04 PM, Zhenfei Zhang wrote:
> Hi all,
>
> If I understand it properly, in the proposal the client need to send the
> whole
> matrix A during the first initiation message. I draw this conclusion from
> the
> datagram:
>
> | a, A := NEWHOPE_KEYGEN(SEED)
> |
> | CLIENT_HDATA := ID || Z || X || A
> |
> |
> |
> | --- CLIENT_HDATA --->
>
>
>
> May I ask why? Is it because the keypair generation is modularized, and
> hence a and A are connected from a protocol point of view? However, in the
> original construction of new hope, or other R-LWE based schemes, a and A
> are sampled independently, giving out the seed of A will not leak
> information
> on a. So how about the following:
>
> | A:= NEWHOPE_PK_KEYGEN(SEED1)
> |
> | a:= NEWHOPE_SK_KEYGEN(SEED2)
> |
> | CLIENT_HDATA := ID || Z || X || SEED1
> |
> |
> |
> | --- CLIENT_HDATA --->
>
>
>
> This will save significant data for the first transmission: over 1 KB of A
> compared to 32 bits of SEED1. The server will be able to recover A from
> NEWHOPE_PK_KEYGEN which will be a public function.
>
>
> Cheers,
> Zhenfei
>
>
> On Mon, May 9, 2016 at 12:07 PM, isis wrote:
>
>> 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&id=5c115905
>> >
>> > You skipped 2:
>> >
>> > - public keys already being in included within the "ntor-onion-key"
>> entry.
>> > + public keys already being included within the "ntor-onion-key" entry.
>> >
>> > - [0]; a pseudocode description of a very naive inplace transformation
>> of an
>> > + [0]; a pseudocode description of a very naive in-place
>> transformation of an
>>
>> Oops! Thanks again. Peter fixed those in this commit:
>>
>> https://gitweb.torproject.org/user/isis/torspec.git/commit/?h=draft/newhope&id=28181cc7
>>
>> --
>> ♥Ⓐ isis agora lovecruft
>> _
>> OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
>> Current Keys: https://fyb.patternsinthevoid.net/isis.txt
>>
>> ___
>> tor-dev mailing list
>> tor-dev@lists.torproject.org
>> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>>
>>
>
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Hello, My tinfoil hat went crinkle in the night[0], and I had an additional thought here. Should we encrypt the `CLIENT_NEWHOPE` and `SERVER_NEWHOPE` values using and something derived from `EXP(Z,x)`/`EXP(X,z)`? It doesn't have perfect forward secrecy (compromise of `z` would allow the adversary to decrypt all previous ciphertexts), but it's better than nothing. CPU-wise it's 1 additional KDF call (assuming you squeeze out the forward and return symmetric keys at once), 1 extra CSPRNG call (for the IV), and 2 AE calls. And `len(IV) + len(Tag)` bytes of extra traffic in each direction in terms of extra network overhead, both which I think are relatively cheap. Regards, -- Yawning Angel [0]: Along with "I do this for basket2 for other reasons[1], and I think it's a good idea even for tor". [1]: newhope public keys are "blatantly obvious" on the wire. pgpLi2snBeLJk.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Yawning Angel transcribed 2.5K bytes:
> Hello,
>
> My tinfoil hat went crinkle in the night[0], and I had an additional
> thought here. Should we encrypt the `CLIENT_NEWHOPE` and
> `SERVER_NEWHOPE` values using and
> something derived from `EXP(Z,x)`/`EXP(X,z)`?
>
> It doesn't have perfect forward secrecy (compromise of `z` would allow
> the adversary to decrypt all previous ciphertexts), but it's better
> than nothing.
>
> CPU-wise it's 1 additional KDF call (assuming you squeeze out the
> forward and return symmetric keys at once), 1 extra CSPRNG call (for
> the IV), and 2 AE calls. And `len(IV) + len(Tag)` bytes of extra
> traffic in each direction in terms of extra network overhead, both
> which I think are relatively cheap.
This is an interesting idea. Let me just make sure I've understood correctly.
In your idea, it goes like this?
Initiator Responder
SEED := H(randombytes(32))
x, X := X25519_KEYGEN()
a, A := NEWHOPE_KEYGEN(SEED)
CLIENT_HDATA := ID || Z || EXP(Z, X || A)
--- CLIENT_HDATA --->
y, Y := X25519_KEYGEN()
X, A := EXP(z, X || A)
NTOR_KEY, AUTH :=
NTOR_SHAREDB(X,y,Y,z,Z,ID,B)
M, NEWHOPE_KEY := NEWHOPE_SHAREDB(A)
SERVER_HDATA := Y || AUTH || M
sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)
<-- SERVER_HDATA
NTOR_KEY:= NTOR_SHAREDA(x, X, Y, Z, ID, AUTH)
NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)
sk := SHAKE-256(NTOR_KEY, NEWHOPE_KEY)
I think I see what you're saying.
In the case of the currect context, it doesn't make much sense: an adversary
with a fully opeerational quantum computer can, in polynomial time, decrypt
the Curve25519 encryption to the ntor-onion-key ("Z" here) and then have
trivial access to the rest of the handshake.
However, moving forward, since we intend to switch to AE(AD) ciphers at the
circuit level, this makes absolute sense. This costs us two extra modular
exponentiations now, but, in the future, with an AEAD cipher, we should be
able to put `X` into the associated data and have the the handshake's
authentication be implicit from the first round. Moving forward, this is
worth the extra two modular exponentiations on either side, since it causes
extra (exponential) computational effort for a classical adversary, until the
time of a quantum adversary (in which it still causes polynomial effort to
decrypt the handshake). For such a minor expense as two exp(), we can cause
exponential expense for a classical adversay, and polynomial expense for a
quantum adversary — which makes this worthwhile.
Did I understand the idea correctly?
Best Regards,
--
♥Ⓐ isis agora lovecruft
_
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
signature.asc
Description: Digital signature
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 12 May 2016 03:48:21 +
isis wrote:
[snippity[
> This is an interesting idea. Let me just make sure I've understood
> correctly. In your idea, it goes like this?
Almost.
Let Seal(key, nonce, plaintext) be the forward
GCM-AES128/XChaCha20Poly1305/whatever encrypt operation, with the
specified key, nonce, and plaintext.
Let Unseal(key, nonce, ciphertext) be the reverse
GCM-AES128/XChaCha20Poly1305/whatever decrypt operation with the
specified key, nonce, and ciphertext.
Initiator Responder
SEED := H(randombytes(32))
x, X := X25519_KEYGEN()
a, A := NEWHOPE_KEYGEN(SEED)
xZ := EXP(Z,x) // X25519 Scalar multiply (raw, later
used in NTOR_SHAREDA)
kTmp := H(tweak || xZ)
nonce:= randombytes(nonceSize) // Random nonce.
CLIENT_HDATA := X || nonce || Z || Seal(kTmp, nonce, ID || A) // If Seal does
AEAD, also send Z as the AD
--- CLIENT_HDATA --->
zX:= EXP(X,z) // X25519 Scalar
multiply (raw)
kTmp := H(tweak || zX)
ID, A := Unseal(kTmp, nonce,
CLIENT_HDATA[ciphertextOffset:]) // Abort if Unseal fails.
y, Y := X25519_KEYGEN()
yX := EXP(X, y) // X25519
Scalar multiply (raw)
NTOR_KEY, AUTH :=
NTOR_SHAREDB(zX,yX,Z,Y,ID,B) // No X25519 calls in here anymore.
M, NEWHOPE_KEY := NEWHOPE_SHAREDB(A)
kTmp' := H(tweak || yX)// Return AE
key, could alternatively reuse kTmp, but this has better forward secrecy.
nonce' := randombytes(nonceSize)
SERVER_HDATA := Y || nonce ||
Seal(kTmp', nonce', AUTH || M)
sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)
<-- SERVER_HDATA
xY := EXP(Y,x) // X25519 Scalar multiply (raw)
kTmp' := H(tweak || xY)
M, AUTH := Unseal(kTmp', nonce', SERVER_HDATA[cipherTextOffset':]) // Abort if
Unseal fails.
NTOR_KEY:= NTOR_SHAREDA(xZ, xY, Y, Z, ID, AUTH) // No X25519 calls in here
anymore either.
NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)
sk := SHAKE-256(NTOR_KEY, NEWHOPE_KEY)
> In the case of the currect context, it doesn't make much sense: an
> adversary with a fully opeerational quantum computer can, in
> polynomial time, decrypt the Curve25519 encryption to the
> ntor-onion-key ("Z" here) and then have trivial access to the rest of
> the handshake.
Correct. In a post quantum world, this is totally pointless,
especially since `Z` is publicly available from the microdescriptors,
but in the mean time it's extra authenticated, and extra sekrit.
> Did I understand the idea correctly?
Mostly. There's no extra EXP() calls at all. NTOR_SHAREDA/SHAREDB requires
that we calculate:
Client: EXP(Z,x), EXP(Y,x)
Server: EXP(X,z), EXP(X,y)
The client uses EXP(Z,x), which we have to calculate anyway for ntor, to
encrypt/authenticate `ID || A` of CLIENT_HDATA (and optionally Z).
(There isn't any point in including X in the AD, because if someone messes with
X, Unseal() will fail).
The server uses EXP(X,y), which we have to calculate anyway for ntor, to
encrypt/authenticate `AUTH || M`.
The only overhead is 2 calls to the AE(AD) construct, 2x random nonce
generation, and 2 calls into H(). If we want to be extra sneaky, we
could also do the NTRU handshake this way (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
algorithm we are using).
Regards,
--
Yawning Angel
pgpVs_RIBcjGB.pgp
Description: OpenPGP digital signature
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 > algorithm we are using). This sounds like a win. We still do not know if/when quantum computers will become practical. It was only just last year that 15 was finally factored "without cheating" : http://www.scottaaronson.com/blog/?p=2673 We do know that advancements against public key crypto systems will occur, so wrapping up the more unknown system more tightly sounds wise. In the shorter term, SIDH would take only one extra cell, maybe none if tweaked downward, as compared to the four of New Hope, and whatever NTRU needs. This variation might be good or bad for anonymity, but it's sound better if fewer nodes can compare the numbers of packets with the algorithms used. Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 have > > a quantum computer and calculate `z` to figure out which post > > quantum algorithm we are using). > > This sounds like a win. > > We still do not know if/when quantum computers will become practical. > It was only just last year that 15 was finally factored "without > cheating" : http://www.scottaaronson.com/blog/?p=2673 > > We do know that advancements against public key crypto systems will > occur, so wrapping up the more unknown system more tightly sounds > wise. > > > In the shorter term, SIDH would take only one extra cell, maybe none > if tweaked downward, as compared to the four of New Hope, and > whatever NTRU needs. This variation might be good or bad for > anonymity, but it's sound better if fewer nodes can compare the > numbers of packets with the algorithms used. Well, if we move the handshake identifier inside the AE(AD) envelope, we can also add padding to normalize the handshake length at minimal extra CPU cost by adding a length field and some padding inside as well. It would remove some of the advantages of using algorithms with shorter keys (since it would result in more traffic on the wire than otherwise would have been), but handshakes will be indistinguishable to anyone but space aliens and the final destinations... Regards, -- Yawning Angel pgpBkG_E2gckQ.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 2016-05-12 at 11:17 +, Yawning Angel wrote: > Well, if we move the handshake identifier inside the AE(AD) envelope, > we can also add padding to normalize the handshake length at minimal > extra CPU cost by adding a length field and some padding inside as > well. > > It would remove some of the advantages of using algorithms with > shorter > keys (since it would result in more traffic on the wire than otherwise > would have been), but handshakes will be indistinguishable to anyone > but space aliens and the final destinations... Is that even beneficial though? If we choose our post-quantum algorithm randomly from New Hope and SIDH, and add random delays, then maybe an adversary has less information about when a circuit build is progressing to the next hop, or when it's actually being used? Is there some long delay between circuit build and first use that makes anything done to obscure build useless? Jeff signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 12 May 2016 14:18:41 +0200 Jeff Burdges wrote: > On Thu, 2016-05-12 at 11:17 +, Yawning Angel wrote: > > Well, if we move the handshake identifier inside the AE(AD) > > envelope, we can also add padding to normalize the handshake length > > at minimal extra CPU cost by adding a length field and some padding > > inside as well. > > > > It would remove some of the advantages of using algorithms with > > shorter > > keys (since it would result in more traffic on the wire than > > otherwise would have been), but handshakes will be > > indistinguishable to anyone but space aliens and the final > > destinations... > > Is that even beneficial though? Padding the handshake out for the number of cells? Maybe? I'm not entirely convinced here either way, just highlighting it as an option. > If we choose our post-quantum algorithm randomly from New Hope and > SIDH, and add random delays, then maybe an adversary has less > information about when a circuit build is progressing to the next > hop, or when it's actually being used? Dunno. I need to re-benchmark product form NTRU but I think it's in the same ballpark as newhope (May be faster, but the differential isn't totally ridiculous as anything compared to SIDH is). I don't think SIDH is really something to worry about now anyway... having both NTRUEncrypt and newhope as options for the first pass should be sufficient, and the bulk of the code required to do this is the infrastructure work for modular/large handshakes anyway (Once we support at least one PQ algorithm, adding others is relatively easy). > Is there some long delay between circuit build and first use that > makes anything done to obscure build useless? We pre-build circuits, but the telescoping extension process and opportunistic data both mean that circuits see "traffic" near-immediately in most cases (everyone but the exit will see the traffic of handshaking to further hops, the exit sees opportunistic data in some cases). Regards, -- Yawning Angel pgp8dkuzERKRd.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 algorithm, but as far as I understand, AEAD is a completely separate discussion within Tor and this would be replaced by whatever that discussion's outcome is? > Correct. In a post quantum world, this is totally pointless, > especially since `Z` is publicly available from the microdescriptors, > but in the mean time it's extra authenticated, and extra sekrit. Can you describe a pre-quantum attacker who breaks the non-modified key exchange and does not, with essentially the same resources, break the modified key exchange? I'm not opposed to your idea, but it adds a bit of complexity and I would like to understand what precisely the benefit is. Best regards, Peter signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 2016-05-12 at 15:54 +0200, Peter Schwabe wrote: > Can you describe a pre-quantum attacker who breaks the non-modified > key > exchange and does not, with essentially the same resources, break the > modified key exchange? I'm not opposed to your idea, but it adds a bit > of complexity and I would like to understand what precisely the > benefit > is. Assuming I understand what Yawning wrote : It's about metadata leakage, not actual breaks. If Tor were randomly selecting amongst multiple post-quantum algorithms, then a malicious node potentially learns more information about the user's tor by observing the type of the subsequent node's handshake. In particular, if there is a proliferation of post-quantum choices, then it sounds very slightly more dangerous to allow users to configure what post-quantum algorithms they use without Yawning's change. Jeff p.s. At the extreme example, there is my up thread comment refuting the idea of using Sphinx-like packets with Ring-LWE. I asked : Why can't we send two polynomials (a,A) and mutate them together with a second Ring-LWE like operation for each hop? It's linear bandwidth in the number of hops as opposed to quadratic bandwidth, which saves 2-4k up in Tor's case and maybe keeps node from knowing quite as much about their position. Answer : If you do that, it forces the whole protocol's anonymity to rest on the Ring-LWE assumption, so it's no longer a hybrid protocol for anonymity, even though cryptographically it remains hybrid. signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 12 May 2016 20:31:56 +0200 Jeff Burdges wrote: > On Thu, 2016-05-12 at 15:54 +0200, Peter Schwabe wrote: > > Can you describe a pre-quantum attacker who breaks the non-modified > > key > > exchange and does not, with essentially the same resources, break > > the modified key exchange? I'm not opposed to your idea, but it > > adds a bit of complexity and I would like to understand what > > precisely the benefit > > is. > > Assuming I understand what Yawning wrote : > > It's about metadata leakage, not actual breaks. > > If Tor were randomly selecting amongst multiple post-quantum > algorithms, then a malicious node potentially learns more information > about the user's tor by observing the type of the subsequent node's > handshake. > > In particular, if there is a proliferation of post-quantum choices, > then it sounds very slightly more dangerous to allow users to > configure what post-quantum algorithms they use without Yawning's > change. Indeed, nailed it in one. My tinfoil hat crinkles less with the idea that people need to drill through X25519/an AEAD construct before they can start trying to break the PQ handshake (serializing the process somewhat, instead of being able to work on breaking each component of the hybrid construct in parallel)[0]. Most of my thoughts in this area stem from writing an obfuscated transport recently where I do use early encryption + padding to hide the algorithms used for the handshake. As a side note, if `Z` wasn't a value that the bad guys could pull out of the microdesc consensus, we could avoid sending it on the wire (and use the ephemeral/static derived keys for both directions) and really win (only `X` and say... `SHA3-256(Z)` (for disambiguation) available to the attacker means that we win, period regardless of space aliens), but alas we need to distribute `Z` somehow, so this is somewhat moot (so ephemeral/static in the forward direction, ephemeral/ephemeral in the reverse is better for forward secrecy reasons). Regards, -- Yawning Angel [0]: Even at the advent of quantum computers, I assume machine time will be a limited resource at first (till I can buy a RasPi 3000 "Now it's Quantum" off Amazon), and the idea of nameless suits from the government's crypto-industrial complex squabbling over machine tasking makes me feel warm and fuzzy inside. pgpeHCxCW_xdH.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Some great developments in lattice-based crypto. DJB just released a paper on NTRU Prime: 1. Competitively fast compared to the leading lattice-based cryptosystems including New Hope. 2. Safer implementation of NTRU that avoids vulnerable ring structures and runs in constant-time. 3. The only implemntation that mitigates decryption failures completely, killing information leaks to adversaries. 4. Includes some handy advice for "transitional cryptography" - mixing and matching classical signature schemes with PQ public-keys. https://ntruprime.cr.yp.to/ntruprime-20160511.pdf ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Hi all, > 3. The only implementation that mitigates decryption failures completely, killing information leaks to adversaries. This is clearly a nice-to-have feature, but it comes with a tradeoff. To remove decryption failures you need to increase the parameter q, but this affects size (and so performance) in two ways: first, the key and ciphertext are arrays of integers mod q, so obviously increasing log_2(q) increases key and ciphertext size; but second, increasing q makes lattice reduction attacks more effective, so it means that you need to increase the dimension parameter N as well to get the same level of lattice security. Conversely, it's not difficult to calculate upper bounds on decryption failure probabilities, so it's straightforward to find a q that gives less than 2^-k chance of a decryption failure. There's no particular need for a decryption failure probability that's less than the security of the other parts of the cryptosystem. Just wanted to explain why the standardized NTRUEncrypt parameter sets (from https://github.com/NTRUOpenSourceProject/ntru-crypto) are chosen the way they are, i.e. to have nonzero decryption failure probability. We could have chosen larger q and N but didn't think the tradeoff is worth it. Obviously the other point of view is legitimate too. Cheers, William On Thu, May 12, 2016 at 9:51 PM, wrote: > Some great developments in lattice-based crypto. DJB just released a paper > on NTRU Prime: > > > 1. Competitively fast compared to the leading lattice-based cryptosystems > including New Hope. > > 2. Safer implementation of NTRU that avoids vulnerable ring structures and > runs in constant-time. > > 3. The only implemntation that mitigates decryption failures completely, > killing information leaks to adversaries. > > 4. Includes some handy advice for "transitional cryptography" - mixing and > matching classical signature schemes with PQ public-keys. > > > https://ntruprime.cr.yp.to/ntruprime-20160511.pdf > > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
ban...@openmailbox.org transcribed 0.7K bytes: > Some great developments in lattice-based crypto. DJB just released a paper > on NTRU Prime: > > > 1. Competitively fast compared to the leading lattice-based cryptosystems > including New Hope. > > 2. Safer implementation of NTRU that avoids vulnerable ring structures and > runs in constant-time. > > 3. The only implemntation that mitigates decryption failures completely, > killing information leaks to adversaries. > > 4. Includes some handy advice for "transitional cryptography" - mixing and > matching classical signature schemes with PQ public-keys. > > > https://ntruprime.cr.yp.to/ntruprime-20160511.pdf 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. 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: 1. 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). 2. 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.) 3. 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 cl
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 the bandwidth a big deal? I suppose circuit building does not occupy much bandwidth, so no. On Thu, 2016-05-12 at 12:33 +, Yawning Angel wrote: > We pre-build circuits, but the telescoping extension process and > opportunistic data both mean that circuits see "traffic" > near-immediately in most cases (everyone but the exit will see the > traffic of handshaking to further hops, the exit sees opportunistic > data in some cases). Ok. I suppose that leaks a node's position in the circuit regardless, but perhaps that's not a concern. And I donno anything about opportunistic data. > I don't think SIDH is really something to worry about now anyway... If you like, I could ask Luca de Feo if he imagines it getting much faster, but I suspect his answer would be only a smallish factor, like another doubling or so. Assuming we stick to schemes with truly hybrid anonymity, then I suspect the anonymity cost of early adoption is that later parameter tweaks leak info about a user's tor version. We can always ask the MS SIDH folk, Luca, etc. what parameters could be tweaked in SIDH to get some idea. Jeff p.s. If taken outside Tor's context, I would disagree with your statement on SIDH : I donno NTRU well enough to comment on even how different the underlying reconciliation is from New Hope, but there might be an argument that most advances big enough to actually break New Hope would break NTRU and NTRU' too, so maybe one Ring-LWE scheme suffices. SIDH is an entirely different beast though. I've warm fuzzy feelings about the "evaluate on two points trick" used by Luca de Feo, et al., and by this SIDH, to fix previous attempts. It could always go down in mathematical flames, but it makes the scheme obnoxiously rigid, leaving jack for homomorphic properties, and could prove remarkably robust as a trapdoor. By comparison, there are going to be more papers on Ring-LWE because academic cryptographers will enjoy playing with it's homomorphic properties. Yet, one could imagine the link between Ring-LWE and dihedral HSP becoming more dangerous "looking", not necessarily producing a viable quantum attack, but maybe prompting deeper disagreements about parameter choices. In other words, I'd expect our future trust in Ring-LWE and SIDH to evolve in different ways. And counting papers will not be informative. Imho, almost anyone protecting user-to-user communications should hybrid ECDH, Ring-LWE, and SIDH all together, as users have CPU cycles to burn. Tor is user-to-volunteer-server though, so the economics are different. signature.asc Description: This is a digitally signed message part ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Mon, 16 May 2016 20:54:42 +0200 Jeff Burdges wrote: > 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? Yes. Even if it's multithreaded (and the client side circuit build crypto currently is not, though will be shortly), though this obviously "depends" on what each node is doing. Eg: * Client side performance is totally irrelevant up until the moment it becomes a busy HS (Eg: facebookcorewwwi.onion) in which case, it matters a huge deal (the X25519 scalar mult montgomery ladder has been a prominent feature in all of our profiling attempts for quite a while). * Relay side performance is totally irrelevant up until the moment it offers a lot of bandwidth, because the way our path selection weighs things right now, circuit builds will be weighted by consensus fraction. We used to have a slower handshake, and it was causing issues (TAP and that stupid botnet). Maybe I'm being over-cautious here. Maybe even the hybrid construct is too slow. Maybe bandwidth matters more. 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... > Is New Hope's 3+ times the bandwidth a big deal? I suppose circuit > building does not occupy much bandwidth, so no. It might. Sending bytes isn't free in terms of CPU either. The NTRUEncrypt based construct is fast and has shorter keys. > > I don't think SIDH is really something to worry about now > > anyway... > > If you like, I could ask Luca de Feo if he imagines it getting much > faster, but I suspect his answer would be only a smallish factor, like > another doubling or so. > > Assuming we stick to schemes with truly hybrid anonymity, then I > suspect the anonymity cost of early adoption is that later parameter > tweaks leak info about a user's tor version. We can always ask the > MS SIDH folk, Luca, etc. what parameters could be tweaked in SIDH to > get some idea. Agree here, though there is an auto updater for a reason, and if we we end up being overly concerned about that we won't even be using X25519 [snip] > In other words, I'd expect our future trust in Ring-LWE and SIDH to > evolve in different ways. And counting papers will not be > informative. Yeah probably. I can envision having no choice but to use SIDH sometime in the future (or vice versa). It's an evolving field, and my current mindset is "pick one or two that probably won't kill the network (CPU/network/whatever)", integrate it in a way that is easy to switch at a later point, and deploy it. > Imho, almost anyone protecting user-to-user communications should > hybrid ECDH, Ring-LWE, and SIDH all together, as users have CPU > cycles to burn. Tor is user-to-volunteer-server though, so the > economics are different. Dunno, I think this depends entirely on "how much money does the person operating the server have to throw at adding more CPU" vs "how many connections/sec does it need to sustain. I think doing something like SIDH on a massively popular website (say, hypothetically it gets added to TLS) would get expensive really quickly, but then again, it's VC monopoly money that's paying for it anyway, and it's not like they ever need to turn a profit right? (*cough* Twitter *cough*). Regards, -- Yawning Angel pgpH0I4BeIbQd.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 make a final, definitive choice of PQ algorithm since any of them could be broken mathematically. The possibility of backdoors in newhope (at least two different ways to do it) makes me nervous. SIDH is (perhaps?) too slow now but computers will get faster. NTRU is patented for the moment, but that will expire soon. It's all a tradeoff between security / cpu cycles / bandwidth and that tradeoff is bound to change over time. So we should have a protcol that allows a hybrid of X25519 for classical security plus one or more (or even zero, until we want to "switch it on") of the PQ algorithms. Use EXP(Z,x) to protect the choice of PQ algorithms and the actual PQ public key(s). Combine the X25519 shared secret and (all) the PQ shared secret(s) in one SHAKE-256 calculation to give sk. We'd need to think about what choice of PQ algorithms the client is allowed to make and what the server would accept. The risk is that we go down a rabbit-hole of TLS-style algorithm negotiation to agree on algorithm choices that are acceptable to both - we want it to "just work" without argument. But if we don't allow some choice, then we may find that the protocol is too slow, or the bandwidth too cumbersome, or we panic when one of the PQ algorithms is broken. > [snip] > > In other words, I'd expect our future trust in Ring-LWE and SIDH to > > evolve in different ways. And counting papers will not be > > informative. > > Yeah probably. I can envision having no choice but to use SIDH > sometime in the future (or vice versa). It's an evolving field, and my > current mindset is "pick one or two that probably won't kill the network > (CPU/network/whatever)", integrate it in a way that is easy to switch > at a later point, and deploy it. The important thing now is surely to get the protocol right so that we can slot algorithms in or out (then pick one or two that we actually want to integrate) -- lukep ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 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: 1. 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). 2. 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.) 3. 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 c
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 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 signature.asc Description: Digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Tue, 17 May 2016 17:49:46 + (UTC) lukep wrote: > > [snip] > > > In other words, I'd expect our future trust in Ring-LWE and SIDH > > > to evolve in different ways. And counting papers will not be > > > informative. > > > > Yeah probably. I can envision having no choice but to use SIDH > > sometime in the future (or vice versa). It's an evolving field, > > and my current mindset is "pick one or two that probably won't kill > > the network (CPU/network/whatever)", integrate it in a way that is > > easy to switch at a later point, and deploy it. > > The important thing now is surely to get the protocol right so that > we can slot algorithms in or out (then pick one or two that we > actually want to integrate) The relevant proposals here would be: https://gitweb.torproject.org/torspec.git/tree/proposals/264-subprotocol-versions.txt https://gitweb.torproject.org/torspec.git/tree/proposals/249-large-create-cells.txt With emphasis on the 264, since that's probably how link handshake crypto support will be signified. Regards, -- Yawning Angel pgpOdNERcXpjl.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Not sure if this has been noted before on this thread, but the BoringSSL team is working on something very similar: https://boringssl-review.googlesource.com/#/c/7962/ On Thu, May 19, 2016 at 1:01 PM Yawning Angel wrote: > On Tue, 17 May 2016 17:49:46 + (UTC) > lukep wrote: > > > [snip] > > > > In other words, I'd expect our future trust in Ring-LWE and SIDH > > > > to evolve in different ways. And counting papers will not be > > > > informative. > > > > > > Yeah probably. I can envision having no choice but to use SIDH > > > sometime in the future (or vice versa). It's an evolving field, > > > and my current mindset is "pick one or two that probably won't kill > > > the network (CPU/network/whatever)", integrate it in a way that is > > > easy to switch at a later point, and deploy it. > > > > The important thing now is surely to get the protocol right so that > > we can slot algorithms in or out (then pick one or two that we > > actually want to integrate) > > The relevant proposals here would be: > > > https://gitweb.torproject.org/torspec.git/tree/proposals/264-subprotocol-versions.txt > > https://gitweb.torproject.org/torspec.git/tree/proposals/249-large-create-cells.txt > > With emphasis on the 264, since that's probably how link handshake > crypto support will be signified. > > Regards, > > -- > Yawning Angel > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
On Thu, 19 May 2016 17:21:47 + Deirdre Connolly wrote: > Not sure if this has been noted before on this thread, but the > BoringSSL team is working on something very similar: > > https://boringssl-review.googlesource.com/#/c/7962/ Skimming the code: * The protocol level stuff is not useful at all because the sort of problems that need to be solved (or changes) with the Tor wire protocol for any sort of PQ handshake are rather different than "just adding another TLS key exchange mechanism". * Their hybrid construct is unauthenticated (handled separately by TLS, with a signature), and is `X25519SharedSecret | NHSharedSecret`, passed into a KDF. * They have their own special snowflake newhope variant (The code is based on the `ref` version, with Google copyrights bolted on top), functional changes are: * CTR-AES128 instead of SHAKE is used to sample `a` (same algorithm, doesn't have the sampling optimization or attempt to hide the rejection sampling timing variation). * SHA256 is used instead of SHA3-256 to generate `mu` from `nu`. * RAND_bytes() is called for noise sampling instead of using ChaCha20 or CTR-AES256. I don't find these changes to be particularly interesting. Any system where using AES-CTR like this makes sense will benefit more from using a vectorized NTT/reconciliation. Regards, -- Yawning Angel pgpUYdc4K8BFG.pgp Description: OpenPGP digital signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 wrote: > > > Not sure if this has been noted before on this thread, but the > > BoringSSL team is working on something very similar: > > > > https://boringssl-review.googlesource.com/#/c/7962/ > > Skimming the code: > > * The protocol level stuff is not useful at all because the sort of >problems that need to be solved (or changes) with the Tor >wire protocol for any sort of PQ handshake are rather different than >"just adding another TLS key exchange mechanism". > > * Their hybrid construct is unauthenticated (handled separately by TLS, >with a signature), and is `X25519SharedSecret | NHSharedSecret`, >passed into a KDF. > > * They have their own special snowflake newhope variant (The code is >based on the `ref` version, with Google copyrights bolted on top), >functional changes are: > > * CTR-AES128 instead of SHAKE is used to sample `a` (same > algorithm, doesn't have the sampling optimization or attempt to > hide the rejection sampling timing variation). > > * SHA256 is used instead of SHA3-256 to generate `mu` from `nu`. > > * RAND_bytes() is called for noise sampling instead of using > ChaCha20 or CTR-AES256. > > I don't find these changes to be particularly interesting. Any > system where using AES-CTR like this makes sense will benefit more > from using a vectorized NTT/reconciliation. > > Regards, > > -- > Yawning Angel > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
Peter Schwabe writes: > > isis wrote: > > Hi all, > > > Nope, it would still not work to fix the timing attack. Although, luckily, we > > already wrote some constant time code for my sorting-network idea, and then, > > with some coffee, Peter made it faster. (Give us something stronger to drink, > > and we'll probably come up with a way to get it even faster.) > > Still on coffee and with a size-84 Batcher sort and Yawning's 5q trick I > now have an AVX2 implementation of NewHope that is faster than the > original and does sampling of the polynomial a in constant time. Now I'm > up for some stronger drinks... > You may want to get more drinks in - there's a new eprint on IACR archive that's claiming a faster generation of 'a' using the 5q / 16 bit trick: https://eprint.iacr.org/2016/467.pdf The other change they make is to replace SHAKE by SHA-256 and AES-256 on the grounds that finding a backdoored 'a' would be implausible, although they no longer have the security reduction. Also they're not considering timing attacks. They get a speed-up of about 1.5x on AVX2. Personally I don't really care about not having the security reduction for 'a' (there's still the proof in the newhope paper for the rest of the key exchange). The bandwidth can be halved for n=512 vice n=1024 - this is the JarJar of NewHope - maybe dubious by itself but could be strong enough in hybrid with X25519 given that bandwidth is at a premium in Tor? -- lukep ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
lukep wrote: Hi lukep, hi all, > You may want to get more drinks in - there's a new eprint on IACR archive > that's claiming a faster generation of 'a' using the 5q / 16 bit trick: > https://eprint.iacr.org/2016/467.pdf I know, I have been in contact with the authors and I think that we will want to include some of their ideas in the final version of the NewHope paper (which has been accepted at USENIX! :-)). I also told them that they do not have to do the 4 conditional subtractions of q; apparently that comment hasn't made it into the eprint version. > The other change they make is to replace SHAKE by SHA-256 and AES-256 on the > grounds that finding a backdoored 'a' would be implausible, although they no > longer have the security reduction. Also they're not considering timing > attacks. > > They get a speed-up of about 1.5x on AVX2. Personally I don't really care > about not having the security reduction for 'a' (there's still the proof in > the newhope paper for the rest of the key exchange). An early version of our software was using something very similar and similarly fast (ChaCha20) until we agreed that the right thing to use is a XOF and pay for this with some performance penalty. As far as I know there is only one properly specified and analyzed XOF out there at the moment and that's SHAKE. We also considered a tree mode of SHAKE (which is faster), but decided against it to prioritize simplicity over some performance gain. I would be very happy to see more research into design and analysis of faster XOFs, and then I would totally support using them in NewHope, but my current impression is that there's more work to be done. > The bandwidth can be halved for n=512 vice n=1024 - this is the JarJar of > NewHope - maybe dubious by itself but could be strong enough in hybrid with > X25519 given that bandwidth is at a premium in Tor? There is a reason that it's called JarJar. Best regards, Peter signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 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. ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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) in this thread: - NTRU - NewHope - NTRUprime - McEliece - SIDH In some of the posts I got the impression that there are considerations for some sort of "algorithm agility" in the key exchange. This can mean two things: - runtime algorithm agility, such that a client can choose what algorithm to use according to some strategy; or - upgrading algorithm agility, which means that for each version number of a client, it is very clear which algorithm it will use, but the key exchange supports (easy) upgrading to better algorithms with increasing version numbers. In my opinion, the second approach is extremely important, in particular because at the moment we certainly want some sort of PQ key exchange, but are quite uncertain about what approach will prove best in the long run. I'm not really sure whether anybody really suggested the first approach, but just in case, I think it's a terrible idea. If the decision of what algorithms to use is left to users, they will certainly end up making worse choices than experts; if it's left to randomness, users inevitably get the worst out of the set from time to time. I simply cannot think of any strategy that lets the user win here. Now, out of the 5 proposals, my impression is that McEliece with binary Goppa codes has been killed as an idea for key exchange in Tor and that whenever somebody mentions it again, Isis will just shout "KEYSIZE" to make sure that it remains dead. I can see good reasons for each of the first three (lattice-based) proposals: - 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 SUPERCOP) are highly vulnerable to timing attacks. Key generation (with protection to against timing attacks) is, as far as I can tell, fairly expensive. - NewHope is explicitely designed for ephemeral key exchange (not public-key encryption), i.e, for the operation that is required. It offers best performance and, as Isis pointed out, the paramters we propose have the largest security margin against all known attacks. Disadvantage (price to pay for the security margin): somewhat longer messages. - NTRUprime is much less conservative than NewHope in its parameter choices against known attacks but offers "defenses" against attacks that may or may not work against NewHope and NTRU. The advertisement of those defenses is a pretty good job of the marketing department: the wording suggests that NTRUprime is, at the same bit-security level, at least as secure as NTRU or NewHope, but then has those defenses as additional safeguards. This is not quite true: NTRUprime operates in a different mathematical structure, which may in the long run prove more secure, it may also prove less secure and it could turn out that the "defenses" against hypothetical attacks turn out to be weaknesses against other attacks. Having said that, I really like the ideas of the NTRUprime paper and much more often than not have Dan and Tanja been right with their intuition for cryptographic design. What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in the context of key exchange). For NTRUprime there is not even a proposal for ephemeral key exchange as needed in Tor; however, I assume that it's not too hard to replace NTRU operations (from the NTRU proposal) by NTRUprime operations. Also (please correct me if I'm wrong), for NTRU it's not clear what parameters to use and there is no optimized and timing-attack protected implementation. Would it help the discussion at this point to fix NTRU parameters, produce an optimized implementation of NTRU (not production-quality code for Tor, but something to obtain benchmarks) and compare performance of NewHope, NTRU, and NTRUprime in an ephemeral key exchange? This would be a nice project for a Ph.D. student. Now, then there is SIDH: I really like SIDH, not so much for the shorter public keys (that's nice, but it's not like a difference of an order of magnitude), but because of two other reasons: 1.) It is a completely different approach and even if all non-standard lattice crypto falls, SIDH may survive. 2.) It's offering the same functionality as (EC)DH right now; both parties can compute their public keys without having received the public key of the other party. This is a great feature for protocol design and for migrating existing DH-based protocols to a post-quantum setting. However, I don't think that SIDH is ready for use at the moment. The reason is not only that it's about 300x slower than ECC, the reason is that security is really not u
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 SUPERCOP) are highly vulnerable > to timing attacks. Key generation (with protection to against timing > attacks) is, as far as I can tell, fairly expensive. We are working on a constant-time implementation of NTRU. We expect to release the source code this summer. However, as far as I know, timing attacks are much more powerful against encryption algorithm (that uses long-lived key for multiple times), rather than KEMs (use ephemeral keys). Our proposal treats NTRU as a KEM so I think the timing attack is not so useful. > What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in > the context of key exchange). Please see the attached for some benchmark results. We are working on the camera-ready version of the paper. The final version should be out soon. Also note that we are using an IND-CCA-2 secure version of NTRU. The performance can be further improved by switching to the IND-CPA secure version. IND-CPA is enough to provide channel security, provide that the ciphertext is accepted for only once for a given key. (This may open doors to some DoS attack.) As far as I can tell, the NewHope and NTRU-prime all uses CPA secure encryption algorithms. > Would it help the discussion at this point to fix NTRU parameters, produce > an optimized implementation of NTRU (not production-quality code for Tor, but > something to obtain benchmarks) and compare performance of NewHope, NTRU, and > NTRUprime in an ephemeral key exchange? This would be a nice project for a > Ph.D. student. It would be very interesting indeed. We need to fix the parameter sets for NTRU. Currently we have 1. ntru-443 with product form, providing 128 pre-quantum/post-quantum security 2. ntru-743 with product form, providing 256 pre-quantum and >128 post-quantum security 3. ntru-887 with non-product form, providing 256 pre-quantum security And all of those parameter sets uses SHA256 rather than SHA-3 as suggested by the community. It would be nice to have a final decision on a. shall we use non-production form b. shall we remove the IND-CCA-2 feature c. shall we use ntru-743/887 to build a sufficiently large margin just like NTRUprime Cheers, Zhenfei On Tue, May 24, 2016 at 6:32 PM, Peter Schwabe wrote: > 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) in this thread: > - NTRU > - NewHope > - NTRUprime > - McEliece > - SIDH > > In some of the posts I got the impression that there are considerations > for some sort of "algorithm agility" in the key exchange. This can mean > two things: > - runtime algorithm agility, such that a client can choose what > algorithm to use according to some strategy; or > - upgrading algorithm agility, which means that for each version number > of a client, it is very clear which algorithm it will use, but the key > exchange supports (easy) upgrading to better algorithms with > increasing version numbers. > > In my opinion, the second approach is extremely important, in particular > because at the moment we certainly want some sort of PQ key exchange, > but are quite uncertain about what approach will prove best in the long > run. > I'm not really sure whether anybody really suggested the first approach, > but just in case, I think it's a terrible idea. If the decision of what > algorithms to use is left to users, they will certainly end up making > worse choices than experts; if it's left to randomness, users inevitably > get the worst out of the set from time to time. I simply cannot think of > any strategy that lets the user win here. > > Now, out of the 5 proposals, my impression is that McEliece with binary > Goppa codes has been killed as an idea for key exchange in Tor and that > whenever somebody mentions it again, Isis will just shout "KEYSIZE" to > make sure that it remains dead. > > I can see good reasons for each of the first three (lattice-based) > proposals: > > - 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 SUPERCOP) are highly vulnerable > to timing attacks. Key generation (with protection to against timing > attacks) is, as far as I can tell, fairly expensive. > > - NewHope is explicitely designed for ephemeral key exchange (not > public-key encryption), i.e, for the operation that is required. It > offers best performance and, as Isis pointed out, the paramters we >
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, as far as I know, timing attacks are much more powerful > against encryption algorithm (that uses long-lived key for multiple > times), rather than KEMs (use ephemeral keys). Our proposal treats > NTRU as a KEM so I think the timing attack is not so useful. It's tricky; I agree that if you get only a single timing trace with the same key, it will be much harder to get useful information about the key than in a public-key encryption (or signature) setting where the private key is used many times. Then again, I also think that it will be very hard to prove that it's impossible to extract useful information about keys from timing on any platform. Maybe more importantly, Tor does not only have to be concerned about leaking the key, but also leaking de-anonymizing information. That's why Isis and I sat down and wrote a constant-time version of the sampling of the public polynomial in NewHope. My general take on this is that it's much easier to write constant-time code than to deal with the fallout caused by software that is vulnerable to timing attacks. > Please see the attached for some benchmark results. Did the attachment get lost? > We are working on the camera-ready version of the paper. The final > version should be out soon. Also note that we are using an IND-CCA-2 > secure version of NTRU. The performance can be further improved by > switching to the IND-CPA secure version. IND-CPA is enough to provide > channel security, provide that the ciphertext is accepted for only > once for a given key. (This may open doors to some DoS attack.) As far > as I can tell, the NewHope and NTRU-prime all uses CPA secure > encryption algorithms. Definitely true for NewHope. Here's what my answers would be to your questions: > It would be nice to have a final decision on > a. shall we use non-production form Would be interesting to see benchmarks of both. > b. shall we remove the IND-CCA-2 feature Again, it would be interesting in a larger context to have benchmarks of both; the Tor handshake should be fine with IND-CPA. > c. shall we use ntru-743/887 to build a sufficiently large margin just like > NTRUprime Definitely. As I wrote in my previous mail, in NewHope we went for a much larger margin than NTRUprime did; I would probably feel better with 887, but for long-term security (and this is what the whole thing is about), 743 is a must-have. Cheers, Peter signature.asc Description: PGP signature ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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 ready in a couple of days. The data are based on ntru-443 with CCA-2. By moving to CPA, we may be able to save say 30% of computation. The ntru-743 is roughly 2.5x slower than ntru-443. Cheers, Zhenfei On Thu, May 26, 2016 at 1:35 AM, Peter Schwabe wrote: > 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, as far as I know, timing attacks are much more powerful > > against encryption algorithm (that uses long-lived key for multiple > > times), rather than KEMs (use ephemeral keys). Our proposal treats > > NTRU as a KEM so I think the timing attack is not so useful. > > It's tricky; I agree that if you get only a single timing trace with the > same key, it will be much harder to get useful information about the > key than in a public-key encryption (or signature) setting where the > private key is used many times. Then again, I also think that it will be > very hard to prove that it's impossible to extract useful information > about keys from timing on any platform. > Maybe more importantly, Tor does not only have to be concerned about > leaking the key, but also leaking de-anonymizing information. That's why > Isis and I sat down and wrote a constant-time version of the sampling of > the public polynomial in NewHope. > My general take on this is that it's much easier to write constant-time > code than to deal with the fallout caused by software that is vulnerable > to timing attacks. > > > Please see the attached for some benchmark results. > > Did the attachment get lost? > > > We are working on the camera-ready version of the paper. The final > > version should be out soon. Also note that we are using an IND-CCA-2 > > secure version of NTRU. The performance can be further improved by > > switching to the IND-CPA secure version. IND-CPA is enough to provide > > channel security, provide that the ciphertext is accepted for only > > once for a given key. (This may open doors to some DoS attack.) As far > > as I can tell, the NewHope and NTRU-prime all uses CPA secure > > encryption algorithms. > > Definitely true for NewHope. > > > Here's what my answers would be to your questions: > > > It would be nice to have a final decision on > > a. shall we use non-production form > > Would be interesting to see benchmarks of both. > > > b. shall we remove the IND-CCA-2 feature > > Again, it would be interesting in a larger context to have benchmarks of > both; the Tor handshake should be fine with IND-CPA. > > > c. shall we use ntru-743/887 to build a sufficiently large margin just > like > > NTRUprime > > Definitely. As I wrote in my previous mail, in NewHope we went for a > much larger margin than NTRUprime did; I would probably feel better with > 887, but for long-term security (and this is what the whole thing is > about), 743 is a must-have. > > > Cheers, > > Peter > > ___ > tor-dev mailing list > tor-dev@lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > > ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
