# What is the malicious potential of a key-substitution-attack?

What is the idea behind a key-substitution-attack?

We start from a given pair of message $m$ and signature $s(m)$. The signature can be verified by anybody in possess of the public key $y$:

$v(m, s, y)= ok$

Now, by some mathematical magic (details are not relevent for the moment), an attacker shall be able to generate a new public key $\bar y$, so that

$v(m, s, \bar y)=ok$

However, I cannot identify the malicious potential of that attack: The recipient, getting $(m, s)$ will still use the original public key $y$, to verify $(m, s, y)$, so what is going to be compromised from the attacker just having such key $\bar y$ ?

As is, the attack seems rather pointless. But one malicious potential is that because $\bar y$ allows to successfully verify a genuine message $(m,s)$, the verifier might grow trust in it and use $\bar y$ instead of $y$ in order to verify other messages. If we assume this, practical issues could arise:

1. That the attacker can somewhat find $(\bar m,\bar s)$ (with $\bar m\ne m$ and/or $\bar s\ne s$ (depending on definition of security of a signature system) so that $v(\bar m,\bar s,\bar y)=\text{ok}$ ; $(\bar m,\bar s)$ will be accepted by a the verifier and in effect is a practical forgery.
2. That the legitimate verifier handed some genuine $(m',s')$ pair (such that $v(m',s',y)=\text{ok}$, and $m'\ne m$) finds that $v(m',s',\bar y)\ne\text{ok}$, and rejects the valid message; this in effect is a denial of service.

In many signature systems where the question's attack is possible, 1 or/and 2 is possible.

Elias suggests that if making a $\bar y$ as in the question is possible, then the signature scheme looses non-repudiation. That's an interesting point of view, but mine is that the definition of non-repudiation is a convention between parties, and that it would be a slippery slope (and an unusual one) to allow exhibition of $\bar y\ne y$ such that $v(m,s,\bar y)=\text{ok}$ to be a valid reason to stop accounting the legitimate holder of the private key matching the public key $y$ as responsible for having signed $m$ whenever $(m,s)$ becomes publicly available and $v(m,s,y)=\text{ok}$.

Two technical reasons are that, without breaking the established definition of security of a signature scheme, it could be that $\bar y$ was produced

• from $y$ and/or $s$, by anyone;
• or additionally with knowledge of the private key for $y$, e.g. by the legitimate key holder wanting to repudiate his/her approval of $m$.

Thus is we allowed what Elias proposes, we'd need to use signature schemes with a stronger and more complex definition of security than we do, for no benefit that I can discern beyond preventing what is explained in the first part of the answer.

It seems like if this is possible the signature scheme loses non-repudation. As there is now a second key that could have been used to sign the message.

However, I doubt that this would actually work. The magic math will probably not allow targeting somebody else's key and therefore it must always have been signed by the known legitimate key anyway.

• +1 for raising an interesting opinion; but my view is that at least in RSA as practiced, we must not (and do not) allow what's considered in the question to break non-repudiation. For example, $v(m,s,(3N,e))=\text{ok}$ holds with odds about $1/3$ if $v(m,s,(N,e))=\text{ok}$, and signature $s$ was produced from random $m$ by a deterministic scheme, or by an honest signer in a randomized scheme. By an easy extension, a dishonest signer with public key $(N,e)$ can sign so that some of his/her signatures will verify with $(N',e)$ and $N'$ 32 more bits than $N$. There are many more ways !
– fgrieu
Jun 13, 2017 at 15:09
• @fgrieu interesting. So why does that not break non-repudiation? Jun 13, 2017 at 20:59
• We need a definition of non-repudiation in order to decide what breaks it. My view is that non-repudiation is when parties agree that they are liable to the consequences of having approved a message whenever anyone can exhibit a signature of that message verifying against their public key; it is a convention between parties, not a property of the signature scheme. In RSA at least, adding "except if it can be exhibited a different $(N',e')$ that verifies the signature" is wrong; and I'm not ready to approve further adding "with $\gcd(N,N')=1$" without a good argument this is without leak.
– fgrieu
Jun 13, 2017 at 21:38
• Okay, but don't you agree that this convention between parties is not a good idea if many people could have produced a certain signature. :) Jun 13, 2017 at 22:10
• The convention would be senseless if other people could have produced a signature $s$ for message $m$ verifying with $y$ (and $\bar y\ne y$) without knowledge of the private key for $y$ (other than by asking the holder of $y$ for signature of message $m$); which matches a common definition of signature security. But exhibition of $\bar y$ as in the question would be indication that $s$ is forged only if we could rule out that $\bar y$ was derived from $y$, $s$ and/or the private key for $y$.
– fgrieu
Jun 14, 2017 at 7:07

