Swiss evoting system – IsProbablePrime is incorrect for input 19
1–10 of 49 posts
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#2Relevant 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
I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#3Can 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.
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#4Can 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.
Im not sure if really the simplest test would catch it. You would need to go over n primes and check them, but you might always finish too early.
There is also a question of impact - i think that 19 does not really cause any harm there.
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#5Can 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.
As humans we do our best, and try to learn from our mistakes.
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#6Can 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.
Im not sure if really the simplest test would catch it. You would need to go over n primes and check them, but you might always finish too early. There is also a question of impact - i think that 19 does not really cause any harm there.
Whats the problem with letting it run for a weeks on 5$ vps
You better have your crypto _primitives_ rock solid
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#7Can 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.
It is brain dead but this is old code from what I recall. We do not have e-voting at this time although the Post which outsourced this first nightmare of a version is still trying to push for it.
I highly doubt we will see e-voting here until there is a verifiable proof that it is verifiable. There was a lot of bad press about this and people don't trust this crap.
They tried a similar thing for E-ID which was supposed to be built by some private cooperation and run on some centralized servers. The people voted against it and now the government has done the right thing and is building an E-ID system that is decentralized and government run. It still has some quirks but it's going in the right direction.
The sad thing is for the governments first version (outsource to private industry) their claim at the poles was that it would take many years for an E-ID if we don't do it this way. Now only 1 year later we have a very good proposal. There is too much corporate interest pushing around pawns in Government at this time even in a direct democracy like Switzerland.
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#8> since 19 is a prime number, if I am not mistaken.
That is one modest reviewer!
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#9Relevant 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 i…
Specifically a bug in that constant sp, which should have a 1 in bit 19 like it does for the other primes ≤ 23.
This is step 1 of the algorithm they're using: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_...
Re: Swiss evoting system – IsProbablePrime is incorrect for input 19
#10Can 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.
It's not really easily testable, because the bug is in pseudocode which cannot be executed.