from Hacker News

Swiss evoting system – IsProbablePrime is incorrect for input 19

by herr_gurke on 10/14/22, 6:33 AM with 48 comments

• by Someone on 10/14/22, 7:02 AM

  Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...):

    𝑠𝑝 ← 8530092
       ▷ I.e. 0b100000100010100010101100: for all primes 𝑝 ≤ 23,
         TestBit(𝑠𝑝, 𝑝) = true
    if 𝑛 ≤ 23 then
      ▷ Quick check for small values, simpler and faster
        than testing equality on each option
      return TestBit(𝑠𝑝, 𝑛)
    end if
    if ¬TestBit(𝑛, 0) then return ⊥
      ▷ I.e. 𝑛 is even and, as per line 2, 𝑛 > 2 thus composite
    end if
  

  And it indeed is a bug. The function guarantees to return false “if the number can be determined to be composite” and true for all primes, so it should err in only one way.

  I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.

• by nairboon on 10/14/22, 8:04 AM

  For context: Switzerland doesn't have evoting. This is just some big company trying to re-sell a evoting system to the government. It has been in the news a few times, due to software and cryptographic quality issues.

• by tromp on 10/14/22, 7:55 AM

  > since 19 is a prime number, if I am not mistaken.

  That is one modest reviewer!

• by raverbashing on 10/14/22, 8:19 AM

  I would be very weary of changing such constants as this

  19 should have been tested by a lookup table, there's no need to apply such heavy test to it

  However, by changing that constant (if not properly verified) I'd worry it might change the primality test for some classes of numbers. Where this might be later manipulated to produce a weak key

• by omega3 on 10/14/22, 10:27 AM

  Could someone explain why they've used a constant sp instead of hardcoding the primes? How was it created, did someone manually hardcoded the bits then converted into a number?

• by gsk22 on 10/14/22, 7:44 AM

  Can someone explain how such a simple and easily-testable bug existed in a seemingly-important system like this?

  I don't know much about Swiss e-voting, but seems even the most brain-dead unit test of the IsProbablePrime function should have caught this.

• by amelius on 10/14/22, 8:16 AM

  Perhaps the word "probable" has something to do with it?