11 ms·

random

123 points by e1ven 13y ago

buo 13y ago
From the abstract: "A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform." I think this is incorrect, since it would imply that a program that produces the sequence 1,2,1,2,1,2,1.... is a PRNG.
- gvb 13y ago
  Not all deterministic algorithms with uniform distributions are PRNGs.
  - buo 13y ago
    I know that, but that is what the first sentence in the paper's abstract is claiming. As I said, I think it's wrong.
    - paddyoloughlin 13y ago
      Breaking Bad is a TV show. American Idol is also a TV show. However, Breaking Bad is not American Idol.
    - gvb 13y ago
      A dog is a mammal, but not all mammals are dogs. The paper states "[a] pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform." You are asserting the converse, that all deterministic algorithms with uniform distributions are PRNGs.
- syzo 13y ago
  you can also check that (1,1), (1,2), (2,1), and (2,2) all happen with expected frequencies (i.e. roughly 25%), where the two numbers in the pair are just two numbers in a row in the sequence. You would have gotten 100% (1,2) and 0% for the rest, so that's suspicious. same for 3-tuples, 4-tuples, ..., and n-tuples. There's probably other, more sophisticated tests as well, but I'm not an expert.
  - buo 13y ago
    I think you missed my point, which is this: the first sentence in the paper's abstract is wrong.
    - syzo 13y ago
      My examples with pairs and n-tuples are also distributions.
      - buo 13y ago
        That's a good point, and that may well be what the authors meant. Since all PRNGs are periodic (at least all I now of), the definition eventually breaks down. I can see how it can be made to work with a bit of extra formalism, though. Thanks.
        jameshart 13y ago
        Any finite state PRNG has to be periodic. Good luck implementing an infinite state one.
- phaemon 13y ago
  Nope, because you don't have the same number of 9s and 8s as 1s and 2s, so it's not uniform.
  - buo 13y ago
    I don't think you're correct. A discrete distribution can be defined for any number of values. Linux, which is the subject of the paper, uses a discrete distribution too.
    - phaemon 13y ago
      Ok, that's fine, you just want to use 1s and 2s (though it would have been more obvious if you'd just used 0s and 1s :) ). In that case, you don't have as many 11s and 22s as 12s and 21s (I'm ignoring the commas since they're irrelevant).
      - deleted 13y ago
        [deleted]
- mcherm 13y ago
  No, your sequence IS distinguishable from a uniform sequence. At least it is if I understand what you mean by "...". If you mean that it generates 1,2,1,2,1,2,1 and then after that generates a mix of different values that include all possible values in approximately equal frequency, then you may have a fairly good PRNG. If you mean that it produces 1,2,1,2,1,2,1 and then after that it continues to alternate between 2 and 1, then this is easily distinguished from uniform.
  - buo 13y ago
    But I never said it was indistinguishable. What I'm saying is that the definition in the first sentence of the paper is wrong or, at least, incomplete.
    - jerf 13y ago
      "whose distribution is indistinguishable from uniform" Emphasis mine. Distribution here is not its English meaning, it is referring to the statistical term. Thus, it is talking about numbers "drawn from the uniform distribution", not "uniform numbers". A PRNG drawing from the uniform distribution may produce that sequence (for any set that includes 1 and 2), but a PRNG that only produced that sequence would certainly not be drawing from the uniform distribution.
    - moocowduckquack 13y ago
      Perhaps you don't understand the terms in context. If you looked at the distribution of your example, it would have two big spikes in it, at numbers one and two.
  - pmelendez 13y ago
    >"No, your sequence IS distinguishable from a uniform sequence." No, it is not distinguishable. The definition according to wikipedia: The discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n. So the distribution is indeed uniform but it fails in being random.
