Non interactive anti-exfil

anti-exfil-nonce-generation.md

Signing protocol:

x: private key
X: public key
m: message to sign
n: nonce extra

H: cryptographically secure hash committment

1. signing device

q = H(x,m,n)
Q = q·G
k = q + H(Q,m,n)
R = k·G
e = H(R,X,m)

Schnorr signature

s = k + x·e

ECDSA signature

r = R.x
s = k⁻¹·(m + r·x)

2. return to wallet app

Q, s

3. wallet app calculates

R = Q + H(Q,m,n)·G
R, s

4. verify

Schnorr verify

e = H(R,X,m)

s·G ?= R + e·X

ECDSA verify

r = R.x

s⁻¹·m·G + s⁻¹·r·X ?= R

Q&A

Where does the SD get n from?

Typically an opensource "Companion App" or view only wallet software would provide the n nonce extra.

The PSBT standard can either be extended with a new field, or n may be included as an invalid but recognizable "signature" that the SD replaces with (Q,s).

What is the function of H, why not simply hash the concatenated values?

m1 = "hello ", n1 = "world!"
m2 = "hello", n2 = " world!"
q = hash(x|"hello world!")
Q = q·G
k = q + hash(Q|"hello world!")

Would generate the exact same nonce, but the SD would sign a different message ("hello " and "hello"), allowing malicious software to extract the private key from the device.

s1 = k + x·e1
s2 = k + x·e2
s1 - s2 = (k - k) + x(e1 - e2)

With k eliminated, the private key x is revealed to the malicious software.

What function is appropriate as H?

With fixed sized fields/values hash(v1|v2|..|vn) can be safely used.

With variable size binary strings:

• hash(serialize(v1, v2, .., vn))
• hash(hash(v1)|hash(v2)|..|hash(vn))
• merkle_root(v1, v2, .., vn)

Any reversible serialization may also be used.

For example: hash(6|"hello "|6|"world!") != hash(5|"hello"|7|" world!")

What is the reason for committing to n in generation of q?

Let's take a look at what happens, when we sign the same message twice, with different nonce extras!

q = H(x,m)
Q = q·G
s1 = q + H(Q,m,n1) x·e1
s2 = q + H(Q,m,n2) x·e2
s1 - s2 = (q - q) + H(Q,m,n1) - H(Q,m,n2) + x(e1 - e2)

With q eliminated, the private key x is revealed to the malicious software.

Are low bandwidth attacks still possible?

Yes, theoretically the SD with malicious firmware could churn the final R point to leak information using for example FEC codes (Pieter Wuille on delving) with 2ⁿ rounds of churning SD can leak the seed phrase by creating bits(seed)/n signatures. For example if the attacker chooses to leak 4 bits each time it takes 32 signatures to leak a 128 bit (12 word) seed phrase. Due to the public transaction graph and plainly observable wallet characteristics the attacker can make good guesses at which signatures could belong to the same seed.

• The attacker can just generate a random q, normally this can not be detected
• The verifier needs to know the private key to verify generation of q (same as RFC6979)
• The attacker can encrypt and obfuscate his own channel
• The attacker decides his channel bandwidth making it impossible to estimate "seed health"
• Transactions may have multiple inputs making signing them not deterministic in time
• Said attack is likely to be "always on" and would be caught by verifying generation of q
• Evil maid scenario is still problematic, factory and user acceptance tests are already passed
• Tamper evident storage of signing devices is still heavily recommended
• This is not a huge concern for cold storage scenarios with very infrequent signing
• This protocol offers protection from immediate catastrophic leaks via chosen nonce
• 24 words are better in this scheme than 12 words

References

1. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-March/017667.html (Pieter Wuille 2020)
2. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017649.html
3. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017655.html
4. https://blog.eternitywall.com/2018/04/13/sign-to-contract/
5. https://bitcointalk.org/index.php?topic=893898.msg9861102#msg9861102
6. https://bitcointalk.org/index.php?topic=893898.msg9841502#msg9841502
7. https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199
8. https://youtu.be/j9Wvz7zI_Ac?t=640
9. https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2019-02-04-threshold-signatures-and-accountability/
10. bitcoin-core/secp256k1#590
11. bitcoin-core/secp256k1#669
12. https://eprint.iacr.org/2017/985
13. https://moderncrypto.org/mail-archive/curves/2017/000925.html

