What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

2010-07-09 Thread Zooko O'Whielacronx
By the way, the general idea of One Hundred Year Security as far as
digital signatures go would be to combine digital signature
algorithms. Take one algorithm which is bog standard, such as ECDSA
over NIST secp256r1 and another which has strong security properties
and which is very different from ECDSA. Signing is simply generating a
signature over the message using each algorithm in parallel.
Signatures consist of both of the signatures of the two algorithms.
Verifying consists of checking both signatures and rejecting if either
one is wrong.

Since the digital signature algorithms that we've been discussing such
as [1] are related to discrete log/Diffie-Hellman and since an
efficient implementation would probably be in elliptic curves, then
those are not great candidates to pair with ECDSA in this combiner
scheme.

Unfortunately I haven't stumbled on a digital signature scheme which
has good properties (efficiency, simplicity, ease of implementation)
and which is based on substantially different ideas and which isn't
currently under patent protection (therefore excluding NTRUSign).

Any ideas?

[1] http://eprint.iacr.org/2007/019

Regards,

Zooko

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-07-09 Thread Jonathan Katz

On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:


There is some interesting work in public key cryptosystems that reduce
to a *random* instance of a specific problem.

Here is a very cool one:

http://eprint.iacr.org/2009/576


...


Unless I misunderstand, if you read someone's plaintext without having
the private key then you have proven that P=NP!


It is not known, and considered extremely unlikely, that P \neq NP implies 
symmetric-key cryptography, much less public-key cryptography.


The paper you cite reduces security to a hard-on-average problem, whereas 
all that P \neq NP guarantees is hardness in the worst case.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-07-09 Thread Jonathan Katz

On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:


On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote
(on the cryptography@metzdowd.com list):

[2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf


As one of the authors of the above paper, I have an obvious interest in 
this thread. =)



Later I discovered this paper [2] which appears to be an improvement
on that one in terms of performance (see Table 1 in [2]) while still
having a tight reduction to the Computational Diffie-Hellman (CDH)
problem. Strangely, this paper [2] doesn't appear to have been
published anywhere except as an eprint on eprint.iacr.org. I wonder
why not. Is there something wrong with it?


While I don't know of any attack, the proof of security does not appear to 
be correct.


On the other hand, there is one published scheme that gives a slight 
improvement to our paper (it has fewer on-line computations): it is a 
paper by Chevallier-Mames in Crypto 2005 titled An Efficient CDH-Based 
Signature Scheme with a Tight Security Reduction.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

2010-07-09 Thread Zooko O'Whielacronx
On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz jk...@cs.umd.edu wrote:
 On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:

 Unless I misunderstand, if you read someone's plaintext without having
 the private key then you have proven that P=NP!
…
 The paper you cite reduces security to a hard-on-average problem, whereas
 all that P \neq NP guarantees is hardness in the worst case.

I see. I did misunderstand. So although cracking the Lyubashevsky,
Palacio, Segev encryption scheme [1] doesn't mean that you've proven
P=NP, because NP is about worst-case rather than average-case, it
*does* mean that you've solved the subset sum problem for a random
instance. If you can do that for all keys that people use in real life
then you can solve the subset sum problem for almost all random
instances, which seems like it would still be a breakthrough in
complexity theory. If you can do it for only a few keys then this
means that the Lyubashevsky, Palacio, Segev scheme is susceptible to
weak keys.

Is that right?

Anyway, although this is not one, there do exist proposals for public
key crypto schemes where breaking the scheme implies solving a worst
case instance of a supposedly hard problem, right?

Here is a recent paper which surveys several of them (all
lattice-based) and estimates secure key sizes: [2].

None of the signature schemes mentioned therein appear to have the
sort of efficiency that we are used to. For example the ecdonaldp
(ECDSA) signature schemes measured on
http://bench.cr.yp.to/results-sign.html have key sizes on the order of
tens of bytes, where the most efficient digital signature algorithm
described in [2] has key sizes on the order of thousands of bytes.
(And that one is a one-time signature scheme!)

Okay, so I'm still searching for a signature algorithm which has the
following properties (or as many of them as I can get):

1. efficient (signing time, verification time, key generation time,
key size, signature size)

2. some kind of strong argument that it really is secure (the gold
standard would be reduction to a worst-case instance of an NP-complete
problem)

or, if we can't have (2) then at least we want (3) and (4):

3. rather different from ECDSA, so that a breakthrough is unlikely to
invalidate both ECDSA and this other scheme at once
and
4. not known to be vulnerable to quantum computers

and finally but importantly:

