On Sat, May 7, 2016 at 12:41 PM, lukep lukep@tutanota.com wrote:
Jeff Burdges <burdges@...> writes:
On Fri, 2016-05-06 at 19:17 +0000, 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