brent saner via NANOG writes:
This happens. Which seems to be a suretell sign that IOS appears to indeed be authenticating only on the *MD5 fingerprint* of the key. Which would reduce an RSA 1024 key's strength, *laughably weak* in today's standards, to a fixed space of *only 16 bytes/128 bits* (the length of an MD5 hash) instead of 128 bytes/1024 bits. That's a difference of *1048576* combinations versus *16384*. The difference, of course, is more stark with stronger keys (for instance, RSA 4096: 16777216 vs 16384)
Comparing the strength of asymmetric keys to the strength of symmetric keys is subtle, because they're not expected to be subject to exactly the same kinds of attacks. You're right that verifying against the public key's MD5 fingerprint would enable a new kind of attack (generating about 2¹²⁸ keypairs to find one that matches the hash), but on the other hand the amount of work required to breaking the original RSA-1024 key directly is less than 2¹⁰²⁴ steps. The factors p and q of the modulus are probably each around 2⁵¹², and successfully finding one factor is enough to recover the whole secret key. In any case, the factorization method used is likely to be much faster than brute force search. The GNFS algorithm has a complicated runtime, but it's still subexponential in the size of the number to be factored (so, sublinear in the number to be factored itself). The best factorization result announced so far is RSA-250 https://en.wikipedia.org/wiki/RSA_numbers#RSA-250 where the factors are about 414 bits long, with the modulus 829 bits long. The project took "approximately 2700 CPU core-years", which is a lot, but clearly didn't require 2⁸²⁹ or even 2⁴¹⁴ steps! NIST has had a formula for matching asymmetric key strength to symmetric key strength: https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths According to this formula, 1024-bit RSA is considered equivalent in security to 80-bit symmetric ciphers. If that's right, authenticating against the MD5 hash of the RSA key is not expected to make the system weaker against known attacks! (Another way of saying this is that NIST anticipates that directly breaking the original 1024-bit key would still be the easiest known method of attack -- it's considered to be an easier computation than an MD5 preimage.) I'm sure NIST would still not recommend it, because there's no reason to give attackers more kinds of attacks rather than fewer, and because some attacker could still conceivably find mathematical tricks that lower the cost of finding the MD5 preimage.