RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

[Christoph Anton Mitterer]

Hi.

This is a question towards the crypto/entropy experts.

When seeding the kernels entropy cache (which is then ultimately used
for /dev/random), e.g. by (semi-)TRNGs like haveged[0],
audio-entropyd[1], Simtec’s Entropy Key[2] or friends... can one spoil
the randomness by that or is this impossible by design?

Of course it's easy to check the distribution of these randomness
sources, but as we see on the plain Mersenne Twister, a "perfect"
distribution is not necessarily usable for cryptography.


Further, one could imagine that closed products like the Entropy Key are
hacked or have backdoors, which may make them produce subtle patterns
that could later be used in cryptoanalysis.
(This is in no way a claim, that Simtec would do this,... just an
example.)


Cheers,
Chris.



[0] http://www.issihosts.com/haveged/
[1] http://www.vanheusden.com/aed/
[2] http://www.entropykey.co.uk/

Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

[Theodore Ts'o]

On Thu, Oct 04, 2012 at 03:32:35PM +0200, Christoph Anton Mitterer wrote:
> 
> When seeding the kernels entropy cache (which is then ultimately used
> for /dev/random), e.g. by (semi-)TRNGs like haveged[0],
> audio-entropyd[1], Simtec’s Entropy Key[2] or friends... can one spoil
> the randomness by that or is this impossible by design?

It is impossible by design.  Or specifically, /dev/random was designed
so that it can be world-writeable, and an attacker can feed in any
kind of input he or she wants, and it will not allow the attacker to
know anything more about the state of the entropy pool than he or she
knew before they started mixing inputs in.

There are comments that go into more detail about the design in
drivers/char/random.c.  Credit for the design goes to Colin Plumb, who
designed RNG in the original PGP 2.x implementation, BTW.

	     	    	     	 	  - Ted

Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

[Christoph Anton Mitterer]

[-- Attachment #1: Type: text/plain, Size: 2051 bytes --]

Hi Ted.


Thanks for your prompt reply.


On Thu, 2012-10-04 at 18:49 -0400, Theodore Ts'o wrote:
> It is impossible by design.  Or specifically, /dev/random was designed
> so that it can be world-writeable, and an attacker can feed in any
> kind of input he or she wants, and it will not allow the attacker to
> know anything more about the state of the entropy pool than he or she
> knew before they started mixing inputs in.

I just wondered because I remembered David Shaw (one of the main
developers from gpg) to imply[0] some time ago, that an "evil" entropy
source would actually be a problem:
> Not completely useless given the Linux random design, but
> certainly an evil source of entropy would be a serious problem.  "



> There are comments that go into more detail about the design in
> drivers/char/random.c.
I had a short glance at it,... but I guess it goes a bit above my
understanding of entropy theory... well at least without without putting
some effort into it.

Some notes though (guess you're the maintainer anyway):
1) With respect to the sources of entropy... would it make sense for the
kernel to follow ideas from haveged[1].
I mean we all now that especially disk-less server systems have problems
with the current sources.
Or is that intended to be kept in userspace?

2) At some places, the documentation mentiones that SHA is used... any
sense in "upgrading" to stronger/more secure (especially as it says the
hash is used to protect the internal state of the pool) and faster
algos?

3) Some places note that things are not so cryptographically strong...
which sounds a bit worrying...

4) Were "newer" developments in PRNGs already taken into account? E.g.
the Mersenne Twister (which is AFAIK however not cryptographically
secure; at least in it's native form)


Thanks again,
Chris.


[0]
http://lists.gnupg.org/pipermail/gnupg-users/2009-September/037301.html
[1] http://www.issihosts.com/haveged/
[2] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5450 bytes --]

Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