One more thing:

    e = tagged_sha256(b"BIP-XYZ",
                      ec_pubkey_serialize(R, compressed=True)
                      + ec_pubkey_serialize(X, compressed=True)
                      + m)

This is definitely wrong, the generation of e and signature must be to the bip-340 standard! But this should be handled by the library, you just provide it with a nonce and a private key and a message! We are only playing with the nonce value itself in this protocol, you can safely ignore the parts for signature generation and verification and use standard library calls for those (if you can)!

@scgbckbone!

There is a function called secp256k1_schnorrsig_sign_internal in secp256k1 which is almost good, but the problem is while secp256k1_nonce_function_hardened could generate q or k to spec, because it has the keypair the message and the extra data (could be nonce extra) it can't really sign with R and return Q, s.

And there is no internal variant for some reason, that just takes a keypair for nonce, which would be ideal for our purposes. In lack of that, one must recreate the functionality of this method with the necessary alterations.

static int secp256k1_schnorrsig_sign_internal(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg, size_t msglen, const secp256k1_keypair *keypair, secp256k1_nonce_function_hardened noncefp, void *ndata) {
    secp256k1_scalar sk;
    secp256k1_scalar e;
    secp256k1_scalar k;
    secp256k1_gej rj;
    secp256k1_ge pk;
    secp256k1_ge r;
    unsigned char buf[32] = { 0 };
    unsigned char pk_buf[32];
    unsigned char seckey[32];
    int ret = 1;

    VERIFY_CHECK(ctx != NULL);
    ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
    ARG_CHECK(sig64 != NULL);
    ARG_CHECK(msg != NULL || msglen == 0);
    ARG_CHECK(keypair != NULL);

    if (noncefp == NULL) {
        noncefp = secp256k1_nonce_function_bip340;
    }

    ret &= secp256k1_keypair_load(ctx, &sk, &pk, keypair);
    /* Because we are signing for a x-only pubkey, the secret key is negated
     * before signing if the point corresponding to the secret key does not
     * have an even Y. */
    if (secp256k1_fe_is_odd(&pk.y)) {
        secp256k1_scalar_negate(&sk, &sk);
    }

    secp256k1_scalar_get_b32(seckey, &sk);
    secp256k1_fe_get_b32(pk_buf, &pk.x);
    ret &= !!noncefp(buf, msg, msglen, seckey, pk_buf, bip340_algo, sizeof(bip340_algo), ndata);
    secp256k1_scalar_set_b32(&k, buf, NULL);
    ret &= !secp256k1_scalar_is_zero(&k);
    secp256k1_scalar_cmov(&k, &secp256k1_scalar_one, !ret);

    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &rj, &k);
    secp256k1_ge_set_gej(&r, &rj);

    /* We declassify r to allow using it as a branch point. This is fine
     * because r is not a secret. */
    secp256k1_declassify(ctx, &r, sizeof(r));
    secp256k1_fe_normalize_var(&r.y);
    if (secp256k1_fe_is_odd(&r.y)) {
        secp256k1_scalar_negate(&k, &k);
    }
    secp256k1_fe_normalize_var(&r.x);
    secp256k1_fe_get_b32(&sig64[0], &r.x);

    secp256k1_schnorrsig_challenge(&e, &sig64[0], msg, msglen, pk_buf);
    secp256k1_scalar_mul(&e, &e, &sk);
    secp256k1_scalar_add(&e, &e, &k);
    secp256k1_scalar_get_b32(&sig64[32], &e);

    secp256k1_memczero(sig64, 64, !ret);
    secp256k1_scalar_clear(&k);
    secp256k1_scalar_clear(&sk);
    memset(seckey, 0, sizeof(seckey));

    return ret;
}

Thank you very much. You cleared up a lot.

the math in the gist is simplified

misunderstood that

Python implementation of bitcoin private/public

above python library is just convenience wrapper around libsecp256k1.so so it uses it "directly"

i would mod with group order

BIP340 uses https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_ref-11-0 but they also mention that mod should be ok on secp256k1 https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_note-13

RFC6979 implementation

we should also take Low R values grinding into consideration, iirc currently we use that extra data to pass counter to nonce_function_rfc6979 for sig grinding (ECDSA only)

So, my understanding is that libsecp (in its current form) only allows us to provide custom noncefp with noncedata for ecdsa_sign and extraparams (with both noncefp and ndata) for secp256k1_schnorrsig_sign_custom. It is possible to generate custom nonce k according to the spec, we just cannot get Q out of noncefp ?

it can't really sign with R

I do not understand this. Looking at your schnorr signing part:

R = k·G
e = hash(R|X|m)
s = k + x·e

it seems to be exactly same as in secp256k1_schnorrsig_sign_internal (BIP340).

Seems to me we could just use those extraparams, define our custom noncefp as in spec:

q = vc(x, m, n)
Q = q·G
k = q + vc(Q, m, n)

and when we need Q we would just recalc it again, outside of noncefp context. We do not need s for companion app as it is part of the signature already. What am I missing ?

Yeah, q = vc(x, m, n) is super similar to what noncefp can do, but we need k = q + vc(Q, m, n) which it could still do.

If we could just do this outside and send two keypairs (k, R, x, X) to secp256k1_schnorrsig_sign_internal that would be great!

An other way is to implement q = vc(x, m, n) and Q = q·G and as you said execute it outside a second time. But then you make the same calc twice.

Third option: re-implement bip-340 Schnorr sigs in python and alter the deterministic nonce generation part only.

improved. still BS most likely. I used secp256k1_schnorrsig_sign_custom with custom noncefp which just passes as result whatever is passed to it as AUX rand data. Real nonce and Q calculations are done beforehand and nonce is only passed to signing algo as argument.

# cpython lib https://github.com/scgbckbone/python-secp256k1
import os, ctypes
from pysecp256k1.low_level.constants import *
from pysecp256k1.low_level import ctypes_functype
from pysecp256k1 import (
    tagged_sha256, ec_seckey_tweak_add, ec_pubkey_combine, ec_pubkey_serialize, ec_seckey_negate,
    ec_seckey_negate, ec_pubkey_negate, ec_pubkey_create
)
from pysecp256k1.extrakeys import (
    keypair_sec, keypair_create, keypair_xonly_pub, xonly_pubkey_serialize,
    xonly_pubkey_parse, keypair_pub
)
from pysecp256k1.schnorrsig import SchnorrsigExtraparams, schnorrsig_verify, schnorrsig_sign_custom


def schnorr_antiexfill_nonce(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes):
    if ec_pubkey_serialize(keypair_pub(keypair))[0] == b"\x03":
        # Because we are signing for a x-only pubkey, the secret key is negated
        # before signing if the point corresponding to the secret key does not
        # have an even Y. */
        sec = keypair_sec(keypair)
        sec_neg = ec_seckey_negate(sec)
        k = keypair_create(sec_neg)
    else:
        k = keypair_create(keypair_sec(keypair))

    t = bytearray(32)  # result of byte-wise xor of private key and ZERO MASK
    #  Precomputed TaggedHash("BIP0340/aux", 0x0000...00);
    ZERO_MASK = bytes([
        84,  241, 105, 207, 201, 226, 229, 114,
        116, 128, 68,  31,  144, 186, 37,  196,
        136, 244, 97,  199, 11,  94,  165, 220,
        170, 247, 175, 105, 39,  10,  165, 20,
    ])
    args = [keypair_sec(k), ZERO_MASK]
    for i in range(32):  # byte-wise xor
        for a in args:
            t[i] ^= a[i]

    q = tagged_sha256(b"BIP-XYZ/nonce", bytes(t + msg + nonce_commit))
    # Q = q·G
    q_kp = keypair_create(q)
    Q_xonly, parity = keypair_xonly_pub(q_kp)
    Q_ser = xonly_pubkey_serialize(Q_xonly)
    # k = q + vc(Q, m, n)
    if parity:
        # sec key was negated when creating Q_xonly
        # need to negate also q
        q = ec_seckey_negate(q)

    k = ec_seckey_tweak_add(q, tagged_sha256(b"BIP-XYZ/nonce", bytes(Q_ser + msg + nonce_commit)))
    print("\tR", xonly_pubkey_serialize(ec_pubkey_create(k)).hex())
    return k, Q_ser


