ElGamal Malleability — scaling plaintext by a known factor without the private key

ElGamal decryption is a group homomorphism in the second ciphertext component, so anyone — with no private key at all — can turn a ciphertext encrypting m into one that decrypts to m * t mod p for any known t.

The signal that betrays it

- Ciphertext is an ElGamal pair (c1, c2) and the service exposes a decryption or verification oracle, but refuses to run it on one specific target ciphertext — "you may not submit this exact ciphertext", "you may not query the flag directly", an exact-match blocklist check. - The task wants you to produce a *different* ciphertext that still leaks something about the same underlying m — "forge a related plaintext", "obtain a scaled/derived value". - Explicit multiplicative-homomorphism framing: "scale", "multiply the ciphertext", "the oracle will decrypt anything except the flag". - A hint that the check happens on the raw ciphertext tuple rather than on the recovered plaintext — that's exactly the gap malleability exploits, since the ciphertext can change while still being *about* the same message. - Contrast signal: if the challenge instead wants you to shift m by an *additive* constant (flip a byte, change one field of a structured plaintext), that is not this technique — see What does NOT work.

How to exploit it

Scale by a known factor, then divide it back out. Given (c1, c2) encrypting m under public key y = g^x:

``python t = 2 # any known, nonzero multiplier mod p c2_new = (c2 * t) % p # (c1, c2_new) now decrypts to m*t m_t = oracle_decrypt(c1, c2_new) # bypasses an exact-match check on the original ciphertext m = (m_t * pow(t, -1, p)) % p # invert t to recover the original m ` t just needs to be nonzero mod p — since p is prime every nonzero residue is invertible, so any small t (2, 3, ...) works and the choice of t` carries no risk of picking a non-invertible value the way it can in a composite-order group (see DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime for what changes there).

Re-randomize instead of just scaling, when `c1` is also checked. If the blocklist compares the *whole* tuple (c1,c2) rather than just c2, transform both components together with a fresh random r: ``python c1_new = (c1 * pow(g, r, p)) % p # = g^(k+r) c2_new = (c2 * pow(y, r, p)) % p # = m * y^(k+r) ` This re-encrypts the same m under a fresh effective ephemeral exponent k+r — the pair no longer matches the blocked ciphertext at all, and decrypting it returns m directly (no division needed, since t=1 here; combine with the scaling trick above if you need a different m` too).

**Chain blinds if the oracle only returns a *derived* plaintext.** If the response isn't the raw decryption but something computed from it (a hash check, a comparison), you may need to query with several different t values and combine the results — same idea as blinding a signing oracle in RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism (RSA's version of this exact move: multiplicative homomorphism plus a random blind defeats an exact-match filter).

What does NOT work

- Expecting this to recover the private key `x` or solve the discrete log. Malleability only lets you relate a *new* ciphertext to a known scaling of m — it gives you no leverage on x or on k by itself. You still need some oracle (decryption, or any response that leaks structure) to get information back out; against a service that never returns anything derived from the plaintext, malleability alone yields nothing. - Trying it against a scheme that adds integrity on top of raw ElGamal. Cramer–Shoup (explicitly built as a non-malleable, CCA2-secure variant of ElGamal) and any hybrid construction that MACs or hashes the plaintext before accepting a ciphertext will reject the mauled ciphertext before the multiplicative structure ever helps you — the fix for this whole technique is exactly "stop being raw ElGamal." - Confusing this with additive malleability. ElGamal only lets you scale m by a multiplicative factor t; there is no native way to add a constant to m the way flipping a ciphertext byte adds a constant into the next plaintext block in CBC/CTR (see CBC Bit-Flipping — controlled tampering with no oracle needed). If a challenge wants "add 1000 to the balance field," that is a different cipher's malleability, not this one — don't force an ElGamal scaling trick onto an additive target. - Mauling only one of `c1`/`c2` when both need to move together. Scaling touches c2 alone; re-randomizing to dodge a full-tuple check touches c1 and c2 together with the *same* r. Transforming just one inconsistently produces garbage on decryption, not a related plaintext — it looks like the attack failed when actually the two components were desynced. - Stopping once the blocklist is bypassed. Getting the oracle to accept your mauled ciphertext is not the win condition — the returned value is m*t, not m. Forgetting the final pow(t, -1, p) division leaves you with a scaled plaintext that still needs to be unwrapped.

Related

ElGamal Encryption — when the key is a discrete log, not a factored modulus DH Man-in-the-Middle — unauthenticated exchange lets an active attacker relay two separate keys Discrete Logarithm — the factorization of the group order picks your algorithm Cryptanalysis Methodology — classify the family before you reach for an attack RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism CBC Bit-Flipping — controlled tampering with no oracle needed DH Composite Modulus — splitting the discrete log by CRT when the modulus isn't prime