Re: depleting the random number generator -- repeated state

David Honig writes: > One of the many uses of nitric acid. Ie, take random samples I thought this is mostly done by removing the bulk of the package polymer by grinding, and then subjecting the rest of it to a plasma etch. I haven't put a processed wafer into nitric acid yet, but I could imag

Re: depleting the random number generator -- repeated state

At 04:00 PM 7/30/99 -0700, Eugene Leitl wrote: >David Honig writes: > > > One of the many uses of nitric acid. Ie, take random samples > >I thought this is mostly done by removing the bulk of the package >polymer by grinding, and then subjecting the rest of it to a plasma >etch. I believe Marcus

Re: depleting the random number generator -- repeated state

At 03:34 PM 7/29/99 -0700, Eugene Leitl wrote: >Of course one would have to believe the CPU designer that it is true >noise, and not pseudorandom. One of the many uses of nitric acid. Ie, take random samples apart and look at them. There are commercial places that will do the lab work for you.

Re: depleting the random number generator -- repeated state

It would seem to be an excellent idea indeed to incorporate a register which gets filled with fresh entropy (from amplified circuit noise, for instance) at every clock tick into the CPU directly, particularly if it is to be used for embedded crypto gadgets. Of course one would have to believe th

Re: depleting the random number generator

-BEGIN PGP SIGNED MESSAGE- [ To: Perry's Crypto List, Bram, James, Dave ## Date: 07/28/99 ## Subject: Re: depleting the random number generator ] >Date: Mon, 26 Jul 1999 11:16:54 -0700 >To: bram <[EMAIL PROTECTED]> >From: "James A. Donald" <[EMAIL PR

Re: depleting the random number generator -- repeated state

At 2:51 PM -0400 7/28/99, Steven M. Bellovin wrote: >In message , "Arnold G. Reinhold" >writes >> I'd spin it the other way. The best approach to making nonces -- DH >> exponents, symetric keys, etc -- is to use a true source of randomness. >> That eliminates

Re: depleting the random number generator -- repeated state

On Wed, 28 Jul 1999, Jon Callas wrote: > I never directly add in entropy > deposits. I run a separate entropy pool that is hash-based, and > periodically tap that pool to update the secondary pool. I get really > nervous about adding entropy directly into a single pool. I also like to > capitaliz

Re: depleting the random number generator -- repeated state

In message , "Arnold G. Reinhold" writes : > > I'd spin it the other way. The best approach to making nonces -- DH > exponents, symetric keys, etc -- is to use a true source of randomness. > That eliminates one area of risk. However most computers do not co

Re: depleting the random number generator -- repeated state

At 10:49 AM -0400 7/28/99, Arnold G. Reinhold wrote: I believe the input mechanism Anonymous described *is* the RC4 key setup mechanism. In any case, I take Anonymous' remarks about the brittle nature of RC4 very seriously. I wouldn't mess with it just to double the entropy pool. If y

Re: depleting the random number generator -- repeated state

At 9:45 AM -0700 7/28/99, bram wrote: >On Tue, 27 Jul 1999, Eugene Leitl wrote: > >> So what's the magic with the entropy pool? Because current algorithms >> don't have enough state, and because the hidden structure of their >> pseudorandomness starts shining through after a while? > >The idea is

Re: depleting the random number generator -- repeated state

On Tue, 27 Jul 1999, Eugene Leitl wrote: > So what's the magic with the entropy pool? Because current algorithms > don't have enough state, and because the hidden structure of their > pseudorandomness starts shining through after a while? The idea is to make it so that if there is a failure, and

Re: depleting the random number generator -- repeated state

At 3:22 PM -0700 7/27/99, Jon Callas wrote: >I built a PRNG that used an RC4 variant as John Kelsey said. The thing is >also actually very Yarrow-like. I modified it later to use a state array >512 long instead of 256 long, just so it would have a larger entropy pool. > >When I added more entropy,

Re: depleting the random number generator -- repeated state

Jon Callas writes: > I'll also note that the state-loop that Anonymous described can easily be > detected and corrected. Given that this is a PRNG, not a cipher, > predictability is not a requirement (although you can algorithmically > correct in a way that will still make it a cipher). I do

Re: depleting the random number generator -- repeated state

I built a PRNG that used an RC4 variant as John Kelsey said. The thing is also actually very Yarrow-like. I modified it later to use a state array 512 long instead of 256 long, just so it would have a larger entropy pool. When I added more entropy, I added entropy using the same basic algorithm a

Re: depleting the random number generator -- repeated state

At 12:19 AM -0700 7/27/99, James A. Donald wrote: >-- >At 08:44 PM 7/26/99 +0200, Anonymous wrote: >> Even aside from active attacks, there is a possible problem based on >> the fact that RC4 can "almost" fall into a repeated-state situation. >> RC4's basic iteration looks like: >> >> (1) i +

Re: depleting the random number generator

At 10:35 AM -0700 7/26/99, bram wrote: >A lot of things include less entropy than one might assume. For example, >keystrokes contain essentially no entropy based on what letter was hit, >and the number of bits of entropy their timing includes is approximately >the logarithm of the number of time t

Re: depleting the random number generator

At 1:49 PM -0700 7/25/99, David Wagner wrote: >In article , >Arnold G. Reinhold <[EMAIL PROTECTED]> wrote: >> One nice advantage of using RC4 as a nonce generator is that you can easily >> switch back and forth between key setup and code byte generation. You

Re: depleting the random number generator

-- > > > Oh dear! This suggestion worries me. > > > Is it reasonable to expect this arrangement to be secure > > > against e.g. chosen-entropy attacks? On Mon, 26 Jul 1999, James A. Donald wrote > > Yes If the attacker knows exactly when the packets arrive (which he > > cannot) this cannot

Re: depleting the random number generator

On Mon, 26 Jul 1999, James A. Donald wrote: > > Oh dear! This suggestion worries me. > > Is it reasonable to expect this arrangement to be secure > > against e.g. chosen-entropy attacks? > > Yes: If the attacker knows exactly when the packets arrive (which he > cannot) this cannot give him any

Re: depleting the random number generator

On Sun, 25 Jul 1999, John Kelsey wrote: > Has anyone looked at this from a cryptanalytic point of > view? I think there are chosen-input attacks available if > you do this in the straightforward way. That is, if I get > control over some of your inputs, I may be able to alternate > looking at y

Re: depleting the random number generator

-- At 01:49 PM 7/25/99 -0700, David Wagner wrote: > > One nice advantage of using RC4 as a nonce generator is that you can easily > > switch back and forth between key setup and code byte generation. You can > > even do both at the same time. (There is no need to reset the index > > variables.

Re: depleting the random number generator

-BEGIN PGP SIGNED MESSAGE- [ To: Perry's Crypto List, James, Ben, Bram ## Date: 07/25/99 ## Subject: Re: depleting the random number generator ] >Date: Sun, 25 Jul 1999 11:01:00 -0400 >To: "James A. Donald" <[EMAIL PROTECTED]>, Ben Laurie > <

Re: depleting the random number generator

In article , Arnold G. Reinhold <[EMAIL PROTECTED]> wrote: > One nice advantage of using RC4 as a nonce generator is that you can easily > switch back and forth between key setup and code byte generation. You can > even do both at the same time. (There is no

Re: depleting the random number generator

At 8:35 AM -0700 7/21/99, James A. Donald wrote: >-- >At 09:24 PM 7/19/99 +0100, Ben Laurie wrote: >> So what you are saying is that you'd be happy to run your server >> forever on an inital charge of 128 bits of entropy and no more >> randomness ever? > >Yes, though I would probably prefer an

Re: depleting the random number generator

John Kelsey wrote: > > -BEGIN PGP SIGNED MESSAGE- > > At 09:24 PM 19-07-99 +0100, Ben Laurie wrote: > > >So what you are saying is that you'd be happy to run your > >server forever on an inital charge of 128 bits of entropy > >and no more randomness ever? > > > >Really? > > > >This mode

Re: depleting the random number generator

At 03:16 PM 7/21/99 -0500, John Kelsey wrote: >Suppose God, in a fit of budget-consciouness, decides to get >rid of all this wasteful hardware for generating random >numbers that are necessary for quantum mechanics, and >instead replaces them with a PRNG with a 256-bit seed. In >this case, all ha

Re: depleting the random number generator

At 03:16 PM 7/21/99 -0500, John Kelsey wrote: >Suppose God, in a fit of budget-consciouness, decides to get >rid of all this wasteful hardware for generating random >numbers that are necessary for quantum mechanics, and >instead replaces them with a PRNG with a 256-bit seed. In >this case, all ha

Re: depleting the random number generator

-BEGIN PGP SIGNED MESSAGE- At 09:24 PM 19-07-99 +0100, Ben Laurie wrote: >So what you are saying is that you'd be happy to run your >server forever on an inital charge of 128 bits of entropy >and no more randomness ever? > >Really? > >This model should work for all the servers in the wor

Re: depleting the random number generator

-- At 09:24 PM 7/19/99 +0100, Ben Laurie wrote: > So what you are saying is that you'd be happy to run your server > forever on an inital charge of 128 bits of entropy and no more > randomness ever? Yes, though I would probably prefer an initial charge of 1684 bits of entropy. (the number o

RE: depleting the random number generator

>= Original Message From David Honig <[EMAIL PROTECTED]> = [...] >Admittedly it may sound religious to claim that physical entropy >matters, when no one can tell the difference between true random & prng >bits (without the prng 'key'). But a prng *is* crackable >if you infer the internal

Re: depleting the random number generator

Bram, the *nix /dev/random code *does* accumulate a pool of 'physical' (interrupt, interrupt timing) entropy and stirs and extracts bits via a crypto secure hash (e.g., MD5 in FreeBSD). And you can easily expand this pool by modifying the code. But the pool is always finite; therefore depleteab

RE: depleting the random number generator

At 03:46 AM 7/19/99 -0400, Enzo Michelangeli wrote: >Sorry folks, but I can't understand where the problem is supposed to be. The >entropy of a pool is a measure of the information about its internal state >that we don't know: which is why in thermodynamics the same name is given to >the logari

Re: depleting the random number generator

Sandy Harris <[EMAIL PROTECTED]> writes: >> /dev/random uses SHA or MD5, so a complete break appears highly unlikely. >> But a special-case break, say in circumstances where the input entropy is >> temporarily exhausted so the attacker gets a look at N successive results >> where the pool does no

Re: depleting the random number generator

On Mon, 19 Jul 1999, Ben Laurie wrote: > > The brief summary of the above is that it's possible to simply replace > > /dev/random with something which doesn't deplete entropy and the problem > > will go away. And yes, it is possible to do that in a secure manner. > > So what you are saying is th

Re: depleting the random number generator

Enzo Michelangeli wrote: > Sorry folks, but I can't understand where the problem is supposed to be. The > entropy of a pool is a measure of the information about its internal state > that we don't know: which is why in thermodynamics the same name is given to > the logarithm of the number of (in

Re: depleting the random number generator

bram wrote: > > On Mon, 19 Jul 1999, Enzo Michelangeli wrote: > > > Sorry folks, but I can't understand where the problem is supposed to be. The > > entropy of a pool is a measure of the information about its internal state > > that we don't know: which is why in thermodynamics the same name is

RE: depleting the random number generator

On Mon, 19 Jul 1999, Enzo Michelangeli wrote: > Sorry folks, but I can't understand where the problem is supposed to be. The > entropy of a pool is a measure of the information about its internal state > that we don't know: which is why in thermodynamics the same name is given to > the logarit

Re: depleting the random number generator

David Honig wrote: > > Ben suggests using "hashcash" to prevent malicious depletion of the entropy > pool, > where the "hashcash" (hashes that are expensive to compute but cheap to > verify) > becomes the limiting resource instead of the server's MIPS. > > This prevents DoS attacks but doesn't s

Re: depleting the random number generator

On Sun, Jul 18, 1999 at 06:09:15PM -0400, Donald E. Eastlake 3rd wrote: > RFC 1750 recommends the Blum Blum Shub generator. Which is pretty slow- on the order of an RSA public key operation. A hardware RNG would be the best solution. It won't help the original poster now, but I think that hardw

RE: depleting the random number generator

Sorry folks, but I can't understand where the problem is supposed to be. The entropy of a pool is a measure of the information about its internal state that we don't know: which is why in thermodynamics the same name is given to the logarithm of the number of (invisible) microstates correspondi

Re: depleting the random number generator

At 09:28 PM 7/18/99 +0100, Ben Laurie wrote: >The obvious way to solve the underlying problem, as I've already said, >is to use hashcash. >Cheers, > >Ben. Hashcash is interesting in general environments - forcing the initiator of a transaction to burn some CPU keeps them from swamping you with a

Re: depleting the random number generator

David Honig wrote: > > At 04:45 PM 7/17/99 -0400, John Denker wrote: > >Hi Folks -- > > > >I have a question about various scenarios for an attack against IPsec by way > >of the random number generator. The people on the linux-ipsec mailing list > >suggested I bring it up here. > > >>..worries

Re: depleting the random number generator

RFC 1750 recommends the Blum Blum Shub generator. Donald From: bram <[EMAIL PROTECTED]> Date: Sat, 17 Jul 1999 16:18:20 -0700 (PDT) To: Eugene Leitl <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] In-Reply-To: <[EMAIL PROTECTED]> Message-ID: <[EMAIL PROTECTED]> Content-Type: TEXT/PLAIN; charset

Re: depleting the random number generator

On Sun, 18 Jul 1999, Bill Stewart wrote: > /dev/urandom will give you pseudo-random bits if it's run out of entropy, > so you've got the security risks inherent in that. > As David Honig points out, you can't avoid those alternatives, Yes you can, if there's a 'pool' of entropy in memory which

Re: depleting the random number generator

At 10:04 PM 7/17/99 -0700, Mike Brodhead wrote: >> Step 3a) If Whitney is getting key material from /dev/random, the result is >> a denial of service. All the IPsec tunnels will time out and will be >> replaced slowly or not at all, because of the entropy shortage. > >seems to me that the reaso

Re: depleting the random number generator

bram wrote: > > > Most of the fancy reseedable PRNG schemes people have come up with are > > > based on using secure hashes. > > > > They are sure validated, but are they the best we can do? MD5, the > > nonplusultra, really? > > The main reason for secure hashes being the primary primitive us

Re: depleting the random number generator

At 04:45 PM 7/17/99 -0400, John Denker wrote: >Hi Folks -- > >I have a question about various scenarios for an attack against IPsec by way >of the random number generator. The people on the linux-ipsec mailing list >suggested I bring it up here. >>..worries that /dev/random exhaustion -> DoS,

Re: depleting the random number generator

On Sat, 17 Jul 1999, Eugene Leitl wrote: > bram writes: > > > Most of the fancy reseedable PRNG schemes people have come up with are > > based on using secure hashes. > > They are sure validated, but are they the best we can do? MD5, the > nonplusultra, really? The main reason for secure has

Re: depleting the random number generator

-- At 04:45 PM 7/17/99 -0400, John Denker wrote: > Step 2) The attacker endlessly iterates step 1. This is easy. > AFAIK there is no useful limit on how often new applications can be > made. This quickly exhausts the entropy pool on Whitney. The attacker can only "exhaust" the entropy po

Re: depleting the random number generator

> Step 3a) If Whitney is getting key material from /dev/random, the result is > a denial of service. All the IPsec tunnels will time out and will be > replaced slowly or not at all, because of the entropy shortage. seems to me that the reason the denial of service attack works does not have an

Re: depleting the random number generator

On Sat, 17 Jul 1999, Eugene Leitl wrote: > Does anybody know how cellular automata perform re cryptographically > solid random number generators? They can crank out a lot of integers > with a minimum investment in instructions executed. Most of the fancy reseedable PRNG schemes people have come

Re: depleting the random number generator

bram writes: > I'm not sure if anybody's yarrowified /dev/random yet - I think someone > from coderpunks was working on it. Does anybody know how cellular automata perform re cryptographically solid random number generators? They can crank out a lot of integers with a minimum investment in in

Re: depleting the random number generator

bram writes: > Most of the fancy reseedable PRNG schemes people have come up with are > based on using secure hashes. They are sure validated, but are they the best we can do? MD5, the nonplusultra, really?

Re: depleting the random number generator

John Denker writes: > The bad part is that Whitney has already gobbled up quite a few > bits of entropy from /dev/random before the slightest bit of > authentication is attempted. You're presuming that you're using the standard Linux version of /dev/random. You could quite easily write a driv

Re: depleting the random number generator

On Sat, 17 Jul 1999, John Denker wrote: > I have a question about various scenarios for an attack against IPsec by way > of the random number generator. The people on the linux-ipsec mailing list > suggested I bring it up here. > > Step 3a) If Whitney is getting key material from /dev/random,

Re: depleting the random number generator

John Denker wrote: > I certainly hope these issues have been analyzed and brought under control. > Can somebody lend me a clue as to the status, and/or where I might read more > about it? If this list is not the optimal forum for discussing such > things, could somebody point me to a better one?