Recipient-Bound Ciphertexts Against Key-Leaking Subverted Encryption in Certificateless Systems

Encryption software can be secretly modified so that it still works correctly while quietly leaking keys to whoever planted the modification. This is called an algorithm-substitution attack. Subvert KEM to Break DEM showed how far this goes for hybrid encryption. A key encapsulation mechanism (KEM) packages a fresh session key for the recipient, and a data encapsulation mechanism (DEM) then encrypts the actual message under that key. If the KEM's ciphertext lives in a fixed public base, of the form $rP$ for coins $r$, then a planted random-number generator can chain its coins through a Diffie–Hellman value shared with the attacker. Under that chaining, an attacker holding a subversion key recovers session keys from just two successive ciphertexts. No recipient secret is involved. The result is retroactive decryption: recorded traffic is read later even though no long-term key was ever stolen.

Our claim is that this chaining works only because the ciphertext does not depend on the recipient's key. If every ciphertext component instead lives in a base $B$ whose discrete logarithm only the recipient knows, the subverted software would have to solve a computational Diffie–Hellman instance to share a value with the attacker. Two things can undo this protection. The first is bilinear pairings, the same linearity that lets one signature be stretched into forgeries. The second is public key replacement in certificateless systems, where an attacker who installs a key of known discrete logarithm restores the fixed base. We propose to prove this picture, use it to build a pairing-free certificateless KEM whose base is hash-bound to the identity, and test it with symbolic attack search and implementations.

Core Claim

Call a KEM recipient-bound if every group element in its ciphertext has the form $r\cdot B$, where $B$ is a recipient-specific base. Write $B = bP$, where $P$ is the public generator and $b$ is known only to the recipient. Suppose the subverter's public key is $Z = zP$. The planted routine knows $r$, $B$ and $Z$, and needs to compute a value $V$. The subverter knows $rB$, $z$ and the public values, and needs to compute the same $V$. In a group without pairings, producing such a matching $V$ amounts to computing $zB$ from $zP$ and $bP$, which is computational Diffie–Hellman.

In a group with a pairing $e$, the bridge is trivial. The routine computes $e(B,Z)^r$, the subverter computes $e(rB,P)^z$, and the two are equal. Identity-dependent pairing KEMs therefore remain chain-subvertible no matter how the base is chosen. This mirrors the ratio-scaling breaks of single signatures in On the security of an enhanced signature scheme and Practical certificateless short signature scheme. Those papers show that pairing linearity lets one observed signature be rescaled by $H(m^*)/H(m)$. Here the same linearity lets the attacker move a shared secret across bases.

In certificateless cryptography, the private key is split between a partial key issued by a Key Generation Center (KGC) and a user-chosen secret value. There are no certificates, so a "Type I" attacker can replace a user's published key. If the base is simply $B = X + R$, with $X$ the user key and $R = dP$ the KGC-issued partial public key, the attacker can set $X = kP - R$. That makes $B = kP$ with $k$ known, and chaining is back. Replacement alone does not let the attacker decrypt, because decryption still needs the partial key $d$. Subversion alone also does not. Together they give full retroactive decryption. That is the interaction Gap 1 of the research file flags as unstudied.

Our construction blocks this with a hashed base,

$$B = H(\mathrm{ID}, X)\cdot X + R,$$

where $H$ maps to scalars. For an honest key $X = xP$, the recipient's base secret is $b = H(\mathrm{ID},X)\,x + d$, and the KGC does not know it because it does not know $x$. A replacer who wants $B$ to have a known discrete logarithm must find an $X$ that solves a self-referential hash equation. Modeling $H$ as a random oracle, that is as hard as finding the discrete logarithm of $R$.

This repurposes the hash binding that Certificate-based Signatures Revisited used against "Super Type I" replacement of signature keys, here as a defense against subversion. The encapsulation sends $C = rB$ and derives $K = H'(rP, \mathrm{ID}, X, C)$. The recipient recovers $rP = b^{-1}C$. Placing $\mathrm{ID}$, $X$ and $C$ inside the key derivation blocks Tian et al.'s Attack II analogue, in which a ciphertext would be rescaled from one identity to another.

The scope is deliberately narrow. Recipient binding defeats coin-chaining attacks, the class that gives two-ciphertext key recovery. It cannot stop generic bias attacks, in which subverted software rejection-samples coins until a few output bits leak. Those apply to any randomized scheme. The claim is therefore quantitative: recipient binding should push the attacker from two ciphertexts per key to the bias regime, costing on the order of $\lambda/\beta$ ciphertexts for a $\lambda$-bit key at $\beta$ leaked bits each, while leaving statistical traces. That figure is our expectation from simple bit-counting, not a reported result. Per-recipient trapdoors, meaning precomputed $zB$ for a known target list, also remain possible. We will measure how much state that requires rather than claim immunity.

Research Program

The theoretical part has three results. First, we formalize "coin-chaining subversion" as an extension of the universal-decryptability and key-pseudorandomness properties of Subvert KEM to Break DEM. We then prove, in the generic group model with random oracles, that recipient-bound KEMs in pairing-free groups resist it under computational Diffie–Hellman. Second, we prove the pairing negative result as a general attack against any identity-dependent pairing KEM. Third, we prove that the hashed base resists combined replacement and subversion, and that the scheme is IND-CCA secure after a standard transform against both Type I attackers (key replacers) and Type II attackers (an honest-but-curious KGC). The reductions will check explicitly that the simulator never aborts on valid queries under replaced keys. That is the soundness flaw On the Security of an Efficient and Robust Certificateless Signature Scheme for IIoT Environments found in a published proof.