- andrewcooke 13y ago
  you're quoting the first sentence from the abstract in isolation; there's a lot more detail in the paper. in particular the define the notion of epsilon-closeness (section 2) for any distinguisher (which could include one that detects repeated patterns).
  - buo 13y ago
    My intention is not to criticize the paper, which I don't even claim to understand. I just thought the authors definition of a PNRG is wrong (or at least incomplete) and that caught my attention. If I'm wrong, I hope somebody will set me right.
    - andrewcooke 13y ago
      i just did. (1) an abstract is just a sketch of the entire paper contents. (2) in section 2 of the paper they give a more precise meaning to indistinguishable which allows you to use any function you can think of to detect non-uniformity (roughly - there are details like it's a limit as you go to large sequences, so that any finite random pattern becomes progressively less likely, etc etc). so you can cover the case you are worried about by using a test that looks for repeated patterns of values. [more generally, even with hn as it is these days, if you're asking for clarification rather than raising an objection, then you should probably prefix your comment with something like "i don't understand the paper, can someone please understand why...".]
      - buo 13y ago
        Thanks.
      - pmelendez 13y ago
        >"(1) an abstract is just a sketch of the entire paper contents." That is not an excuse for containing a bogus definition without a warning, especially in the abstract which is the first thing that you read to tell if the paper is interesting enough to look it in depth.
- manulp 13y ago
  This sequence is trivially distinguishable from something uniform.
- deutronium 13y ago
  Using ent, and 0's and 1's (instead of 1's and 2's). (By this I mean a pattern of 0,1,0,1 bits etc. - 4248759 bytes worth in this case) Below is the output from ent: ---------------------------- Entropy = 0.000000 bits per byte. Optimum compression would reduce the size of this 4248759 byte file by 100 percent. Chi square distribution for 4248759 samples is 1083433545.00, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 170.0000 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is undefined (all values equal!).
- bmm6o 13y ago
  I don't think people understand what your point is. What do you think is missing from the sentence? An explicit mention of independence? Why do you think 1,2,1,2,1,2,... is indistinguishable from uniform? In another response you said > But I never said it was indistinguishable which is confusing in context. What properties do yo claim your sequence has?
  - buo 13y ago
    I'm sorry for being unclear. The authors define a a PRNG as a sequence such that, if you find its distribution (histogram), it resembles the uniform distribution (all values appear the same number of times). In 1,2,1,2,1,2,..., all values appear the same number of times and its histogram is uniform. However, it is not random. It is clearly not random -- so it is distinguishable from a uniform "true random" sequence, which was my point. However, as was explained to me by another commenter, what I missed is that you may group a number of consecutive numbers together and find the histogram of that, and, in that case, my sequence fails to have a uniform histogram. So, at this point I'm willing to accept that the author's definition is correct and I just had a hole in my understanding.
    - bqe 13y ago
      Are you missing the point of a limit? As t->inf, if we counted all of the 1's and all of the 2's and all of the 3's, etc. and there were no 3's, it's not random according to this definition or any definition I'm aware of.
      - pmelendez 13y ago
        I guess he is restricting the domain to [1,2] in which case 1,2,1,2,1,2... is as "random" as 1,2,2,2,1,2,1,1 ... I guess what is bothering him is the lack of entropy in the sequence.
    - bmm6o 13y ago
      I guess I could see your interpretation, but it requires that you ignore all of the context of the paper. For instance, you take distribution to equal histogram. This may make sense in some contexts, but here it's absolutely not true; the values are supposed to be taken independently from some probability distribution. Pro tip: if you think you've spotted a major problem in the first line of an abstract, maybe give the author the benefit of the doubt. Especially if you're not familiar with the field.
- mistercow 13y ago
  I am not terribly good with statistical terminology, but I don't think that the definition you're assuming for "uniform distribution" is the one in general use. Once you know a[n], a[n+1] will follow a delta distribution, not a uniform distribution.
- akjj 13y ago
  Clearly, a PRNG is a subtle concept and it's common for abstracts to not be completely precise. In context, it's clear to me that by "uniform" they mean "a random process which generates numbers independently from a uniform distribution." Your process is generating numbers uniformly, but successive outputs are definitely not independent. One reason why I feel your interpretation is strained is that the phrasing makes "uniform" sound like a single process. You seem to be reading it as "numbers which are distributed uniformly," but the word indistinguishable really suggests that it's more than just the distribution that matters.
- betterunix 13y ago
  The sequence 1,2,1,2,1,2,1... is not indistinguishable from a uniform sequence, at least in the context of cryptography. With high probability, an algorithm that checks if all the even indexed inputs are 1 and all the odd indexed inputs are 2 will distinguish that sequence from a uniform random sequence (this is easy to see, as the probability of a sequence of that form being generated by repeatedly tossing a fair coin is very small).
