Swiss evoting system – IsProbablePrime is incorrect for input 19(gitlab.com)

36 pointsby herr_gurke4 anni fa48 comments

Swiss evoting system – IsProbablePrime is incorrect for input 19

https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/issues/13

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.

mkl4 anni fa

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

threatripper4 anni fa

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.

vmilner4 anni fa

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

nairboon4 anni fa

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.

mthld4 anni fa

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

Igrom4 anni fa

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.

huhtenberg4 anni fa

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

nairboon4 anni fa

and you are living abroad?

popcalc4 anni fa

https://www.evoting.ch/en

Do the bare minimum research before posting please.

xupybd4 anni fa

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.

eps4 anni fa

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.

popcalc4 anni fa

>Swiss Post has been providing an e-voting system for the cantons since 2016. It has been developing its new system with complete verifiability at its IT site in Neuchâtel since 2020, providing an e-voting system from Switzerland.

https://www.post.ch/en/business-solutions/e-voting?shortcut=...

Igrom4 anni fa

Then next paragraph says:

>It plans to make the system available to the cantons for the trial operation once the development and evaluation of the system has been completed.

https://www.post.ch/en/business-solutions/e-voting

In addition, another page on the same website says:

>The cantons of Neuchâtel, Fribourg, Thurgau and Basel-Stadt used Swiss Post’s previous e-voting system until 2019. The following cantons (among others) are planning to use the new Swiss Post system once this becomes legally and technically possible: [list of cantons follows]

>https://www.post.ch/en/business-solutions/e-voting/success-t...

A Swiss Post press statement says:

>Since the beginning of 2021, Swiss Post’s future e-voting system has been put through its paces by independent experts from all over the world. Another testing opportunity is now available: in addition to the ongoing test options, ethical hackers can now attack the e-voting infrastructure for a period of four weeks. This means that, for the first time, they can accurately simulate and target the vote casting process on the voting portal using sample voting cards. The aim is to detect potential vulnerabilities and rectify them in good time. Swiss Post expects to make its new e-voting system available for use by interested cantons during the course of 2023.

https://www.post.ch/en/about-us/media/press-releases/2022/et...

I don't understand why you must be so haughty (vide "Do the bare minimum research before posting please."). Certainly, you are correct for some definition of "Switzerland has an e-voting system" --- there is one under development, and it had been piloted for a limited time period. However, at the moment, it's only in the public testing stage, it's not officially recognized, cannot be used to cast votes, and there is no guarantee that it will get a green light. I think that's the more accepted definition of "to have an e-voting system", in which case the OP was right, and it was you who did not do adequate research.

sampo4 anni fa

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

nairboon4 anni fa

Cantons may experiment with evoting in limited pilot schemes.

greyw4 anni fa

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

crisbal_4 anni fa

> big company

Isn't it the Swiss post?

benevol4 anni fa

> Switzerland doesn't have evoting.

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

tromp4 anni fa

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

That is one modest reviewer!

OJFord4 anni fa

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

raverbashing4 anni fa

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

mkl4 anni fa

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

raverbashing4 anni fa

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

vmilner4 anni fa

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

omega34 anni fa

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?

gsk224 anni fa

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.

sschueller4 anni fa

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.

dbrgn4 anni fa

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

hutzlibu4 anni fa

Hm, but it sounds quite solid(I only know, what is written in the links):

They made an open public intrusion test with a bug bounty and they released the sources. And so far no one could find a real weakness.

tarakat4 anni fa

How many nation-states burned their best zero-days on this public intrusion test?

hutzlibu4 anni fa

Likely none, but nation-states can also manipulate traditional voting with enough effort.

(classic spycraft, blackmailing of key persons, intercept mailvoting, etc.)

Nothing is 100% secure.

So the question is, is it good enough?

They said they took great effort to verificate the voting and detect manipulation. I cannot confirm or verify it, but since it is open, I could. That is a great step forward, compared to the closed black boxes, e-voting systems I have heard of before.

tarakat4 anni fa

Your examples are all less scalable and easier to detect that hacking.

> That is a great step forward, compared to the closed black boxes, e-voting systems I have heard of before.

It's still a black box. You have only their word to go that the published source is what is actually running on the machine in front of you in the voting booth. And they have only the word of their computers.

So yes, it's a great step forward, in the same way that going up a flight of stairs is a great step towards reaching orbit.

hutzlibu4 anni fa

"Your examples are all less scalable and easier to detect that hacking."

Less scalable likely yes, but easier to detect depends. How would I know, if my local vote regulator is a russian asset?

"You have only their word to go that the published source is what is actually running on the machine in front of you in the voting booth."