4. easy to understand and to implement

Suggestions welcome!

Regards,

Zooko Wilcox-O'Hearn

[1] http://eprint.iacr.org/2009/576
[2] http://eprint.iacr.org/2010/137

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

2010-07-09 Thread Jonathan Katz

On Wed, 28 Apr 2010, Zooko O'Whielacronx wrote:


Anyway, although this is not one, there do exist proposals for public
key crypto schemes where breaking the scheme implies solving a worst
case instance of a supposedly hard problem, right?


Not to worst-case hardness of an NP-complete problem, no. Quite the 
contrary, there has been some body of work showing that a result of this 
sort is unlikely. (Though, as with all things related to complexity theory 
where our state of knowledge is so limited, such a statement must be taken 
wit ha grain of salt. In any case, such a result is well beyond anything 
we can currently prove.)



2. some kind of strong argument that it really is secure (the gold
standard would be reduction to a worst-case instance of an NP-complete
problem)


See above.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Jerry Leichter

On Apr 21, 2010, at 7:29 PM, Samuel Neves wrote:
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.



While EC (by that I assume you mean ECDSA) does not have a formal
security proof, i.e., it is as hard as the EC discrete log, it it much
closer to one than RSA is to factoring. In particular, Pointcheval and
Stern, and later Brown come close to a formal proof for ECDSA [1]
It's perhaps worth pointing out again how little formal complexity  
proves tell you about security.


Suppose we could show that RSA was as hard as factoring.  So?  Nothing  
is really known about how hard factoring is.  At worst, it's NP- 
complete (though that's actually considered unlikely).  But suppose  
*that* was in fact known to be the case.  What would it tell us about  
the difficulty of factoring any particular product of two primes?   
Absolutely nothing.  NP-completeness is a worst-case result.  In  
principle, it could be the case that factoring is easy for numbers  
less than a billion bits long - it just becomes much harder  
eventually.  (I put easy in quotes because it's usually taken to  
mean there's a poly-time algorithm, and that's a meaningless  
statement for a finite set of problems.  *Every* finite set of  
problems has a O(1) time solution - just make a lookup table.)


There are some concrete complexity results - the kind of stuff Rogoway  
does, for example - but the ones I've seen tend to be in the block  
cipher/cryptographic hash function spaces.  Does anyone one know of  
similar kinds of results for systems like RSA?

-- Jerry


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Thierry Moreau

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


Regards,

--
- 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 majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Thierry Moreau

Jerry Leichter wrote:

On Apr 21, 2010, at 7:29 PM, Samuel Neves wrote:
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.



While EC (by that I assume you mean ECDSA) does not have a formal
security proof, i.e., it is as hard as the EC discrete log, it it much
closer to one than RSA is to factoring. In particular, Pointcheval and
Stern, and later Brown come close to a formal proof for ECDSA [1]
It's perhaps worth pointing out again how little formal complexity 
proves tell you about security.


Suppose we could show that RSA was as hard as factoring.  So?  Nothing 
is really known about how hard factoring is.  At worst, it's NP-complete 
(though that's actually considered unlikely).  But suppose *that* was in 
fact known to be the case.  What would it tell us about the difficulty 
of factoring any particular product of two primes?  Absolutely nothing.  
NP-completeness is a worst-case result.  In principle, it could be the 
case that factoring is easy for numbers less than a billion bits long 
- it just becomes much harder eventually.  (I put easy in quotes 
because it's usually taken to mean there's a poly-time algorithm, and 
that's a meaningless statement for a finite set of problems.  *Every* 
finite set of problems has a O(1) time solution - just make a lookup 
table.)


There are some concrete complexity results - the kind of stuff Rogoway 
does, for example - but the ones I've seen tend to be in the block 
cipher/cryptographic hash function spaces.  Does anyone one know of 
similar kinds of results for systems like RSA?

-- Jerry


E.g. Koblitz, Neal; Menezes, Alfred, Another Look at ``Provable 
Security'', Cryptology ePrint Archive: Report 2004/152, available at 
http://eprint.iacr.org/2004/152.pdf.



- Thierry Moreau

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Florian Weimer
* Thierry Moreau:

 For which purpose(s) is the DNS root signature key an attractive
 target?

You might be able to make it to CNN if your spin is really good.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Thierry Moreau

Florian Weimer wrote:

* Thierry Moreau:


For which purpose(s) is the DNS root signature key an attractive
target?


You might be able to make it to CNN if your spin is really good.



Thanks for this feedback.

No, no, and no.

No, because I asked the question as a matter of security analysis 
methodology. My conclusion is that no purpose justifying an attack on 
the overall DNSSEC scheme particularly threatens the DNS root.


No, because while someone else's answer might be formulated based on 
non-rationale anti-USG paranoia (leading to a nice media story), the 
pervasive USG influence in the DNSSEC key management has very different 
impacts, the foremost one being that the DNS root may actually be signed 
soon (hey, great!).


No, because I don't want to handle the trouble of high visibility in a 
field where the public relations are already mixing up things (e.g. .org 
is signed but a registrant can't have a secure delegation for a .org 
domain as of today).


Caveat: I stopped volunteering information about specific elements of 
official DNSSEC root key management which might be criticized. It is 
time for the DNS root signature project to move forward. Also, the 
Intaglio NIC project has no value unless the official DNS root holds 
secure delegations.


But even without this self-restraint, there would be no spin for a CNN 
story. Dedication to good cryptographic key management is squarely dull 
and boring for a typical person.


Regards,

--
- 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 majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Florian Weimer
* Thierry Moreau:

 Florian Weimer wrote:
 * Thierry Moreau:

 For which purpose(s) is the DNS root signature key an attractive
 target?

 You might be able to make it to CNN if your spin is really good.

 But even without this self-restraint, there would be no spin for a CNN
 story. Dedication to good cryptographic key management is squarely
 dull and boring for a typical person.

I was referring to news of a breach (whether through factoring or
otherwise), not the key management procedures as such.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Zooko O'Whielacronx
On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter leich...@lrw.com wrote:

 There are some concrete complexity results - the kind of stuff Rogoway does,
 for example - but the ones I've seen tend to be in the block
 cipher/cryptographic hash function spaces.  Does anyone one know of similar
 kinds of results for systems like RSA?

There is some interesting work in public key cryptosystems that reduce
to a *random* instance of a specific problem.

Here is a very cool one:

http://eprint.iacr.org/2009/576


Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

Vadim Lyubashevsky and Adriana Palacio and Gil Segev

Abstract: We propose a semantically-secure public-key encryption
scheme whose security is polynomial-time equivalent to the hardness of
solving random instances of the subset sum problem. The subset sum
assumption required for the security of our scheme is weaker than that
of existing subset-sum based encryption schemes, namely the
lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03,
STOC '05), and Peikert (STOC '09). Additionally, our proof of security
is simple and direct. We also present a natural variant of our scheme
that is secure against key-leakage attacks, as well as an oblivious
transfer protocol that is secure against semi-honest adversaries.


Unless I misunderstand, if you read someone's plaintext without having
the private key then you have proven that P=NP!

Nice. :-)

