What's the state of the art in factorization?

Thierry Moreau thierry.moreau at connotech.com
Wed Apr 21 23:19:48 EDT 2010

Victor Duchovni wrote:
> 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.

Do you have a suggestion for a less ad-hoc fashion?

> 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.

For which purpose(s) is the DNS root signature key an attractive target? 
Given these purposes, who are the potential adversaries (Dan Bernstein 
claims that they don't need to be well funded)? I am not really seeking 
an answer, but these question are investigated (indeed in a rather 
ad-hoc fashion) in the above referenced annex.

> 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.

Indeed. And maybe social-engineering the zone signature function comes 
in this category.

You may observe that the DNS root zone signature function is also 
subject to social-engineering attack. This should be a basic concern for 
the DNS root key management procedures, independently for both the 
official DNS root signature and the Intaglio NIC alternative source.

>> 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.

Correct. In this perspective, the Rabin-Williams cryptosystem is 
superior. But nowadays nobody seeks to make this advantage available in 
standardized protocols. This is a fascinating area, ...


- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

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

More information about the cryptography mailing list