Re: Toshiba shows 2Mbps hardware RNG
Dan Kaminsky [EMAIL PROTECTED] writes: For example, the following construction: Start with an RNG. Retrieve 64K of random data. Assume there might be a bias somewhere in there, but that at least 256 bits are good. SHA-256 the data. AES-256 encrypt the data with the result from the SHA-256. XOR the random data against its encrypted self. Return 64K of PNRG-hardened RNG data. Aside from the obvious rejoinder to maybe XOR *another* batch of entropy against the previous batch's encrypted self (a change that halves performance), I can't see much wrong. I rather deeply doubt I'm the first to come up with a suggestion like that either. PRNG design starts getting into the philosophy of paranoia fairly quickly. How much safety is enough? When do you stop? For example I designed my PRNG so that any one critical-path component in it can fail completely without it affecting the security of the generator (barring pathological failures like every byte of code spontaneously transmuting itself into a NOP). In other words you can replace (say) the SHA-1 operation with a memcpy() and it won't affect overall security. OTOH other designers have assumed that their mixing operation has the desired properties and therefore adding this level of redundancy is complete overkill. Who's right? (You are not expected to answer this :-). So, uh, why do weak RNG's keep showing up? Is there something fundamentally breakable in the above design? I think the answer to this generalises to why does weak security keep showing up? The answer, to quote Bruce Schneier, is that people will deploy technology that's as insecure as they can possibly get away with. Ages ago when DPA attacks were first publicised I talked to some folks who had designed a particular piece of crypto gear that happened to be completely immune to any attempts to mount DPA attacks (and various other side-channel attacks) on it. They hadn't designed it to be specifically immune to DPA attacks, all they'd done was apply sound engineering design with good power-supply decoupling, filtering of all signal lines, and so on. The result was that the NRE cost was higher, the manufacturing cost was higher, and it took a bit longer to get to market, but they had a device that severely annoyed the pen-testers because everything they tried simply bounced off. The competitors' engineers probably got a bonus for bringing their product to market faster and at lower cost by being less conservative with their design. The folks in the competitors' manufacturing department who figured out that you could omit several of the security features in the product once it had been evaluated in order to save money almost certainly got a bonus for their clever cost-cutting. Ask hardcode geeks and they'll say that the former product is better. Ask almost anyone else and they'll say the latter product is better - it's much cheaper, and who cares about a few theoretical attacks that never happen in the real world. I did warn you that it'd get philosophical... Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
Steven M. Bellovin [EMAIL PROTECTED] writes: Remember the Clipper chip? Clipper (or more specifically Capstone, via the Fortezza card) is a great example of the NSA's sound engineering approach to generating random data [0]. They used a physical randomness source of an unpublished type, presumably a standard noise-based source. And a Skipjack-based ANSI X9.17 PRNG with a pre- set random seed. *And* a 48-bit counter. All were mixed up with SHA-1. The design was such that there was no single point of failure in the sources themselves, so that as long as SHA-1 was at least vaguely useful as a mixing function the sources themselves didn't have to be totally failure-proof. For example if some environmental condition reduced the utility of the noise-based source, the PRNG would still provide strong input. If the PRNG locked up for some reason, the secret seed for that combined with the counter would still provide varying input to the SHA-1 step. I assume they also sampled the output as per FIPS 140 to detect a lockup of the SHA-1 step. The result was a failure-tolerant design that didn't rely on the totally failure-proof operation of a single component in order to function. Peter. [0] I'm calling it a sound engineering approach because I did the same thing in my PRNG design (independent of Fortezza). Others may wish to call it excessively paranoid and other things :-). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Toshiba shows 2Mbps hardware RNG
On Wed, 13 Feb 2008, Dave Korn wrote: On 11 February 2008 17:37, Crawford Nathan-HMGT87 wrote: I'm wondering if they've considered the possibility of EMI skewing the operation of the device, or other means of causing the device to genearate less than completely random numbers. Not necessarily a problem, although it does depend on their design. Even if by saturating the chip in an intense EM field you can skew the result almost all the way to 1 or 0, won't the standard debiassing trick of examining successive pairs of bits handle that? It depends on the attack: Consider John von Neumann's algorithm that, say, outputs the first bit in each pair if bits are different. If you apply EM attack and get 0s almost everywhere 00 00 00 01 00 00 00 10 00 00 10 00 00 but cannot control where 1s are exactly, then JvN corrector helps, but if your EM attack is such that it makes long runs of 0s and 1s 00 00 00 11 11 11 10 00 00 00 01 11 11 and you can detect when the bits are produced then you know exactly what bits are produced (if a bit produced on transition from 0s to 1s then it is 0). Considering speed of nondeterministic RNG, it seems pointless at least for those who go thru FIPS certification. FIPS 140-2 says Commercially available nondeterministic RNGs may be used for the purpose of generating seeds for Approved deterministic RNGs. [...] An Approved RNG shall be used for the generation of cryptographic keys used by an Approved security function. The output from a non-Approved RNG may be used 1) as input (e.g., seed, and seed key) to an Approved deterministic RNG or 2) to generate initialization vectors (IVs) for Approved security function(s). and currently there is no Approved nondeterministic RNG, so the only option is to use nondeterministic RNG to generate seeds for the deterministic one and one does not need MBps speed to generate a seed. But again, comparing a useful feature and a check mark on marketing slides, the latter is doomed to be implemented. -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
David Wagner [EMAIL PROTECTED] writes: Crawford Nathan-HMGT87 writes: One of the problems with the Linux random number generator is that it happens to be quite slow, especially if you need a lot of data. /dev/urandom is blindingly fast. For most applications, that's all you need. Alas, reading from /dev/urandom depletes the entropy pool much like reading from /dev/random does. So if you read a lot of data from /dev/urandom, you make /dev/random unusable in practice. This problem has hit libgcrypt/gnutls via the MTA Exim on a lot of Debian systems. I would argue that the linux kernel /dev/*random system is sub-optimally designed, reading a lot of data from /dev/urandom should not cause the system's /dev/random to be unusable. (Admittedly, there were other design flaws in how exim used gnutls, such as re-generating the DH parameters every X hour, and doing that synchronously in the SMTP process, causing them all to stall waiting for entropy, but that has been fixed.) /Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
Peter Gutmann wrote: David G. Koontz [EMAIL PROTECTED] writes: Military silicon already has RNG on chip (e.g. AIM, Advanced INFOSEC Machine, Motorola), That's only a part of it. Military silicon has a hardware RNG on chip alongside a range of other things because they know full well that you can't trust only a hardware/noise-based RNG, there are too many variables and too many things that can go wrong with that single source. That's why I was sceptical of the we've solved the RNG problem with our custom hardware claim, they've created one possible source of input but not a universal solution. Peter. Peter, you've just hit on something that's genuinely confused me for quite some time. Combining hash functions has always seemed naive -- the problem with chaining two different functions is that it creates a midpoint; you can collide half the bitspace independently of the other half. Better to just thoroughly mix them both. But shouldn't it be an improvement to XOR a theoretically correct RNG with a well seeded PRNG, based on the theory that: 1) Either generator could be safely XOR'd against a repeated series of 0x41's, and the output would still be just as random 2) The flaws of a subtlety broken RNG would be difficult to exploit through the noise of a sufficiently validated cryptographic function, and vice versa For example, the following construction: Start with an RNG. Retrieve 64K of random data. Assume there might be a bias somewhere in there, but that at least 256 bits are good. SHA-256 the data. AES-256 encrypt the data with the result from the SHA-256. XOR the random data against its encrypted self. Return 64K of PNRG-hardened RNG data. Aside from the obvious rejoinder to maybe XOR *another* batch of entropy against the previous batch's encrypted self (a change that halves performance), I can't see much wrong. I rather deeply doubt I'm the first to come up with a suggestion like that either. So, uh, why do weak RNG's keep showing up? Is there something fundamentally breakable in the above design? --Dan - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
On Wed, 13 Feb 2008 20:38:49 -0800 [EMAIL PROTECTED] wrote: - Original Message - From: Pat Farrell [EMAIL PROTECTED] To: Subject: Re: Toshiba shows 2Mbps hardware RNG Date: Sun, 10 Feb 2008 17:40:19 -0500 Perry E. Metzger wrote: [EMAIL PROTECTED] (Peter Gutmann) writes: I've always wondered why RNG speed is such a big deal for anything but a few highly specialised applications. Perhaps it isn't, but any hardware RNG is probably better than none for many apps, and they've managed to put the whole thing in a quite small bit of silicon. The speed is probably icing on the cake. One of the benefits of speed is that you can use cleanup code to control bias. Carl Ellison put some out on his website last century. It is a HUGE win for designing a crypto system to have a really fast (and good) HW RNG. Being able to generate 10-20,000 AES keys per second means that you can engineer things that were impossible to do otherwise. You can generate as many keys as you like, throw away keys after one time use, treat them as ephemeral authentication keys (say give a few million or so to a user), etc. Or you could hand a sender 10 MBytes (less than a minute to generate), which then can be used to create billions of keys (say using Ueli Maurer's Bounded Storage Model). The sender could then use each key to uniquely encrypt (AES CTR) each message of a series of messages or packets to a receiver (AES key setup is fast). No need for an IV or worrying about message ordering (each one has a key id), or even the compromise of a key or two. Randomness is the most fundamental underpinning of a crypto system and having lots of it on demand is really fabulous to have in our system security design tool box. Leaving aside whether or not your scenarios make sense, why must this be done via a hardware RNG? I ran 'openssl speed aes' on a 3.4 Ghz single-core Pentium. On 16-byte blocks with AES-128 -- i.e., running AES in counter mode to generate 128-bit keys -- it ran at about 3.4M encryptions/second. That's more than two orders of magnitude better than you say is needed. Why do I need hardware? Hardware RNGs are great for producing initial seeds. They're also great for producing new randomness to stir into the pot (i.e., via something like Yarrow). But they're lousy for ongoing work because they're relatively low assurance. As others have noted, software has a big advantage: it's deterministic. Once you know its working, you have much higher assurance that it will continue to work the same way. (Aside: I know quite a bit about the problem of certifying complex software. A cryptographically strong PRNG doesn't fall into that category if you have confidence in the algorithm.) Remember the Clipper chip? According to Dorothy Denning, the escrowed keys -- that is, the entire security of the basic scheme -- was generated by several applications of the Skipjack, the underlying block cipher -- see http://catless.ncl.ac.uk/Risks/14.52.html#subj1 for details. (Note: that statement was later disavowed. I'm not sure I believe the disavowal; it looked secure to me.) --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Toshiba shows 2Mbps hardware RNG
|SAN FRANCISCO -- Toshiba Corp. has claimed a major breakthrough in |the field of security technology: It has devised the world's |highest-performance physical random-number generator (RNG) |circuit. | |The device generates random numbers at a data rate of 2.0 megabits |a second, according to Toshiba in a paper presented at the |International Solid-State Circuits Conference (ISSCC) here. | | I'm wondering if they've considered the possibility of EMI skewing the | operation of the device, or other means of causing the device to | genearate less than completely random numbers. I wonder if they considered the possibility that the device will be destroyed by a static discharge? It's one thing to criticize a design about which you know nothing on the basis of a broad, little-known or brand new, attack. But the fact that EMI can skew devices has been known for years. Hardware that may need to work in (deliberately or otherwise) high-EMI environments has to be appropriately designed and shielded (just as devices have for years been protected against static discharge through multiple layers of protection, from the chip design itself through ground straps for people handling them). I know nothing at all about Toshiba or its designers. Do you know something that makes you think they are so incompetent that they are unaware of well-known issues that arise in the design of the kinds of devices they work with? | It is certainly an interesting device; I think this would find | considerable use in communication infrastructure and high-bandwidth | applications. As someone else mentioned, generating a single, random, | 128 bit seed is not too difficult with current technology, but it | doesn't address the issue that often times you want more than just a | single key. One of the problems with the Linux random number generator | is that it happens to be quite slow, especially if you need a lot of | data. | | Some potential uses: | 1.) Secure file erasure. Why? Writing hard random values over the previous data is neither more nor less secure than writing zeroes, unless you descend to the level of attacking the disk surface and making use of remnance effects. Once you do that ... it's still not clear that writing random values is better or worse than writing all zeroes! (As Peter Gutmann showed years ago, there are *highly technology-specific sets of patterns* that do a better job than all zeroes, or all ones, or whatever. There's little reason to believe that a random set of bits is good for much of anything in this direction.) If you're concerned about someone distinguishing between erased data and real data ... if the real data is unencrypted, then the game is over anyway. If the real data is encrypted, you want the erased data to look exactly as random as the encrypted real data. That is, if you believe that your AES-encrypted (say) data can be distinguished from random bits without knowning the key, then if you fill the erased blocks with *really* random bits, the distinguisher will tell you exactly where the real data is! Better to use exactly the same encryption algorithm to generate your random erasure pattern. BTW, even pretty average disks these days can write 50 MB/second, or 200 times the rate at which this device can generate random bits. | 2.) OTP keygen for those _really_ high security applications. OK. | 3.) Faster symmetric keyset generation. You know, when you need to | build 32k keys... OK, though given the computational overhead involved in generating symmetric keys, it's hard to see the random number generation as the throttling factor. | 4.) Random seeding of communication packets. If you're talking about inserting fillers to thwart traffic analysis, the same argument as for erasing disk blocks: Either you believe your encrypted packets can't be distinguished from random, in which case you don't need the generator; or you are afraid they *can* be, in which case you'd better not use the generator! | There used to be (maybe still) a TCP spoofing exploit that relied on the | timing of packets; there are also various de-anonymization attacks based | on clock skew. With a chip like this, you could add a small, random | number to the timestamp, or even packet delay, and effectively thwart | such attacks. Such systems need high-bandwidth, random number | generators. I don't buy it. First off, the rates are pretty low - how many packets per second do you send? Second, the attacks involved are probably impossible to counter using software, because the timing resolutions are too small. Maybe you can build random jitter into the hardware itself - but that brings in all kinds of other issues. (The hardware is, of course, *already* introducing random jitter - that's the basis of the attack. Just adding more without getting rid of the bias that enables the attacks is little help; at worst, it just requires the attacker to take more samples to average away the
Re: Toshiba shows 2Mbps hardware RNG
- Original Message - From: Pat Farrell [EMAIL PROTECTED] To: Subject: Re: Toshiba shows 2Mbps hardware RNG Date: Sun, 10 Feb 2008 17:40:19 -0500 Perry E. Metzger wrote: [EMAIL PROTECTED] (Peter Gutmann) writes: I've always wondered why RNG speed is such a big deal for anything but a few highly specialised applications. Perhaps it isn't, but any hardware RNG is probably better than none for many apps, and they've managed to put the whole thing in a quite small bit of silicon. The speed is probably icing on the cake. One of the benefits of speed is that you can use cleanup code to control bias. Carl Ellison put some out on his website last century. It is a HUGE win for designing a crypto system to have a really fast (and good) HW RNG. Being able to generate 10-20,000 AES keys per second means that you can engineer things that were impossible to do otherwise. You can generate as many keys as you like, throw away keys after one time use, treat them as ephemeral authentication keys (say give a few million or so to a user), etc. Or you could hand a sender 10 MBytes (less than a minute to generate), which then can be used to create billions of keys (say using Ueli Maurer's Bounded Storage Model). The sender could then use each key to uniquely encrypt (AES CTR) each message of a series of messages or packets to a receiver (AES key setup is fast). No need for an IV or worrying about message ordering (each one has a key id), or even the compromise of a key or two. Randomness is the most fundamental underpinning of a crypto system and having lots of it on demand is really fabulous to have in our system security design tool box. - Alex - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
David G. Koontz [EMAIL PROTECTED] writes: Military silicon already has RNG on chip (e.g. AIM, Advanced INFOSEC Machine, Motorola), That's only a part of it. Military silicon has a hardware RNG on chip alongside a range of other things because they know full well that you can't trust only a hardware/noise-based RNG, there are too many variables and too many things that can go wrong with that single source. That's why I was sceptical of the we've solved the RNG problem with our custom hardware claim, they've created one possible source of input but not a universal solution. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
Hal Finney wrote: Looking at the block diagram for the new Toshiba circuit, and comparing with the Intel design, one concern I have is with attacks on the device via external electromagnetic fields which could modulate current flows and potentially influence internal random numbers. Intel attempted to mitigate this attack by using a pair of resistors spaced close together, and taking differentials between them. I don't see any such countermeasures in the (admittedly crude) block diagram in the Toshiba press release. From the EE Times article, the stochastic noise source for the Toshiba RNG is from a trap layer of Silicon Nitride in a MOSFET transistor. An Analog to Digital Converter is used as a gating amplifier and the random noise bit rate is dependent on the conversion speed instead of transformer etc.impulse response. The difference in size between the 2 Mb/s and 10 Mb/s RNG appear to be due to A/D converter area (from the ISSCC session 22 advanced program). http://www.toshiba.co.jp/rdc/rd/detail_e/e0704_03.html It's a floating gate structure. it is clear from the figure that the SiN MOSFET device generates greater current fluctuation. This is presumably because more frequent occurrence of electron capture and emission between the Si channels and dangling bonds owing to the remarkably large number of the traps that cause noise generation makes possible generation of a large amount of noise. Also, the SiN MOSFET?s ID fluctuation makes it possible to generate a larger amount of random noise due to the respective parameter designs of the devices (gate length, gate width, tunnel oxidized film thickness (Tox), the Si/N atomic ratio). The more signal, the higher the noise immunity, presumably. The description reminds me of tube thermionic noise. I'd suspect it would benefit from a drawing done on a rotated axis showing the Trap layer as a 2D array. You get a random noise source that doesn't require the cryptographic boundary be pushed into instruction/procedural space or across chip boundaries for RNG generation, avoiding those pesky predictable random numbers as attributed to a Microsoft software implementation recently. Military silicon already has RNG on chip (e.g. AIM, Advanced INFOSEC Machine, Motorola), you wonder if someone would consider an FPGA with a good RNG hard core cell on chip, now that someone has figured out how to do red/black separation in an FPGA compiler. Wonder how cheap it is to spot dope SiN or will we have to switch to anti-fuse FPGAs to take advantage? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
[EMAIL PROTECTED] (Hal Finney) writes: When the Intel RNG came out several years ago, built into the bus controller chipset, it was not widely accepted by the cryptographic community due to fears of back doors or internal weaknesses. A generally positive analysis by Cryptographic Research (http://www.cryptography.com/intelRNG.pdf) failed to assuage these concerns. I think a much bigger reason for its non-acceptance was that it wasn't there (either present or available or accessible) in most cases. The PRNG in VIA's C7 series hasn't had any of these problems, and is supported out of the box by a pile of software and even some distros (typically via /dev/random). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
Danilo Gligoroski [EMAIL PROTECTED] writes: At 04:02 AM 2/10/2008, Peter Gutmann wrote: Perry E. Metzger [EMAIL PROTECTED] writes: \snip So your potential market for this is people running Monte Carlo simulations who don't like PRNGs. Seems a bit of a limited market... I think that the market is a little bit bigger than just applications running Monte Carlo simulations. For example, Gambling industry - which is also multi- billion industry world-wide. The security target for the gambling industry is to pass (incredibly stringent) auditing requirements. A simple PRNG seeded from a factory-set initial value is fine as long as it's been certified to death. The impression I got from this some time ago from people who work in this area was that they really wanted deterministic PRNGs rather than nondeterministic hardware ones, although at the time I didn't ask whether it was because it made certification easier or because they just didn't trust unpredictable RNGs (unpredictable meaning that an infinite number of environmental variations can cause it to potentially do things that you don't want). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
At 07:02 PM 2/9/2008, Peter Gutmann wrote: I've always wondered why RNG speed is such a big deal for anything but a few highly specialised applications. For security use you've got two options: 1. Use it with standard security protocols, in which case you need all of 128 or so bits every now and then (and very rarely a few thousand bits for asymmetric keygen). One obvious application I can think of is Diffie-Hellman session key generation for web or email servers that handle lots of sessions. Sure, you _could_ use PRNGs to generate the keys, with real RNG now and then, but a fast RNG can help protect you against one popular threat model, which is auditors. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Toshiba shows 2Mbps hardware RNG
Perry E. Metzger [EMAIL PROTECTED] writes: EE Times: Toshiba tips random-number generator IC SAN FRANCISCO -- Toshiba Corp. has claimed a major breakthrough in the field of security technology: It has devised the world's highest-performance physical random-number generator (RNG) circuit. The device generates random numbers at a data rate of 2.0 megabits a second, according to Toshiba in a paper presented at the International Solid-State Circuits Conference (ISSCC) here. I've always wondered why RNG speed is such a big deal for anything but a few highly specialised applications. For security use you've got two options: 1. Use it with standard security protocols, in which case you need all of 128 or so bits every now and then (and very rarely a few thousand bits for asymmetric keygen). 2. Use it at its full data rate, in which case you can only communicate with someone else who has the same device, but more importantly you need to design and build your own custom security infrastructure to take advantage of the high-data-rate randomness, which is much harder than simply designing an RNG device and declaring victory. (In any case if you really need high-data-rate randomness, you just take your initial 128 bits and use it to seed AES in CTR mode). So your potential market for this is people running Monte Carlo simulations who don't like PRNGs. Seems a bit of a limited market... Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
