6 ms·

Swiss evoting system – IsProbablePrime is incorrect for input 19

36 points by herr_gurke 4y ago

tromp 4y ago
> since 19 is a prime number, if I am not mistaken. That is one modest reviewer!
- OJFord 4y ago
  Well, it would be embarrassing to have a slow morning and get that wrong. Always build in a way out!
Someone 4y ago
Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf 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.
- mkl 4y 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_test https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_...
- threatripper 4y 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.
  - vmilner 4y ago
    It’s not easily testable if it’a pseudocode that hasn’t been implemented yet.
gsk22 4y 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.
- simonmales 4y ago
  As humans we do our best, and try to learn from our mistakes.
- mkl 4y ago
  It's not really easily testable, because the bug is in pseudocode which cannot be executed.
  - gsk22 4y ago
    I must be missing some context, then. It's unclear to me how pseudocode would be used in e-voting?
    - mkl 4y ago
      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.
- herr_gurke 4y 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.
  - hardware2win 4y ago
    Whats the problem with letting it run for a weeks on 5$ vps You better have your crypto _primitives_ rock solid
nairboon 4y 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.
- crisbal_ 4y ago
  > big company Isn't it the Swiss post?
- popcalc 4y ago
  https://www.evoting.ch/en https://www.evoting.ch/en Do the bare minimum research before posting please.
  - eps 4y ago
    That's exactly the company and the product. You could've scrolled a bit more: https://www.evoting.ch/en#transparenz https://www.evoting.ch/en#transparenz Voting in Switzerland is either in person or by mail.
    - popcalc 4y ago
      >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=evoting https://www.post.ch/en/business-solutions/e-voting?shortcut=...
      - Igrom 4y ago
        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 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-through-cooperation 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/ethical-hackers-can-now-target-the-e-voting-system 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.
amelius 4y ago
Perhaps the word "probable" has something to do with it?
raverbashing 4y 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
- mkl 4y 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/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...
  - vmilner 4y ago
    To be fair, there’s a reasonable chance this would have picked up in testing once the pseudocode was actually implemented.
  - raverbashing 4y 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)
omega3 4y 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?

36 points by herr_gurke 4y ago

tromp 4y ago

> since 19 is a prime number, if I am not mistaken. That is one modest reviewer!

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

Someone 4y ago

Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf 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.

mkl 4y 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_test https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_...
threatripper 4y 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.
- vmilner 4y ago
  It’s not easily testable if it’a pseudocode that hasn’t been implemented yet.

gsk22 4y 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.

simonmales 4y ago
As humans we do our best, and try to learn from our mistakes.
mkl 4y ago
It's not really easily testable, because the bug is in pseudocode which cannot be executed.
- gsk22 4y ago
  I must be missing some context, then. It's unclear to me how pseudocode would be used in e-voting?
  - mkl 4y ago
    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.
herr_gurke 4y 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.
- hardware2win 4y ago
  Whats the problem with letting it run for a weeks on 5$ vps You better have your crypto _primitives_ rock solid

nairboon 4y 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.

crisbal_ 4y ago
> big company Isn't it the Swiss post?
popcalc 4y ago
https://www.evoting.ch/en https://www.evoting.ch/en Do the bare minimum research before posting please.
- eps 4y ago
  That's exactly the company and the product. You could've scrolled a bit more: https://www.evoting.ch/en#transparenz https://www.evoting.ch/en#transparenz Voting in Switzerland is either in person or by mail.
  - popcalc 4y ago
    >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=evoting https://www.post.ch/en/business-solutions/e-voting?shortcut=...
    - Igrom 4y ago
      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 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-through-cooperation 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/ethical-hackers-can-now-target-the-e-voting-system 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.

amelius 4y ago

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

raverbashing 4y 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

mkl 4y 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/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...
- vmilner 4y ago
  To be fair, there’s a reasonable chance this would have picked up in testing once the pseudocode was actually implemented.
- raverbashing 4y 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)

omega3 4y 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?