linux-kernel - Re: [PATCH] random: add blocking facility to urandom

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <11721.1315846699@turing-police.cc.vt.edu>
Date:	Mon, 12 Sep 2011 12:58:19 -0400
From:	Valdis.Kletnieks@...edu
To:	Jarod Wilson <jarod@...hat.com>
Cc:	Sandy Harris <sandyinchina@...il.com>,
	Steve Grubb <sgrubb@...hat.com>,
	Neil Horman <nhorman@...hat.com>,
	Tomas Mraz <tmraz@...hat.com>,
	Sasha Levin <levinsasha928@...il.com>,
	"Ted Ts'o" <tytso@....edu>, linux-crypto@...r.kernel.org,
	Matt Mackall <mpm@...enic.com>,
	Herbert Xu <herbert.xu@...hat.com>,
	Stephan Mueller <stephan.mueller@...ec.com>,
	lkml <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] random: add blocking facility to urandom

On Mon, 12 Sep 2011 09:55:15 EDT, Jarod Wilson said:

> Well, previously, we were looking at simply improving random entropy 
> contributions, but quoting Matt Mackall from here:
> 
> http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg05799.html
> 
> 'I recommend you do some Google searches for "ssl timing attack" and 
> "aes timing attack" to get a feel for the kind of seemingly impossible 
> things that can be done and thereby recalibrate your scale of the 
> impossible.'

If you're referring to Dan Bernstein's 2005 paper on AES timing attacks
(http://cr.yp.to/antiforgery/cachetiming-20050414.pdf), note that it took
him on the order of 2*25 packets per byte of AES key - targeting a
dummy server intentionally designed to minimize noise.  Although he
correctly notes: 

     Of course, I wrote this server to minimize the amount of noise in the timings
  available to the client. However, adding noise does not stop the attack: the client
  simply averages over a larger number of samples, as in [7]. In particular, reducing
  the precision of the server's timestamps, or eliminating them from the server's
  responses, does not stop the attack: the client simply uses round-trip timings
  based on its local clock, and compensates for the increased noise by averaging
  over a larger number of samples.

one has to remember that he's measuring average differences in processing
time on the order of single-digits of cycles - if any *real* processing was happening
it would only take a few cache line misses or an 'if' statement branching the
other way to almost totally drown out the AES computation.  (Personally,
I'm amazed that FreeBSD 4.8's kernel is predictable enough to do these
measurements - probably helps a *lot* that the server was otherwise idle -
if somebody else was getting a timeslice in between it would totally swamp
the numbers).

Dan's reference [7] mentions specifically that RSA blinding (first implemented
by default all the way back in OpenSSL 0.9.7b) defeats that paper's timing
attack.

If anything, those attacks are the best proof possible that the suggested
"fix" for /dev/urandom is a fool's errand - why would anybody bother trying to
figure out what the "next" data out of /dev/urandom is, when they can simply
wait for a few milliseconds and extract it out of whatever program read it? :)

Content of type "application/pgp-signature" skipped