# How hard is it to generate a partial RSA fingerprint collision?

When I use SSH to log into a new system, I get asked to verify that the fingerprint (a 32 hex digits string) of the hosts's RSA key is correct. How much if it must I actually compare (by hand/eye) to make it unfeasible for someone to man-in-the-middle me? Assume the adversary has a budget of a few thousand dollars.

Clarification: I'm assuming that a human will never hand verify that the fingerprint printed by there SSH client is in fact exactly the same as the key on there server, but rather (assuming they are more diligent than the average human) will read a limited prefix and/or suffix. If we assume they will read the first and last 4 digits then you should be able to create a collision of just those digest in $2^{(4+4)4}=2^{32}$ guesses.

The question then becomes; how many digits can an attacker expect to match with the budget described above?

-
I don't know how much time it would take to compute such a table, but it is heuristically highly likely that there are lookup tables of 21.1 GiB for 8 hexadigits and 6.3 TiB for 10 hexadigits that make the rest of the computation very fast. $\;$ –  Ricky Demer Jun 19 '13 at 1:44
Reading between the lines, anyone with more than a passing interest could forge 10-12 selected hex digits of a fingerprint. So if you are going to even bother looking you had better check at least 20. –  BCS Jun 19 '13 at 15:56

As far as we know, it is totally infeasible for anyone to create an RSA private key with a public key that has a specific 32 character fingerprint. This remains true if you give the adversary a budget of a few billion dollars; the best approach for an adversary would be to try to break in and steal (or purchase) the private key (and the second best approach would be to factor the existing RSA key to obtain the private key, rather than trying to create a second one).

SSH uses MD5 to do its fingerprinting; the best way known to find preimages is just to go through a huge number of images, and hope to stumble across one that happens to hash into the value you're looking for; for this to work, we would expect to involve testing about $2^{128}$ images before we get lucky. We might get lucky earlier than that; however we're more likely to hit the lottery than for this procedure to take less than $2^{100}$ trial images; creating and testing this number of RSA keys is completely unthinkable.

On the other hand, if we're looking for a partial match, for example, the first 4 characters and the last 4 characters (total of 32 bits), this changes entirely.

To attack this, we would need to generate and hash an expected $2^{32}$ RSA keys. So, the question is "how realistic would such an attempt be for an attacker?"

Well, the answer is surpising; an attacker can probably do this in a few hours even if he has only one cPU at his disposal.

The immediate obvious objection to this is "it takes me quite a while - hundreds of milliseconds - to generate an RSA key; how can an attacker do it so much faster?".

Well, the answer is that the reason it takes you so long to generate a key is that you actually care that the RSA key is hard to factor, and so you spend a lot of time looking for large primes. Now, it appears likely that an attacker might not actually take so much care that the RSA key he generates is as secure.

Once you stop caring whether the RSA key is actually secure, it becomes a lot faster to generate them; all you need to do is find a bunch of (say) 32 bit primes, and multiply them together in various combinations until he gets a match. Once he has found an RSA public key that matches the parts of the hash he cares about, he knows the factorization of the RSA modulus, and so he can then generate the RSA private key, and he's good to go.

When you look at the inner-most loop of this procedure, it consists of taking a $N-31$ or $N-32$ bit number (of known factorization), multiplying it be a 32 bit prime, and then hashing that product, along with the $e$ value, and then seeing if that hash is partial match to the target.

I haven't tested it myself; it appears plausible that this multiplication and hashing might take a microsecond; if that guess is approximately close, then an attacker could, with a single CPU, find such a partial collision in a few hours.

So, to answer your clarification question: an attacker can easily find a match over 8 digits; he might (by using several CPUs and/or spending more time for the search) be able to find a match over 10 digits. To go much beyond that would appear to require a zombie farm, or an array of FPGAs, or something other way of gaining more computing resources than are available to your average script kiddie.

-
See clarification. –  BCS Jun 18 '13 at 18:20
@BCS: See response to clarification –  poncho Jun 18 '13 at 19:52
If you have money to throw at it, buying time on commercial VM service is a real option. I've heard real stories of academics running GNFS on Amazons S3. At ~0.6 USD/hr (aws.amazon.com/ec2/#pricing) and your guesses, that's $2^{42}$ to $2^{43}$ for 1k cash. –  BCS Jun 18 '13 at 20:20
One could check for small factors to make the innermost loop slightly more expensive. $\hspace{.4 in}$ –  Ricky Demer Jun 18 '13 at 23:58
@RickyDemer: yes, an SSH implementation could do that (actually, something like attempting a Monte Carlo factorization would be cheaper); in practice, they don't. –  poncho Jun 19 '13 at 0:11