Re: post-quantum computing in GnuPG
Or someone builds a working quantum computer with many bits and demonstrate a working decryption of RSA-2048 in a few seconds. :-) Well, you'd need 4096 qubits in the ensemble, representing a state space of something like 10^1233 (not a typo). At that point I'm going to just give up and offer my services to our new Space Overlords from Zarbnulax Prime. Maybe if I help round up pesky humans they'll give me a ride in their FTL spaceships! :) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
post-quantum computing in GnuPG
Hi, is there any plan to include post-quantum cryptography ciphers such as McEliece and NTRU in GnuPG? I know that NTRU is patented until 2020, but I found some C implementations. It says that modifying the code it is possibile to have it patent-free in 2017. http://goo.gl/cQGavW This is there officiale implementation by Security Innovation. http://goo.gl/J6Adjw In any case there is McEliece. Thanks. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: post-quantum computing in GnuPG
Hi, is there any plan to include post-quantum cryptography ciphers such as McEliece and NTRU in GnuPG? I am not a GnuPG developer: they will have the official word. Unofficially, no. GnuPG tracks the RFCs published by the IETF Working Group. If you want to see this, make a case for it to the WG and get algorithm numbers, etc., assigned. Then implement it as a patch to a GnuPG tree and let people beat on it for a while. If it survives, you've got an excellent chance of getting it adopted into GnuPG. I know, I know -- I didn't mean 'how do *I* implement it,' I meant 'are *you* going to implement it.' And the answer there is probably not, not unless someone like you gets the ball rolling in the above fashion. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: post-quantum computing in GnuPG
On 02-04-2014 1:43, Robert J. Hansen wrote: I know, I know -- I didn't mean 'how do *I* implement it,' I meant 'are *you* going to implement it.' And the answer there is probably not, not unless someone like you gets the ball rolling in the above fashion. Or someone builds a working quantum computer with many bits and demonstrate a working decryption of RSA-2048 in a few seconds. :-) -- ir. J.C.A. Wevers PGP/GPG public keys at http://www.xs4all.nl/~johanw/pgpkeys.html ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On 4-1-2014 13:31, micha137 wrote: A spoofing organization is no fertile ground for true innovation. The real scientists, not the NSA are going to make progress in quantum computing. And it is not going to be as cheap as some tens of megabucks. Progress to get it practical will be painfully slow. You IT people can sit back and relax. Not really, whoever builds a quantum computer doesn't really matter. As soon as the technology becomes widely available QC-resistant crypto becomes necessary anyway. -- Met vriendelijke groet / With kind regards, Johan Wevers PGP/GPG public keys at http://www.xs4all.nl/~johanw/pgpkeys.html ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Quantum computing
They cheat, they bribe, they lie, they blackmail, they take polygraph tests on each other but they don't invent. A spoofing organization is no fertile ground for true innovation. The real scientists, not the NSA are going to make progress in quantum computing. And it is not going to be as cheap as some tens of megabucks. Progress to get it practical will be painfully slow. You IT people can sit back and relax. Cheers Michael Anders (a dedicated physicist) Von Samsung Mobile gesendet___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
Hello, micha137. You wrote 4 января 2014 г., 16:31:44: m They cheat, they bribe, they lie, they blackmail, they take polygraph m tests on each other but they don't invent. As far as I know, NSA is biggest employer of mathematicians in the world. I don't know about physics and quantum computing, but they CAN invent something, that depends on number theory. -- // Black Lion AKA Lev Serebryakov l...@serebryakov.spb.ru ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
Hi! Anders Breindahl schrieb: So please restate that -- even in the face of quantum computers -- we won't ever factor 256 bit numbers. Apart from the fact that 256bit is about symmetric keys (a 256bit number would be factored quite easily -- that's why we have 4096 bit RSA keys), possible advances in cryptology are nothing that would require key lifetimes. Once you do not feel comfortable enough with your current keylength anymore, you can simply revoke the key manually. Actually, predicting possible advances in fields like quantum computing is very hard, so it would be far easier to follow the news on this topic rather than decide *today* when your current key might become insecure (to make a sensible decision about the expiry-date). Consequently, your choice would have to be over-conservative (which is not necessarily a bad thing). Key expiry, to my understanding, is more of an automatic fallback mechanism to limit the possible damage/inconvenience in the case that you cannot take care of revoking the key yourself. This does very well justify the short lifetimes that we see on keys today. cu, Sven ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On 200704201113, Robert J. Hansen wrote: Yeah, again. I completely agree on the practical aspect of it, but would nevertheless like to see proofs of complexity that weren't dependent on the current models of computations. I don't mean to sound flip, but as soon as you invent a hypercomputer I would love to revisit this issue with you. I realise(d). See below. For now, all our computational theoretic proofs will be limited by the the lambda calculus. I don't mean to sound blunt there, but our current model of computation is extraordinarily robust, and there are very strong arguments that hypercomputation is both physically and mathematically impossible. (If any problem in UNDECIDABLE can be solved by an oracle, then math goes from incomplete and inconsistent straight into pervasively self-contradictory and broken. That's the rationale for hypercomputation being physically and mathematically impossible.) A pretty good one, too. In any case, if I want a model-of-computation-unbound proof of difficulty, you'll simply invent a new model-of-computation that handles my problem efficiently. The point that you're telling me and I'm telling you is that such proofs can't exist and aren't feasible to pursue. So yeah, I'm not sure why you want flawless perfect proofs of security when reality shows that provably secure systems never are. ``never'' is in this case based on one case of provable secure scheme (that was notably difficult in implementation)? Though it sounds sweet, it's beyond the scope of cryptography to ensure such protection (to some extent, though, security should limit room for personnel ``breakage''). It's beyond the realm of mathematical cryptography, but not the field as a whole. My day job involves security analysis of electronic voting machines for the National Science Foundation [*]. We spend far, far more time scrutinizing the human side of the cryptography than the mathematical side. Probably an order of magnitude. I could easily imagine. Also, I assume that your systems limit room of human control. Regards, skrewz. signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 ``never'' is in this case based on one case of provable secure scheme (that was notably difficult in implementation)? I wouldn't be so quick to place blame on the difficulty of implementing the one-time pad. Implementing the OTP is really pretty simple: use each pad once and burn it when you're done. The difficulty lies in trying to make fallible human nature rise to the level of competency required to use the OTP. Anyway, to answer your question, no. It's based on a couple of things. 1. Many provably secure schemes are isomorphic to the one-time pad. This means that the other provably secure schemes share the same flaws as the OTP. 2. The provably secure schemes that aren't isomorphic to the OTP typically get broken pretty quickly. As an example of #2, look at IBM's Atjai-Dwork, which was released at CRYPTO97. Atjai-Dwork was some nice work, really, with a beautiful mathematical proof of security. I emphasize this: _proof_. It wasn't built on conjecture. Within a year there were three different breaks against Atjai-Dwork. Turns out the axioms Atjai and Dwork used to build the algorithm weren't quite as robust as they thought. Moral of the story: proofs of security are nice. They give us something to point and laugh at. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (Darwin) iQEcBAEBCgAGBQJGKoqZAAoJELcA9IL+r4EJ0NAH/iITpey1J+7LSzmOEhQXmx07 neLiSqeTb++9yy2mWWlYt8WyfvALbljNWrgmyZqFoRrMRVkkF+MhbqEPm9PcyOcp ndE78mqt+9xI+H7SY6heFyWRemKtXVpGBYalHeFh3P+K/1xzmAio6SwfTw6PxYl+ gvAy1pvvNY1HNi/jux6PzCyI3AVSZGudV92/6cQJkED0UOPIdWcuoyu1PHY2g8St hhLmVXewBe41P883wV1y3/5mwQBTGp+j6yH9i1FZ/46vzVhRbwidJgtYSZpnB9Yn fsXfZlazX5MFVIJQyeUOzkARYmD4Go+sALw6TP75HhRrXYBlv7CWAqsMkm57WPg= =sGBb -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On 200704191925, Robert J. Hansen wrote: While I agree that commercial development _may_ lead to developments in QC, I think it's equally likely that the engineering difficulties will be insurmountable. Which means that, from where I sit, we should just shrug and say we really can't say with any confidence what the future will or will not hold. Well. Yeah. But the thing that was and is fascinating about cryptography is that it -- assuming some model of computing -- is ``provable too hard'' to bypass. I'm worried that the future holds in store revolutions in computability that will shake those assumptions on ``too hard''. This is in contrast to quantum cryptography, which, IINM, is provably uninterceptable (but, unlike traditional cryptography, has many weaknesses beyond the purely theoretical ones). found -- this pragmatism causes me to ponder the scenario in which something like Rice' theorem could be established for quantum computers' ability (or traditional computers' inability): What do you mean? Rice's theorem applies to QC. Again, if I got it correctly, Rice' theorem came into a world where science was occupied with proving that this and that property was undecidable. Something ``like'' Rice' theorem would in a similar way alter the way that the scientific field is on. It's true that in mathematics there could always be a proof delivered tomorrow by some hungry graduate student which will utterly shatter our knowledge of math as we know it. But this is true for all of mathematics. It's not as if this risk is special to QC. I was mostly focusing on positive proofs, by which I mean those that define what _is_ doable or assumable, rather than the negative proofs that define what is undoable. Both are convenient. However, the proofs that consolidate the security of programs like gnupg, assume some model of computation... And in the face of quantum computing, that assumption may (=has the potential to) radically change. So what I would love to see is some proof that -- even when faced with this new model of computing, ignoring its practical limitations -- the best-known attack on gnupg's algorithms takes factor ten of the lifetime of the universe or would cost twice the energy of the sun. Which can't be said of RSA on a huge quantum computer, if I understood you correctly. You should be just as concerned about the prospect of P=NP. I haven't had my introductory courses in computability theory yet. I don't know what that is, and will patiently wait for it. Thanks for the lecture. Regards, skrewz. signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On Fri, 20 Apr 2007 09:09, [EMAIL PROTECTED] said: This is in contrast to quantum cryptography, which, IINM, is provably uninterceptable (but, unlike traditional cryptography, has many weaknesses beyond the purely theoretical ones). While you mention this, I can't resist to forward Perry E. Metzger's comments: To: cryptography at metzdowd Subject: my periodic rant on quantum crypto From: Perry E. Metzger Date: Mon, 12 Apr 2004 15:37:33 -0400 /. is running yet another story on quantum cryptography today, with the usual breathless hype: http://science.slashdot.org/article.pl?sid=04/04/12/133623 I'm especially unimpressed with the Does this spell the end of the field of cryptography? comment. For those who don't know much about what it is, Quantum Cryptography is a very expensive way of producing an unauthenticated link encryption device. It is useless for any application other than link encryption over a short distance and requires a dedicated optical fiber to work. QC has no properties that render it especially better for link encryption than, say, a box from one of several vendors running AES on the link instead. It is perhaps theoretically safer, but in practice no one is going to break AES either -- they're going to bribe the minimum wage guard at your colo to have 20 minutes alone with your box while they install a tap on the clear side of it (or worse, they'll slip in while the guard is asleep at his desk.) QC still requires link authentication (lest someone else other than the people you think you're talking to terminate your fiber instead). As a result of this, you can't really get rid of key management, so QC isn't going to buy you freedom from that. QC can only run over a dedicated fiber over a short run, where more normal mechanisms can work fine over any sort of medium -- copper, the PSTN, the internet, etc, and can operate without distance limitation. QC is fiendishly costly -- orders of magnitude more expensive than an AES based link encryption box. QC is extremely hard to test to assure there are no hardware or other failures -- given the key in use, I can use intercepted traffic to assure my AES link encryption box is working correctly, but I have no such mechanism for a QC box. On top of all of this, the real problems in computer security these days have nothing to do with stuff like how your link encryption box works and everything to do with stuff like buffer overflows, bad network architecture, etc. Given that what we're dealing with is a very limited technology that for a very high price will render you security that is at best not particularly better than what much more economical solutions will yield, why do people keep hyping this? Indeed, why do people buy these boxes, if indeed anyone is buying them? It is stunning that a lab curiosity continues to be mentioned over and over again, not to mention to see venture capitalists dump money after it. BTW, none of this has anything to do with Quantum Computing, which may indeed yield breakthroughs someday in areas such as factoring but which is totally unrelated... Perry Salam-Shalom, Werner ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
Anders Breindahl wrote: Well. Yeah. But the thing that was and is fascinating about cryptography is that it -- assuming some model of computing -- is ``provable too hard'' to bypass. I'm worried that the future holds in store revolutions in computability that will shake those assumptions on ``too hard''. I forget who said this, but it's my favorite quote about predicting the future. The future never comes to us well-ordered. It's always punctuated with unpredictable advances and inexplicable delays. You can either obsess over the fact that crypto is a branch of mathematics, and thus a human endeavor subject to the disordered-future rule, or you can smile and shrug and say well, we'll do the best with what we have, and keep our eyes open for the future. My best advice is to not worry about it. :) This is in contrast to quantum cryptography, which, IINM, is provably There is no such thing as quantum cryptography. Cryptography is a broad term encompassing a great many subjects, and we simply don't have that for the quantum world. Quantum key exchange is an interesting trick of physics. But that's all quantum cryptography is at this point--a simple key exchange algorithm. There are no quantum encryption algorithms, no quantum signature schemes, no quantum hash functions. Just quantum key exchange... which is nowhere near as cool as people make it out to be. It's an interesting parlor trick. It's not anything new in the world of crypto. Again, if I got it correctly, Rice' theorem came into a world where science was occupied with proving that this and that property was undecidable. Something ``like'' Rice' theorem would in a similar way alter the way that the scientific field is on. [scratches head] Are you talking about the second Hilbert problem? That one generally goes to Gödel or Turing. Rice's theorem is an interesting bit of work with some deep consequences for computer science, but it's not anywhere near as big of a shakeup as incompleteness. Both are convenient. However, the proofs that consolidate the security of programs like gnupg, assume some model of computation... What proofs? There are none. There are just lines of reasoning which we believe to have substantial weight, but nobody has delivered an actual proof of security for any cipher or hash. To do so you'd have to prove P != NP, and that's one of the Holy Grails of CompSci. Look at something as simple as RSA. There are three major conjectures that go into RSA. 1. The RSA problem (RSAP) is equivalent to the integer factorization problem. 2. The Integer Factorization Problem is not in P. 3. P != NP. None of those have been proven. None. We like to pretend that they have been, we like to handwave them, but the reality is those conjectures are unproven... and, in fact, #1 is probably false. See Boneh and Venkatesan, Breaking RSA May Be Easier than Factoring. http://theory.stanford.edu/~dabo/papers/no_rsa_red.pdf So what I would love to see is some proof that -- even when faced with this new model of computing, ignoring its practical limitations -- Why? Seriously. Why? By and large, cryptanalysis of intercepts is a dead issue. Nobody with half a brain does it. According to the best information available, during the entire Cold War the KGB and GRU were never able to break a single United States cipher cleared for top-secret information. That's not to say the KGB and GRU weren't reading top-secret cables on a regular basis. Instead of cryptanalyzing the traffic, they just sent expensive hookers and good bourbon to cipher clerks in the American embassy. There are literally thousands of ways to skin this cat. Focusing on purely the mathematical aspect is very shortsighted. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
[ Please interrupt if this is getting too off-topic. ] On 200704200441, Robert J. Hansen wrote: Anders Breindahl wrote: Well. Yeah. But the thing that was and is fascinating about cryptography is that it -- assuming some model of computing -- is ``provable too hard'' to bypass. I'm worried that the future holds in store revolutions in computability that will shake those assumptions on ``too hard''. I forget who said this, but it's my favorite quote about predicting the future. The future never comes to us well-ordered. It's always punctuated with unpredictable advances and inexplicable delays. You can either obsess over the fact that crypto is a branch of mathematics, and thus a human endeavor subject to the disordered-future rule, or you can smile and shrug and say well, we'll do the best with what we have, and keep our eyes open for the future. My best advice is to not worry about it. :) Yeah, again. I completely agree on the practical aspect of it, but would nevertheless like to see proofs of complexity that weren't dependent on the current models of computations. However, then you'll just invent the hardware-coming-in-3050 model, that does all its calculations by solving RSA. Or whatever I aim to defend. This is in contrast to quantum cryptography, which, IINM, is provably There is no such thing as quantum cryptography. Cryptography is a broad term encompassing a great many subjects, and we simply don't have that for the quantum world. I was referring to the subject that is mentioned on the Wikipedia page: http://en.wikipedia.org/wiki/Quantum_cryptography Saying that ``there is no such thing'' seems harsh and as if you ignore reality. The European Union put its hopes up for implementing a ``quantum cryptography'' network of communications. That sort of makes the term real in itself. Link to that statement in Danish: http://ing.dk/apps/pbcs.dll/article?AID=/20040826/IT/108270093 That doesn't mean that it (quantum cryptography) by any means is practical. It would seem from Werner's forward that it's so deeply buried in its own infancy or -- more seriously -- inherent technicalities, that it won't find any practical use ever. However, quantum cryptography does have that nice inherent benefit, that it _can't_ be eavesdropped, according to said article. That is, after authenticity has been established and the line has been paid for: http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks: In Quantum Cryptography, traditional man-in-the-middle attacks are impossible due to the Observer Effect. If Mallory attempts to intercept the stream of photons, he will inevitably alter them. He cannot re-emit the photons to Bob correctly, since his measurement has destroyed information about the photon's full state and correlations. I suppose that this is the feature that got the European Union's attention. Again, if I got it correctly, Rice' theorem came into a world where science was occupied with proving that this and that property was undecidable. Something ``like'' Rice' theorem would in a similar way alter the way that the scientific field is on. [scratches head] Are you talking about the second Hilbert problem? That one generally goes to Gödel or Turing. Rice's theorem is an interesting bit of work with some deep consequences for computer science, but it's not anywhere near as big of a shakeup as incompleteness. Then take that for an example. My point is that proofs can alter the heading of a scientific field in the time it takes to they're generally accepted. Both are convenient. However, the proofs that consolidate the security of programs like gnupg, assume some model of computation... What proofs? There are none. I was merely assuming that such proofs existed. But, when I think again, formal proofs of correctness are hard to get, too, so why would common cryptography be provable? So what I would love to see is some proof that -- even when faced with this new model of computing, ignoring its practical limitations -- Why? Seriously. Why? By and large, cryptanalysis of intercepts is a dead issue. Nobody with half a brain does it. It's the you-don't-know-that-question. *Probably*, it's secure, and all data supports it, but it hasn't been proved to be secure. Therefore, it's restricted to being ``probably'' or ``very probably'' secure. Right? Contrary to one time pads, which are provably secure -- where ``secure'' means ``unbreakable from theoretical standpoint, but with no thought given to practical limits''. I was told that one time pads were also used by the KGB, by the way. Mini-books whose pages were to be burned after using. According to the best information available, during the entire Cold War the KGB and GRU were never able to break a single United States cipher cleared for top-secret information. That's not to say the KGB and GRU weren't reading top-secret cables on a regular basis. Instead of
Re: Quantum computing
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 Yeah, again. I completely agree on the practical aspect of it, but would nevertheless like to see proofs of complexity that weren't dependent on the current models of computations. I don't mean to sound flip, but as soon as you invent a hypercomputer I would love to revisit this issue with you. For now, all our computational theoretic proofs will be limited by the the lambda calculus. I don't mean to sound blunt there, but our current model of computation is extraordinarily robust, and there are very strong arguments that hypercomputation is both physically and mathematically impossible. (If any problem in UNDECIDABLE can be solved by an oracle, then math goes from incomplete and inconsistent straight into pervasively self-contradictory and broken. That's the rationale for hypercomputation being physically and mathematically impossible.) I was referring to the subject that is mentioned on the Wikipedia page: http://en.wikipedia.org/wiki/Quantum_cryptography Wikipedia is not an authoritative reference. Quantum cryptography is a nice catchphrase. I'm unaware of any respected authority in the field of crypto who takes the phrase seriously. The phrase is used in nontechnical media, and in that environment its usage is probably defensible. After all, people reading the newspaper don't want to be bothered with the details of what QKE is all about. But we're trying to be precise here, and for that reason, let's not talk about quantum cryptography. Let's be precise and talk about QKE. Contrary to one time pads, which are provably secure -- where ``secure'' means ``unbreakable from theoretical standpoint, but with no thought given to practical limits''. I was told that one time pads were also used by the KGB, by the way. Mini-books whose pages were to be burned after using. The NSA was breaking the KGB's one-time pads. Look into Project VENONA. Soviet cipher clerks were making technical errors in using their one-time pads and the NSA was able to start reading their traffic. So yeah, I'm not sure why you want flawless perfect proofs of security when reality shows that provably secure systems never are. Though it sounds sweet, it's beyond the scope of cryptography to ensure such protection (to some extent, though, security should limit room for personnel ``breakage''). It's beyond the realm of mathematical cryptography, but not the field as a whole. My day job involves security analysis of electronic voting machines for the National Science Foundation [*]. We spend far, far more time scrutinizing the human side of the cryptography than the mathematical side. Probably an order of magnitude. [*] I'm not speaking for the NSF here, obviously, I'm completely responsible for any errors I make, etc., etc. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (Darwin) iQEcBAEBCgAGBQJGKOavAAoJELcA9IL+r4EJ0cUIAKtWkRqLLXEfUfUzGmCTLXep rsaxL2M3pBooQ9IIrnaTqKJxGkwyctYELZj94q+qcO+UZQ63HQGs7cslK7o1/Wyl lN23aBlio7lABDT+jqyZYg2RWj2Urb6TKpYdTqsKiYM7MA2oxLpvIw9ear5s3Nxe 33uGKb5S3rZzjoYPgz35KXaqX7Qq9STbXFkiP70PsA8CazYXo3F9Tlqa+/n2/Wwf Ti18Ga3DVjQoFx3uuU2U/+99gAQKrU9f6J6Q0N4WDFJO3Elst+7eCB89FEuoQYOl iM2/bxTvJ+2/Uk022b++nlc7agtgMtJaVTsec7mbDqyaNinD5BR3jQgRl3oG7E8= =p91A -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On Fri, Apr 20, 2007 at 01:57:46PM +0200, Anders Breindahl wrote: Saying that ``there is no such thing'' seems harsh and as if you ignore reality. The European Union put its hopes up for implementing a ``quantum cryptography'' network of communications. That sort of makes the term real in itself. This is because they are a governement and gov't usually wants to have super secure comm network for gov't super secret communication. However, quantum cryptography does have that nice inherent benefit, that it _can't_ be eavesdropped, according to said article. That is, after authenticity has been established and the line has been paid for: It can be eavesdropped, but it is impossible to intercept information that way and the eavesdropping is detectable. Or rather should be: eavesdropping on QC link is detectable if by rule single photons are used as transmission units. This is because there's no way to intercept a photon and reinject it without destroying its quantum state. However, in commercial installations pulses (batches of photons) are used, so its perfectly possible to intercept a piece of the pulse. My quantum-fu is too weak to really know if this makes the eavesdropping undetectable, but the intuition says that yes. I suppose that this is the feature that got the European Union's attention. EU is know for sinking money in very bizarre projects. But the attractive part of focusing on the mathematical aspects are that -- if provable -- it could give some guarantee ( reassurance) of the unbreakability of the ciphers out there. You may not be interested in that, but I am. I too however neither will end up a mathematician whose life is focused on solving some single problem. But I would be interested in the result. I could pick the cipher that provably could withstand any battering thinkable over the cipher that perhaps couldn't. But the point is that the ciphers live in the real world and in the real world it is much easier to do HUMINT (like ale and whores mentioned before, or rubberhose cryptanalysis) instead of trying to break the mathematically unbreakable. Be it provably unbreakable or not. OpenPGP and GPG is about making the idea-based mathematic apparatus suited to survive in the real world. If you want to see what it takes, find a movie called In ascolto or The Listening (it was shot in Italy by Italians, and was released both in Italian and English), it is a somewhat loose on technical side, but shows the difference between mathematical/theoretical and real life security. P2P file details on (encrypted) request. Alex -- JID: [EMAIL PROTECTED] PGP: 0x46399138 od zwracania uwagi na detale są lekarze, adwokaci, programiści i zegarmistrze -- Czerski ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing (Robert J. Hansen)
Message: 4 Date: Wed, 18 Apr 2007 19:56:48 -0500 From: Robert J. Hansen [EMAIL PROTECTED] Subject: Re: Quantum computing Brute-forcing a 128-bit cipher using a traditional computer is a ridiculous proposition, but using Grover's, it becomes as hard as brute-forcing a 64-bit cipher... hard, but possible. So the best way to defend against exhaustive key search in a quantum world is to either (a) trust that quantum computing is going to remain in just a couple of years for the next few decades (which may very well be true), or (b) multiply your key sizes by a factor of 2. The principal reason why AES supports a 256-bit key is because of the possibility of quantum computing and Grover's algorithm. Brute- forcing a 256-bit cipher with Grover's is as hard as brute-forcing a 128-bit cipher with a conventional computer... absolutely ridiculous. :) am not familiar with quantum physics, but do have some math background please confirm if i have understood your post correctly to imply that if someone uses a straight diceware passphrase (choosing words as they appear in the diceware list without alteration, so that a brute force dictionary attack using a diceware word list is possible) to protect a message encrypted symmetrically with a 256 bit algorithm, then quantum computing could crack the passphrase even if it consisted of 10 diceware words, and that in order to achieve passphrase security at the 128 bit level a 20 word diceware passphrase would be necessary ? =[begin background calculations]= a diceware word list has 7776 possiblities, 7776 = 6^5 (5 dicethrows, 6 possibilities each) 7776 = [(2)(3)]^5 2^(1.58) 3 2^(1.59) (2)(3) = (2)(2^[1.58]) = 2^[2.58] (7776) = [(2)(3)]^5 = [2^(2.58)]^5 = 2^(12.9) so, to find the number of diceware words that would provide equivalent security to a 128 or 256 bit symmetrical algorithm, we do (7776)^x = 2^128 and (7776)^y = 2^256 which becomes 2^[(12.9)x] = 2^128 and 2^[(12.9)y] = 2^256 so the closest integral values for x and y are 10 and 20 respectively (whether the 1.58 or 1.59 exponents are used) =[end background calculations]= so, back to the quantum issue, does this mean that if quantum computing ever becomes functional to where a 128 bit symmetrical cipher is feasibly attackable, then symmetrically encrypted messages, sda's, etc. using 10 diceware words or less, are similarly attackable? tia, vedaal -- Click to find great rates on medical insurance, save big, shop here http://tagline.hushmail.com/fc/CAaCXv1QS4cgSbayabBZZAAdxaOeMea0/ ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing (Robert J. Hansen)
please confirm if i have understood your post correctly to imply that if someone uses a straight diceware passphrase I'm not going to talk about this for three reasons. 1. I've never used Diceware, so I can't talk intelligently about it. 2. The answer will depend a lot on implementation details. What s2k algorithm is being used? What algorithm is used to encrypt the secret key? What... etc., etc. 3. I've already explained why quantum computing is not something we need to worry about. Be far, _far_ more concerned with the physical security of your machine more than any hypothetical developments in quantum computation. We tend to obsess over quantum computing. We shouldn't. At this point in time it's science fiction. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
Hi, On 200704181956, Robert J. Hansen wrote: Please bear with me. This is going to be long. Introductory cryptography in the middle of the night. Why would I miss it? :) Thanks for answering. As mentioned, Grover's is the best we can do for quantum speedups to brute-forcing. Grover's algorithm is a technique for using quantum mechanics to search through a database of N entries in time proportional to the square root of N, using an amount of storage proportional to the logarithm of N. Now, that said, Grover's has limits. Its first constraint is that it doesn't make problems trivial. It just increases our ability to deal with them. Brute-forcing a 128-bit cipher using a traditional computer is a ridiculous proposition, but using Grover's, it becomes as hard as brute-forcing a 64-bit cipher... hard, but possible. The executive summary being that increases in key sizes makes traditional symmetric cryptography keep up with advances in quantum computing, such as Grover's algorithm for searching the keyspace. Then... It would seem that quantum computers poses no threat to traditional cryptography -- helped by increases in key sizes...? Quantum computing poses no threat to symmetric cryptography. Asymmetric cryptography, however, gets a little funky. Shor's algorithm uses quantum mechanics to solve the integer factorization problem (and, I believe, the discrete logarithm problem) in extraordinary short time. The downside of Shor's is it requires an insane amount of memory--you need two qubits for each and every bit of the number you're trying to factor. So if you're trying to factor a 2048-bit RSA key, you need over four _thousand_ qubits. Our current largest quantum computer is about fifteen qubits. Which I also remarked in the original post. However, when (if?) commercial interests grab a hold of quantum computing, huge leaps in cost of production perhaps could be achieved, making memory-rich quantum computers abundant -- at least, from my chair, there's no obstruction to this future. (?) If and when quantum computing develops to the point where a research lab gets a couple of hundred qubits together, the OpenPGP working group will almost certainly add asymmetric algorithms that are highly resistant to quantum computing. Although this fight between attacking and defending computer security measures is probably inevitable -- no final solution will probably be found -- this pragmatism causes me to ponder the scenario in which something like Rice' theorem could be established for quantum computers' ability (or traditional computers' inability): Something that pops out of the blue and shatters all hope for traditional cryptography... Perhaps only in the long run, but still inevitably forces a move towards other measures of security. It's somewhat a political issue, too. Not that it can be solved politically, but it has political consequences -- will cryptography (or computer security in a more general sense) once again be for those who can afford it? -- But leave that be. For now, it's technical. You're asking a very, very detailed and technical question that requires a ton of disciplined study just to learn the language needed to describe the boundaries of the problem. If you really want to know this material, you need to take a graduate-level course in computational theory and a strong undergraduate course in quantum physics. You'll also need enough background in mathematics not to go running screaming from the room when people start talking about Hadamard matrices and discrete Fourier transforms and everything else that goes along with it. I'm already on it. Regards, skrewz. signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 Which I also remarked in the original post. However, when (if?) commercial interests grab a hold of quantum computing, huge leaps in cost of production perhaps could be achieved, making memory-rich quantum computers abundant -- at least, from my chair, there's no obstruction to this future. (?) Eh. I'm still unconvinced. It wasn't until last year that the final physics hurdle to large-scale QC was addressed (large systems have a strong tendency to near spontaneously decohere, turning your quantum computer into an expensive paperweight). We still have no idea how to apply this physics knowledge, however. Just knowing that something is possible doesn't mean the ability to do it is around the corner. We can teleport atoms in laboratories at the speed of light and we know how to do it for macro-scale items, but the engineering difficulties are so large that I doubt we'll see it in our lifetimes. While I agree that commercial development _may_ lead to developments in QC, I think it's equally likely that the engineering difficulties will be insurmountable. Which means that, from where I sit, we should just shrug and say we really can't say with any confidence what the future will or will not hold. found -- this pragmatism causes me to ponder the scenario in which something like Rice' theorem could be established for quantum computers' ability (or traditional computers' inability): What do you mean? Rice's theorem applies to QC. Computational theory is computational theory. We've already got very robust mathematics to describe the computational properties of QC. We know that BQP is a superset of P, that it does not encompass NP- COMPLETE, that it has some overlap with NP, etc., etc. It's true that in mathematics there could always be a proof delivered tomorrow by some hungry graduate student which will utterly shatter our knowledge of math as we know it. But this is true for all of mathematics. It's not as if this risk is special to QC. You should be just as concerned about the prospect of P=NP. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (Darwin) iQEcBAEBCgAGBQJGKAhmAAoJELcA9IL+r4EJPM4H/3lBPfZa9Uo+86whHTtKX2Vi Y7tm/jXSdy0JVCXXjpOfl8tlb7vllX7OeG2PzCwjX8mbn20OaaEFccBLSRhKga00 YBKB6xdcaXtPDBHVq/bgFO2wFQyc77xdpdd6Uoem34OCx8H65XC/4N+pgvTC0LDj JkAGVaAABaCKwS4wIWrVNiFZRpVfuXDYx6QTaAWw789vDmVR3I06elbYVYHANnr4 R7KzTl+Y46qp2XMoKSLBore+xrvjqdailkMYP97D7rsYyCE5V3CtntoUYMerMiWy DgXjHR/kM06Ja1jaOTu4SKstE1zJjMGgHwj3qeCLgqvijiiuTmSYVdvhjMU4ROE= =wy/G -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On 4/18/07, Anders Breindahl [EMAIL PROTECTED] wrote: However, I assume you know what you talk about, when you say that we aren't likely to factor 256-bit-numbers ever. So please restate that -- even in the face of quantum computers -- we won't ever factor 256 bit numbers. By the way, I realize that this is a more general question of gnupg's life expectancy in a quantum computer world. But it's interesting to get answered. Robert was referring to a 256-bit key space, which refers to symmetric encryption, such as AES, Factoring, on the other hand, applies only to public-key RSA encryption. There bits mean something totally different; a bit of RSA key length is worth less than a bit of symmetric key length. Numbers have already been factored in the ~600 bit range, so at least 1024 bits are recommended for RSA, and 2048 bits is a good idea. The keyspace size of RSA is roughly equivalent to the O(exp(64/9b)^(1/3)(log b)^(2/3)) that you quote; That is the number of operations that must be performed to break the algorithm by brute force. For strong symmetric algorithms,like AES or Twofish, the number of operations required is simply two to the power of the number of bits in the key, Note that breaking Diffie-Hellman and other discrete logarithm based algorithms is thought to be nearly equivalent to factoring, but has not been proven to be so. I suggest you borrow a copy of Bruce Schneier's _Applied Cryptography_; it is a very good primer. Regards, Ryan ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 Note that breaking Diffie-Hellman and other discrete logarithm based algorithms is thought to be nearly equivalent to factoring, but has not been proven to be so. Going off the top of my head, the DLP is known to be greater than or equal to the difficulty of the IFP. You can make strong arguments that they're equal difficulty in a computational-theoretic sense, and you can make strong arguments that in real silicon DLP will be stronger due to our current lack of understanding of how to efficiently use the general number field sieve for the DLP. The current state of the art in the GNFS requires a large amount of storage overhead for the DLP, while the storage overhead for the IFP is comparatively minimal. As a word of warning, comparing DLP to IFP is a spectacularly black art. There are so many nuances to it that just expressing some of the ideas in English is difficult. As further warning: it's 9:10am, I haven't yet had my morning cup of coffee, and I'm working without my references. This being the internet, there's also a nonzero chance that I'm barking mad. Confirm this information before relying on it. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.7 (Darwin) iQEcBAEBCgAGBQJGJierAAoJELcA9IL+r4EJSgoH/jz2SyN/4ZfAsnoJossJn6cp /b/CND53iaqPnIv6vKcjDNfseBYdp2ZRHTZPw1ZVhd9+zdUwKr8IfVmFh8+XA/Ra ayEnbf/OzfVw+VK9nSJfvroHBZnW/UQYFkwFsCpwYpXLDSab1JjNPV1Ys67lqx3e gnM2w0fjDoXwE0hI+InCceL+bptOIpZL+xQN3AgYRovsUGG5rwngjOPk31+5SCFV iMe1msmNhOV8KWcIkOFHeRZQxHKMtDVoZfSnv7BLYh4Ufh/moNDpIF9RI1/JuwJI 5eSXPEAzNAOXSxqyyrd5YC9ykMxMss69/BD7I6yfBQxHCcskUBjDsynxjLg+2NQ= =Qxyo -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Quantum computing
On Wed, Apr 18, 2007 at 09:10:17AM +0200, Anders Breindahl wrote: On 200704172359, Robert J. Hansen wrote: 1. We are unlikely to ever be able to brute-force a 256-bit keyspace. Ever. Not until computers are made of something other than matter, occupy something other than space, run on something other than energy, according to rules other than physics. I was under the impression that quantum computers were about to provide a break in factorization. From quick grep on Wikipedia, I find that: Robert was commenting on a symmetric cipher (like AES), not asymmetric (like RSA). Factoring a 256-bit RSA key is trivial and can be done on regular home PCs in fairly short order. However, factoring is not an attack against symmetric ciphers. My favorite comment (from Jon Callas at PGP, Inc) about brute forcing keys is one I think I've posted here before, but still: Modern cryptographic systems are essentially unbreakable, particularly if an adversary is restricted to intercepts. We have argued for, designed, and built systems with 128 bits of security precisely because they are essentially unbreakable. It is very easy to underestimate the power of exponentials. 2^128 is a very big number. Burt Kaliski first came up with this characterization, and if he had a nickel for every time I tell it, he could buy a latte or three. Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years. If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking. Note that he's talking about brute-forcing keys here. If someone finds a weakness in AES (or whatever), then this math may change radically. Pure brute-forcing without such a weakness is just not viable. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
