Replay attacks are among the most well-known attacks against vote privacy. Many e-voting systems have been proven vulnerable to replay attacks, including systems like Helios that are used in real practical elections.
Despite their popularity, it is commonly believed that replay attacks are inefficient but the actual threat that they pose to vote privacy has never been studied formally. Therefore, in this paper, we precisely analyze for the first time how efficient replay attacks really are.
We study this question from commonly used and complementary perspectives on vote privacy, showing as an independent contribution that a simple extension of a popular game-based privacy definition corresponds to a strong entropy-based notion.
Our results demonstrate that replay attacks can be devastating for a voter’s privacy even when an adversary’s resources are very limited. We illustrate our formal findings by applying them to a number of real-world elections, showing that a modest number of replays can result in significant privacy loss. Overall, our work reveals that, contrary to a common belief, replay attacks can be very efficient and must therefore be considered a serious threat.
B.Adida, Helios: Web-based open-audit voting, in: Proceedings of the 17th USENIX Security Symposium, San Jose, CA, USA, July 28–August 1, 2008, P.C.van Oorschot, ed., USENIX Association, 2008, pp. 335–348.
2.
M.S.Alvim, K.Chatzikokolakis, C.Palamidessi and G.Smith, Measuring information leakage using generalized gain functions, in: Proceedings of the 2012 IEEE 25th Computer Security Foundations Symposium, CSF’12, IEEE Computer Society, USA, 2012, pp. 265–279. doi:10.1109/CSF.2012.26.
3.
G.Bana, M.Biroli, M.Dervishi, F.E.Orche, R.Géraud-Stewart, D.Naccache, P.B.Rønne, P.Y.A.Ryan and H.Waltsburger, Time, privacy, robustness, accuracy: trade offs for the open vote network protocol. IACR Cryptol., ePrint Arch., 2021, p. 1065.
D.Bernhard, V.Cortier, D.Galindo, O.Pereira and B.Warinschi, SoK: A comprehensive analysis of game-based ballot privacy definitions, in: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17–21, 2015, 2015, pp. 499–516. doi:10.1109/SP.2015.37.
6.
D.Bernhard, V.Cortier, O.Pereira and B.Warinschi, Measuring vote privacy, revisited, in: ACM Conference on Computer and Communications Security (CCS 2012), T.Yu, G.Danezis and V.D.Gligor, eds, ACM, 2012, pp. 941–952.
7.
D.Bernhard, O.Pereira and B.Warinschi, How not to prove yourself: Pitfalls of the Fiat–Shamir heuristic and applications to helios, in: Advances in Cryptology – ASIACRYPT 2012 – 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2–6, 2012, Proceedings, X.Wang and K.Sako, eds, Lecture Notes in Computer Science, Vol. 7658, Springer, 2012, pp. 626–643.
8.
O.Blazy, G.Fuchsbauer, D.Pointcheval and D.Vergnaud, Signatures on randomizable ciphertexts, in: Public Key Cryptography – PKC 2011 – 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6–9, 2011, Proceedings, D.Catalano, N.Fazio, R.Gennaro and A.Nicolosi, eds, Lecture Notes in Computer Science, Vol. 6571, Springer, 2011, pp. 403–422.
9.
X.Boyen, T.Haines and J.Müller, Epoque: Practical end-to-end verifiable post-quantum-secure e-voting, in: IEEE European Symposium on Security and Privacy, EuroS&P 2021, Vienna, Austria, September 6–10, 2021, IEEE, 2021, pp. 272–291.
10.
S.Bursuc, C.C.Dragan and S.Kremer, Private votes on untrusted platforms: Models, attacks and provable scheme, in: IEEE European Symposium on Security and Privacy EuroS&P 2019, Stockholm, Sweden, June 17–19, 2019, IEEE, 2019, pp. 606–620.
11.
C.Burton, C.Culnane, J.Heather, T.Peacock, P.Y.A.Ryan, S.Schneider, V.Teague, R.Wen, Z.Xia and S.Srinivasan, Using Prêt à Voter in Victoria state elections, in: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections, EVT/WOTE’12, Bellevue, WA, USA, August 6–7, 2012, J.A.Halderman and O.Pereira, eds, USENIX Association, 2012.
12.
R.Carback, D.Chaum, J.Clark, J.Conway, A.Essex, P.S.Herrnson, T.Mayberry, S.Popoveniuc, R.L.Rivest, E.Shen, A.T.Sherman and P.L.Vora, Scantegrity II municipal election at Takoma Park: The first E2E binding governmental election with ballot privacy, in: 19th USENIX Security Symposium, Washington, DC, USA, August 11–13, 2010, Proceedings, USENIX Association, 2010, pp. 291–306.
13.
P.Chaidos, V.Cortier, G.Fuchsbauer and D.Galindo, BeleniosRF: A non-interactive receipt-free electronic voting scheme, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24–28, 2016, E.R.Weippl, S.Katzenbeisser, C.Kruegel, A.C.Myers and S.Halevi, eds, ACM, 2016, pp. 1614–1625. doi:10.1145/2976749.2978337.
D.Chaum, P.Y.A.Ryan and S.A.Schneider, A practical voter-verifiable election scheme, in: Computer Security – ESORICS 2005, 10th European Symposium on Research in Computer Security, Milan, Italy, September 12–14, 2005, Proceedings, S.D.C.di Vimercati, P.F.Syverson and D.Gollmann, eds, Lecture Notes in Computer Science, Vol. 3679, Springer, 2005, pp. 118–139.
16.
M.R.Clarkson, S.Chong and A.C.Myers, Civitas: Toward a secure voting system, in: 2008 IEEE Symposium on Security and Privacy (S&P 2008), 18–21 May 2008, Oakland, California, USA, IEEE Computer Society, 2008, pp. 354–368. doi:10.1109/SP.2008.32.
17.
V.Cortier, D.Galindo, R.Küsters, J.Müller and T.Truderung, SoK: Verifiability notions for e-voting protocols, in: IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22–26, 2016, 2016, pp. 779–798. doi:10.1109/SP.2016.52.
18.
V.Cortier and B.Smyth, Attacking and fixing helios: An analysis of ballot secrecy, in: Proceedings of the 24th IEEE Computer Security Foundations Symposium, CSF 2011, Cernay-la-Ville, France, 27–29 June, 2011, IEEE Computer Society, 2011, pp. 297–311. doi:10.1109/CSF.2011.27.
19.
J.Dreier, P.Lafourcade and Y.Lakhnech, Vote-independence: A powerful privacy notion for voting protocols, in: Foundations and Practice of Security – 4th Canada–France MITACS Workshop, FPS 2011, Paris, France, May 12–13, 2011, Revised Selected Papers, J.García-Alfaro and P.Lafourcade, eds, Lecture Notes in Computer Science, Vol. 6888, 2011, pp. 164–180, Springer.
20.
A.Fiat and A.Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: Advances in Cryptology – CRYPTO’86, Santa Barbara, California, USA, 1986, Proceedings, A.M.Odlyzko, ed., Lecture Notes in Computer Science, Vol. 263, Springer, 1986, pp. 186–194.
21.
A.Gelman and T.C.Little, Poststratification into many categories using hierarchical logistic regression, Survey Methodology46(1) (1997).
22.
B.Gnedenko, Theory of Probability, 6th edn, Taylor & Francis, 1998.
23.
Helios voting. Attacks and defenses, https://documentation.heliosvoting.org/attacks-and-defenses (accessed 11.04.2022).
24.
L.Hirschi, L.Schmid and D.A.Basin, Fixing the Achilles heel of e-voting: The bulletin board, in: 34th IEEE Computer Security Foundations Symposium, CSF 2021, Dubrovnik, Croatia, June 21–25, 2021, IEEE, 2021, pp. 1–17.
V.Iovino, A.Rial, P.B.Rønne and P.Y.A.Ryan, Universal unconditional verifiability in e-voting without trusted parties, in: 33rd IEEE Computer Security Foundations Symposium, CSF 2020, Boston, MA, USA, June 22–26, 2020, IEEE, 2020, pp. 33–48.
27.
S.Khazaei and D.Wikström, Randomized partial checking revisited, in: Topics in Cryptology – CT-RSA 2013 – the Cryptographers’ Track at the RSA Conference 2013, San Francisco, CA, USA, February 25–March 1, 2013, Proceedings, E.Dawson, ed., Lecture Notes in Computer Science, Vol. 7779, Springer, 2013, pp. 115–128.
28.
R.Küsters, J.Liedtke, J.Müller, D.Rausch and A.Vogt, Ordinos: A verifiable tally-hiding e-voting system, in: IEEE European Symposium on Security and Privacy, EuroS&P 2020, Genoa, Italy, September 7–11, 2020, IEEE, 2020, pp. 216–235.
29.
R.Küsters, J.Müller, E.Scapin and T.Truderung, SElect: A lightweight verifiable remote voting system, in: IEEE 29th Computer Security Foundations Symposium, CSF 2016, Lisbon, Portugal, June 27–July 1, 2016, 2016, pp. 341–354. doi:10.1109/CSF.2016.31.
30.
R.Küsters, T.Truderung and A.Vogt, Verifiability, privacy, and coercion-resistance: New insights from a case study, in: 32nd IEEE Symposium on Security and Privacy, S&P 2011, 22–25 May 2011, Berkeley, California, USA, 2011, pp. 538–553. doi:10.1109/SP.2011.21.
31.
R.Küsters, T.Truderung and A.Vogt, Verifiability, privacy, and coercion-resistance: New insights from a case study. IACR Cryptol, 2011, ePrint Arch., 2011:517.
32.
R.Küsters, T.Truderung and A.Vogt, Formal analysis of Chaumian mix nets with randomized partial checking, in: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18–21, 2014, 2014, pp. 343–358. doi:10.1109/SP.2014.29.
33.
B.E.Lauderdale, D.Bailey, J.Blumenau and D.Rivers, Model-based pre-election polling for national and sub-national outcomes in the US and UK, International Journal of Forecasting36(2) (2020), 399–413. doi:10.1016/j.ijforecast.2019.05.012.
34.
B.Lee, C.Boyd, E.Dawson, K.Kim, J.Yang and S.Yoo, Providing receipt-freeness in mixnet-based voting protocols, in: Information Security and Cryptology – ICISC 2003, 6th International Conference, Seoul, Korea, November 27–28, 2003, Revised Papers, J.I.Lim and D.H.Lee, eds, Lecture Notes in Computer Science, Vol. 2971, Springer, 2003, pp. 245–258.
35.
D.A.Levin, Y.Peres and E.L.Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2006.
36.
A.McIver, T.Rabehaja, R.Wen and C.Morgan, Privacy in elections: How small is “small”?, J. Inf. Secur. Appl.36(C) (2017), 112–126.
37.
D.Mestel, J.Müller and P.Reisert, How efficient are replay attacks against vote privacy? A formal quantitative analysis, in: 35th IEEE Computer Security Foundations Symposium, CSF 2022, Haifa, Israel, August 7–10, 2022, IEEE, 2022, pp. 179–194.
38.
K.W.Ng, G.-L.Tian and M.-L.Tang, Dirichlet and Related Distributions: Theory, Methods and Applications, 2011.
39.
K.Sako and J.Kilian, Secure voting using partially compatible homomorphisms, in: Advances in Cryptology – CRYPTO’94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21–25, 1994, Proceedings, Y.Desmedt, ed., Lecture Notes in Computer Science, Vol. 839, Springer, 1994, pp. 411–424.
40.
B.Schoenmakers, A simple publicly verifiable secret sharing scheme and its application to electronic voting, in: Advances in Cryptology – CRYPTO’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15–19, 1999, Proceedings, M.J.Wiener, ed., Lecture Notes in Computer Science, Vol. 1666, Springer, 1999, pp. 148–164. doi:10.1007/3-540-48405-1_10.
