Skip to contentSkip to conversation

Fortuna

DISCUSSION [email protected] 6 participants 28 messages Apr 14, 2005 – Apr 20, 2005

lore
Share & tools
lore
#0 lore raw

Just to refersh everyone's memory as to the strengths and weaknesses of Fortuna...

First, a reminder that the design goal of /dev/random proper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power. If you want a weaker guarantee, use /dev/urandom.

I've heard a suggestion that something like /dev/urandom, but which blocks until it has received a minimum amount of seed material at least once, would be a nice thing. So boot-time crypto initialization can stall until it has achieved a minimum level of security.

The minimum could be measured two ways:
- Some reasonable default, like 256 bits, or
- (clever) the size of the read() request, which is presumably the key size that the user needs. This might be too subtle to explain to programmers, though.

Anyway, there are two main parts to Fortuna. The central "random pool", and the round-robin sub-pool system for reseeding the main pool.

Fortuna uses a "small pool, trust the crypto" central pool. /dev/random uses a large pool that is deliberately designed to be robust against failure of the crypto primitives. Indeed, the basic design just uses it as a uniform hash. Cryptographic strength is irrelevant to the information-theoretic guarantees.

This portion of Fortuna is at odds with /dev/random's design goals, but it could be replaced easily enough. It's not the clever part.

The "neat idea" in Fortuna is the round-robin sub-pool seeding technique, which attempts to avoid the entire issue of entropy estimation.

Now, for information-theoretic guarantees, entropy measurement is *required*. You cannot be information-theoretic secure unless you have received more seed entropy than you have produced output.

However, Fortuna has a different philosophy. This difference is why Fortuna will NEVER be an "exact drop-in replacement" for /dev/random, although it can do the job for /dev/urandom. There are important user-visible differences in the guarantees it makes. Someone may argue that the difference is immaterial in practice, but existence of a difference is indisputable.

It tries to divide up the seed entropy into sub-pools and hold off re-seeding the main pool until the sub-pool has accumulated enough entropy to cause "catastrophic reseeding" of the main pool, adding enough entropy at once that someone who had captured the prior state of the main pool would not be able (due to computational limits and the one-way nature of the pool output function) to reverse-engineer the post-state.

The way it schedules the additions, it doesn't know *which* re-seed of the main pool will be catastrophic, but it knows that it will be within a factor of 64 of the shortest time that's possible.

However, it possible to come up with some pathological entropy sources for which the standard Fortuna design completely fails to achieve that goal.

So Fortuna would be helped by some better understanding of what exactly makes it fail, so the discussion could move to whether real-world seed sources have those properties.

But until that understanding is gained, Fortuna is questionable.

Appendix: how to "break" Fortuna.

First, the standard assumptions: the "attacker" can collect arbitrary amounts of RNG output at any time, and can see all operations on the pool except for the value of the seed material.

In particular, if the attacker's uncertainty about the pool's state is small, she can collect enough output to distinguish all the possibilities and attempt a brute-force computation to recover the unknown state information.

Finally, assume the attacker knows the full initial state of the generator.

For a classic 32-subpool Fortuna, let the seed be a 32-bit integer. Every time a new seed is produced, shift the previous value and insert a fresh random bit. Thus, the seed does deliver 1 bit of entropy per sample, which should make for a secure source.

If you want to be cruel, encrypt that seed with a strong cipher known only to the attacker before producing output. That keeps the nature of the seed from the Fortuna implementation.

Anyway, every 32 cycles, a seed word is added to subpool 0, which is then immediately added to the main pool. An attacker who knows the prior state of the main pool can attempt a brute-force search for the 32 bits of the seed word in a reasonable period of time.

Because of the shifting property, an attacker who knows the seeds added to pool 0 at times t and t+32 can also deduce, with perfect accuracy, the seeds added to the other 31 pools at times t+1 through t+31.

The result being that the other subpools, which are supposed to be hoarding secret information unknown to the attacker, are actually being seeded with bits known to the attacker.

The ultimate result is that catastrohpic reseeding never takes place. If we could somehow separate the "fresh" entropy in the input samples from the "holdover" material, the problem would go away, but that's an entropy measurement problem!

Until this cloud is dissipated by further analysis, it's not possible to say "this is shiny and new and better; they's use it!" in good conscience.

#1 lore raw

Thanks for the post.

Waiting for 256bits of entropy before outputting data is a good goal. Problem becomes how do you measure entropy in a reliable way? This had me lynched last time I asked it so I'll stop right there.

Info-theoretic randomness is a strong desire of some/many users, and they think the current entropy estimation technique does the trick, so I left it there with the option to #define it out.

I'll not make any claim that random-fortuna.c should be mv'd to random.c, the patch given allows people to kernel config it in under the Cryptographic Options menu. Perhaps a disclaimer in the help menu would be in order to inform users that Fortuna has profound consequences for those expecting Info-theoretic /dev/random?

The case where an attacker has some small amount of unknown in the pool is a problem that effects BOTH random-fortuna.c and random.c (and any other replacement for that matter). Just an FYI.

As for the "shifting property" problem of an attacker controlling some input to the pooling system, I've tried to get around this:

r->pools_bytes[r->pool_index] += nwords * sizeof(__u32); crypto_digest_update(r->pools[r->pool_index], sg, 1);

if (r->pool_index == 0) {
    r->pool0_len += nwords*sizeof(__u32);
}
/* idx = (idx + r) mod ( (2^N)-1 ) */
r->pool_index = (r->pool_index + r->key[keyidx])
                      & ((1<<random_state->pool_number)-1);

/* first 8 bytes of the key are used, 8 * 8 = 64 bits */ keyidx = (keyidx + 1) & 7;

The add_entropy_words() function uses the first 8 bytes of the central pool to aggravate the predictability of where entropy goes. It's still a linear progression untill the central pool is re-keyed, then you don't know where it went. The central pool is reseeded every 0.1ms.

This causes problems of course, the hard upper bound of "we recover from state compromise in at most a factor of 64 times the rate of entropy inflow" is no longer non-deterministic. That is, it changes to "we expect to recover from state compromise in a factor of 64 times the rate of entropy inflow."

Not sure if this was caught or not, but <linux@>Anyway, every 32 cycles, a seed word is added to subpool 0, which is then immediately added to the main pool</linux@>. Entirely true however, every time other than the first seeding other pools will be adding words to the main pool as well.

Cheers,

JLC

Quoted 114 lines · On Thu, Apr 14, 2005 at 02:15:38PM -0000, [email protected] wrote:

Just to refersh everyone's memory as to the strengths and weaknesses of Fortuna...

First, a reminder that the design goal of /dev/random proper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power. If you want a weaker guarantee, use /dev/urandom.

I've heard a suggestion that something like /dev/urandom, but which blocks until it has received a minimum amount of seed material at least once, would be a nice thing. So boot-time crypto initialization can stall until it has achieved a minimum level of security.

The minimum could be measured two ways:
- Some reasonable default, like 256 bits, or
- (clever) the size of the read() request, which is presumably the key size that the user needs. This might be too subtle to explain to programmers, though.

Anyway, there are two main parts to Fortuna. The central "random pool", and the round-robin sub-pool system for reseeding the main pool.

Fortuna uses a "small pool, trust the crypto" central pool. /dev/random uses a large pool that is deliberately designed to be robust against failure of the crypto primitives. Indeed, the basic design just uses it as a uniform hash. Cryptographic strength is irrelevant to the information-theoretic guarantees.

This portion of Fortuna is at odds with /dev/random's design goals, but it could be replaced easily enough. It's not the clever part.

The "neat idea" in Fortuna is the round-robin sub-pool seeding technique, which attempts to avoid the entire issue of entropy estimation.

Now, for information-theoretic guarantees, entropy measurement is *required*. You cannot be information-theoretic secure unless you have received more seed entropy than you have produced output.

However, Fortuna has a different philosophy. This difference is why Fortuna will NEVER be an "exact drop-in replacement" for /dev/random, although it can do the job for /dev/urandom. There are important user-visible differences in the guarantees it makes. Someone may argue that the difference is immaterial in practice, but existence of a difference is indisputable.

It tries to divide up the seed entropy into sub-pools and hold off re-seeding the main pool until the sub-pool has accumulated enough entropy to cause "catastrophic reseeding" of the main pool, adding enough entropy at once that someone who had captured the prior state of the main pool would not be able (due to computational limits and the one-way nature of the pool output function) to reverse-engineer the post-state.

