Re: [Eligibility-discuss] On 3797 alternatives

[Martin Thomson <[e-mail]>]

On Sat, Jun 3, 2023, at 07:46, Donald Eastlake wrote:
> So, what is a reasonable estimate of the amount of bias that can be 
> introduced by the attack you hypothesize?

Let's take the simplest case.  There is just one person who volunteers, but the attacker intends to add one more.  The process therefore needs only to choose from two people.  There is one real candidate and a small set of people who might volunteer for the other position.

The seed contains 2 bits of entropy, which is then fed into MD5 and whatnot.  By the logic presented in 3797, this is ample entropy.  It's twice as much as you would seem to need.

There are four possible outcomes in this scenario.  Each outcome is either first chosen or second chosen. If the set of outcomes is all first chosen, then the attacker chooses a volunteer that will be sorted first; if the set of outcomes is all second chosen they do the opposite.  Probability of success in that case is 1, not some probability distribution.

If we model MD5 as an ideal PRF (which it isn't, but I'll hold my nose briefly), then maybe we conclude that the odds of this outcome only occurs one time in eight.  But then there is the 3/4 case, which occurs half the time, but provides a 3/4 odds of attacker success.  And at 2/2, the attacker's preferred outcome occurs half the time with 3/8 probability.  Multiply out and you get odds of influence at 0.75, which is an advantage of random of 0.25 over pure 50/50 chance.

Extending that model with more bits would seem to reduce that advantage quite a bit.

My point is that the 3797 analysis has a shortcoming in that it considers the PRF as a random oracle, when it isn't.  Consequently, the system is not as strong as it might seem.

Of course, I want to point out that this is all academic.  In practice, we use high entropy seeds and there is no real reason not to continue to do so.