Re: What's the state of the art in factorization?
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: Quantum Key Distribution: the bad idea that won't die...
At 11:31 AM -0400 4/20/10, Perry E. Metzger wrote: 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. Paul Hoffman wrote: You hit it: almost. As long as a few researchers are interested, and there is money to be thrown down the drain^w^w^wat them, there will be active development. I too once worked exclusively in the world of classical cryptography and was sceptical of QKD. I now work in both worlds - classical cryptography and QKD. I now know that QKD can be a part of a high performance, cost competitive, highly secure system. I found that having an open mind about new technologies - and I don't mean just QKD - can and does provide insights that are useful in not only developing those new technologies, but also in improving existing ones. Just because everyone who claims to be a crypto expert, or a few of the more well-known popular experts (often the ones with big egos and loud voices) say that crypto is not the weakest link, or that QKD is a bad idea, doesn't mean it's true forever, even if you want to believe that it's true now. I don't know what the future holds, but when I think about what technology might be like in 10, 20, 50 years from now, I think back to what technology was like 10, 20, 50 years ago. Things change. And they change a lot. I doubt that public key encryption as we know it will survive the next 50 years. Maybe it won't survive the next 10 or 20 years. Maybe it will - I just don't know. I believe that it's important to acknowledge what we don't know, and to do our best to mitigate risks that may come from not knowing. We can of course identify and mitigate certain risks, even if we don't know all the facts about the risk itself. I worry when I see critically secure systems being deployed that rely exclusively on public key cryptography for key distribution. I'm disappointed when I read and hear comments from people that reject outright, even the possibility that QKD might be practical, and have a place in securing our current and future systems. To respond directly to Perry's comment quoted at the beginning of this email, I can assure you that there is actually very strong interest in QKD in the security community. The interest is not purely academic or oriented towards research. It has a very sound practical, commercial, and security basis. -- John Leiseboer, CTO, QuintessenceLabs Everything expressed by me in this email is my personal opinion. It is not necessarily the opinion of my employer. - 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 Wed, Apr 21, 2010 at 1:31 AM, Perry E. Metzger pe...@piermont.com 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. Useless now maybe, but it's preparing for a world where RSA is broken (i.e. quantum computers) and it doesn't require quantum computers; so it's quite practical, in that sense. 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 -- silky http://www.programmingbranch.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
silky michaelsli...@gmail.com writes: On Wed, Apr 21, 2010 at 1:31 AM, Perry E. Metzger pe...@piermont.com 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. Useless now maybe, but it's preparing for a world where RSA is broken (i.e. quantum computers) and it doesn't require quantum computers; so it's quite practical, in that sense. No, it isn't. QKD is useless three different ways. First, AES and other such systems are fine, and the way people break reasonably designed security systems (i.e. not WEP or what have you) is not by attacking the crypto. Second, you can't use QKD on a computer network. It is strictly point to point. Want 200 nodes to talk to each other? Then you need 40,000 fibers, without repeaters, in between the nodes, each with a $10,000 or more piece of equipment at each of the endpoints, for a total cost of hundreds of millions of dollars to do a task ethernet would do for a couple thousand dollars. Third, QKD provides no real security because there is no actual authentication. If someone wants to play man in the middle, nothing stops them. If someone wants to cut the fiber and speak QKD to one endpoint, telling it false information, nothing stops them. You can speak the QKD protocol to both endpoints and no one will be the wiser. So, you need some way of providing privacy and authentication... perhaps a conventional cryptosystem. So, what did QKD provide you with again? There is no point to QKD at all. 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?
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: Quantum Key Distribution: the bad idea that won't die...
silky michaelsli...@gmail.com writes: First of all, I'm sure you know more about this than me, but allow me to reply ... On Wed, Apr 21, 2010 at 11:19 PM, Perry E. Metzger pe...@piermont.com wrote: Useless now maybe, but it's preparing for a world where RSA is broken (i.e. quantum computers) and it doesn't require quantum computers; so it's quite practical, in that sense. No, it isn't. QKD is useless three different ways. First, AES and other such systems are fine, and the way people break reasonably designed security systems (i.e. not WEP or what have you) is not by attacking the crypto. I didn't say AES, I said RSA. Specifically I was referring to Shors factoring algorithm on quantum computers : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3862 I'm well aware, however, AES is not going to be broken by quantum computers (see Scott Aaronson's excellent lay explanations of the fact that quantum computers likely can't solve NP complete problems in polynomial time), and no one uses RSA or any other asymmetric cipher for link encryption. RSA+DH is typically used only for bootstrapping a symmetric cipher. QKD only provides link encryption anyway. Second, you can't use QKD on a computer network. It is strictly point to point. Want 200 nodes to talk to each other? Then you need 40,000 fibers, without repeaters, in between the nodes, each with a $10,000 or more piece of equipment at each of the endpoints, for a total cost of hundreds of millions of dollars to do a task ethernet would do for a couple thousand dollars. Sure, now. That's the point of research though; to find more efficient ways of doing things. I'm afraid that QKD is literally incapable of being done more efficiently than this. The whole point of the protocol is to get guarantees of security from quantum mechanics, and as soon as you have any intermediate nodes they're gone. I know of no one who claims to have any idea about how to extend the protocol beyond that, and I suspect it of being literally impossible (that is, I suspect that a mathematical proof that it is impossible should be doable.) Third, QKD provides no real security because there is no actual authentication. If someone wants to play man in the middle, nothing stops them. If someone wants to cut the fiber and speak QKD to one endpoint, telling it false information, nothing stops them. You can speak the QKD protocol to both endpoints and no one will be the wiser. So, you need some way of providing privacy and authentication... perhaps a conventional cryptosystem. I agree this is an issue, and from my reading it doesn't seem completely resolved, It isn't resolved at all. but again I think it's reasonable to continue researching into solutions. No one is doing that, though. People are working on things like faster bit rates, as though the basic reasons the whole thing is useless were solved. Importantly, however, is that if a classical system is used to do authentication, then the resulting QKD stream is *stronger* than the classically-encrypted scheme. Nope. It isn't. The system is only as strong as the classical system. If the classical system is broken, you lose any assurance that you aren't being man-in-the-middled. So, what did QKD provide you with again? There is no point to QKD at all. I disagree. That is, of course, your privilege. Perry -- Perry E. Metzgerpe...@piermont.com - 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 10:47 AM, Perry E. Metzger pe...@piermont.com wrote: [...] Second, you can't use QKD on a computer network. It is strictly point to point. Want 200 nodes to talk to each other? Then you need 40,000 fibers, without repeaters, in between the nodes, each with a $10,000 or more piece of equipment at each of the endpoints, for a total cost of hundreds of millions of dollars to do a task ethernet would do for a couple thousand dollars. Sure, now. That's the point of research though; to find more efficient ways of doing things. I'm afraid that QKD is literally incapable of being done more efficiently than this. The whole point of the protocol is to get guarantees of security from quantum mechanics, and as soon as you have any intermediate nodes they're gone. I know of no one who claims to have any idea about how to extend the protocol beyond that, and I suspect it of being literally impossible (that is, I suspect that a mathematical proof that it is impossible should be doable.) What do you mean intermediate nodes? It's possible to extend the length of QKD depending on the underlying QKD protocol used. I.e. in the EPR-based QKD, extension is possible. [...] No one is doing that, though. People are working on things like faster bit rates, as though the basic reasons the whole thing is useless were solved. I don't think you can legitimately speak for the entire community as to what or not they may be doing. It's interesting to me that some arguably unrelated fields of research (i.e. quantum repeaters) may be useful. Importantly, however, is that if a classical system is used to do authentication, then the resulting QKD stream is *stronger* than the classically-encrypted scheme. Nope. It isn't. The system is only as strong as the classical system. If the classical system is broken, you lose any assurance that you aren't being man-in-the-middled. No, it's not only as strong as the classical; it gets stronger if the classical component works. Quoting from: http://arxiv.org/abs/0902.2839v2 - The Case for Quantum Key Distribution If authentication is unbroken during the first round of QKD, even if it is only computationally secure, then subsequent rounds of QKD will be information-theoretically secure. Perry -- Perry E. Metzger pe...@piermont.com -- silky http://www.programmingbranch.com/ - 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 12:04 PM, Perry E. Metzger pe...@piermont.com wrote: No one is doing that, though. People are working on things like faster bit rates, as though the basic reasons the whole thing is useless were solved. I don't think you can legitimately speak for the entire community as to what or not they may be doing. I think I can, actually. I know of very few people in computer security who take QKD seriously. I feel pretty safe making these sorts of statements. But QKD is more about Physics than computer security. Anyway, it seems there is little purpose in continuing the discussion. Importantly, however, is that if a classical system is used to do authentication, then the resulting QKD stream is *stronger* than the classically-encrypted scheme. Nope. It isn't. The system is only as strong as the classical system. If the classical system is broken, you lose any assurance that you aren't being man-in-the-middled. No, it's not only as strong as the classical; it gets stronger if the classical component works. Quoting from: http://arxiv.org/abs/0902.2839v2 - The Case for Quantum Key Distribution If authentication is unbroken during the first round of QKD, even if it is only computationally secure, then subsequent rounds of QKD will be information-theoretically secure. Read what you just wrote. IF THE AUTHENTICATION IS UNBROKEN. That is, the system is only secure if the conventional cryptosystem is not broken -- that is, it is only as secure as the conventional system in use. Break the conventional system and you've broken the whole thing. Yes, I never stated the opposite (quote tree left intact). You were saying that it is only as strong as the classical system. It is clearly shown that the security of a QKD system *after* authentication is *stronger* than classical, due to the OTP. If what you meant to say was it is broken if authentication is broken then the answer is obviously yes. But the strength, in cryptographic terms, is clearly better. Perry -- Perry E. Metzger pe...@piermont.com -- silky http://www.programmingbranch.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
Let me note that Mr. Leiseboer is the CTO of a company that makes QKD equipment. John Leiseboer jleiseb...@bigpond.com writes: I too once worked exclusively in the world of classical cryptography and was sceptical of QKD. I now work in both worlds - classical cryptography and QKD. I now know that QKD can be a part of a high performance, cost competitive, highly secure system. On what basis do you know this? Again, there are three insurmountable problems here: QKD requires a conventional cryptosystem on top to provide authentication and privacy in the face of man-in-the middle attacks (so why do you want the QKD system?) QKD is inherently incompatible with networks -- it is point to point security only. QKD provides no practical security over conventional cryptosystems. No one attacks your security by breaking a modern system like AES -- people look elsewhere to attack you. Not, of course, that it matters, because if you can break AES, you can break a QKD system just by playing man-in-the-middle, so again, why use QKD? Just because everyone who claims to be a crypto expert, or a few of the more well-known popular experts (often the ones with big egos and loud voices) say that crypto is not the weakest link, or that QKD is a bad idea, doesn't mean it's true forever, even if you want to believe that it's true now. It is true forever. QKD doesn't even provide any security at all. As I've said repeatedly: As soon as you put a man in the middle with a pair of QKD boxes, each endpoint will happily communicate with it as though it was the other end. So, your security depends on having the data also authenticated and encrypted with a conventional system. If the conventional system is broken, the QKD added nothing. If the conventional system works, you didn't need the QKD. Game over. If you can explain how to get around this, I'm all ears. And please, no more comments about big egos. Technical arguments only. This is not a marketing list, it is a technical list. I'm pretty ruthless about cutting people off if they get insulting. I don't know what the future holds, but when I think about what technology might be like in 10, 20, 50 years from now, I think back to what technology was like 10, 20, 50 years ago. Things change. And they change a lot. I doubt that public key encryption as we know it will survive the next 50 years. That's a very bold statement, and one that I doubt you can back up, but it is irrelevant to the current discussion, since no one encrypts links with public key anyway. They may use it for key exchange -- but again, QKD only provides link security, and you need a conventional crypto system running on top of it anyway because it can't defend against man in the middle attacks anyway, so it doesn't matter. If RSA and DH can't be trusted for key exchange, then both the conventional and the QKD systems will need keys for conventional ciphers manually loaded at both ends -- QKD isn't secure without the conventional cipher system providing authentication and privacy in the face of man in the middle attacks. I worry when I see critically secure systems being deployed that rely exclusively on public key cryptography for key distribution. Well, since any secure QKD system needs a conventional cryptosystem on top to provide the actual security anyway, this is not an advantage of QKD. If it is a problem conventional systems can't surmount, QKD can't surmount it. If conventional systems can get beyond it, then QKD isn't needed. I'm disappointed when I read and hear comments from people that reject outright, Well, you'll have to explain why I'm wrong, then. In detail. even the possibility that QKD might be practical, and have a place in securing our current and future systems. It is practical to build very expensive QKD boxes. It is totally impractical to use them vs. just using a conventional cipher. To respond directly to Perry's comment quoted at the beginning of this email, I can assure you that there is actually very strong interest in QKD in the security community. Not at the conferences I go to. I can't name anyone who has any interest in it at all. Mostly we sit around at the bar and wonder why the hell people keep spending money on it. If you care to name people who have an interest here, please let me know. I haven't found them. The interest is not purely academic or oriented towards research. It has a very sound practical, commercial, and security basis. I again note that Mr. Leiseboer is the CTO of a company that makes QKD equipment. If you dispute my position here, I'm happy to discuss it, but you're going to have to explain why I'm wrong -- a detailed technical explanation, not a set of assertions. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Quantum Key Distribution: the bad idea that won't die...
silky michaelsli...@gmail.com writes: On Thu, Apr 22, 2010 at 12:04 PM, Perry E. Metzger pe...@piermont.com wrote: No one is doing that, though. People are working on things like faster bit rates, as though the basic reasons the whole thing is useless were solved. I don't think you can legitimately speak for the entire community as to what or not they may be doing. I think I can, actually. I know of very few people in computer security who take QKD seriously. I feel pretty safe making these sorts of statements. But QKD is more about Physics than computer security. I agree it is an interesting physics trick -- considerable fun to read about. I disagree that it is of use in making computer systems secure. Yes, I never stated the opposite (quote tree left intact). You were saying that it is only as strong as the classical system. It is clearly shown that the security of a QKD system *after* authentication is *stronger* than classical, due to the OTP. If what you meant to say was it is broken if authentication is broken then the answer is obviously yes. But the strength, in cryptographic terms, is clearly better. Lets look at the two possible scenarios. If the conventional crypto is secure, then the whole system is secure. If the conventional crypto is insecure, then the whole system is insecure. Looks to me like the system is only as strong as the classical system. If the classical system is unbroken, you don't need the QKD box. If the classical system is broken, the QKD box adds no security. Ergo, the system is only as strong as the classical system. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
