Second round is unnecessary #37
Comments
|
How do you solve for Wagner k-sum attack without a second round? see #34 for details |
|
In the first round, each user includes a proof of knowledge of secret key (an ecdh sig is fine). This prevents rogue key attacks. But yes, as long as R̂ is a simple sum, it seems 2 signers using a birthday attack could discover a favorable R̂ - allowing those 2 signers to sign arbitrary messages. Seems like this paper proves that nearly all 2 round schemes are somewhat insecure https://eprint.iacr.org/2018/417.pdf. |
|
exactly |
|
I've been puzzling over this. Certainly a 2 round scheme is fine when there are only 2 signers. If you have, for example, a 2 of 4 threshold scheme (a useful and common configuration)... then 2 rounds are sufficient since k-sum is a non-issue. Hence a POKSK round is enough to ensure that a single attacker cannot rouge-key you. Finally, another solution to k-sums is to simply double the bit strength since the best k-sums can do is halve it, again... POKSK should be sufficient if the bits in R̂ is large. This could still be made bitwise compatible with bitcoin since the specification of the nonce doesn't impact the final signature and validation (hash of R can be used to get the bits into a shape bitcoin needs) So, 2 decent options that can reduce the number of rounds to 2 while solving for a k-sums attack on R. I suspect you can get it to 1 using pairings + the message itself as a secure multiparty offline nonce-generator. Sounds fun. |
|
I tend to agree with you that the two party case is a special case. IIRC we even implemented a 2 round 2 parties EdDSA (cc @oleiba ). About doubling the bit size : sounds interesting but I am not sure how this can be done in practice. Can you elaborate more on how such protocol will look like? Pairing would enable you to do 1 round but it will not be called Schnorr anymore |
|
|
Hi!
about 2 - I must admit I didn't understand. btw, have you looked into : https://crysp.uwaterloo.ca/software/frost/frost-techreport-20200120.pdf ? |
|
Hello, I'm the author of the stackexchange question. Erik Aronesty, thank you for the invite. I'm trying to find a solid response for the proposal, since I can't believe myself that such a simple solution exists. It's hard for me to find people to validate my work. So, I would appreciate your help in this matter and, it seems that it would also be useful for you. Furthermore, I have to say that this scheme is not entirely deterministic for the same message. If you select a different set of t + 1 nodes, the nonce would be different. |
|
I did read the frost paper, and I think shumy solves the problem more elegantly. it's intuitive to me that a simple random oracle solution to the nonce should exist, although I've tried and messed up a couple times in the past. |
|
FYI: We found that it was insecure on multiple levels. Didn't protect against k-sums, and had an issue with multiple signings of the same message. I'm back to pairings on the best way to sign stuff, where there's less of a possibility of "doing it wrong". |
|
Got it, thanks for the update. |
|
@earonesty "it was insecure on multiple levels" - Although I'm still trying to reach to a complete proof of security. With the exception that first attack (which is easily solvable with the seq parameter) none of the other proposed attacks work. The followup in Is this distributed random oracle scheme safe? doesn't present hard evidences that any of the attacks work. And, unless you want to give up on Schnorr's signatures, what you proposed about the oracle model should also be applicable to non threshold schemes. You may want to go with Pairings, but I'm still waiting for a good attack on the proposed scheme. |
|
All you have to do is wait for all the other signers to report their
shares. Then you and your attacker partner can ksums attack R. You don't
need to attack m0. You and your partner can sign one message now, knowing
R.
Another way to think of it is this. If your scheme is secure then any
random nonce is secure. Because the hash isn't any better than a random
number. And there is no ksums attack at all.
…On Fri, Mar 6, 2020, 5:39 AM shumy-tools ***@***.***> wrote:
@earonesty <https://github.com/earonesty> "it was insecure on multiple
levels" - Although I'm still trying to reach to a complete proof of
security. With the exception that first attack (which is easily solvable
with the seq parameter) none of the other proposed attacks work. The
followup in Is this distributed random oracle scheme safe?
<https://crypto.stackexchange.com/questions/77683/is-this-distributed-random-oracle-scheme-safe>
doesn't present hard evidences that any of the attacks work.
And, unless you want to give up on Schnorr's signatures, what you proposed
about the oracle model should also be applicable to non threshold schemes.
You may want to go with Pairings, but I'm still waiting for a good attack
on the proposed scheme.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#37>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAAMMUIBGXRZ6MGAUGZNICTRGDHEZANCNFSM4KQ5UBNQ>
.
|
|
@earonesty By R you meen m*G = R ? This is dicussed in the other topic. You can't sign a message without having m, and you can't have m without having m0. You need at least one honest share of y and m. You can k-sum R as you want, you can't revert it. And... "Aman Grewal" in that topic finally assumes this in his response "This shouldn't an issue for signatures". I state, there is no proof that k-sum works. |
|
The attacker can have m without being able to get m0, and that's enough.
…On Mon, Mar 9, 2020 at 5:54 AM shumy-tools ***@***.***> wrote:
@earonesty <https://github.com/earonesty> By R you meen m*G = R ? This is
dicussed in the other topic. You can't sign a message without having m, and
you can't have m without having m0. You need at least one honest share of y
and m. You can k-sum R as you want, you can't revert it. And... "Aman
Grewal" in that topic finally assumes this in his response "This shouldn't
an issue for signatures".
I state, there is no proof that k-sum works.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#37>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAAMMUNVZCTXJ7HBAOL6IP3RGS4E5ANCNFSM4KQ5UBNQ>
.
|
|
How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i. |
|
Not really good at math proofs. But, it's easy to see that you can
birthday-attack to control for a specific R. Which implies you
already have m.
…On Mon, Mar 9, 2020 at 11:15 AM shumy-tools ***@***.***> wrote:
How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or unsubscribe.
|
|
The idea is that two or more attackers are "lying" about their shares
of the public nonce. They aren't following your formula and hashing
the message. They are just controlling what R will be... because you
have know way of knowing whether they are hashing.
…On Mon, Mar 9, 2020 at 11:48 AM Erik Aronesty ***@***.***> wrote:
Not really good at math proofs. But, it's easy to see that you can
birthday-attack to control for a specific R. Which implies you
already have m.
On Mon, Mar 9, 2020 at 11:15 AM shumy-tools ***@***.***> wrote:
>
> How, can you give me a math proof on that? Because the math formulation that I have done doesn't allow to recover m without knowing m0. Even if k-sum on R you cannot get the respectives m_i.
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub, or unsubscribe.
|
|
"Which implies you already have m" - There is where you assumption fails. Having a public key does not imply to have the private key, or else every asymmetric encryption would be broken! You cannot produce a signature by just having R. Yes, you have a R that corresponds to an existing R* for other signature; however, deriving that via a k-sum of public keys won't be able to get you m_i or m, only a set of M_i values. Note that, past m_i values won't work because m0 is always different. In this sense, to get the corresponding m_i values to perform the signature you need to break the DLP. |
|
In a conclusion, controling the R value is a false assumption. It's pointless to control R if you cannot output a signature with it! Because, to output the signature require you to know m_i shares directly. |
|
Seems this answer here shows the issue better than I can: https://crypto.stackexchange.com/questions/77683/is-this-distributed-random-oracle-scheme-safe |
|
The answer already assumes that the k-sum is not a problem "This shouldn't an issue for signatures", due to exactly of what I explained. The second attack, is also not proved, refer to my comment in the response. The bounty is still open. |
|
A curiosity... if a bilinear pairing can perform a second degree verification, and if you can perform a threshold signature with BLS in one round; then (by intuition), you should be able to perform a 2 round signature without bilinear pairings! Although that intuition may be wrong, but that's what i'm trying to find out. |
If, in the first round each party uses a proof of knowledge of secret key, the second round where signers verify the commitment - which is necessary to prevent a rogue key attack - is not needed. In addition, there's no need to use each of the signer's public keys in the hash.
Instead a precomputed aggregate public key can be used for a given set of signers and a given threshold. Since proof of secret key was used during the establishment of this aggregate, it cannot be pre-selected, and is sufficient to use in the subsequent digest computations.
Finally, it is often desirable for signature schemes to be "malleable" (each message gets a unique sig), and others to be "fixed", (the signature corresponding to a given message is deterministic).
Such a library should allow for both scenarios.
The text was updated successfully, but these errors were encountered: