1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
Return-Path: <jonasdnick@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id B2CFBC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Oct 2022 15:34:29 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id 78F0540227
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Oct 2022 15:34:29 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 78F0540227
Authentication-Results: smtp4.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20210112 header.b=Azk+YwQV
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id U50WToGeB0aX
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Oct 2022 15:34:28 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 7637740223
Received: from mail-qv1-xf31.google.com (mail-qv1-xf31.google.com
[IPv6:2607:f8b0:4864:20::f31])
by smtp4.osuosl.org (Postfix) with ESMTPS id 7637740223
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Oct 2022 15:34:28 +0000 (UTC)
Received: by mail-qv1-xf31.google.com with SMTP id g9so9146157qvo.12
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Oct 2022 08:34:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=content-transfer-encoding:in-reply-to:content-language:references
:to:subject:user-agent:mime-version:date:message-id:from:from:to:cc
:subject:date:message-id:reply-to;
bh=6bRSM4LjkTVkF4XHYbhiKafFK6vqMtJ2Lx0N/dgfhtI=;
b=Azk+YwQVPespXEXhf03ZbltSvdaRvOL7OPCD+QsPkLg1jpHmclNOZxIr1v1CB6of86
EcSGJTlY4DC0xDP39bLBHf7iUoQ6zd4btmu706lpeZdyXQ9+wG+HxA7Redu6RGXHUfVm
4GFOUQ5lbQpzQv0xk7sxLmNiZvZUvfVuuyoklnuwKeQTj7zFIiFebvsRiUrlcb/nPlYg
ygkB1/FEwJ4pbgqtArLV5qxOecNfhZdNJdNVD0z1cOM6BVCwpy8Qew+R5s27rTbMu10F
bnmwqgyfrmgBxnaISMqGGfbj69TCqr1fEw/F3mhAmKn2TCAYslLYch/poN21/hRm+wkO
sikw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=content-transfer-encoding:in-reply-to:content-language:references
:to:subject:user-agent:mime-version:date:message-id:from
:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
bh=6bRSM4LjkTVkF4XHYbhiKafFK6vqMtJ2Lx0N/dgfhtI=;
b=Nf5E1ksDBATsK8SjRECrBbsodssqRwSRRFH/c3FdnIJaZnkyh3Yd6WfJ5cIOUy4+h5
ax/PPV1Lz1T7C2ZS4ljf7wOZiSuYx8HRCUJbDmUEV2pXk++D5DRMW+654127MwvY14Et
T+w2xTf0AiGwxFsl84R3Bh2jbhUL9lg3T92MWlUheAkXTFPxqpInBrl9jhB1zsOB9D67
WKJmdFGIO8ZYaXIGhBcbke4zA1fSAocX7PX1Qp750IE6P8xWmSmFr5Z6Xxo1psGW9zeT
1P0eh6usAUVsnInbVKg+ogqvzrCSftqe5+TDa7cRXtpSXPoG/jFhnglMt5b1stBnY53e
PpCQ==
X-Gm-Message-State: ACrzQf20FYtInXotnlvRDadHyUNUGp+cBIHLt0OWy6VbyWJJ2pkfE5Hz
mM9W9DvwyYMDelFk4tPE7f1dO1ZFcJSK9T+S
X-Google-Smtp-Source: AMsMyM5xB0d39iNq1TAsvYcJzTXodY08vgfD4YtSHlsCsnwYyZKtIwx3cRoCZ6bF/VMlzRW7QonDGQ==
X-Received: by 2002:ad4:5aee:0:b0:4b4:595:fb54 with SMTP id
c14-20020ad45aee000000b004b40595fb54mr8719290qvh.5.1665502467245;
Tue, 11 Oct 2022 08:34:27 -0700 (PDT)
Received: from ?IPV6:2607:fb90:d75b:d6e6:6e3c:4f33:e65e:f1f?
([2607:fb90:d75b:d6e6:6e3c:4f33:e65e:f1f])
by smtp.googlemail.com with ESMTPSA id
t24-20020a37ea18000000b006e42a8e9f9bsm13128454qkj.121.2022.10.11.08.34.25
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Tue, 11 Oct 2022 08:34:26 -0700 (PDT)
From: Jonas Nick <jonasdnick@gmail.com>
X-Google-Original-From: Jonas Nick <jonasd.nick@gmail.com>
Message-ID: <576db60c-b05b-5b9a-75e5-9610f3e04eda@gmail.com>
Date: Tue, 11 Oct 2022 15:34:23 +0000
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
Thunderbird/102.3.1
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
References: <46175970-d2ab-a58e-7010-f29820849604@gmail.com>
<6d823ec7-fe88-9311-09e8-be22ca8bfd89@gmail.com>
Content-Language: en-US
In-Reply-To: <6d823ec7-fe88-9311-09e8-be22ca8bfd89@gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Mailman-Approved-At: Tue, 11 Oct 2022 19:47:29 +0000
Subject: Re: [bitcoin-dev] MuSig2 BIP
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 11 Oct 2022 15:34:29 -0000
It is still true that cryptography is hard, unfortunately. Yannick Seurin, Tim
Ruffing, Elliott Jin, and I discovered an attack against the latest version of
BIP MuSig2 in the case that a signer's individual key A = a*G is tweaked before
giving it as input to key aggregation.
In more detail, a signer may be vulnerable if _all_ of the following conditions
are true:
1. The signer supports signing with a tweaked individual key (as provided to
key aggregation) and the tweak is known to the attacker (e.g., as in BIP 32
unhardened derivation).
2. The signer's public key appears at least two times with different tweaks in
the set of public keys that are aggregated. This would, for example, be the
case if a signer with public key A=a*G creates partial signatures for an
aggregate key corresponding to public key set {A, A+t*G} where t is some
tweak. Note that an attacker could make this condition true by using the key
B = A+t*G after having seen A.
3. The signer uses "concurrent signing", i.e., the signer stores secnonces for
multiple signing sessions.
4. The secret key provided to the Sign algorithm is not yet fully determined when the
NonceGen algorithm is called. This would, for example, be the case if the
attacker, after having seen the nonce of the signer, can influence whether a
or a+t will be provided as a secret key to Sign.
In this scenario, an attacker may forge a signature for any message and any
aggregate public key that contains the signer's individual public key A (with
any attacker-chosen tweak). In particular, the attacker may forge a signature
for any message and the public key A itself.
Condition 4 should only apply in relatively rare cases unless the signer is
tricked into such a situation.
Fix:
Note that if the optional secret key argument is provided to the NonceGen
algorithm and matches the secret key provided to the Sign algorithm, then
Condition 4 will not hold. Thus, one definite fix is to make the secret key
argument to the NonceGen algorithm mandatory. We are investigating other options
and will follow up shortly with a concrete fix of the BIP draft.
This discovery does not invalidate the security proof of the scheme as presented
in the MuSig2 paper because the security model in the paper does not support
tweaking a signer's key.
If you've implemented the BIP draft in your library or are already using it in
production don't hesitate to reach out to clarify the implications of this
discovery.
Tim Ruffing, Elliott Jin, Jonas Nick
|
