[Eligibility-discuss] On 3797 alternatives

[Martin Thomson <[e-mail]>]

Paul's core idea here is neat, but I fear that his implementation has flaws.

Ekr's point about requirements is important.  We want an outcome that is hard to predict.  Our threat model allows an attacker to know the set of candidates and to manipulate it.  Therefore, in addition to being independently verifiable, any selection procedure needs to inject sufficient entropy.  We do this so that it is infeasible to alter the inputs in such a way as to alter the outcome toward an attacker's preferred choice, even with low probability[*].  This means the analysis in 3797 is flawed.  That concentrates on ensuring that the amount of entropy exceeds the number of permutations possible in the outcome, where what is needed is entropy sufficient to make an enumeration of possible outcomes impractical.

An example might help.  Let's say that an attacker's goal is to deny a certain person access to the NomCom, but only that one person will decide on their own to participate.  The attacker needs to start by adding at least 10 people to the slate.  But which set of people is up to them.  (Let's assume affiliation is no issue in this case and that the number of people the attacker can add is bounded.)  If the attacker can run a simulation for all possible - or even plausible -- values of D for each set of people they might consider adding, then they can find out which set of 10 (or more) people ensures that the person they singled out does not get selected with high probability.  Even with a large possible number of values for D, running something like Monte Carlo could increase the odds that the attacker gets the outcome they want.

Of note here is that if the input entropy is stocks, then there isn't a whole lot of entropy.  Low entropy values give the attacker an advantage.  Note that RFC 3797 claims that 40 bits is likely enough.  That's a tiny amount of entropy, making enumeration of outcomes close to attainable.

[*] Note that no outcome exists in this threat model where the attacker's advantage over a purely random process is zero, but we can ensure that it is negligible in a sense we're accustomed to, even if the attacker is willing to expend significant effort.

That's flaw 1 in Paul's draft: insufficient entropy.  Flaw 1b is that D is described as a number, but a byte sequence is better and what it really is anyway.

Flaw 2 is more academic.  This really needs a KDF.  H(D || name) is an approximation of that, but it is not a very good one.  It's a tiny bit more cryptography, but we can do better.  (Ideally, what you have is a KDF to extract entropy from D, then you can run a simpler expansion function.  Conveniently, RFC 5869 exists, is widely implemented, ...)

Flaw 3 is engineering.  The code in the draft is vastly more complex than necessary.  After defining a KDF, this should suffice:

import fileinput
for n in fileinput.input():
    print(f"{hex(kdf(d, n))} {n}")

Followed by a call to `sort`, of course, but you don't need to reimplement that.  That has a certain elegance, I think: `nomcom.py < candidates.txt | sort`

Finally, the controversial part.  I believe that a NomCom chair (whoever that might be) is able to choose any selection process, provided that it meets the stated requirements from Section 4.16 of RFC 8713: https://www.rfc-editor.org/rfc/rfc8713.html#section-4.16

The more controversial part is that - based on the above analysis - it seems like RFC 3797 does not meet the stated requirements in RFC 8713.

On Mon, May 29, 2023, at 20:03, Paul Hoffman wrote:
> My draft is only aimed at making #1 simpler and easier to understand 
> and having essentially the same security. If folks here like that idea, 
> all the parts of the ceremony from #2 can be wrapped around it.