Re: beware: being old sucks

[Seth David Schoen via NANOG <nanog () lists nanog org>]

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.
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/DAWB6W4JWRC54OJRT4XRSQZEPS2UWCJJ/