Topic: multisig using Curve25519 (Read 3591 times)

I must have made a mistake somewhere...


I noticed in polynomial form it can vary, but when compressed to 256 bit number it is always the same, so I display both the x and z vals.


  8e0539c79e4c30   8926b81faef662   811fdcd5840e1d   86c88ac5c0c565   829f821a0b73fa  spoly
604d9ec739059eb377fdc035898b036135f747ea8a818b1591ad40b7a021f829  s

2c7332292b79212c31ae926c6cf62ea339c80452761a7d3f53eced415368c430   sGx
2dfd7e0f309e76ec163b674dfffdf8b4b07156abbcc8d282456f1c7494838637 sGz

4d8a4ccda4b4c3959c7040478fe6ac3830aafc28d6432da97d4c834224888412   xsumx (eP + sG)
28768f66cef5f334af3746d27b427f52d5b91f1e1338b73af6e625b870f5d275 xsumz

908c0ac5a707594261b3df6fc64896033f61166afd6b98b7f0e32f615a514259   ysumx (eP + sG)
9422a680f5a74e05d561458d8ad25945ab64b5fc73aeb8b070e166a2eb34b93e ysumz

Not 100% sure that the (eP + sG) checks are even right, and maybe s or e are messed up. Without anyway to have known values part way, it seems it cant have any bugs through the entire process. Hopefully, I am at least close.

James

I use libtom:

    sha256_init(&md);
    sha256_process(&md,src,len);
    sha256_done(&md,hash);

so I think I just add a second     sha256_process(&md,src,len) before the sha256_done to concatenate.

    sha256_init(&md);
    sha256_process(&md,msg,msglen);
    sha256_process(&md,&R,256>>3);
    sha256_done(&md,hash);

James

Oops! || is concatenation -- you hash the message, then hash R with the same sha2 state. (The existing ed25519 code should do this somewhere..) (I say Oops because I thought to write this and evidently forgot..)

Using xor is not secure.

tricky! m for message

e = sha256(m || (αG + βG))

ok so m can just be sha256(msg) and the "||" presumably can be XOR, so:

e = sha256(sha256(msg) ^ (αG + βG))

