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).