- tiagobraw 13y ago
  why not 4, 4, 4, 4, 4,... ;) obligatory: http://xkcd.com/221/ http://xkcd.com/221/
  - poizan42 13y ago
    Or: http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/
tptacek 13y ago
This is an interesting paper that was discussed widely on Twitter a few months back. It includes a very useful breakdown of the Linux kernel CSPRNG starting on page 17. The attacks the paper describes start on page 22. The front part of the paper is dominated by a discussion of the theoretical modeling of CSPRNGs, in part because the theoretical foundations for CSPRNGs and their interactions with applications are not well documented. The most important bit of information you probably want to know about this paper is that it is modeling the security of a CSPRNG when its entropy inputs are entirely controlled by attackers. For instance, one of the attacks involves tricking the entropy estimator into believing it's seeding itself with high-quality random data when that data in fact has no entropy. This is not a realistic attack scenario for the vast majority (maybe all) of applications. Having said that, the Linux kernel CSPRNG doesn't (as far as I know) have a particularly well formalized design. There are good CSPRNG designs out there; for instance, the BSDs use Yarrow, and Ferguson followed that design up with Fortuna, which dispenses with the need for entropy estimators altogether.
- XorNot 13y ago
  Wouldn't this in fact be completely unrealistic? If attackers have full control of entropy inputs, they can just hook up a very high quality randomness source, but record every single bit before it gets to /dev/random. Of course, why bother with that if you have that kind of access?
- plantsbeans 13y ago
  Using a "false entropy" model feels partially like a response to criticism of things like RdRand, for example.
tytso 13y ago
So I'm the maintainer for Linux's /dev/random driver. I've only had a chance to look at the paper very quickly, and I will at it more closely when I have more time, but what the authors of this paper seem to be worried about is not even close to the top of my list in terms of things I'm worried about. First of all, the paper is incorrect in some minor details; the most significant error is its (untrue) claim that we stop gathering entropy when the entropy estimate for a given entropy pool is "full". Before July 2012, we went into a trickle mode where we only took in 1 in 096 values. Since then, the main way that we gather entropy, which is via add_interrupt_randomness(), has no such limit. This means that we will continue to collect entropy even if the input pool is apparently "full". This is critical, because secondly their hypothetical attacks presume certain input distributions which have an incorrect entropy estimate --- that is, either zero actual entropy but a high entropy estimate, or a high entropy, but a low entropy estimate. There has been no attempt by the paper's authors to determine whether the entropy gathered by Linux meets either of their hypothetical models, and in fact in the "Linux Pseudorandom Number Generator Revisited"[1], the analysis showed that our entropy estimator was actually pretty good, given the real-life inputs that we are able to obtain from an actual running Linux system. [1] http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don't want to block, that they end up with keys that aren't very random. We had some really serious problems with this, which was written up in the "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices"[2] paper, and the changes made in July 2012 were specifically designed to address these worries. [2] https://www.factorable.net/paper.html https://www.factorable.net/paper.html However, it may be that on certain systems, in particular ARM and MIPS based systems, where a long-term public key is generated very shortly after the first power-on, that there's enough randomness that the techniques used in [2] would not find any problems, but that might be not enough randomness to prevent our friends in Fort Meade from being able to brute force guess the possible public-private key pairs. Speaking more generally, I'm a bit dubious about academic analysis which are primarily worried about recovering from the exposure of the state of the random pool. In practice, if the bad guy can grab the state of random pool, they probably have enough privileged access that they can do much more entertaining things, such as grabbing the user's passphrase or just grabbing their long-term private key. Trying to preserve the amount of entropy in the pool, and making sure that we can extract as much uncertainty from the system as possible, are much higher priority things to worry about. That's not to say that I might not make changes to /dev/random in reaction to academic analysis; I've made changes in reaction to [2], and I have changes queued for the next major kernel release up to make some changes to address concerns raised in [1]. However, protection against artificially constructed attacks is not the only thing which I am worried about. Things like making sure we have adequate entropy collection on all platforms, especially embedded ones, and adding some conservatism just in case SHA isn't a perfect random function are some of the other things which I am trying to balance as we make changes to /dev/random.