Regards,

Zooko

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-22 Thread Zooko O'Whielacronx
On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote
(on the cryptography@metzdowd.com list):
 [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

I've been looking at that one, with an eye to using it in the One
Hundred Year Cryptography project that is being sponsored by Google as
part of the Google Summer of Code (see recent discussions on the
tahoe-dev archives for April 2010 [1]).

Later I discovered this paper [2] which appears to be an improvement
on that one in terms of performance (see Table 1 in [2]) while still
having a tight reduction to the Computational Diffie-Hellman (CDH)
problem. Strangely, this paper [2] doesn't appear to have been
published anywhere except as an eprint on eprint.iacr.org. I wonder
why not. Is there something wrong with it?

I still have some major questions about the funky hash into a curve
part of these schemes. I'm hoping that [3] will turn out to be wrong
and a nice simple dumb efficient hack will be secure for these
particular digital signature schemes.

Of course if the newfangled schemes which reduce to a random instance
of a classic hard problem work out, that would provide an even
stronger assurance of long-term safety than the ones that reduce to
CDH. See for example the paper [4] that I mentioned previously on the
cryptography@metzdowd.com mailing list. Unless I misunderstand, if you
can break that scheme by learning someone's plaintext without knowing
their private key, then you've also proven that P=NP!

Unfortunately that one in particular doesn't provide digital
signatures, only public key encryption, and what I most need for the
One Hundred Year Cryptography project is digital signatures.

Regards,

Zooko

[1] http://allmydata.org/pipermail/tahoe-dev/2010-April/date.html
[2] http://eprint.iacr.org/2007/019
[3] http://eprint.iacr.org/2009/340
[4] http://eprint.iacr.org/2009/576

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-21 Thread Victor Duchovni
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.

-- 
Viktor.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-21 Thread Samuel Neves
On 21-04-2010 02:40, Victor Duchovni wrote:
 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.
   

While EC (by that I assume you mean ECDSA) does not have a formal
security proof, i.e., it is as hard as the EC discrete log, it it much
closer to one than RSA is to factoring. In particular, Pointcheval and
Stern, and later Brown come close to a formal proof for ECDSA [1].

If one goes further into other schemes, there is Rabin-Williams for the
factoring problem. There are also the schemes by Goh et al. [2] that are
reducible to the CDH and DDH problems in generic abelian groups (like
EC.)  Would patents also apply to one of these schemes over an elliptic
curve?

Best regards,
Samuel Neves

[1] http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-54.ps
[2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-20 Thread Samuel Neves

The state of the art in factorization is the same as for, e.g., the
factorization of RSA-768 [1] --- there haven't been many advances in the
number field sieve algorithm itself. The current effort, as Bernstein
puts it, is in speeding up smoothness detection, as part of the relation
collection process.

Both the RSA-768 factorization paper and a previous one by the same
authors [2] try to predict the effort needed for a 1024-bit prediction,
which is estimated to be around 1000 times harder than a 768-bit
modulus. [1] estimates to number of operations in the RSA768
factorization to be in the ballpark of 2^67 instructions: a thousand
times harder puts this on about 2^77, which puts it in the realm of
doable, but very hard, even for a well funded organization.

We also have to take into account the logistics of doing such a
factorization. Unlike an elliptic curve discrete logarithm computation,
that takes (relatively) negligible storage and communication, the number
field sieve requires massive amounts of data, and the linear algebra
step could become (even more of) a problem.

Best regards,
Samuel Neves

[1] http://eprint.iacr.org/2010/006
[2] http://eprint.iacr.org/2009/389

On 20-04-2010 16:45, Perry E. Metzger wrote:
 I was alerted to some slides from a talk that Dan Bernstein gave a few
 days ago at the University of Montreal on what tools will be needed to
 factor 1024 bit numbers:

 http://cr.yp.to/talks/2010.04.16/slides.pdf

 It has been a couple of years since there has been serious discussion on
 the list on this topic, and especially in the light of various technical
 decisions being undertaken on the size of DNS signing keys for high
 valued zones (like root), I was curious as to whether anyone had any
 interesting comments on the state of the art in factorization.

 Perry
   

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: What's the state of the art in factorization?

2010-04-20 Thread Thierry Moreau

Perry E. Metzger wrote:

I was alerted to some slides from a talk that Dan Bernstein gave a few
days ago at the University of Montreal on what tools will be needed to
factor 1024 bit numbers:

http://cr.yp.to/talks/2010.04.16/slides.pdf



I had the opportunity to listen to Prof. Dan Bernstein talk last Friday 
morning. I was very glad to see him as I respect his dedication to 
crypto maths, algorithm implementation, and very applied studies of 
computation complexity.


The slides are pretty much representative of his talk. New material 
starts on slide 17. If you are familiar with the contents of slides 1-16 
and elliptic curve methods (I am not), then you should appreciate the 
contents of slides 17 up to 45.


Slides 46 to 47 deal with the computation speedups available with 
graphics processors.


In the audience, there seemed to be some who followed the presentation 
more than I did but Dan made a great talk even for people like me.



It has been a couple of years since there has been serious discussion on
the list on this topic, and especially in the light of various technical
decisions being undertaken on the size of DNS signing keys for high
valued zones (like root), I was curious as to whether anyone had any
interesting comments on the state of the art in factorization.



According to my records, the state-of-the-art is reference

Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, 
and Peter L. Montgomery, On the Security of 1024-bit RSA and 160-bit 
Elliptic Curve Cryptography, version 2, August 7, 2009, 18 pages 
(published on pages 43-60 in Comments on the Transition Paper 
available at 
http://csrc.nist.gov/groups/ST/key_mgmt/documents/Transition_comments_7242009.pdf, 
which was listed at http://csrc.nist.gov/groups/ST/key_mgmt/index.html).


plus this talk last Friday (and references). From these, you have to do 
your homework in guesswork about your actual enemy's power.



In the Intaglio NIC project white paper I contributed towards the 
deployment of an alternate source for signed official DNS root data, I 
had to refer to the state-of-the-art. See 
http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:3.6 
(document section 3.6 Early Project Decisions about Protection Level).


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



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.



So, yes, it's always good to ask questions. I usually complain that one 
seldom gets a simple answer for a simple question addressed to a 
specialist. I don't feel I provided a simple answer, but I don't claim 
to be a specialist.



Regards,

- Thierry Moreau


Perry


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com