secure (proactive?) clock synchronization
We've been recently working on what seems like a neat new clock synchronization protocol, which will hopefully offer proactive security (recovery from penetrations, see http://www.hrl.il.ibm.com/proactive). Surprisingly, it also appears a very practical protocol. It has been some time since I last worked on clock synchronization, so I wonder, what is the state of the art - practical protocols (any substantially change in NTP recently or any serious alternative), and protocols designed to withstand attackers (of course I'll be esp. interested if there's anything with some recovery properties!!). Thanks for any pointers. Best Regards, Amir Herzberg Manager, E-Business and Security Technologies IBM Research - Haifa Lab (Tel Aviv Office) http://www.hrl.il.ibm.com New e-mail: [EMAIL PROTECTED] New Lotus notes mail: amir herzberg/haifa/ibm@IBMIL
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 corresponding to an (observed) macrostate. Now: if we extract bits from the generator, we cannot gain insight over the internal state and its evolution, because on the path of a well-designed RNG there is a one-way function whose inversion is not computationally feasible. If we can't increase our knowledge of the internal state, the entropy of the pool is not depleted at all; in particular, we don't gain any information about the bits that the next requestor (i.e., the victim of the attack) will get. Am I missing something? Enzo = Original Message From Ben Laurie [EMAIL PROTECTED] = 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 that /dev/random exhaustion - DoS, and /dev/urandom - PRNG after exhaustion.. You are correct. There is no way around this, except to add a true RNG to your server. With an open source OS, you can add this to the existing /dev/[u]random code That isn't a way around it, that just gives you higher speed randomness. The obvious way to solve the underlying problem, as I've already said, is to use hashcash. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "My grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first group; there was less competition there." - Indira Gandhi
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 hardware RNGs will become more common in the next year or two. Another solution besides those already mentioned is to use quality random bits to seed a good PRNG and then hash together with the PRNG output what random bits the machine can generate at the rate required. From: bram [EMAIL PROTECTED] Date: Sat, 17 Jul 1999 16:18:20 -0700 (PDT) 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 up with are based on using secure hashes. -Bram -- Eric Murray N*Able Technologieswww.nabletech.com (email: ericm at the sites lne.com or nabletech.com) PGP keyid:E03F65E5
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 solve the problem of a VPN server running out of cryto-quality randomness, which it could easily do under normal usage. I think we all agree that you can't fool mother nature (ie, entropy is conserved) and if your legitimate users are consuming too much randomness, you need a higher bandwidth source. That's true, of course, but the question was how to prevent the DoS. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "My grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first group; there was less competition there." - Indira Gandhi
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 given to the logarithm of the number of (invisible) microstates corresponding to an (observed) macrostate. Now: if we extract bits from the generator, we cannot gain insight over the internal state and its evolution, because on the path of a well-designed RNG there is a one-way function whose inversion is not computationally feasible. That's true, but not horribly obvious to most people, and the design of the random number gizmo isn't all that trivial. 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 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 world, of course (operating from a single initial charge of 128 bits shared between them). Are we all happy? Cheers, Ben. -- http://www.apache-ssl.org/ben.html "My grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first group; there was less competition there." - Indira Gandhi
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 (invisible) microstates corresponding to an (observed) macrostate. Now: if we extract bits from the generator, we cannot gain insight over the internal state and its evolution, because on the path of a well-designed RNG there is a one-way function whose inversion is not computationally feasible. If we can't increase our knowledge of the internal state, the entropy of the pool is not depleted at all; in particular, we don't gain any information about the bits that the next requestor (i.e., the victim of the attack) will get. Am I missing something? I think what you're missing is the (arguably appropriate) level of paranoia that requires the design remain plausibly secure even if the one-way function used is broken. /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 not change, the only difference is the intial value of the hash's internal variables? I don't think that's likely either, but I've much less confidence that it is impossible. If you want the thing to stand when the output hash breaks, you need enough input entropy and a good mixing function.
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 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? Well, I simplified a bit - it's a good idea to mix in more entropy whenever it's available just for good measure, and pool it to be introduced in large enough chunks to prevent continuation attacks, but the short answer is yes. -Bram
PGP encryption
Hi Folks, When implementing PGP base encryption, is this implementation MUST use symetrically Algorithms ?? Is it possible to use only the public/private key ? I would like more explanation about that! :o) Best regards, Hans...
DCSB: Ari Juels; Outsourcing MicroMint Coins, and X-Cash for Contingent Financial Instruments
--- begin forwarded text Date: Mon, 19 Jul 1999 10:51:32 -0400 To: [EMAIL PROTECTED], [EMAIL PROTECTED] From: Robert Hettinga [EMAIL PROTECTED] Subject: DCSB: Ari Juels; Outsourcing MicroMint Coins, and X-Cash for Contingent Financial Instruments Cc: Ari Juels [EMAIL PROTECTED] Sender: [EMAIL PROTECTED] Reply-To: Robert Hettinga [EMAIL PROTECTED] -BEGIN PGP SIGNED MESSAGE- The Digital Commerce Society of Boston Presents Dr. Ari Juels Senior Research Scientist RSA Laboratories Security Dynamics, Inc. MicroMint on the Cheap and Executable Financial Instruments Tuesday, August 3rd, 1999 12 - 2 PM The Downtown Harvard Club of Boston One Federal Street, Boston, MA We discuss two technologies that aim to facilitate electronic commerce in distributed environments under minimal assumptions of trust. First, we show how the MicroMint micropayment scheme of Rivest and Shamir can be broken up into a collection of small "puzzles". Distribution of these puzzles enables the minting operation for the scheme to be outsourced to a large group of untrusted computational devices. Additionally, we discuss a cryptographic technique that enables mobile agents to carry digital cash in such a way that they are secure against "pickpocketing". We refer to this technique as "X-cash" or "Executable digital cash". X-cash may also be used as the basis for creating digital financial instruments with flexibly defined properties. The first portion of the talk includes material to appear in the paper "Bread Pudding and Proofs of Work (POWs)" in Communications and Multimedia Security '99. The second portion of the talk draws on the paper "X-cash: Executable Digital Cash", which appeared in Financial Cryptography '98. Both papers are by Markus Jakobsson (Bell Laboratories) and Ari Juels (RSA Laboratories). Dr. Juels received his B.A. in Latin Literature and Mathematics from Amherst College in 1991, and his Ph.D. in Computer Science from the University of California at Berkeley in 1996. He subsequently joined RSA Laboratories, where he now holds the position of senior research scientist. His research interests span several areas of cryptography, with a special focus on protocols underlying and supporting financial applications. This meeting of the Digital Commerce Society of Boston will be held on Tuesday, August 3, 1999, from 12pm - 2pm at the Downtown Branch of the Harvard Club of Boston, on One Federal Street. The price for lunch is $32.50. This price includes lunch, room rental, various A/V hardware, and the speakers' lunch. The Harvard Club *does* have dress code: jackets and ties for men (and no sneakers or jeans), and "appropriate business attire" (whatever that means), for women. Fair warning: since we purchase these luncheons in advance, we will be unable to refund the price of your lunch if the Club finds you in violation of the dress code. We need to receive a company check, or money order, (or, if we *really* know you, a personal check) payable to "The Harvard Club of Boston", by Saturday, July 31st, or you won't be on the list for lunch. Checks payable to anyone else but The Harvard Club of Boston will have to be sent back. Checks should be sent to Robert Hettinga, 44 Farquhar Street, Boston, Massachusetts, 02131. Again, they *must* be made payable to "The Harvard Club of Boston", in the amount of $32.50. Please include your e-mail address so that we can send you a confirmation If anyone has questions, or has a problem with these arrangements (We've had to work with glacial A/P departments more than once, for instance), please let us know via e-mail, and we'll see if we can work something out. We are actively searching for future speakers. If you are in Boston on the first Tuesday of the month, and you are a principal in digital commerce, and would like to make a presentation to the Society, please send e-mail to the DCSB Program Commmittee, care of Robert Hettinga, mailto: [EMAIL PROTECTED]. For more information about the Digital Commerce Society of Boston, send "info dcsb" in the body of a message to mailto: [EMAIL PROTECTED] . If you want to subscribe to the DCSB e-mail list, send "subscribe dcsb" in the body of a message to mailto: [EMAIL PROTECTED] . We look forward to seeing you there! Cheers, Robert Hettinga Moderator, The Digital Commerce Society of Boston -BEGIN PGP SIGNATURE- Version: PGPfreeware 6.5.1 for non-commercial use http://www.pgp.com iQEVAwUBN5M6r8UCGwxmWcHhAQE+Ewf/eBxwvO7DQXsWhpTndg4FLSyS3NLFs5U3 mJyg62c9bt2Pdi44QLnMkJzcvkqxPSyy8uxCL/AfI/9plffqQ27u7oFJHXEwaETf +sRGT8wSm9qrc97Qkn65fkmXyxJwWjm6iI9s6QQcR0C3mRr3nLe/zgcNmWNEumqD KxQh7KBCjNaNPNoR5x3CABAYHe6taLH77ixDiaF0RMkGz9357abo82PQCZQtRZps
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 not change, the only difference is the intial value of the hash's internal variables? I don't think that's likely either, but I've much less confidence that it is impossible. If you want the thing to stand when the output hash breaks, you need enough input entropy and a good mixing function. I think people in this thread are confusing pragmatic reality with theoretical security. It would be great if every random bit I needed came from an overbiased zener diode. But for most uses of encryption, the output of a decent PRNG which hasn't been reseeded in a while is just fine. In every real-world situation I've seen, cryptographic systems which failed did so because of something other than the crypto failing. I'm not saying we don't need good output hashes and mixing functions, but the likelyhood of SHA-1 turning into ROT-13 tomorrow certainly isn't keeping me up at night. Marc
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 depleteable. Note that you can't tell whether you've run out of entropy by examining the output of /dev/Urandom, since its a strong PRNG. Yarrow doesn't change this. And yes, you *never* use raw measurements as random bits without conditioning. At 05:08 PM 7/18/99 -0700, bram wrote: 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 contains a cryptographycally large number of bits and it's both mixed and extracted from in a cryptographically secure way then the need for constant reseeding is eliminated, although it's still helpful. The paper on Yarrow explains the threat model pretty well - http://www.counterpane.com/yarrow.html so if you need the high quality randomness, you need hardware randomizers. Those are helpful as well, but should still never be used in the raw - their entropy output should be estimated conservatively and fed into a reseedable PRNG. -Bram
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 logarithm of the number of (invisible) microstates corresponding to an (observed) macrostate. Now: if we extract bits from the generator, we cannot gain insight over the internal state and its evolution, because on the path of a well-designed RNG there is a one-way function whose inversion is not computationally feasible. If we can't increase our knowledge of the internal state, the entropy of the pool is not depleted at all; in particular, we don't gain any information about the bits that the next requestor (i.e., the victim of the attack) will get. Am I missing something? Enzo 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 state. Yes, this should be infeasable. But the crypto-uses require fully unguessable bits. Otherwise you could use a one-time-seeded prng and turn the crank without bothering to reseed.
