Swiss evoting system – IsProbablePrime is incorrect for input 19 (opens in new tab)

(gitlab.com)

36 pointsherr_gurke3y ago48 comments

48 comments

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.

mkl3y ago

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_...

threatripper3y ago

Let me repeat if I understand it right:

* The function will return True for all primes.

* The function will return False if the number is detected as a composite by some tests.

* The function can return True or False for all other numbers.

* For numbers<=23 they implemented a shortcut using a lookup table which is implemented as bits in a number.

* The bit for number 19 is wrong. It returns false for a prime number which violates "return True for all prime numbers".

This is indeed quite shoddy programming for such an essential and easily testable piece of software.

vmilner3y ago

It’s not easily testable if it’a pseudocode that hasn’t been implemented yet.

nairboon3y ago

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.

mthld3y ago

Well, I'm swiss and evoting at least twice a year... https://www.eda.admin.ch/eda/en/fdfa/living-abroad/schweizer...

Igrom3y ago

I can't really dispute it if that's what you claim that you're doing, but how can that be? Article 2.3 from the file "Political rights of the Swiss abroad", which is available under your link, asserts:

>2.3 E-voting

>The option to vote online in federal votes and elections has been on hold since mid-2019.

>Adjustments are to be made to the pilot scheme by the end of 2020. The aim is to establish a stable scheme, using the latest technology, and create an accurate and transparent end-to-end voting system that also preserves the secrecy of the ballot. Efforts are also being made to raise levels of public confidence in e-voting by extending independent monitoring, ensuring greater transparency with regard to e-voting systems and how they operate, and involving the scientific community more effectively. The necessary conditions for resuming the e-voting trials will be redefined by 2020.

Is the government information out of date? If so, this should be reported.

huhtenberg3y ago

That's not the same system and it's just for the people living outside of the country.

nairboon3y ago

and you are living abroad?

popcalc3y ago

https://www.evoting.ch/en

Do the bare minimum research before posting please.

xupybd3y ago

There is also a bare minimum of manners for polite conversation. I for one prefer when people act politely here. HN is one of the few places online that's normally civil in the comments section.

eps3y ago

That's exactly the company and the product. You could've scrolled a bit more:

https://www.evoting.ch/en#transparenz

Voting in Switzerland is either in person or by mail.

1 more reply

sampo3y ago

> Switzerland doesn't have evoting.

Looks like they had it in varying number of areas from 2003 to 2019. Then all systems were withdrawn due to security concerns.

https://en.wikipedia.org/wiki/Electronic_voting_in_Switzerla...

https://www.ch.ch/en/votes-and-elections/e-voting/#revision-...

nairboon3y ago

Cantons may experiment with evoting in limited pilot schemes.

greyw3y ago

It's a state owned company so it is kinda selling to itself.

crisbal_3y ago

> big company

Isn't it the Swiss post?

benevol3y ago

> Switzerland doesn't have evoting.

And given what they show off, they should abstain from it for the next 1000 years.

tromp3y ago

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

That is one modest reviewer!

OJFord3y ago

Well, it would be embarrassing to have a slow morning and get that wrong. Always build in a way out!

raverbashing3y ago

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

mkl3y ago

I think you're misunderstanding the constant: it is only used for small numbers (≤ 23), which are tested with a lookup table, and the constant is itself that lookup table. The test for small numbers is literally just checking a bit, so is not heavy at all.

They intended to do 2^2+2^3+2^5+2^7+2^11+2^13+2^17+2^19+2^23 = 9054380, but they accidentally left out 2^19, and got 2^2+2^3+2^5+2^7+2^11+2^13+2^17+2^23 = 8530092.

You can see the problematic Algorithm 4.16 on p31 here: https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...

raverbashing3y ago

Thanks for explaining it, now it makes sense (and I guess it makes sense to implement the "lookup table" like this in this case)

vmilner3y ago

To be fair, there’s a reasonable chance this would have picked up in testing once the pseudocode was actually implemented.

omega33y ago

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?

gsk223y ago

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.

sschueller3y ago

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.

dbrgn3y ago

Well, unfortunately they do plan to relaunch their e-voting system next year, after having "tested their system against more than 60'000 attacks from hackers" (whatever that is supposed to mean)...

https://www.srf.ch/news/schweiz/elektronische-stimmabgabe-ha...

https://www.heise.de/news/Schweizer-Post-Hacker-konnten-E-Vo...

1 more reply

gerdesj3y ago

"their claim at the poles was"

Sorry for being a bit of a pedant but: A pole is a simple structure (eg flag pole), a Pole is a person from Poland and a poll is what you meant 8)

1 more reply

herr_gurkeOP3y ago

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.

gsk223y ago

> You would need to go over n primes and check them, but you might always finish too early.

I mean sure, but it's pretty simple to at least enumerate the primes < 100 and test those...

hardware2win3y ago

Whats the problem with letting it run for a weeks on 5$ vps

You better have your crypto _primitives_ rock solid

mkl3y ago

It's not really easily testable, because the bug is in pseudocode which cannot be executed.

gsk223y ago

I must be missing some context, then. It's unclear to me how pseudocode would be used in e-voting?

1 more reply

simonmales3y ago

As humans we do our best, and try to learn from our mistakes.

amelius3y ago

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

j / k navigate · click thread line to collapse

48 comments

Someone3y ago

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.

mkl3y ago

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_...

threatripper3y ago

Let me repeat if I understand it right:

* The function will return True for all primes.

* The function will return False if the number is detected as a composite by some tests.

* The function can return True or False for all other numbers.

* For numbers<=23 they implemented a shortcut using a lookup table which is implemented as bits in a number.

* The bit for number 19 is wrong. It returns false for a prime number which violates "return True for all prime numbers".

This is indeed quite shoddy programming for such an essential and easily testable piece of software.

vmilner3y ago

It’s not easily testable if it’a pseudocode that hasn’t been implemented yet.

nairboon3y ago

mthld3y ago

Well, I'm swiss and evoting at least twice a year... https://www.eda.admin.ch/eda/en/fdfa/living-abroad/schweizer...

Igrom3y ago

>2.3 E-voting

>The option to vote online in federal votes and elections has been on hold since mid-2019.

Is the government information out of date? If so, this should be reported.

huhtenberg3y ago

That's not the same system and it's just for the people living outside of the country.

nairboon3y ago

and you are living abroad?

popcalc3y ago

https://www.evoting.ch/en

Do the bare minimum research before posting please.

xupybd3y ago

There is also a bare minimum of manners for polite conversation. I for one prefer when people act politely here. HN is one of the few places online that's normally civil in the comments section.

eps3y ago

That's exactly the company and the product. You could've scrolled a bit more:

https://www.evoting.ch/en#transparenz

Voting in Switzerland is either in person or by mail.

1 more reply

sampo3y ago

> Switzerland doesn't have evoting.

Looks like they had it in varying number of areas from 2003 to 2019. Then all systems were withdrawn due to security concerns.

https://en.wikipedia.org/wiki/Electronic_voting_in_Switzerla...

https://www.ch.ch/en/votes-and-elections/e-voting/#revision-...

nairboon3y ago

Cantons may experiment with evoting in limited pilot schemes.

greyw3y ago

It's a state owned company so it is kinda selling to itself.

crisbal_3y ago

> big company

Isn't it the Swiss post?

benevol3y ago

> Switzerland doesn't have evoting.

And given what they show off, they should abstain from it for the next 1000 years.

tromp3y ago

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

That is one modest reviewer!

OJFord3y ago

Well, it would be embarrassing to have a slow morning and get that wrong. Always build in a way out!

raverbashing3y ago

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

mkl3y ago

They intended to do 2^2+2^3+2^5+2^7+2^11+2^13+2^17+2^19+2^23 = 9054380, but they accidentally left out 2^19, and got 2^2+2^3+2^5+2^7+2^11+2^13+2^17+2^23 = 8530092.

You can see the problematic Algorithm 4.16 on p31 here: https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...

raverbashing3y ago

Thanks for explaining it, now it makes sense (and I guess it makes sense to implement the "lookup table" like this in this case)

vmilner3y ago

To be fair, there’s a reasonable chance this would have picked up in testing once the pseudocode was actually implemented.

omega33y ago

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?

gsk223y ago

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.

sschueller3y ago

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.

dbrgn3y ago

Well, unfortunately they do plan to relaunch their e-voting system next year, after having "tested their system against more than 60'000 attacks from hackers" (whatever that is supposed to mean)...

https://www.srf.ch/news/schweiz/elektronische-stimmabgabe-ha...

https://www.heise.de/news/Schweizer-Post-Hacker-konnten-E-Vo...

1 more reply

gerdesj3y ago

"their claim at the poles was"

Sorry for being a bit of a pedant but: A pole is a simple structure (eg flag pole), a Pole is a person from Poland and a poll is what you meant 8)

1 more reply

herr_gurkeOP3y ago

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.

gsk223y ago

> You would need to go over n primes and check them, but you might always finish too early.

I mean sure, but it's pretty simple to at least enumerate the primes < 100 and test those...

hardware2win3y ago

Whats the problem with letting it run for a weeks on 5$ vps

You better have your crypto _primitives_ rock solid

mkl3y ago

It's not really easily testable, because the bug is in pseudocode which cannot be executed.

gsk223y ago

I must be missing some context, then. It's unclear to me how pseudocode would be used in e-voting?

1 more reply

simonmales3y ago

As humans we do our best, and try to learn from our mistakes.

amelius3y ago

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

j / k navigate · click thread line to collapse