The mechanical part builds a catalogue of KEMs in Tamarin, which supports Diffie–Hellman and bilinear-pairing equational theories. The catalogue covers hashed ElGamal, Kurosawa–Desmedt, Cramer–Shoup, a Boneh–Franklin-style certificateless KEM, a Sakai–Kasahara-style identity-based KEM, the unhashed base $X+R$, and our hashed base. For each scheme, Tamarin searches for a chaining subversion, with and without a key-replacement oracle. This follows the precedent of How to Wrap it up, which used Tamarin to find and exclude key-exposure paths in PKCS#11. The prediction is falsifiable. Every fixed-base and pairing-based scheme should yield an attack trace. The unhashed certificateless base should yield one only when replacement is allowed. The hashed base should yield none.

Baselines

The naive reference point is hashed ElGamal with Chen et al.'s chaining subversion implemented as described. The strongest existing result on this question is the attack itself. Subvert KEM to Break DEM reports recovering a session key "from just two successive ciphertexts" against Cramer–Shoup, Kurosawa–Desmedt and related KEMs. We reimplement that attack on the same schemes, verify the two-ciphertext figure, and then run the identical attacker code against each recipient-bound variant. Beating it means that no chaining attacker within the same software budget recovers a key at better than random-guess rate, and that the best remaining attack, generic biased sampling, needs at least tens of ciphertexts per key and fails a chi-square uniformity test on ciphertext bits at a fixed false-alarm rate.

Two ablations isolate the key ingredient. The first uses the unhashed base $B = X + R$, which separates the effect of recipient dependence from the effect of hash binding. The prediction is that it is secure without replacement and fully broken with replacement. The second is a "hash the public key into the key derivation only" variant. It keeps a fixed-base ciphertext $rP$ but derives $K = H(\ldots, X)$, and tests whether binding inside the key derivation, rather than in the ciphertext base, is enough.

On efficiency, the comparison points come from the file. Efficient Certificateless Authentication and Key Agreement (CL-AK) for Grid Computing reports zero on-line pairings. An Attack on a Certificateless Signature Scheme reports that its proof-of-possession repair doubles verification from two pairings to four. All schemes are timed with MIRACL on the Raspberry Pi 3 B+ and Intel Core i7 setup used by SUSIC, which reports about 22.6 ms device-side and about 12.1 ms controller-side for its protocol. Every scheme uses the same curve security level and the same code paths. Our target is device-side encapsulation in the same range, with no pairings.

Why not just…?

Why not just hash the recipient's public key into the session-key derivation? The subverter knows the public key too. Hashing it into $K$ changes nothing about the subverter's ability to compute $z\cdot rP$ from a fixed-base ciphertext. This is exactly the second ablation. We expect it to stay at two-ciphertext recovery. If it does not, our core claim is wrong in an informative way.

Why not just use certificates and ephemeral Diffie–Hellman? Certificates stop key replacement, and ephemeral exchanges stop retroactive decryption after a long-term key is stolen. But an ephemeral share $rP$ is itself a fixed-base element, so a subverted coin generator can chain through it just as Chen et al. do. Our analysis predicts that subverted ephemeral Diffie–Hellman is chain-vulnerable, and we include it in the Tamarin catalogue to check. Certificate overhead on constrained devices is a separate cost, noted in Certificate-based Signatures Revisited.

Why not just put a re-randomizing device between sender and network? An external party that refreshes ciphertext randomness is the most serious competitor, because it also defeats bias attacks, which our scheme does not. We found no reported result on Lacuna for such re-randomizers applied to these KEMs. This approach needs a trusted extra party. Our ciphertexts $rB$ remain publicly re-randomizable as $C + r'B$, so the two approaches are complementary rather than exclusive. We will state that a re-randomizer is required if bias-attack resistance is needed.

Why not just require proof of possession on public keys? Proof of possession stops replacement, but it does not touch subverted coins under an honest key. Subvert KEM to Break DEM attacks legitimate keys. It also costs extra pairings, two to four in An Attack on a Certificateless Signature Scheme. Our hash binding gets replacement resistance at the cost of one scalar multiplication.

Why not just use an identity-dependent pairing KEM? This is the negative result we expect to prove. Bilinearity gives the subverter $e(B,Z)^r = e(C,P)^z$. The Tamarin runs and an executable attack will show whether this is right.

Proposed Experiments

The decisive checks come from three sources. The first is the Tamarin catalogue, where attack traces should appear exactly where predicted. The second is executable attacks that measure ciphertexts per recovered key across all schemes. The baseline is Chen et al.'s reported two, and our prediction is "chaining impossible, bias-only" for the hashed base. The third is a combined-adversary experiment on the unhashed certificateless base, where replacement plus subversion should succeed although neither succeeds alone.

As the retroactive-decryption measure, we record 10,000 hybrid-encrypted messages per scheme under subverted software and report the fraction of DEM payloads the attacker decrypts afterwards. For the bias attacks, we report key-recovery cost against detection rate. MIRACL timings and operation counts complete the efficiency comparison.

If the hashed base yields a chaining trace in Tamarin, or a working attack in code, the proposal fails on its central claim.