The way it schedules the additions, it doesn't know *which* re-seed of the main pool will be catastrophic, but it knows that it will be within a factor of 64 of the shortest time that's possible.

However, it possible to come up with some pathological entropy sources for which the standard Fortuna design completely fails to achieve that goal.

So Fortuna would be helped by some better understanding of what exactly makes it fail, so the discussion could move to whether real-world seed sources have those properties.

But until that understanding is gained, Fortuna is questionable.

Appendix: how to "break" Fortuna.

First, the standard assumptions: the "attacker" can collect arbitrary amounts of RNG output at any time, and can see all operations on the pool except for the value of the seed material.

In particular, if the attacker's uncertainty about the pool's state is small, she can collect enough output to distinguish all the possibilities and attempt a brute-force computation to recover the unknown state information.

Finally, assume the attacker knows the full initial state of the generator.

For a classic 32-subpool Fortuna, let the seed be a 32-bit integer. Every time a new seed is produced, shift the previous value and insert a fresh random bit. Thus, the seed does deliver 1 bit of entropy per sample, which should make for a secure source.

If you want to be cruel, encrypt that seed with a strong cipher known only to the attacker before producing output. That keeps the nature of the seed from the Fortuna implementation.

Anyway, every 32 cycles, a seed word is added to subpool 0, which is then immediately added to the main pool. An attacker who knows the prior state of the main pool can attempt a brute-force search for the 32 bits of the seed word in a reasonable period of time.

Because of the shifting property, an attacker who knows the seeds added to pool 0 at times t and t+32 can also deduce, with perfect accuracy, the seeds added to the other 31 pools at times t+1 through t+31.

The result being that the other subpools, which are supposed to be hoarding secret information unknown to the attacker, are actually being seeded with bits known to the attacker.

The ultimate result is that catastrohpic reseeding never takes place. If we could somehow separate the "fresh" entropy in the input samples from the "holdover" material, the problem would go away, but that's an entropy measurement problem!

Until this cloud is dissipated by further analysis, it's not possible to say "this is shiny and new and better; they's use it!" in good conscience.

#2 lore raw
Quoted 3 lines

Waiting for 256bits of entropy before outputting data is a good goal. Problem becomes how do you measure entropy in a reliable way? This had me lynched last time I asked it so I'll stop right there.

It's a problem. Also, with the current increase in wireless keyboards and mice, that source should possibly not be considered secure any more.

On the other hand, clock jitter in GHz clocks is a *very* rich source of seed material. One rdtsc per timer tick, even accounted for at 0.1 bit per rdtsc (I think reality is more like 3-5 bits) would keep you in clover.

Quoted 5 lines

I'll not make any claim that random-fortuna.c should be mv'd to random.c, the patch given allows people to kernel config it in under the Cryptographic Options menu. Perhaps a disclaimer in the help menu would be in order to inform users that Fortuna has profound consequences for those expecting Info-theoretic /dev/random?

I don't mean to disparage you efforts, but then what's the upside to the resultant code maintenance hassles? Other than hack value, what's the advantage of even offering the choice? An option like that is justified when the two options have value for different people and it's not possible to build a single merged solutions that satisfies both markets.

Also, Ted very deliberately made /dev/random non-optional so it could be relied on without a lot of annoying run-time testing. Would a separate /dev/fortuna be better?

Quoted 3 lines

The case where an attacker has some small amount of unknown in the pool is a problem that effects BOTH random-fortuna.c and random.c (and any other replacement for that matter). Just an FYI.

Yes, but entropy estimation is supposed to deal with that. If the attacker is never allowed enough information out of the pool to distinguish various input states, the output is secure.

Quoted 2 lines

As for the "shifting property" problem of an attacker controlling some input to the pooling system, I've tried to get around this:

(Code that varies the pool things get added to based on r->key[i++ & 7])

Quoted 4 lines

The add_entropy_words() function uses the first 8 bytes of the central pool to aggravate the predictability of where entropy goes. It's still a linear progression untill the central pool is re-keyed, then you don't know where it went. The central pool is reseeded every 0.1ms.

You need to think more carefully. You're just elaborating it without adding security. Yes, the attacker *does* know! The entire underlying assumption is that the attacker knows the entire initial state of the pool, owing to some compromise or another.

The assumption is that the only thing the attacker doesn't know is the exact value of the incoming seed material. (But the attacker does have an excellent model of its distribution.)

Given that, the attacker knows the initial value of the key[] array, and thus knows the order in which the pools are fed. The question then arises, come next reseed, can the attacker (with a small mountain of computers, able to brute-force 40-bit problems in the blink of an eye) infer the *complete* state of the pool from the output.

The confusion is over the word "random". In programming jargon, the word is most often used to mean "arbitrary" or "the choice doesn't matter". But that doesn't capture the idea of "unpredictable to a skilled and determined opponent" that is needed in /dev/random.

So while the contents of key[] may be "random-looking", they're not *unpredictable*, any more than the digits of pi are.

The attacker just has to, after each reseeding, brute-force the seed bits fed to the (predictable) pools chosen to mix in, and then use that information to infer the seeds added to the not-selected pools.

If the attacker's uncertainty about the state of some of the subpools increases to the catastrophic reseeding level, then the Fortuna design goal is achieved.

If the seed samples are independent, then it's easy to see that the schedule works.

But if the seed samples are correlated, it gets a lot trickier.

#3 lore raw
In reply to Jean-Luc Cooke
Quoted 1 line · Jean-Luc Cooke

Info-theoretic randomness is a strong desire of some/many users, [..]

I don't know. Most of the time that I've seen users say they want information-theoretic randomness, I've gotten the impression that those users didn't really understand what information-theoretic randomness means, and their applications usually didn't need information-theoretic randomness in the first place.

As for those who reject computational security because of its unproven nature, they should perhaps be warned that any conjectured information-theoretic security of /dev/random is also unproven.

Personally, I feel the issue of information-theoretic security is a distraction. Given the widespread confusion about what information-theoretic security means, I certainly sympathize with why Jean-Luc Cooke left in the existing entropy estimation technique as a way of side-stepping the whole argument.

Anyway, the bottom line is I don't consider "information-theoretic arguments" as a very convincing reason to reject Cooke's proposal.

#4 lore raw
In reply to [email protected]
Quoted 4 lines · On Thu, Apr 14, 2005 at 02:15:38PM -0000, [email protected] wrote:

I've heard a suggestion that something like /dev/urandom, but which blocks until it has received a minimum amount of seed material at least once, would be a nice thing. So boot-time crypto initialization can stall until it has achieved a minimum level of security.

