[dlc-dev] CET collision attacks

[Lloyd Fournier]

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/35d4a1a8/attachment.htm>