Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

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

share|improve this answer
    
You can ignore the hashing step, it doesn't affect security. An attacker wins if he finds $a$, he doesn't care about finding a $k$. –  CodesInChaos Aug 23 '12 at 8:03
    
@CodesInChaos: The question was about creating a key pair which looks similar, and this contains a $k$. Of course, the $a$ itself is sufficient for signing, and depending on the actual goal it might be enough to find such one. –  Paŭlo Ebermann Aug 24 '12 at 17:21
1  
I believe the root question is: "Can an attacker impersonate a known public key by creating a keypair with a similar looking public key, for which he can execute private key operations such as signing or diffie-hellman." The actual representation of the private key is irrelevant. –  CodesInChaos Sep 6 '12 at 13:47
add comment

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:

enter image description here

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

share|improve this answer
1  
Doesn't your algorithm assume that the attacker can easily solve the discrete logarithm problem on this elliptic curve? Elliptic curves are essentially logarithmic, so your "division" is actually discrete logarithm. The equivalent of A=aB on an elliptic curve is A=g^a using the multiplicative group modulo a prime. –  CodesInChaos Aug 23 '12 at 6:37
    
Can you fix the division part? The rest of the answer contains a nice explanation why the attacker doesn't care about k, but making it sound like DL is easy is highly misleading. –  CodesInChaos Aug 25 '12 at 10:02
    
@Codes: Yep, you're right. Let me see if there's a better way to go about it, or if I just need to re-word that entire section. –  B-Con Aug 25 '12 at 15:37
    
Your talking about "multiplicate inverse" is still weird. AFAIK there is no operation that multiplies two points on a curve. There is only an operation that multiplies a scalar with a curve point. If you look at the analogous operation in a finite field $B^{a'}=A'$, you can't find an inverse element for $B$ either. –  CodesInChaos Sep 6 '12 at 13:38
    
Thanks, I missed that somehow in the previous edit. I'm not sure why I thought "multiplicative inverse" was the right way to word that, originally. –  B-Con Sep 7 '12 at 22:36
show 2 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.