def schnorrsig_sign_antiexfill(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes):

    k, Q_xonly_ser = schnorr_antiexfill_nonce(keypair, msg, nonce_commit)

    NONCEFP_CLS = ctypes_functype(
        ctypes.c_int,
        ctypes.POINTER(ctypes.c_char * 32),  # nonce32
        ctypes.POINTER(ctypes.c_char * 32),  # msg
        ctypes.c_size_t,
        ctypes.POINTER(ctypes.c_char * 32),  # secret key
        ctypes.POINTER(ctypes.c_char * 32),  # xonly pubkey
        ctypes.POINTER(ctypes.c_char * 32),  # algo
        ctypes.c_size_t,  # algolen
        ctypes.c_void_p,  # void *data
    )

    def BIPXYZ_nonce_fp(nonce32, msg, msg_len, sk, xonly_pk, algo, algo_len, data):
        # take already calculated nonce from data and put to output arg nonce32
        try:
            k = (ctypes.c_char * 32).from_address(data).raw
            nonce32.contents.raw = k
            return 1
        except:
            return 0

    noncefp = NONCEFP_CLS(BIPXYZ_nonce_fp)

    extraparams = SchnorrsigExtraparams(
        SCHNORRSIG_EXTRAPARAMS_MAGIC,
        ctypes.cast(noncefp, ctypes.c_void_p),
        ctypes.cast(ctypes.create_string_buffer(k), ctypes.c_void_p),
    )
    sig = schnorrsig_sign_custom(keypair, msg, extraparams)
    return sig, Q_xonly_ser


def hw_sign(x, m, n, evil=False):
    # SIGNING DEVICE
    if evil:
        # do not commit to nonce provided
        print("EVIL HWW")
        n = tagged_sha256(b"evilhww", n)

    k = keypair_create(x)
    sig, QXonly = schnorrsig_sign_antiexfill(k, m, n)
    print("\tsig", sig.hex())
    s = sig[32:]
    k_xonly, parity = keypair_xonly_pub(k)
    assert schnorrsig_verify(sig, m, k_xonly)
    return QXonly, s

def sw_verify(X, pkQ, s, m, n):
    # WATCH-ONLY companion app with extended public keys
    # watch-only wallet knows the corresponding pubkey X
    Q = xonly_pubkey_parse(pkQ)
    # R = Q + vc(Q, m, n)·G
    vc = tagged_sha256(b"BIP-XYZ/nonce", pkQ + m + n)
    kp = keypair_create(vc)
    xonly_pk, parity = keypair_xonly_pub(kp)
    if parity:
        xonly_pk = ec_pubkey_negate(xonly_pk)
    R = ec_pubkey_combine([Q, xonly_pk])
    print("\tR", xonly_pubkey_serialize(R).hex())
    sig = xonly_pubkey_serialize(R) + s
    print("\tsig", sig.hex())
    assert schnorrsig_verify(sig, m, X)


if __name__ == '__main__':
    sk = os.urandom(32)
    print("\nprivate key", sk.hex())
    k = keypair_create(sk)
    X, X_parity = keypair_xonly_pub(k)
    print("public key", xonly_pubkey_serialize(X).hex())
    msg = os.urandom(32)
    print("msg", msg.hex())
    nonce_extra = os.urandom(32)  # from WO app via PSBT
    print("nonce extra", nonce_extra.hex())

    print("HWW:")
    # HW uses new nonce_extra from PSBT
    # tweak evil to True to not commit to nonce_extra
    Q_ser, s = hw_sign(sk, msg, nonce_extra, evil=False)
    print("\tQ", Q_ser.hex())
    print("\ts", s.hex())
    # fill PSBT fields with Q and s, return to WO app
    print("SW:")
    sw_verify(X, Q_ser, s, msg, nonce_extra)
    print()

That's a cool trick! Nice! 🔥
I didn't think of a simple passover dummy nonce_fp. Couldn't find anything wrong with the code, does it verify?

That's a cool trick! Nice! 🔥 I didn't think of a simple passover dummy nonce_fp. Couldn't find anything wrong with the code, does it verify?

yes

# cpython lib https://github.com/scgbckbone/python-secp256k1
import os, ctypes
from pysecp256k1.low_level.constants import *
from pysecp256k1 import (
    tagged_sha256, ec_seckey_tweak_add, ec_pubkey_combine, ec_pubkey_serialize, ec_seckey_verify,
    ec_seckey_negate, ec_pubkey_negate, ec_pubkey_create, ecdsa_sign, ecdsa_verify,
    ecdsa_signature_serialize_der, ecdsa_signature_parse_der, ecdsa_signature_serialize_compact,
    ec_pubkey_parse, ecdsa_signature_parse_compact, Libsecp256k1Exception, ECDSA_NONCEFP_CLS
)
from pysecp256k1.extrakeys import (
    keypair_sec, keypair_create, keypair_xonly_pub, xonly_pubkey_serialize,
    xonly_pubkey_parse, keypair_pub, xonly_pubkey_from_pubkey
)
from pysecp256k1.schnorrsig import (
    SchnorrsigExtraparams, schnorrsig_verify, schnorrsig_sign_custom, SCHNORRSIG_NONCEFP_CLS
)


