[21527] in cryptography@c2.net mail archive
Re: Linux RNG paper
daemon@ATHENA.MIT.EDU (Travis H.)
Thu Mar 23 09:27:25 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 23 Mar 2006 01:55:30 -0600
From: "Travis H." <solinym@gmail.com>
To: "Heyman, Michael" <Michael.Heyman@sparta.com>
Cc: cryptography@metzdowd.com, zvikag@cs.huji.ac.il,
benny@cs.haifa.ac.il
In-Reply-To: <5ABE30CE099A524CBF95C715D37BCACC1A14D1@nemo.columbia.ads.sparta.com>
I have examined the LRNG paper and have a few comments.
CC'd to the authors so mind the followups.
1) In the paper, he mentions that the state file could be altered by
an attacker, and then he'd know the state when it first came up. Of
course, if he could do that, he could simply install a trojan in the
OS itself, so this is not really that much of a concern. If your hard
drives might be altered by malicious parties, you should be using some
kind of cryptographic integrity check on the contents before using
them. This often comes for free when encrypting the contents.
2) His objection against using keyboard data is perhaps just an
indication that reseeding of the pool should occur with sufficient
entropy that the values cannot efficiently be guessed via brute force
search and forward operation of the PRNG. If the reseeding is of
insufficient to deter brute force input space search, other bad things
can happen. For example, in the next paragraph the author mentions
that random events may reseed the secondary pool directly if the
primary pool is full. If an attacker were to learn the contents of
the secondary pool, he could guess the incremental updates to its
contents and compare results with the real PRNG, resulting in an
incremental state-tracking attack breaking backward security until a
reseed from the primary is generated (which appears to have a minimum
of 8 bytes, also perhaps too low). The answer is more input, not
less.
It's annoying that the random number generator code calls the
unpredictable stuff entropy. It's unpredictability that we're
concerned with, and Shannon entropy is just an upper bound on the
predictability. Unpredictability cannot be measured based on outputs
of sources, it must be based on models of the source and attacker
themselves. But we all know that. Maybe we should invent a term?=20
Untropy?
And now a random(3) tangent:
While we're on the subject of randomness, I was hoping that random(3)
used the old (TYPE_0) implementation by default... lots of DoS tools
use it to fill spoofed packet fields, and one 32-bit output defines
the entire state of the generator --- meaning that I could distinguish
DoS packets which had at least 32 bits of state in them from other
packets. However, it appears that Linux and BSD both use a TYPE_3
pool, which makes such simple techniques invalid, and would probably
require identification of a packet stream, instead of testing packets
one by one. Since use of a real pool has put it beyond my interest
and perhaps my ability, I'm giving the idea away. Email me if you
find a really good use for PRNG analysis of this sort.
For a TYPE_0 generator, the equation is:
i' =3D (i * 1103515245 + 12345) & 0x7fffffff
As far as low-hanging fruit goes, the higher generator types still
never set the highest order bit (RAND_MAX is 0x7fffffff), and the
outputs are unaltered pool contents.
--
Security Guru for Hire http://www.lightconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