123 points by e1ven 13y ago

buo 13y ago

From the abstract: "A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform." I think this is incorrect, since it would imply that a program that produces the sequence 1,2,1,2,1,2,1.... is a PRNG.

gvb 13y ago
Not all deterministic algorithms with uniform distributions are PRNGs.
- buo 13y ago
  I know that, but that is what the first sentence in the paper's abstract is claiming. As I said, I think it's wrong.
  - paddyoloughlin 13y ago
    Breaking Bad is a TV show. American Idol is also a TV show. However, Breaking Bad is not American Idol.
  - gvb 13y ago
    A dog is a mammal, but not all mammals are dogs. The paper states "[a] pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform." You are asserting the converse, that all deterministic algorithms with uniform distributions are PRNGs.
syzo 13y ago
you can also check that (1,1), (1,2), (2,1), and (2,2) all happen with expected frequencies (i.e. roughly 25%), where the two numbers in the pair are just two numbers in a row in the sequence. You would have gotten 100% (1,2) and 0% for the rest, so that's suspicious. same for 3-tuples, 4-tuples, ..., and n-tuples. There's probably other, more sophisticated tests as well, but I'm not an expert.
- buo 13y ago
  I think you missed my point, which is this: the first sentence in the paper's abstract is wrong.
  - syzo 13y ago
    My examples with pairs and n-tuples are also distributions.
    - buo 13y ago
      That's a good point, and that may well be what the authors meant. Since all PRNGs are periodic (at least all I now of), the definition eventually breaks down. I can see how it can be made to work with a bit of extra formalism, though. Thanks.
      - jameshart 13y ago
        Any finite state PRNG has to be periodic. Good luck implementing an infinite state one.
phaemon 13y ago
Nope, because you don't have the same number of 9s and 8s as 1s and 2s, so it's not uniform.
- buo 13y ago
  I don't think you're correct. A discrete distribution can be defined for any number of values. Linux, which is the subject of the paper, uses a discrete distribution too.
  - phaemon 13y ago
    Ok, that's fine, you just want to use 1s and 2s (though it would have been more obvious if you'd just used 0s and 1s :) ). In that case, you don't have as many 11s and 22s as 12s and 21s (I'm ignoring the commas since they're irrelevant).
    - deleted 13y ago
      [deleted]
mcherm 13y ago
No, your sequence IS distinguishable from a uniform sequence. At least it is if I understand what you mean by "...". If you mean that it generates 1,2,1,2,1,2,1 and then after that generates a mix of different values that include all possible values in approximately equal frequency, then you may have a fairly good PRNG. If you mean that it produces 1,2,1,2,1,2,1 and then after that it continues to alternate between 2 and 1, then this is easily distinguished from uniform.
- buo 13y ago
  But I never said it was indistinguishable. What I'm saying is that the definition in the first sentence of the paper is wrong or, at least, incomplete.
  - jerf 13y ago
    "whose distribution is indistinguishable from uniform" Emphasis mine. Distribution here is not its English meaning, it is referring to the statistical term. Thus, it is talking about numbers "drawn from the uniform distribution", not "uniform numbers". A PRNG drawing from the uniform distribution may produce that sequence (for any set that includes 1 and 2), but a PRNG that only produced that sequence would certainly not be drawing from the uniform distribution.
  - moocowduckquack 13y ago
    Perhaps you don't understand the terms in context. If you looked at the distribution of your example, it would have two big spikes in it, at numbers one and two.
- pmelendez 13y ago
  >"No, your sequence IS distinguishable from a uniform sequence." No, it is not distinguishable. The definition according to wikipedia: The discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n. So the distribution is indeed uniform but it fails in being random.
