Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S1752893Ab3IMS7p (ORCPT <rfc822;w@1wt.eu>);
	Fri, 13 Sep 2013 14:59:45 -0400
Received: from imap.thunk.org ([74.207.234.97]:59794 "EHLO imap.thunk.org"
	rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP
	id S1751726Ab3IMS7o (ORCPT <rfc822;linux-kernel@vger.kernel.org>);
	Fri, 13 Sep 2013 14:59:44 -0400
Date: Fri, 13 Sep 2013 14:59:31 -0400
From: "Theodore Ts'o" <tytso@mit.edu>
To: Stephan Mueller <smueller@chronox.de>
Cc: =?iso-8859-1?Q?J=F6rn?= Engel <joern@logfs.org>,
        John Stultz <john.stultz@linaro.org>,
        LKML <linux-kernel@vger.kernel.org>, dave.taht@bufferbloat.net,
        Frederic Weisbecker <fweisbec@gmail.com>,
        Thomas Gleixner <tglx@linutronix.de>
Subject: Re: [PATCH] /dev/random: Insufficient of entropy on many
 architectures
Message-ID: <20130913185931.GB15366@thunk.org>
Mail-Followup-To: Theodore Ts'o <tytso@mit.edu>,
	Stephan Mueller <smueller@chronox.de>,
	=?iso-8859-1?Q?J=F6rn?= Engel <joern@logfs.org>,
	John Stultz <john.stultz@linaro.org>,
	LKML <linux-kernel@vger.kernel.org>, dave.taht@bufferbloat.net,
	Frederic Weisbecker <fweisbec@gmail.com>,
	Thomas Gleixner <tglx@linutronix.de>
References: <10005394.BRCyBMYWy3@tauon>
 <522F984C.2070909@linaro.org>
 <20130912213148.GE3809@logfs.org>
 <1974157.PE35U8AyTG@tauon>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1974157.PE35U8AyTG@tauon>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Mail-From: tytso@thunk.org
X-SA-Exim-Scanned: No (on imap.thunk.org); SAEximRunCond expanded to false
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 2887
Lines: 57

On Fri, Sep 13, 2013 at 07:36:20AM +0200, Stephan Mueller wrote:
> 
> And here the RNG theory breaks: a whitening function (crypto function) 
> like the used SHA1 does not add entropy. Thus, the SHA1 just spreads out 
> the entropy evenly over the output buffer. As entropy can be considered 
> as a kind of percentage value, if you have, say, 10% of your input 
> buffer holding entropy, applying a whitening function, you output buffer 
> still holds 10% of entropy only.

Well..... it's a little bit more complicated than that.  What you're
saying is aboslutely true for normal entropy that we might gather.
For example, if a disk read might take 11, 12, or 13 milliseconds
depending on the chaotic air currents affecting how much times it
takes to do a read, you have at best 1.5 bits of entropy.  So if the
NSA knows that during a standard boot sequences, you will be doing a
certain precise set of reads, it can try all of the different
possibilities of 11/12/13 ms and try to brute force what might be
generated by the RNG.

This is the source of my recommendation that embedded devices should
wait as long as possible before generating things like ssh host keys.
The longer you wait, more uncertainty will be added to the entropy
pool, and the harder it will be for an attacker to try to brute-force
attack the /dev/random output.

However, if you are worried about a malicious entropy source, things
are a little bit different.  Suppose RDRAND == AES(i++, NSA_KEY),
where the NSA doesn't know the starting value of i.  But if it get can
get a raw RDRAND value (say, someone uses it without doing any
whitening as a session key or as a D-H parameter), it can decrypt the
output using the NSA_KEY, and then now that it knows i, it can brute
force break the RDRAND output, even if it's not entirely sure how many
times RDRAND has been called between that cleanb RDRAND value and the
RDRAND output it is trying to break.

In *this* case, smearing out the value of RDRAND across the entropy
pool does help, becuase it makes it significantly harder to get a
clean RDRAND value to decrypt.


That being said, the much bigger problem that I'm worried about is not
necessarily a trojan'ed RDRAND, but rather on embedded ARM and MIPS
devices where we have unsufficient entropy, and on the first boot out
of the box, there is no random seed file that can be fixed in at boot
time.  Mixing in personalization information (serial numbers, MAC
addresses) which *hopefully* the NSA wouldn't know in the case of
pervasive, bulk surveillance, is a bit of a help.  But it's certainly
no help against a direct, targetted attack.

Regards,

						- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/