In traditional public key cryptography, digital certificates act as the bedrock of trust. A Certificate Authority (CA) signs a certificate to bind a user’s identity to their public key, ensuring that an adversary cannot simply substitute their own key to impersonate a legitimate user. However, managing certificates introduces heavy infrastructure overhead and complex revocation lists.
To bypass this complexity, researchers developed identity-based and certificateless cryptographic systems. In these frameworks, public keys are either derived directly from a user's identity (like an email address) or generated without a traditional certificate. But eliminating certificates introduces a profound vulnerability: if a verifier does not have a certified guarantee that a public key belongs to a specific user, what prevents an attacker from replacing that public key with a malicious one?
This core tension gives rise to public key replacement attacks (and their close relative, identity substitution attacks). When a cryptographic scheme fails to mathematically bind a user's identity, secret keys, and public parameters together, an adversary can manipulate the underlying algebra to forge valid signatures.
The Mechanics of the Balancing Act
To understand why a public key replacement attack works, we must look at how verification equations function. In a typical digital signature scheme, verification relies on an algebraic equation where the signature and the public key must balance out.
In a public key replacement attack, an adversary swaps a user's legitimate public key with a crafted value that they control. As Cao et al. demonstrated, if the verification logic does not enforce a strict mathematical dependency between the user's private secret and their public key, this substitution allows the attacker to bypass authentication entirely.
Legitimate Flow:
[Identity + Secret] ──> [Valid Signature] ──> Verified via [Legitimate Public Key]
Replacement Attack:
[Adversary] ──> [Crafted Public Key] ──> [Manipulated Signature] ──> Equation Balances!
The attack succeeds because the adversary manipulates the signature components to balance the verification equation against the fake key. As Yang et al. showed in their analysis of schemes designed for Industrial IoT environments, an attacker does not need to know the user's actual private key. Instead, they select a malicious public key specifically designed to cancel out the unknown variables within the verification equation. This algebraic loophole allows unauthorized parties to achieve universal forgery—generating valid signatures for any arbitrary message after observing minimal legitimate network traffic, a vulnerability exposed in multiple systems by Zhang et al..
Identity Substitution via Public Key Scaling
In identity-based systems, the public key is tightly coupled with an identity string. However, if the verification process exhibits algebraic malleability, a different flavor of this vulnerability emerges: the identity substitution attack.
This attack relies on the linear properties of modern cryptographic primitives, such as bilinear pairings. As Tian et al. exposed, if a system lacks a non-malleable proof or a trusted binding from a Private Key Generator, an attacker can intercept a single valid signature and mathematically scale both the signature and the public key by a specific scalar ratio.
Because the underlying pairing equations are homogeneous or linear in their exponents, this scaling propagates perfectly through the verification logic. In a parallel analysis, the authors (Tian et al.) explained that this allows an adversary to morph a signature meant for Identity A into a valid signature for an entirely different Identity B. The verifier accepts the forgery because the mathematical relationship between the scaled key and the scaled signature remains internally consistent, even though the central authority never authorized that public key for the new identity.
Designing for Strict Mathematical Binding
The recurring breakdown across these schemes highlights a fundamental rule of certificate-free cryptography: omitting a certificate requires replacing its structural trust with strict mathematical binding.
As Chen et al. noted, while some forms of public key substitution are inherent to specific trust models (such as a compromised Certificate Authority issuing fraudulent certificates), external adversarial substitutions are entirely preventable. One standard mitigation is enforcing a "Proof of Possession" (PoP), requiring users to prove they hold the private key corresponding to a public key before it can be used.
Ultimately, to withstand key replacement, a cryptographic scheme must ensure that the user's identity, the public parameters, and the signature components are cryptographically locked together. As explored by Wu et al., if any component can be substituted or scaled independently without breaking the algebraic balance of the verification equation, the system remains vulnerable to forgery. Secure alternatives, such as the short proxy signature scheme proposed by Huang et al., achieve security by ensuring that dishonest participants or delegators cannot manipulate public parameters to impersonate other entities, effectively neutralizing the algebraic flexibility that substitution attacks rely upon.
Key Foundational Work
An Attack on a Certificateless Signature Scheme (2006) — contributed 4 concept elements to this direction.
Comment on the Public Key Substitution Attacks (2005) — contributed 1 concept elements to this direction.
A Short Proxy Signature Scheme: Efficient Authentication in the Ubiquitous World (2005) — contributed 1 concept elements to this direction.