[dns-operations] [Ext] Obsoleting 1024-bit RSA ZSKs (move to 1280 or algorithm 13)

[Viktor Dukhovni]

On Wed, Oct 20, 2021 at 05:15:25PM +0000, Paul Hoffman wrote:

> > https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002 
> > 
> > the cost of factoring 1024-bit keys at ~200x more is now conservatively
> > 0.54M core years or less given better optimised algorithms, parallel
> > attacks on multiple keys, ...
> 
> The word "conservatively" is misused here. You have no way of
> estimating whether "better optimised algorithms" or "parallel attacks
> on multiple keys" will ever happen, and even if they do, how much or
> little they will improve the NFS algorithm.

I should perhaps have been more clear, I meant a conservative *upper*
bound.  The cost could be much lower, but there's no public information
on that.

> > While 0.54M core years is not cheap, it is plausibly within reach and
> > attacks only get better.
> 
> The word "plausible" carries a lot of weight here. It is indeed
> possible that a state actor has the resources to break short-lived
> 1024-bit RSA ZSKs. The question is why someone who controls that much
> computer power would want to mount that attack, which has very limited
> value to such a state actor, as compared to using it to break other
> 1024-bit RSA keys that were used for encrypting material of interest.

Well, as I noted on "mattermost", there 607k RSA 1024-bit ZSKs that have
not been rolled in 4 years.  I admit that few if any are likely targets,
but the safety margins (as it seems you agree) are rather narrow.

> > The cost of attacking 1280-bit RSA with GNFS is ~90k times the cost of
> > the 829-bit RSA-250 challenge, or ~24M core years.
> 
> This statement also makes guesses about scaling that cannot be
> supported by the current data. It also makes it sound like an attacker
> who could pull together a huge computing system for 1024-bit keys
> could not expand that system by 50x. In the cryptographic world, 50x
> (about 5 bits of effective strength) is considered a negligible
> difference.

You lost a factor of 9, the work-factor ratio from 1024-bit to 1280-bit
keys is ~450 not ~50.  That's almost 9 bits, and while it is as you note
a narrow margin, when were' looking at the edge of what's possible and/or
cost-effective, a factor of 450 is *significant* if not comforting.

> > moving to 1280-bit RSA is a substantially worthwhile improvement,
> 
> The word "substantially" is unsupported, particularly given that
> cryptographers only look at jumps of maybe 32 bits of effective
> strength as interesting.

I disagree, see above.  Of course it would be super-peachy if all
operators also rolled their ZSKs regularly.  Sadly, that's not yet
current practice.

> > and with reasonable key rotation
> > (say every 90 days), attacks using publicly known techniques appear
> > likely out of reach (spin ~100M cores for 90 days in the hope of
> > cracking one key just before it is replaced).
> 
> This misstates the value of breaking ZSKs. Once a ZSK is broken, the
> attacker can impersonate the zone only as long as the impersonation is
> not noticed. Once it is noticed, any sane zone owner will immediately
> change the ZSK again, thus greatly limiting the time that the attacker
> has.

Yes, this is true, and the fact that DNS keys are authentication-only
and no longer relevant once no longer published, also reduces the
incentives to attack these, rather than find a softer and/or
higher-value target.

So sure, the sky's not falling, *but* I still think that the evidence
supports moving from 1024-bits to 1280-bits and paying more attention
to regular key rollovers.

> In summary, it is fine to propose that software default to issuing
> larger RSA keys for ZSKs, but not with an analysis that makes a lot of
> unstated guesses. Instead, it is fine to say "make them as large as
> possible without causing automatically needing TCP, and ECDSA P256 is
> a great choice at a much smaller key size". 

Yes, but I think the numbers do lend support to making the change.

-- 
    Viktor.