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

[isis]

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>