then if the following three are just normal 256 bit arithmetic:
(α - xe)
(β - ye)
(s' + s'')

the only missing piece is how to calculate (αG - βG),  it seems it is just one point not two and in the code it was {9} for the keypair calculation, so if it is as simple as just using {9} then I can code up something that tests this

James

Hi James,

m is the message to be signed . The signature is the pair (r, s).

Andrew

Hi James,

It seems like are a few misunderstandings here. Let me start with some background. It is easier to explain what's going on if we abstract a bit: let's start by defining a group. A group is simply a set with an operation (called +), some set element 0 such that 0 + x = x + 0 = x for all x in the group, and a unary operation - such that x + (-x) = 0 for all x in the group. So, the integers with addition are a group (as are the reals, rationals, etc), the reals with multiplication are a group, the set of invertible nxn matrices are a group under matrix multiplication, etc.

An important group in cryptography is an elliptic curve group, which is a group whose elements are pairs (x, y) of numbers which satisfy an elliptic curve equation. Addition is defined in a bit of a funny way, but there is a Wikipedia page on it that is interesting.

What's important about these groups for cryptography is the following: given a group element G, you can "multiply" by an integer n by adding G to itself n times. (If n is negative, add -G to itself -n times.) It turns out that if you fix an element G in some group, then take all the elements {nG} for integers n, this set is itself a group such that (nG) + (mG) = (n + m)G. It's a true statement that given any nonzero elements in this group, say P and Q, there is always some number n such that P = nQ. But for elliptic curve group, there is the so-called "discrete logarithm assumption" which says that actually calculating n is very hard. There is also the "Diffie-Hellman" assumption which says that given nG, mG in the group, it is hard to calculate nmG. (Of course, if you know n or m, it's easy to calculate. This is why the "shared secret" scheme you described is efficiently computable by the participants, and the Diffie-Hellman assumption is why it is a secret.)

So...everywhere you say Curve25519(n, G), you really mean nG, where G is some element in the elliptic curve group defined by djb's curve25519 curve. Where you say Curve25519(A, B) where both A and B are elements .... I don't know what you mean. Can you clarify what you are actually computing here? It is possible you are interpreting curvepoints as numbers without realize it, in which case you should use a better programming language that has a type system. (In particular, C is has a very weak type system and djb's code uses char* for everything, which is an asinine thing to do in public code with subtle operation. But possibly it compiles to faster code than it would if he'd used wrapper structs..) It is possible to convert a group element to a number, e.g. by choosing a binary encoding, hashing this, and interpreting the hash as a number.

Now, shared secrets are not really useful for building multisignature schemes. They let you build 1-of-N signatures (every party who has the secret is able to sign) but nothing stronger. The reason is that any party who knows the shared secret is able to use this to sign arbitrary messages. As an example of an actual multisig scheme, I will show how to construct a N-of-N multisig Schnorr signature. The semantics will be that as long as all parties agree to sign a specific message, they are able to form a signature on that message. However, no individual will see enough secret material to form signatures or her own, or even with the cooperation of (fewer than N) other members.

djb's ed25519 signature scheme is based off the standard Schnorr signature, but has some changes to allow efficient batch validation. I don't recall what these changes are (and don't have the paper with me on the bus that I'm typing this from), so I'm not sure if this is directly applicable .... but it is illustrative in any case. So here it is:

Suppose we have a public key P, and let G be a generator of some elliptic curve group, and let H be a hash function. A standard Schnorr signature is a pair (s, e) of numbers which satisfy the following relation: if R = eP + sG then e = H(m || R). It is possible to create such a signature if you know x such that xG = P (so x is the secret key here, and the "discrete logarithm assumption" above is why it is secret even though P is public), by the following mechanism: choose random secret k and compute R = kG; then set e = H(m||R) and s = k - xe. The signature is (s, e). Given some very strong assumptions on the hash function (that it is a opaque mystical source of uniformly random numbers except that it returns the same output when given same input), we can prove that any algorithm which forges Schnorr signatures can be extended to extract the secret key. So given such a hash function, forging Schnorr signatures is as hard as the discrete log problem.

Now, the question is: how can we make a 2-of-2 signature? One idea, as you suggested, is to use a shared secret: users have secret values x and y and form a private key from (a hash of) xyG. The problem with this is as mentioned: both parties knows the whole secret, so they can both form signatures on their own. So this is really a 1-of-2 multisig scheme. To get 2-of-2, we need to be a bit more clever. Here is a protocol:
0. Suppose we have two keypairs (x, xG) and (y, yG) belonging to parties A and B. We will show how to construct a signature with the "2-of-2" key (x + y, (x + y)G).
1. Both parties choose secret random numbers. Call A's secret α and B's secret β. A sends αG to B, and B sends βG to A. Now both parties can compute R = αG + βG = (α + β)G, and they compute e = H(m||R).
2. A computes s' = α - xe and B computes s'' = β - ye, and they send these to each other. Then both compute s = s' + s''.

Now (s, e) is a signature of m on public key (x + y)G, which required both parties' cooperation to form, but neither party gained enough information to produce such a signature alone.


It's a worthwhile exercise to (a) verify that the standard Schnorr signature k - xe actually satisfies the relation (e = H(m||R) where R = sG + eP) that I claimed it did, and (b) so does the 2-of-2 version.


This isn't really an answer to your question, but I hope it sheds some light on things.

Andrew

First off I remind you I am just a simple C programmer and not a cryptographer. If anybody has the math background to confirm or deny my experimental finding, please post!

I was experimenting with Curve25519 yesterday and I observed a very useful property that allows the creation of multisig. https://forum.thesupernet.org/index.php?topic=154.msg1262#msg1262

Now I doubt it was just in the few cases that I discovered that works. I bruteforce searched thousands of combinations and found a very simple relationship that I believe can be used for arbitrary M of N signatures.

The fundamental property of Curve25519 is that if A and B know each others public key, they can create a shared secret. Let A and B be the private keys and a and b the public keys:

curve25519(A,b) == curve25519(B,a)

I searched and searched on the Internet to find little actual useful info, so I started with the above and my intuition and searched for combinations that created the same result and there were many, but the simplest and clearest was:

Add C and c to the above and denote S_ab to being the result of curve25519(A,b) or curve25519(B,a) (they are the same)

curve25519(A,S_bc) == curve25519(B,S_ac) == curve25519(C,S_ab)!

This relationship is quite useful and it is probably obvious to anybody familiar with curve25519 so maybe I am just getting excited over nothing, but the recommendation is to immediately hash the output S_ab. Presumably to avoid any low entropy sections of the point and once you do this, the above relationship does not work as you end up totally scrambling the location of the point in the finite field. I call this the rawsharedkey and maybe it has been explored in depth so we can get some math proofs of the above relationship.

We also know that curve25519(A,curve25519(B,curve25519(C,seed))) is equal to all the permutations of order, I think this is because the field forms an abelian group, but it has been a long time since I did any abstract algebra so I probably have the terms wrong. It is just a fancy way of saying the order doesnt matter.

So how to use these math properties to make multisig?

Since S_xy is constant for each set of keypairs for each node, these values can actually be cached locally. Of course this means that the presence of S_xy in the output does not mean that either X or Y actually signed anything. Turns out this is fine, as the final step requires the signing node to actively participate and the final output can be processed till the dogs come home:

sha256(seed ^ curve25519(A,S_bc))
sha256(seed ^ curve25519(B,S_ac))
sha256(seed ^ curve25519(C,S_ab))

all the above produce the identical result and proves that A, B and C all signed it with the seed (which should have a timestamp in it) and since it goes through sha256 the output gives no useful info about A, B or C. I am not sure if S_xy is leaking any info to the nodes that get access to it, but I dont think so as it is the output of curve25519 and that's supposed to be hard to reverse.

Since it is safe to publish the final number, A, B and C publish it and everybody can verify if 0, 1, 2 or 3 signers signed it. The enforcement of following the result is beyond the scope of this thread

Now, how can this be generalized? I feel strongly that the "triangle" relationship can be generalized, but so far my experimental results are not finding the right sequence.

Let me ramble a bit, that sometimes helps

Starting with the fundamental triangle:
curve25519(A,S_bc) == curve25519(B,S_ac) == curve25519(C,S_ab)

Let us replace C,c with D, d:
curve25519(A,S_bd) == curve25519(B,S_ad) == curve25519(D,S_ab)

The problem is these are different values as it is S_ab combined with C vs D, however, we can use the priv/pub equivalence:

curve25519(d,curve25519(C,S_ab)) ?? curve25519(c,curve25519(D,S_ab))

nope, that didnt work, but as expected:

curve25519(D,curve25519(C,S_ab)) == curve25519(C,curve25519(D,S_ab))
which means:

curve25519(D,curve25519(C,S_ab)) ==  curve25519(C,curve25519(D,S_ab))  == curve25519(B,curve25519(D,S_ac))  == curve25519(A,curve25519(D,S_bc))

Hey! That means there is a 4 signer solution, but this requires multiple signings and then correlations, so not exactly what I am looking for. Anyway I hope to get some math help here so an efficient M of N multisig using curve25519 is possible. Experimentally I found the triangle relationship, which I am not sure if it is trivially obvious or something significant.

James