Is it possible to pick your Ed25519 public key?

Question

Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this as hard as solving one of SHA-512 or the discrete logarithm problem?

Answer 1

If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation.

Here's a diagram of how Ed25519 works, note how keys are generated:

(Image source.)

A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 - 11).

To recap the image and slides: The secret is hashed and public key is derived from the "left half" of the hash. The left half is manipulated to be value $a$, which is a bit string with a few conditions. Then $a$ is applied to a curve point $B$ to produce the public key $A$.

The critical thing to note is that the seed's hash output is used in key generation. Apparently implementations differ on what they store as the private key, but the algorithm itself does not need the original secret, only the hash from it. This means that if you control the implementation you use, you can just make up any hash that suits your purposes and you don't need to care what the corresponding secret would be. (This prevents the need to finding any sort of SHA-512 pre-image.) We can use this by working backwards from the desired public key value and deciding what hash value we want.

The goal of this attack is to choose the value of $A$, or to at least choose something very similar to it. Call the new target public key we're trying to build $A'$, then if $A'$ is a valid public key there is an $a'$ such that $a'B = A'$. This reduces to finding the inverse on the elliptic curve, $a' = AB^{-1}$, which is actually the Discrete Logarithm problem and certainly non-trivial to calculate. But if you could find a valid $a'$, you would have everything you need.

As an important side-note, not all values of $a$ are valid in the scheme. See the Ed25519 paper for all restrictions for $a$ (I believe they are all listed on pg 6). There aren't very many restrictions, I think the most restrictive one is that $a$ be divisible by 8 (ie, the low three bits are 0). Assuming you can can calculate the $a'$ from a chosen $A'$, you could just pick random $A'$s until you find one that produces a valid $a'$. This step would prevent you from explicitly choosing your public key, because you have no guarantee that the desired value for $A'$ is valid. You can probably find a valid $A'$ after only a few tries, so just flip a bit here and there in the desired $A'$ and you should be able to find one that works and has a small Hamming distance from the original desired $A'$, which is probably good enough to produce keys that look alike.

If you have $a'$ then you have the public key and you can create a corresponding private key. You can make up a random "right-side" of the SHA-512 hash value and incorporate the new $a'$ to construct the private key.

This all assumes you can control the implementation and solve the necessary discrete logarithm. Regarding the implementation, the NaCl project has a high-speed performance-oriented implementation of Ed25519, and as such it stores as much pre-computed data as possible in the private key. It would allow you to perform this sort of manual crafting of the keys. But in general, with other implementations, you may have no such luck. I would think that for most attacks, the attacker should be assumed to be able to choose the implementation they use.

(Hopefully this is all correct, I hadn't looked at Ed25519 before this.)

Answer 2

The core of the problem is finding a near first pre-image on the function $A = aB$ on an elliptic curve, where $A$ is the public key, and $a$ the private key¹.

For a normal hash function you $ 2^m $ operations to fix $m$ specific bits.² In particular a full pre-image takes $ 2^n $ hash function calls.

A full pre-image on $A = aB$ is equivalent to solving the discrete logarithm problem on that curve. This problem only needs $ 2^{n/2} $ operations, which is something around $ 2^{126} $ for Ed25519³. i.e. much faster than for a hash function, but still prohibitively slow.

Now the interesting question is, if you want to find only $ m < 126 $ matching bits, how much work do you need? And I can't answer that, so this doesn't really answer your question. I know of no way to do this faster than brute-force, but I'm certainly no expert on this matter.

---

¹ The standard implementation of Ed25519 does use a different private key $k$ from which $a$ is derived via hashing, but an attacker would simply skip that step, so we can ignore it. It does not affect security.

² If you don't care about which bits you fix, then the problem becomes a bit easier than $ 2^m $ but it doesn't matter that much.

³ I believe Curve25519 has a small subgroup, reducing security by a few bits, so I assumed a 126 bit security level. A few bits more or less don't matter, especially since one "operation" can be much more expensive for some primitives than for others.

Answer 3

Looking at the Ed25519 paper, it seems that a key pair consists of a private key $k$ (just a $k$-bit string) and a public key $A$, where $A = a · B$ and $a$ is derived from the first half of the hash $H(k)$ ($B$ is the base point of an elliptic curve (or actually a twisted Edwards curve equivalent to an elliptic curve) and $·$ is the scalar multiplication in this curve).

A different private key $k'$ (even if just different by one bit) ought to create a quite different hash $H(k')$, and thus quite likely also different $a'$ and $A'$.

The only way to succeed here would be to brute-force different values for $k'$ and see if the difference between $A$ and $A'$ is below some limit, but that will take quite long (depending on how high you set the difference limit).

Answer 4

I assume from the "fooling a casual visual comparison" in the question that it is actually talking about visual comparison of the fingerprint of the public key. So, absent a full break of Ed25519, even if we had some fancy efficient way to generate public keys with particular structure, an attack still requires a near-second-preimage for the hash used for the fingerprint. (Not a near-collision attack, because it does not benefit the attacker just to generate two similar public key fingerprints; they have to generate a fingerprint that is similar to an existing one for a victim server or servers.)

An ssh fingerprint is an MD5 hash of the Base64-encoded public key. MD5 is a relatively old hash algorithm and there are known attacks better than brute force for collision-resistance and near-collision-resistance. The status of MD5 for near-second-preimage resistance is less clear.

Note that in principle, an attacker might not need a secure or valid public key. So we might think of generating invalid key encodings, or encodings that vary in redundant information that doesn't require us to do a point multiplication per trial, and combining that with a near-second-preimage attack on MD5. In practice I think this is unlikely to be feasible given that Ed25519 key encodings are designed to always represent elements of a group in which discrete log is hard (even if not the intended elliptic curve subgroup), and AFAIK they do not contain redundant information.

That leaves brute force multi-target attacks. Suppose we are satisfied with finding a second preimage for a fingerprint that agrees in k specified bits with any of n target fingerprints. The expected cost of finding one by brute force is 2^k / n hashes. (Note: we don't have to do a full point multiplication for each trial, because it's sufficient to iterate through valid keys by incrementing the secret key and adding the group base to the public key -- so we only need a point addition per trial, and the Base64 encoding and hash, at most.)

If you don't care where the matched bits are, then there are L-choose-k times as many possibilities where L is the hash output size (128 in this case), so the cost is then 2^k / (L-choose-k * n). However, what we're actually interested in is matched hex digits (i.e. groups of 4 bits) rather than bits. To match h such digits in a 16-digit hash, the cost is 16^h / (16-choose-h * n).

To reduce the cost further it may also be beneficial to consider visually similar characters, e.g. 3 and B, as matches, and similar tricks such as allowing transposition.

Also, note that the attacker doesn't necessarily have to choose the same key exchange algorithm. The OpenSSH command-line client displays the key type by default, but other clients may not, and the user might not know what the key type should be. So, if it were somehow easier to generate visual matches for a different algorithm than Ed25519 (either by a constant factor due to less overhead per trial, or to facilitate a faster-than-brute-force near-second-preimage attack on MD5), then they would probably do that, even if targeting the fingerprint(s) of an Ed25519 key or keys.