With a properly set up set of init scripts, /dev/random is initialized with seed material for all but the initial boot (and even that problem can be solved by having the distribution's install scripts set up /var/lib/urandom/random-seed after installing the system).

If the init scripts aren't set up correctly, then you're screwed, yes, but (a) all distributions that I know do the init scripts correctly, and the right of doing this is documented in random.c, and (b) if user space is screwed up in other ways, you can even worse off.

What if someone accesses the seed file directly before the machine boots? Well, either (a) they have broken root already, or (b) have direct access to the disk. In either case, the attacker with such powers can just has easily trojan an executable or a kernel, and you've got far worse problems to worry about that the piddling worries of (cue Gilbert and Sullivan overly dramatic music, <Oh, horror!>) the dreaded state-extension attack.

Quoted 6 lines

It tries to divide up the seed entropy into sub-pools and hold off re-seeding the main pool until the sub-pool has accumulated enough entropy to cause "catastrophic reseeding" of the main pool, adding enough entropy at once that someone who had captured the prior state of the main pool would not be able (due to computational limits and the one-way nature of the pool output function) to reverse-engineer the post-state.

Actually, if you check the current random.c code, you'll see that it has catastrophic reseeding in its design already.

Quoted 8 lines

So Fortuna would be helped by some better understanding of what exactly makes it fail, so the discussion could move to whether real-world seed sources have those properties.

But until that understanding is gained, Fortuna is questionable.
...
Until this cloud is dissipated by further analysis, it's not possible to say "this is shiny and new and better; they's use it!" in good conscience.

My big concern with Fortuna is that it really is the result of cryptographic masturbation. It fundamentally assumes that crypto primitives are secure (when the recent break of MD4, MD5, and now SHA1 should have been a warning that this is a Bad Idea (tm)), and makes assumptions that have no real world significance (assume the attacker has enough privileges that he might as well be superuser and can trojan your system to a fare-thee-well ---- now, if you can't recover from a state extension attack, your random number generator is fatally flawed.)

In addition, Frotuna is profligate with entropy, and wastes it in order to be able make certain claims of being able to recover from a state-extension attack. Hopefully everyone agrees that entropy collected from the hardware is precious (especially if you don't have special-purpose a hardware RNG), and shouldn't be wasted. Wasting collected entropy for no benefit, only to protect against a largely theoretical attack --- where if a bad guy has enough privileges to compromise your RNG state, there are far easier ways to compromise your entire system, not just the RNG --- is Just Stupid(tm).

- Ted

#5 lore raw
Quoted 7 lines

What if someone accesses the seed file directly before the machine boots? Well, either (a) they have broken root already, or (b) have direct access to the disk. In either case, the attacker with such powers can just has easily trojan an executable or a kernel, and you've got far worse problems to worry about that the piddling worries of (cue Gilbert and Sullivan overly dramatic music, <Oh, horror!>) the dreaded state-extension attack.

So the only remaining case is where an attacker can read the random seed file before boot but can't install any trojans. Which seems like an awfully small case. (Although in some scenarios, passive attacks are much easier to mount than active ones.)

Quoted 2 lines

Actually, if you check the current random.c code, you'll see that it has catastrophic reseeding in its design already.

Yes, I know. Fortuna's claim to fame is that it tries to achieve that without explicitly measuring entropy.

Quoted 9 lines

My big concern with Fortuna is that it really is the result of cryptographic masturbation. It fundamentally assumes that crypto primitives are secure (when the recent break of MD4, MD5, and now SHA1 should have been a warning that this is a Bad Idea (tm)), and makes assumptions that have no real world significance (assume the attacker has enough privileges that he might as well be superuser and can trojan your system to a fare-thee-well ---- now, if you can't recover from a state extension attack, your random number generator is fatally flawed.)

I'm not a big fan of Fortuna either, but the issues are separate. I agree that trusting crypto prmitives that you don't have to is a bad idea. If my application depends on SHA1 being secure, then I might as well go ahead and use SHA1 in my PRNG. But a kernel service doesn't know what applications are relying on.

(Speaking of which, perhaps it's time, in light of the breaking of MD5, to revisit the cut-down MD4 routine used in the TCP ISN selection? I haven't read the MD5 & SHA1 papers in enough detail to understand the flaw, but perhaps some defenses could be erected?)

But still, all else being equal, an RNG resistant to a state extension attack *is* preferable to one that's not. And the catastrophic reseeding support in /dev/random provides exactly that feature.

What Fortuna tries to do is sidestep the hard problem of entropy measurement. And that's very admirable. It's a very hard thing to do in general, and the current technique of heuristics plus a lot of derating is merely adequate.

If a technique could be developed that didn't need an accurate entropy measurement, then things would be much better.

Quoted 9 lines

In addition, Frotuna is profligate with entropy, and wastes it in order to be able make certain claims of being able to recover from a state-extension attack. Hopefully everyone agrees that entropy collected from the hardware is precious (especially if you don't have special-purpose a hardware RNG), and shouldn't be wasted. Wasting collected entropy for no benefit, only to protect against a largely theoretical attack --- where if a bad guy has enough privileges to compromise your RNG state, there are far easier ways to compromise your entire system, not just the RNG --- is Just Stupid(tm).

Just to be clear, I don't remember it ever throwing entropy away, but it hoards some for years, thereby making it effectively unavailable. Any catastrophic reseeding solution has to hold back entropy for some time.

And I think that, even in the absence of special-purpose RNG hardware, synchronization jitter on modern GHz+ CPUs is a fruitful source of entropy.

#6 lore raw
Quoted 4 lines · On Fri, Apr 15, 2005 at 01:34:17AM -0000, [email protected] wrote:

(Speaking of which, perhaps it's time, in light of the breaking of MD5, to revisit the cut-down MD4 routine used in the TCP ISN selection? I haven't read the MD5 & SHA1 papers in enough detail to understand the flaw, but perhaps some defenses could be erected?)

The ISN selection is there only to make it harder to accomplish TCP hijacking attacks from people who are on networking path between the source and destination. And you have to guess the ISI before the 3-way TCP handshake has been negotiated (or if you can stop the SYN packet in flight, before the other side times out the attempted TCP connection); and we also rekey every few minutes, so even if you do figure out the seed that we are using to generate the ISI (which is harder than just merely finding a hash collision; find the preimage that we are using as a seed given the only a portion of the crypto hash output), it becomes useless and you have to start all over again within a few minutes.

Furthermore, if you really cared about preventing TCP hijacks, the only real way to do this is to use Real Crypto. And these days, Cisco boxes support Kerberized telnets and ssh connections, which is the real Right Answer.

It might be possible to use a more expensive crypto primitive here, since CPU's have gotten so much faster, but the reason why we moved to MD4, and then cut it down, was because otherwise it was causing a noticeable difference in the speed we could establish TCP connections, and hence for certain network-based benchmarks.

Quoted 4 lines

Just to be clear, I don't remember it ever throwing entropy away, but it hoards some for years, thereby making it effectively unavailable. Any catastrophic reseeding solution has to hold back entropy for some time.

It depends on how often you reseed, but my recollection was that it was far more than years; it was *centuries*. And as far as I'm concerned, that's equivalent to throwing it away, especially given the pathetically small size of the Fortuna pools.

- Ted

#7 lore raw
Quoted 11 lines

The ISN selection is there only to make it harder to accomplish TCP hijacking attacks from people who are on networking path between the source and destination. And you have to guess the ISI before the 3-way TCP handshake has been negotiated (or if you can stop the SYN packet in flight, before the other side times out the attempted TCP connection); and we also rekey every few minutes, so even if you do figure out the seed that we are using to generate the ISI (which is harder than just merely finding a hash collision; find the preimage that we are using as a seed given the only a portion of the crypto hash output), it becomes useless and you have to start all over again within a few minutes.

Er... are you sure that's right? I think there are several mistakes there.

First of all, people *on* the netowrk path can just *see* the packets. Or modify them. Or whatever.
The point is to prevent hijacking by people *not* on the path. Such people can only blindly inject forged packets, and try to send "passwd\nhax0r\nhax0r\n" into an open telnet connection. Or sending FINs to DoS.

Such injection requires guessing the TCP sequence number. That depends on the ISN plus the number of bytes sent. Fortunately, some of the most interesting protocols to attack are interactive ones like telnet where the number of bytes sent is small and the uncertainty can be exhausted with a flood of packets.

The problem was to prevent someone from connecting to endpoints A and B and using the ISN they received to guess the ISNs that A and B would use to talk to each other. The classic TCP ISN algorithm just uses a global timestamp, so it's pretty easy.

Further, if I capture ISNs from A and B in the same rekey interval as the initiation of the connection I'm trying to hijack, and that connection proceeds slowly, then I have the lifetime of the connection to solve the crypto problem.

All that said, you are quite right (I had just figured it out myself, actually) that the required attack is a (first) preimage attack (albeit with partially known plaintext), not a collision, so the published collision attacks are not directly relevant. And the fact that the amount of hash output is not enough to determine the input key material so you have to make multiple probes with dirrecnt port numbers, and it's all masked by a high-speed clock that you can only come close to guessing the value of, makes it all even nastier for a would-be cryptanalyst.

Quoted 4 lines

Furthermore, if you really cared about preventing TCP hijacks, the only real way to do this is to use Real Crypto. And these days, Cisco boxes support Kerberized telnets and ssh connections, which is the real Right Answer.

It's just so high-level. While ipsec is the most general solution, setting it up is a PITA. I've often thought about trying to add a TCP option for stream encryption what could provide opportunistic encryption for everyone.

Quoted 5 lines

It might be possible to use a more expensive crypto primitive here, since CPU's have gotten so much faster, but the reason why we moved to MD4, and then cut it down, was because otherwise it was causing a noticeable difference in the speed we could establish TCP connections, and hence for certain network-based benchmarks.

Yes, I recall. I was more thinking that the MD5 and SHA0 problems were insufficient mixing between columns of bits, and even SHA1 still has the problem. Notice how much more aggressive the shifting is in the SHA256 key schedule.

As long as it's homebrew ad-hoc crypto, perhaps some study of the attacks could suggest a better key schedule than just using the key words in different orders and with different constants added.

Quoted 9 lines
Quoted 4 lines

Just to be clear, I don't remember it ever throwing entropy away, but it hoards some for years, thereby making it effectively unavailable. Any catastrophic reseeding solution has to hold back entropy for some time.

It depends on how often you reseed, but my recollection was that it was far more than years; it was *centuries*. And as far as I'm concerned, that's equivalent to throwing it away, especially given the pathetically small size of the Fortuna pools.

Well, subpool n is added to the main pool every 1/2^n additions of subpool 0. So with pool 0 added every 0.1 second (say), then subpool 31 is added every 6.8 years.

But the whole things depends on a minimum assumed entropy feed rate. The idea is to be sure that *some* subpool will hoard entropy long enough to cause catastrophic reseeding. You can reduce the number of subpools to fit any arbitrary bound.

E.g. if you think that 24 hours is long enough, and you have the same 0.1 second maximum reseed rate, then 21 pools will have pool 20 added every 29:07:37.6.

As I keep saying, the small size of the Fortuna pools is a separate matter, and can be changed without affecting the subpool structure that is Fortuna's real novel contribution. That was just what Niels and Bruce came up with to make the whole thing concrete.

#8 lore raw
Quoted 4 lines · On Fri, Apr 15, 2005 at 03:38:01PM -0000, [email protected] wrote:

First of all, people *on* the netowrk path can just *see* the packets. Or modify them. Or whatever.
The point is to prevent hijacking by people *not* on the path.

Yes, you're correct of course. Of course, I'll note that people who *not* on the path have to not only guess the ISN, but they also have to somehow know that there is a TCP connection between hosts A and B, and what ports they are using. Someone not on the path isn't necessarily going to know this, unless there are publically accessible SNMP-enabled routers that are overly free with this sort of information. (Loose lips sink ships!)

Quoted 4 lines

Further, if I capture ISNs from A and B in the same rekey interval as the initiation of the connection I'm trying to hijack, and that connection proceeds slowly, then I have the lifetime of the connection to solve the crypto problem.

True, although the longer it takes to break the crypto, the greater the uncertainty of how much data has gone across the connection, which makes the problem harder in other ways.

Quoted 9 lines
Quoted 4 lines

Furthermore, if you really cared about preventing TCP hijacks, the only real way to do this is to use Real Crypto. And these days, Cisco boxes support Kerberized telnets and ssh connections, which is the real Right Answer.

It's just so high-level. While ipsec is the most general solution, setting it up is a PITA. I've often thought about trying to add a TCP option for stream encryption what could provide opportunistic encryption for everyone.

But ssh is pretty easy, and even if you completely ignore the host key issue (to protect you against man-in-the-middle attacks), a simple diffie-helman type approach is plenty to protect you against the class of attacks which the randomized ISN buys you.

- Ted

#9 lore raw
In reply to Theodore Ts'o
Quoted 9 lines · Theodore Ts'o
Quoted 4 lines

Just to be clear, I don't remember it ever throwing entropy away, but it hoards some for years, thereby making it effectively unavailable. Any catastrophic reseeding solution has to hold back entropy for some time.

It depends on how often you reseed, but my recollection was that it was far more than years; it was *centuries*. And as far as I'm concerned, that's equivalent to throwing it away, especially given the pathetically small size of the Fortuna pools.

"pathetically" is an interesting term to call it. 256 bits is the most any one of the 32 pools can hold, true. And the n-th pool is used only once every 2^n times (where the first pool is the 0-th pool, hence it's used everytime).

2^31 * 0.1s reseeds, mean the 31st (aka. last) pool will be drawn from once every 6.8 years.

And the argument that "random.c doesn't rely on the strength of crypto primitives" is kinda lame, though I see where you're coming from. random.c's entropy mixing and output depends on the (endian incorrect) SHA-1 implementation hard coded in that file to be pre-image resistant. If that fails (and a few other things) then it's broken.

Fortuna depends on known cipher-text attacks on the cipher in use (in this case AES-256) and the digest algo in use (in this case SHA-256) to be pre-image resistant. Cryptographers like reducing things to known quantities, it may be flaw.

Once I set some personal things sorted out I'll take another crack at making /dev/fortuna with it's claws in random.c to feed it some of that entropy as [email protected] suggested.

JLC

#10 lore raw
Quoted 5 lines

And the argument that "random.c doesn't rely on the strength of crypto primitives" is kinda lame, though I see where you're coming from. random.c's entropy mixing and output depends on the (endian incorrect) SHA-1 implementation hard coded in that file to be pre-image resistant. If that fails (and a few other things) then it's broken.

/dev/urandom depends on the strength of the crypto primitives. /dev/random does not. All it needs is a good uniform hash.

Do a bit of reading on the subject of "unicity distance".

(And as for the endianness of the SHA-1, are you trying to imply something? Because it makes zero difference, and reduces the code size and execution time. Which is obviously a Good Thing.)

As for hacking Fortuna in, could you give a clear statement of what you're trying to achieve?

Do you like:
- The neat name,
- The strong ciphers used in the pools, or
- The multi-pool reseeding strategy, or
- Something else?

If you're doing it just for hack value, or to learn how to write a device driver or whatever, then fine. But if you're proposing it as a mainline patch, then could we discuss the technical goals?

I don't think anyone wants to draw and quarter *you*, but your code is going to get some extremely critical examination.

#11 lore raw
Quoted 3 lines · On Fri, Apr 15, 2005 at 04:50:36PM -0000, [email protected] wrote:

(And as for the endianness of the SHA-1, are you trying to imply something? Because it makes zero difference, and reduces the code size and execution time. Which is obviously a Good Thing.)

It just bugged me when I was reading random.c for the first time. First impressions and all.

Quoted 9 lines

As for hacking Fortuna in, could you give a clear statement of what you're trying to achieve?

Do you like:
- The neat name,
- The strong ciphers used in the pools, or
- The multi-pool reseeding strategy, or
- Something else?

Quoted 6 lines

If you're doing it just for hack value, or to learn how to write a device driver or whatever, then fine. But if you're proposing it as a mainline patch, then could we discuss the technical goals?

I don't think anyone wants to draw and quarter *you*, but your code is going to get some extremely critical examination.

The multi-pool reseeding strategy is what I find particular interesting. It's design that can fit neatly into my little head and I hope into the heads of others in the future. You can call it Bob or whatever you want, names doesn't matter to me. As for the ciphers/digest algos used, they are not if great concern to me, replace them with what you want. It's the design of the RNG itself that has my attention for the time being.

Ted and yourself are in the nest position to say "we understand random.c currently, and should be need arise, we can feel strong enough that we can find someone to take it over and go up the learning curve" and with a statement "we like the current RNG design now for mixing entropy and don't see the need to confuse people with alternatives to /dev/{u}random" and that'll be that.

I'll take my patch and not bother you anymore. I'm sure I've taken a lot of your time as it is.

Not to sound like a "I'm taking my ball and going home" - just explaining that I like the Fortuna design, I think it's elegant, I want it for my systems. GPL requires I submit changes back, so I did with the unpleasant side-dish of my opinion on random.c.

JLC

#12 lore raw

MErging e-mails, first from [email protected]:

Quoted 2 lines

You really ought to look at the _current_ implementation. There is no SHA1 code in random.c.

So I'm imagining the call to sha_transform() in 2.6.12-rc2's extract_buf()? The SHA1 code has been moved to lib/sha1.c, so there's no SHA1 code *lexically* in random.c, but that's a facile response; it's a cryptologically meaningless change.

The way it's done, the length ends up being byte-swapped twice. Here's an alternative sha1_final, moving the byte-swapping into sha1_update and saving a few cycles and a few bytes (234 -> 214 bytes with gcc-4.0 -O -fomit-frame-pointer on x86). I assume that moving the byte-swapping from sha_transform to sha1_update has no code size impact.

extern void sha_transform(u32 state[5], u32 temp[80]);

void sha1_final(void* ctx, u8 *out)

{
	struct sha1_ctx *sctx = ctx;
	u32 temp[SHA_WORKSPACE_WORDS];
	u64 count = sctx->count;
	u32 i, j, index;
	static const u8 padding[64] = { 0x80, };
	
	/* Pad out to 56 mod 64 */
	index = (((unsigned)sctx->count >> 3) + 8) & 0x3f;
	sha1_update(sctx, padding, 64-index); 
	
	/* Byte-swap the first 14 words of the buffer */
	for (i = 0; i < 14; i++)
		temp[i] = be32_to_cpu(((u32 const *)sctx->buffer)[i]);
		
	/* Append length, two native words, in big-endian word order. */
	((u32 *)sctx->buffer)[14] = (u32)(count >> 32);
	((u32 *)sctx->buffer)[15] = (u32)count; 
	
	/* And the final transformation */
	sha_transform(sctx->state, temp);
	
	/* Store state in digest */
	for (i = j = 0; i < 5; i++, j += 4) {
		u32 t2 = sctx->state[i]; 
		out[j+3] = t2 & 0xff; t2>>=8;
		out[j+2] = t2 & 0xff; t2>>=8;
		out[j+1] = t2 & 0xff; t2>>=8;
		out[j  ] = t2 & 0xff;
	}

	/* Wipe context */
	memset(temp, 0, sizeof temp);
	memset(sctx, 0, sizeof *sctx);
}

Anyway, back to the long-suffering [email protected]:

Quoted 5 lines
Quoted 2 lines

something? Because it makes zero difference, and reduces the code size and execution time. Which is obviously a Good Thing.)

It just bugged me when I was reading random.c for the first time. First impressions and all.

Interesting. Hopefully, further reflecton has shown you that the change has zero security implications. (For the same reason, cryptanalysts studying DES ignore the initial permutation.)

Quoted 6 lines
Quoted 5 lines

Do you like:
- The neat name,
- The strong ciphers used in the pools, or
- The multi-pool reseeding strategy, or
- Something else?

Quoted 6 lines

The multi-pool reseeding strategy is what I find particular interesting. It's design that can fit neatly into my little head and I hope into the heads of others in the future. You can call it Bob or whatever you want, names doesn't matter to me. As for the ciphers/digest algos used, they are not if great concern to me, replace them with what you want. It's the design of the RNG itself that has my attention for the time being.

Great, we agree! (Okay, almost.) My point about "the neat name" was a facetious straw-man. That's a metaphor for "some stupid non-technical reason". Newer is not neceaarily better. But your reason for liking Fortuna is not quite that shallow. Good.

Ted doesn't like Fortuna's pool design, I don't care for it much, but you agree it's not important. Great, no real point of contention there. With lots of subpools, they need to be smaller, but the details of the structure can be settled later.

But as I think I've said often enough, the sub-pool structure is what makes Fortuna interesting. *That* is Fortuna's contribution to the state of the art, and the neat idea worth stealing. We still agree!

However, there are a few issues, and if you'd like to address them, we can actually get closer to agreeing, or at least clearly stating what we disagree about.

1) Fortuna is trying to sidestep the hard problem of entropy measurement, to make it unnecessary. This is a laudable goal, but /dev/random's information-theoretic design goal precludes this simplification. It *has* to measure entropy. Are Fortuna's benefits sufficient to motivate a public interface change like that? If you can argue that the current entropy measurement is such crap that it's not actually delivering its promise anyway, that would be a good reason.

But as long as you *have* entropy measurement, you don't *need* Fortuna's elaborate scheme for avoiding it. You only need *one* sub-pool.

2) Fortuna tries to support such a wide range of entropy source rates, down to very low rates, that it sequesters some entropy for literally years. Ted thinks that's inexcusable, and I can't really disagree. This can be fixed to a significant degree by tweaking the number of subpools.

3) Fortuna's design doesn't actually *work*. The authors' analysis only works in the case that the entropy seeds are independent, but forgot to state the assumption. Some people reviewing the design don't notice the omission.

It's that assumption which lets to "divide up" the seed material among various sub-pools. Without it, seed information leaks from the sequestered sub-pools to the more exposed ones, decreasing the "value" of the sequestered pools.

I've shown a contrived pathological example, but I haven't managed to figure out how to characterize the leakage in a more general way. But let me give a realistic example.

Again, suppose we have an entropy source that delivers one fresh random bit each time it is sampled.

But suppose that rather than delivering a bare bit, it delivers the running sum of the bits. So adjacent samples are either the same or differ by +1. This seems to me an extremely plausible example.

Consider a Fortuna-like thing with two pools. The first pool is seeded with n, then the second with n+b0, then the first again with n+b0+b1. n is the arbitrary starting count, while b0 and b1 are independent random bits.

Assuming that an attacker can see the first pool, they can find n. After the second step, their uncertainty about the second pool is 1 bit, the value of b0.

But the third step is interesting. The attacker can see the value of b0+b1. If the sum is 0 or 2, the value of b0 is determined uniquely. Only in the case that b0+b1 = 1 is there uncertainty. So we have only *half* a bit of uncertainty (one bit, half of the time) in the second pool.

Where did the missing entropy go? Well, remember the Shannon formula for entropy, H(p_1,...,p_n) = - Sum(p_i * log(p_i)). If the log is to the base 2, the result is in bits.

Well, p_0 = 1/4, p_1 = 1/2, and p_2 = 1/4. The logs of those are -2, -1, and -2, respectively. So the sum works out to 2 * 1/4 + 1 * 1/2 + 2 * 1/4 = 1.5.

Half a bit of entropy has leaked from the second pool back into the first!

I probably just don't have enough mathematical background, but I don't currently know how to bound this leakage. In pathological cases, *all* of the entropy leaks into the lowest-order pool, at which point the whole elaborate structure of Fortuna is completely useless.

*That* is my big problem with Fortuna. If someone can finish the analysis and actually bound the leakage, then we can construct something that works. But I've pushed the idea around for a while and not figured it out.

Quoted 2 lines

I'll take my patch and not bother you anymore. I'm sure I've taken a lot of your time as it is.

And you've spent a lot of time preparing that patch. It's not a bad idea to revisit the ideas occasionally, but let's talk about the real *meat* of the issue.

If you think my analysis of Fortuna's issues above is flawed, please say so! If you disagree about the importance of the issues, that's worth discussing too, although I can't promise that such a difference of opinions will ever be totally resolved. But arguing about the relative importance of good and bad points is meaningful.

Ideally, we manage to come up with a solution that has all the good points.

The only thing that's frustrating is discussing it with someone who doesn't even seem to *see* the issues.

Quoted 4 lines

Not to sound like a "I'm taking my ball and going home" - just explaining that I like the Fortuna design, I think it's elegant, I want it for my systems. GPL requires I submit changes back, so I did with the unpleasant side-dish of my opinion on random.c.

Actually, the GNU GPL doesn't. It only requires that you give out the source if and when you give out the binary. You can make as many private changes as you like. (Search debian-legal for "desert island test".)

#13 lore raw
Quoted 1 line · On Sat, Apr 16, 2005 at 10:05:55AM -0000, [email protected] wrote:

Anyway, back to the long-suffering [email protected]:

;)

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

something? Because it makes zero difference, and reduces the code size and execution time. Which is obviously a Good Thing.)