andrewcooke 13y ago
you're quoting the first sentence from the abstract in isolation; there's a lot more detail in the paper. in particular the define the notion of epsilon-closeness (section 2) for any distinguisher (which could include one that detects repeated patterns).
- buo 13y ago
  My intention is not to criticize the paper, which I don't even claim to understand. I just thought the authors definition of a PNRG is wrong (or at least incomplete) and that caught my attention. If I'm wrong, I hope somebody will set me right.
  - andrewcooke 13y ago
    i just did. (1) an abstract is just a sketch of the entire paper contents. (2) in section 2 of the paper they give a more precise meaning to indistinguishable which allows you to use any function you can think of to detect non-uniformity (roughly - there are details like it's a limit as you go to large sequences, so that any finite random pattern becomes progressively less likely, etc etc). so you can cover the case you are worried about by using a test that looks for repeated patterns of values. [more generally, even with hn as it is these days, if you're asking for clarification rather than raising an objection, then you should probably prefix your comment with something like "i don't understand the paper, can someone please understand why...".]
    - buo 13y ago
      Thanks.
    - pmelendez 13y ago
      >"(1) an abstract is just a sketch of the entire paper contents." That is not an excuse for containing a bogus definition without a warning, especially in the abstract which is the first thing that you read to tell if the paper is interesting enough to look it in depth.
manulp 13y ago
This sequence is trivially distinguishable from something uniform.
deutronium 13y ago
Using ent, and 0's and 1's (instead of 1's and 2's). (By this I mean a pattern of 0,1,0,1 bits etc. - 4248759 bytes worth in this case) Below is the output from ent: ---------------------------- Entropy = 0.000000 bits per byte. Optimum compression would reduce the size of this 4248759 byte file by 100 percent. Chi square distribution for 4248759 samples is 1083433545.00, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 170.0000 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is undefined (all values equal!).
bmm6o 13y ago
I don't think people understand what your point is. What do you think is missing from the sentence? An explicit mention of independence? Why do you think 1,2,1,2,1,2,... is indistinguishable from uniform? In another response you said > But I never said it was indistinguishable which is confusing in context. What properties do yo claim your sequence has?
- buo 13y ago
  I'm sorry for being unclear. The authors define a a PRNG as a sequence such that, if you find its distribution (histogram), it resembles the uniform distribution (all values appear the same number of times). In 1,2,1,2,1,2,..., all values appear the same number of times and its histogram is uniform. However, it is not random. It is clearly not random -- so it is distinguishable from a uniform "true random" sequence, which was my point. However, as was explained to me by another commenter, what I missed is that you may group a number of consecutive numbers together and find the histogram of that, and, in that case, my sequence fails to have a uniform histogram. So, at this point I'm willing to accept that the author's definition is correct and I just had a hole in my understanding.
  - bqe 13y ago
    Are you missing the point of a limit? As t->inf, if we counted all of the 1's and all of the 2's and all of the 3's, etc. and there were no 3's, it's not random according to this definition or any definition I'm aware of.
    - pmelendez 13y ago
      I guess he is restricting the domain to [1,2] in which case 1,2,1,2,1,2... is as "random" as 1,2,2,2,1,2,1,1 ... I guess what is bothering him is the lack of entropy in the sequence.
  - bmm6o 13y ago
    I guess I could see your interpretation, but it requires that you ignore all of the context of the paper. For instance, you take distribution to equal histogram. This may make sense in some contexts, but here it's absolutely not true; the values are supposed to be taken independently from some probability distribution. Pro tip: if you think you've spotted a major problem in the first line of an abstract, maybe give the author the benefit of the doubt. Especially if you're not familiar with the field.
mistercow 13y ago
I am not terribly good with statistical terminology, but I don't think that the definition you're assuming for "uniform distribution" is the one in general use. Once you know a[n], a[n+1] will follow a delta distribution, not a uniform distribution.
akjj 13y ago
Clearly, a PRNG is a subtle concept and it's common for abstracts to not be completely precise. In context, it's clear to me that by "uniform" they mean "a random process which generates numbers independently from a uniform distribution." Your process is generating numbers uniformly, but successive outputs are definitely not independent. One reason why I feel your interpretation is strained is that the phrasing makes "uniform" sound like a single process. You seem to be reading it as "numbers which are distributed uniformly," but the word indistinguishable really suggests that it's more than just the distribution that matters.
betterunix 13y ago
The sequence 1,2,1,2,1,2,1... is not indistinguishable from a uniform sequence, at least in the context of cryptography. With high probability, an algorithm that checks if all the even indexed inputs are 1 and all the odd indexed inputs are 2 will distinguish that sequence from a uniform random sequence (this is easy to see, as the probability of a sequence of that form being generated by repeatedly tossing a fair coin is very small).
tiagobraw 13y ago
why not 4, 4, 4, 4, 4,... ;) obligatory: http://xkcd.com/221/ http://xkcd.com/221/
- poizan42 13y ago
  Or: http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/

