# Brief Description/ Summary `ExactlyOnceCommandExecutor.process` first checks whether a semantically identical command has already run with `commandService.findSemanticallyIdenticalCommand(commandId)`. If not, it executes the command, and stores it after execution. This allows multiple semantically identical commands to run at the same time. There is a database consistency check which happens when storing a command execution with `commandService.save(commandId, requestContent, requestDateTime, result, LocalDateTime.now());`; This check however does not prevent storing multiple semantically identical commands, as the check includes the `correlationId`, which can be freely set by the voting server (and therefore, the adversary). For `RabbitListener` configured with `concurrency` to be more than 1, this is a real issue, as demonstrated by the test in [concurrentExecuteOnceExecution.diff](/uploads/21f984eac4e9ae59addaf3cf19b19776/concurrentExecuteOnceExecution.diff). This could be an issue if the underlying cryptographic algorithms assume they are only executed once. This includes all algorithms using this mechanism: - `PartialDecryptPCCAlgorithm.partialDecryptPCC` - `CreateLCCShareAlgorithm.createLCCShare` - `CreateLVCCShareAlgorithm.createLVCCShare` - `VerifyLVCCHashAlgorithm.verifyLVCCHash` - `MixDecOnlineAlgorithm.mixDecOnline` - `MixDecOfflineAlgorithm.mixDecOffline` While we could test that the `ExactlyOnceCommandExecutor` indeed executes multiple times, we could not fully integration test the command executions: We did not find similar integration tests (and test-data) in the code base, and they are very high-effort to setup initially. Based on a careful code review, we however proposed two exploits, and Swiss Post helped to assess their impact: - Executing `PartialDecryptPCCAlgorithm.partialDecryptPCC` multiple times for the same voter, to tally a different vote as the voter intended ((ab)using the consistency resolution procedure). This does not work, as the partially decrypted vote is stored in the `ENCRYPTED_VERIFIABLE_VOTE` table, which has a primary key constraint on `VERIFICATION_CARD_FK_ID` (i.e. only the first partially decrypted vote would be stored successfully to the database). - Executing `CreateLVCCShareAlgorithm.createLVCCShare` multiple times concurrently, to attempt more than `MAX_CONFIRMATION_ATTEMPTS`. This does not work, as the number of attempts is stored in the `VERIFICATION_CARD_STATE` table using hibernate with a `@VersionId` annotation, and Hibernate caching further ensures the entity is the same for both the max confirmation attempts check and the attempt increment (i.e. only the first check and increment per attempt succeeds; the others crash with a `StaleStateException`). The command execution isolation has been fixed in the meantime: https://gitlab.com/swisspost-evoting/e-voting/e-voting/-/commit/23ebdd24a0d8b2d57e4ddeb80aa53f1875d89a74#dd3439c738ee59f24a86e7bb8d262cce672d87e1 We see no other concrete possible exploits as the ones which were already investigated. <details> <summary>Original issue description</summary> ## Original title: Concurrent execution allows to insert additional vote(s), which breaks Individual and Universal Verifiability To vote, the user enters their voting choices into the voter device. The voter device then encrypts the voting choices into the vote, and sends the vote over the voting server to the control components. Each control component `i` then validates the vote, partially decrypts it into `d_i` and sends `d_i` to the other control components. Once valid `d_j` of all the other control components `j != i` is received, the control component uses `d_1, d_2, ...` to derive the return codes sent to the voter. The voter validates the return codes, and then confirms the vote. A dishonest voting device can generate further valid votes, and send them to the dishonest server. In case multiple valid votes per voter exist, Algorithm 6.9 `SendVoteAgreement` is executed, which decides on the vote to tally by checking that all control components have produced a respective `d_j`. So that `SendVoteAgreement` has a unique result (and therefore the single correct vote is tallied), the control component must only partially decrypt a single vote. However, as currently implemented, it is possible that an untampered / honest control component *partially decrypts multiple votes for the same voter*. The honest control component even creates the return codes as expected for the voter, making the attack undetectable to the voter. The result of the attack are two (or more) valid votes for the same voter which both pass the `SendVoteAgreement` check. The attack relies on the timing of concurrent processes. This breaks the one ballot per voter subproperty of individual verifiability: For the same voter, multiple valid ballots are accepted. Further, attempts to resolve this situation will likely break universal verifiability (i.e. the election result is incorrect): The `SendVoteAgreement` check cannot decide which vote is valid, hence needs to drop all, count all or randomly choose one. Only in the latter case it has a slim chance to determine the election result correctly. Another attack, using the same issue & adversary model, allows the adversary to try out more than 5 confirmation codes. This makes it easier for the adversary to guess a confirmation code, and therefore to confirm a vote (e.g. which the voter did not confirm themselves, because the return codes were wrong). ## Root cause technical writeup The critical sections are not properly isolated. For example, the following critical section can be entered by two concurrent processes: ```java checkArgument(verificationCardStateService.isNotPartiallyDecrypted(vc_id), "The partial Choice Return Codes have already been partially decrypted."); // critical section verificationCardStateService.setPartiallyDecrypted(vc_id); ``` If `isNotPartiallyDecrypted(vc_id)` is false (which is the case initially) multiple processes can enter the critical section, as for all `checkArgument` succeeds. Only after the first process exited the critical section will further processes be prevented to enter it. But those processes already in the critical section can continue processing, and finish execution without crashing (i.e. `setPartiallyDecrypted(vc_id)` can be called multiple times without raising an exception). This lack of isolation is present in at least the following algorithms: - `PartialDecryptPCCAlgorithm.partialDecryptPCC` (see code above; fails to enforce single execution) - `CreateLCCShareAlgorithm.createLCCShare` (fails to enforce a single successful execution) - `CreateLVCCShareAlgorithm.createLVCCShare` (fails to enforce at most `MAX_CONFIRMATION_ATTEMPTS` executions) - `VerifyLVCCHashAlgorithm.verifyLVCCHash` (fails to enforce a single successful execution) - `MixDecOnlineAlgorithm.mixDecOnline` (fails to enforce mixing only once) - `MixDecOfflineAlgorithm.mixDecOffline` (fails to enforce mixing only once) Further, `ExactlyOnceCommandExecutor.process` uses the same pattern, so there might be multiple commands running at the same time which are semantically identical (as checked by `commandService.findSemanticallyIdenticalCommand(commandId)`). The database consistency check which happens when storing a command execution with `commandService.save(commandId, requestContent, requestDateTime, result, LocalDateTime.now());` does not prevent storing multiple semantically identical commands, as the database consistency check includes the `correlationId`, which can be freely set by the voting server (and therefore, the adversary). For `RabbitListener` configured with `concurrency` to be more than 1, this is a real issue, as demonstrated by the test in [concurrentExecuteOnceExecution.diff](/uploads/21f984eac4e9ae59addaf3cf19b19776/concurrentExecuteOnceExecution.diff). This is notably the case for all the mentioned algorithms above (except `MixDecOfflineAlgorithm.mixDecOffline` which does not run on a control component). While we could test that the `ExactlyOnceCommandExecutor` indeed executes multiple times, we could not integration test the command executions: We did not find similar integration tests (and test-data) in the code base, and they are very high-effort to setup initially. Our description of the concrete exploits is therefore based on a careful code review, but without reproducing integration tests. ### Partially decrypting multiple votes to tally a different vote as the voter intended The attack proceeds as follows: 1. Dishonest voter device creates the two valid votes `v` (= user chosen), `v'` (= voter-device chosen). 2. `PartialDecryptProcessor.onMessage` listens concurrently; and spawns process A for `v` and process B for `v'`. 3. `ExactlyOnceCommandExecutor.process` is eventually invoked, fails to isolate, and therefore both processes eventually enter `partialDecryptService.performPartialDecrypt`. 4. Both processes eventually enter `partialDecryptPCCAlgorithm.partialDecryptPCC` which fails to isolate, so both make it past of line 97 `checkArgument`. 5. Process A finalizes the command execution quickly (publishing `d` for `v`) and spawns further commands to generate the return codes. 6. Process B takes longer, and only finishes command execution later (publishing `d'` for `v'`). Notably, process B finishes after process A reached `LCCShareProcessor.verifyPayload` to ensure A succeeds in decrypting the PCC. The expected behavior would be that either 3 or 4 do not allow more than one process to proceed, and crash the other. ### Attempting more than MAX_CONFIRMATION_ATTEMPTS The attack proceeds as follows: 1. Adversary sends multiple confirm messages `c`. 2. `LongVoteCastReturnCodesShareHashProcessor.onMessage` listens concurrently; and spawns processes for each `c`. 3. `ExactlyOnceCommandExecutor.process` is eventually invoked; does not isolate as `confirmationKeyAsString` is part of the `contextId`; and invokes `generateControlComponenthlVCCPayload`. 4. All processes enter `CreateLVCCShareAlgorithm.createLVCCShare` which fails to isolate, so both make it past of line 109 `checkArgument`. 5. All processes finish the execution, publishing each a `hlVCC` corresponding to their respective input. The expected behavior would be that 4 does not allow more than five process to proceed (respectively less if it has been executed before for the same voter), and crash all others. ## Impact The first attack breaks the one ballot per voter subproperty of individual verifiability: For the same voter, multiple valid ballots are accepted. Further, attempts to resolve this situation will likely break universal verifiability (i.e. the election result is incorrect): The `SendVoteAgreement` check cannot decide which vote is valid, hence needs to drop all, count all or randomly choose one. Only in the latter case it has a slim chance to determine the election result correctly. The second attack allows the adversary to try to guess the confirmation codes more than five times, which decreases the individual verifiability guarantees. ## Severity Severity is at least high: It compromises the voting process. The timing necessary for the attack to work is probably hard to setup. ## Possible Solution The critical sections must be properly isolated. Proposals: - `ExactlyOnceCommandExecutor.process` must properly isolate; e.g. by storing the command execution *first*, then checking only a single execution is stored, and only the actually executing it. - The algorithms need to reconsidered for concurrent executions. This then likely results in a locking mechanism which is e.g. synchronized over the database. </details>