Add sanity check after key generation #5224

sipa commented at 9:19 AM on November 6, 2014: member

Add a sanity check to prevent cosmic rays from flipping a bit in the generated public key, or bugs in the elliptic curve code. This is simply done by signing a (randomized) message, and verifying the result.

in src/key.cpp:None in 2637ba2ec5 outdated

 122 | @@ -123,6 +123,20 @@ bool CKey::Sign(const uint256 &hash, std::vector<unsigned char>& vchSig, bool lo
 123 |  #endif
 124 |  }
 125 |  
 126 | +bool CKey::VerifyPubKey(const CPubKey& pubkey) const {
 127 | +    if ((pubkey.size() == 33) != fCompressed) {

laanwj commented at 9:28 AM on November 6, 2014:

Maybe

if (pubkey.IsCompressed() != fCompressed) {

sipa commented at 9:51 AM on November 6, 2014:

Done.

in src/key.h:None in 2637ba2ec5 outdated

 135 | @@ -136,6 +136,12 @@ class CKey
 136 |      //! Derive BIP32 child key.
 137 |      bool Derive(CKey& keyChild, unsigned char ccChild[32], unsigned int nChild, const unsigned char cc[32]) const;
 138 |  
 139 | +    /**
 140 | +     * Verify thoroughly whether a private key and a public key match.
 141 | +     * This is doing using a different mechanism than just regenerating it.

laanwj commented at 9:29 AM on November 6, 2014:

s/doing/done

sipa commented at 9:51 AM on November 6, 2014:

Done doing the s/doing/done/.

in src/key.cpp:None in 2637ba2ec5 outdated

 129 | +    }
 130 | +    unsigned char rnd[8];
 131 | +    std::string str = "Bitcoin key verification\n";
 132 | +    GetRandBytes(rnd, 8);
 133 | +    uint256 hash;
 134 | +    CHash256().Write((unsigned char*)&str[0], str.size()).Write(rnd, sizeof(rnd)).Finalize((unsigned char*)&hash);

laanwj commented at 9:31 AM on November 6, 2014:

please use str.data() instead of &str[0]

sipa commented at 9:51 AM on November 6, 2014:

Done.

in src/key.cpp:None in 2637ba2ec5 outdated

 127 | +    if ((pubkey.size() == 33) != fCompressed) {
 128 | +        return false;
 129 | +    }
 130 | +    unsigned char rnd[8];
 131 | +    std::string str = "Bitcoin key verification\n";
 132 | +    GetRandBytes(rnd, 8);

laanwj commented at 9:32 AM on November 6, 2014:

s/8/sizeof(rnd)/ ? (as you use that below too)

sipa commented at 9:51 AM on November 6, 2014:

Done.

laanwj added the label Priority High on Nov 6, 2014

laanwj added the label Wallet on Nov 6, 2014

in src/key.cpp:None in 2637ba2ec5 outdated

 169 | @@ -156,16 +170,10 @@ bool CKey::Load(CPrivKey &privkey, CPubKey &vchPubKey, bool fSkipCheck=false) {
 170 |          return false;
 171 |      key.GetSecretBytes(vch);
 172 |  #endif
 173 | -    fCompressed = vchPubKey.IsCompressed();
 174 | -    fValid = true;

laanwj commented at 9:42 AM on November 6, 2014:

fCompressed / fValid no longer set?

sipa commented at 9:51 AM on November 6, 2014:

Ugh. Thankfully the tests caught this...

sipa force-pushed on Nov 6, 2014

in src/key.cpp:None in baf4dfede9 outdated

 122 | @@ -123,6 +123,20 @@ bool CKey::Sign(const uint256 &hash, std::vector<unsigned char>& vchSig, bool lo
 123 |  #endif
 124 |  }
 125 |  
 126 | +bool CKey::VerifyPubKey(const CPubKey& pubkey) const {
 127 | +    if (pubkey.IsCompressed() != fCompressed) {
 128 | +        return false;
 129 | +    }
 130 | +    unsigned char rnd[8];
 131 | +    std::string str = "Bitcoin key verification\n";

Diapolo commented at 7:20 PM on November 6, 2014:

What use has the \n here ;)?

sipa commented at 7:21 PM on November 6, 2014:

Exactly as much as the 24 character before it.

in src/key.cpp:None in baf4dfede9 outdated

 127 | +    if (pubkey.IsCompressed() != fCompressed) {
 128 | +        return false;
 129 | +    }
 130 | +    unsigned char rnd[8];
 131 | +    std::string str = "Bitcoin key verification\n";
 132 | +    GetRandBytes(rnd, sizeof(rnd));

Diapolo commented at 7:22 PM on November 6, 2014:

As GetRandBytes() can fail and this is intended as an intensive check you should perhaps consider that.

laanwj commented at 12:32 PM on November 7, 2014:

Huh - I remember changing GetRandBytes to never fail, but stop with an assertion instead. There is no way bitcoin can handle a failing RNG gracefully. Seems that never got merged?

in src/key.cpp:None in baf4dfede9 outdated

 129 | +    }
 130 | +    unsigned char rnd[8];
 131 | +    std::string str = "Bitcoin key verification\n";
 132 | +    GetRandBytes(rnd, sizeof(rnd));
 133 | +    uint256 hash;
 134 | +    CHash256().Write((unsigned char*)str.data(), str.size()).Write(rnd, sizeof(rnd)).Finalize((unsigned char*)&hash);

Diapolo commented at 7:22 PM on November 6, 2014:

Just asking, could (unsigned char*)str.data() be changed to just .c_str()? I guess no, because it's not unsigned ^^.

laanwj commented at 10:35 AM on November 7, 2014:

@diapolo Please don't suggest that. If you want the data (to be used with .size()), use .data(). .c_str() is if you want a null-terminated string.

TheBlueMatt commented at 7:24 PM on November 6, 2014: member

I'd vote this wait on #5220, though concept ACK 100%.

laanwj commented at 10:35 AM on November 7, 2014: member

@TheBlueMatt What rationale to wait? This seems self-contained and a useful sanity check no matter what.

gmaxwell commented at 4:56 PM on November 7, 2014: contributor

Do we want to also add something in init.cpp that generates a rnadom key, verifies, and bombs out if it fails? (so that broken code is more likely to fail at startup with an explicable error message?)

Not just totaly hypotetical: right now fedora's openssl compiles, links, and starts but fails at runtime the first time something tries to actually use the EC code.

theuni commented at 5:00 PM on November 7, 2014: member

@gmaxwell see ECC_InitSanityCheck() in init.cpp. Currently it just tries to call EC_KEY_new_by_curve_name() and returns false if it fails, in which case we die. That could be expanded as you suggest.

TheBlueMatt commented at 5:47 PM on November 7, 2014: member

@laanwj This just leaks even more shit via sidechannels...I'd assume OpenSSL's transform-priv-to-pub does too, but I'd prefer to not add to it. At least secp256k1 tries to not leak too much.

gmaxwell commented at 8:20 PM on November 7, 2014: contributor

The non-constant time ness in signing for openssl is the r*G multply and the computation of k^-1 (which is very not constant time), but since we never publish that data it would be hard to make use of it. (E.g. you leak data about a random number, ... which might be bad if you published the resulting signature, but you don't). So, with this in mind it doesn't concern me much.

sipa commented at 10:30 PM on November 8, 2014: member

@gmaxwell there already was an ECC sanity check as @theuni mentioned, but I've added a commit that does a key generation/verification in that check as well.

sipa force-pushed on Nov 19, 2014

sipa commented at 2:41 PM on November 19, 2014: member

Rebased.

gmaxwell commented at 5:05 PM on November 19, 2014: contributor

It looks like CWallet::AddKeyPubKey also needs to call VerifyPubKey so that rpc imported and newly generated keys get tested too.

sipa commented at 5:12 PM on November 19, 2014: member

Do we want to apply the check to every key loaded at startup? That's probably a significant slowdown...

gmaxwell commented at 5:16 PM on November 19, 2014: contributor

I think so, just once (e.g. not every unlock). The generation of the pubkey each time is already slow, doing this basically quadruples it. Any idea how long it would take for 100k keys?

sipa commented at 5:21 PM on November 19, 2014: member

For unecnrypted wallets we use a hash-based mechanism now; we used to re-derive the public key for every private key before, and apparently that was too slow (to @phantomcircuit, I believe).

gmaxwell commented at 5:28 PM on November 19, 2014: contributor

Okay, well if that was too slow, verifying will be too slow.

sipa added this to the milestone 0.10.0 on Nov 21, 2014

gmaxwell commented at 7:25 AM on November 23, 2014: contributor

@sipa Where are we on this? If putting it at AddKeyPubKey is too much of a perfomance concern, it could just be added at GenerateNewKey, importprivkey, and (maybe?) importwallet.

Add sanity check after key generation

Add a sanity check to prevent cosmic rays from flipping a bit in the
generated public key, or bugs in the elliptic curve code. This is
simply done by signing a (randomized) message, and verifying the
result.

d0c41a7350

Add key generation/verification to ECC sanity check f321d6bfff

sipa force-pushed on Nov 23, 2014

sipa commented at 9:49 AM on November 23, 2014: member

@gmaxwell Done.

gmaxwell commented at 10:38 AM on November 23, 2014: contributor

ACK

jgarzik commented at 2:45 PM on November 23, 2014: contributor

ut ACK

laanwj merged this on Nov 24, 2014

laanwj closed this on Nov 24, 2014

laanwj referenced this in commit 6582f323f0 on Nov 24, 2014

MarcoFalke locked this on Sep 8, 2021