tptacek 13y ago

This is an interesting paper that was discussed widely on Twitter a few months back. It includes a very useful breakdown of the Linux kernel CSPRNG starting on page 17. The attacks the paper describes start on page 22. The front part of the paper is dominated by a discussion of the theoretical modeling of CSPRNGs, in part because the theoretical foundations for CSPRNGs and their interactions with applications are not well documented. The most important bit of information you probably want to know about this paper is that it is modeling the security of a CSPRNG when its entropy inputs are entirely controlled by attackers. For instance, one of the attacks involves tricking the entropy estimator into believing it's seeding itself with high-quality random data when that data in fact has no entropy. This is not a realistic attack scenario for the vast majority (maybe all) of applications. Having said that, the Linux kernel CSPRNG doesn't (as far as I know) have a particularly well formalized design. There are good CSPRNG designs out there; for instance, the BSDs use Yarrow, and Ferguson followed that design up with Fortuna, which dispenses with the need for entropy estimators altogether.

XorNot 13y ago
Wouldn't this in fact be completely unrealistic? If attackers have full control of entropy inputs, they can just hook up a very high quality randomness source, but record every single bit before it gets to /dev/random. Of course, why bother with that if you have that kind of access?
plantsbeans 13y ago
Using a "false entropy" model feels partially like a response to criticism of things like RdRand, for example.

tytso 13y ago

So I'm the maintainer for Linux's /dev/random driver. I've only had a chance to look at the paper very quickly, and I will at it more closely when I have more time, but what the authors of this paper seem to be worried about is not even close to the top of my list in terms of things I'm worried about. First of all, the paper is incorrect in some minor details; the most significant error is its (untrue) claim that we stop gathering entropy when the entropy estimate for a given entropy pool is "full". Before July 2012, we went into a trickle mode where we only took in 1 in 096 values. Since then, the main way that we gather entropy, which is via add_interrupt_randomness(), has no such limit. This means that we will continue to collect entropy even if the input pool is apparently "full". This is critical, because secondly their hypothetical attacks presume certain input distributions which have an incorrect entropy estimate --- that is, either zero actual entropy but a high entropy estimate, or a high entropy, but a low entropy estimate. There has been no attempt by the paper's authors to determine whether the entropy gathered by Linux meets either of their hypothetical models, and in fact in the "Linux Pseudorandom Number Generator Revisited"[1], the analysis showed that our entropy estimator was actually pretty good, given the real-life inputs that we are able to obtain from an actual running Linux system. [1] http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don't want to block, that they end up with keys that aren't very random. We had some really serious problems with this, which was written up in the "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices"[2] paper, and the changes made in July 2012 were specifically designed to address these worries. [2] https://www.factorable.net/paper.html https://www.factorable.net/paper.html However, it may be that on certain systems, in particular ARM and MIPS based systems, where a long-term public key is generated very shortly after the first power-on, that there's enough randomness that the techniques used in [2] would not find any problems, but that might be not enough randomness to prevent our friends in Fort Meade from being able to brute force guess the possible public-private key pairs. Speaking more generally, I'm a bit dubious about academic analysis which are primarily worried about recovering from the exposure of the state of the random pool. In practice, if the bad guy can grab the state of random pool, they probably have enough privileged access that they can do much more entertaining things, such as grabbing the user's passphrase or just grabbing their long-term private key. Trying to preserve the amount of entropy in the pool, and making sure that we can extract as much uncertainty from the system as possible, are much higher priority things to worry about. That's not to say that I might not make changes to /dev/random in reaction to academic analysis; I've made changes in reaction to [2], and I have changes queued for the next major kernel release up to make some changes to address concerns raised in [1]. However, protection against artificially constructed attacks is not the only thing which I am worried about. Things like making sure we have adequate entropy collection on all platforms, especially embedded ones, and adding some conservatism just in case SHA isn't a perfect random function are some of the other things which I am trying to balance as we make changes to /dev/random.