It just bugged me when I was reading random.c for the first time. First impressions and all.

Interesting. Hopefully, further reflecton has shown you that the change has zero security implications. (For the same reason, cryptanalysts studying DES ignore the initial permutation.)

Yes I saw that the first time, just struck me as "why? why did I have to sit here and add a that to the litany of things to remember when it's so easy to just do it right?"

Guess I just see a different approach to software engineering, making it easier to analyse makes it easier to improve. You're 100% correct - security wise it doesn't matter.

Quoted 11 lines

1) Fortuna is trying to sidestep the hard problem of entropy measurement, to make it unnecessary. This is a laudable goal, but /dev/random's information-theoretic design goal precludes this simplification. It *has* to measure entropy. Are Fortuna's benefits sufficient to motivate a public interface change like that? If you can argue that the current entropy measurement is such crap that it's not actually delivering its promise anyway, that would be a good reason.

But as long as you *have* entropy measurement, you don't *need* Fortuna's elaborate scheme for avoiding it. You only need *one* sub-pool.

I agree with the statement:
"If the current entropy estimation does not over estimate and crypto
primitives don't fail to leak information, then we're OK"

What I've seen in my study of an older kernel (2.6.x) (the estimation scheme hasn't changed afaik) is it's very conservative from what I understand of my devices (keyboard,mouse not included, which is good. But they don't contribute as much randomness as disks and interrupts.)

