Need a new function for a recovery(v) for HSM

[drhanlondon]

Hello,

I am building a custodial wallet with AWS KMS for Polkadot blockchain (with ecdsa scheme). This research is motivated from AWS blockchain research (https://aws.amazon.com/blogs/database/part1-use-aws-kms-to-securely-manage-ethereum-accounts/) where a private key is created and stored HSM (Hardware Security Module), a private key never leaves HSM and a transaction payload is signed offline in HSM.

We can see clearly that Polkadot-JS heavily depends on Noble-curves:
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/sign.ts#L19
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/verify.ts#L16
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/recover.ts#L7

So, I have very carefully looked at two Git repositories (here and https://github.com/paulmillr/noble-curves).

To sign a transaction payload offline with AWS KMS, I create a transaction object and pass it to AWS KMS, and then KMS returns "r" and "s" values. Next I need compose a signature from these “r” and "s” values with “recovery (v)” . But here my problem is that I myself have to calculate "v" value.

Using Noble-curves, Polkadot-JS gets "v" as well as “r” and "s” , as we see https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/sign.ts#L32

So, I have investigated the process of calculating "recovery" from here ( https://github.com/paulmillr/noble-curves/blob/d5de5d2659d5268f5731579b0cf0f48e3358ad37/src/abstract/weierstrass.ts#L968)

This recovery (v) value should be either 0 or 1. I have defined the function getRecovery which takes three areguments (encodedHash of transaction payload, "r" value and "s" value) where "r" and "s" are already provided by AWS KMS. This function is created from a little modification of the original code

    import { Point } from './noble-secp256k1';
    
    const B256 = 2n ** 256n;                                // secp256k1 is short weierstrass curve
    const N = B256 - 0x14551231950b75fc4402da1732fc9bebfn;  // curve (group) order
    const P = B256 - 0x1000003d1n;                          // curve's field prime
    type Bytes = Uint8Array; type Hex = Bytes | string; type PrivKey = Hex | bigint;
    const padh = (n: number | bigint, pad: number) => n.toString(16).padStart(pad, '0');
    
    const b2h = (b: Bytes): string => Array.from(b).map(e => padh(e, 2)).join(''); // bytes to hex
    
    const b2n = (b: Bytes): bigint => BigInt('0x' + (b2h(b) || '0')); // bytes to number
    
    const bits2int = (bytes: Uint8Array): bigint => {       // RFC6979: ensure ECDSA msg is X bytes.
        const delta = bytes.length * 8 - 256; // RFC suggests optional truncating via bits2octets
        const num = b2n(bytes); // FIPS 186-4 4.6 suggests the leftmost min(nBitLen, outLen) bits, which
        return delta > 0 ? num >> BigInt(delta) : num; // matches bits2int. bits2int can produce res>N.
    };
    
    const mod = (a: bigint, b = P) => { let r = a % b; return r >= 0n ? r : b + r; }; // mod division
    const err = (m = ''): never => { throw new Error(m); }; // error helper, messes-up stack trace
    
    const inv = (num: bigint, md = P): bigint => {          // modular inversion
        if (num === 0n || md <= 0n) err('no inverse n=' + num + ' mod=' + md); // no neg exponent for now
        let a = mod(num, md), b = md, x = 0n, y = 1n, u = 1n, v = 0n;
        while (a !== 0n) {                                    // uses euclidean gcd algorithm
          const q = b / a, r = b % a;                         // not constant-time
          const m = x - u * q, n = y - v * q;
          b = a, a = r, x = u, y = v, u = m, v = n;
        }
        return b === 1n ? mod(x, md) : err('no inverse');     // b is gcd at this point
      };
    
    const { BASE: G, ZERO: I } = Point;                     // Generator, identity points
    
    const lowS = true;
    const moreThanHalfN = (n: bigint): boolean => n > (N >> 1n) // if a number is bigger than CURVE.n/2
    const big = (n: unknown): n is bigint => typeof n === 'bigint'; // is big integer
    const ge = (n: bigint) => big(n) && 0n < n && n < N;    // is group element
    
    export function getRecovery(kBytes: Uint8Array, r_value : bigint, s_value: bigint): number | undefined {
    
        const k = bits2int(kBytes);                         // RFC6979 method.
        if (!ge(k)) return;                                 // Check 0 < k < CURVE.n
       
        const q = G.mul(k).aff();                           // q = Gk
        let r = r_value;                              // r = q.x mod n
        if (r === 0n) return;                               // r=0 invalid
        let s = s_value;   // s = k^-1(m + rd) mod n
        if (s === 0n) return;                               // s=0 invalid
        let normS = s;                                      // normalized S
        let rec = (q.x === r ? 0 : 2) | Number(q.y & 1n);   // recovery bit
        if (lowS && moreThanHalfN(s)) {                     // if lowS was passed, ensure s is always
          normS = mod(-s, N);                               // in the bottom half of CURVE.n
          rec ^= 1;
        }
    
        rec = rec - 2; // before this line, rec is either 2 or 3; but is should be 0 or 1
        return rec
    }

This function returns either 0 or 1. We have a half-and-half chance to get a correct value, either 0 or 1. This function returns a wrong value sometimes, so I have failed to recover a correct a public Key.

I would be very grateful if you could advise me or correct the code above.

Thanks.

[paulmillr]

To produce rec using this code, you will need kBytes. kBytes is not a "hash of transaction payload" - it's something completely different. Leaking kBytes it could lead to leaking your private key.

As you can see from the code below, same r/s with different recovery ids will produce different public keys, all of which are VALID and pass verification test.

So, I don't think it's possible to calculate v.

import { secp256k1 } from '@noble/curves/secp256k1';
import { bytesToHex } from '@noble/curves/abstract/utils';

const priv = secp256k1.utils.randomPrivateKey();
const pub_original = bytesToHex(secp256k1.getPublicKey(priv));
const msgHash = 'cafecafecafecafecafecafecafecafecafecafecafecafecafecafecafecafe';
const signed = secp256k1.sign(msgHash, priv);

[0, 1, 2, 3].forEach(rec => {
  const sig = new secp256k1.Signature(signed.r, signed.s);
  const sig_v = sig.addRecoveryBit(rec);
  let pub_recovered;
  try {
    pub_recovered = sig_v.recoverPublicKey(msgHash).toHex();
  } catch (error) {
    return;
  }
  console.log('recovered == original', pub_original === pub_recovered);
  console.log('verify', secp256k1.verify(sig_v, msgHash, pub_recovered));
})

[drhanlondon]

Thanks for your comments.

1. from your comment "same r/s with different recovery ids will produce different public keys", you are right. But verification will fail except for the one correct public key. So, we are looking for a correct recovery value, which is either 0 or 1 on Polkadot case.

2. Finding a correct recovery value from "r" and "s" values, which are calcualted and provided by an external custodial wallet like AWS KMS, is definitely possible. From aws research I mentioned above and git repo (https://github.com/aws-samples/aws-kms-ethereum-accounts/blob/b17779a89c8c072ecb6a03293f0e6ab2ef0d3aca/aws_kms_lambda_ethereum/_lambda/functions/eth_client_eip1559/lambda_helper.py#L137), we have successfully built custodial wallets for Ethereum and XRPL blockchains so far by finding a correct "v".

3. could you explain more what kBytes: Uint8Array is for, please?

I would be very grateful if you could advise me further on the three points above.

Thanks.

[paulmillr]

But verification will fail except for the one correct public key

No, it will not fail. It will succeed. Run my code above and you will see that it verifies same msg and r/s with 2 different public keys.

If you also store public key, or eth address somewhere, then yes, it's possible to compare the public key / address to a recovered public key.

The code above brute-forces all recovery values. You can use it to get recovery id, but only if you already have address/public key.