/dev/random and /dev/psaux: too much entropy assumed?
Florian Weimer
/dev/random, and, after that, reads byte by byte from /dev/random and
counts the total number of interrupts occurred (summing up the second
column in /proc/interrupts) until a timeout occurs, I obtained the
following interesting results:
First run: single-user mode, no activity during the sampling phase:
Sampling time: 15.006219 (in seconds)
Interrupts: 1501
Random bits: 0
(The 1501 interrupts are probably timer interrupts.)
Second run: single-user mode, cat < /dev/psaux > /dev/null was running
in the background, I kept moving the mouse during the sampling phase:
Sampling time: 15.000942
Interrupts: 5931
Random bits: 40216
After subtracting the timer interrupts, we get an average of over
nine bits added on each /dev/psaux interrupt to the /dev/random pool.
I don't think that there is that much entropy involved to justify this
high value.
The same might be the case for other interrupts, but I haven't looked
at them.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majo...@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
C. Scott Ananian
> After subtracting the timer interrupts, we get an average of over
> nine bits added on each /dev/psaux interrupt to the /dev/random pool.
> I don't think that there is that much entropy involved to justify this
> high value.
How many bits would you propose? Remember you've got several sources of
randomness here:
1) time between mouse events (in processor cycles, usually)
2) x delta
3) y delta
4) button status
Nine bits doesn't seem all that unreasonable to me. And if you care, why
not distill it further. The techniques used to make very random numbers
out of partially random numbers are well known.
Speaking personally, I would like to see much more analysis of the sources
of mouse randomness and the number of bits you think we can "reasonably"
extract from these before you start throwing stones. Note that the kernel
sources are open, so all the algorithms are in plain view. In particular,
the algorithm used to calculate how many bits of 'true' randomness we're
getting for each parcel of information added to the pot is in
linux/drivers/char/random.c, and takes into account first and second order
deltas to more accurately respond to how 'random' your input source
currently is. I suspect during your test you were tossing the mouse
around quite randomly, leading to a greater amount of entropy added to the
pot than if you observed more 'natural' conditions with smaller mouse
movements.
--s
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cana...@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
SEAL Team 6 quiche struggle cracking assassination Sudan Noriega KGB
Ft. Bragg Ortega Honduras Serbian Hawk DES nuclear fissionable UKUSA
Theodore Y. Ts'o
Date: 30 May 1999 19:43:47 +0200
After subtracting the timer interrupts, we get an average of over
nine bits added on each /dev/psaux interrupt to the /dev/random pool.
I don't think that there is that much entropy involved to justify this
high value.
The entropy estimation is based on the jitter in the timestamp clock for
the interrupts. The dx,dy values from the mouse are folded into the
entropy pool along with the timestamp information, but it's only the
first, second, and third order derivitives of the timestamp which are
used in estimating the entropy.
What can influence the time that the interrupt comes in? A lot of
things, including when/if the kernel has interrupts disabled, to how
quickly or slowly the mouse is being moved around.
- Ted
Florian Weimer
> On 30 May 1999, Florian Weimer wrote:
>
> > After subtracting the timer interrupts, we get an average of over
> > nine bits added on each /dev/psaux interrupt to the /dev/random pool.
> > I don't think that there is that much entropy involved to justify this
> > high value.
>
> How many bits would you propose? Remember you've got several sources of
> randomness here:
> 1) time between mouse events (in processor cycles, usually)
> 2) x delta
> 3) y delta
> 4) button status
I'm terribly sorry but I missed sources 2 to 4 (and the parameter to
add_timer_randomness). In addition, I have grossly underestimated the
cycle clock speed of today's machines. :(((
> I suspect during your test you were tossing the mouse around quite
> randomly, leading to a greater amount of entropy added to the pot than
> if you observed more 'natural' conditions with smaller mouse
> movements.
Yes, I did. But this shouldn't influence the results, because the data
parameter in add_timer_randomness is not used for entropy estimation.
I would certainly like to end the thread after this, but I've got one
further question: The implementation of /dev/random assumes that the
output of the SHA-1 hash function is random for random (or almost random)
input. Neither the people on sci.crypt nor I know of any analysis
of SHA-1 in this direction (which doesn't prove anything of course).
Are there any particular reasons why SHA-1 was chosen to supersede MD5?
(It might indeed become practical to find collisions for MD5 soon,
but this doesn't mean that MD5 is not suitable for applications like
/dev/random.)
C. Scott Ananian
> I would certainly like to end the thread after this, but I've got one
> further question: The implementation of /dev/random assumes that the
> output of the SHA-1 hash function is random for random (or almost random)
> input. Neither the people on sci.crypt nor I know of any analysis
> of SHA-1 in this direction (which doesn't prove anything of course).
> Are there any particular reasons why SHA-1 was chosen to supersede MD5?
> (It might indeed become practical to find collisions for MD5 soon,
> but this doesn't mean that MD5 is not suitable for applications like
> /dev/random.)
Patent issues, I strongly suspect. And most of the applications for
/dev/random don't actually require 'uniformly distributed' output (which
is my guess as to what you mean by 'random'); rather they require
'unguessable' output. SHA-1, being a strong one-way function, provides
unguessable output.
--s
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cana...@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
ammunition kibo IDEA genetic Sigint FBI jihad Indonesia Waco, Texas
Panama BATF Honduras domestic disruption Nazi strategic supercomputer
David Whysong
>On 1 Jun 1999, Florian Weimer wrote:
>
>> I would certainly like to end the thread after this, but I've got one
>> further question: The implementation of /dev/random assumes that the
>> output of the SHA-1 hash function is random for random (or almost random)
>> input. Neither the people on sci.crypt nor I know of any analysis
>> of SHA-1 in this direction (which doesn't prove anything of course).
>> Are there any particular reasons why SHA-1 was chosen to supersede MD5?
>> (It might indeed become practical to find collisions for MD5 soon,
>> but this doesn't mean that MD5 is not suitable for applications like
>> /dev/random.)
>
>Patent issues, I strongly suspect. And most of the applications for
>/dev/random don't actually require 'uniformly distributed' output (which
>is my guess as to what you mean by 'random'); rather they require
>'unguessable' output. SHA-1, being a strong one-way function, provides
>unguessable output.
> --s
What? /dev/random not uniform? You've got to be kidding!
I use /dev/random a great deal in setting up large n-body simulations,
which requires a very uniform distribution of numbers (huge monte-carlo
methods, srand() probably isn't good enough). If it doesn't have
'uniformly distributed' output, it really isn't random and I'd like to
know about that...
I did run some simple tests at one time and it looked uniform. But those
were pretty silly tests (i.e. make a million numbers in [0,1] and plot a
histogram).
Dave
David Whysong dwhy...@physics.ucsb.edu
Astrophysics graduate student University of California, Santa Barbara
My public PGP keys are on my web page - http://www.physics.ucsb.edu/~dwhysong
DSS PGP Key 0x903F5BD6 : FE78 91FE 4508 106F 7C88 1706 B792 6995 903F 5BD6
D-H PGP key 0x5DAB0F91 : BC33 0F36 FCCD E72C 441F 663A 72ED 7FB7 5DAB 0F91
C. Scott Ananian
> On Tue, 1 Jun 1999, C. Scott Ananian wrote:
> >On 1 Jun 1999, Florian Weimer wrote:
> >> further question: The implementation of /dev/random assumes that the
> >> output of the SHA-1 hash function is random for random (or almost random)
> >> input. Neither the people on sci.crypt nor I know of any analysis
> >> of SHA-1 in this direction (which doesn't prove anything of course).
[...]
> >Patent issues, I strongly suspect. And most of the applications for
> >/dev/random don't actually require 'uniformly distributed' output (which
> >is my guess as to what you mean by 'random'); rather they require
> >'unguessable' output. SHA-1, being a strong one-way function, provides
> >unguessable output.
[...]
> What? /dev/random not uniform? You've got to be kidding!
Careful, I didn't quite say that. The original poster said "he didn't
know of any analysis of SHA-1" and I said "it probably doesn't matter".
Neither of us are claiming that SHA-1 isn't uniform.
I personally doubt that you'll find any *specific* proofs that SHA-1 is
uniform because I believe that there are *general* proofs relating
security to uniformity, and then *specific* proofs of certain security
properities to SHA-1. The cryptography community generally has a much
higher standard of proof than the statistical community, and I would be
very very surprised indeed to find a *secure* algorithm that was *not*
statistically random. On the other hand, there are many uniformly random
sources that are not secure.
--s
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cana...@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
Serbian PLO quiche AES Shoal Bay NORAD Albanian bomb Japan nuclear
radar AK-47 SEAL Team 6 spy Soviet Semtex Hager fissionable Qaddafi
C. Scott Ananian
matter for /dev/random. The uses the kernel has for random numbers
require unguessability, and /dev/random supplies this. If you need some
other property in user-space, it is *your* responsibility to verify that
/dev/random supplies this, not the kernel's. Repeatability, for example,
is often considered a virtue for simulation uses. The kernel doesn't
supply a *repeatable* random number stream, nor should it ever be required
to.
--s
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cana...@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
CIA FSF AES North Korea jihad Honduras Sabana Seca Semtex Ortega $400 million in gold bullion
David Whysong
>and, btw, I stand by my assertion that statistical uniformity doesn't
>matter for /dev/random. The uses the kernel has for random numbers
>require unguessability, and /dev/random supplies this. If you need some
>other property in user-space, it is *your* responsibility to verify that
>/dev/random supplies this, not the kernel's. Repeatability, for example,
>is often considered a virtue for simulation uses. The kernel doesn't
>supply a *repeatable* random number stream, nor should it ever be required
>to.
> --s
I have to disagree strongly...
A stream of n bits from /dev/random should not be repeatable with any
frequency greater than 1 in 2^n, but it definately should be uniformly
distributed. Otherwise the numbers aren't really random, and therefore
they aren't useful for any purpose I can think of -- certainly not monte
carlo integration or anything else that uses "random" numbers, and not for
cryptographic applications.
Dave
David Whysong dwhy...@physics.ucsb.edu
Astrophysics graduate student University of California, Santa Barbara
My public PGP keys are on my web page - http://www.physics.ucsb.edu/~dwhysong
DSS PGP Key 0x903F5BD6 : FE78 91FE 4508 106F 7C88 1706 B792 6995 903F 5BD6
D-H PGP key 0x5DAB0F91 : BC33 0F36 FCCD E72C 441F 663A 72ED 7FB7 5DAB 0F91
C. Scott Ananian
> A stream of n bits from /dev/random should not be repeatable with any
> frequency greater than 1 in 2^n, but it definately should be uniformly
> distributed. Otherwise the numbers aren't really random, and therefore
> they aren't useful for any purpose I can think of -- certainly not monte
> carlo integration or anything else that uses "random" numbers, and not for
> cryptographic applications.
ok, ok, this is all going nowhere. as has been pointed out to me
`multiple times, it is *not possible* to have 'unguessable' numbers that
*aren't* uniformly distributed. because if they're not 'statistically
random' you can guess them. right? we all know that.
my point was more subtle: it is your responsibility to verify that the
uses you put /dev/random to are appropriate. monte-carlo integration and
n-body simulations are *not* kernel issues and thus *not* appropriate for
linux-kernel. attacks on tcp sequence numbers *are* kernel issues, but no
one has ever claimed that statistical uniformity was relevant here.
--s
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cana...@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
KGB Rule Psix Albanian FSF atomic [Hello to all my fans in domestic surveillance]
Suharto PLO blowfish Cocaine quiche Ortega Waihopai Hawk Clinton Uzi
Damien Miller
> my point was more subtle: it is your responsibility to verify that the
> uses you put /dev/random to are appropriate. monte-carlo integration and
> n-body simulations are *not* kernel issues and thus *not* appropriate for
> linux-kernel. attacks on tcp sequence numbers *are* kernel issues, but no
> one has ever claimed that statistical uniformity was relevant here.
It is relevant:
from drivers/char/random.c:
* This routine gathers environmental noise from device drivers, etc.,
* and returns good random numbers, suitable for cryptographic use.
* Besides the obvious cryptographic uses, these numbers are also good
* for seeding TCP sequence numbers, and other places where it is
* desirable to have numbers which are not only random, but hard to
* predict by an attacker.
and
* The two other interfaces are two character devices /dev/random and
* /dev/urandom. /dev/random is suitable for use when very high
* quality randomness is desired (for example, for key generation or
* one-time pads), as it will only return a maximum of the number of
/dev/random is explicitly designed for use by user-space cryptography
software. If its collection and entrophy estimation is erroneous then
it is a bug which should be fixed where it happens - in the driver.
Regards,
Damien Miller
--
| "Bombay is 250ms from New York in the new world order" - Alan Cox
| Damien Miller - http://www.ilogic.com.au/~dmiller
| Email: dmi...@ilogic.com.au (home) -or- dam...@ibs.com.au (work)