GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
(I'll try to start a new thread from the following quotes.) On Sat, Nov 28, 2009 at 8:50 AM, Robert J. Hansen wrote: > Matt wrote: >> If I had a sufficiently good passphrase, would Google returning my >> secret key as the first hit result for every search for a day still be >> secure? > > "Secure" is not a very good word to use. It means so many different > things to so many different people. "Secure" really means "in > accordance with my security policies" -- the use of the word is > inherently subjective. Related to the same problem (strength of the secret key data encryption measures), I've posted some months ago an email on the scy.crypt Usenet group, but I didn't got a satisfactory (that is factual) answer. (See below.) Maybe someone could clear this out (at least from GnuPG part). (My original post was related with both GnuPG an OpenSSH). ~~ Original post: (I have a very basic question that to most of the persons reading this news-group might seem trivial. But anyway...) My concern (as stated in the subject) is related to the security strength of GnuPG and OpenSSH secret / private keys in the following context: * the secret / private keys are encrypted by using a password that only me (the owner) knows; * an attacker is in possession of my secret / private key files; * the attacker wants to gain access to the secret / private key (thus being able to impersonate me); * the attacker chooses as attack method to brute-force the files off-line, by trying to guess my password; * (by guessing the password I mean trying all possible passwords that fit a given pattern; the password is not a dictionary word, but instead is (truly) randomly created (i.e. DiceWare);) The question is: what does GnuPG or OpenSSH do to slow down password brute-force? I mean does the password derivation function use some iterations? If so how many? Can I configure them? I guess so but I couldn't find any data on the net on a quick search. (Any references are appreciated.) Also, how many bits of security should my password have in order to withstand an attack from a small / medium enterprise? (Government is out of the question as they could get access to my infrastructure by force...) Thank you for your patience and your wisdom, Ciprian Craciun. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Nov 28, 2009, at 9:42 AM, Ciprian Dorin, Craciun wrote: Maybe someone could clear this out (at least from GnuPG part). (My original post was related with both GnuPG an OpenSSH). ~~ Original post: (I have a very basic question that to most of the persons reading this news-group might seem trivial. But anyway...) My concern (as stated in the subject) is related to the security strength of GnuPG and OpenSSH secret / private keys in the following context: * the secret / private keys are encrypted by using a password that only me (the owner) knows; * an attacker is in possession of my secret / private key files; * the attacker wants to gain access to the secret / private key (thus being able to impersonate me); * the attacker chooses as attack method to brute-force the files off-line, by trying to guess my password; * (by guessing the password I mean trying all possible passwords that fit a given pattern; the password is not a dictionary word, but instead is (truly) randomly created (i.e. DiceWare);) The question is: what does GnuPG or OpenSSH do to slow down password brute-force? I mean does the password derivation function use some iterations? If so how many? Can I configure them? I guess so but I couldn't find any data on the net on a quick search. (Any references are appreciated.) GnuPG (really OpenPGP) does iterated password hashing. See section 3.7.13 "Iterated and Salted S2K" of RFC-4880 for the fine details, but the gist is as you surmised - the passphrase is run through many hash iterations. This slows down passphrase guessers as they must also repeat the hashing part the same number of times. By default, GnuPG uses 65536 iterations of the pasphrase hash, but can be configured via the --s2k-count option to be as high as 65011712 iterations. Be careful though - in some cases, a too-large value can hurt you here. If you create a passphrase-encrypted message on a fast machine, and pick a huge s2k-count, and then try to decrypt on a slow machine (say, a cell phone), the message may become effectively unusable since the repeated hashes can take an unusable amount of time on the slow processor. I'd have to look up the details if anyone is interested, but there was a case a few months back of a huge s2k-count actually causing an embedded device to trigger its deadman timer - someone had generated the message on a fast machine (so never noticed the large iteration count), but sent it to the slow one which clobbered it. Also, how many bits of security should my password have in order to withstand an attack from a small / medium enterprise? (Government is out of the question as they could get access to my infrastructure by force...) Difficult question to answer, since everyone is going to wave around their opinion. :) I'd suggest starting with the various calculators on http://www.keylength.com/ David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 David Shaw escribió: > On Nov 28, 2009, at 9:42 AM, Ciprian Dorin, Craciun wrote: ... >>Also, how many bits of security should my password have in order >> to withstand an attack from a small / medium enterprise? (Government >> is out of the question as they could get access to my infrastructure >> by force...) > > Difficult question to answer, since everyone is going to wave around > their opinion. :) > > I'd suggest starting with the various calculators on > http://www.keylength.com/ Now the interesting question would be, how to calculate the real bit length of a passphrasse? I googled, and found this message, from this list: http://lists.gnupg.org/pipermail/gnupg-users/2008-October/034842.html Best Regards -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBCAAGBQJLEVCJAAoJEMV4f6PvczxAYLIH/2kwGMDiBa7UNs83MyyzdeFs 0DnKyEpoK4HSsvvVZhpEqBUOLuxep6qtn2uhnFlXCw7tC3e+iGTfyudPK9dhLi0J 9aIkvYMSjzTCiiywiRAMHha6Z0dei5ffIsVupjeUnuzwiEXCDliUR5MODiQc4fP6 uGJcU0Z/e/IkFlFfFKAACySvLHJcoNzllBMEnfXudqfJpeOsUoGq/T6P2zZfjGrZ ly0gwKVfEowB7fi5QXYwYL6Dfi+FmctNRbzxL0ED2Pq1q1N+fzg4VnxGX6dqtLgX EtBsg2z3jvLZE6nSD65kxkSmxu9fWSS8UIlWu21YzgFtSYWQTl1w/5gJaNTwt7o= =CL86 -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Sat, Nov 28, 2009 at 5:47 PM, David Shaw wrote: > On Nov 28, 2009, at 9:42 AM, Ciprian Dorin, Craciun wrote: > >> Maybe someone could clear this out (at least from GnuPG part). (My >> original post was related with both GnuPG an OpenSSH). >> >> ~~ Original post: >> >> (I have a very basic question that to most of the persons reading >> this news-group might seem trivial. But anyway...) >> >> My concern (as stated in the subject) is related to the security >> strength of GnuPG and OpenSSH secret / private keys in the following >> context: >> * the secret / private keys are encrypted by using a password that >> only me (the owner) knows; >> * an attacker is in possession of my secret / private key files; >> * the attacker wants to gain access to the secret / private key >> (thus being able to impersonate me); >> * the attacker chooses as attack method to brute-force the files >> off-line, by trying to guess my password; >> * (by guessing the password I mean trying all possible passwords >> that fit a given pattern; the password is not a dictionary word, but >> instead is (truly) randomly created (i.e. DiceWare);) >> >> The question is: what does GnuPG or OpenSSH do to slow down >> password brute-force? I mean does the password derivation function use >> some iterations? If so how many? Can I configure them? I guess so but >> I couldn't find any data on the net on a quick search. (Any references >> are appreciated.) > > GnuPG (really OpenPGP) does iterated password hashing. See section 3.7.13 > "Iterated and Salted S2K" of RFC-4880 for the fine details, but the gist is > as you surmised - the passphrase is run through many hash iterations. This > slows down passphrase guessers as they must also repeat the hashing part the > same number of times. By default, GnuPG uses 65536 iterations of the > pasphrase hash, but can be configured via the --s2k-count option to be as > high as 65011712 iterations. > > Be careful though - in some cases, a too-large value can hurt you here. If > you create a passphrase-encrypted message on a fast machine, and pick a huge > s2k-count, and then try to decrypt on a slow machine (say, a cell phone), > the message may become effectively unusable since the repeated hashes can > take an unusable amount of time on the slow processor. > > I'd have to look up the details if anyone is interested, but there was a > case a few months back of a huge s2k-count actually causing an embedded > device to trigger its deadman timer - someone had generated the message on a > fast machine (so never noticed the large iteration count), but sent it to > the slow one which clobbered it. > >> Also, how many bits of security should my password have in order >> to withstand an attack from a small / medium enterprise? (Government >> is out of the question as they could get access to my infrastructure >> by force...) > > Difficult question to answer, since everyone is going to wave around their > opinion. :) > > I'd suggest starting with the various calculators on > http://www.keylength.com/ > > David Thank you for the quick reply. (This is the kind of answer I was hopping to get. :) ) It seems that `s2k-count` escaped me. :) Maybe there should be an entry in the FAQ about this topic. Related with my question about the password bit strength there still is a vale on my eyes. So I guess (sorry for not being properly documented here): * the private / public key pair is generated by using whatever means (RSA / DSA); * my password is taken and fed into "Iterated and Salted S2K" to obtain the secret key encryption. * the private key data is taken and fed into '' algorithm that uses as password what has been obtained at the previous step. So my question about key strength is: what symmetric key algorithm is used to safeguard the key. (Again I'm not properly documented here.) And based on the identity of this algorithm, I can use the site cited (http://www.keylength.com/) to determine a "best practices" key length. (Other wise I'll have to go with the generic term "symmetric key encryption"... :) ) > Now the interesting question would be, how to calculate the real bit > length of a passphrasse? I googled, and found this message, from this list: > http://lists.gnupg.org/pipermail/gnupg-users/2008-October/034842.html By key strength I mean the bits of entropy given by the password generation pattern. For example a 4-digit PIN number has only 13.3 bits of entropy, even though we need at least 16 bits to store it. (This was also pointed out by Farami in his reply.) Thanks again, Ciprian. P.S.: I'm also aware of the fact that iterations do not help at all, if a big-budget agency (NSA and the like), is going to build a hardware based brute-force key breaking, as they can build a pipeline of iteration functions that would try one key in O(1) time. :) (Or I'm wrong here?) ___ Gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 November 28th for gnupg-users@gnupg.org thread "GnuPG private key resilience against off-line brute-force attacks" Entropy is a relative thing AFAIR: For one who knows than a password was generated by using diceware the entropy will be 7776^n + 7776^n-1 ... 7776^1 where n is the number of words. For one who knows the lenght of password the entropy will be 256^n where n is the length. If it is know than it is english text entropy would be (26+26+10)^n. In contrast for one who do not know how password has been generated the entropy will be as if it were a random one. In short the apparent entropy of passowrds depends of how many the atacker know of it. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREIAAYFAksRVbsACgkQZ4DA0TLic4iwsgCfSpBGgu2zIYTL98CTde7QgTBu u9sAn3fgOtJhGoj4QTXgm6A1IjE+n4HU =t1Dq -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Backup of private key
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 There is thread in the archives with the subject "TPK Archival" that may be useful. http://lists.gnupg.org/pipermail/gnupg-users/2009-March/035996.html Regards, Chris -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQIcBAEBAgAGBQJLEVDIAAoJEKba9nIFysTLIBgP/jbW5IfIWApDJq5EAHGXg9cY y5/ce671duK9uimSBl1hXJWme+C1b/OFpbVAbCR7/Uu3UxVwQeCVD8F+T6mgaPsb mUPsX5GwrOZf5YMihq0h8aRsZYb1rAccHihGnEtJi9nQd9oLyxGUGc2DGh1sMOip Oz3KJnVjpp4rP7mbNoBiIWVcJFuSwHrvhwizaAEX3M7e/82SF1ty4ycIX1MqhWuZ YM2pRbisP8Qd1RlnER0El+Cec3R4DNpxLFAS5R7rQPAVlE8LzZLg3jZtBW+yLgiJ Ec3sAtWvgxnQBWUqX6svZug3e8rbwIZiZVtkGl1b+St+SwvlpOy55aFFhMFv2LDh QaQIzWo5GFS1NxnXFzOWh+fIS1aF9xRPsuj9dNW7S1k02A3DlwwRSuS26R+TZ/D2 NHYvzct9DRG2cssv1hdGi14WJW742j0EzZ8io9bUujHJ+qwNaHbfjdrkNPc8jDbH VOCUF36jdccZP1QmmoXYRTowl2cTqs9e+osbbICqVtiIEl+Z7LDyFCYNwCcJyppd BUOOWyr8rkPoDkc0uh4Pw34uszLRYU+fGUa0+z3Vs/t8EbzhxDmCf/WZafhjcz+r B/8AUJOMxvudxOgJhZ6fQuT1vj5pNem/lMd/VWP7/XbcI3tPI2V7NeYxOmOba8E2 w2ps4NbLQbHZo95KIW7A =8Q46 -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
David Shaw wrote: > Difficult question to answer, since everyone is going to wave around > their opinion. :) There are some empirical facts which may be useful, though -- like observing the RC5-64 project was able to break a 64-bit key via a massive distributed project that took 18 months of runtime. That's not a recommendation, just a data point which may be useful to people in making their own estimations. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
Robert J. Hansen wrote: > David Shaw wrote: >> Difficult question to answer, since everyone is going to wave around >> their opinion. :) > > There are some empirical facts which may be useful, though -- like > observing the RC5-64 project was able to break a 64-bit key via a > massive distributed project that took 18 months of runtime. > And estimates for RC5-72 including Moore's Law effects were hovering at 18 years. -- John P. Clizbe Inet:John (a) Mozilla-Enigmail.org You can't spell fiasco without SCO. hkp://keyserver.gingerbear.net or mailto:pgp-public-k...@gingerbear.net?subject=help Q:"Just how do the residents of Haiku, Hawai'i hold conversations?" A:"An odd melody / island voices on the winds / surplus of vowels" signature.asc Description: OpenPGP digital signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Sat, Nov 28, 2009 at 3:47 PM, David Shaw wrote: [snip] > I'd suggest starting with the various calculators on > http://www.keylength.com/ A very interesting website. I followed the links, and found this document: http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml It seems that the NSA is moving away from RSA/DH etc. cryptography, and now "only" approves their use for secret level material. They are instead pushing elliptic curve cryptography. I hadn't realised that there was such pressure to move away from traditional key exchange. Is this about the fear of quantum computing, or something else? EC in gpg is still some way off, it seems. N ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
Hi, On Sat, Nov 28, 2009 at 1:47 PM, David Shaw wrote: >> The question is: what does GnuPG or OpenSSH do to slow down >> password brute-force? I mean does the password derivation function use >> some iterations? If so how many? Can I configure them? I guess so but >> I couldn't find any data on the net on a quick search. (Any references >> are appreciated.) > > GnuPG (really OpenPGP) does iterated password hashing. See section 3.7.13 > "Iterated and Salted S2K" of RFC-4880 for the fine details, but the gist is > as you surmised - the passphrase is run through many hash iterations. This > slows down passphrase guessers as they must also repeat the hashing part the > same number of times. By default, GnuPG uses 65536 iterations of the > pasphrase hash, but can be configured via the --s2k-count option to be as > high as 65011712 iterations. Considering a password/passphrase, which has -- by default, its 65536th hash iteration result, locally stored for comparison. If I adjust (via --s2k-count) my GnuPG's iterations number, will it generate and store a new sum value for my actual passphase? Or for this passphrase specifically, it will continue working with the number of iterations used by the time the passphrase was created? Regards, Marcio Barbado, Jr. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Nov 28, 2009, at 12:37 PM, Robert J. Hansen wrote: David Shaw wrote: Difficult question to answer, since everyone is going to wave around their opinion. :) There are some empirical facts which may be useful, though -- like observing the RC5-64 project was able to break a 64-bit key via a massive distributed project that took 18 months of runtime. That's not a recommendation, just a data point which may be useful to people in making their own estimations. That's sort of the problem, though. There are countless facts that can be brought to bear on this question, and each one, by itself is just an additional point which does not add very much to the perennial question of key length. The nice thing about the keylength.com site is that they (or rather the several research papers and guides that comprise the site) gather together hundreds or more of individual facts and - carefully showing their methodology so that others can learn - do derive recommendations. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Nov 28, 2009, at 3:07 PM, M.B.Jr. wrote: Hi, On Sat, Nov 28, 2009 at 1:47 PM, David Shaw wrote: The question is: what does GnuPG or OpenSSH do to slow down password brute-force? I mean does the password derivation function use some iterations? If so how many? Can I configure them? I guess so but I couldn't find any data on the net on a quick search. (Any references are appreciated.) GnuPG (really OpenPGP) does iterated password hashing. See section 3.7.13 "Iterated and Salted S2K" of RFC-4880 for the fine details, but the gist is as you surmised - the passphrase is run through many hash iterations. This slows down passphrase guessers as they must also repeat the hashing part the same number of times. By default, GnuPG uses 65536 iterations of the pasphrase hash, but can be configured via the --s2k-count option to be as high as 65011712 iterations. Considering a password/passphrase, which has -- by default, its 65536th hash iteration result, locally stored for comparison. If I adjust (via --s2k-count) my GnuPG's iterations number, will it generate and store a new sum value for my actual passphase? Or for this passphrase specifically, it will continue working with the number of iterations used by the time the passphrase was created? The s2k-count is only used when creating the passphrase for the first time (and that applies to both creating a new secret key as well as encrypting something with a passphrase via --symmetric). If you want to change the s2k-count of an existing secret key, you need to set the new s2k-count and then change the passphrase. You can "change" it to the same passphrase if you like - it's the creation of a new passphrase-to-key that picks up the new s2k-count. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 November 28th 2009 for gnupg-users@gnupg.org thread "GnuPG private key resilience against off-line brute-force attacks" Loop unrolling only gives more performance in very small loops, for not so small ones there can be in fact a performance penality since as the unrolled code is great it leaves less cache for data. The complexity of a S2K algoritm is constant for variable input and constant iterations, in other words, it is O(1) but this O(1) assumes constant number of iterations, if we consider that factor the complexity would be O(iterations). So that O(1) than you say is correct but meaningless in this context. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREIAAYFAksRpCIACgkQZ4DA0TLic4iEUACgjxnvVcF0JXiBI3MuMv8HHwdY +P4AniUvv+j5Ysg99Qc+xDZ9e1LnCzxS =h116 -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Nov 28, 2009, at 11:55 AM, Ciprian Dorin, Craciun wrote: Thank you for the quick reply. (This is the kind of answer I was hopping to get. :) ) It seems that `s2k-count` escaped me. :) Maybe there should be an entry in the FAQ about this topic. Related with my question about the password bit strength there still is a vale on my eyes. So I guess (sorry for not being properly documented here): * the private / public key pair is generated by using whatever means (RSA / DSA); * my password is taken and fed into "Iterated and Salted S2K" to obtain the secret key encryption. * the private key data is taken and fed into '' algorithm that uses as password what has been obtained at the previous step. The "" is CAST5, by default. You can change it with --s2k-cipher- algo. The usual s2k rules apply - if you change the s2k-cipher-algo, it won't take effect until you change the passphrase. Also, be careful you don't shoot yourself in the foot with setting the algorithm to something you can't handle. This is less of a danger than with most algorithm changing tweaks: you only have to guarantee that *you* (and not all of your correspondents) have the ability to handle the key. So if you want your passphrase to be as strong as CAST5, you'd need a really massive passphrase. The passphrase is almost always the weakest part of this sort of system, by far. P.S.: I'm also aware of the fact that iterations do not help at all, if a big-budget agency (NSA and the like), is going to build a hardware based brute-force key breaking, as they can build a pipeline of iteration functions that would try one key in O(1) time. :) (Or I'm wrong here?) They're more likely to hit you with a wrench, a la http://xkcd.com/ 538/ :) David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
On Sun, Nov 29, 2009 at 12:29 AM, Mario Castelán Castro wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA256 > > November 28th 2009 for gnupg-users@gnupg.org thread "GnuPG private key > resilience against off-line brute-force attacks" > > Loop unrolling only gives more performance in very small loops, for > not so small ones there can be in fact a performance penality since as > the unrolled code is great it leaves less cache for data. > > The complexity of a S2K algoritm is constant for variable input and > constant iterations, in other words, it is O(1) but this O(1) assumes > constant number of iterations, if we consider that factor the > complexity would be O(iterations). > > So that O(1) than you say is correct but meaningless in this context. > -BEGIN PGP SIGNATURE- > Version: GnuPG v1.4.9 (GNU/Linux) > > iEYEAREIAAYFAksRpCIACgkQZ4DA0TLic4iEUACgjxnvVcF0JXiBI3MuMv8HHwdY > +P4AniUvv+j5Ysg99Qc+xDZ9e1LnCzxS > =h116 > -END PGP SIGNATURE- Again, as I've replied to Mario (off-the-list, below the excerpt for the rest of the list), by pipe-lining I assumed something like a hardware SIMD architecture. But I do agree that for a software-based implementation the iteration count does imply O(iteration_count) time complexity (which is constant). But not for a hardware implementation, where I can trade O(1) (and by `1` I don't mean constant, I actually mean `one heart-beat or a small number of hardware cycles`) in time with a O(n) in hardware complexity. In short: >Now imagine that we construct `iteration_count` many hardware > based `hash` blocks. > > password -> (hash) -> ... iteration_count ... -> (hash) -> output Could someone prove me wrong? (I'm not a hardware expert, but I believe it's technical possible.) Ciprian. On Sat, Nov 28, 2009 at 7:20 PM, Ciprian Dorin, Craciun wrote: > On Sat, Nov 28, 2009 at 7:08 PM, Mario Castelán Castro > wrote: >> -BEGIN PGP SIGNED MESSAGE- >> Hash: SHA256 >> >> November 28th for gnupg-users@gnupg.org thread "GnuPG private key >> resilience against off-line brute-force attacks" >> >>>P.S.: I'm also aware of the fact that iterations do not help at all, >>>if a big-budget agency (NSA and the like), is going to build a >>>hardware based brute-force key breaking, as they can build a pipeline >>>of iteration functions that would try one key in O(1) time. :) (Or >>>I'm wrong here?) >> >> Pipelining do not make iterated functions go to O(1)!. They are faster >> but still of the same complexity. So: more iterations, more time that >> it took to calculate, be the CPU where ejecuted pipelined or not. >> -BEGIN PGP SIGNATURE- >> Version: GnuPG v1.4.9 (GNU/Linux) >> >> iEYEAREIAAYFAksRWPcACgkQZ4DA0TLic4hC/QCfe9k3PybJ7X4W0oApBuob1OWh >> yjAAn2tYiBK3yUZkAQh8dcWwwlrgxUU5 >> =Om9a >> -END PGP SIGNATURE- > > >By pipeline-ing, I don't mean what we have in CPU's. > >I assume that the general working principle of the iterations work > like this: > >password = ... >iteration_count = ... >hashed_password = password >for i in range (0, iterattion_count): >hashed_password = hash (hashed_password) > > >Now this code can be unroll-ed (if the iteration count is known at > build-time): > >password = ... >hashed_password = password >hashed_password = hash (hashed_password) >... in total iteration_count times >hashed_password = hash (hashed_password) > > >Now imagine that we construct `iteration_count` many hardware > based `hash` blocks. > > password -> (hash) -> ... iteration_count ... -> (hash) -> output > >And at each time-tick (heartbeat) we fed 'password + 1' and push > the output from one hash box to another (at the same time). Thus at > each step we obtain as output one hashed password per heart-beat. > >This is why I'm saying it is only O(1), but O(n) in > hardware-blocks. Thus we trade hardware complexity with time > complexity. > >This architecture is called SIMD (Single Instruction Multiple > Data) http://en.wikipedia.org/wiki/SIMD > >So, does it seem possible now? :) (I've not actually have seen any > mention of such method, but my opinion is that it's possible.) > >Ciprian. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 November 28th 2009 for gnupg-users@gnupg.org thread "GnuPG private key resilience against off-line brute-force attacks" Ciprian: Wath you say is possible but useless. One could build a machine who computes anything in only 1 clock cycle or than not even need clock cycles: there are circuits than change it output as it input is changed without need of a pulse (Usually from a clock, it is: constant frecuency pulse generator) but the change is not inmmediate. As the compexity (Circuit complexity, not computational complexity) increases the delay betwen input change (Or clock signal) and output change becomes greater and greater thus they operating frecuence is low. So, yes, it can be built a machine than compues the S2K in one clock cycle, but it clock cycle shold be of very very low frecuency thus having the same performance as a machine than computes a S2K in say, 20,000 cycles but with much faster cicles. This is the contrary version of the megahert myth: "More cycles, more speed" than assumes than a 2.4 GHz CPU have the same eficiency per cycle than a 3.2 one. You instead think than more eficience per cycle gives more performance, your mistrake is than the cycles will be larger and frecuency much lower. Performance = Frecuency * Performance of each cycle. Sometimes one can make cycles 2 times more efficient but frecuency only 20% lower as intel do with P4 to Core 2 but this tradeoff can't be repeated infite times. There are some point where slighty more efficient cycles provokes a much more loss in frecuency and therefore the overall performance will be low. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREIAAYFAksRwJ4ACgkQZ4DA0TLic4il2QCeKXlMID7S0K8/ay3JuWCqvxrP Kq8An1GDC/bGlgbwjGr8ebrdRAPgJ+H4 =o+UI -END PGP SIGNATURE- 2009/11/28 Ciprian Dorin, Craciun : > On Sun, Nov 29, 2009 at 12:29 AM, Mario Castelán Castro > wrote: >> -BEGIN PGP SIGNED MESSAGE- >> Hash: SHA256 >> >> November 28th 2009 for gnupg-users@gnupg.org thread "GnuPG private key >> resilience against off-line brute-force attacks" >> >> Loop unrolling only gives more performance in very small loops, for >> not so small ones there can be in fact a performance penality since as >> the unrolled code is great it leaves less cache for data. >> >> The complexity of a S2K algoritm is constant for variable input and >> constant iterations, in other words, it is O(1) but this O(1) assumes >> constant number of iterations, if we consider that factor the >> complexity would be O(iterations). >> >> So that O(1) than you say is correct but meaningless in this context. >> -BEGIN PGP SIGNATURE- >> Version: GnuPG v1.4.9 (GNU/Linux) >> >> iEYEAREIAAYFAksRpCIACgkQZ4DA0TLic4iEUACgjxnvVcF0JXiBI3MuMv8HHwdY >> +P4AniUvv+j5Ysg99Qc+xDZ9e1LnCzxS >> =h116 >> -END PGP SIGNATURE- > > > Again, as I've replied to Mario (off-the-list, below the excerpt > for the rest of the list), by pipe-lining I assumed something like a > hardware SIMD architecture. > > But I do agree that for a software-based implementation the > iteration count does imply O(iteration_count) time complexity (which > is constant). But not for a hardware implementation, where I can trade > O(1) (and by `1` I don't mean constant, I actually mean `one > heart-beat or a small number of hardware cycles`) in time with a O(n) > in hardware complexity. > > In short: >> Now imagine that we construct `iteration_count` many hardware >> based `hash` blocks. >> >> password -> (hash) -> ... iteration_count ... -> (hash) -> output > > Could someone prove me wrong? (I'm not a hardware expert, but I > believe it's technical possible.) > > Ciprian. > > > On Sat, Nov 28, 2009 at 7:20 PM, Ciprian Dorin, Craciun > wrote: >> On Sat, Nov 28, 2009 at 7:08 PM, Mario Castelán Castro >> wrote: >>> -BEGIN PGP SIGNED MESSAGE- >>> Hash: SHA256 >>> >>> November 28th for gnupg-users@gnupg.org thread "GnuPG private key >>> resilience against off-line brute-force attacks" >>> P.S.: I'm also aware of the fact that iterations do not help at all, if a big-budget agency (NSA and the like), is going to build a hardware based brute-force key breaking, as they can build a pipeline of iteration functions that would try one key in O(1) time. :) (Or I'm wrong here?) >>> >>> Pipelining do not make iterated functions go to O(1)!. They are faster >>> but still of the same complexity. So: more iterations, more time that >>> it took to calculate, be the CPU where ejecuted pipelined or not. >>> -BEGIN PGP SIGNATURE- >>> Version: GnuPG v1.4.9 (GNU/Linux) >>> >>> iEYEAREIAAYFAksRWPcACgkQZ4DA0TLic4hC/QCfe9k3PybJ7X4W0oApBuob1OWh >>> yjAAn2tYiBK3yUZkAQh8dcWwwlrgxUU5 >>> =Om9a >>> -END PGP SIGNATURE- >> >> >> By pipeline-ing, I don't mean what we have in CPU's. >> >> I assume that the general working principle of the iterations work >> like this: >> >> password = ... >>
Re: GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)
* "Ciprian Dorin, Craciun" wrote: > Thank you for the quick reply. (This is the kind of answer I was > hopping to get. :) ) It seems that `s2k-count` escaped me. :) > > Maybe there should be an entry in the FAQ about this topic. Well, other projects make good use of that option, f.e. loop-AES, have a look at section 5 of http://loop-aes.sourceforge.net/loop-AES.README -- left blank, right bald pgphmDBHXrpjd.pgp Description: PGP signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
