[dlc-dev] CET collision attacks
Thibaut Le Guilly
thibaut at cryptogarage.co.jp
Mon Apr 12 09:41:36 CEST 2021
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).
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?).
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/20210412/538462ad/attachment.htm>
More information about the dlc-dev
mailing list