That can be changed. In a way, that I also can voluntarily help with the voting and vote count today, you could have community based people overwatching the technical deployment of the machines.

I am not saying, that what the swiss are doing is enough. But I like voting and I would like voting to happen more often. That would be way easier with digital secure solutions. We can transfer our money digital securly, so why not also our vote?

(well yes, anonymity of vote makes it harder, but not impossible)

More voting, more democracy.

dbrgn4 anni fa

Even if experts are convinced that the e-voting system is secure, it cannot be understood by laypeople. To a random person on the street, e-voting is absolutely intransparent, it's a magic black box that spits out a result. And as soon as distrust of the government comes up (no matter whether justified or not), e-voting can amplify the allegations of voting manipulation.

In contrast, paper and mail voting are things that are technically less secure than a well-designed e-voting system, but they can be understood by laypeople. In Switzerland, my vote goes into a ballot box, guarded by people from different parties. They are counted by citizens from different parties, with many people in the same room. Manipulation has happened in the past, but it has always happened in a constrained scope (e.g. people fishing voting ballots out of the mailboxes of their neighbors). And if it happens large-scale in a single town, this may be detected by statistical analysis ("the number of votes for a certain party is unusually high or low compared to other similar towns"). If citizens don't trust the count, they can request a re-count of the sealed voting ballots by other people.

Making voting simpler is a good thing. In Switzerland, we have had mail voting for a long time now. Yes, you still need to fill out a piece of paper and bring it to a post box, but the thing that takes the most time is actually informing yourself about the things/laws/referendums you're voting on, not filling out the paper. And the attack vector on mail voting is easy to understand.

The problem with e-voting is not security, it's trust. If we erode trust in our voting systems, we erode trust in our democracy. This has already started to happen in a few places, most notably in some areas in the US where e-voting systems are deployed, and where certain groups of people keep repeating their allegations of voter fraud. (They can claim this about regular voting as well, but it's easier to disprove than with closed e-voting systems that only very few "experts" can understand.)

hutzlibu4 anni fa

"In Switzerland, my vote goes into a ballot box, guarded by people from different parties. They are counted by citizens from different parties, with many people in the same room. "

I very much agree to your point, that laypersons need to be able to understand the system. At least the basic concept. No dark magic.

After all a vote is just encrypted information going to a server.

The details are more complex, sure, but there is a growing number of tech literate people.

So not all people might understand it all directly, but if their neigbhor does (and indeed also checks occasionally), then this might be enough.

dbrgn4 anni fa

A vote is not just "encrypted information going to a server". The law says that every voter must be able to vote once (and only once), and that the vote must be secret, towards other voters and towards the government. A vote must be authenticated, it must be ensured that it's only counted once, but the counting system may not know what you voted (at least as long as the vote is tied to your identity). This means that you cannot use classic encryption algorithms, because for tallying the votes, you must be able to sum up votes for which you're not allowed to know what the vote is. This requires "novel" schemes like homomorphic encryption, zero-knowledge proofs, etc. (Not novel in the academic sense, but in a practical sense, there is still quite little practical experience with this kind of cryptosystem, compared to TLS for example.)

I have yet to find someone that can explain me how homomorphic encryption works in a way that I fully understand. And I'm a software engineer. I understand RSA or Diffie Hellman. A lot of people understand RSA or Diffie Hellman. Almost nobody understands homomorphic encryption. This means that almost nobody even has the necessary base knowledge to even being able to review an e-voting system.

Without voting secrecy, I'd say that building a robust system would work reasonably well. With voting secrecy, it's a different story.

hutzlibu4 anni fa

"Without voting secrecy, I'd say that building a robust system would work reasonably well. With voting secrecy, it's a different story. "

Sadly this is true and I agree to that. I am also a fan of open voting, but I can see that general society is not ready for that.

And to your other points I mainly agree, but I am a bit more optimistic, than one can build a system of open trust, even though I have to admit, that I also do not understand the specific system, but I also did not really look into it.

gerdesj4 anni fa

"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)

hn_zorba4 anni fa

You might be a pedant but it actually helped me understand that message, I was really confused by the poles.

herr_gurke4 anni fa

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.

gsk224 anni fa

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

hardware2win4 anni fa

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

You better have your crypto _primitives_ rock solid

mkl4 anni fa

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

gsk224 anni fa

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

mkl4 anni fa

I think this is the specification for the software that would be used for e-voting. There is code in that repository too, and it calls a method named isProbablePrime, but I can't see a definition of it.

simonmales4 anni fa

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

amelius4 anni fa

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