[Theodore Ts'o]

On Mon, Oct 08, 2012 at 02:41:31AM +0200, Christoph Anton Mitterer wrote:
> I just wondered because I remembered David Shaw (one of the main
> developers from gpg) to imply[0] some time ago, that an "evil" entropy
> source would actually be a problem:

I've looked at his message, I didn't see any justification for his
concern/assertion.  So I can't really comment on it since he didn't
give any reason for his belief.

> Some notes though (guess you're the maintainer anyway):
> 1) With respect to the sources of entropy... would it make sense for the
> kernel to follow ideas from haveged[1].
> I mean we all now that especially disk-less server systems have problems
> with the current sources.
> Or is that intended to be kept in userspace?

We've made a lot of changes in how we gather entropy recently, so that
we're gathering a lot more entropy even on disk-less server systems.
We are using the time stamp counter, so in some ways we are using a
scheme which isn't that far off from haveged.  Historically,
/dev/random was created back before high resolution counters were not
always available on all CPU's, and so we depended on interrupts being
unpredictable.  What haveged does instead is to depend on cycle
counters, and count on some amount of uncertainty to cause differences
in the expected cycle counter when performing a known fixed workload.
What we are now doing is depending on the cycle counter on interrupts
which are will be at least as unpredictable and probably more so, than
haveged's fixed workload.

That's because we have an avantage of having access to the interrupt
timing information, which is something haveged doesn't have, since it
is a userspace solution.  So I think what we have right now in
/dev/random is better than what haveged has as a userspace-only
collection algorithm.

> 2) At some places, the documentation mentiones that SHA is used... any
> sense in "upgrading" to stronger/more secure (especially as it says the
> hash is used to protect the internal state of the pool) and faster
> algos?

We're not using SHA has a traditional cryptographic hash; so the
weaknesses caused by being able to find collisions in somewhat faster
than brute force aren't a problem.  We are hashing 4k bits of input to
produce 80 bits of output (we take the 160 bits output of SHA-1 and
xor them togethre to fold what we expose to the outside world to only
80 bits).  So there will always be collisions --- the pigeon hole
princple states that with 2**4096 possible inputs, and only 2**80
possible outputs, there will be definitely be collisions where
multiple inputs result in the same hash.  The trick is being able to
find all of the possible collisions --- and then being able to figure
out which one was really the one that represents the state of the
entropy pool at a particular point in time.  This is a very different
sort of analysis than simply being able to find two known inputs that
result in the same output.

So I'm not particularly worried at this point.  The other thing to
note is that the possible alternatives to SHA-1 (i.e., SHA-2 and
SHA-3) are actually slower, not faster.  So we would be giving up
performance if we were to use them.

> 3) Some places note that things are not so cryptographically strong...
> which sounds a bit worrying...

There is a specific tradeoff going in these places.  For example,
there are certain TCP hijacking attacks where so long as we can
prevent the attacker from being able to guess the next TCP sequence
number in less than say, five or ten minutes, we are fine.  We don't
need to protect this "secret" for more than a very limited amount of
time.  In addiiton, networking performance is very important.  If it
took several seconds to establish a TCP conneciton --- that would be
bad; consider what that would do for a web server!

The bottom line is that strength is not the only thing that we have to
engineer for.  If we did that for airplanes, for example, they would
never fly or require so much fuel as to be economically impractical.
Good engineering is to understand what strength is require, adding a
appropriate safety margin, and then saying, *enough*.

> 4) Were "newer" developments in PRNGs already taken into account? E.g.
> the Mersenne Twister (which is AFAIK however not cryptographically
> secure; at least in it's native form)

The problems solved by the Mersenne Twister are quite different from
the problems we are trying to solve in a cryptographic random number
generator.  PRNG's and CRNG's are very different animals.  You might
as well ask a basketball coach if they have taken into account the
latest scocer strategies...

					- Ted

Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs

[Christoph Anton Mitterer]

[-- Attachment #1: Type: text/plain, Size: 1483 bytes --]

On Sun, 2012-10-07 at 21:24 -0400, Theodore Ts'o wrote:
> I've looked at his message, I didn't see any justification for his
> concern/assertion.  So I can't really comment on it since he didn't
> give any reason for his belief.
I asked him again[0] to be sure and he replied to have no reason to
believe it's possible to spoil it.



> We've made a lot of changes in how we gather entropy recently
>...
I see,.. I guess this was in 3.6 then? Cause I made some tests with 3.5
and there (even on my desktop) available entropy is always rather
low ... but with haveged it quickly falls and rises (that actually
puzzles me) between 4096  and ~1k



> We're not using SHA has a traditional cryptographic hash
>...
Of course :) Thanks for the good explanation of the operation though!


> So I'm not particularly worried at this point.  The other thing to
> note is that the possible alternatives to SHA-1 (i.e., SHA-2 and
> SHA-3) are actually slower, not faster.  So we would be giving up
> performance if we were to use them.
I rather meant some other fast algos, e.g. those from the SHA3
competition which seem to be faster than SHA1.
Haven't measured myself but just took:
http://arctic.org/~dean/crypto/sha-sse2-20041218.txt
http://skein-hash.info/sha3-engineering
Well it's perhaps rather minor...


Thanks anyway for all your information :)


Cheers,
Chris.



[0]
http://lists.gnupg.org/pipermail/gnupg-users/2012-October/045551.html

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5450 bytes --]