On the security of the nomcom process

| Comments (4) |
The IETF has a rather unusual method for selecting its leadership, at the heart of which is the Nominating Committee (nomcom), which selects the candidate lists. The nomcom is randomly selected from a list of eligible volunteers. The actual selection, is one of those algorithms that could only have been designed by nerds; a cryptographic public commitment and verifiable random choice scheme. It works as follows:
  1. People volunteer to serve.
  2. Their eligibility is checked.
  3. The filtered list is sorted in alphabetical order and published at time X. Say it has N members,
  4. A bunch of unpredictable data (stock prices) available only at time X + 7 days used as the seed of a cryptographic pseudorandom number generator.
  5. The output of that CPRNG is used to generate 10 unique numbers from 0 to N-1 (nerds, remember).
  6. The corresponding people on the list are the nomcom members.

So, from a cryptographer's perspective, the nice thing about this design is that it mostly can't be cheated.

  1. Because the list is published before the random numbers are known, there's no way to structure it in order to cheat.
  2. You can of course include fake members but if they're not selected they don't bias the result and if they are then they can be challenged. Similarly, you can remove people you don't like, but they can challenge the list in the week between publication and selection.
  3. Because the seed data is public anyone can verify the result.
  4. Everyone on the list has an even chance of being chosen.1

In other words, it's a classic cryptographic design in that it involves placing total trust in the math and no trust whatsoever in the people running the algorithm--and that's what went wrong this year.

The person who is responsible for running the algorithm is the nomcom chair, who is selected by the ISOC President. This year, the chair made two errors:

  1. He failed to remove at least one person who was ineligible from the list.
  2. He failed to publish the list ahead of time (step 3 above).

Error (1) wouldn't ordinarily be a big deal, because as I indicated in point (2) above it doesn't affect the outcome. But error (2) is a big deal because it means that the nomcom chair had an opportunity to bias the process. The easy way to do this looks like this:

  1. Collect a bunch of "fake" volunteers. These can be either fake names, or people who are ineligible, or who don't care if they're volunteered or not.
  2. Collect the random number output as described in step (5) above.
  3. Generate a bunch of different volunteer lists with different combinations of fake names.
  4. Each of these lists induces a bunch of different nomcom results.
  5. Select the nomcom you like best and publish the corresponding list as the list.
  6. Publish your chosen nomcom.

What stops this attack, of course, is that the list is published (a cryptographer would say "committed to") in advance. But because that wasn't done in this case, there's the possibility that the nomcom chair could have cheated. Now, as a practical matter nobody believes (at least everybody says they don't) that the nomcom chair did anything nefarious but because the whole process is predicated on the theory that he might cheat and is designed to make it impossible, having a situation where he had the opportunity puts us in an uncomfortable position.

The obvious thing to do, of course, is simple to run the process over, and that's indeed what's happened. The problem is that that isn't really adequate either because we've already seen the current nomcom and so if we really hate it, then a do-over would be nice even if we can't predict anything about the composition of the new nomcom other than that it's a random shuffle. So, given that we have one set of selections in hand, it's no longer possible for the process to be unbiased. And we can't really exclude the possibility that the chair cheated even though, as I said, nobody believes it.

As I indicated earlier (and as Phill Hallam-Baker just argued on the IETF list , a lot of the problem here is designing a system which is secure cryptographically but really intolerant of human error--and then expecting that system to give 100% assurance of fairness. All such systems involve a human element and you need to be prepared for what happens when the humans screw up and then be willing to live with less than 100% certainty.

1. This actually isn't entirely true because the CPRNG produces numbers in the range 1..2128 which doesn't quite evenly divide by N, so there's a tiny bias towards people with indices < 2128%N, but it's too tiny to be important.

4 Comments

It seems the process actually implemented this time can still be used to cheat.

Assume that there is an eligible volunteer whom the chair wants to be on or off the committee. The chair can intentionally make both of the mistakes in question (ineligible volunteer, unpublished list) or replace the failure to publish a list with any other semi-irregularity. Then the chair can follow this process:

  1. (A) If the ineligible (fake) volunteer was chosen (10/69 chance), the process will need to be reset, and the result will be fair.
  2. (B) If the results are satisfactory, and the volunteer in question is on or off as the chair wanted, use the fact that the single ineligible volunteer wasn't chosen to argue against a reset.
  3. (C) If the results are unsatisfactory (the unwanted volunteer was chosen or the wanted one wasn't) use the irregularity to argue for a reset.

In a fair, correctly run process, every eligible volunteer's chance of being chosen should be 10/68 = 14.7%.

But with the possibility of a do-over, but no rule absolutely requiring one, the probability of a member whom the chair wants actually making it onto the committee is (A: 10/69 fake chosen × 10/68 fair do-over) + (B: 59/69 not A × 10/68 chosen in first round) + (C: 59/69 not A × 58/68 not B × 10/68 chosen in second round) = 25.4%.

The probability of a member whom the chair doesn't want nonetheless getting on the committee is 1 − (A: 10/69 fake chosen × 58/68 fair do-over) − (B: 59/69 not A × 58/68 eliminated in first round) − (C: 59/69 not A × 10/68 not B × 58/68 eliminated in second round) = 3.98%!

Right. Anything that allows the chair to do a do-over at their discretion after seeing the list introduces the possibility of cheating.

If I read RFC 3797 correctly, it is stock volumes (in thousands of shares), rather than stock prices, that is used in step 4.

I published a followup to this on my blog elaborating on the proposal to fix it.

The best fix would be to do away with the NOMCON entirely and have direct elections. The point of NOMCON is to provide power without accountability.

Leave a comment