Click here to Skip to main content
14,326,100 members

Bitcoin Traffic Sniffer and Analyzer

Rate this:
4.80 (4 votes)
Please Sign up or sign in to vote.
4.80 (4 votes)
9 Sep 2016CPOL
A Bitcoin traffic sniffer that intercepts bitcoin protocol messages and analyzes them in order to check if bitcoin addresses in transactions are vulnerable.

Console Application

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 2 Image taken from Wikipedia

// This is in the base class for traffic sniffers
public SnifferBase(IPAddress bindTo)
{
    // Create and configure the Raw Socket 
    _socket = new Socket(AddressFamily.InterNetwork, SocketType.Raw, ProtocolType.IP);
    _socket.Bind(new IPEndPoint(bindTo, 0));
    _socket.SetSocketOption(SocketOptionLevel.IP, SocketOptionName.HeaderIncluded, true);                           //option to 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);
    
    // Parse the IP header and based on the  
    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.

// After parsing the IP header, this method is invoked. Here is where magic happens.
protected override void ProcessPacket(ProtocolType protocolType, object packet)
{
    // Bitcoin is build over TCP so, we only want to process TCP protocol
    if (protocolType != ProtocolType.Tcp) return;

    var tcpHeader = (TcpHeader) packet;
    
    // If the destination port is not 8333 that means the it has not bitcoin 
    // node as destination 
    if (tcpHeader.DestinationPort != 8333) return;
    if(tcpHeader.MessageLength == 0) return;

    // Parse the Bitcoin message header
    var btcHeader = new BtcHeader(tcpHeader);
    
    // We are interested only in transaction messages
    if(! btcHeader.Command.StartsWith("tx")) return;

    // Parse the transaction message
    var tx = ParseTx(btcHeader.Payload);
    
    // Here is where we perform our analysis-----------+
                             //                        |
    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);

    // private key
    // x = (s1 * k - e1)/r   % 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):

Image 3

The transaction input structure (TxIn):

Image 4

Image taken from Bitcoin wiki

And here we have the same transaction example as we have to parse.

var rtx = new byte[] {
    /*   0 - Version   */ 0x01, 0x00, 0x00, 0x00,
    /*   4 - # inputs  */ 0x02,
        /*   5 - in #1     */ 
            /*   5 - prev output */ 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, 
            /*  32 - output idx  */ 0x01, 0x00, 0x00, 0x00, 
            /*  41 - script len*/ 0x8a, 
            /*  42 - script    */ 0x47, /*len*/ 0x30, 0x44, //signature length 
            /*  45 - signature R   */ 0x02, 0x20,
            /*  47 */                 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, 
            /*  79 - signature S   */ 0x02, 0x20, 
            /*  81 */                 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, 
            /* 113 - hashtype      */ 0x01, 
            /* 114 - pubkey    */ 0x41, 
            /* 115 */                 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,
        /* 184 - in #2     */ 
            /* 184 - prev output */ 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, 
            /* 216 - output idx  */ 0x01, 0x00, 0x00, 0x00, 
            /* 220 - script len*/ 0x8a, 
            /* 221 - script    */ 0x47, 0x30, 0x44, 
            /* 224 - signature R   */ 0x02, 0x20, 
            /* 226 */                 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, 
            /* 258 - signature S   */ 0x02, 0x20, 
            /* 260 */                 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, 
            /* 292 - hashtype      */ 0x01, 
            /* 293 - pubkey    */ 0x41, 
            /* 294 */                 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, 
            /* 359 */                 0xff, 0xff, 0xff, 0xff,
    /* 363 - # outputs */ 0x01,
    /* 364 - out #1    */  
    /* 365 - value     */ 0xa0, 0x86, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 
    /* 373 - pk_script len */ 0x19, /* pk_script is 25 bytes long */ 
    /* 378 - pk_script */ 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,
    /* 398 - locktime  */ 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();
			// Read the transaction inputs
			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();
				// And here we have the R value
				input.rawR = reader.ReadStringAsByteArray();
				vv = reader.ReadByte();
				// And the S value
				input.rawS = reader.ReadStringAsByteArray();
				input.HashType = reader.ReadByte();
				input.PublicKey = reader.ReadStringAsByteArray();
				input.Seq = reader.ReadInt32();
				tx.Inputs.Add(input);
			}
			// Read the transaction outputs
			.....
			..... 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.

// Find duplicated R values
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Lucas Ontivero
Architect
Argentina Argentina
No Biography provided

Comments and Discussions

 
Questionhow to run?? Pin
Member 1432083220-Apr-19 7:39
memberMember 1432083220-Apr-19 7:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 7 Sep 2016

Stats

18K views
463 downloads
8 bookmarked