Possible new vulnerability: poor entropy in Windows generated keypairs..

[Sergio_Demian_Lerner]

I'm making this (non-)vulnerability public since I'm quite sure that there is no immediate danger, but the source code should be modified by the core dev-team for the next version.

In the Bitcoin Windows client, entropy is provided by:

1. RAND_Screen at initialization (in util.cpp)
2. Periodic calls to RandAddSeedPerfmon()

But the second method may present two problems:

A. RandAddSeedPerfmon() calls RandAddSeed() that calls QueryPerformanceCounter() which gets a timestamp with about 25 bits of real entropy (since service applications tend to be run when the computer starts). But QueryPerformanceCounter() requires the argument to be QWORD aligned, and I'm not sure if gcc aligns to 8-byte boundaries (I think it aligns to 4-byte). So maybe the call sometimes fails quietly, and these entropy bits are never returned.

B. RandAddSeedPerfmon() calls RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global" with a fixed buffer size of 250000. If the returned data is bigger than this buffer, it fails. But in my XP (and probably in many other systems) the returned data is around 280 Kb, so this functions fails quietly.

At the end, the ONLY source of random may be RAND_Screen with no entropy reseeding taking place.


Note that the first keypair is created with just two calls to RandAddSeedPerfmon(), so it would be possible to guess keys if RAND_Screen would not be strong enough. (Luckily it is in XP and above).

The problem I see is that there is nothing logged in the debug.log file or message telling the user that he may be generating weak keys.  Both failures of QueryPerformanceCounter() and RegQueryValueExA should be logged and the user should be alarmed.

To the dev-team: please don't remove RAND_Screen (interesting talk at http://bitcoinstats.com/irc/bitcoin-dev/logs/2012/06/04)

Best regards,
 Sergio.

PS: Congratulations Gavin for the Bitcoin Foundation!

[Mike Hearn]

Keypairs are generated by OpenSSL which has its own code for getting entropy from the host system. Are you sure your conclusions are correct?

[Gavin Andresen]

Is there a good open source piece of code we can use to test to make sure we're generating good entropy?

These bugs should be investigated and fixed (Sergio can you open issues on github?), but I'd like a test we could periodically run to make sure they stay fixed. Even better is if the code could monitor itself and let the user know if there's a problem with entropy generation.

[Sergio_Demian_Lerner]

Keypairs are generated by OpenSSL which has its own code for getting entropy from the host system. Are you sure your conclusions are correct?

Yes, as I said: RAND_Screen seems strong enough. (check OpenSSL code at openssl-1.0.1c\crypto\rand\rand_win.c)

OpenSSL does not add additional entropy by itself: the user must call RAND_poll() periodically. Only the first time RAND_Bytes is called OpenSSL calls RAND_poll().

[Sergio_Demian_Lerner]

Is there a good open source piece of code we can use to test to make sure we're generating good entropy?

These bugs should be investigated and fixed (Sergio can you open issues on github?), but I'd like a test we could periodically run to make sure they stay fixed. Even better is if the code could monitor itself and let the user know if there's a problem with entropy generation.

