Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
On Sun, 2013-09-08 at 13:27 +0200, Eugen Leitl wrote: > - Forwarded message from "James A. Donald" - > On 2013-09-08 3:48 AM, David Johnston wrote: > > Claiming the NSA colluded with intel to backdoor RdRand is also to > > accuse me personally of having colluded with the NSA in producing a > > subverted design. I did not. > > Well, since you personally did this, would you care to explain the > very strange design decision to whiten the numbers on chip, and not > provide direct access to the raw unwhitened output. > > A decision that even assuming the utmost virtue on the part of the > designers, leaves open the possibility of malfunctions going > undetected. I may have missed this part of the thread, but I'm interested in knowing the rational for letting the hyper-visor intercept the RDRAND call and return any value it likes, bypassing the random hardware. I've had one person speculate it would be useful for keeping 2 CPUs in sync, (the TSC can also be intercepted), but it does worry me that RDRAND calls can be rendered predictable by a compromised VM. eric For those interested, Intel document 325462.pdf, "Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C" Page 'Vol. 3C 27-23', Table 27-12. Format of the VM-Exit Instruction-Information Field as Used for RDRAND ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
> -Original Message- > From: cryptography-bounces+owen.shepherd=e43...@metzdowd.com > [mailto:cryptography-bounces+owen.shepherd=e43...@metzdowd.com] > On Behalf Of David Johnston > Sent: 09 September 2013 05:41 > To: cryptography@metzdowd.com > Subject: Re: [Cryptography] [cryptography] Random number generation > influenced, HW RNG > > #1 So that that state remains secret from things trying to discern that state > for purposes of predicting past or future outputs of the DRBG. > > #2 So that one thread cannot undermine a second thread by putting the > DRNG into a broken mode. There is only one DRNG, not one per core or one > per thread. Having one DRNG per thread would be one of the many > preconditions necessary before this could be contemplated. > > #3 Any method of access is going have to be documented and supported and > maintained as a constant interface across many generations of chip. We don't > throw that sort of thing into the PC architecture without a good reason. > > #4 Obviously there are debug modes to access raw entropy source output. > The privilege required to access those modes is the same debug access > necessary to undermine the security of the system. This only happens in very > controlled circumstances. There are lots of aspects of IA-32/AMD64 which aren't consistent across generations. The power management interface, for example, tends to get somewhat infrequent backwards incompatible tweaks. Fundamentally, I don't think anybody would have complained if you provided some potentially non-stable method of /reading/ the RNG state; for example, a bunch of MSRs (Hell, the potential instability is there in the name: _Model_specific_, as much as a misnomer that is for the majority of stuff dumped into an MSR) which could read the state wouldn't be out of the question. Plus, there it is: the required security protections. The only pieces of software which can read MSRs are the kernel and SMM. If either of those is compromised, well, you're boned anyway. Some way of reading the raw RNG output, and establishing that things are working as they should? That would give a lot of confidence Also, you could have made rdrand set CF or similar if its state could be predictable due to a recent read of the DRNG's state or similar. -BEGIN PGP MESSAGE- Version: GnuPG v2.0.21 (MingW32) owGdVmtsFUUULigNVPABEX9o6BASHuH2UmgxUhEo1FLQUmyJDTakzt2dvTvt7sw6 M9vLQqI/JCBqVHzEGAMGI4I/MCUiCSgGCUHxQWLA1MYYqII2waAmJCoS4jmz996W +M8mt72zO3POd77vO2f60qSbKsaOefu9fQemPju2MObLS7mK9ppvDy4hNfjTpnie CxqQVqY1zTP7cFLVEtKsZNhAHJVERuYVjfykJidj4TA9VxaYyGqfRT5T7gOsvi7L 4mUhM5tcWXCzjgzxfFdIeWBkw/+LsAFDtAmynPk08EibR5poH3fJaukLbaTA1x1M mAZSuwi+RIaFOabIgtr5daR2YUP9fNywTt5YwH8wdsS5HuZAkHbWQLpWjNq6gXQ5 NyzbqXBlSERs8+SZYIoangLhwgtiBoW5GdLSSdrXrMSn+Jkxn3RIYnxq0l/aUMOI YsCN0EQzRzFDPGAaXnOR18SoBP4SI4nLtcOUGHUOA3pSkShWkdRME+mRSDGXOwbP RFQbAq+92MSKERmbKDZ2k/EZaWpfvjJbhrWgDEsKBl8Uoy5xqBDSkFi4TIUcnlNE KIVb2pBLILexySAkBmqCWqF8gEtJTsleJkgoXZYl60BYRjikF0Fik+DWDMEEuIqA REciTIVrjIWP0kRZ0gJiQ5bSuVHvSEHGAUBh9mWxuJCKxIZQFi9HYTQRzEFPqwR2 e5gLONaQtXgedoJrogCYdUeYqSONIiFgFF+6GJ46GAQryUuE5NM+hvJAAFc6cQge ZC4BcxAdR5FUxRXGQpENfPCJBoIgIegoDBLGlEcdYNhREqIj/lGesqI5Po+ypBPT iFkG4wEBslD0AyRKi0dMVgDkYe0KQhUcNGBq9ECBQxmxgdx5CeUAf1qKcq2EzKgn bbk+LmMNIhkrGYWPy3Jx3gqpsdQiBYoWCFSrZJRA/lg5JY/ZgCA40M/7eMDy6PAn Yg7WHHUckGhWDMq1hatpWEqWbsJAI6rB2REv2v3MiRU3SUl2nWhQEM1WMppPo4gB f1yQPqasJ1BmJYMAwDhcgWKoAaQA1JOq1pVrDmTaK1RHQJ79uqqxpm7BvMbWpnvr ScHnjo8bQQsrJIfUIGVRwFHaZVMqYMIp1BVGKnpkRPOM7WG2kYL1YAFRXMtynqGs ISugvjBRkEI8mKNOb4EqF4uCsRVBllwAfBQY7U2LaAaWKCahQZBkyKrUMdYbveDF JCfdpNg21r0YJUh9yT2SyBiEkzBcYY0AADuWxjEa9KuoAcIw40hPzMNGBOPNsypg f9r5dP+NlcFEgGHv44HWjnZNZrewIMjYI+UMUBNG5wGqmroCx4awuwQU1UC6W8Ey QTfKwj3udGewmcIY1cCmCrkWAFqlfQEhEEM6E3pkySzaxJ5H3DiMsGY7rgSCmlPU NZ0JdrxYX9kpbRlDInPW6CXTgSoahbbUrw1inSmhxvQNdk/Z/mXHAsPYlCMGsXaN OJrdIpSeKaAPi4AAn4VjmaMq9X8v3AcssMOmo7U1S1Z5hHFMnmLD/rIDLoRswAte RwXLOWg8C2LkpJ1Fx7pEUqCJLaADBYcFRiiqmlYAzY7Cph2esTmZNQLXfrqJmtKl ZXFL1YvPqRURJoSP9C2FWmFfar4878M7JZCWS2giDzwHrYg4GgMtLc6iFtaoIXUB iavsdIX2WNGM14XmIQ+oQu9yaNRUrPJUL16I1rFubEc1hcocbCXLaPk+XLNyVun0 SNTs9jH33FwxZmxF5bix+F9SRdWE20v/Ou0+PL7i/ZOTf95ywq/8dPquc+7J8eS2 2XOeOjv+m+P9H4fjxu+bPnB64mtXZz4UdN+yZ8+EaYsvH9/xxw8HZjbWnh4+++af Xy3+5Vpbzc7HTq3Yf5Rt7x88NrRxOB545sUH5645P/HHt+oHn26a3H/qRM+lqfcN DW9rca/c+vqVV/euv2tz8+r+i3d3fLA3f/3cjsyj7kdDnw0f2PTqw69UVcYv7Ny9 6uSZlw9OGxg+NHT5i8WP7CDLtv302+bjucd7sjOGf/9rad8RTx6tvtpZOfBG9a+r 71x/eP+FubP52U/OLNxy8cPTU7YOdn7+XfU/7/QPbv363BHxnDr6/CE+ZfK7xy7d sfX4ovOZ609e+/v75Xurdw1VtfIL1f8C =YDgw -END PGP MESSAGE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
>> would you care to explain the very strange design decision >> to whiten the numbers on chip, and not provide direct >> access to the raw unwhitened output. On 2013-09-09 2:40 PM, David Johnston wrote: > #1 So that that state remains secret from things trying to > discern that state for purposes of predicting past or > future outputs of the DRBG. This assumes the DRGB is on chip, which it should not be. It should be in sofware. Your argument is circular. You are arguing that the DRGB should be on chip, because it is on chip, that is has some of its menacing characteristics because it has other menacing characteristics. > #2 So that one thread cannot undermine a second thread by > putting the DRNG into a broken mode. There is only one > DRNG, not one per core or one per thread. Having one DRNG > per thread would be one of the many preconditions necessary > before this could be contemplated. You repeat yourself. Same circular argument repeated. > #3 Any method of access is going have to be documented and > supported and maintained as a constant interface across > many generations of chip. Why then throw in RDSEED? You are already adding RDSEED to RDRAND, which which fails to address any of the complaints. Why provide a DRNG in the first place. Answer: It is a NIST design, not an Intel design. Your design documents reference NIST specifications. And we already know that NIST designs are done with hostile intent. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
On 9/8/2013 4:27 AM, Eugen Leitl wrote: - Forwarded message from "James A. Donald" - Date: Sun, 08 Sep 2013 08:34:53 +1000 From: "James A. Donald" To: cryptogra...@randombit.net Subject: Re: [cryptography] Random number generation influenced, HW RNG User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 Reply-To: jam...@echeque.com On 2013-09-08 3:48 AM, David Johnston wrote: Claiming the NSA colluded with intel to backdoor RdRand is also to accuse me personally of having colluded with the NSA in producing a subverted design. I did not. Well, since you personally did this, would you care to explain the very strange design decision to whiten the numbers on chip, and not provide direct access to the raw unwhitened output. #1 So that that state remains secret from things trying to discern that state for purposes of predicting past or future outputs of the DRBG. #2 So that one thread cannot undermine a second thread by putting the DRNG into a broken mode. There is only one DRNG, not one per core or one per thread. Having one DRNG per thread would be one of the many preconditions necessary before this could be contemplated. #3 Any method of access is going have to be documented and supported and maintained as a constant interface across many generations of chip. We don't throw that sort of thing into the PC architecture without a good reason. #4 Obviously there are debug modes to access raw entropy source output. The privilege required to access those modes is the same debug access necessary to undermine the security of the system. This only happens in very controlled circumstances. A decision that even assuming the utmost virtue on the part of the designers, leaves open the possibility of malfunctions going undetected. That's what BIST is for. It's a FIPS and SP800-90 requirement. That is a question a great many people have asked, and we have not received any answers. Yes they have. I've answered this same question multiple times. Access to the raw output would have made it possible to determine that the random numbers were in fact generated by the physical process described, since it is hard and would cost a lot of silicon to simulate the various subtle offwhite characteristics of a well described actual physical process. Access to the raw output would have been a massive can of worms. The statistical properties of the entropy source are easy to model and easy to test online in hardware. They are described in the CRI paper if you want to read them. That's a necessary part of a good entropy source. If you can't build an effective online test in hardware then the entropy source is not fit for purpose. DJ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
On 09/08/2013 04:27 AM, Eugen Leitl wrote: On 2013-09-08 3:48 AM, David Johnston wrote: Claiming the NSA colluded with intel to backdoor RdRand is also to accuse me personally of having colluded with the NSA in producing a subverted design. I did not. Well, since you personally did this, would you care to explain the very strange design decision to whiten the numbers on chip, and not provide direct access to the raw unwhitened output. Y'know what? Nobody has to accuse anyone of anything. The result, no matter how it came about, is that we have a chip whose output cannot be checked. That isn't as good as a chip whose output can be checked. A well-described physical process does in fact usually have some off-white characteristics (bias, normal distribution, etc). Being able to see those characteristics means being able to verify that the process is as described. Being able to see also the whitened output means being able to verify that the whitening is working correctly. OTOH, it's going to be more expensive due to the additional pins of output required, or not as good because whitening will have to be provided in separate hardware. Ray ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sep 7, 2013, at 8:06 PM, John Kelsey wrote: > There are basically two ways your RNG can be cooked: > > a. It generates predictable values. Any good cryptographic PRNG will do > this if seeded by an attacker. Any crypto PRNG seeded with too little > entropy can also do this. > > b. It leaks its internal state in its output in some encrypted way. > Basically any cryptographic processing of the PRNG output is likely to > clobber this. There's also another way -- that it's a constant PRNG. For example, take a good crypto PRNG, seed it in manufacturing, and then in its life, it just outputs from that fixed state. That fixed state might be secret or known to outsiders, but either way, it's a cooked PRNG. Sadly, there were (are?) some hardware PRNGs on TPMs that were precisely this. Jon -BEGIN PGP SIGNATURE- Version: PGP Universal 3.2.0 (Build 1672) Charset: us-ascii wj8DBQFSLLbjsTedWZOD3gYRAhMzAJ93/YEF8mTwdJ/ktl5SiR5IPp4DtwCeIrZh KHVy+CIpN69GpJNlX0LiKiM= =i4b8 -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
- Forwarded message from "James A. Donald" - Date: Sun, 08 Sep 2013 08:34:53 +1000 From: "James A. Donald" To: cryptogra...@randombit.net Subject: Re: [cryptography] Random number generation influenced, HW RNG User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 Reply-To: jam...@echeque.com On 2013-09-08 3:48 AM, David Johnston wrote: > Claiming the NSA colluded with intel to backdoor RdRand is also to > accuse me personally of having colluded with the NSA in producing a > subverted design. I did not. Well, since you personally did this, would you care to explain the very strange design decision to whiten the numbers on chip, and not provide direct access to the raw unwhitened output. A decision that even assuming the utmost virtue on the part of the designers, leaves open the possibility of malfunctions going undetected. That is a question a great many people have asked, and we have not received any answers. Access to the raw output would have made it possible to determine that the random numbers were in fact generated by the physical process described, since it is hard and would cost a lot of silicon to simulate the various subtle offwhite characteristics of a well described actual physical process. ___ cryptography mailing list cryptogra...@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography - End forwarded message - -- Eugen* Leitl http://leitl.org";>leitl http://leitl.org __ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
There are basically two ways your RNG can be cooked: a. It generates predictable values. Any good cryptographic PRNG will do this if seeded by an attacker. Any crypto PRNG seeded with too little entropy can also do this. b. It leaks its internal state in its output in some encrypted way. Basically any cryptographic processing of the PRNG output is likely to clobber this. The only fix for (a) is to get enough entropy in your PRNG before generating outputs. I suspect Intel's RNG and most other hardware RNGs are extremely likely to be better than any other source of entropy you can get on your computer, but you don't have to trust them 100%. Instead, do whatever OS level collection you can, combine that with 256 bits from the Intel RNG, and throw in anything else likely to help--ethernet address, IP address, timestamp, anything you can get from the local network, etc. Hash that all and feed it into a strong cryptographic PRNG--something like CTR-DRBG or HMAC-DRBG from SP 800-90. If you do that, you will have guarded against both (a) and (b). --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
- Forwarded message from Thor Lancelot Simon - Date: Sat, 7 Sep 2013 15:36:33 -0400 From: Thor Lancelot Simon To: Eugen Leitl Cc: cryptogra...@randombit.net Subject: Re: [cryptography] Random number generation influenced, HW RNG User-Agent: Mutt/1.5.20 (2009-06-14) On Sat, Sep 07, 2013 at 09:05:33PM +0200, Eugen Leitl wrote: > > This pretty much rules out CPU-integral RNGs. It has to be > a third-party add-on (USB or PCIe), and it has to be open hardware. I think you take this more than a little too far. I see CPU-integral RNGs as very valuable source to be mixed with other sources in a software pool of entropy. Why should we reject them, unless we think the mixing functions themselves are useless? The lesson here seems to me to be that we should be far more assiduous in seeking out additional sources of entropy and in always ensuring software RNGs mix input from multiple such sources into all output. We should abandon sacred cows like the notion of information-theoretic randomness (that we don't actually know how to measure, but in pursuit of which we hamstring our software RNGs by arranging that they refuse to produce any output unless, by some questionable criterion, there is enough of it) and pursue engineering goals we can actually achieve, like mixing enough other-source input, of whatever quality, with the output of fast generators we can no longer trust that the adversary must actually attack the mixing function, rather than iteratively guessing the few state bits he does not already know. Secondarily -- and sadly! -- we must now be very suspicious of devices that integrate random number generation and encryption. Can we even trust raw hardware RNG output for the generation of IVs? I would argue not, because the same device's AES engine could be leaking key bits into our explicit IVs, etc, and we couldn't ever know. Devices that offload packet processing in its entirety (SSL accellerators, IPsec accellerators, etc.) have even more opportunity to do this sort of thing. Hardware crypto offload may still be very useful -- random number generation perhaps in particular -- but we will have to apply it with extreme care, and with a deliberate eye towards eliminating covert channels put in place by people at least as smart as we are, and with far more time and experience thinking about the problem from the offensive point of view. Finally, we have to accept that the game might just be over, period. So you use a pure software RNG, mixing in RdRand output or not as you may prefer. How hard do you think it is to identify the datastructures used by that RNG if you can execute code on a coprocessor with access to host RAM? Almost every modern server has such a coprocessor built in (its management processor) and you won't find the source code to its firmware floating around. Intel even puts this functionality directly on its CPUs (Intel AMT). Rather than beating up on the guy who put a lovely RNG instruction into every processor we're likely to use any time soon, it seems to me we ought to be beating up on ourselves for ignoring far simpler and more obvious risks like this one for well over a decade. Seriously, show of hands, who here has ever really put his or her foot down and insisted that a product they were purchasing _omit_ such functionality? Not chosen not to pay for it, refused to buy server X or mainboard Y simply on the basis that management processor functionality was onboard? Now, compare to the number of people complaining about backdoored RNGs here and elsewhere on the Internet. Go figure. To me the interesting question, but one to which I don't expect to ever know the answer, is whether the adversary -- having, we can assume, identified high value devices to systematically compromise, and lower value devices to defer for later or simply ignore entirely -- went at those devices sniper-style, or shotgun-style. Were a few key opportunities for tampering identified, and one or two attempted against each targeted device? Or were a wide variety of avenues explored, and every single one that seemed relevant attempted everywhere, or at least against certain particularly high value devices? If we knew that, in a way we might know, when we did finally see concrete evidence of a particular kind of tampering, how long to keep looking for more. But we aren't going to know that, no matter how much we might want to. Attacks on crypto hardware, attacks on management processors, attacks on supervisory or trusted execution modes seldom exercised in normal system operation, attacks on flash modules holding boot code, so that under the right circumstances they replace page P with evil page P', attacks on elements of IC vendors' standard cell libraries (DMA engines would seem promising); assume the adversaries are smart, and good at their jobs, and the sky would seem to be the limit. The sky will fall, of course, when various nation-states' agencies really start digging for th