12

It seems (to a non-expert) that /dev/random is acclaimed to be useable as a source of pure random data. However, I am curious as to the analysis of the file /dev/random.

/dev/random is a collection point of noisy data from hardware. The file is expanded as more noise is gathered from hardware; as new noise is added, the old data is shifted around so that the file as a whole represents a sort of source of entropy.

I will assume that /dev/random will be used only once to avoid issues arising from reusing a one time pad. Then there is one thing bugging meーhow the entropy is estimated. I am less interested in the answers to the following questions themselves, and more interested in whether past research has considered these questions and provided anything relevant.

How is the number of bits of entropy in the file calculated? I suspect that it is not size of the file, since stat and ls -s return 0, but the number of bits of entropy is available in /proc/sys/kernel/random/entropy_avail. Is it something like the number of bits that can be obtained without learning anything but the bit itself?

I didn't really understand the explanation in the source code or in Gutterman et al. I suspect that one cannot feasibly compute this value exactly. However, can one guarantee that if I read less than entropy_avail bits from /dev/random, then the entropy in that string is approximately the length of the string? In other words is the value of entropy_avail a conservative lower bound on the number of random bits that can be obtained from reading /dev/random?

I would be very interested for a reference on the last one!

techraf
  • 9,141
  • 11
  • 44
  • 62
  • I migrated your question here from cryptography Stack Exchange, because it seemed to be less about the cryptographic algorithms, and more about entropy collection. Please register your account here and on Crypto SE so you can gain possession of your question, comment and accept an answer. – Paŭlo Ebermann Nov 19 '12 at 16:01
  • See [Feeding /dev/random entropy pool?](http://security.stackexchange.com/questions/89/feeding-dev-random-entropy-pool) and [Is a rand from /dev/urandom secure for a login key?](http://security.stackexchange.com/questions/3936/is-a-rand-from-dev-urandom-secure-for-a-login-key) – Gilles 'SO- stop being evil' Nov 19 '12 at 19:08

2 Answers2

3

There is a short paper on the ePrint cryptography archive that could answer your question. Basically the author interprets the code of the entropy estimator as Kolmogorov-type entropy estimation where an event is "random" if it didn't happen too close from the previous event, if the time between two consecutive events is not too predictable and so on Here is the link that will answer the question better than I did http://eprint.iacr.org/2012/487.pdf

1

/proc/sys/kernel/random/entropy_avail simply gives you the number of bits that can currently be read from /dev/random. Attempts to read more than that will block until more entropy becomes available. You may treat these bits as you would any other bits from a cryptographically random source.

The bits from /dev/random cannot be reread.

Stephen Touset
  • 5,736
  • 1
  • 23
  • 38
  • 3
    This is all fine, but it seems to me that the questions is *"Where does the value in `/proc/.../entropy_avail` come from?"* rather than *"How do I, as a user, know how much I can currently read from `/dev/random`?"*. –  Nov 19 '12 at 15:32
  • @everyone remember this was an answer posted from crypto.SE with a different perspective on the problem. Though I have to agree it doesn't really address the question which is really about how the kernel comes up with this entropy estimate. – Thomas Nov 19 '12 at 16:00
  • I provided this answer because the questioner himself appeared to be somewhat confused about /dev/random itself. For example, "...if I read less than "entropy_avail" bits from /dev/random...", seems like an odd distinction, because you can read as much data as you like from /dev/random, and all of it will have sufficient entropy — the call will just end up blocking until it can satisfy your request. Or, "is the value of entropy_avail a conservative lower bound...?" No, the value of entropy_avail is simply the number of bits of entropy that can be read without blocking. – Stephen Touset Nov 19 '12 at 18:11
  • 2
    According to the current source code of [drivers/char/random.c in Linux v4.7](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c?h=v4.7-rc4#n1703), `entropy_avail` is the size of the "input" pool. The size of the "output" pools (for random and urandom) cannot be extracted as far as I can see (search for `blocking_pool.entropy_count`). – Lekensteyn Jun 21 '16 at 11:38