[dlc-dev] CET collision attacks
Lloyd Fournier
lloyd.fourn at gmail.com
Tue Apr 13 03:21:08 CEST 2021
On Mon, 12 Apr 2021 at 17:41, Thibaut Le Guilly <thibaut at cryptogarage.co.jp>
wrote:
> Hi Lloyd,
>
> Regarding 2., I find the ability to keep Schnorr style attestations
> appealing, however am I correct in thinking that this scheme would prevent
> any kind of optimization as it requires computing a different hash for each
> different aggregation? This would be quite unfortunate I think (to say the
> least).
>
Actually it's worse than that it makes you do m multiplications for m
nonces for each CET! I just threw that idea out there because it's
interesting to me. It demonstrates the link between the security of Schnorr
"half-aggregation" and multi-nonce CET points. I think there is no way for
us to create a secure multi-oracle multi-nonce support without in effect
creating a secure Schnorr half-aggregation scheme (and vise-versa). Using
their scheme to produce CET points would be extremely inefficient. But it
shows what we have to do to make it secure if changing the oracle structure
is out of the question -- and it doesn't look good!
> Regarding 1., first the twitter thread was really interesting to read.
> Also would it be fine to do H(X || R || m) * r + x instead (just reversing
> the X and R in the hash)? The reason I ask is because then the code change
> would be minimal as one could just call regular Schnorr passing the nonce
> in place of the secret key and vice versa (unless I missed something
> maybe?).
>
The hash ordering doesn't matter so that would work in theory. In the
random oracle model it might also mean you don't need to do a proof of
knowledge for each R as well (not sure yet).
Another important discovery I made is that this also fixes the no_hash
scheme if you map the first outcome to 1 and so forth. Taking the original
example of CETs for two nonces R_0 and R_1 it becomes:
0: 1*R_0 + 1*R_1 + 2*X
1: 2*R_0 + 1*R_1 + 2*X
2: 1*R_0 + 2*R_1 + 2*X
3: 2*R_0 + 2*R_1 + 2*X
Each of these are linearly independent and so can't have a collision (a
collision would mean you have discovered a discrete log of one nonce to the
other).
Another benefit of multiplying by R seems to be that you *would* have an
equivocation punishment even with multiple-oracles. So if a set of oracles
all publically attest to one thing but then you extract a CET secret that
contradicts some or all of the public attestations you would be able to
extract the secret keys for all oracles that equivocated!
Taking the example of two oracles (X_0 and X_1) with nonces (R_0 and R_1)
with public attestations s_0 = c_0 * r_0 + x_0 and s_1 = c_1 + r_1 + x_1.
Now if you extract s' from a fraudulent CET your counterparty broadcasts
then you have s' = c_0' * r_0 + x_0 + c_1' * r_1 + x_1. If both c_0' != c_
0 and c_1' != c_1 you have three linearly independent equations and three
unknowns so you can solve everyone's keys. Note if only one of the the c's
are different you can then solve only for that equivocating oracle. I think
that's pretty neat even though I'm not a big fan of the equivocation
penalty.
A caveat is that all cheating oracles have to publicly attest to something.
If one of them cheats privately (contributes to s') and then disappears you
don't have enough equations to solve I think. You would only get the fraud
proof of the oracle never attesting to something they announced.
I would hold off on and wait for this line of research to develop before
doing anything about it though :)
LL
> Thanks for your continued work on this, really quite interesting to follow.
>
> Cheers,
>
> Thibaut
>
> On Mon, Apr 12, 2021 at 9:07 AM Lloyd Fournier <lloyd.fourn at gmail.com>
> wrote:
>
>> Hi All,
>>
>> At the last DLC specs meeting I basically said that the analysis here is
>> not really asking the right questions and the best thing to do now is to go
>> back to how things were. I still agree with this statement but there are a
>> couple of things I figured out recently that I wanted to share with you:
>>
>> 1. H(R || X || m) * r + x is actually a secure variant of Schnorr and I
>> believe it solves the collision problem[1]. Notice how if you add two of
>> these together for the same oracle you get H(R1 || X || m1) * r1 + H(R2 ||
>> X || m2) * r2 + 2*x. Where are with normal Schnorr you get r1 + r2 (H(R1 ||
>> X || m1) + H(R2 || X || m2)) * x. The problem is the addition between the
>> hashes allows you to solve the k-sum problem to find a collision in the
>> additions. This attack doesn't apply if you multiply by the r's
>> 2. This recent paper[2] demonstrates how to safely "add" the s values of
>> Schnorr signatures together and comes with relatively straightforward
>> proofs of security. The idea is actually applicable to DLCs too I think. So
>> without changing the oracle from creating Schnorr-style attestations you
>> can just get users to do a more sophisticated combination to get a secure
>> aggregate s that cannot have collisions. This is attractive since it works
>> regardless of whether the s values are from the same oracle or different.
>> This also means fraud proofs validated with this method cannot be
>> constructed by finding collisions.
>>
>> [1] https://twitter.com/LLFOURN/status/1380313536086208512 ://twhttps
>> itter.com/LLFOURN/status/1380313536086208512?s=20
>> [2] https://eprint.iacr.org/2021/350.pdf
>>
>> Cheers,
>>
>> LL
>>
>> On Wed, 31 Mar 2021 at 14:06, Lloyd Fournier <lloyd.fourn at gmail.com>
>> wrote:
>>
>>> Hi Tibo,
>>>
>>> On Tue, 30 Mar 2021 at 17:49, Thibaut Le Guilly <
>>> thibaut at cryptogarage.co.jp> wrote:
>>>
>>>> Hi Lloyd,
>>>>
>>>> Thanks for this analysis. I'm trying to properly understand it, but I'm
>>>> a bit stuck and was hoping you could help me clarify things.
>>>>
>>>> > On average how many nonces and outcomes per nonce do we need before
>>>> there is a collision?
>>>> > Each term like H(R_0 || X || o_a0) - H(R_0 || X || o_b0) can take on
>>>> m * (m - 1) possible values where m is the number of possible outcomes.
>>>> > For n nonces we have (m^2 - m) ^ n possible CET encryption keys.
>>>> Let's say we have m = 2^10 = 1024 outcomes per nonce this means to get at
>>>> least 2^256 possible CETs we need roughly n = 13 nonces to be involved on
>>>> average to have a collision.
>>>>
>>>> I don’t understand why you relate the number of possible “CET
>>>> encryption keys” with the subtraction above. It seems to me that the number
>>>> of CET encryption keys would be m^n if you have m outcome per nonces and n
>>>> nonces.
>>>> Also your problem statement says “on average”, but if you reach 2^256
>>>> CET encryption keys, it seems to me that the probability of having a
>>>> collision reaches 1 (from the pigeonhole principle). So I’m not sure what
>>>> you meant by average.
>>>>
>>>
>>>
>>> Yes I confused myself even. Sorry. This is not the number of CET
>>> encryption keys. This is the number of candidate solutions to the collision
>>> equation. The average number of samples before picking one that satisfies
>>> it will be 2^256. n = 13, m = 1024 = 2^10 gives you ~2^256 possible
>>> solutions but gives you 2^130 CET encryption keys. Given the CET encryption
>>> key space is 2^256 you would expect roughly sqrt(2^256) = 2^128 required to
>>> have a collision (due to birthday principle) if each key CET key was just
>>> sampled uniformly. This is not a coincidence -- by the way I modelled the
>>> problem the result was bound to be related to the birthday principle
>>> because I assumed that each outcome combination was a uniform sampling of a
>>> number 0..~2^256 (in practice the curve order). Is this the correct way of
>>> modelling the problem? I am not sure but I *think* it's close enough.
>>>
>>> The interesting thing is that even though the number of CET encryption
>>> keys you have for a nonce combination is the same for H(R || X || o) and
>>> H(R || X) * o the latter has a much lower collision incidence in this model.
>>> The claim I have above is that for m = 2^10 you'd need n = 24 to produce
>>> ~2^240 different combinations on average before having a collision (as
>>> opposed to 2^128).
>>> How can this be so much higher? The structure just seems to mean the
>>> birthday principle doesn't apply. The distribution of ( H(R || X || 1), H(R
>>> || X || 2) ) is random but the distribution of (H(R || X)*1, H(R || X)*2)
>>> is not (in the random oracle model).
>>> It's very possible that I am wrong here (I would love to know why). I am
>>> still pretty weak at this kind of probability analysis. Perhaps doing a
>>> monte carlo simulation would be a way to check this without actually having
>>> to do math.
>>>
>>> Cheers,
>>>
>>> LL
>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210413/127a61d8/attachment.htm>
More information about the dlc-dev
mailing list