You could run Diehard tests (http://en.wikipedia.org/wiki/Diehard_tests) but they won't detect low entropy unless you generate terabytes of data to test. I don't think it would work.

I said before, since RAND_Screen calls CryptGenRandom() which is supposed to be strong, entropy should be enough.
But again! OpenSSL will not tell the function caller if CryptAcquireContext() fails and so CryptGenRandom()  is never called.

I not sure how CryptAcquireContext() can fail, but there are so many failure error codes that I suppose it will fail sometimes! (I would prefer fail-safe semantics that informs the user of the actual entropy acquired for RAND_Screen)
(check http://msdn.microsoft.com/en-us/library/windows/desktop/aa379886%28v=vs.85%29.aspx)

The best solution I can think of is to notify the user if the entropy generation code is not working.

Note that Bitcoind running in Windows 2000 or earlier would probably suffer from lack of entropy, but I think Win2K is not supported.

[Peter Todd]

OpenSSL implements a strong PRNG-based random pool, so in addition to other entropy gathering why don't we seed the random number generator at startup with all the private keys in the wallet? That'd quite effectively act as a persistent entropy source with protections just as good as the wallet it's trying to protect in the first place. It's also perfectly safe:

When using data to seed the RNG state, the data used should not be extractable from the RNG state. I believe this should be a requirement because one possible source of 'secret' semi random data would be a private key or a password. This data must not be disclosed by either subsequent random numbers or a 'core' dump left by a program crash.

http://www.openssl.org/docs/crypto/rand.html

as the data added is hashed into the pool using a cryptographically strong hash function. Equally hashing in the user's decryption password, if the wallet is encrypted, is also safe. Of course, this won't happen until the wallet is decrypted, but random bytes aren't needed until the wallet is decryption anyway. Even with a really broken entropy source, you'll eventually accumulate enough that subsequent keys are safe. Also, if we accidentally release a version with a broken source, that won't immediately break key generation for users who already have wallets.

I could probably cook up a patch sometime after next week if no-one beats me too it.

Edit: come to think of it, if people are worried that inserting keypairs could somehow leak data in the event of a break in the OpenSSL library or something, insert half of each key, the same half each time. Even cracking a key with half the bits known is approximately a formidable 2^128 problem. I dunno exactly how the ECC key format works, so maybe I should pick specific bits, any insight on that?

[kjj]

Erm.  The general principle in cryptography is not to use the same entropy twice, if you can possibly avoid it.

Also, if you have a problem with your entropy source, feeding that low entropy input back in doesn't seem like it'll help much.

[Peter Todd]

Erm.  The general principle in cryptography is not to use the same entropy twice, if you can possibly avoid it.

Also, if you have a problem with your entropy source, feeding that low entropy input back in doesn't seem like it'll help much.

The thing is, with a proper entropy pool implementation adding in data with zero entropy is safe, and any entropy, however little, accumulates.

Lets suppose my "pool" is exactly two bits of data. We start with it in a known state:

00

I'll add it additional entropy sources using XOR. First, lets add two bits from a broken entropy source, that outputs all ones:

00 xor 11 = 11

Basically that source repeatedly just flips the bits from one to the other. However, now I'm going to add in an entropy source where the first bit is broken, but the second bit is truly random:

00 xor 11 xor 1? = 0?

The attacker can figure out the first bit, but not the second. Lets add that totally broken entropy source again:

00 xor 11 xor 1? xor 11 = 1?

The attacker *still* can't guess the second bit. Now lets add an entropy source with the second bit broken, but the first bit OK:

00 xor 11 xor 1? xor 11 xor ?1 = ??

Totally random. Similarly in Bitcoin, if you take all the private keys in your keystore, XOR them together to create a seed, you'll have at least as much entropy in that seed as any one key in your keystore contains. If all you did was hash that seed to generate your next key and saved that key, XORing all your private keys together would still produce a seed with the same amount of entropy.

OpenSSL's default random pool method, RAND_SSLeay in crypto/rand/md_rand.c, works in a kinda similar way. Data added to the pool is hashed, and then added to a rotating set of multiple blocks. When you want some bytes, those blocks get XORed together into a state, and the hash of that state is returned to the caller. (er, roughly anyway, I might have missed something reading the source code) This file is also where the Debian project screwed up and broke SSL key generation a few years back... We really want to avoid a similar mistake at all costs. Bitcoin on Debian systems in 2008 might have left your private keys guessable.

http://en.wikipedia.org/wiki/Fortuna_(PRNG) is a good explanation of another good PRNG, with provable bounds on how long it takes to get back to a secure system after a key compromise.

Anyway, I wrote up really rough notes/sketched out code on how you'd actually implement this idea: https://github.com/petertodd/bitcoin/blob/devel.persistent-seed/persistent-seed-notes.txt

[Diapolo]

Some time ago I was looking at our RandAddSeed()-functions and came to a similar conclusion, that the registry hive thing with perf data is not the best thing we could do, as the MS CryptoAPI offers a function to generate random data (which is used by OpenSSL anyway), with better sources of entropy (although it's a closed-source MS function).

Below is my version of RandAddSeed(), which replaces RandAddSeedPerfmon() and is always used then.

Code:

void RandAddSeed()
{
    int64 nStart = 0;
    if (fDebug)
        nStart = GetTimeMillis();

    // Seed with CPU performance counter
    int64 nCounter = GetPerformanceCounter();
    RAND_add(&nCounter, sizeof(nCounter), 1.5);
    memset(&nCounter, 0, sizeof(nCounter));

#ifdef WIN32
    HCRYPTPROV hCryptProv;
    unsigned char pdata[250000];
    memset(pdata, 0, sizeof(pdata));
    unsigned long nSize = sizeof(pdata);

    if (CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
    {
        //  fills pdata with cryptographically random bytes
        if (CryptGenRandom(hCryptProv, nSize, pdata))
        {
            RAND_add(pdata, nSize, nSize/100.0);
            memset(pdata, 0, nSize);
            if (fDebug)
                printf("RandAddSeed() %d bytes in %"PRI64d"ms\n", nSize, GetTimeMillis() - nStart);
        }
        CryptReleaseContext(hCryptProv, 0);
    }
#endif
}

Here is a small bench comparison:
old:
RandAddSeedPerfmon() 198396 bytes in 1548ms
new (MS CryptoAPI):
RandAddSeed() 250000 bytes in 16ms

Edit 1: After your read I'm now sure it's better to not think about removing RAND_screen() !

Dia

[Dabs]

In many encryption software (even for Windows) they ask users to help seed by gathering mouse movements and keyboard input. If the bitcoin client can use a file as a seed (command line options maybe) then we can generate a file just for this purpose using the many available password generating tools, or a hash of a random picture taken from a camera aimed at the sky. (Or even a video file.)

This one would be an advanced feature or a power user feature.

[Sergio_Demian_Lerner]

These are my opinions (which are more based on intuition and experience than on theoretical grounds that I can cite).
They are based on how the system would respond to a failure of one of the components, as damage control.

1. Don't add private ECC keys as random source.

A failure in OpenSSL random pool would imply the leakage of private keys as a new vector of attack.

2. Use a simple pool state file, with RAND_load_file(). The first time bitcoin is run, gather entropy from keys pressed and save that entropy to the state file. Mix the entropy state file with the current pool state each time the application starts.

3. Don't XOR private ECC keys.

The properties of XOR over the EC field were not analyzed. Hashing them together would be better. Nevertheless if a state file is used, this is not necessary.

4. If half of the private ECC key is disclosed, is possible that the full key is compromised. That happens in many number theoretic ciphers and signature algorithms. Half a private key is NOT half of the security.

5. Call RAND_event() each time we process a Windows message.

6. Leave RAND_Screen where it is (It cannot do any harm).

As the first call to RAND_bytes calls RAND_Poll, RAND_Screen is not strictly necessary. (see http://security.stackexchange.com/questions/7718/openssl-rand-poll-good-enough )

I like Diapolo code but the application should tell the user or halt if CryptAcquireContext fails. 250000 bytes is probably not needed. Just 64 bytes (as in OpenSSL) would be ok.

[Mike Hearn]

Yes, I see now. I was confused by the title of your post which states there is poor entropy in Windows generated keypairs.

But OpenSSL does use the MS random data sources, automatically, which is as I stated, and in fact none of the random-pool setup code in util.cc is necessary.

So I agree with you that there is no vulnerability.

[Sergio_Demian_Lerner]

But OpenSSL does use the MS random data sources, automatically, which is as I stated, and in fact none of the random-pool setup code in util.cc is necessary.

So I agree with you that there is no vulnerability.

The point is that we really don't know if CryptAcquireContext() in RAND_Screen fails. OpenSSL tells nothing to the user about it.

I don't even known in which situations it can fail. Maybe "Windows HOME BASIC For Childen under 13" does not support it. Or Maybe "Windows for Cuba"  does not either because crypto export controls...

[Diapolo]

But OpenSSL does use the MS random data sources, automatically, which is as I stated, and in fact none of the random-pool setup code in util.cc is necessary.

So I agree with you that there is no vulnerability.

The point is that we really don't know if CryptAcquireContext() in RAND_Screen fails. OpenSSL tells nothing to the user about it.

I don't even known in which situations it can fail. Maybe "Windows HOME BASIC For Childen under 13" does not support it. Or Maybe "Windows for Cuba"  does not either because crypto export controls...

I had that discussion on IRC, you linked it above, and my initial question was similar, do we need the util.cpp stuff for entropy and what does it add. Then I intended to speedup the process and requested to remove RAND_screen(), which should be kept. Anyway, I'm rather sure Gavin dislikes the idea of removing it entirely and if I extend my code with a debug.log warning on failing CryptAcquireContext() it should not hurt + we kick that registry hive access out, which is pretty slow and adds nothing IMHO.

Dia

[Peter Todd]

These are my opinions (which are more based on intuition and experience than on theoretical grounds that I can cite).
They are based on how the system would respond to a failure of one of the components, as damage control.

1. Don't add private ECC keys as random source.

A failure in OpenSSL random pool would imply the leakage of private keys as a new vector of attack.

Well, what's your threat model? If it's just low entropy, your second suggestion below solves the problem very well, modulo theoretical worries that the pool state should be encrypted on disk. If we're worried about bugs or malicious code, then at the extreme we're screwed anyway as we already trust our keys to OpenSSL.

However, if we assume that the ECC-related code, and SHA256-related code works, which is core to Bitcoin's security anyway, then a reasonable approach is still creating a hash of the users passphrase/some enciphered keys and private keys and either sending that to RAND_add() or hashing in RAND_bytes() and using the result of that as the next key material. The worst that can happen with is you've fallen back to a deterministic key algorithm with no key strengthening, quite like sipa's proposal. It's also highly unlikely to leak data in the output of the SHA256 hash, as that implies that digests aren't being correctly calculated which will be noticed very quickly. You want to be sure that secure memory is being used by the SHA256 routines of course, but that's already required with a deterministic key system anyway.

Using the digest directly, rather than sending it to RAND_add(), does add critical code that could have bugs in it though. We're essentially creating a parallel PRNG; smells like over-engineering.

2. Use a simple pool state file, with RAND_load_file(). The first time bitcoin is run, gather entropy from keys pressed and save that entropy to the state file. Mix the entropy state file with the current pool state each time the application starts.

Designing PRNG's is fun and all, but no, the code is already written so I'd rather see this done than my proposal.

How does RAND_file_name() work on windows? Putting the PRNG next to the user's keyfile is reasonable, and might head off users asking why stuff is getting written to locations other than the keyfile directory. (default file_name behavior) Either way, RAND_load_file() at startup and RAND_save_file() when the wallet is modified on disk sounds reasonable to me. Again, I'll write up a patch if no-one else beats me to it.

3. Don't XOR private ECC keys.

The properties of XOR over the EC field were not analyzed. Hashing them together would be better. Nevertheless if a state file is used, this is not necessary.

4. If half of the private ECC key is disclosed, is possible that the full key is compromised. That happens in many number theoretic ciphers and signature algorithms. Half a private key is NOT half of the security.

Exactly what I was worried about.

5. Call RAND_event() each time we process a Windows message.

6. Leave RAND_Screen where it is (It cannot do any harm).

Both good ideas.

[Mike Hearn]

The Windows random source probably includes the timings and various data of hardware events, at any rate, if there's a weakness in the Windows CSPRNG and OpenSSL uses that it's a much bigger issue than just with Bitcoin.

Apparently CryptGenRandom is just a wrapper for RtlGenRandom for some time now. I suspect it doesn't even use the crypto context parameter anymore.

Anyway, if you think the OpenSSL code is bugged and incorrectly using the Windows API, that's a discussion to have in the OpenSSL forums.

[runeks]

Edit: come to think of it, if people are worried that inserting keypairs could somehow leak data in the event of a break in the OpenSSL library or something, insert half of each key, the same half each time. Even cracking a key with half the bits known is approximately a formidable 2^128 problem. I dunno exactly how the ECC key format works, so maybe I should pick specific bits, any insight on that?

As far as I know, cracking a 128 bit ECC key requires only 2^64 operations on average using Pollard's rho algorithm. Considering a 109-bit key has been compromised in 2004, I wouldn't consider a 128 bit key to be sufficient.

[Dabs]

Instead of just automatically generating random keys when the client starts, why not an option to generate a fresh wallet? With input on several factors: How many keys? (default 100), and then you can ask the user to generate, so there is an option to wait (timings) and to move the mouse around or keyboard inputs.

You could also ask the user if he wants it encrypted, and skip the unencrypted generating part completely, which seemed to be an issue prior to 0.7.1. (satoshi client)