{"id":"82d58e00-e24a-4b00-bab3-f8e753c2eb5b","arxiv_id":"1908.05127","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The Moscow Internet voting system's ElGamal encryption was broken twice: 256-bit keys allowed full private key recovery, and the patched version leaked the quadratic residuosity of each vote.","lead":"The authors broke the encryption used in Moscow's 2019 Internet voting system twice: first by recovering the private keys from too-small 256-bit primes in minutes, then by showing the patched 1024-bit version leaks one bit of every vote. This matters because it shows that a real high-stakes e-voting deployment used cryptography that was not secure, and the attacks forced emergency fixes before election day.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified. The two attacks are mathematically sound and reproducible; the only caveat is the contingent practical impact of the second attack's one-bit leak, which does not undermine the cryptographic claim.","rationale":"The reader's weakest assumption correctly identifies the only contingency in the second attack's practical vote-counting impact: candidate deputy IDs must have a suitable quadratic-residue split. This is not a property of the encryption scheme and could fail in a given election. However, the central cryptographic claims do not depend on it. The first attack is unconditional given the small primes and the published public keys, and the second attack is a valid semantic-security break regardless of the ID distribution. The paper already supplies direct evidence that the split occurs in the actual public test. The proof of the Legendre-symbol leakage is elementary and correct: with g and pk in the subgroup of quadratic residues, b = pk^r * m is a QR exactly when m is. No internal inconsistency, missing step, or unsupported computational claim was found. The merger of two preprints and the lack of formal verification are noted but do not undermine correctness. Hence the ACCEPT verdict should remain unchanged.","tokens_in":13614,"tokens_out":7504,"duration_ms":76363,"concrete_test":"Re-run the Appendix A shell script from the pinned CADO-NFS commit against the public keys of revision d70986b2c4da and verify all three private keys are recovered; then recompute the Legendre symbols of the ten second-components in Appendix B from the modified revision 1d4f348681e9 and confirm exactly five are quadratic residues. If either step fails, the corresponding attack claim would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I cannot identify a load-bearing concern that would invalidate the central claim. The first attack is a direct key-recovery via discrete logarithms in 256-bit prime fields, with timings and a reproducible script; nothing in the argument depends on an unverified assumption. The second attack is a correct Legendre-symbol distinguisher: since the generator and public key are quadratic residues, the second ciphertext component is a quadratic residue if and only if the plaintext is, and the published ciphertexts confirm the expected 5/10 split. The only real limitation is explicitly acknowledged in Section 2.3: turning the one-bit distinguisher into a vote-counting attack requires the relevant candidate deputy IDs to fall into different quadratic-residue classes. That is an empirical contingency about a particular election, not a flaw in the proof of semantic insecurity. The paper even demonstrates the contingency is satisfied in the August 28 public test (Appendix C). Therefore the core claims that both versions' encryption is broken stand.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the encryption used by the Moscow Internet voting system at two revisions. In the original revision (d70986b2c4da), the system uses a triple-nested ElGamal over finite fields with three 256-bit safe primes; the authors show via CADO-NFS discrete-log computations that the secret keys can be recovered from the public keys in roughly five to nine minutes per key on a desktop machine, and they provide a shell script and measured timings. In the modified revision (1d4f348681e9), after the key size was increased to 1024 bits and the scheme simplified, the authors identify a subgroup/one-bit leak: because the generator lies in the quadratic-residue subgroup while plaintexts are arbitrary small integers, the Legendre symbol of the second ciphertext component equals that of the plaintext. This is a distinguisher that breaks semantic security. They verify the bit split in the published test ciphertexts (five out of ten) and show in Appendix C that in the August 28 test the two candidates' IDs fell in opposite quadratic-residue classes, so the leaked bit would have distinguished the two candidates. The paper also discusses the protocol-level consequences and the final fix (squaring the plaintext before encryption).","tokens_in":13730,"tokens_out":8755,"duration_ms":88835,"significance":"The first attack is a reproducible, precisely documented break of a deployed e-voting encryption scheme: exact git revisions, a public toolchain, and measured running times are given. The second attack is a clean and correct distinguisher argument that does not rely on fitted parameters or unstated assumptions; it demonstrates how a subtle encoding error converts standard ElGamal into a scheme that is not semantically secure. The paper is more than a catalog of mistakes: it gives concrete evidence of the leak's practical relevance while honestly acknowledging the contingency that the vote-counting scenario requires the candidate IDs to be split between quadratic-residue classes. The appendices with scripts and data are a strength of the paper. If the claims hold, this is a significant case study for both the cryptographic and e-voting communities.","major_comments":[],"minor_comments":[{"comment":"The symbol q denotes both the subgroup order (p = 2q + 1) and the upper bound of the plaintext interval [1, q−1] in the same section. This is mathematically consistent, but a sentence clarifying that [1, q−1] is a set of integers mapped into F_p^*, and that the Legendre symbols are computed modulo p, would remove a likely source of confusion.","section":"Section 2.2"},{"comment":"The description of the sign choice after taking the square root ('the sign choice is based on the relative size of p − m and m') is terse; please spell out that only one of the two square roots lies in the small interval corresponding to a 32-bit deputy id, which is what allows unambiguous decryption.","section":"Section 3.2"},{"comment":"Reference [12] contains a doubled article: 'An attack on the the encryption scheme...' should read 'An attack on the encryption scheme...'.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"For the editor: the manuscript is a convincing and reproducible case study of real-world cryptographic failure, and the authors transparently disclose that it merges two of their earlier preprints. The only limitation, the contingent practical impact of the one-bit distinguisher, is explicitly acknowledged in the text and does not undermine the central claim that the second version is not semantically secure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: the paper really does break the encryption of the Moscow voting system in both deployed versions, and it shows its work. If you care about e-voting security or about real-world failures of textbook ElGamal, this is worth your time.\n\nWhat's actually new: nothing deep cryptographically. The first attack is simply observing that 256-bit primes are far too small for finite-field discrete log, and then using CADO-NFS to compute the private keys in minutes. The second attack is the old Lim-Lee subgroup/key-validation idea: since the generator and public key are quadratic residues but the message is not restricted to the QR subgroup, the Legendre symbol of the second ciphertext component leaks the QR class of the message. Both techniques are textbook. The paper is explicit that it is a merger of the authors' earlier preprints, so the results themselves are not new.\n\nWhat the paper does well: it is precise and reproducible. Exact git revisions, a shell script for the discrete log attack, timings on a standard machine, and a Python snippet for the Legendre test on the published ciphertexts. The second attack's distinguisher is proven cleanly and verified: exactly five of ten published b-values are quadratic residues. The authors also honestly discuss the limit of the second attack: one leaked bit is only a vote-counting break when the relevant candidate IDs happen to split between QR and non-QR classes. They show that in the August 28 public test the two candidate IDs did split, so the attack would have decoded every ballot there. That contingency is real but does not weaken the cryptographic claim: the scheme is not semantically secure, period.\n\nSoft spots: the paper's larger narrative about the protocol, the blockchain, and the D-day events is necessarily speculative because there is no specification, and the authors label it as such. That material is useful context but not a technical contribution. Also, the claim that the second attack 'can be used for counting the number of votes cast for a candidate' is only true for districts with a particular QR split; the text makes this clear, but a careless reader might overstate the result.\n\nBottom line: this deserves a serious referee. The techniques are old, but the applied break of a legally binding e-voting system—with one district decided by fewer than 100 votes—is a significant case study, and the reproducibility is a model. I would accept it as a short paper at a security or e-voting venue, with minor revisions to tighten the claims about the second attack's practical reach.","headline":"The paper delivers two reproducible breaks of a real deployed e-voting encryption; the techniques are old but the applied result is solid and deserves review.","tokens_in":14304,"tokens_out":1887,"would_cite":true,"duration_ms":19223,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The Moscow Internet voting system's ElGamal encryption was broken in both tested versions: the first via fast discrete-logarithm key recovery, the second via a one-bit quadratic-residue leak.","keywords":["Internet voting security","ElGamal encryption","discrete logarithm","quadratic residue","Legendre symbol","semantic security","subgroup attack","Moscow election"],"falsifier":"Run the paper's key-recovery procedure against the published public keys of the original revision and time it; if a private key cannot be recovered within an hour on comparable hardware, the claim of minute-scale recovery fails. For the second attack, compute the residue class of every candidate identifier for an election run under the modified scheme; if all identifiers of viable candidates lie in one class, the leaked bit distinguishes nothing.","tokens_in":13378,"feed_emoji":"🗳️","tokens_out":8142,"duration_ms":81932,"temperature":0.7,"pith_summary":"The paper reports two attacks on the encryption used in Moscow's September 2019 Internet voting experiment, both confirmed against the public source code and both fixed after disclosure. In the original revision, each ballot was encrypted with a three-level ElGamal construction over 256-bit prime fields; the paper shows that recovering the three private keys from the public keys by discrete logarithm takes minutes, so any ballot can be decrypted. In the modified revision, a single 1024-bit ElGamal encryption was used, but the message space was not restricted to the quadratic-residue subgroup generated by the encryption key, so the Legendre symbol of the second ciphertext component leaks whether the plaintext is a quadratic residue, breaking the scheme's semantic security. Because the plaintext is the candidate's identifier, this one-bit leak can reveal the vote when the leading candidates' identifiers fall into different residue classes.","feed_headline":"Moscow e-voting encryption was practically broken—twice","feed_subtitle":"First version leaked private keys in minutes; second leaked one bit per ballot through quadratic residues.","key_machinery":"The first mechanism is discrete-logarithm computation modulo primes of about 256 bits via the General Number Field Sieve; the identity that carries the attack is $sk = \\log_g pk$, and because each $p_i$ is small enough the logarithm is computable in seconds to minutes. The second mechanism is a quadratic-residue test: with $p = 2q+1$, generator $g \\in Q_p$, and message $m \\in [1,q-1]$, the second ciphertext component satisfies $b = pk^r m$, and the Legendre symbol $\\left(\\frac{b}{p}\\right)$ equals $\\left(\\frac{m}{p}\\right)$, giving an efficient distinguisher. The paper thus shows that the scheme's security rests on two things: sufficiently large prime groups, and encoding the message inside the group generated by the encryption key. When either condition fails, vote secrecy leaks.","core_discovery":"The central claim is that neither of the two tested versions of the Moscow Internet voting system's ElGamal encryption was secure. For revision d70986b2c4da, the three 256-bit primes make the discrete logarithm of each public key computable with a number field sieve implementation in 314 to 507 seconds, giving an attacker the three private keys and full decryption of all ballots. For revision 1d4f348681e9, although the generator was moved to the quadratic-residue subgroup of a 1024-bit safe prime, the message was still any integer in $[1, q-1]$; therefore the Legendre symbol of $b = pk^r \\cdot m$ immediately says whether $m$ is a quadratic residue, and the scheme is not semantically secure. The paper demonstrates this leak on the published test data: exactly five of ten published ciphertexts had $b$ a quadratic residue, and in the August 28 test the two candidate identifiers were one in each class, so every vote would have been decodable.","pith_inferences":["A general screening rule for any ElGamal-based system follows: if the generator lives in a proper subgroup, the encryption routine must test that every plaintext lies in that subgroup, otherwise any multiplicative character of the group leaks one bit.","The residue split is easy to audit in advance: an election authority could list the Legendre symbol of every candidate identifier before the vote, and in any election where the two front-runners fall on opposite sides the modified scheme is a full vote-revealer, not just a one-bit curiosity.","A less obvious consequence is that the leaked bit is a deterministic fingerprint of a candidate: even if ballots are rerandomized, the Legendre symbol of the ciphertext's second component stays fixed for a given candidate, which could allow linking multiple encryptions of the same choice."],"forward_implications":["Under the original revision, an attacker who reads the blockchain can decrypt every ballot as soon as the three public keys are published, which is before or during the election; the 12-hour challenge window is irrelevant because key recovery takes minutes.","Under the modified revision, computing one Legendre symbol per ciphertext recovers one bit of every plaintext; in the Moscow protocol that bit distinguishes between a voter's two main candidates whenever their deputy IDs lie in different quadratic-residue classes.","Both attacks were validated against real published data: the three private keys of the original system were recovered in 314 to 507 seconds each, and in the modified system five of ten published test ciphertexts corresponded to quadratic non-residues.","The fix adopted for the final election, squaring the message before encryption, closes the Legendre-symbol leak, but the paper notes the 1024-bit prime remains too small for medium-term security and that textbook ElGamal is not IND-CCA2, so future protocol changes could reintroduce exploitable weaknesses."],"supporting_citations":[{"why":"Public source code that defines the exact revisions and ciphertext data used in both attacks.","marker":"[10]"},{"why":"Number-field-sieve software implementation that performs each discrete-logarithm recovery in the first attack.","marker":"[27]"},{"why":"Largest published prime-field discrete-logarithm record, at 768 bits, used as the baseline to extrapolate 1024-bit hardness.","marker":"[19]"},{"why":"Logjam-style shared precomputation that the software exploits when computing two logarithms modulo one prime.","marker":"[2]"},{"why":"Original prime-order subgroup attack on discrete-log-based schemes that the second attack extends.","marker":"[23]"},{"why":"Efficient Legendre-symbol algorithm that makes the quadratic-residue check on ciphertext components instantaneous.","marker":"[32]"},{"why":"Survey of real-world small-subgroup attacks that motivates the key-validation concern behind the second attack.","marker":"[31]"}],"fun_headline_variants":["Moscow e-voting crypto cracked twice","Two attacks break Moscow e-voting encryption","ElGamal flaws exposed in Moscow e-voting","Moscow e-voting: key size and semantics fail","Practical breaks in Moscow e-voting scheme"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the one-bit leak to reveal which candidate a voter chose, the two leading candidates' identifier numbers must fall into different classes under the scheme's residue test; the paper assumes that is likely because the identifiers look random, but it is not guaranteed by the scheme.","fun_headline_variants_meta":{"raw":{"variants":["Moscow e-voting crypto cracked twice","Two attacks break Moscow e-voting encryption","ElGamal flaws exposed in Moscow e-voting","Moscow e-voting: key size and semantics fail","Practical breaks in Moscow e-voting scheme"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000154,"raw_usage":{"total_tokens":1191,"prompt_tokens":905,"completion_tokens":286,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":214}},"tokens_in":521,"tokens_out":286,"duration_ms":3339,"temperature":1.0,"reasoning_tokens":214,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:23:01.191626+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's key-recovery procedure against the published public keys of the original revision and time it; if a private key cannot be recovered within an hour on comparable hardware, the claim of minute-scale recovery fails. For the second attack, compute the residue class of every candidate identifier for an election run under the modified scheme; if all identifiers of viable candidates lie in one class, the leaked bit distinguishes nothing.","supporting_citations":[{"cited_title":"https://github.com/moscow-technologies/blockchain-voting, 2019","cited_arxiv_id":null,"evidence_quote":"Public source code that defines the exact revisions and ciphertext data used in both attacks."},{"cited_title":"CADO-NFS, an implement ation of the num- ber field sieve algorithm, 2019","cited_arxiv_id":null,"evidence_quote":"Number-field-sieve software implementation that performs each discrete-logarithm recovery in the first attack."},{"cited_title":"Computation of a 768-bit prime field discrete logarithm","cited_arxiv_id":null,"evidence_quote":"Largest published prime-field discrete-logarithm record, at 768 bits, used as the baseline to extrapolate 1024-bit hardness."},{"cited_title":"Alex Halderman, Nadia Heninger, Drew Springall, Emmanue l Thomé, Luke Valenta, Ben- jamin VanderSloot, Eric Wustrow, Santiago Zanella Béguelin , and Paul Zimmermann","cited_arxiv_id":null,"evidence_quote":"Logjam-style shared precomputation that the software exploits when computing two logarithms modulo one prime."},{"cited_title":"A key recovery attack on d iscrete log-based schemes using a prime order subgroup","cited_arxiv_id":null,"evidence_quote":"Original prime-order subgroup attack on discrete-log-based schemes that the second attack extends."},{"cited_title":"Modern computer algebra","cited_arxiv_id":null,"evidence_quote":"Efficient Legendre-symbol algorithm that makes the quadratic-residue check on ciphertext components instantaneous."},{"cited_title":"Measuring small subgr oup attacks against Diffie- Hellman","cited_arxiv_id":null,"evidence_quote":"Survey of real-world small-subgroup attacks that motivates the key-validation concern behind the second attack."}],"review_version":1}