Quoted 5 lines

2) Fortuna tries to support such a wide range of entropy source rates, down to very low rates, that it sequesters some entropy for literally years. Ted thinks that's inexcusable, and I can't really disagree. This can be fixed to a significant degree by tweaking the number of subpools.

Well, I'd take hording entropy for 7 years over trusting a general entropy accounting heuristic that is impossible to determine proper functioning. Assuming again that the problems of malicious entropy event injection is overcome. Havn't come up with anything yet on how to do this nicely.

Quoted 4 lines

3) Fortuna's design doesn't actually *work*. The authors' analysis only works in the case that the entropy seeds are independent, but forgot to state the assumption. Some people reviewing the design don't notice the omission.

...

Quoted 3 lines

Assuming that an attacker can see the first pool, they can find n. After the second step, their uncertainty about the second pool is 1 bit, the value of b0.

...

Quoted 1 line

Half a bit of entropy has leaked from the second pool back into the first!

...

Quoted 4 lines

*That* is my big problem with Fortuna. If someone can finish the analysis and actually bound the leakage, then we can construct something that works. But I've pushed the idea around for a while and not figured it out.

I feel this goes back to the round-robin event input system. Your argument of n, n+b0, n+b0+b1, ... makes sense, in the state compromise / state initialisation scenarios if the attacker can know for certain that they will see 1 out of every 32 inputs. If each of the pools has a 1:32 probability of landing into any of the pools, then the things get a lot harder.