def ecdsa_antiexfill_nonce(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes, counter: int = 0):
    t = bytearray(32)  # result of byte-wise xor of private key and ZERO MASK
    #  Precomputed TaggedHash("BIP0340/aux", 0x0000...00);
    ZERO_MASK = bytes([
        84,  241, 105, 207, 201, 226, 229, 114,
        116, 128, 68,  31,  144, 186, 37,  196,
        136, 244, 97,  199, 11,  94,  165, 220,
        170, 247, 175, 105, 39,  10,  165, 20,
    ])
    args = [keypair_sec(keypair), ZERO_MASK]
    for i in range(32):  # byte-wise xor
        for a in args:
            t[i] ^= a[i]

    q = tagged_sha256(b"BIP-XYZ/nonce", bytes(t + msg + nonce_commit + bytes([counter])))
    # Q = q·G
    q_kp = keypair_create(q)
    Q = keypair_pub(q_kp)
    Q_ser = ec_pubkey_serialize(Q)
    # k = q + vc(Q, m, n)
    k = ec_seckey_tweak_add(q, tagged_sha256(b"BIP-XYZ/nonce", bytes(Q_ser + msg + nonce_commit)))
    print("\tR", ec_pubkey_serialize(ec_pubkey_create(k)).hex())
    return k, Q_ser


def ecdsa_sign_antiexfill(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes):
    counter = 0
    while True:
        k, Q_ser = ecdsa_antiexfill_nonce(keypair, msg, nonce_commit, counter)
        try:
            ec_seckey_verify(k)  # nonce needs to be a valid private key
            break
        except Libsecp256k1Exception:
            counter += 1

    def BIPXYZ_ecdsa_nonce_fp(nonce32, msg, sk, algo, data, counter):
        # take already calculated nonce from data and put to output arg nonce32
        try:
            k = (ctypes.c_char * 32).from_address(data).raw
            nonce32.contents.raw = k
            return 1
        except:
            return 0

    noncefp = ECDSA_NONCEFP_CLS(BIPXYZ_ecdsa_nonce_fp)

    sig = ecdsa_sign(
        keypair_sec(keypair),
        msg,
        ctypes.cast(noncefp, ctypes.c_void_p),
        ctypes.cast(ctypes.create_string_buffer(k), ctypes.c_void_p),
    )
    return ecdsa_signature_serialize_der(sig), Q_ser


def ecdsa_hww_sign(x, m, n, evil=False):
    # SIGNING DEVICE
    if evil:
        # do not commit to nonce provided
        print("EVIL HWW")
        n = tagged_sha256(b"evilhww", n)

    k = keypair_create(x)
    der_sig, Q = ecdsa_sign_antiexfill(k, m, n)
    print("\tsig", der_sig.hex())
    sig = ecdsa_signature_parse_der(der_sig)
    s = ecdsa_signature_serialize_compact(sig)[32:]
    X = keypair_pub(k)
    assert ecdsa_verify(sig, X, m)
    return Q, s

def ecdsa_sww_verify(X, pkQ, s, m, n):
    # WATCH-ONLY companion app with extended public keys
    # watch-only wallet knows the corresponding pubkey X
    Q = ec_pubkey_parse(pkQ)
    # R = Q + vc(Q, m, n)·G
    vc = tagged_sha256(b"BIP-XYZ/nonce", pkQ + m + n)
    kp = keypair_create(vc)
    pk = keypair_pub(kp)
    R = ec_pubkey_combine([Q, pk])
    print("\tR", ec_pubkey_serialize(R).hex())
    # using xonly serialization below just to get rid of marker
    sig = xonly_pubkey_serialize(R) + s
    print("\tsig", sig.hex())
    assert ecdsa_verify(ecdsa_signature_parse_compact(sig), X, m)


