Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 smime.p7s Description: S/MIME cryptographic signature
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 smime.p7s Description: S/MIME cryptographic signature
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 smime.p7s Description: S/MIME cryptographic signature
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 smime.p7s Description: S/MIME cryptographic signature
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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/ -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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/ -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: RNG: is it possible to spoil /dev/random by seeding it from (evil) TRNGs
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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/