[dlc-dev] CET collision attacks

[Lloyd Fournier]

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/20210331/9b28b847/attachment.htm>