Does this make sense? Ignoring the "where are you going to get a secure 1-in-32 RNG" issue.

If we look at this "slow-incremental entropy event input" situation with current random.c, do we get a similar result?

Assuming an attacker can see the secondary-pool (/dev/random output) and events {n, n+b0, b+b0+b1} enter primary-pool at times {t, t+t1, t+t1+t2}. If the rate is slow enough, then an accurate entropy estimation will stop anything from getting out, great.

"How does the entropy estimator measure entropy of the event?" becomes a crucial concern here. What if, by your leading example, there is 1/2 bit of entropy in each event? Will the estimator even account for 1/2 bits? Or will it see each event as 3 bits of entropy? How much of a margin of error can we tolerate?

/dev/random will output once it has at least 160 bits of entropy (iirc), 1/2 bit turning into 3 bits would mean that 160bits of output it effectively only 27 bits worth of true entropy (again, assuming the catastrophic reseeder and output function don't waste entropy).

It's a lot of "ifs" for my taste.
waste any entropy

Quoted 13 lines
Quoted 2 lines

I'll take my patch and not bother you anymore. I'm sure I've taken a lot of your time as it is.

And you've spent a lot of time preparing that patch. It's not a bad idea to revisit the ideas occasionally, but let's talk about the real *meat* of the issue.

If you think my analysis of Fortuna's issues above is flawed, please say so! If you disagree about the importance of the issues, that's worth discussing too, although I can't promise that such a difference of opinions will ever be totally resolved. But arguing about the relative importance of good and bad points is meaningful.

Quoted 4 lines

Ideally, we manage to come up with a solution that has all the good points.

The only thing that's frustrating is discussing it with someone who doesn't even seem to *see* the issues.

Well, I'll do what I can then. I understand your position and do my best to explain in the thread in LKML.

Quoted 4 lines

Actually, the GNU GPL doesn't. It only requires that you give out the source if and when you give out the binary. You can make as many private changes as you like. (Search debian-legal for "desert island test".)

Humm, must be confused with another license then. One that effects my company required we submit back to the authors, so we just assumed that to be the case for all of them and save the legal fees.

JLC

#14 lore raw
Quoted 3 lines

Yes I saw that the first time, just struck me as "why? why did I have to sit here and add a that to the litany of things to remember when it's so easy to just do it right?"

Huh? Why? Because it's faster and less code, that's why. In what conceivable way is it NOT right?

On little-endian machines, we define the mixing function to the the bit-reversed hash of the bit-reversed pool. We could just as easily store the entire pool bit-reversed and bit-reverse the inputs before mising them in, and use stock SHA1.

Since we don't need to interoperate with anybody, details like bit-ordering conventions are at the implementor's convenience.

The entire transformation has zero cryptological impact, so do it with less code. You don't *have* to remember it, any more than you have to remember whether I incremented the loop counter with i++, ++i, i += 1, or i = i+1. It's SHA-1, and all the security properties still apply.

Quoted 3 lines

Guess I just see a different approach to software engineering, making it easier to analyse makes it easier to improve. You're 100% correct - security wise it doesn't matter.

I don't even see how it's any harder to analyze. Any more than it matters for most algorithm analysis whether the numbers are stored in binary or decimal, or whether the loop counter is called i or j.

Quoted 3 lines

I agree with the statement:
"If the current entropy estimation does not over estimate and crypto
primitives don't fail to leak information, then we're OK"

Er.. "if the crypto primitives don't fail TO leak information"? I'm not quite sure I follow...

Quoted 10 lines
Quoted 5 lines

2) Fortuna tries to support such a wide range of entropy source rates, down to very low rates, that it sequesters some entropy for literally years. Ted thinks that's inexcusable, and I can't really disagree. This can be fixed to a significant degree by tweaking the number of subpools.

Well, I'd take hording entropy for 7 years over trusting a general entropy accounting heuristic that is impossible to determine proper functioning. Assuming again that the problems of malicious entropy event injection is overcome. Havn't come up with anything yet on how to do this nicely.

The problem is that it's spectacularly unlikely that the computer will still be running in 7 years. Any entropy put into that pool is effectively lost *permanently*.

But maybe we can come to a compromise like 24 hours.

Plus, even a crude entropy estimate can do better.
Suppose we want do to 128-bit catastrophic reseeding. But we don't trust our entropy estimator. Still, we think it's within a factor of 100 of being correct. So we keep 8 subpools. The first is dumped into the main pool when we estimate it holds 128 bits. The second, when the extimate reaches 256. Etc, until the eighth, which we wait for 16K bits - the 128 bits we want plus a factor-of-128 safety margin.

And that only requires 8 pools, not 32.

(Still, unless our 8th pool can actually hold 16 kbits = 2048 bytes, we're still wasting lots of entropy in the case that our entropy estimator is correct. And it's already pretty damn conservative by design.)

Quoted 6 lines

I feel this goes back to the round-robin event input system. Your argument of n, n+b0, n+b0+b1, ... makes sense, in the state compromise / state initialisation scenarios if the attacker can know for certain that they will see 1 out of every 32 inputs. If each of the pools has a 1:32 probability of landing into any of the pools, then the things get a lot harder.

Yes, but if you had a way to get 5 uniform random bits the attacker didn't know, the entire issue would be trivial; just keep getting 5 random bits until you have as much as you need.

Quoted 2 lines

Does this make sense? Ignoring the "where are you going to get a secure 1-in-32 RNG" issue.

I have a really hard time letting go of the latter, but let me think...

No, I don't see how it helps more than the 5 random bits you're giving yourself for free. After any given subpool-0-to-main-pool transfer, the attacker can easily see if subpool 0 was reseeded or not. If it was, we can brute-force the seed. With enough seeds at known sequence positions, and high enough serial correlations, we can deduce all the intermediate seeds. Now the only uncertainty is which other pools they got added to.

Which is the 5 bits of uncertainty you're giving yourself for free.

Quoted 4 lines

Assuming an attacker can see the secondary-pool (/dev/random output) and events {n, n+b0, b+b0+b1} enter primary-pool at times {t, t+t1, t+t1+t2}. If the rate is slow enough, then an accurate entropy estimation will stop anything from getting out, great.

That's the hope.

Quoted 5 lines

"How does the entropy estimator measure entropy of the event?" becomes a crucial concern here. What if, by your leading example, there is 1/2 bit of entropy in each event? Will the estimator even account for 1/2 bits? Or will it see each event as 3 bits of entropy? How much of a margin of error can we tolerate?

