bcgit / bc-java

Bouncy Castle Java Distribution (Mirror)
https://www.bouncycastle.org/java.html
MIT License
2.33k stars 1.14k forks source link

Constant time signing Schnorr and ECDSA with BC #703

Open ghost opened 4 years ago

ghost commented 4 years ago

Hello, I'm using ECDSA signing for a bitcoin implementation in java. and i have one question and one request if its possible

First Is the ECDSA signing with ECDSASigner(HMacDSAKCalculator(SHA2561Digest)) constant time?

Secondly, I'm using bouncy castle to implement Schnorr signatures. Using a variant of HMacDSAKCalculator(SHA2561Digest) The only difference is that at init we include a piece of additional data to avoid issues with ECDSA signing. nextK is identical as HMacDSAKCalculator. what should i look into making this implementation constant time?

    def sign(unsigned: ByteVector, privkey: PrivateKey): Signature = {
      val privkeyNum    = privkey.toBigInteger
      val privkeyParams = new ECPrivateKeyParameters(privkeyNum, ecc.domain)
      val N             = ecc.domain.getN
      val G             = ecc.domain.getG

      /** Calculate k*/
      val nonceFunction = nonceRFC6979
      nonceFunction.init(N, privkeyParams.getD, unsigned.toArray, additionalData.toArray)
      val k0 = nonceFunction.nextK.mod(N)

      /** R = k * G. Negate nonce if R.y is not a quadratic residue */
      val R = G.multiply(k0).normalize
      val k = if (hasSquareY(R)) k0 else N.subtract(k0)

      /** e = Hash(R.x || compressed(P) || m) mod n */
      val P        = G.multiply(privkeyNum)
      val pubBytes = P.getEncoded(true).toByteVector
      val rx       = R.getXCoord.toBigInteger.toUnsignedByteVector
      val e        = Sha256.hash(rx ++ pubBytes ++ unsigned).toBigInteger.mod(N)

      /** s = (k + e * priv) mod n */
      val s = e.multiply(privkeyNum).add(k).mod(N).toUnsignedByteVector

      /** Signature = (R.x, s) */
      val sig = rx ++ s
      Signature(sig)
    }

The K Generator is here https://gist.github.com/sken77/f8b7d2a06e6a6dc703e77c609218d26d

From what I understand the problem could be on the multiplication of kG. does the Bouncy castle does this in constant time? Thanks!

ghost commented 4 years ago

https://crypto.stackexchange.com/questions/80492/how-to-confirm-my-implementation-is-constant-time/80493#80493

I asked here, and they basically said its impossible with BC. They also included some recommendations. what else you think i can do to mitigate issues with BigIntegers