[cryptography] Fatal flaw in Taiwanese smart card RNG

Jeffrey Goldberg jeffrey at goldmark.org
Tue Sep 17 01:30:10 EDT 2013

On 2013-09-16, at 11:56 AM, Seth David Schoen <schoen at loyalty.org> wrote:

> Well, there's a distinction between RNGs that have been maliciously
> designed and RNGs that are just extremely poor

This has been something that I’ve been trying to learn more about in the past week or so. And if this message isn’t really appropriate for this list, please suggest alternatives.

Roughly, I’m trying to figure out how bad the (allegedly) RNGs that come with Apple or Microsoft Operating systems could be without that badness being discovered. I’m not talking about the spectacularly awful RNG apparently used for Taiwanese Citizen Digital Certificate cards.   Previously I’d only thought about this in terms of accidental badness; it’s hard to get these things right. But more recently, I’ve had to think in terms of malicious implementation.

Now when I say, “I’ve had to think about” it means little more than me just thinking about it. I don’t have the skills or training necessary to actually make much progress in my thinking.

My primary concern is with symmetric key generation.  For my application, I’m not looking at streams, and I’m only generating a small number of keys.  So really the question is if I grab 32 bytes from, say, Apple’s SecCopyRandomBytes(), how unsuitable is that to use directly as a key. I *think* an equivalent way of asking this question is do we have an estimate of how big of a Statistical Distance there could be between these RNGs and a uniform distribution without it being detected by public research?

I believe that I can compensate for a non-negligible SD from uniform by just getting for data than the target key length and using something like HKDF(). But is the same approach appropriate if I consider that the RNG may be maliciously bad, but still not bad enough to have been detected?

It seems that a one way to look for a large SD from uniform is to just fetch lots of data and look for collisions. (And without having to look for collisions of factors of public keys as we direct access to the output of the RNG.) But I”m not sure whether that is sufficient to demonstrate that I am safe using these RNGs as I do.

> It sounds like such extremely poor RNGs are getting used in the wild
> quite a bit, and these problems might well be detected by more
> systematic and widespread use of these researchers' techniques. It's

> true that a maliciously designed RNG would not be detected this way.

If we had access to the private keys, the factors, generated would checking for collisions be sufficient for identifying a maliciously designed RNG? I have no clear intuition on whether that would be sufficient, and I really need to not trust my intuitions anyway.

I’m interested in this both practically (so I can take appropriate defensive measures in app development) and also because I find this stuff fascinating. But I should acknowledge that my linear algebra sucks. I was able to fully understand everything in this research until talk a matrix as generator for a lattice.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4393 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130917/59314188/attachment.p7s>

More information about the cryptography mailing list