H'm... the old code *used* to handle fractional bits, but the new code seems to round down to the nearest bit. May have to get fixed to handle low-rate inputs.

As for margin of error, any persistent entropy overestimate is Bad. a 6-fold overestimate is disastrous.

What we can do is refuse to drain the main pool below, say, 128 bits of entropy. Then we're safe against any *occasional* overestimates as long as they don't add up to 128 bits.

Quoted 6 lines

/dev/random will output once it has at least 160 bits of entropy (iirc), 1/2 bit turning into 3 bits would mean that 160bits of output it effectively only 27 bits worth of true entropy (again, assuming the catastrophic reseeder and output function don't waste entropy).

It's a lot of "ifs" for my taste.

/dev/random will output once it has as many bits of entropy as you're asking for. If you do a 20-byte read, it'll output once it has 160 bits. If you do a 1-byte read, it'll output once it has 8 bits.

#15 lore raw
Quoted 9 lines · On Sat, Apr 16, 2005 at 05:16:22PM -0000, [email protected] wrote:
Quoted 5 lines

"How does the entropy estimator measure entropy of the event?" becomes a crucial concern here. What if, by your leading example, there is 1/2 bit of entropy in each event? Will the estimator even account for 1/2 bits? Or will it see each event as 3 bits of entropy? How much of a margin of error can we tolerate?

H'm... the old code *used* to handle fractional bits, but the new code seems to round down to the nearest bit. May have to get fixed to handle low-rate inputs.

I don't believe that was ever true, though it can fairly trivially be added. JLC, please note that entropy estimation is much more conservative now than it was a month ago.

Quoted 6 lines

As for margin of error, any persistent entropy overestimate is Bad. a 6-fold overestimate is disastrous.

What we can do is refuse to drain the main pool below, say, 128 bits of entropy. Then we're safe against any *occasional* overestimates as long as they don't add up to 128 bits.

I've been moving in that direction already, most of the infrastructure is already in place.

Quoted 10 lines
Quoted 6 lines

/dev/random will output once it has at least 160 bits of entropy (iirc), 1/2 bit turning into 3 bits would mean that 160bits of output it effectively only 27 bits worth of true entropy (again, assuming the catastrophic reseeder and output function don't waste entropy).

It's a lot of "ifs" for my taste.

/dev/random will output once it has as many bits of entropy as you're asking for. If you do a 20-byte read, it'll output once it has 160 bits. If you do a 1-byte read, it'll output once it has 8 bits.

That's not quite right. It needs 8 bits in the relevant output pool. Failing that, it needs 64 bits in the input pool to reseed the output pool. In the case of /dev/urandom, it needs 128 bits in the input pool, it always leaves enough for /dev/random to reseed.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#16 lore raw
In reply to [email protected]
Quoted 8 lines · On Sat, Apr 16, 2005 at 10:05:55AM -0000, [email protected] wrote:

MErging e-mails, first from [email protected]:

Quoted 2 lines

You really ought to look at the _current_ implementation. There is no SHA1 code in random.c.

So I'm imagining the call to sha_transform() in 2.6.12-rc2's extract_buf()? The SHA1 code has been moved to lib/sha1.c, so there's no SHA1 code *lexically* in random.c, but that's a facile response; it's a cryptologically meaningless change.

No, it's exactly to the point: he's forked random.c before a large set of changes that he needs to be aware of. The SHA1 code is now shared by cryptolib and obviously no longer suffers from the (non-existent) weakness he referenced.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#17 lore raw
In reply to [email protected]
Quoted 4 lines · linux

3) Fortuna's design doesn't actually *work*. The authors' analysis only works in the case that the entropy seeds are independent, but forgot to state the assumption. Some people reviewing the design don't notice the omission.

Ok, now I understand your objection. Yup, this is a real objection. You are right to ask questions about whether this is a reasonable assumption.

I don't know whether /dev/random makes the same assumption. I suspect that its entropy estimator is making a similar assumption (not exactly the same one), but I don't know for sure.

I also don't know whether this is a realistic assumption to make about the physical sources we currently feed into /dev/random. That would require some analysis of the physics of those sources, and I don't have the skills it would take to do that kind of analysis.

Quoted 21 lines

Again, suppose we have an entropy source that delivers one fresh random bit each time it is sampled.

But suppose that rather than delivering a bare bit, it delivers the running sum of the bits. So adjacent samples are either the same or differ by +1. This seems to me an extremely plausible example.

Consider a Fortuna-like thing with two pools. The first pool is seeded with n, then the second with n+b0, then the first again with n+b0+b1. n is the arbitrary starting count, while b0 and b1 are independent random bits.

Assuming that an attacker can see the first pool, they can find n. After the second step, their uncertainty about the second pool is 1 bit, the value of b0.

But the third step is interesting. The attacker can see the value of b0+b1. If the sum is 0 or 2, the value of b0 is determined uniquely. Only in the case that b0+b1 = 1 is there uncertainty. So we have only *half* a bit of uncertainty (one bit, half of the time) in the second pool.

[..]

Quoted 2 lines

I probably just don't have enough mathematical background, but I don't currently know how to bound this leakage.

Actually, this example scenario is not a problem. I'll finish the analysis for you. Suppose that the adversary can observe the entire evolution of the first pool (its initial value, and all updates to it). Assume the adversary knows n. In one round (i.e., a pair of updates), the adversary learns the value of b0 + b1 (and nothing more!). In the next round, the adversary learns b0' + b1' -- and so on.

How many bits of uncertainty have been added to the second pool in each round? With probability 1/2, the uncertainty of the second pool remains unchanged. With probability 1/2, the uncertainty increases by exactly 1 bit. This means there are two classes of updates, and both classes are equally likely.

Suppose we perform 200 rounds of updates. Then we can expect about 100 of these updates to be of the second class. If the updates were split evently (50/50) between these two classes, the adversary would have 100 bits of uncertainty about the second pool. In general, we expect somewhere near 100 bits of uncertainty -- sometimes a bit more, sometimes a bit less, but the chances that it is a lot less than 100 bits of uncertainty are exponentially small.

Therefore, except for an event that occurs with exponentially small probability, the adversary will be left with many bits of uncertainty about the second pool. So this kind of source should not pose a serious problem for Fortuna, or for any two-pool solution.

If you want a better example of where the two-pool scheme completely falls apart, consider this: our source picks a random bit, uses this same bit the next two times it is queried, and then picks a new bit. Its sequence of outputs will look like (b0,b0,b1,b1,b2,b2,..,). If we alternate pools, then the first pool sees the sequence b0,b1,b2,.. and the second pool sees exactly the same sequence. Consequently, an adversary who can observe the entire evolution of the first pool can deduce everything there is to know about the second pool. This just illustrates that these multiple-pool solutions make some assumptions about the time-independence of their sources, or at least that the bits going into one pool don't have too much correlation with the bits going into the other pool.

#18 lore raw
In reply to [email protected]
Quoted 2 lines · linux

/dev/urandom depends on the strength of the crypto primitives. /dev/random does not. All it needs is a good uniform hash.

That's not at all clear. I'll go farther: I think it is unlikely to be true.

If you want to think about cryptographic primitives being arbitrarily broken, I think there will be scenarios where /dev/random is insecure.

As for what you mean by "good uniform hash", I think you'll need to be a bit more precise.

Quoted 1 line

Do a bit of reading on the subject of "unicity distance".

Yes, I've read Shannon's original paper on the subject, as well as many other treatments.

I stand by my comments above.

#19 lore raw
In reply to Jean-Luc Cooke
Quoted 5 lines · Jean-Luc Cooke

And the argument that "random.c doesn't rely on the strength of crypto primitives" is kinda lame, though I see where you're coming from. random.c's entropy mixing and output depends on the (endian incorrect) SHA-1 implementation hard coded in that file to be pre-image resistant. If that fails (and a few other things) then it's broken.

You really ought to look at the _current_ implementation. There is no SHA1 code in random.c.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#20 lore raw
In reply to Theodore Ts'o
Quoted 2 lines · Theodore Ts'o

With a properly set up set of init scripts, /dev/random is initialized with seed material for all but the initial boot [...]

I'm not so sure. Someone posted on this mailing list several months ago examples of code in the kernel that looks like it could run before those init scripts are run, and that looks like it might well be using /dev/*random before it has been seeded.

I never saw any response.

Quoted 3 lines

It fundamentally assumes that crypto
primitives are secure (when the recent break of MD4, MD5, and now SHA1 should have been a warning that this is a Bad Idea (tm)),

It looks to me like the recent attacks on MD4, MD5, and SHA1 do not endanger /dev/random. Those attacks affect collision-resistance, but it looks to me like the security of /dev/random relies on other properties of the hash function (e.g., pseudorandomness, onewayness) which do not seem to be threatened by these attacks. But of course this is a complicated business, and maybe I overlooked something about the way /dev/random uses those hash functions. Did I miss something?

As for which threat models are realistic, I consider it more likely that my box will be hacked in a way that affects /dev/random than that SHA1 will be broken in a way that affects /dev/random.

Quoted 1 line

In addition, Fortuna is profligate with entropy, [...]

Yup.

#21 lore raw
In reply to Theodore Ts'o
Quoted 2 lines · Theodore Ts'o

With a properly set up set of init scripts, /dev/random is initialized with seed material for all but the initial boot

What about CD-ROM based distros (e.g., Knoppix), where every boot is the initial boot?

Quoted 3 lines

(and even that problem can be solved by having the distribution's install scripts set up /var/lib/urandom/random-seed after installing the system).

Could you elaborate? How should Knoppix seed its /dev/urandom?

Would reading 256 bits from /dev/random and writing them to /dev/urandom do the job?

- Pat

#22 lore raw
In reply to [email protected]
Quoted 3 lines

First, a reminder that the design goal of /dev/random proper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power.

I am skeptical.
I have never seen any convincing evidence for this claim, and I suspect that there are cases in which /dev/random fails to achieve this standard.

And it seems I am not the only one. See, e.g., Section 5.3 of:
http://eprint.iacr.org/2005/029

Fortunately, it doesn't matter whether /dev/random provides information-theoretic security. I have reasonable confidence that it provides computational security, and that is all that applications need.

#23 lore raw

[please reply to all when posting to lkml]

Quoted 11 lines · David Wagner
Quoted 3 lines

First, a reminder that the design goal of /dev/random proper is information-theoretic security. That is, it should be secure against an attacker with infinite computational power.

I am skeptical.
I have never seen any convincing evidence for this claim, and I suspect that there are cases in which /dev/random fails to achieve this standard.

And it seems I am not the only one. See, e.g., Section 5.3 of:
http://eprint.iacr.org/2005/029

Unfortunately, this paper's analysis of /dev/random is so shallow that they don't even know what hash it's using. Almost all of section 5.3 is wrong (and was when I read it initially).

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#24 lore raw
Quoted 6 lines · Matt Mackall
Quoted 1 line · David Wagner

http://eprint.iacr.org/2005/029

Unfortunately, this paper's analysis of /dev/random is so shallow that they don't even know what hash it's using. Almost all of section 5.3 is wrong (and was when I read it initially).

Yes, that is a minor glitch, but I believe all their points remain valid nonetheless. My advice is to apply the appropriate s/MD5/SHA1/g substitution, and re-read the paper to see what you can get out of it.

The problem is not that the paper is shallow; it is not. The source of the error is likely that this paper was written by theorists, not implementors. There are important things we can learn from them, and I think it is worth reading their paper carefully to understand what they have to offer.

I believe they raise substantial and deep questions in their Section 5.3. I don't see why you say Section 5.3 is all wrong. Can you elaborate? Can you explain one or two of the substantial errors you see?

#25 lore raw
Quoted 9 lines · David Wagner

Yes, that is a minor glitch, but I believe all their points remain valid nonetheless. My advice is to apply the appropriate s/MD5/SHA1/g substitution, and re-read the paper to see what you can get out of it.

The problem is not that the paper is shallow; it is not. The source of the error is likely that this paper was written by theorists, not implementors. There are important things we can learn from them, and I think it is worth reading their paper carefully to understand what they have to offer.

Since the paper was written by theorists, it appears that they didn't bother to read the implementation, but instead made assumptions from the man pages, as well as making the assumption that the man page (which was not written as a specification from which the code was implemented, and indeed was not even written by the code authors) was in fact an accurate representation of drivers/char/random.c.

So section 5.3 is essense a criticism of a straw man implementation based on a flawed reading of a flawed man page. Other than that, it's fine. :-)

Quoted 3 lines

I believe they raise substantial and deep questions in their Section 5.3. I don't see why you say Section 5.3 is all wrong. Can you elaborate? Can you explain one or two of the substantial errors you see?

For one, /dev/urandom and /dev/random don't use the same pool (anymore). They used to, a long time ago, but certainly as of the writing of the paper this was no longer true. This invalidates the entire last paragraph of Section 5.3.

The criticisms of the /dev/random man page do have some point, but the man page != the implementation. Also, the paper does not so much make an attack on the entropy estimator, so much as it casts asperions on it, while at the same time making the unspoken assumption that cryptographic primitives are iron-clad and unbreakable.

So I don't see any particular substantial deep questions, unless you count, "It is not at all clear that /dev/random ... provides information-theoretic security. Indeed, we suspect it sometimes doesn't" as a deep question. I don't.

- Ted

#26 lore raw
Quoted 4 lines · Theodore Ts'o

For one, /dev/urandom and /dev/random don't use the same pool (anymore). They used to, a long time ago, but certainly as of the writing of the paper this was no longer true. This invalidates the entire last paragraph of Section 5.3.

Ok, you're right, this is a serious flaw, and one that I overlooked. Thanks for elaborating. (By the way, has anyone contacted to let them know about these two errors? Should I?)

I see three remaining criticisms from their Section 5.3:
1) Due to the way the documentation describes /dev/random, many programmers will choose /dev/random by default. This default seems inappropriate and unfortunate.
2) There is a widespread perception that /dev/urandom's security is unproven and /dev/random's is proven. This perception is wrong. On a related topic, it is "not at all clear" that /dev/random provides information-theoretic security.
3) Other designs place less stress on the entropy estimator, and thus are more tolerant to failures of entropy estimation. A failure in the entropy estimator seems more likely than a failure in the cryptographic algorithms.
These three criticisms look right to me.

