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

Question

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$ ?

Answer 1

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.

Answer 2

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.

Answer 3

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 [1]. 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<p$. I do not have any more sparetime to add more attacks like this :( Anyone feel free to add and correct. :)

Sources

[1] https://en.wikipedia.org/wiki/ElGamal_signature_scheme

Answer 4

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

Answer 5

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.