1
$\begingroup$

I have been given the task to test the security of our company software. Our company software generates ecdsa signed supply order files. One can generate as many files as he wants.

so my question is Is there any ECDSA Attack if I have millions of signatures?

we are using 112bit prime curve order: 4451685225093714776491891542548933

I have calculated 1 million signatures using the following method:

public void GenerateSignature()
{
    //curve order
    BigInteger n = ec.N;

    Ramdom rand = new Random();

    //private key
    BigInteger d = ((ECPrivateKeyParameters)key).D;


    //loop for 1 million signatures
    for (int i = 1; i <= 1000000; i++)
    {
        //random k and e
        BigInteger e = new BigInteger(112, rand).Mod(n);        //new biginteger by giving bitlength and random
        BigInteger k = new BigInteger(112, rand).Mod(n);

        //calculate r
        BigInteger r = key.Parameters.G.Multiply(k).X.ToBigInteger().Mod(n);

        //calculate s
        BigInteger s = k.ModInverse(n).Multiply(e.Add(d.Multiply(r))).Mod(n);

        //save generated signatures to database
        new DBCon().ExecuteNonQuery("Insert into signatures values ('" + e.ToString() + "', '" + r.ToString() + "', '" + s.ToString() + "')");
    }   
}

I am using BouncyCastle crypto library with C#.

I know private key can be calculated if k value is known by d = (sk - e) / r

I also know private key can be calculated if two signatures have identical r value then we can calculate k by k = (e1 - e2) / (s1 - s2) and then d by using above formula.

I also know that private key can be calculated if some bits of k are known using about 100 signatures with lattice attacks, but in this case bits of k are unknown.

any help will be appreciated. Thanks.

$\endgroup$
  • 1
    $\begingroup$ 112 bits supply less than 56 bits of security, the same security provided using single DES. Tell the company that if you want to convince them that this is not secures. Using a larger curve and a cryptographic library would probably have been faster and more secure, at the expense of about 20 million bytes to store 1 million signatures. I'm not sure if this code was created because of the programmer or overactive bean counter, but it will now start to cost money. $\endgroup$ – Maarten Bodewes Feb 24 '18 at 13:39
  • $\begingroup$ No the code is only used by me for testing purpose only, 20 million bytes are costing my personal laptop not the company. I need very strong reason to convince them and I am searching for one. $\endgroup$ – rajadr99 Feb 24 '18 at 16:47
  • $\begingroup$ Ah, OK, good. Well you've got your reasons to change now anyway :) $\endgroup$ – Maarten Bodewes Feb 24 '18 at 18:42
2
$\begingroup$

In the question's particular context, and ignoring the preamble, yes, the private key can be found (assuming the public key is known, which is a standard assumption). I see two ways, the first using no signature at all, the second likely requiring only a few ones.

  • Mere knowledge of the public key allows to find the private key for the curve secp112r1, using moderate brute force and 2009 technology. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in IJACT 2012.

  • As an artifact of the code shown in the question, we get in the database the result of BigInteger e = new BigInteger(112, rand).Mod(n); where rand is an instance of the basic, non cryptographically-secure Random. With a little digging (left a an exercise to the reader) in the source code of this BigInteger constructor (likely equivalent to this) and of Random, it should be possible to mount an attack recovering the state of rand, and the rest is easy.

In real life, it is possible we would not be so lucky as to have the second avenue. Yet, if the non-cryptographically secure Random was used, we might be able to attack its seed, or multiple signatures could be sharing the same $k$ due to poor seeding (but in the question, repeated $k$ is unlikely).

$\endgroup$
  • $\begingroup$ Yes public key is known because it is used to verify signatues. And yes you are right "second avenue" is not possible because we are using deterministic k generation approach in software, the code given in question is just used by me for testing purpose only. According to this equation s = (e + rd) / k we have one million e , r , s values d is common in calculation of every s and k is different, so I was wandering if there is any mathematical solution or any algorithm to find d by using all one million signatures, I mean sorting them out or something like that. $\endgroup$ – rajadr99 Feb 24 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.