random: use xor for mixing
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Theodore Tso
maintainerQuoted 13 lines · Matt Mackall
random: use xor for mixing
With direct assignment, we can determine the twist table element used for mixing (the high 3 bits of the table are unique) and reverse a single step of mixing. Instead, use xor, which should also help preserve entropy in a given pool slot.
Signed-off-by Matt Mackall <[email protected]>diff -r
bc336762cfdbdrivers/char/random.c
drivers/char/random.c static void __add_entropy_words(struct e · line 500
Quoted 6 lines
drivers/char/random.c +1
-1@@ -496,7 +496,7 @@ static void __add_entropy_words(struct e w ^= r->pool[(i + tap4) & wordmask]; w ^= r->pool[(i + tap5) & wordmask]; w ^= r->pool[i]; - r->pool[i] = (w >>3 ) ^ twist_table[w &7 ]; + r->pool[i] ^= (w >>3 ) ^ twist_table[w &7 ]; }
In the original design of add_entropy_words(), in order to provably not lose any entropy, you want add_entropy_words() to be reversible if you mix in all zero's. So the fact that you can determine the twist table element used from looking at the high bits was deliberate. The mixing done in add_entropy_words() is *not* intended to be cryptographic, but merely to smear the bits around as they are added and then to permute the pool so that when you use SHA in the output stage, enough bits are changing that even if there are weaknesses discovered in the crypto hash algorithm, it won't help the attacker.
The internals of the pool are never exposed, so an attacker should never gain direct access to the entropy pool; hence worry about whether someone can "reverse" the mixing isn't particuarly a worry; indeed, in order to make sure we preserve entropy, the whole *point* of the mixing algorithm is that it is reversible.
(note: credit for this design should go to Colin Plumb, who worked with me on this aspect of the design. Colin was responsible for the original random number generator in PGP....)
- Ted
Quoted 10 lines · Theodore Tso
Quoted 9 lines · Matt Mackall
random: use xor for mixing
With direct assignment, we can determine the twist table element used for mixing (the high 3 bits of the table are unique) and reverse a single step of mixing. Instead, use xor, which should also help preserve entropy in a given pool slot.
Signed-off-by Matt Mackall <[email protected]>
Quoted 14 lines
drivers/char/random.c static void __add_entropy_words(struct e · line 500
Quoted 10 lines
diff -r
bc336762cfdbdrivers/char/random.cdrivers/char/random.c +1
-1@@ -496,7 +496,7 @@ static void __add_entropy_words(struct e w ^= r->pool[(i + tap4) & wordmask]; w ^= r->pool[(i + tap5) & wordmask]; w ^= r->pool[i]; - r->pool[i] = (w >>3 ) ^ twist_table[w &7 ]; + r->pool[i] ^= (w >>3 ) ^ twist_table[w &7 ]; }In the original design of
add_entropy_words(), in order to provably not lose any entropy, you wantadd_entropy_words()to be reversible if you mix in all zero's.
Ahh, yes, that's true. I'd somehow missed that we effectively had a tap at 0, so I thought this was actually improving the situation. I'll replace this with a comment explaining the situation.
Quoted 5 lines
The internals of the pool are never exposed, so an attacker should never gain direct access to the entropy pool; hence worry about whether someone can "reverse" the mixing isn't particuarly a worry; indeed, in order to make sure we preserve entropy, the whole *point* of the mixing algorithm is that it is reversible.
I'm working on strengthening forward security for cases where the internals are exposed to an attacker. There are any number of situations where this can and does happen, and ensuring we don't expose ourselves to backtracking is a worthwhile theoretical concern.
---
random: document revisibility of mixing function.
drivers/char/random.c +6 -0
@@ -447,6 +447,12 @@ static struct entropy_store nonblocking_* degree, and then twisted. We twist by three bits at a time because * it's cheap to do so and helps slightly in the expected case where * the entropy is concentrated in the low-order bits. +* +* This function is intentionally reversible, meaning that if we mix +* in known values, we can run the algorithm backwards and recover the +* earlier state. Because we can recover the original state, we are +* provably not destroying any existing entropy content in the pool +* when we mix. */ static void __add_entropy_words (struct entropy_store *r,const __u32 *in,int nwords,__u32 out[16 ])
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerQuoted 4 lines · Matt Mackall
I'm working on strengthening forward security for cases where the internals are exposed to an attacker. There are any number of situations where this can and does happen, and ensuring we don't expose ourselves to backtracking is a worthwhile theoretical concern.
See my other comments; I don't think we are currently vulnerable to backtracking.
I tend to view backtracking as largely a theoretical concern, as most of the time, if the attacker has read access to kernel memory in order to compromise the internal state of /dev/random, the attacker very likely has *write* access to kernel memory, at which point you have much bigger problems to worry about, at least going forward.
I suppose if you had *just* generated an 80-bit AES session key, right before the internal state was compromised, this might be interesting, but if the attacker can compromise arbitrary kernel memory, then attacker might as well just grab keying information from the userspace process --- such as perhaps the long-term private key of the user, or the data to be encrypted.
So my personal take on it is that protecting against backtracking attacks is mainly useful in silencing academics who like to come up with, well, largely academic and theoretical scenario. If it doesn't take much effort, sure, let's try to protect against it (and I think we're OK already).
But a much better use of our time would be spent creating userspace support so we can more efficiently pull entropy from TPM modules, or the noise from a sound/microphone input, etc., or other hardware sources of entropy. That would provide a much more practical improvement to the /dev/random subsystem than worry about what I feel are largely academic concerns.
Regards,
- Ted
Quoted 5 lines
So my personal take on it is that protecting against backtracking attacks is mainly useful in silencing academics who like to come up with, well, largely academic and theoretical scenario. If it doesn't take much effort, sure, let's try to protect against it (and I think we're OK already).
That problem seems to arise here because we have an interface to add 'real' entropy to the pool but not one to add randomness to be used solely for urandom. If we had both then the user could choose to add some degree of randomness solely for urandom usage.
Alan
Quoted 28 lines · Theodore Tso
Quoted 4 lines · Matt Mackall
I'm working on strengthening forward security for cases where the internals are exposed to an attacker. There are any number of situations where this can and does happen, and ensuring we don't expose ourselves to backtracking is a worthwhile theoretical concern.
See my other comments; I don't think we are currently vulnerable to backtracking.
I tend to view backtracking as largely a theoretical concern, as most of the time, if the attacker has read access to kernel memory in order to compromise the internal state of
/dev/random, the attacker very likely has *write* access to kernel memory, at which point you have much bigger problems to worry about, at least going forward.I suppose if you had *just* generated an 80-bit AES session key, right before the internal state was compromised, this might be interesting, but if the attacker can compromise arbitrary kernel memory, then attacker might as well just grab keying information from the userspace process --- such as perhaps the long-term private key of the user, or the data to be encrypted.
So my personal take on it is that protecting against backtracking attacks is mainly useful in silencing academics who like to come up with, well, largely academic and theoretical scenario. If it doesn't take much effort, sure, let's try to protect against it (and I think we're OK already).
Quoted 6 lines
But a much better use of our time would be spent creating userspace support so we can more efficiently pull entropy from TPM modules, or the noise from a
sound/microphoneinput, etc., or other hardware sources of entropy. That would provide a much more practical improvement to the/dev/randomsubsystem than worry about what I feel are largely academic concerns.
That doesn't actually sound too hard, and the sounds of passing traffic are not likely to be replicable in any case. Lots of sensor data might be used as well, fan rpm, etc. That sounds so obvious I can't believe there isn't a reason it's not being done.
Signature · 3 lines
Bill Davidsen <[email protected]> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot
A message that is not in the archive (sent off-list or not yet received): [email protected]
Theodore Tso
maintainerRe: [PATCH 3/6] random: do extraction before mixing
Quoted 4 lines · Matt Mackall
random: do extraction before mixing
If an attacker manages to capture the current pool state, she can determine the last 10 bytes extracted from the pool.
That's not true; we aren't just extracting data in the __add_entropy_words() call. In fact, above that, the bulk of the extraction comes form when we hash the entire pool, feeding back a portion of the hash into the pool here:
for (i = 0; i < r->poolinfo->poolwords; i += 16) {
/* hash blocks of 16 words = 512 bits */
sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
/* feed back portion of the resulting hash */
add_entropy_words(r, &buf[i % 5], 1);
}So the buf[0..5] contains a hash of the entire pool, and every 16 words, we're already mixing 32 bits into the pool. So even if the attacker captures the current pool state, she's not going to be able to undo the intermediate SHA values that had been mixed into the pool.
Quoted 2 lines
By mixing after
the extraction, this is made substantially harder.
Not that much harder; as I mentioned as comments in my last patch, we are doing a linear polynomial mixing for speed purposes, so relying on the mixing to obscure the extraction isn't going to help much.
But that's OK, we don't need to depend on that. Note the amount of feedback that we do in the above loop.
- Ted
Re: [PATCH 3/6] random: do extraction before mixing
Quoted 11 lines · Theodore Tso
Quoted 4 lines · Matt Mackall
random: do extraction before mixing
If an attacker manages to capture the current pool state, she can determine the last 10 bytes extracted from the pool.
That's not true; we aren't just extracting data in the
__add_entropy_words()call. In fact, above that, the bulk of the extraction comes form when we hash the entire pool, feeding back a portion of the hash into the pool here:
Quoted 6 lines
for (i = 0; i < r->poolinfo->poolwords; i += 16) {
/* hash blocks of 16 words = 512 bits */
sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
/* feed back portion of the resulting hash */
add_entropy_words(r, &buf[i % 5], 1);
}Ok, yes, I'd forgotten we were chaining in the final sha_transform. I plead too many bufs and buf+5s, which I fix up in 6/6. Funny thing is that I'd convinced myself that this attack didn't work (correct) last year when I read the paper I mentioned earlier. But yesterday and today I couldn't spot the problem with it. So again, I'll add an explicit comment for future hackers and researchers.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Theodore Tso
maintainerRe: [PATCH 4/6] random: make backtracking attacks harder
Quoted 7 lines · Matt Mackall
random: make backtracking attacks harder
At each extraction, we change (poolbits / 16) + 32 bits in the pool, or 96 bits in the case of the secondary pools. Thus, a brute-force backtracking attack on the pool state is less difficult than breaking the hash. In certain cases, this difficulty may be is reduced to 2^64 iterations.
OK, a backtracking attack assumes a fairly catastrophic case where the attacker has managed to compromise the internal pool state. In Linux, if an attacker has this much access, in most scenarios the attacker probably has the ability to gain write access to kernel memory as well, at which point you have far worse problems.
The definition of a backtracking attack is when the attacker uses the current pool state to try to recover the last entropy extraction. As you point out, at each extraction, 96 bits are changed in the pool. But at each extraction, only 80 bits are extracted.
If you are trying to find the value of the 80 bits that were extracted, and you know the current state of the pool, yes, you can take the 96 bits that were changed after the last extraction, and try all possible 2**96 combinations of the bits; but you probably won't rule anything out, since after you iterate over all of the 2**96 combinations, you'll probably be able to generate all of the 2**80 possible output bits. So you won't gain anything by trying to do a backtracking attack. So I don't think there's anything to worry about here.
What you describe in your comments:
Review
Quoted 8 lines
(quoted diff) +7
-0+ * We mix the hash back into the pool to prevent backtracking + * attacks (where the attacker knows the state of the pool + * plus the current outputs, and attempts to find previous + * ouputs), unless the hash function can be inverted. By + * mixing at least a SHA1 worth of hash data back, we make + * brute-forcing the feedback as hard as brute-forcing the + * hash. */
.... sounds like not a backtracking attack, but an Iterative guessing attack, where "knowledge of internal state at some point and the intervening PRNG outputs, to learn internal state at a later point when the inputs collected during this span of time are guessable by the attacker." (Definition taken from:
http://www.ee.oulu.fi/research/ouspg/frontier/sota/whitepaper-prng/)
But note first of all, all this lets you do is unwind to an earlier state just before the known PRNG outputs. In order to use this to guess PRNG output, you still have to solve the above mentioned backtracking attack --- where you have 96 bits that changed, and 80 possible extraction bits.
Secondly, the fact that we use catastrophic reseeding means that even if the state was compromised, at some point in time, every so often when we do a "catastrophic reseed", this acts as a firewall to limit the damage caused by a internal state exposure, both in the past and the future.
- Ted
Re: [PATCH 4/6] random: make backtracking attacks harder
Quoted 15 lines · Theodore Tso
Quoted 7 lines · Matt Mackall
random: make backtracking attacks harder
At each extraction, we change (poolbits / 16) + 32 bits in the pool, or 96 bits in the case of the secondary pools. Thus, a brute-force backtracking attack on the pool state is less difficult than breaking the hash. In certain cases, this difficulty may be is reduced to 2^64 iterations.
OK, a backtracking attack assumes a fairly catastrophic case where the attacker has managed to compromise the internal pool state. In Linux, if an attacker has this much access, in most scenarios the attacker probably has the ability to gain write access to kernel memory as well, at which point you have far worse problems.
Quoted 4 lines
The definition of a backtracking attack is when the attacker uses the current pool state to try to recover the last entropy extraction. As you point out, at each extraction, 96 bits are changed in the pool. But at each extraction, only 80 bits are extracted.
Agreed.
Quoted 9 lines
If you are trying to find the value of the 80 bits that were extracted, and you know the current state of the pool, yes, you can take the 96 bits that were changed after the last extraction, and try all possible 2**96 combinations of the bits; but you probably won't rule anything out, since after you iterate over all of the 2**96 combinations, you'll probably be able to generate all of the 2**80 possible output bits. So you won't gain anything by trying to do a backtracking attack. So I don't think there's anything to worry about here.
Two observations:
- 2**96 << 2**160 so our feedback is much weaker than our hash so we should improve it on general principle
- there's a way to improve this attack to 2**64 in some situations!
I presume you've seen this paper:
http://eprint.iacr.org/2006/086.pdf
It was fairly obsolete at printing and makes a bunch of mistakes. But they do observe that at certain points in our feedback, the first 512-bit block of the pool is not overwritten by the feedback and thus 32 bits of feedback can be immediately discovered. Then an attacker can run 2**64 hashes to recover the remaining bits with excellent odds of having a unique preimage. It can't usually be extended multiple iterations because we move the add_ptr too much, so it's fairly weak as a backtracking attack.
They precede this with a more general description of a 2**96 attack which doesn't work for precisely the reason you describe (2**16 possible preimages for each output). But their 2**64 attack does seem like it works (in the world of cryptanalysis, and not real hardware of course!).
Simply feeding back all five words of our hash rather than three in the secondary pools hardens this all right up. This patch also makes everything in here much easier to read and analyze.
Quoted 6 lines
What you describe in your comments:
Review
Quoted 4 lines
(quoted diff) +4
-0+ * We mix the hash back into the pool to prevent backtracking + * attacks (where the attacker knows the state of the pool + * plus the current outputs, and attempts to find previous + * ouputs), unless the hash function can be inverted.
That part of the comment is not new, but I don't remember which of us wrote it..
Quoted 5 lines
Review
Quoted 5 lines
...By
(quoted diff) +3
-0+ * mixing at least a SHA1 worth of hash data back, we make + * brute-forcing the feedback as hard as brute-forcing the + * hash. */
That part is new and I think is accurate.
Quoted 5 lines
Secondly, the fact that we use catastrophic reseeding means that even if the state was compromised, at some point in time, every so often when we do a "catastrophic reseed", this acts as a firewall to limit the damage caused by a internal state exposure, both in the past and the future.
Absolutely. Having some depth in the design is quite valuable. But that doesn't mean we shouldn't shore up individual weaknesses when we find them.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerRe: [PATCH 4/6] random: make backtracking attacks harder
Quoted 10 lines · Matt Mackall
Quoted 9 lines
If you are trying to find the value of the 80 bits that were extracted, and you know the current state of the pool, yes, you can take the 96 bits that were changed after the last extraction, and try all possible 2**96 combinations of the bits; but you probably won't rule anything out, since after you iterate over all of the 2**96 combinations, you'll probably be able to generate all of the 2**80 possible output bits. So you won't gain anything by trying to do a backtracking attack. So I don't think there's anything to worry about here.
Quoted 4 lines
Two observations:
- 2**96 << 2**160 so our feedback is much weaker than our hash so we should improve it on general principle
Well, no. You're comparing apples and oranges here. You can iterate over 2**96 choices, but given that even if you are doing an iterative guessing attack, you have 2**80 knowns, and 2**96 unknowns, it doesn't buy you anything. So saying that there is a successful attack with O(2**96) simply isn't true! Secondly, a 160-bit hash is actually only 80 bits strong (because of the birthday attack); when SHA was originally published by the US government, it was designed to be paired with the Clipper chip, which was an 80 bit symmetric key cipher with a backdoor.
Quoted 1 line
- there's a way to improve this attack to 2**64 in some situations!
Yeah, but again, what does this "attack" buy you? If you know the output, and the current state of the pool, after doing 2**64 iterations you can get the state of the pool before the output. Big-di-whoopdie-do. You can't actually *do* anything with it.
If you want to use that to obtain the unknown 80-bit output at that point in time, you're back to the 96-bits unknown problem, since in the case where you don't know the output, the shortcut attack doesn't work.
Quoted 5 lines
I presume you've seen this paper:
http://eprint.iacr.org/2006/086.pdf
It was fairly obsolete at printing and makes a bunch of mistakes.
Oh yes, I'm familiar with the paper; I wrote a rebuttal to it to LKML at the time, and cc'ed the authors, who never got back to me. I also made a bunch of changes to strengthen /dev/random against some of their observations that described weaknesses, even though I didn't and still don't think you could leverage them into a practical attack, even *if* you accept their premise of a state compromise that didn't involve even worse consequences than enabling theoretical attacks against /dev/random.
Quoted 3 lines
Simply feeding back all five words of our hash rather than three in the secondary pools hardens this all right up. This patch also makes everything in here much easier to read and analyze.
It's fixing a non-problem, but I don't think changing actually hurts anything. My preferred way of dealing with this problem is simply to increase the output pool size, since that increases the number of bits that change each time from 96 bits to 160 bits.
(This is a private paranoia patch I've been carrying around for a while.)
- Ted
commit 9c6c0954b3d56de04f03225e16d7f0d31c823c92
Author: Theodore Ts'o <[email protected]> Date: Sat Oct 13 00:03:26 2007 -0400
randomness-fix-increase_output_pool
drivers/char/random.c +5 -5
@@ -249,7 +249,7 @@* Configuration information */ #define INPUT_POOL_WORDS 128 -#define OUTPUT_POOL_WORDS 32 +#define OUTPUT_POOL_WORDS 64#define SEC_XFER_SIZE 512/*
@@ -288,8 +288,8 @@ static struct poolinfo { } poolinfo_table[] = {/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ { 128, 103, 76, 51, 25, 1 }, -/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ - { 32, 26, 20, 14, 7, 1 }, +/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ + { 64, 52, 39, 26, 14, 1 }, #if 0 /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ { 2048, 1638, 1231, 819, 411, 1 },
@@ -314,8 +314,8 @@ static struct poolinfo { /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ { 128, 103, 78, 51, 27, 2 }, - /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ - { 64, 52, 39, 26, 14, 1 }, + /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ + { 32, 26, 20, 14, 7, 1 }, #endif };
Re: [PATCH 4/6] random: make backtracking attacks harder
Quoted 13 lines · Theodore Tso
Quoted 12 lines · Matt Mackall
Quoted 9 lines
If you are trying to find the value of the 80 bits that were extracted, and you know the current state of the pool, yes, you can take the 96 bits that were changed after the last extraction, and try all possible 2**96 combinations of the bits; but you probably won't rule anything out, since after you iterate over all of the 2**96 combinations, you'll probably be able to generate all of the 2**80 possible output bits. So you won't gain anything by trying to do a backtracking attack. So I don't think there's anything to worry about here.
Two observations:
Quoted 8 lines
Quoted 2 lines
- 2**96 << 2**160 so our feedback is much weaker than our hash so we should improve it on general principle
Well, no. You're comparing apples and oranges here. You can iterate over 2**96 choices, but given that even if you are doing an iterative guessing attack, you have 2**80 knowns, and 2**96 unknowns, it doesn't buy you anything. So saying that there is a successful attack with
O(2**96)simply isn't true!
Again, I agree that there's not any sort of useful attack here.
Quoted 6 lines
Quoted 1 line
- there's a way to improve this attack to 2**64 in some situations!
Yeah, but again, what does this "attack" buy you? If you know the output, and the current state of the pool, after doing 2**64 iterations you can get the state of the pool before the output. Big-di-whoopdie-do. You can't actually *do* anything with it.
Ahh, but this an attack on the output! You know only:
pool' (including a fortuitously placed add_ptr)
and from that, you can get all but 64 bits of pool. By 2**64 iterations of:
pool = pool' + guess
hash = SHA1(init, pool) # simplified
pool^ = add(pool, hash)
if pool^ = pool':
success!
Now you've recovered pool. Then you can recover the *output* with:
hash = SHA1(init, pool)
pool' = add(pool, hash)
entropy = extract(pool)
output = SHA1(hash, entropy)
Depending on where the add_ptr lands, we might even be able to go back another iteration.
By the way, I think the paper missed out on some corner case attacks which extend the range to greater than half of the possible add_ptr positions. Whenever less than 96 bits are changed in the first block, we can discover the pool in O(2**64).
Quoted 4 lines
It's fixing a non-problem, but I don't think changing actually hurts anything. My preferred way of dealing with this problem is simply to increase the output pool size, since that increases the number of bits that change each time from 96 bits to 160 bits.
Let's do that. But let's also do this because it makes the code more readable and somewhat stronger (for instance the first word fed back will be cascaded from the whole pool rather than the first 512 bits). We also only need to grab the lock once.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerRe: [PATCH 4/6] random: make backtracking attacks harder
Quoted 11 lines · Matt Mackall
Ahh, but this an attack on the output! You know only:
pool' (including a fortuitously placed
add_ptr)and from that, you can get all but 64 bits of pool. By 2**64 iterations of:
pool = pool' + guess
hash =SHA1(init, pool)# simplified
pool^ =add(pool, hash)
if pool^ = pool':
success!
Yes, you're right. I thought O(2**64) shortcut attack required knowledge of the output to unwind an interation, but looking again at the paper, I was incorrect. You can indeed roughly half of the time, be able to go backwards in O(2**64) operations, instead of O(2**96) operations. Note BTW, that if you assume that you can do SHA in 11 cycles per second (source: http://www.cryptopp.com/benchmarks.html)
and this requires you to hash approximatly half the pool, 11 cycles * 64 bytes * 2^64 operations is approximately 190.7 *centuries* assuming a 2 gigahertz processor. Obviously that's much better than 7 million *millenia* (i.e., 7 billion years) for O(2**96), but 190,669 years is quite a long time.
I suppose if the NSA had 20,000 2Ghz processors in the basement cranking for 10 years, then 50% of the time *after* they did a black bag job to crack the random pool state, they could get the last 80 bits generated from /dev/random, but it just seems that if you are assuming the power to grab the pool plus add_ptr, there would be much more useful things you could --- like for example having the black bag job trojaning the software to grab the private key directly.
So, I still view this as an academic weakness, and not a real-life threat. :-)
Quoted 4 lines
Let's do that. But let's also do this because it makes the code more readable and somewhat stronger (for instance the first word fed back will be cascaded from the whole pool rather than the first 512 bits). We also only need to grab the lock once.
Yeah, fair enough. Mixing in the whole hash doesn't actually cost that much more. It might have a theoretical chance of potentially losing slightly more entropy, but that is really a theoretical issue as well --- and the fact that we are mixing in the time each time we extract more than makes up for that. Oh, wait. Right, I forgot, you took that out at some point after you took over maintainership.
Can you add this patch, too? (Compile tested, not boot tested, but it's pretty obviously correct.)
- Ted
commit 499aa1b63923ff8a2309b3a1eccacb54db159c58
Author: Theodore Ts'o <[email protected]> Date: Mon Dec 10 08:35:53 2007 -0500
random: Mix in the time of extraction into the entropy pool
We don't actually add any entropy credit, but we do mix in the time of extraction to add further jitter and make life harder for an attacker by making the extraction process time-dependent. This means that any attacks on the /dev/random pool can't use a static analysis.
drivers/char/random.c +8 -0
@@ -767,6 +767,14 @@ static void extract_buf(struct entropy_store *r, __u8 *out) {int i;__u32 data[16 ], buf[5 +SHA_WORKSPACE_WORDS ]; +struct { +cycles_t cycles; +long jiffies; + } sample; + + sample.jiffies = jiffies; + sample.cycles =get_cycles (); +add_entropy_words (&input_pool, (u32 *)&sample,sizeof (sample)/4 );sha_init (buf);/*
A message that is not in the archive (sent off-list or not yet received): [email protected]
Theodore Tso
Acked-by Theodore Ts'oRe: [PATCH 5/6] random: step more rapidly through the pool when adding and extracting
Quoted 6 lines · Matt Mackall
random: step more rapidly through the pool when adding and extracting
Second, this patch spreads the mixing across the pool more rapidly by using a larger step. For our secondary pools, we'll be sure to touch both blocks with each mix, and for our primary pool, we'll change 5 of 8 blocks.
Yeah, that's a good idea.
- Ted
Re: [PATCH 5/6] random: step more rapidly through the pool when adding and extracting
Quoted 12 lines · On Sat, 8 Dec 2007 20:48:20 -0500 Theodore Tso <[email protected]> wrote:
Quoted 6 lines · Matt Mackall
random: step more rapidly through the pool when adding and extracting
Second, this patch spreads the mixing across the pool more rapidly by using a larger step. For our secondary pools, we'll be sure to touch both blocks with each mix, and for our primary pool, we'll change 5 of 8 blocks.
Yeah, that's a good idea.
Acked-by "Theodore Ts'o" <[email protected]>
I cannot find the emails to which you are replying. Not in inbox, not on lkml, not in spam folders. And lkml.org records your emails and not the emails to which you are replying.
I think something went wrong with Matt's outgoing.
Re: [PATCH 5/6] random: step more rapidly through the pool when adding and extracting
Quoted 12 lines · Andrew Morton
Quoted 10 lines · On Sat, 8 Dec 2007 20:48:20 -0500 Theodore Tso <[email protected]> wrote:
Quoted 6 lines · Matt Mackall
random: step more rapidly through the pool when adding and extracting
Second, this patch spreads the mixing across the pool more rapidly by using a larger step. For our secondary pools, we'll be sure to touch both blocks with each mix, and for our primary pool, we'll change 5 of 8 blocks.
Yeah, that's a good idea.
Quoted 8 lines
Quoted 2 lines
Acked-by "Theodore Ts'o" <[email protected]>I cannot find the emails to which you are replying. Not in inbox, not on lkml, not in spam folders. And lkml.org records your emails and not the emails to which you are replying.
I think something went wrong with Matt's outgoing.
It did. My laptop didn't relay them through my smarthost and my domain has an SPF record.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerRe: [PATCH 5/6] random: step more rapidly through the pool when adding and extracting
Quoted 3 lines · Matt Mackall
It did. My laptop didn't relay them through my smarthost and my domain has an SPF record.
Ah, yes:
http://homepages.tesco.net/~J.deBoynePollard/FGA/smtp-spf-is-harmful.html
- Ted
Re: [PATCH 5/6] random: step more rapidly through the pool when adding and extracting
Quoted 8 lines · Theodore Tso
Quoted 3 lines · Matt Mackall
It did. My laptop didn't relay them through my smarthost and my domain has an SPF record.
Ah, yes:
http://homepages.tesco.net/~J.deBoynePollard/FGA/smtp-spf-is-harmful.html
Yep, I temporarily set it up to mitigate a spate of From: forgeries against my domain, then it bit me later.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Theodore Tso
Acked-by Theodore Ts'oRe: [PATCH 6/6] random: improve variable naming, clear extract buffer
Quoted 10 lines · Matt Mackall
random: improve variable naming, clear extract buffer
- split the SHA variables apart into hash and workspace
- rename data to extract
- wipe extract and workspace after hashingdiff -r
924f9a441236drivers/char/random.c
drivers/char/random.c static void __add_entropy_words(struct e · line 467
Quoted 8 lines
drivers/char/random.c +1
-1@@ -461,7 +461,7 @@ static void __add_entropy_words(struct eunsigned long flags;/* rotate the add pointer more rapidly to span more of the * pool on a given add */ -const int step =5 ; +const int step =13 ;/* Taps are constant, so we can load them without holding r->lock. */ tap1 = r->poolinfo->tap1;
This change has nothing to do with the patch comment. If you want to change the step size from 5 to 13, why not just change patch 5/6 to just use a step size of 13 from the beginning?
Otherwise, yeah, this patch does make sense.
- Ted
Re: [PATCH 6/6] random: improve variable naming, clear extract buffer
Quoted 17 lines · Theodore Tso
Quoted 16 lines · Matt Mackall
random: improve variable naming, clear extract buffer
- split the SHA variables apart into hash and workspace
- rename data to extract
- wipe extract and workspace after hashingdiff -r
924f9a441236drivers/char/random.cdrivers/char/random.c +1
-1@@ -461,7 +461,7 @@ static void __add_entropy_words(struct eunsigned long flags;/* rotate the add pointer more rapidly to span more of the * pool on a given add */ -const int step =5 ; +const int step =13 ;
Quoted 6 lines
drivers/char/random.c static void __add_entropy_words(struct e · line 467
Quoted 2 lines
drivers/char/random.c +0
-0/* Taps are constant, so we can load them without holding r->lock. */ tap1 = r->poolinfo->tap1;This change has nothing to do with the patch comment. If you want to change the step size from 5 to 13, why not just change patch 5/6 to just use a step size of 13 from the beginning?
Patch refresh gone wrong.
Quoted 1 line
Otherwise, yeah, this patch does make sense.
Twice, in fact. This patch as sent won't compile due to an extra &.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.