What's the state of the art in factorization?

Victor Duchovni Victor.Duchovni at morganstanley.com
Tue Apr 20 21:40:35 EDT 2010

On Tue, Apr 20, 2010 at 08:58:25PM -0400, Thierry Moreau wrote:

> The DNS root may be qualified as a "high valued" zone, but I made the 
> effort to put in writing some elements of a "risk analysis" (I have an 
> aversion for this notion as I build *IT*controls* and the consultants are 
> hired to cost-justify avoiding their deployments, basically -- but I needed 
> a risk analysis as much as a chief financial officer needs an economic 
> forecast in which he has no faith.) The overall conclusion is that the DNS 
> root need not be signed with key sizes that would resist serious brute 
> force attacks.
> See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:C. 
> (document annex C. Risk Analysis Elements for DNSSEC Support at the Root).

This conclusion is arrived at in a rather ad-hoc fashion. One can equally
easily reach opposite conclusions, since the majority of administrators
will not configure trust in static keys below the root, and in many
cases domains below the root will have longer keys, especially if the
root keys are not conservative.

Sure, cracking the root will not be the easiest attack for most,
but it really does need to be infeasible, as opposed to just
difficult. Otherwise, the root is very much an attractive target
for a well funded adversary. Even if in most cases it is easier to
social-engineer the domain registrar or deliver malware to the
desktop of the domain's system administrator.

> By the way, state-of-the-art in factorization is just a portion of the 
> story. What about formal proofs of equivalence between a public key 
> primitive and the underlying hard problem. Don't forget that the USG had to 
> swallow RSA (only because otherwise its very *definition* of public key 
> cryptography would have remained out-of-sync with the rest) and is still 
> interested in having us adopt ECDSA.

EC definitely has practical merit. Unfortunately the patent issues around
protocols using EC public keys are murky.

Neither RSA nor EC come with complexity proofs.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list