Re: [long] Yet another random number generator
-BEGIN PGP SIGNED MESSAGE- [ To: Sandy Harris, Perry's Crypto List ## Date: 07/12/99 ## Subject: Re: Yet another random number generator ] Date: Sun, 11 Jul 1999 13:10:56 + From: Sandy Harris [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [long] Yet another random number generator Proposal: Could we do a large part of this with a fairly simple chip, all digital, without diodes etc.? A system bus has typically at least 32 data and 32 address lines plus a bunch of control signals. Perhaps 80 bits that can be sampled at perhaps 100 MHz. 10 Mbytes/sec. Crunch that down to 10K highly random bytes? Some bits have dreadful entropy of course: e.g. on systems with under a gig of RAM, top two address lines are always 0. On any system, bottom two are usually 0 for aligned access. All ASCII characters have top bit 0, much numeric data is small integers, etc. Interrupt lines should spend most of their time in the non-asserted state. So, if I understand correctly, the entropy is based on everything that passes over the system bus, right? What is the source of entropy when the system is quietly humming away running the screensaver, while the user is downstairs drinking his morning coffee? It looks to me like your entropy will be *very* uneven. Would this kind of sampling get TrueRand-type phase drift between CPU clock and time clock? I can't see how. What other sources of entropy would be available? (Maybe hard drive timings for page swaps and such.) I have a crunching mechanism to propose. Nyberg showed that perfect s-boxes (all columns and all linear combinations of columns are bent boolean functions) can be built whenever there are twice as many input bits as output bits. Build a substitution-permutation network with perfect s-boxes. Wait a second, here! Nyberg's perfect S-boxes can give you provable security against standard differential and linear attacks, but I don't see why this is relevant, here. We're trying to crunch this huge stream of data down into a fixed-length buffer, presumably with some kind of arguments for entropy-preservation. We don't care much here about an attacker controling our inputs--he would have to be in control of our system bus! Anyway, I think your entropy-gathering proposal ought to be kept separate from the crunching mechanism. I claim that we can design a reasonable crunching mechanism using existing components, probably block ciphers or hash functions. Is there a reason why (say) treating the buffer as circular, and continually processing inputs by XORing them into the buffer, and then CBC-mode encrypting the resulting blocks with a fixed key, wouldn't suffice? Details would depend on analysis of input entropy (how much crunching is needed) and of target chip technology (what is pratical) but it might look something like: Wouldn't the entropy on the system bus vary depending on what was going on? I mean, if I get to load all the software onto your machine and have you start it up and run it, there won't be much going over the system bus that will be of much interest. (Maybe you'll get phase jitter between the CPU clock and the RNG's clock.) [ Lots of design ideas deleted.] Comments? The entropy collection method is interesting. The crunching method is interesting. It seems like they are more-or-less independent, though. - --John Kelsey, Counterpane Internet Security, [EMAIL PROTECTED] NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF -BEGIN PGP SIGNATURE- Version: PGPfreeware 5.5.3i for non-commercial use http://www.pgpi.com iQCVAwUBN5AqUSZv+/Ry/LrBAQGUUgP+LWIqCZ8JDuYmO3M/d8f1/JhgFAm3c7xp lXTiMz2VgYfGS3ohY3mreEcOF1+Tw3tnGM+5hDIY4070ItD3d7iSG5+cNTvriWGn tKixWWBNR9PPrjSKxyE5RwBih/Zc/eqW17aUi9jeeh5wuyCLB+gGOtOsUl88NF9D /+YoShdtP68= =WiyW -END PGP SIGNATURE-
Drawing A Hard Line On Encryption (was Re: Edupage, 16 July 1999)
At 4:35 PM -0600 on 7/16/99, EDUCAUSE wrote: DRAWING A HARD LINE ON ENCRYPTION The House Permanent Select Committee on Intelligence unanimously approved a measure to control exports of encryption software and provide government access to encrypted data. The committee was the fourth House panel to approve the amendment, which was designed to ensure that government agencies can obtain court orders to access encrypted information. The committee also adopted a measure allowing the president to control, and deny, encryption exports significant to national security. Last, the committee approved language authorization funding to enable law enforcement and intelligence agencies to better prevent the spread of increasingly powerful encryption software. These issues have been the subject of much controversy, as software manufacturers argue that they are losing market share from export controls, while privacy activists oppose law enforcement access to encrypted data. (Washington Post 07/16/99) - Robert A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
depleting the random number generator
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. Specifically: consider a central machine (call it Whitney) that is implementing many IPsec tunnels. For me, this is a highly non-hypothetical situation. Step 1) Suppose some as-yet unknown person (the "applicant") contacts Whitney and applies for an IPsec tunnel to be set up. The good part is that at some point Whitney tries to authenticate the Diffie-Hellman exchange (in conformance with RFC2409 section 5) and fails, because this applicant is an attacker and is not on our list of people to whom we provide service. 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. 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. 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. Step 3b) OTOH if Whitney is getting its key material from /dev/urandom (that's urandom with a U), then we don't have a DoS attack, but instead we have a situation where the attacker can mount a low-entropy attack against any or all of the other tunnels. Yuuuck. = There are variations on this theme. For instance, note that sshd is a prodigious consumer of random bits. Therefore if your IPsec machine is running sshd, bad guys have another way of mounting attacks against your RNG. They don't even need to know a valid ssh key; failed ssh attempts suck up plenty of entropy. == 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? Thanx --- jsd
Lucre documentation
For those who care, I've added a little docco to Lucre. Here's the explanation of the executable demos. Also available is the theory, such as it is (check out the CVS for that, or shout at me). bank-new key length bank private file bank public file Create a bank. The stuff you should guard with your life is added to bank private file and the stuff you can give to Joe Public ends up in bank public file. coin-request bank public file coin private file coin request Create a coin (or at least, a request for one. What is sometimes known as a protocoin). The bank public file is the bank info generated by bank-new. The coin private file is the bit that will be worth money once the bank has signed stuff. The coin request is what the bank will sign. bank-sign bank private file coin request coin signature Having received a coin request, the bank signs it (after due deliberation, of course). Here's how it does it. coin signature is what you send back to the victim, err, customer. coin-unblind bank public file coin private file coin signature coin Now that the bank believes we are worth something, we've got a coin signature back from it. Here's how we convert that, plus other bits, to an actual blinded coin. bank-verify bank private file coin Naturally, a coin is worth nothing unless the bank will stand behind it. This is how you check the coin isn't crap. 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
