here we go ...
Team,
Here is a patch for the 2.6.8.1 Linux kernel which replaces the existing PRNG
in random.c with the Fortuna PRNG designed by Ferguson and Schneier (Practical
Cryptography). It is regarded in crypto circles as the current state-of-the-art
in cryptographically secure PRNGs.
Warning: Ted Ts'o and I talked about this at great length in sci.crypt and
in the end I failed on convince him that my patch was worth becoming main-line,
and he failed to convince me that status-quo is acceptable considering a better
solution exists.
I've made a page to capture my reasons and findings for this patch.
http://jlcooke.ca/random/
Please review this link. As a minimum the first table comparing status-quo
and Fortuna.
Changes in this patch (2 files):
include/linux/sysctl.h
+ added a RANDOM_DERIVE_SEED enum for the new
/proc/sys/kernel/random/derive_seed interface.
drivers/char/random.c
+ Kept all the event collection mechanisms, and interfaces.
+ Removed MD5-noPadding, SHA1-noPadding-endianIncorrect, halfMD4-noPadding (!?)
and twoThirdsMD4-noPadding (!?)
- Now uses Fortuna and the CryptoAPI (SHA-256, AES256)
+ Removed the one-of-a-kind (to my knowledge anyway) linear input mixing
function
- Now uses Fortuna and the CryptoAPI (SHA-256, AES256)
+ Removed the SHA1-feedback RNG output function
- Input/Output now uses the Fortuna PRNG
+ Removed the "HASH+HASH++++" system of SynCookies
- SynCookies now use block cipher CBC encryption
+ Removed the "HASH+++" system of TCPv4/v6 sequence number generation
- Now uses a block cipher CTR system to generate 32bit random value
+ Removed the "HASH" system of IPv4/v6 ID number generation
- Now uses a block cipher CTR system to generate 32bit random value
+ Removed entropy estimation
- Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like
PRNGs do to survive state compromise and other attacks.
- /dev/random is synonymous with /dev/urandom
- /proc/sys/kernel/random/entropy_avail is always the same as
/proc/sys/kernel/random/pool_size so ssh, dm-crypt and other apps who
block waiting for entropy don't seize up all together.
+ Added /proc/sys/kernel/random/derive_pool to save the pooling system's
state. This is a good thing because Fortuna will avoid using the entire
pooling system for output (this is a strength).
I expect much discussion on this. So let me lay out some facts:
- I have not broken /dev/random. I wrote this patch because I think we can
do better and Fortuna is the best there is right now.
- Current /dev/random is difficult to analyze because it doesn't use standards
compliant cryptographic primitives.
- Current /dev/random is slower then my proposed patch (5x on output, 2x on input)
- Current /dev/random's input mixing function is a linear function. This is bad in crypto-circles.
Why? Linear functions are communitive, associative and sometimes distributive.
Outputs from Linear function based PRNGs are very weak.
+ Note: Currently, output from /dev/random is feed-back into the input mixing
function making linear attacks of the PRNG more complex. But I fear
the combination of linear input mixing & knowing the feedback input
is a bad combination. Fortuna eliminates this and other theoretical
attacks. Read:
http://groups.google.com/groups?lr=&ie=UTF-8&th=2d80024f677ccadc&seekm=BemdnYeJjt2qMc3cRVn-jw%40comcast.com
- If need-be, I am prepared to take over maintainership of drivers/char/random.c
+ I don't want to push such a big change into Ted's lap, I am capable of taking
over for him.
I look forward to hearing from all of you.
JLC
On Thu, Sep 23, 2004 at 07:43:40PM -0400, Jean-Luc Cooke wrote:
>
> Here is a patch for the 2.6.8.1 Linux kernel which replaces the existing PRNG
> in random.c with the Fortuna PRNG designed by Ferguson and Schneier (Practical
> Cryptography). It is regarded in crypto circles as the current state-of-the-art
> in cryptographically secure PRNGs.
>
> Warning: Ted Ts'o and I talked about this at great length in sci.crypt and
> in the end I failed on convince him that my patch was worth becoming main-line,
> and he failed to convince me that status-quo is acceptable considering a better
> solution exists.
I've taken a quick look at your patch, and here are some problems with it.
0. Code style issues
Take a look at /usr/src/linux/Documentation/CodingStyle, and follow
it, please. In particular, pay attention to wrapping text
(particularly comment blocks) at 80 characters, max, and lose the
C++-style comments, please. Maintaining a good common comment
convention is good, too.
1. Don't leave out-of-date comments behind.
Your patch makes significant changes, but you haven't updated the
comments to reflect all of your changes. For example, the comments
for secure TCP sequence number generation are no longer correct. The
comments about the twisted GFSR document the original scheme, not the
Fortuna generator. If you're going to remove the code, remove the
comments too, or the resulting mess will be confusing and not very
maintainable.
2. The kernel will break if CONFIG_CRYPTO is false
The /dev/random driver is designed to be present in the system no
matter what. This was a design decision that was made long ago, to
simplify user space applications that could count on /dev/random being
present. This is a philosophical divide; your belief (as you put it
on your web site) seems to be: "If you want secure random numbers but
don't want crypto, then you don't want secure random numbers." The
problem is that someone may not want (or need) encryption algorithms
in the *kernel*, but they may still want secure random numbers in
*userspace*.
In any case, your patch is broken, since the kernel will simply fail
to build if CONFIG_CRYPTO is turned off. And simply making the
compilation of /dev/random conditional on CONFIG_CRYPTO isn't good
enough, since there are other portions of the kernel that assume that
random.c will be present. (For example, irqaction for providing
entropy input, and the TCP stack depends on it for secquence numbers.)
3. The TCP sequence numbers are broken
The requirements on secure sequence number is far more than just
"needs to be random-ish, but incresing [sic]". Read RFC 1948:
The choice of initial sequence numbers for a connection is not
random. Rather, it must be chosen so as to minimize the probability
of old stale packets being accepted by new incarnations of the same
connection [RFC 1185].
The increasing bit is also not guaranteed, since tmp[0] isn't masked
off. Not that it would really matter if it did; with only 8 bits
worth of COUNT_BITS, every 256 TCP connections you will wrap, and
expose that connection to the risk that stale packets being accepted.
I'm also a bit concerned about how much time AES takes over the
cut-down MD4, as this may affect networking benchmarks. (And we don't
need super-strength crypto here.)
As far as the Fortuna generator being "better", it really represents a
philosophical divide between what I call Crypto academics" and "Crypto
engineers". I won't go into that whole debate here, except to note
that the current /dev/random was designed with close consultation with
Colin Plumb, who wrote the random number generator found in PGP, and
indeed /dev/random is very close to that used in PGP. In discussions
on sci.crypt, there were those who argued on both side of this issue,
with such notables as Peter Gutmann lining up against Jean-Luc.
> + Removed entropy estimation
> - Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like
> PRNGs do to survive state compromise and other attacks.
Entropy estimation is a useful concept in that it attempts to limit
possible attacks caused by weaknesses in the crypto algorithms (such
what happened at this year's Crypto's conference, where MD4, MD5,
HAVAL, and SHA-0 were all weakened). The designed used by PGP and
/dev/random both limit the amount of reliance placed in the crypto
algorithms, where as Fortuna and Yarrow both assume that crypto
primitives are 100% strong. This is again a philosophical divide;
given that we have access to unpredicitability based on hardware
timings, we should limit the dependence on crypto algorithsm and to
design a system that is closer to "true randomness" as possible.
> - Current /dev/random's input mixing function is a linear function. This is bad in crypto-circles.
> Why? Linear functions are communitive, associative and sometimes distributive.
> Outputs from Linear function based PRNGs are very weak.
This is a red herring. /dev/random is not a linear function based
PRNG. We use a linear function for mixing, yes, but we do use SHA-1
as part of the output stage. And based on how we use SHA-1, even if
arbitrary collisions can be found in SHA-1 (as has been found in
SHA-0) this wouldn't cause a failure of /dev/random's security ---
this is part of the design philosophy of trying to avoid relying over
much on the security of the crypto primitives, as much as possible.
- Ted
On Fri, Sep 24, 2004 at 12:38:51AM -0400, Theodore Ts'o wrote:
> I've taken a quick look at your patch, and here are some problems with it.
>
>
> 0. Code style issues
>
> Take a look at /usr/src/linux/Documentation/CodingStyle, ...
Will-do. My bad.
> 1. Don't leave out-of-date comments behind.
>
> Your patch makes significant changes, but you haven't updated the
> comments to reflect all of your changes. ...
>
> 2. The kernel will break if CONFIG_CRYPTO is false
> matter what. This was a design decision that was made long ago, to
> simplify user space applications that could count on /dev/random ...
My naive point of view tells me either this design decision from days of
yore was not thought out properly (blasphemy!), or the cryptoapi needs to
be in kernel.
A compromise would be to have a primitive PRNG in random.c is no
CONFIG_CRYRPTO is present to keep things working.
> 3. The TCP sequence numbers are broken
I see. I'll make the change. Thank you.
> As far as the Fortuna generator being "better", it really represents a
> philosophical divide between what I call Crypto academics" and "Crypto
> engineers". I won't go into that whole debate here, except to note
> that the current /dev/random was designed with close consultation with
> Colin Plumb, who wrote the random number generator found in PGP, and
> indeed /dev/random is very close to that used in PGP. In discussions
> on sci.crypt, there were those who argued on both side of this issue,
> with such notables as Peter Gutmann lining up against Jean-Luc.
Agreed. This is why I've been dreading in posting the patch here. The
current /dev/random is good, possibly the best OS-level RNG out there
right now. Ted, if I've never said it before or ever again, you've done
a great job. But my first impressions when I dove in were:
- gah! Why did someone go through so much trouble to make this hard to
analyse?
- humm, why not use the cryptoapi if we want random data?
- why do linux users want information secure random numbers? Wouldn't
crypto-secure random numbers be what they really want?
+ this, I've learned, is not something you can argue well against. It's
a matter of taste ... like Brittany Spears.
I wanted something more structured running on my machines so I re-wrote
random.c to use Fortuna, no entropy estimators, and uses the cryptoapi.
For the record, I believe David Wagner saw the case for replacing the PRNG
with Fortuna holding water. Even removing the entropy estimator. But
coneeded that some people will want /dev/random to block, so let them eat
cake.
> > + Removed entropy estimation
> > - Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like
> > PRNGs do to survive state compromise and other attacks.
>
> Entropy estimation is a useful concept in that it attempts to limit
> possible attacks caused by weaknesses in the crypto algorithms (such
> what happened at this year's Crypto's conference, where MD4, MD5,
> HAVAL, and SHA-0 were all weakened). The designed used by PGP and
> /dev/random both limit the amount of reliance placed in the crypto
> algorithms, where as Fortuna and Yarrow both assume that crypto
> primitives are 100% strong. This is again a philosophical divide;
> given that we have access to unpredicitability based on hardware
> timings, we should limit the dependence on crypto algorithsm and to
> design a system that is closer to "true randomness" as possible.
What if I told the SHA-1 implementation in random.c right now is weaker
than those hashs in terms of collisions? The lack of padding in the
implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There
are billions of other examples.
The academic vs. engineer analogy works the other way as well. Fortuna's
security can be directly reduced to the security of the underlying
algorithms. This is a good thing. If the security of all applications
were reduced in the same way, the world would be a safer place (political
discussions not withstanding).
Vanilla random.c depends on SHA-1 be to be resistant to 1-st pre-image
attacks. Fortuna depends on this as well with SHA-256 (or whatever
other hash you put in there). The "folding over with XOR" method you
use to make random.c stronger can work against you as well. It comes
down to "I've changed SHA-1 to make it stronger". The logic question
becomes: "Then why doesn't everyone use it?"
JLC
On Fri, Sep 24, 2004 at 12:38:51AM -0400, Theodore Ts'o wrote:
> I'm also a bit concerned about how much time AES takes over the
> cut-down MD4, as this may affect networking benchmarks. (And we don't
> need super-strength crypto here.)
Oh,
openssl speed md4 aes shows:
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
md4 10708.72k 38240.96k 111170.47k 215872.85k 296828.93k
aes-128 cbc 32121.81k 32678.31k 33119.49k 33221.29k 33210.59k
aes-192 cbc 27915.92k 27868.52k 28418.08k 28677.12k 28721.15k
aes-256 cbc 24599.57k 25142.38k 25381.80k 25474.88k 25392.46k
Since we're using small blocks.
Attached is the patch with the problems Ted pointed out.
JLC
On Fri, Sep 24, 2004 at 08:54:57AM -0400, Jean-Luc Cooke wrote:
> On Fri, Sep 24, 2004 at 12:38:51AM -0400, Theodore Ts'o wrote:
> > 2. The kernel will break if CONFIG_CRYPTO is false
> > matter what. This was a design decision that was made long ago, to
> > simplify user space applications that could count on /dev/random ...
>
> My naive point of view tells me either this design decision from days of
> yore was not thought out properly (blasphemy!), or the cryptoapi needs to
> be in kernel.
There is some historical issues here --- namely, back in the early
1990's crypto still had significant export control issues, so we
didn't want to put any crypto code into the core kernel. So we didn't
have *any* encryption algorithms in the kernel at all. As to whether
or not cryptoapi needs to be mandatory in the kernel, the question is
aside from /dev/random, do most people need to have crypto in the
kernel? If they're not using ipsec, or crypto loop devices, etc.,
they might not want to have the crypto api in their kernel
unconditionally.
That aside, it's been demonstrated through a lot of experience, to the
point of it being a principle of software engineering, that optional
interfaces significantly complicate the users of that interface. In
order to encourage applications to use /dev/random, we wanted to make
it something that people could guarantee would be there. Random
numbers are important!
> A compromise would be to have a primitive PRNG in random.c is no
> CONFIG_CRYRPTO is present to keep things working.
Now *that*'s an extremely ill-considered idea. It means that an
application can without any warning, can have its strong source of
random numbers replaced with a weak random number generator. It
should be blatently obvious why this is a specatularily bad, horrific
idea.
> - why do linux users want information secure random numbers? Wouldn't
> crypto-secure random numbers be what they really want?
If they only want crypto-secure random numbers, they can do it in
userspace. Information secure random numbers is something the kernel
can provide, because it has low-level access to entrpoy sources. So
why not try to do the best possible job?
This by the way your complaint that /dev/random is "too slow" is a
complete red herring. When do you need more than 6 megs of random
numbers per second? And if the application just needs crypto-secure
random numbers, then the application can just extract 32 bytes or so
of randomness from /dev/random, and then do the CRNG in userspace, at
which point it will be even faster, since the data won't have to
copied from kernel to userspace.
> The design used by PGP and
> > /dev/random both limit the amount of reliance placed in the crypto
> > algorithms, where as Fortuna and Yarrow both assume that crypto
> > primitives are 100% strong. This is again a philosophical divide;
> > given that we have access to unpredicitability based on hardware
> > timings, we should limit the dependence on crypto algorithsm and to
> > design a system that is closer to "true randomness" as possible.
>
> What if I told the SHA-1 implementation in random.c right now is weaker
> than those hashs in terms of collisions? The lack of padding in the
> implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There
> are billions of other examples.
This is another red herring. First of all, we're not using the hash
as a MAC, or in any way where we would care about collisions.
Secondly, all of the places where we take a hash, we are always doing
it 16 bytes at a time, which is SHA's block size, so that there's no
need for any padding. And although you didn't complain about it,
that's also why we don't need to mix in the length in the padding;
extension attacks just simply aren't an issue, since the way we are
using the hash, that just simply an issue as far as the strength of
/dev/random.
> Vanilla random.c depends on SHA-1 be to be resistant to 1-st pre-image
> attacks. Fortuna depends on this as well with SHA-256 (or whatever
> other hash you put in there).
Incorrect, vanilla random.c does *not* depend on SHA-1's resistance to
1st pre-image attacks. In other words, even if you did have an oracle
which given a SHA-1 hash will give you a string which hashes to that
value, /dev/random's security properties would not be affected. Just
because you have *a* string which hashes to that value, that won't
help you find the contents of the pool.
That's my whole point. We have not changed SHA-1 to make it stronger;
we simply have carefully designed /dev/random to minimize its reliance
on crypto primitives, since we have so much entropy available to us
from the hardware. Fortuna, in contrast, has the property that if its
cryptoprimitives are broken, you might as well go home.
- Ted
If I submitted a patch that gave users the choice of swapping my Fortuna for
the current /dev/random, would you be cool with that then?
Our discussions on the matter always seem to move to areas where we can never
agree.
On Fri, Sep 24, 2004 at 01:43:01PM -0400, Theodore Ts'o wrote:
> > A compromise would be to have a primitive PRNG in random.c is no
> > CONFIG_CRYRPTO is present to keep things working.
>
> Now *that*'s an extremely ill-considered idea. It means that an
> application can without any warning, can have its strong source of
> random numbers replaced with a weak random number generator. It
> should be blatently obvious why this is a specatularily bad, horrific
> idea.
Easy fix - use CryptoAPI in our PRNGs and make it standard in the kernel. :)
You can see we're going in circles.
> If they only want crypto-secure random numbers, they can do it in
> userspace. Information secure random numbers is something the kernel
> can provide, because it has low-level access to entrpoy sources. So
> why not try to do the best possible job?
Sure. I hate Brittney Spears, but I will not deny people the choice.
> This by the way your complaint that /dev/random is "too slow" is a
> complete red herring. When do you need more than 6 megs of random
> numbers per second? And if the application just needs crypto-secure
> random numbers, then the application can just extract 32 bytes or so
> of randomness from /dev/random, and then do the CRNG in userspace, at
> which point it will be even faster, since the data won't have to
> copied from kernel to userspace.
I never complained that it was too slow. I've just noticed that when ever a
patch is submitted there are only 3 reasons to accept it:
- does it do something we havn't done before?
- does it do something faster / smaller?
- is it in someway better then what's there now?
I did my best to alliviate #2. #3 I've decided I'll never be able to
convince enough people for an all-out replacement. I'd be happy with a
configuration choice.
> > What if I told the SHA-1 implementation in random.c right now is weaker
> > than those hashs in terms of collisions? The lack of padding in the
> > implementation is the cause. HASH("a\0\0\0\0...") == HASH("a") There
> > are billions of other examples.
>
> This is another red herring. First of all, we're not using the hash
> as a MAC, or in any way where we would care about collisions.
> Secondly, all of the places where we take a hash, we are always doing
> it 16 bytes at a time, which is SHA's block size, so that there's no
> need for any padding. And although you didn't complain about it,
> that's also why we don't need to mix in the length in the padding;
> extension attacks just simply aren't an issue, since the way we are
> using the hash, that just simply an issue as far as the strength of
> /dev/random.
Woh there. Didn't you just say "see, these hashes are weakened. That's
bad". Now I just demonstrated the same thing with your SHA1 implementation
and you throw that "red-herring" phrase out again?
Point of history when breaking a hash:
- first a method for collisions is found
- then comes 2nd pre-image
- then comes complete inversion
MD4 case and point. Any how. I've given up trying to sell a replacement.
Can users have an option to switch?
JLC
On Fri, 24 Sep 2004, Theodore Ts'o wrote:
> have *any* encryption algorithms in the kernel at all. As to whether
> or not cryptoapi needs to be mandatory in the kernel, the question is
> aside from /dev/random, do most people need to have crypto in the
> kernel? If they're not using ipsec, or crypto loop devices, etc.,
> they might not want to have the crypto api in their kernel
> unconditionally.
As far as I know embedded folk do not want the crypto API to be mandatory,
although I think Matt Mackall wanted to try and make something work
(perhaps a subset just for /dev/random use).
- James
--
James Morris
<[email protected]>
On Fri, Sep 24, 2004 at 02:43:07PM -0400, James Morris wrote:
> On Fri, 24 Sep 2004, Theodore Ts'o wrote:
>
> > have *any* encryption algorithms in the kernel at all. As to whether
> > or not cryptoapi needs to be mandatory in the kernel, the question is
> > aside from /dev/random, do most people need to have crypto in the
> > kernel? If they're not using ipsec, or crypto loop devices, etc.,
> > they might not want to have the crypto api in their kernel
> > unconditionally.
>
> As far as I know embedded folk do not want the crypto API to be mandatory,
> although I think Matt Mackall wanted to try and make something work
> (perhaps a subset just for /dev/random use).
I want to move a couple critical hash algorithms into lib/ as has been done
with the CRC code. Then cryptoapi and /dev/random and a couple other
things (htree comes to mind) could share code without inflicting the
cryptoapi overhead and context limitations on everyone.
(currently about 4k messages behind on lkml, sorry for not chiming in sooner)
--
Mathematics is the supreme nostalgia of our time.
On Fri, 2004-09-24 at 14:43, James Morris wrote:
> On Fri, 24 Sep 2004, Theodore Ts'o wrote:
>
> > have *any* encryption algorithms in the kernel at all. As to whether
> > or not cryptoapi needs to be mandatory in the kernel, the question is
> > aside from /dev/random, do most people need to have crypto in the
> > kernel? If they're not using ipsec, or crypto loop devices, etc.,
> > they might not want to have the crypto api in their kernel
> > unconditionally.
>
> As far as I know embedded folk do not want the crypto API to be mandatory,
> although I think Matt Mackall wanted to try and make something work
> (perhaps a subset just for /dev/random use).
/dev/random used to be a source of high latencies, but Ingo's patches
fix this. There was not a lot of CPU overhead but the latency was was a
problem for serious audio use. But, audio is a unique set of
requirements, it's somewhere between desktop and embedded and hard-RT.
This could certainly be a problem for the embedded folks due to space or
CPU concerns, but the latency problem seems to be solved.
Lee
Jean-Luc Cooke wrote:
> If I submitted a patch that gave users the choice of swapping my Fortuna for
> the current /dev/random, would you be cool with that then?
I would certainly appreciate this option, given that my customers often
have very different ideas of what they need. I don't see how it hurts
the kernel to have a choice for /dev/random.
--
Scott Robert Ladd
site: http://www.coyotegulch.com
blog: http://chaoticcoyote.blogspot.com
On Fri, Sep 24, 2004 at 01:59:29PM -0400, Jean-Luc Cooke wrote:
> > If they only want crypto-secure random numbers, they can do it in
> > userspace. Information secure random numbers is something the kernel
> > can provide, because it has low-level access to entrpoy sources. So
> > why not try to do the best possible job?
>
> Sure. I hate Brittney Spears, but I will not deny people the choice.
The principle of avoiding kernel bloat means that if it doesn't have
to be done in the kernel, it should be done in userspace. If all
you're providing is an CRNG, the question then is why should it be
done in kernel, when it could be done just as easily in userspace, and
using /dev/random as its input?
> > This is another red herring. First of all, we're not using the hash
> > as a MAC, or in any way where we would care about collisions.
> > Secondly, all of the places where we take a hash, we are always doing
> > it 16 bytes at a time, which is SHA's block size, so that there's no
> > need for any padding. And although you didn't complain about it,
> > that's also why we don't need to mix in the length in the padding;
> > extension attacks just simply aren't an issue, since the way we are
> > using the hash, that just simply an issue as far as the strength of
> > /dev/random.
>
> Woh there. Didn't you just say "see, these hashes are weakened. That's
> bad". Now I just demonstrated the same thing with your SHA1 implementation
> and you throw that "red-herring" phrase out again?
No, what I'm saying is that crypto primitives can get weakened; this
is a fact of life. SHA-0, MD4, MD5, etc. are now useless as general
purpose cryptographic hashes. Fortuna makes the assumptions that
crypto primitives will never break, as it relies on them so heavily.
I have a problem with this, since I remember ten years ago when people
were as confident in MD5 as you appear to be in SHA-256 today.
Crypto academics are fond of talking about how you can "prove" that
Fortuna is secure. But that proof handwaves around the fact that we
have no capability of proving whether SHA-1, or SHA-256, is truly
secure.
In contrast, /dev/random doesn't have this dependence, which (a) is a
good thing, and (b) why it doesn't bother with the SHA finalization
step. It's simply not necessary.
- Ted
On Fri, Sep 24, 2004 at 05:34:52PM -0400, Theodore Ts'o wrote:
> > Woh there. Didn't you just say "see, these hashes are weakened. That's
> > bad". Now I just demonstrated the same thing with your SHA1 implementation
> > and you throw that "red-herring" phrase out again?
>
> No, what I'm saying is that crypto primitives can get weakened; this
> is a fact of life. SHA-0, MD4, MD5, etc. are now useless as general
> purpose cryptographic hashes. Fortuna makes the assumptions that
> crypto primitives will never break, as it relies on them so heavily.
> I have a problem with this, since I remember ten years ago when people
> were as confident in MD5 as you appear to be in SHA-256 today.
http://eprint.iacr.org/2004/207.pdf
SHA-256 showing indications of weakness. Fortuna's algorithms can be
replaced at compile-time. I may even consider doing them at run-time.
> Crypto academics are fond of talking about how you can "prove" that
> Fortuna is secure. But that proof handwaves around the fact that we
> have no capability of proving whether SHA-1, or SHA-256, is truly
> secure.
Our issues are that we are *both* handwaving.
JLC
I recently posted the following article on sci.crypt, which has a more
detailed analysis of the design of JLC's proposed patch to random.c
- Ted
From: [email protected] (Theodore Y. Ts'o)
Subject: Re: new /dev/random
Newsgroups: sci.crypt
Date: 27 Sep 2004 00:05:32 -0400
Organization: Massachusetts Institute of Technology
Paul Rubin <http://[email protected]> writes:
>Huh? JLC's patch *is* Fortuna.
Actually, it isn't Fortuna. But more on that in a moment....
>However, IMO, JLC's patch (Fortuna)
>should not go into the kernel in its present form, and the kernel
>maintainers should reject it. It should not be a configuration
>option. It has too much potential of screwing the user, until the
>entropy accounting is restored.
The problem is that Fortuna's design isn't really particularly
compatible with entropy accounting. Each pool only contains 256 bits,
and by definition, the pool can not possibly store more entropy than
that. Once you extract 256 bits, you have to wait a second before you
can drain whatever entropy might be in pool #1, then two seconds
before you can drain whatever entropy might be in pool #2, then four
seconds before you can drain whataver might be in pool #3, and so on.
This means that even if all of the pools are completely filled, in
order to extract 2048 bits of entropy (for an long-term RSA key pair,
for example), this would require waiting for a little over 4 minutes
(255 seconds, to be precise). To extract 4096 bits of entropy, we
would have to wait 18 hours, 12 minutes, and 15 seconds (65535 seconds).
Indeed, one of the complaints that I have about the whole Fortuna
design is that from the entropy perspective, 25% of the entropy is
stashed away in pools that will never be used for over six *months*,
with 50% of the pools never getting used until after 18 hours or more.
Of course in that time, those pools will get filled, refilled and
overfilled, many times over, uselessly wasting entropy. Entropy is a
precious resource; it should not be so thoughtlessly squandered.
.... but of course, waiting over 18 hours to before sufficient amounts
of entropy cascades through the pool structure in order to generate a
4096-bit RSA key isn't a problem with JLC's patch, because it doesn't
implement the 2^k second delay for each pool, as specified by the
Fortuna design. Instead, it reseeds at every call to extract_entropy,
and every 2^k reseeds, it uses a particular pool. But in order to
provide resistance to the state-extension attack --- which is the only
justification for replacing /dev/random's current algorithm with
Fortuna, and Fortuna's raison de etre --- you have to wait until a
pool has a sufficient amount of entropy in order to provide for a
catastrophic reseeding. Because the rate at which the pools are drawn
down is dependent on the extraction rate, not based on a time basis,
or based on some estimate of the amount of entropy collected in each
of the pools, JLC's proposed patch is vulnerable to state extension
attack. In other words, the proposed patch doesn't even do what it
sets out to do!!
P.S. Despite the fact that JLC's patch is vulnerable to the state
extension attack, because it does not faithfully implement the Fortuna
design, it still squanders entropy. In fact, because under normal
operations, reads to /dev/random are happen even less frequently than
once a second, over 50% of the collected entropy could be stored for
**years** before it is ever used, with the net result that the
high-level entropy pools will get overfilled, and the entropy wasted.
This is despite the fact that in the attack scenario, the attacker can
still force the high-order pools to be used before sufficient entropy
can be stored. So with respect to these two defects, it is the worst
of both worlds.
P.P.S. Despite the fact that JLC's patch defines a #define
RANDOM_RESEED_INTERVAL, which might lead one to believe that it is
using a time-based cascading, in fact, that #define is never used in
his patch. Despite the fact that a certain party has been seen
whining about "obfuscated" code being hard being "rude", I won't go
down that particular path. Nevertheless, the JLC's patch, with a
profusion of unsued #define's, and dead code from the original
/dev/random that is incompletely removed, has obfuscation not from the
subtle design standpoint, but from the sloppy coding perspective,
which IMHO is far worse (although of course, this can be corrected).
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Theodore Ts'o http://web.mit.edu/user/tytso/www/
Everybody's playing the game, but nobody's rules are the same!