Apart from the merits or demerits of Section 5.3, the rest of the paper seemed to have some interesting ideas for how to simplify and possibly improve the /dev/random generator, which might be worth considering at some point.

#27 lore raw
Quoted 9 lines · David Wagner
Quoted 4 lines · Theodore Ts'o

For one, /dev/urandom and /dev/random don't use the same pool (anymore). They used to, a long time ago, but certainly as of the writing of the paper this was no longer true. This invalidates the entire last paragraph of Section 5.3.

Ok, you're right, this is a serious flaw, and one that I overlooked. Thanks for elaborating. (By the way, has anyone contacted to let them know about these two errors? Should I?)

I don't know of anyone who has contacted the authors yet. I haven't had the time, since I'm currently travelling at the moment.

Quoted 5 lines

I see three remaining criticisms from their Section 5.3:
1) Due to the way the documentation describes /dev/random, many programmers will choose /dev/random by default. This default seems inappropriate and unfortunate.
2) There is a widespread perception that /dev/urandom's security is

Quoted 8 lines

unproven and /dev/random's is proven. This perception is wrong. On a related topic, it is "not at all clear" that /dev/random provides information-theoretic security.
3) Other designs place less stress on the entropy estimator, and thus are more tolerant to failures of entropy estimation. A failure in the entropy estimator seems more likely than a failure in the cryptographic algorithms.
These three criticisms look right to me.

/dev/urandom is a cryptographic RNG, which is seeded from RNG. /dev/random uses a very similar cryptographic RNG, but it uses large pool to collect entropy, and uses an entropy estimator to limit the amount of data that can be extracted from the rng.

If the entropy estimator fails, /dev/random degrades to a cryptographic RNG. So it is not a disaster, whereas the approach described in this paper (which uses a non-cryptographic extractor) would seem to me to be *more* prone to catastrophically failure if the entropy estimator fails than /dev/random.

As to whether or not applications should be using /dev/random or /dev/urandom, /dev/random is no worse than /dev/urandom, as long as the application doesn't mind blocking when the entropy levels are too low. In practice, most of the time this situation doesn't arise since the appropriate way of using /dev/random is only to extract a small amount of entropy when needed to generate long-term keys, or when seeding a userspace cryptographic RNG for session keys.

- Ted