def schnorr_antiexfill_nonce(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes):
    if ec_pubkey_serialize(keypair_pub(keypair))[0] == b"\x03":
        # Because we are signing for a x-only pubkey, the secret key is negated
        # before signing if the point corresponding to the secret key does not
        # have an even Y. */
        sec = keypair_sec(keypair)
        sec_neg = ec_seckey_negate(sec)
        k = keypair_create(sec_neg)
    else:
        k = keypair_create(keypair_sec(keypair))

    t = bytearray(32)  # result of byte-wise xor of private key and ZERO MASK
    #  Precomputed TaggedHash("BIP0340/aux", 0x0000...00);
    ZERO_MASK = bytes([
        84,  241, 105, 207, 201, 226, 229, 114,
        116, 128, 68,  31,  144, 186, 37,  196,
        136, 244, 97,  199, 11,  94,  165, 220,
        170, 247, 175, 105, 39,  10,  165, 20,
    ])
    args = [keypair_sec(k), ZERO_MASK]
    for i in range(32):  # byte-wise xor
        for a in args:
            t[i] ^= a[i]

    q = tagged_sha256(b"BIP-XYZ/nonce", bytes(t + msg + nonce_commit))
    # Q = q·G
    q_kp = keypair_create(q)
    Q_xonly, parity = keypair_xonly_pub(q_kp)
    Q_ser = xonly_pubkey_serialize(Q_xonly)
    # k = q + vc(Q, m, n)
    if parity:
        # sec key was negated when creating Q_xonly
        # need to negate also q
        q = ec_seckey_negate(q)

    k = ec_seckey_tweak_add(q, tagged_sha256(b"BIP-XYZ/nonce", bytes(Q_ser + msg + nonce_commit)))
    print("\tR", xonly_pubkey_serialize(ec_pubkey_create(k)).hex())
    return k, Q_ser


def schnorrsig_sign_antiexfill(keypair: Secp256k1Keypair, msg: bytes, nonce_commit: bytes):

    k, Q_xonly_ser = schnorr_antiexfill_nonce(keypair, msg, nonce_commit)

    def BIPXYZ_schnorr_nonce_fp(nonce32, msg, msg_len, sk, xonly_pk, algo, algo_len, data):
        # take already calculated nonce from data and put to output arg nonce32
        try:
            k = (ctypes.c_char * 32).from_address(data).raw
            nonce32.contents.raw = k
            return 1
        except:
            return 0

    noncefp = SCHNORRSIG_NONCEFP_CLS(BIPXYZ_schnorr_nonce_fp)

    extraparams = SchnorrsigExtraparams(
        SCHNORRSIG_EXTRAPARAMS_MAGIC,
        ctypes.cast(noncefp, ctypes.c_void_p),
        ctypes.cast(ctypes.create_string_buffer(k), ctypes.c_void_p),
    )
    sig = schnorrsig_sign_custom(keypair, msg, extraparams)
    return sig, Q_xonly_ser


def schnorr_hww_sign(x, m, n, evil=False):
    # SIGNING DEVICE
    if evil:
        # do not commit to nonce provided
        print("EVIL HWW")
        n = tagged_sha256(b"evilhww", n)

    k = keypair_create(x)
    sig, QXonly = schnorrsig_sign_antiexfill(k, m, n)
    print("\tsig", sig.hex())
    s = sig[32:]
    k_xonly, parity = keypair_xonly_pub(k)
    assert schnorrsig_verify(sig, m, k_xonly)
    return QXonly, s

def schnorr_sww_verify(X, pkQ, s, m, n):
    # WATCH-ONLY companion app with extended public keys
    # watch-only wallet knows the corresponding pubkey X
    Q = xonly_pubkey_parse(pkQ)
    # R = Q + vc(Q, m, n)·G
    vc = tagged_sha256(b"BIP-XYZ/nonce", pkQ + m + n)
    kp = keypair_create(vc)
    xonly_pk, parity = keypair_xonly_pub(kp)
    if parity:
        xonly_pk = ec_pubkey_negate(xonly_pk)
    R = ec_pubkey_combine([Q, xonly_pk])
    print("\tR", xonly_pubkey_serialize(R).hex())
    sig = xonly_pubkey_serialize(R) + s
    print("\tsig", sig.hex())
    assert schnorrsig_verify(sig, m, X)


