Re: What's the state of the art in factorization?
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?
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: The EC patent issues discussion
On 2010-04-22 9:17 AM, Paul Hoffman wrote: At 9:40 PM -0400 4/20/10, Victor Duchovni wrote: EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. This is starting to turn around. More vendors are questioning the murk. Please seehttp://tools.ietf.org/html/draft-mcgrew-fundamental-ecc. To summarize that document: All the EC stuff that you need was published more than fifteen years ago, therefore you cannot be violating patents if you stick to that stuff. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
While I'm quite skeptical that QKD will prove of practical use, I do think it's worth investigating. The physics are nice, and it provides an interesting and different way of thinking about cryptography. I think that there's a non-trivial chance that it will some day give us some very different abilities, ones we haven't even thought of. My analog is all of the strange and wondrous things our cryptographic protocols can do -- blind signatures, zero knowledge proofs, secure multiparty computation, and more -- things that weren't on the horizon just 35 years ago. I'm reminded of a story about a comment Whit Diffie once heard from someone in the spook community about public key crypto. We had it first -- but we never knew what we had. You guys have done much more with it than we ever did. All they knew to do with public key was key distribution or key exchange; they didn't even invent digital signatures. They had non-secret encryption; we had public key cryptography. Might the same be true for QKD? I have no idea. I do suggest that it's worth thinking in those terms, rather than how to use it to replace conventional key distribution. Remember that RSA's essential property is not that you can use it to set up a session key; rather, it's that you can use it to send a session key to someone with whom you don't share a secret. Beyond Perry's other points -- and QKD is inherently point-to-point; you need n^2 connections, since you can't terminate the link-layer crypto at a router without losing your security guarantees -- it's worth reminding people that the security guarantees apply to ideal quantum systems. If your emitter isn't ideal -- and of course it isn't -- it can (will?) emit more photons; I can play my interception games with the ones your detector doesn't need. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
On Apr 20, 2010, at 11:31 AM, Perry E. Metzger wrote: Via /., I saw the following article on ever higher speed QKD: http://www.wired.co.uk/news/archive/2010-04/19/super-secure-data-encryption-gets-faster.aspx Very interesting physics, but quite useless in the real world. I wonder why it is that, in spite of almost universal disinterest in the security community, quantum key distribution continues to be a subject of active technological development. Perry -- Perry E. Metzger pe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com There have been many misattributions in the technological world to include remarks supposedly made about 640K of memory, the number of computers required for global processing needs, and the number of routers that would eventually be required for internetworking. Perry's claim has the property of actually having been said, so I will archive it. My own speculation is that the security community and its interests are perhaps a bit broader than than some members wish it were. If you want to see some interesting physics that represents unexpected results relevant to communications (and comes from entangled QKD research) then take a look at: http://pra.aps.org/abstract/PRA/v81/i2/e023835 There is a human-readable summary at: http://focus.aps.org/story/v25/st7 John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
Steven Bellovin s...@cs.columbia.edu writes: While I'm quite skeptical that QKD will prove of practical use, I do think it's worth investigating. I agree. What I don't understand is why people are trying to *commercialize* it, or claiming that it is of practical use as it stands. The physics are nice, and it provides an interesting and different way of thinking about cryptography. I think that there's a non-trivial chance that it will some day give us some very different abilities, ones we haven't even thought of. I don't disagree, and I think that this, too, is a good reason to study it in an academic setting. What I don't get, as I said, is people going off and spending large amounts of effort on things like getting the systems to do video rate communications or trying to sell them. My analog is all of the strange and wondrous things our cryptographic protocols can do -- blind signatures, zero knowledge proofs, secure multiparty computation, and more -- things that weren't on the horizon just 35 years ago. I'm reminded of a story about a comment Whit Diffie once heard from someone in the spook community about public key crypto. We had it first -- but we never knew what we had. You guys have done much more with it than we ever did. All they knew to do with public key was key distribution or key exchange; they didn't even invent digital signatures. They had non-secret encryption; we had public key cryptography. Might the same be true for QKD? I have no idea. I do suggest that it's worth thinking in those terms, rather than how to use it to replace conventional key distribution. Remember that RSA's essential property is not that you can use it to set up a session key; rather, it's that you can use it to send a session key to someone with whom you don't share a secret. Fair point. There may be quite interesting tricks there, but I think it would be better if people treated this as a very interesting research space and not as an important security technology, which is how it gets portrayed to the press. As an academic research project, the intersection of quantum effects and security remains a very interesting area to explore, and we may yet get valuable security technologies out of it. However, the current QKD concept is not of practical use, but it is generally portrayed as being a really important breakthrough in the press. (This also reflects a considerable popular misunderstanding of where the problems in security are -- they're not in defending our link layers against eavesdropping.) Beyond Perry's other points -- and QKD is inherently point-to-point; you need n^2 connections, since you can't terminate the link-layer crypto at a router without losing your security guarantees -- it's worth reminding people that the security guarantees apply to ideal quantum systems. If your emitter isn't ideal -- and of course it isn't -- it can (will?) emit more photons; I can play my interception games with the ones your detector doesn't need. Indeed, and from my readings of the literature there are other attacks. I find it important, however, that even if the systems worked perfectly and as advertised, there is little reason to want them. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
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: Quantum Key Distribution: the bad idea that won't die...
On Thu, Apr 22, 2010 at 09:46:18AM -0400, John Lowry wrote: My own speculation is that the security community and its interests are perhaps a bit broader than than some members wish it were. If you want to see some interesting physics that represents unexpected results relevant to communications (and comes from entangled QKD research) then take a look at: http://pra.aps.org/abstract/PRA/v81/i2/e023835 This is interesting. However, even if you can use LoS up to LEO, the question is of what the added value of a (supposedly, trend in QC state cloning attacks is there) tamperproof exchange is over traditional cryptography. I agree with Perry that it solves a non-problem. There is a human-readable summary at: http://focus.aps.org/story/v25/st7 -- Eugen* Leitl a href=http://leitl.org;leitl/a http://leitl.org __ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
* 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?
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?
* 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?
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?
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