It depends on the signature-scheme, in detail: on the verification. Not every single signature-scheme has a malleability for that attack.

This answere will be split in describing ElGamal, then pointing out the malicious step and conclude, why it is malicious.

# ElGamal

Preset

Let us keep an eye on the ElGamal Signature Scheme . We will randomly choose a secret $$x\in \{2, ..., p-3\}$$, where $$p$$ denotes a "large" prime. We then will compute the public key $$y=g^x\bmod p$$. $$H$$ describes a hashing function with integer output.

Signature

Input: (g,p,x)

Output: (r,s)

Algo:

1.) Choose a (random) coprime $$k\in\{2, ..., p-2\}$$ (coprime means: gcd(p,k)=1)

2.) Compute $$r\equiv g^k \bmod p$$

3.) Compute $$s\equiv (H(m)-xr)k^{-1} \bmod (p-1)$$ (Here you see, why k has to be coprime, otherwise $$k$$ is not invertible and you can't compute $$k^{-1}$$.)

4.) If $$s\neq0$$ publish $$(r,s)$$ as the signature of the message $$m$$.

Verification: Check, if the signing output tupel $$(r,s)$$ is valid.

Input: (r,s, g, p, y) sometimes $$m$$ is left or added. Keep in mind, you need the message, since all "keys" are depending on that. (Sence of signature :D )

Output: bool 0 or 1.

Algo:

1.) Check if r and s are valid, so if $$r\in\{1,...,p-1\}$$ and $$s\in\{1,...,p-2\}$$.

2.) Check if $$g^{H(m)} \equiv y^rr^s\bmod p$$

Note: I'd chose $$(r,s)$$ in analogous to Wikipedia. You provided the Signature as $$s(m)=:\overline{s}(m)$$. The connection is made by $$\overline{s}(m)=(r(m),s(m))$$

# Malicious

The 2nd step is the malicious one. Lets fill in, how we computed $$r, s$$ and $$y$$. You will get:

$$y^rr^s = g^{xr}\cdot g^{k(H(m)-xr)k^{-1}} = g^{xr +H(m) - xr} (\bmod p)$$

Note: You can see, why $$k$$ has to be invertible.

Since your question does not have the mathematical background, we will further discuss the key-substituion.

# Key Substitution

The first question to answere is: How do we have to compute another key $$\overline{k}$$, so that the verification-step will output "true". As you might expected, you could use every $$\overline{y}=y^{Z}$$ where $$Z\equiv 1 \bmod (p-1)$$, since the modular arithmetics is bilinear in addition and multplication. ($$p-1=\phi(p)$$ if p is a prime, as in this case.) But note, this "attack" can easily be prevented, by checking $$y. I do not have any more sparetime to add more attacks like this :( Anyone feel free to add and correct. :)

# Sources

Check out this paper for a concrete attack using key substitution on a real (though obscure) protocol. It also gives the "mathematical magic" of substitution attacks against RSA and ECDSA:

https://eprint.iacr.org/2019/130

• Welcome to Cryptography.se We rather prefer some details of the article. What you wrote is almost a link only answer that is going to be converted into a comment if you don't change into more details. Thanks. Oct 19, 2022 at 21:04

As to my knowledge, a real key substitution attack (where the malicious key gives the identical signature as the original key) is not a feasible attack with robust algorithms such as 2048+ RSA keys. However, key substitution attacks are possible when use is being made of the key fingerprint, which is often a 8-bit alfa-numerical string. When mapping a 2048 bit key to a 8-bit fingerprint for (visual) verification, it is easy to imagine that one can forge a malicious key that has the same 8-bit fingerprint. To better understand this weakness I will explain a simple MITM attack that exploits this scenario. Attack scenario:

• Bob has a business card with his email address and the 8 bit fingerprint of his 2048 RSA gpg key that he uses for email encryption (or signing). He gives his business card to Alice.
• Eve manages to create a malicious key that has the same fingerprint as Bob's key.
• She creates an evil twin of Alice's favorite key server and lists the malicious key under Bob's email address.
• Alice encrypts here mail with the malicious key and sends it. Eve intercepts the message.
• Eve decrypts the message of Alice, encrypts it with Bob's real key and sends it to Bob
• Bob signs his message with his key and sends it away. Eve intercepts the message.
• Eve signs the message with the malicious key and sends it to Alice.

Therefore you should never trust a key fingerprint to verify a key or its owner.

• This may be more relevant for other secure schemes with different properties such as IIUC schnorr. Mar 20, 2018 at 5:00