if __name__ == '__main__':
    sk = os.urandom(32)
    print("\nprivate key", sk.hex())
    k = keypair_create(sk)
    X = keypair_pub(k)
    print("public key", ec_pubkey_serialize(X).hex())
    msg = os.urandom(32)
    print("msg", msg.hex())
    nonce_extra = os.urandom(32)  # from WO app via PSBT
    print("nonce extra", nonce_extra.hex())

    print()
    print("=== SCHNORRSIG ===")
    print("HWW:")
    # HW uses new nonce_extra from PSBT
    # tweak evil to True to not commit to nonce_extra
    Q_ser, s = schnorr_hww_sign(sk, msg, nonce_extra, evil=False)
    print("\tQ", Q_ser.hex())
    print("\ts", s.hex())
    # fill PSBT fields with Q and s, return to WO app
    print("SW:")
    schnorr_sww_verify(xonly_pubkey_from_pubkey(X)[0], Q_ser, s, msg, nonce_extra)
    print("schnorrsig: OK\n")

    print("=== ECDSA ===")
    print("HWW:")
    # HW uses new nonce_extra from PSBT
    # tweak evil to True to not commit to nonce_extra
    Q_ser, s = ecdsa_hww_sign(sk, msg, nonce_extra, evil=False)
    print("\tQ", Q_ser.hex())
    print("\ts", s.hex())
    # fill PSBT fields with Q and s, return to WO app
    print("SW:")
    ecdsa_sww_verify(X, Q_ser, s, msg, nonce_extra)
    print("ecdsa: OK\n")

• added ECDSA

Very nice!

Can you tell me, how many milliseconds it takes on average to create one of these signatures on a ColdCard MK4? @scgbckbone

We are discussing low bandwidth attacks, and have been wondering if any further mitigation is possible? The problem is, the time for a single sig is one thing, but a TX can and often does contain more inputs.

I do not have the data yet, but I assume this will have almost no visible impact as we have only changed noncefp (iirc one classic ECDSA signature is around 25ms on STM32). Default secp noncefp seem even heavier than what we have here.

I think we should first properly specify those nonce functions.

• I do not think my ZERO_MASK thing is safu.
• I added counter to ECDSA noncefp as we may get invalid k (small but non-zero chance):

q = H(x,m,n, counter)
Q = q·G
k = q + H(Q,m,n)

Right! A counter was a likely addition if we require a certain checksum on R. However generation of q is not routinely verifiable.

Edit: churning the outer k = q + H(Q,m,n,c) might be better. Especially if c is in a certain range prescribed by the companion app.

Edit: if you want to prove out a fix computation cost recursive hashing is needed, if you want R to conform to a harmless checksum, this is ok.

counter is not something provided by companion app, but rather way to grind correct k to be 0<k<order. it will be 99.9% 0, from time to time 1, and very very very limited number of times something different. I think that for c to be number greater than 255 is impossible(tho non-zero but we need 255 incorrect keys in a row). As this will "always" be 1 byte in theory, it should not mess with fixed length serialization .

if you want to prove out a fix computation cost recursive hashing is needed, if you want R to conform to a harmless checksum, this is ok

iiuc k = q + H(Q,m,n,c) this better ?

Yes, my point was the companion app can also grind it. If you expect R to conform to a checksum (to make low bandwith leaks more expensive computationally) then you can use this outside counter for that and the companion app can expect a certain range like if 1 sig takes 50 ms on the device, then if the target is ~2 sec then n bit checksum or R could be demanded to be all zero or some magic word.

Edit: I probably wouldn't use this, because PoW makes the signature generation time highly random. It was just something that came up in discussion.

What if we simply used k = q - H(Q,m,n) and R = Q - H(Q,m,n)·G (or whichever is a valid R point)?
@scgbckbone

what is that - ? is this ecdsa case where k is not valid key ?

Where R is not a valid point for the scheme. At least my understanding is, that can happen. Also with BIP-340, because you need an even R (0x02).

Where R is not a valid point for the scheme. At least my understanding is, that can happen. Also with BIP-340, because you need an even R (0x02).

as we use secp256k1_schnorrsig_sign_custom and only provide it with custom noncefp my understanding is that this is done for us in secp256k1_schnorrsig_sign_internal https://github.com/bitcoin-core/secp256k1/blob/1988855079fa8161521b86515e77965120fdc734/src/modules/schnorrsig/main_impl.h#L165-L180