[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope
isis
isis at torproject.org
Sun May 8 10:23:05 UTC 2016
Jeff Burdges transcribed 3.1K bytes:
> 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.
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160508/851ca2a1/attachment.sig>
More information about the tor-dev
mailing list