Re: Recommended key size for life long key
On 9/9/2013 3:03 AM, John Clizbe wrote: Several minutes to verify a signature makes such large key sizes non-starters. Folks using a baseline of a 1GHz cellphone seem to have no idea of the lifetimes involved in MIL-SPEC equipment. I'm sure there are some 1 MIPS VAX 11/780s still in military service somewhere. /MAYBE/ the 233Mhz hardened Pentium chips have been decommissioned by now. As a data point on that one: the 80386 production line shut down in 2007 after 22 years of production. It ran at a top speed of 25MHz, but was more frequently undervolted to enhance lifetime at the cost of reducing it to 16MHz. Today it's still a commonly embedded processor. For those who wonder why the 386 has survived even into the present day, it mostly has to do with legacy support and recertification costs. If you have a piece of Assembly from '86 that works just fine and which you paid a lot of money to develop and get certified for use in a certain environment running on x86 hardware, you will probably be very reluctant to hire the developers, pay for the re-engineering expense, and pay for the recertification expense, in order to get your application to run on a modern-day StrongARM. The embedded 80386 may be slow and antiquated, but it's *cheap*, and lets you leverage your existing resources. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/8/2013 6:25 PM, Doug Barton wrote: he seems to have studiously ignored all of the facts that point to why what he's trying to do is a bad idea. Nitpick: I think what he's trying to do (make credible, accurate long-term projections) is a good idea. I just think he's going about it in a way that will not give credible or accurate answers, and that as a result his write-up is rubbish. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/9/2013 5:27 AM, Peter Lebbing wrote: [1] https://en.wikipedia.org/wiki/Bald_man_paradox Heh. I always heard that as the beard paradox. Same basic idea, except the example given involves beards instead of full heads of hair. :) At age thirty-eight, I'm beginning to develop a bit of gray in my facial hair. I guess that I can now legitimately call myself a graybeard... ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/9/2013 4:27 AM, Doug Barton wrote: If what you meant was, It's important for knowledgeable people to examine how long various key sizes can be expected to remain secure More like, it is good that key lengths and their expected lifetimes be subjected to rigorous study, with a soupcon of but that write-up is very much lacking in rigor. I personally don't like phrasing things in terms of knowledgeable people. There's a joke I like to tell -- === A mathematician, an economist and a physicist are traveling through Great Britain via rail. The physicist looks out the window and sees an animal grazing in a meadow. Look! the physicist exclaims. In Scotland, sheep are brown! The economist pooh-poohs this. You're generalizing. All you've proven is that in Scotland there exists at least one brown sheep. The mathematician rolls his eyes. Not even that. All he's proven is that in Scotland there exists at least one sheep that has at least one brown side. A fellow passenger on the train looks quizzically at the three, then shares: We're in Wales, and around here we call them 'cattle'. === Knowledgeable people get things wrong all the time, and especially when they say trust me, I'm knowledgeable. I trust in process instead -- I trust in rigor and logical development of thoughts and ideas to reach a conclusion. If I review the process and feel that it's valid, then it doesn't matter if the person presenting the idea is a Ph.D. or is in the eighth grade. :) I suspect, though, that we are overall in violent agreement. :) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sun, Sep 8, 2013 at 12:06 AM, Ingo Klöcker kloec...@kde.org wrote: On Saturday 07 September 2013 23:35:08 Ole Tange wrote: On Sat, Aug 31, 2013 at 11:46 AM, Ole Tange ta...@gnu.org wrote: : http://oletange.blogspot.dk/2013/09/life-long-key-size.html : but I'm pretty sure it's relevant for the battery life of your and your communication partners' smart phones. In particular, if you and your communication partners use equally large keys and encrypt each and every email, SMS, chat message, etc. Assuming a new smartphone runs at 1 GHz with GnuPG 2.0 then decryption+verify or sign+encryption will be in the order of 10 seconds if both sender and receiver use 10kbit keys. So we are talking about 10 seconds per RSA encrypted message. Potentially lower if the phone is multicore and GnuPG's RSA implementation supports parallelized RSA operations. If RSA is only used to negotiate the initial session key, then I would reckon the 10 seconds is hardly noticeable from a battery perspective. My old Nokia N900 with wifi on will let you sign+encryption 657 messages with 10kbit keys on a full battery using GnuPG 1.4.6. With GnuPG 2.0 that would be in the order of 1000 messages per charge. So where your concern really matters would be for high volume messages (100 per day or more) that are all RSA encrypted and are used on battery operated slow devices. Apart from email, can you mention any app that works like that today? If I am to include the battery perspective and speculations on what apps that _could_ be made, I should probably also include what would happen if smartphones get a cryptochip included (which would bring RSA operations into the millisecond range - thus rendering the battery concern moot). /Ole ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sun, Sep 8, 2013 at 1:53 AM, Robert J. Hansen r...@sixdemonbag.org wrote: On 9/7/2013 5:35 PM, Ole Tange wrote: Feel free to let me know if you feel I have left out important concerns. : You're projecting 87 years into the future. Why should we have any confidence in your analysis? The short answer: You do not have to trust projection to use the other findings. If you have a better projection, use that instead. The projection is based on www.win.tue.nl/~klenstra/key.pdf but I think you are completely missing the point: The projection is not some sort of guarantee that 10kbit keys will not be broken before 2100 (which is stressed by using the phrase 'It should be stressed that this is only a guess'), but simply to give an estimate on what key size we cannot given our knowledge _today_ say will be broken for sure. Even if the guess proves to be wrong it will still be better than 4kbit which seems fairly likely to be broken by 2100 (at least if no attack is found that renders RSA completely useless). If you can come with a better supported guess for the key length, that would be great. Based on the guess that 10kbit has the potential of not being broken within a person's life span: What problems would you experience if you chose to use a 10kbit key today instead of a 4kbit key (which seems to be the common choice - but which we are fairly certain will be broken before 2100)? THIS (i.e. the problems by using 10kbit today instead of 4kbit) being the focus of the document. So if you are focusing on the projection of the key size, help me rephrase the text so you do not focus on that, because that has never been the intended focus of the document. There are a large number of other errors in your write-up, but those two questions above are the most critical shortcomings. Having now addressed that question, please elaborate what other errors you find. /Ole ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/8/2013 4:32 AM, Ole Tange wrote: The short answer: You do not have to trust projection to use the other findings. If you have a better projection, use that instead. I do, actually. If I see that a major part of your write-up is seriously lacking in rigor, that causes me to suspect the rest of your write-up is similarly lacking. this is only a guess'), but simply to give an estimate on what key size we cannot given our knowledge _today_ say will be broken for sure. We can't be sure 2048-bit keys will be broken by 2100. Likewise, it's within the realm of possibility 4096-bit keys will be broken tomorrow. Factoring/discrete-log technology has stalled out for the last 20-odd years after some very promising periods in the late-80s and early-90s. The dominant technology used today is the General Number Field Sieve, which was first developed around 1993. This shouldn't really surprise us. Factoring is *hard*. It's provably an NP problem, which means that (assuming P!=NP) there will never, ever, ever, be an efficient algorithm for it [1]. We've been looking for efficient ways to factor ever since Eratosthenes; it is quite likely there simply isn't one. So on the one hand, focusing on advances in factoring technology is suspect. And on the other hand, you're completely ignoring the possibility of vast advances in other areas of number theory. A couple of years ago Dan Boneh published a paper that rocked a lot of people's worlds to the core: he proved that *breaking RSA is not equivalent to factoring* [2]. The RSA Conjecture (breaking RSA is equivalent to factoring) is *false*. Wow. And since the long-term security of RSA is predicated on the RSA Conjecture, and the idea there's no other way to attack RSA than by factoring... along comes Dan Boneh and opens the door to the possibility of there existing many other mathematical ways to attack RSA. Some of them will undoubtedly be worse than factoring. Some of them may be better. It's possible one of them might even be in P. And how do we project for the future when we cannot predict if, when, one of these Boneh approaches will be developed? I am not even scratching the surface of the difficulties involved in long-term prediction. I know exactly where my limitations lie in making long-term predictions. I doubt you have a better look on the future than I do -- and given your write-up doesn't even address the factors that make long-term prediction difficult, I have no confidence whatsoever in your 87-year projection. [1] An efficient *classical* algorithm for it. Although factoring is in NP, it's also in BQP, which means efficient quantum algorithms exist. [2] http://crypto.stanford.edu/~dabo/abstracts/no_rsa_red.html Further: By 2100, I expect some kind of quantum computation to exist. 87 years is a long time for technology: it took us fewer than seventy years to go from the first airplane flight to Armstrong's first steps on the Moon. It took fewer than thirty-five years to go from ENIAC to the Apple II. Quantum computing, if-and-when it appears in a large scale (hundreds or more of qubits in an ensemble), will transform our society in ways that are hard to imagine. It is literally science fiction technology. Right now, two of the few things we know for a fact is that quantum computers will be able to efficiently factor large composites and compute discrete logarithms in finite fields. That means RSA and Elgamal are both out the window the instant quantum computing becomes a possibility. Your write-up barely mentions the possibility of quantum computing, and says nothing of the consequences should it come to pass. Even just an I arbitrarily project that quantum computing will become possible in 2050 and mainstream by 2060 would be better, because at least you've drawn a line on the map and said beyond 2060 there be dragons, and the world will be radically unpredictable. What do I mean by radically unpredictable? Imagine that you're an academic in the early 1930s, and you're working on an estimate of how much computation humanity has done. You bury yourself in studies of how many computers (remember, in the 1930s, computer was an occupation) there are today, how much growth there has been for the field, how many there were in the past, and you project dramatic exponential growth for the profession of computing. Then along comes ENIAC which, in the first fifteen minutes of its operation, did more computing than had been performed in the whole of human history up to that point. All of your estimates are immediately null and void because the future has bushwhacked you. *The very first quantum computer with more than two hundred qubits will, in its very first calculation, do more computation than has been done by all the world's computers from 1945 to the present.* Anyone who attempts to predict the future of computing past the introduction of quantum elements is either (a) a science fiction author or (b) living in sin.
Re: Recommended key size for life long key
On Sunday 08 September 2013 10:29:18 Ole Tange wrote: On Sun, Sep 8, 2013 at 12:06 AM, Ingo Klöcker kloec...@kde.org wrote: On Saturday 07 September 2013 23:35:08 Ole Tange wrote: On Sat, Aug 31, 2013 at 11:46 AM, Ole Tange ta...@gnu.org wrote: http://oletange.blogspot.dk/2013/09/life-long-key-size.html but I'm pretty sure it's relevant for the battery life of your and your communication partners' smart phones. In particular, if you and your communication partners use equally large keys and encrypt each and every email, SMS, chat message, etc. Assuming a new smartphone runs at 1 GHz with GnuPG 2.0 then decryption+verify or sign+encryption will be in the order of 10 seconds if both sender and receiver use 10kbit keys. So we are talking about 10 seconds per RSA encrypted message. Potentially lower if the phone is multicore and GnuPG's RSA implementation supports parallelized RSA operations. If RSA is only used to negotiate the initial session key, then I would reckon the 10 seconds is hardly noticeable from a battery perspective. My old Nokia N900 with wifi on will let you sign+encryption 657 messages with 10kbit keys on a full battery using GnuPG 1.4.6. With GnuPG 2.0 that would be in the order of 1000 messages per charge. So where your concern really matters would be for high volume messages (100 per day or more) that are all RSA encrypted and are used on battery operated slow devices. Apart from email, can you mention any app that works like that today? Some chat software (on PCs) uses GnuPG for encryption, but I'm not sure whether they use RSA only for the initial key exchange or for every chat message. Not having a smart phone I have no idea whether there are similar apps for smart phones. Having said this, in view of Snowden's disclosures, there's definitely a need for such apps. If I am to include the battery perspective and speculations on what apps that _could_ be made, I should probably also include what would happen if smartphones get a cryptochip included (which would bring RSA operations into the millisecond range - thus rendering the battery concern moot). Using a cryptochip might not only render the battery concern moot, but this whole discussion about life long keys because even a 1mbit RSA key is useless if the session keys created by the cryptochip are easily guessable by the NSA. Regards, Ingo signature.asc Description: This is a digitally signed message part. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
Am So 08.09.2013, 11:07:21 schrieb Robert J. Hansen: Once more I feel enlightened (and I am sure I am not the only one). From time to time it seems appropriate to me that someone says thank you. So this time I do that. -- Crypto für alle: http://www.openpgp-schulungen.de/fuer/bekannte/ OpenPGP: 7D82 FB9F D25A 2CE4 5241 6C37 BF4B 8EEF 1A57 1DF5 signature.asc Description: This is a digitally signed message part. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
Hi On 09/08/2013 05:07 PM, Robert J. Hansen wrote: On 9/8/2013 4:32 AM, Ole Tange wrote: The short answer: You do not have to trust projection to use the other findings. If you have a better projection, use that instead. (...) We can't be sure 2048-bit keys will be broken by 2100. Likewise, it's within the realm of possibility 4096-bit keys will be broken tomorrow. Interesting comment for a sworn enemy of longer then default/hardcoded key length :) (no provocation or trolling intended Robert) Citing B. Schneier: (...) If we think that's the case, the fix is easy: increase the key lengths.* Factoring/discrete-log technology has stalled out for the last 20-odd years after some very promising periods in the late-80s and early-90s. The dominant technology used today is the General Number Field Sieve, which was first developed around 1993. This shouldn't really surprise us. Factoring is *hard*. It's provably an NP problem, which means that (assuming P!=NP) there will never, ever, ever, be an efficient algorithm for it [1]. We've been looking for efficient ways to factor ever since Eratosthenes; it is quite likely there simply isn't one. (...) After Mr Schneier again: Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily.** And one more time: If we think that's the case, the fix is easy: increase the key lengths.* *, ** - https://www.schneier.com/blog/archives/2013/09/the_nsas_crypto_1.html Regards, Filip M. Nowak ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 As must I. Robert has one of the clearest modes of exposition from which I have ever been fortunate to benefit. - --Avi -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.21 (MingW32) Comment: Most recent key: Click show in box @ http://is.gd/4xJrs iL4EAREIAGYFAlIszFZfGGh0dHA6Ly9rZXlzZXJ2ZXIudWJ1bnR1LmNvbS9wa3Mv bG9va3VwP29wPWdldCZoYXNoPW9uJmZpbmdlcnByaW50PW9uJnNlYXJjaD0weDBE NjJCMDE5RjgwRTI5RjkACgkQDWKwGfgOKflqQgD/cj8FdidQyWj3UqZ9kEjPnzTd bzXp1b3hIAgpeUiGV7oA/jIQoveP0PBnNG773wyN/WaQtATIbKHKDyV9B9wUHTwu =+VfZ -END PGP SIGNATURE- User:Avraham pub 3072D/F80E29F9 1/30/2009 Avi (Wikimedia-related key) avi.w...@gmail.com Primary key fingerprint: 167C 063F 7981 A1F6 71EC ABAA 0D62 B019 F80E 29F9 On Sun, Sep 8, 2013 at 12:55 PM, Hauke Laging mailinglis...@hauke-laging.de wrote: Am So 08.09.2013, 11:07:21 schrieb Robert J. Hansen: Once more I feel enlightened (and I am sure I am not the only one). From time to time it seems appropriate to me that someone says thank you. So this time I do that. -- Crypto für alle: http://www.openpgp-schulungen.de/fuer/bekannte/ OpenPGP: 7D82 FB9F D25A 2CE4 5241 6C37 BF4B 8EEF 1A57 1DF5 ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 09/08/2013 04:02 PM, Filip M. Nowak wrote: [snip] Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily.** I would think the NSA would have two teams, that might work together at times. One is interested in breaking the encryption of those they deem to be enemies. The other is making encryption mechanisms that are as difficult to break as they know how, for the use of our own secret services, state department, and so on. So perhaps the snooping division is pushing elliptic curve technology because they have a technique for breaking those that they have not published and that has not yet been leaked. But the other division is developing some superior technique, such as hyperbolic curves (I made that name up; it has nothing to do with reality) that is at least an order of magnitude more difficult to break. For use by any government agency that has secrets to keep but must communicate from place to place, or from time to time. Some might need public key encryption methods, some might manage with symmetric key methods. -- .~. Jean-David Beyer Registered Linux User 85642. /V\ PGP-Key:166D840A 0C610C8B Registered Machine 1935521. /( )\ Shrewsbury, New Jerseyhttp://counter.li.org ^^-^^ 16:55:01 up 10 days, 23:40, 3 users, load average: 4.76, 4.43, 4.30 ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sun, Sep 08, 2013 at 03:15:24PM -0400, Avi wrote: As must I. Robert has one of the clearest modes of exposition from which I have ever been fortunate to benefit. I have to agree on this point. The issue is that I disagree with him on his stance : in my opinion, having a schedule stating when the keylengths will become insecure is useless : we just have to be able to predict that longer keys will most likely be at least as hard to crack. And this means that, as long as the drawbacks associated with the use of the key are assumed by the key owner only (as the tables state, encrypt and verify operations being almost unchanged in time), preconizing 10kbit RSA keys is no issue, and can only improve overall security, to the key owner's usability's detriment at most. And each key owner might choose whatever keylength they feel best suits them, according to their usability / security needs ; as long as these choices do not impede other keyholders' usability or security. BTW, the statement [Dan Boneh] proved that breaking RSA is not equivalent to factoring is wrong : he did not prove that breaking RSA is easier than factoring numbers ; only that a whole ways of proving that breaking RSA is as hard as factoring numbers are ineffective ; thereby reducing the search space for potential valid ways of proving the conjecture. Hence the title of the article : Breaking RSA *may* not be equivalent to factoring. Please pardon me if I misunderstood the english used in the abstract. Oh, and... Please correct me if I am mistaken, but I believe the best we can do at the moment, even with a quantum computer is Shor's algorithm, taking a time of O(log^3 n). Thus, going from 2k keys to 10k keys makes if approx. 125 times harder to break. Sure, not so wonderful as what it is today, but if the constant is large enough (which, AFAIK, we do not know yet), it might be a practical attack infeasible for a few more years. So, back to the initial question, I do not understand why the article should be judged so poor. No, to me the article is not about predicting 87 years in front of us. To me, the article is about stating that using 10k RSA keys is not as bad as one might think at first. The gist of the article is, to me, precisely this set of tables. And the first part is, still in my opinion, only here to explain why 10k RSA keys were chosen for the experiment. Explaining that, according to our current estimates, they might potentially resist until 2100, assuming no major breakthrough is made until then in the cryptanalysis field. You might notice that such precautions are taken in the article too. So... I find the article interesting. I would not have thought everyday use of a 10k key would have so little drawbacks. And, finally, I want to recall that signing keys need not be the same as certifying key, thus allowing us to lose the signature time only for certifications, and use normal keys the rest of the time ; thus getting the best of both worlds, by being able to upgrade signing keys to stronger ones without losing one's WoT. The only remaining drawback being when others certify our master key. Cheers, Leo ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 09/08/2013 02:00 PM, Leo Gaspard wrote: And this means that, as long as the drawbacks associated with the use of the key are assumed by the key owner only (as the tables state, encrypt and verify operations being almost unchanged in time), preconizing 10kbit RSA keys is no issue, and can only improve overall security, to the key owner's usability's detriment at most. The problem here is the knowledge sieve issue. Ole asked some questions and did some research, then filtered what he got back through a mixture of his preconceived notions, desires, etc. I'm not saying that he picked only the data that agreed with his desired conclusion, but he seems to have studiously ignored all of the facts that point to why what he's trying to do is a bad idea. Now the next reader is going to come along, very likely someone who is more naive about encryption than Ole is, and filter that blog post through his own preconceptions, impatience, etc.; and come to the conclusion, If I make a 10k key it'll be safe for life! Has Ole done this reader a disservice? I think the biggest disservice is a false sense of security. If your attacker can only pole vault 10 meters, and you already have a fence 1,000 meters high, does a 100,000 meter fence make you any more secure? And what happens if your attacker develops a technique that is universally effective against all fences, no matter the height? The flip side question is, What harm is there to using a 10k key? Aside from CPU and storage for the user of the key, everyone else in the community bears part of the cost when they have to verify a signature on an e-mail, for example. Is that a serious enough problem to cause us to wish no one would suggest the use of 10k keys? I don't know. ... and all of this is presupposing that his only a guess has any validity to it at all. I don't know the work by Arjen K. Lenstra and Eric R. Verheul that he based his graph on, and I have no idea if Ole's method of projecting key sizes out into the future is valid. What I DO know (and Robert emphasized this point in his first post), is that those authors, and other serious heavyweights in the crypto community have not felt comfortable doing what Ole has done. That fact alone should be enough reason for anyone not to take Ole's blog post seriously. Doug ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/8/2013 5:00 PM, Leo Gaspard wrote: BTW, the statement [Dan Boneh] proved that breaking RSA is not equivalent to factoring is wrong : he did not prove that breaking RSA is easier than factoring numbers ; only that a whole ways of proving that breaking RSA is as hard as factoring numbers are ineffective ; thereby reducing the search space for potential valid ways of proving the conjecture. Hence the title of the article : Breaking RSA *may* not be equivalent to factoring. Please pardon me if I misunderstood the english used in the abstract. From the abstract, We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers ... an oracle for breaking RSA does not help in factoring integers. The title involves the word 'may' out of an abundance of caution and a decent respect for the opinions of the mathematical community. Whether he's proven it or not is not really for him to claim, but for the mathematical community. He's provided a conjecture and strong evidence to support it, and I feel his conjecture is well-proven. Your mileage may vary. :) Oh, and... Please correct me if I am mistaken, but I believe the best we can do at the moment, even with a quantum computer is Shor's algorithm, taking a time of O(log^3 n). Thus, going from 2k keys to 10k keys makes if approx. 125 times harder to break. A factor of 125 is so small as to be irrelevant. The real obstacle is that Shor's algorithm requires 2n qubits to be formed in an ensemble, so you'd be going from requiring a 4k quantum computer to a 20k quantum computer. Given decoherence, that might amount to a much more insurmountable obstacle. Still, my money is on QC. And the first part is, still in my opinion, only here to explain why 10k RSA keys were chosen for the experiment. Explaining that, according to our current estimates, they might potentially resist until 2100, assuming no major breakthrough is made until then in the cryptanalysis field. The problem is the exact same thing can be said for RSA-2048. RSA-2048 is expected to last at least the next 25 years; it may last for the next century. Hard to say. Depends a lot on the progression of science fiction level technologies, like quantum computation. And again, anyone trying to predict out past about 25 years needs to explain why they are able to do this where NIST, RSA Data Security, and so many others have failed to be able to do this. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sat, Aug 31, 2013 at 11:46 AM, Ole Tange ta...@gnu.org wrote: : Why not recommend a key size that will not be broken for the rest of your natural life? Thanks for all your feed back on the list. I have now summed up the concerns raised on the list on http://oletange.blogspot.dk/2013/09/life-long-key-size.html Feel free to let me know if you feel I have left out important concerns. /Ole ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Saturday 07 September 2013 23:35:08 Ole Tange wrote: On Sat, Aug 31, 2013 at 11:46 AM, Ole Tange ta...@gnu.org wrote: Why not recommend a key size that will not be broken for the rest of your natural life? Thanks for all your feed back on the list. I have now summed up the concerns raised on the list on http://oletange.blogspot.dk/2013/09/life-long-key-size.html Feel free to let me know if you feel I have left out important concerns. I see you have checked the influence of large keys on the CPU time needed to do key operations on different hardware. But key operations with large keys not only cost lots of time (see your numbers on low end hardware), but also energy. The additional energy consumption might not be relevant ecologically, but I'm pretty sure it's relevant for the battery life of your and your communication partners' smart phones. In particular, if you and your communication partners use equally large keys and encrypt each and every email, SMS, chat message, etc. Obviously, those concerns might be irrelevant in pratice (e.g. because nobody uses encryption anyway). Regards, Ingo signature.asc Description: This is a digitally signed message part. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 9/7/2013 5:35 PM, Ole Tange wrote: Feel free to let me know if you feel I have left out important concerns. The good news is that you are not your ideas. Whether your ideas are good or bad has nothing to do with your worth as a person. A great paper won't make you a good human being -- I've known some true geniuses who are terrible people -- and a bad paper doesn't make you stupid, inferior, or bad. Now for the bad news: it's rubbish. NIST, RSA Data Security, Lenstra and Schneier (just to name four) have been extraordinarily careful about their long-term recommendations. None of them have been willing to project beyond about 25 years in the future. They have all shared their reasoning for their circumspection and detailed the factors that make long-term prediction difficult. You're projecting 87 years into the future. Why should we have any confidence in your analysis? In my opinion, you very much need to address two questions right off: 1. What factors have prevented NIST, RSA Data Security, Lenstra, Schneier, et al., from being able to make an 87-year prediction? 2. Why do these factors not apply to your analysis? Without those two questions being raised directly and immediately, there is no reason for a reader to have any confidence in what you've written. It is far more likely that you are limited by the same factors that have limited NIST, RSA Data Security, Lenstra, Schneier, et al., and are simply not aware of how those factors are confounding your analysis. There are a large number of other errors in your write-up, but those two questions above are the most critical shortcomings. Without answers to those two questions I can see no reason for anyone to take your writeup seriously. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
I just use 4096 bit because that is the biggest size my OpenPGP Cards can handle. In my opinion using a smart card instead of online keys increase security far more than strange large key sizes! I also see no point using less than 4096 because modern hardware is fast enough. Maybe my keys last longer that way. Am 01.09.2013 02:43 schrieb Robert J. Hansen r...@sixdemonbag.org: On 08/31/2013 05:46 AM, Ole Tange wrote: The FAQ http://www.gnupg.org/faq/GnuPG-FAQ.html#what-is-the-recommended-key-size recommends a key size of 1024 bits. Reading http://www.keylength.com/en/4/ I am puzzled why GnuPG recommends that. It shouldn't; NIST recommends 2048 bits for 20 years of security. NIST notably makes no recommendations past 20 years, as they are deeply skeptical of their ability to forecast out that far. I suspect your ability is no greater than theirs is, so I'd be very careful about declaring a 10K key to be greater than your natural lifespan. Per NIST, a 2048-bit key is of comparable difficulty to breaking 3DES. Given the tremendous level of confidence people have in the long-term suitability of 3DES, I am convinced a 2048-bit key will outlast my ability to remember the passphrase to it. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sun, Sep 1, 2013 at 12:12 PM, Josef Schneider jo...@netpage.dk wrote: I just use 4096 bit because that is the biggest size my OpenPGP Cards can handle. In my opinion using a smart card instead of online keys increase security far more than strange large key sizes! I also see no point using less than 4096 because modern hardware is fast enough. Maybe my keys last longer that way. One of the problems that this kind of discussion highlights is that moving to new keys is a real pest. People keep keys long after they really should and are reluctant to change keys because getting a given key certified and trusted is a pain - even with the web of trust. In a more ideal world, no one would want a key to last longer than a few years, and replacing keys at regular intervals would be the norm. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Sun, Sep 01, 2013 at 01:18:12PM +0100, Nicholas Cole wrote: On Sun, Sep 1, 2013 at 12:12 PM, Josef Schneider jo...@netpage.dk wrote: I just use 4096 bit because that is the biggest size my OpenPGP Cards can handle. In my opinion using a smart card instead of online keys increase security far more than strange large key sizes! I also see no point using less than 4096 because modern hardware is fast enough. Maybe my keys last longer that way. One of the problems that this kind of discussion highlights is that moving to new keys is a real pest. People keep keys long after they really should and are reluctant to change keys because getting a given key certified and trusted is a pain - even with the web of trust. In a more ideal world, no one would want a key to last longer than a few years, and replacing keys at regular intervals would be the norm. I carried a 1024 bit key for 5 years (2004-2009). For me it was easy to change over to newer size in 2009 because never been able to get my key signed. Next set made use of sub keys, in hopes of futur getting them signed, and just using bigger/better sub keys as need arose. Alas, 5 years later and still not found any other gpg uses so no signatures. Wolf signature.asc Description: Digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 09/01/2013 02:45 PM, Johan Wevers wrote: Why? What's the advantage of that? I replace keys after I they have a chance of being compromised, but not before. Same for my mail domain - I created a ssh certificate that is valid for 50 years (unlimited was not an option) and I'll replace it whan I fear intrusions or crypto breakthroughs make it unsecure. Not before. The longer a key is in use the greater the chance of compromise. Just because you believe it has not been compromised doesn't make it so. By regenerating keys every so often you drastically lessen the chances of a key being compromised or of a possible compromise having as much effect on you. There is a reason things like IPSEC keys are renegotiated after so many minutes or after so many bytes are transmitted. :) -- Larry Brower, CCNA Fedora Ambassador - North America Fedora Quality Assurance lbro...@fedoraproject.org http://www.fedoraproject.org/ 0x0806CF8B.asc Description: application/pgp-keys ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 1-9-2013 14:18, Nicholas Cole wrote: In a more ideal world, no one would want a key to last longer than a few years, and replacing keys at regular intervals would be the norm. Why? What's the advantage of that? I replace keys after I they have a chance of being compromised, but not before. Same for my mail domain - I created a ssh certificate that is valid for 50 years (unlimited was not an option) and I'll replace it whan I fear intrusions or crypto breakthroughs make it unsecure. Not before. Your advice makes me think of company password policies where you have to change it every month, leading to passwordprefix01, passwordprefix02, ..., passwordprefix12. Complete waste of effort. -- 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
Recommended key size for life long key
The FAQ http://www.gnupg.org/faq/GnuPG-FAQ.html#what-is-the-recommended-key-size recommends a key size of 1024 bits. Reading http://www.keylength.com/en/4/ I am puzzled why GnuPG recommends that. Why not recommend a key size that will not be broken for the rest of your natural life? (Assuming the acceleration of advances in key breaking remains the same as it has done historically, thus no attack is found that completely destroys the algorithm used). I just generated a 10kbit RSA key. It took 10 minutes which is long to sit actively waiting, but not very long if you are made aware it will take this long and just leave it in the background while doing other work; and to me 10 minutes (or even 10 hours) is a tiny investment if that means that I do not loose the signatures on my key by changing key every 5 years. /Ole (Please Cc any answer) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On Saturday 31 August 2013 11:46:31 Ole Tange wrote: The FAQ http://www.gnupg.org/faq/GnuPG-FAQ.html#what-is-the-recommended-key-s ize recommends a key size of 1024 bits. Reading http://www.keylength.com/en/4/ I am puzzled why GnuPG recommends that. Why not recommend a key size that will not be broken for the rest of your natural life? (Assuming the acceleration of advances in key breaking remains the same as it has done historically, thus no attack is found that completely destroys the algorithm used). I just generated a 10kbit RSA key. It took 10 minutes which is long to sit actively waiting, but not very long if you are made aware it will take this long and just leave it in the background while doing other work; and to me 10 minutes (or even 10 hours) is a tiny investment if that means that I do not loose the signatures on my key by changing key every 5 years. Now try sending a message signed with this key to yourself. And then try verifying the signature on this message. And then imagine doing the same on a mobile phone with a processor that is 10 times slower than that of your PC. I'm pretty sure that this will make you realize that a 10kbit RSA key is a PITA for everybody, for you when you sign messages or other people's keys and for others when they need to verify your signatures. Once you've realized this you might understand the recommendation in the FAQ. BTW, the FAQ recommends creating a 1024 bit DSA key; IIRC this is more or less equivalent to a 2048 bit RSA key. Regards, Ingo signature.asc Description: This is a digitally signed message part. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 31-8-2013 11:46, Ole Tange wrote: Why not recommend a key size that will not be broken for the rest of your natural life? In that case, I assume 3072bit is sufficient. Making the public/secret key a little stronger than the session keys (128 bit for most symmetric ciphers) makes sense (breaking the secret key lets an attacker read all messages, breaking a session key only one so the pubkey is more valuable) but making it extremely much stronger is useless. Attackers will go for the weakest link in the chain. -- 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
Re: Recommended key size for life long key
-BEGIN PGP SIGNED MESSAGE- Hash: SHA512 On 08/31/2013 04:46 AM, Ole Tange wrote: The FAQ http://www.gnupg.org/faq/GnuPG-FAQ.html#what-is-the-recommended-key-size recommends a key size of 1024 bits. Reading http://www.keylength.com/en/4/ I am puzzled why GnuPG recommends that. Why not recommend a key size that will not be broken for the rest of your natural life? (Assuming the acceleration of advances in key breaking remains the same as it has done historically, thus no attack is found that completely destroys the algorithm used). I just generated a 10kbit RSA key. It took 10 minutes which is long to sit actively waiting, but not very long if you are made aware it will take this long and just leave it in the background while doing other work; and to me 10 minutes (or even 10 hours) is a tiny investment if that means that I do not loose the signatures on my key by changing key every 5 years. Hi Ole, There are other problems that need to be considered when creating a 'lifelong' extra large key. First, you need to consider people on older hardware or mobile devices. That 10k key might take 10 minutes to do anything with on modern hardware. But do you think a mobile device will have the kind of horsepower needed to use that key in any way? Probably not. That may lock out a significant portion of your contacts from being able to communicate with you. Secondly, a long key length won't protect you if 1) an incredibly efficient factoring algorithm is designed and used, 2) quantum computers are used against your key, or 3) side channel attacks. In all of those sceneries, large keys won't protect you at all. Especially in side channel attacks or qc attacks. Personally, I trust my 4096 bit key for now until ECC is integrated into GnuPG. Then, I'll recreate my keys. Looking for a key that will never be broken is like looking for the fountain of youth: it's a nice idea but not realistic to plan your life around. Security is always moving. You have to be prepared to move with it. Regards, Anthony - -- Anthony Papillion XMPP/Jabber: cypherp...@patts.us SIP: 17772471...@callcentric.com PGP Key: 0x53B04B15 -BEGIN PGP SIGNATURE- iQIcBAEBCgAGBQJSIlHEAAoJEAKK33RTsEsVCBEP/2iX/lCeUzr4XOfl9M2dKOYX Jmspl0/xUEuJ/pN8A+XXfH6Roe1HtO/sIDRxMB/yM6speLnvrfpin3lxLNh68IPW A5wkgIit61ERSpFFMw7oaaWViqZ9dz4qkm9FVA5b2WQBYJzC5jWu6t0vfJJgQIE3 PJHarT+Ok3tMPPZvDpOiC0dE0tTVmvod1O3mk5fOnbnCdXq1mIdy+cqM182t9pl2 lJWgJ4H6fsJsIYqUvC7MWJtNGXJ++8i3WySttoMbvOeVT+YyJk3/R/BetqRYxbuD qE4Clniu5l/NB/LtO7nmD4cziszU6WFZVKXft1pR8qnyFbItb/2vpA4g8PbM3m2W 4dbTGn5SA2ouF8glCukRjydeCeca1/jf/DQQ5w5DSnQegLwbH7FzORVQ79k7CyXV 4l6ulmLwrb5Jn7aw/GOukEqAjBQcaJjg1C5TjIAyfy+7yQye9nuoVRz3rf5JcOwx luu5KARLGcIyxCatrQPqydvr7FuNCH1oyLzvYTZ1qpRt5KI85bGqesTAh2ltiv/n BWEs2auasD62PxaneH8PurlPpdw5D+b6bxTs6QnKG90IhvIBfQqr/62DnkpK9D5f ImYbo6Z/pgzAqggtbXDlOEfmn9gr8g1egkNfrFei8EYSNLaNqTrQkumV9gX+RrHq zqszn5xP94iqkj1JFd9V =4t2X -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 08/31/2013 08:27 PM, Anthony Papillion wrote: Personally, I trust my 4096 bit key for now until ECC is integrated into GnuPG. Then, I'll recreate my keys. Looking for a key that will never be broken is like looking for the fountain of youth: it's a nice idea but not realistic to plan your life around. Security is always moving. You have to be prepared to move with it. And I was flamed for suggesting a 4096 bit key just a short six years ago. Currently I am using 2048R/2048R but I don't have top-secret needs. You should tailor your keys lengths and other factors to both yours AND OTHERS needs. The last time I checked I wasn't enciphering top-secret level embassy communiques. Make your keys to match their intended uses and part of that is what others can handle. But other than your key size maybe being too large for an iPhone (currently) all the rest of the advice you have given here is good. I noticed my previous 4096R/4096R did take a little bit of time and would not be appropriate for a person with s single core CPU so my current keys are 2048R/2048R so they can handle it. I especially like your fountain of youth analogy. It lets people know that there is no totally secure. There is only what is currently best for yours and others you communicate with needs. My main concern is that they don't upload those keys instantly to the key-servers after creating them. Play around with them for a while. Many people create keys with the following factors - no expire date - my current ones were for ten years but I can always revoke them if the key sizes finally become too small. They have lasted 2+ years now and I see no reason for them not to last at least another 3-5 years. But the day will come when they will no longer be adequate. There is no such thing as keys that can be used forever. - key sizes too large for THEIR needs and most especially for other people's needs. The key size really should be created to match OTHER people's needs more than yours. - passphrases that are either too short and simple or the opposite of being so long and and convoluted that even a top Jeopardy champion couldn't remember them. - no thought or knowledge of changing the preferences of their ciphers, digests and other factors. It isn't just the key sizes. http://www.securemecca.com/public/GnuPG/GnuPG_Prefs.txt - uploaded WAY too soon to the key-servers without playing around with them for a while. This last issue is CRITICAL. They just don't understand the need to play and think for a sufficiently long time. They want to use what they have with others immmediately. LEARN PATIENCE! - don't immediately generate a key revoke and encipher the revoke file. I think most beginners would actually be better off with writing down their pass-phrase and storing it in a safety box but at the same time giving their keys a reasonable expire date. That is better than a key that they don't use enough, forget the pass-phrase, and then their key is lodged on the key-servers forever with no expration date and no chance for it to gracefully expire and pass on into history. It would also give them the opportunity to revoke the keylater on. I know. I said they should generate a revoke key file but they didn't do it. But at least with with the pass-phrase in a strong box they have the opportunity to revoke and upload the revoked keys to the key-servers. The 10K bit key size being spoken should be a play-toy to find out why it should NOT be used. That ten minutes to generate with the hottest CPU out there would probably be a pain for me even with my dual-core and lower level quad-core systems. I suspect it may take as long as ten seconds to verify a signed message. They would have no problems sending me an enciphered message with my shorter 2048R key and even a TWOFISH cipher. But I would suspect me sending them a PK enciphered message even with a CAST5 symmetric cipher as their first choice would take a LONG time. For an iPhone user it would be utterly impossible. PITA my foot! Just remember there are probably more iPhone users now than there are PC owners. HHH signature.asc Description: OpenPGP digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Recommended key size for life long key
On 08/31/2013 05:46 AM, Ole Tange wrote: The FAQ http://www.gnupg.org/faq/GnuPG-FAQ.html#what-is-the-recommended-key-size recommends a key size of 1024 bits. Reading http://www.keylength.com/en/4/ I am puzzled why GnuPG recommends that. It shouldn't; NIST recommends 2048 bits for 20 years of security. NIST notably makes no recommendations past 20 years, as they are deeply skeptical of their ability to forecast out that far. I suspect your ability is no greater than theirs is, so I'd be very careful about declaring a 10K key to be greater than your natural lifespan. Per NIST, a 2048-bit key is of comparable difficulty to breaking 3DES. Given the tremendous level of confidence people have in the long-term suitability of 3DES, I am convinced a 2048-bit key will outlast my ability to remember the passphrase to it. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
