🐞 HashedElGamalCiphertext is buggy, fails inconsistently

[danwallach]

Is there an existing issue for this?

• I have searched the existing issues

Current Behavior

In my attempts to understand HashedElGamal, I've found problems. I wrote this unit test, while setting the environment variable to ensure I was using the 4096-bit production group.

    @given(elgamal_keypairs(), binary(min_size=10, max_size=400))
    def test_hashed_elgamal_properties(self, kp: ElGamalKeyPair, plaintext: bytes) -> None:
        hmac_nonce = rand_range_q(2)
        hmac_seed = rand_range_q(2)
        padded_plaintext = _add_padding(plaintext, PaddedDataSize.Bytes_512)
        hmac = hashed_elgamal_encrypt(padded_plaintext, hmac_nonce, kp.public_key, hmac_seed)
        decryption_bytes_padded = hmac.decrypt(kp.secret_key, hmac_seed)
        self.assertIsNotNone(decryption_bytes_padded)

        decryption_bytes = _remove_padding(decryption_bytes_padded, PaddedDataSize.Bytes_512)
        self.assertEqual(plaintext, decryption_bytes)

This test passes often. But it sometimes fails the HMAC check.

-------------------------------- Captured stdout call --------------------------------
[48413:2022-06-06 16:23:24,477]:ERROR:elgamal.py.decrypt:#L143: MAC verification failed in decryption.
--------------------------------- Captured log call ----------------------------------
ERROR    electionguard:logs.py:87 elgamal.py.decrypt:#L143: MAC verification failed in decryption.
------------------------------------- Hypothesis -------------------------------------
Falsifying example: test_hashed_elgamal_properties(
    kp=ElGamalKeyPair(secret_key='54A8CC61CB8ACD8B4EE35F007CC979960C3F493A3F0347B6AFAD6B620FF575E5', public_key='858B268D0FEFB9FA57506456B6B4C99998F1A5E8327E09181B656584B3197722D55FFCA61CE859702A3FDF4B9CC3A8D14F7382314CD92D8287DEC501C44BCA11A0008D47D654F34723E944703CC1F1F831A3C2EB190B16CF74685CACF96135DA60CEAD422A7EBD9E07B9038FC48889FD17F22E058CB2BD077D1CBFBDD3502A9F2AAFDFFACB58E0459D7D173D1D0F152ED0FEB7EE866261192F45C3F49D6E5691A967C271335BC3B2A2940B76A25991407265FE18BBB1DF90D087205B26431C97627EEF4AAEB594C7E6D1FC4B3BD5E8FF4D685F19DCB69A1FF6757C50E4462A02CB642C691373A1CFB9BAEF101629BA773994062EBF7EC90D8B6BC6F5ACB551C1DCF06F321E9E4ADC123735544E104A7481AD5DB9C64594BEC5D10B36A10A40A2E88356F282C4E900581CD6E4D8CD15A735A0B7B1E5FF77B056495FD70683937FC5EDA73DD8E8689FC4202A0146853A72BC05C3D0504CD3DD2530A11B47316E2D9BBC2A629FC3BA3DDF3D4C15F4583EE12C2E6116CE45A4A21F46690ECEF1AFFD91A1A47D043A5EE72FC8EF762B81B6EE87A09C335492A96E60F68ABFDA881C95287CC8DE4D129E6507D16ACA205598083B3D6F9723EF90B8220F8B593AFC64C5E31426CC6D8D38F1740884B3E2D736C4957D0ADECBF3F16C27255C32BDDA6F0E44EB9A3ADA6A16919ACAC342B38ED4BEB1D42E5375FA26314D7085CEEADF6A4F'),
    plaintext=b'k\xdc\x9e\xad\xb2\xdfp0[\x84\xd4\x19\x96\xf7\xb9',
    self=<tests.property.test_elgamal.TestElGamal testMethod=test_hashed_elgamal_properties>,
)
Failed to reproduce exception. Expected: 
self = <tests.property.test_elgamal.TestElGamal testMethod=test_hashed_elgamal_properties>
kp = ElGamalKeyPair(secret_key='54A8CC61CB8ACD8B4EE35F007CC979960C3F493A3F0347B6AFAD6B620FF575E5', public_key='858B268D0FEF...D38F1740884B3E2D736C4957D0ADECBF3F16C27255C32BDDA6F0E44EB9A3ADA6A16919ACAC342B38ED4BEB1D42E5375FA26314D7085CEEADF6A4F')
plaintext = b'k\xdc\x9e\xad\xb2\xdfp0[\x84\xd4\x19\x96\xf7\xb9'

    @given(elgamal_keypairs(), binary(min_size=10, max_size=400))
    def test_hashed_elgamal_properties(self, kp: ElGamalKeyPair, plaintext: bytes) -> None:
        hmac_nonce = rand_range_q(2)
        hmac_seed = rand_range_q(2)
        padded_plaintext = _add_padding(plaintext, PaddedDataSize.Bytes_512)
        hmac = hashed_elgamal_encrypt(padded_plaintext, hmac_nonce, kp.public_key, hmac_seed)
        decryption_bytes_padded = hmac.decrypt(kp.secret_key, hmac_seed)
>       self.assertIsNotNone(decryption_bytes_padded)
E       AssertionError: unexpectedly None

tests/property/test_elgamal.py:235: AssertionError

It's worth noting that this padding process is not specified anywhere in the NIST spec. The NIST encryption has a length field that allows for truncation, and of course the message is "chunked" into 32-byte pieces that fit the underlying hash function's input size. I've only included the padding here because I need to be compatible with it.

If I strip out the padding altogether, the test will always fail.

Expected Behavior

There should exist a suitable property-based test, perhaps like the one above, that passes consistently.

For contrast, here's our TypeScript version:
https://github.com/danwallach/ElectionGuard-TypeScript/blob/main/src/electionguard/core/hashed-elgamal.ts

And the property-based tests that it passes:
https://github.com/danwallach/ElectionGuard-TypeScript/blob/main/test/electionguard/core/hashed-elgamal.test.ts

The TypeScript implementation, for contrast:

• Complies with the NIST spec
• Doesn't do anything weird with padding
• Doesn't do anything weird with key bits
• Passes a vigorous property-based test

Steps To Reproduce

No response

Environment

No response

Anything else?

Related bug report: #646

[keithrfung]

Example in GitHub Action

[keithrfung]

See fix/review-hashed-elgamal for starting point