Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 30/09/13 22:11, Jeffrey Goldberg wrote: With SRP requires a shared secret key, so the attacker doesn’t even need to “crack a hash” after getting hold of a server’s password database i don't think that's true. https://en.wikipedia.org/wiki/Secure_Remote_Password_protocol The host pwd is of the form g^x where x=H(p,s) same goes for JPAKE. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 1/10/13 12:22 PM, Florian Weimer wrote: Which leaves open the question (in my mind) as to whether to require this: "Both end points must authenticate each other." Keep in mind that the client side was deliberately crippled in browsers for privacy reasons. Support used to be much better—you could transparently created a client certificate which would automatically be used for future TLS handshakes. Right, another requirement: "Minimise the leakage of identifying information to eavesdroppers." These two requirements then might appear opposed. Or might not, there are many ways to skin the connection cat. iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
> Which leaves open the question (in my mind) as to whether to require this: > > "Both end points must authenticate each other." Keep in mind that the client side was deliberately crippled in browsers for privacy reasons. Support used to be much better—you could transparently created a client certificate which would automatically be used for future TLS handshakes. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 1/10/13 11:56 AM, ianG wrote: On 1/10/13 05:00 AM, d...@geer.org wrote: >Well clearly passwords are bad and near the end of their life-time with >GPU advances, and even amplified password authenticated key exchanges like >EKE have a (so far) unavoidable design requirement to have the server >store something offline grindable, which could be key stretched, but thats >it. PBKDF2 + current GPU or ASIC farms = game over for passwords. Before discarding passwords as yesterday's fish, glance at this: http://www.wired.com/opinion/2013/09/the-unexpected-result-of-fingerprint-authentication-that-you-cant-take-the-fifth I think the takeaway from this password debate (for me) is that any requirements listed for a TLS2 should be something like: "Integrates well with current and future authentication methods." (and leave the contenders to duke it out...) Which leaves open the question (in my mind) as to whether to require this: "Both end points must authenticate each other." iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 1/10/13 05:00 AM, d...@geer.org wrote: >Well clearly passwords are bad and near the end of their life-time with >GPU advances, and even amplified password authenticated key exchanges like >EKE have a (so far) unavoidable design requirement to have the server >store something offline grindable, which could be key stretched, but thats >it. PBKDF2 + current GPU or ASIC farms = game over for passwords. Before discarding passwords as yesterday's fish, glance at this: http://www.wired.com/opinion/2013/09/the-unexpected-result-of-fingerprint-authentication-that-you-cant-take-the-fifth I think the takeaway from this password debate (for me) is that any requirements listed for a TLS2 should be something like: "Integrates well with current and future authentication methods." (and leave the contenders to duke it out...) iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
>Well clearly passwords are bad and near the end of their life-time with >GPU advances, and even amplified password authenticated key exchanges like >EKE have a (so far) unavoidable design requirement to have the server >store something offline grindable, which could be key stretched, but thats >it. PBKDF2 + current GPU or ASIC farms = game over for passwords. Before discarding passwords as yesterday's fish, glance at this: http://www.wired.com/opinion/2013/09/the-unexpected-result-of-fingerprint-authe ntication-that-you-cant-take-the-fifth --dan ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 2013-09-30, at 10:43 AM, Adam Back wrote: > On Mon, Sep 30, 2013 at 02:34:27PM +0100, Wasa wrote: >> On 30/09/13 10:47, Adam Back wrote: >>> PBKDF2 + current GPU or ASIC farms = game over for passwords. >> >> what about stronger pwd-based key exchange like SRP and JPAKE? Well SRP most certainly isn’t a solution to this problem. With SRP requires a shared secret key, so the attacker doesn’t even need to “crack a hash” after getting hold of a server’s password database. I don’t know enough about JPAKE to comment. Of course SRP can be used in a way to ensure that the shared secret is never reused among services, but I don’t actually know how SRP is used in practice. > of even more concern an attacker who steals the whole > database of user verifiers from the server can grind passwords against it. > There is a new such server hashed password db attack disclosed or hushed up > every few weeks. They are far more common than that. See http://blog.passwordresearch.com/2013/01/passwords-found-in-wild-for-december.html Undiscovered breaches are probably much more common than hushed up breaches, which in turn are more common that disclosed breaches. > You know GPUs are pretty good at computing scrypt. I’ve been told by those who develop password cracking tools that (current) GPUs have a hard time with SHA512. So for the moment anyway, something like PBKDF2-HMAC-SHA512 should bring down the attacker-defender ratio. But this is hardly a long term solution and is focused on the specific architectures that exist today. However, it is what I am advocating as a temporary measure until we have something usable out of the Password Hashing Competition. The PHC is intended to find (spur the development of) a successor to PBKDF2 and scrypt. https://password-hashing.net > But there is a caveat which is the client/server imbalance is related to the > difference in CPU power between mobile devices and server GPU or ASIC farms. Yep. I work for a company that produces password manager that is used on mobile devices. The attacker will have much more to bring to the fight. All we can do is try to make the best use of the 500ms we think our users will put up with for key derivation. At the moment, that's PBKDF2-HMAC-SHA512 with the number of iterations initially calibrated to 500ms on the device where the data was created. But we are stuck with this asymmetry between attacker and defender, and have to design with it very much in mind. > Anyway and all that because we are seemingly alergic to using client side > keys which kill the password problem dead. I’m hardly allergic to that. Back in the 90s, I thought that this really would solve the password problem. I worked briefly on trying to initiate a project to develop a scheme where UK universities would sign client certs for members of the university. But, among other things, X.509 is a bitch. So I'm not so much allergic as pessimistic. For a long time I thought the password problem would be solved within the next few years. I’ve long seen client keys as the solution of the future. My fear is that it will remain the solution of the future. (Of course, given the business I’m in, my pessimism may be self-serving.) (Sure, a solution to the password problem would eliminate the need for the product that contributes to my livelihood, so maybe my pessimism is self-interested. But back when a chunk of my income was from fighting spam; I longed for the day I there would be no need for those services.) > For people with smart phones to > hand all the time eg something like oneid.com (*) ...(*) disclaimer I > designed the crypto as a consultant to oneid. Cool. I will take a look. And even in my pessimism, I don’t see passwords (even with great password management tools) sticking around forever. It’s just that I’ve learned over time that, like unencrypted email, they have a disturbing staying power. Cheers, -j smime.p7s Description: S/MIME cryptographic signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On Mon, Sep 30, 2013 at 07:41:20PM +0100, Wasa wrote: The only attack is on the PBKDF2 stored on the server (or malware to grab the password on the client) right. I was think SRP/JPAKE where the server does not store PBKDF2(salt,pwd) server-side, but rather it stores something like g^{PBKDF2(pwd)}. If I break into server and get hold of all g^{PBKDF2(pwd_i)}, can I parallelize the DL part? Well ok, this IRTF draft I was coincidentally just reading claims to be marginally more efficient than SRP https://datatracker.ietf.org/doc/draft-irtf-cfrg-augpake/?include_text=1 and has a verifier of that form. You could parallelize it somewhat at a micro level but I dont think you need to because you can just try lots of passwords in parallel against the same verifier. Because I think one of the claims of SRP and JPAKE is not only to be resistant to passive/active sniffing followed by offline brute-force, but also to be more resistant against server compromise. No I do not think that is true. And I noticed the IRTF draft above's security comments section confirms, it explicitly states that all it can offer in the event of server compromise is that the attacker has to brute force the PBKDF (aka function H in their terminology). (Actually that is why I bothered to read the draft because of their title/abstract I wondered if they had claimed to do better against server compromise and if so how as that is beyond the state of the art AFAIK; turns out they are the same as SRP etc). Idea? If it turns out to be difficult to parallelize the brute-force, why not move towards this? It would be an incremental improvement more likely to be widely-accepted than brand-new schemes. JPAKE is a bit slow I presume (given the number of required rounds), SRP is not and the patent expires soon (if memory serves). I think SRP is not patented, and in fact is designed to be free from reliance on any pre-existing patent details. There were some EKE patents but coincidentally the AKE version just expired last month. Nice timing. Adam ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 30/09/13 19:41, Wasa wrote: - with no server i meant "with no password". Arguably we can have decoy password if users feel more secure with them :-) ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 30/09/13 19:22, Adam Back wrote: On Mon, Sep 30, 2013 at 06:52:47PM +0100, Wasa wrote: Also the PBKDF2 / scrypt happens on the client side - how do you think your ARM powered smart phone will compare to a 9x 4096 core GPU monster. Not well :) How much would it help to delegate PBKDF2 / scrypt to smartphone GPU to break this asymmetry? It might help a little in the right direction, and so probably should be done; but I presume phone GPUs wont have that many cores nor high performance to compare to an AMD 7990 (4096x 1Ghz cores) even if it outperforms the phone CPU by a reasonable margin. since SRP and JPAKE use exponent_modulo sort of computation rather than a hash, any idea how this impacts attackers? how well can you paralellize a dictionary brute force for DL problem? I'm not expert so glad to hear about it. The A part of AKE password amplification, means that you cant break it via the DL stuff. The password only authenticates the diffie-hellman like key exchange, so it just is there to prevent MITM. You still have a full 2048 bit DL or 256-bit ECDL to attack and that is hopeless. The only attack is on the PBKDF2 stored on the server (or malware to grab the password on the client) right. I was think SRP/JPAKE where the server does not store PBKDF2(salt,pwd) server-side, but rather it stores something like g^{PBKDF2(pwd)}. If I break into server and get hold of all g^{PBKDF2(pwd_i)}, can I parallelize the DL part? Because I think one of the claims of SRP and JPAKE is not only to be resistant to passive/active sniffing followed by offline brute-force, but also to be more resistant against server compromise. Idea? If it turns out to be difficult to parallelize the brute-force, why not move towards this? It would be an incremental improvement more likely to be widely-accepted than brand-new schemes. JPAKE is a bit slow I presume (given the number of required rounds), SRP is not and the patent expires soon (if memory serves). Anyway and all that because we are seemingly alergic to using client side keys which kill the password problem dead. For people with smart phones to hand all the time eg something like oneid.com (*) can avoid passwords (split keys between smart phone and server, nothing on server to grind, even stolen smart phone cant have its encrypted key store offline ground to recover encrypted private keys (they are also split so you need to compromise the server and the client simultaneously). Also the user can lock the account at any time in event of theft or device loss. i like the idea. Any issue/complications with re-provisioning or multiple devices with same identity? If you lose one device you can replace the device enrole it authenticated by your other devices and securely restore access keys into it. It does support multiple devices, though each device also has a unique key as well as a common identity key so that individual devices can be revoked instantly if they are stolen. It uses some fun crypto like a blind MAC to do split key KDF and AKE type protocols. They have a recovery mechanism also I think if you simultaneously lose all our devices (laptop and smartphone) (user print out 128-bit key on registration). If the user doesnt do that they have to re-enrole as a new identity with oneid and the relying parties. I was thinking it could be a good tech for access to bitcoin online wallets and exchanges because also the transaction details are displayed for approval on the smart phone, so even if the laptop had bitcoin related password targetted malware on it, you could still securely transact if you read the transaction details on the smartphone before approving. so I wonder: - with no server, what would be the user perception of security? and would that prevents them from using such systems? Say, you log into your online banking with no password; would user feel secure and use the service? - would Facebook/twitter and co. like this sort of security where users cannot log-in from anywhere from any device? Surely they prefer a bit less security on client side + more ML detection server-side and more users connected; right? - I guess the sort of service you describe is great for large companies; but the complexity might put off smaller ones. Thoughts? - how different is the client cert approach compared to token used on mobile devices (e.g. Google stores a unique token on smartphones to access google services and hence requires no passwd)? Essentially it too removes phishing problems, but seems more flexible. But it does not have fancy crypto so maybe less exciting on an intellectual level :-) Adam ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On Mon, Sep 30, 2013 at 06:52:47PM +0100, Wasa wrote: Also the PBKDF2 / scrypt happens on the client side - how do you think your ARM powered smart phone will compare to a 9x 4096 core GPU monster. Not well :) How much would it help to delegate PBKDF2 / scrypt to smartphone GPU to break this asymmetry? It might help a little in the right direction, and so probably should be done; but I presume phone GPUs wont have that many cores nor high performance to compare to an AMD 7990 (4096x 1Ghz cores) even if it outperforms the phone CPU by a reasonable margin. since SRP and JPAKE use exponent_modulo sort of computation rather than a hash, any idea how this impacts attackers? how well can you paralellize a dictionary brute force for DL problem? I'm not expert so glad to hear about it. The A part of AKE password amplification, means that you cant break it via the DL stuff. The password only authenticates the diffie-hellman like key exchange, so it just is there to prevent MITM. You still have a full 2048 bit DL or 256-bit ECDL to attack and that is hopeless. The only attack is on the PBKDF2 stored on the server (or malware to grab the password on the client) Anyway and all that because we are seemingly alergic to using client side keys which kill the password problem dead. For people with smart phones to hand all the time eg something like oneid.com (*) can avoid passwords (split keys between smart phone and server, nothing on server to grind, even stolen smart phone cant have its encrypted key store offline ground to recover encrypted private keys (they are also split so you need to compromise the server and the client simultaneously). Also the user can lock the account at any time in event of theft or device loss. i like the idea. Any issue/complications with re-provisioning or multiple devices with same identity? If you lose one device you can replace the device enrole it authenticated by your other devices and securely restore access keys into it. It does support multiple devices, though each device also has a unique key as well as a common identity key so that individual devices can be revoked instantly if they are stolen. It uses some fun crypto like a blind MAC to do split key KDF and AKE type protocols. They have a recovery mechanism also I think if you simultaneously lose all our devices (laptop and smartphone) (user print out 128-bit key on registration). If the user doesnt do that they have to re-enrole as a new identity with oneid and the relying parties. I was thinking it could be a good tech for access to bitcoin online wallets and exchanges because also the transaction details are displayed for approval on the smart phone, so even if the laptop had bitcoin related password targetted malware on it, you could still securely transact if you read the transaction details on the smartphone before approving. Adam ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On 30/09/13 16:43, Adam Back wrote: On Mon, Sep 30, 2013 at 02:34:27PM +0100, Wasa wrote: On 30/09/13 10:47, Adam Back wrote: Well clearly passwords are bad and near the end of their life-time with GPU advances, and even amplified password authenticated key exchanges like EKE have a (so far) unavoidable design requirement to have the server store something offline grindable, which could be key stretched, but thats it. PBKDF2 + current GPU or ASIC farms = game over for passwords. what about stronger pwd-based key exchange like SRP and JPAKE? what I mean there is a so far unavoidable aspect of the AKE design pattern is that the server holds verifier v = PBKDF2(count,salt,password), so the server if hostile, or of even more concern an attacker who steals the whole database of user verifiers from the server can grind passwords against it. There is a new such server hashed password db attack disclosed or hushed up every few weeks. Passwords don't scale up and are very inconvenient, but are you sure your argument "PBKDF2 + current GPU or ASIC farms = game over for passwords" really holds? what about scrypt? And theoretically, you can always increase the number of rounds in the hash... I refer to this link too: http://www.lightbluetouchpaper.org/2013/01/17/moores-law-wont-kill-passwords/ You know GPUs are pretty good at computing scrypt. Eg look at litecoin (bitcoin with hashcash mining changed to scrypt mining, people use GPUs for ~10x speed up over CPUs). Litecoin was originally proposed as I understood it to be more efficient on CPU than GPU, so that people could CPU mine and GPU mine without competing for resources, but they chose a 128kB memory consumption parameter, and it transpired that GPUs can compute on that memory size fine (any decent GPU has > 1GB of ram and a quite nice cacheing hierarchy). Clearly its desirable to have modest memory usage on a CPU or if it fill L3 cache the CPU will slow down significantly for other applications. depends on the context i guess. if you are using a smartphone to log-in your banking app, it does not matter so much if you slow down other _background_ apps. Even 128kB is going to fill L1 and half of L2 which has to cost generic performance. Anyway in the bitcoin context that coincidentally was fine because then FPGAs & ASICs became the only way to profitably mine hashcash based bitcoin, and so GPUs were freed up to mine scrypt based litecoin. Also for bitcoin purposes higher memory scrypt parameters increase the validation phase (where all full nodes check all hashes and signatures, a double SHA256 is a lot faster than a scrypt at even 128KB, changing that to eg 128MB will only make it worse. Also the PBKDF2 / scrypt happens on the client side - how do you think your ARM powered smart phone will compare to a 9x 4096 core GPU monster. Not well :) i had this in the back of mind when I replied to ur email; so I tend to be on ur side here How much would it help to delegate PBKDF2 / scrypt to smartphone GPU to break this asymmetry? since SRP and JPAKE use exponent_modulo sort of computation rather than a hash, any idea how this impacts attackers? how well can you paralellize a dictionary brute force for DL problem? I'm not expert so glad to hear about it. So yes I stand by that. One could use higher memory scrypt parameters, and so the claim goes with memory bound functions that memory IO is less dissimilar between classes of machines than CPU speed (smartphone vs GPU). However you have to bear in mind also that scrypt actually has CPU memory tradeoffs, known about and acknowledged by its designer. I believe its realtively easy to construct a tweaked scrypt that doesnt have this problem. Also for the bitcoin/litecoin side of things I heard a rumor that there were people working on a litecoin ASIC. Bitcoin FTW in terms of proving the vulnerability of crypto password focussed KDFs to ASIC hardware. The scrypt time memory tradeoff issue maybe useful for efficient scrypt ASIC design. But there is a caveat which is the client/server imbalance is related to the difference in CPU power between mobile devices and server GPU or ASIC farms. While it is true that moore's law seems to have slowed down in terms of clock rates and serial performance the number of cores and memory architectures are still moving forward, and for ASICs density, clock rates and energy efficiency are increasing, and thats what counts for password cracking. But yes the longer term picture depends on the trend of the ratio between server GPU/ASIC performance vs mobile CPU. Another factor also is the mobiles are more elastic (variable clock, more cores) but to get full perf you end up with power drain and people dont thank you for draining their phone battery. It is possible for ARM eg to include an scrypt or a new ASIC unfriendly password KDF on the die perhaps if there was enough interest. The ready availability of clo
[cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)
On Mon, Sep 30, 2013 at 02:34:27PM +0100, Wasa wrote: On 30/09/13 10:47, Adam Back wrote: Well clearly passwords are bad and near the end of their life-time with GPU advances, and even amplified password authenticated key exchanges like EKE have a (so far) unavoidable design requirement to have the server store something offline grindable, which could be key stretched, but thats it. PBKDF2 + current GPU or ASIC farms = game over for passwords. what about stronger pwd-based key exchange like SRP and JPAKE? what I mean there is a so far unavoidable aspect of the AKE design pattern is that the server holds verifier v = PBKDF2(count,salt,password), so the server if hostile, or of even more concern an attacker who steals the whole database of user verifiers from the server can grind passwords against it. There is a new such server hashed password db attack disclosed or hushed up every few weeks. Passwords don't scale up and are very inconvenient, but are you sure your argument "PBKDF2 + current GPU or ASIC farms = game over for passwords" really holds? what about scrypt? And theoretically, you can always increase the number of rounds in the hash... I refer to this link too: http://www.lightbluetouchpaper.org/2013/01/17/moores-law-wont-kill-passwords/ You know GPUs are pretty good at computing scrypt. Eg look at litecoin (bitcoin with hashcash mining changed to scrypt mining, people use GPUs for ~10x speed up over CPUs). Litecoin was originally proposed as I understood it to be more efficient on CPU than GPU, so that people could CPU mine and GPU mine without competing for resources, but they chose a 128kB memory consumption parameter, and it transpired that GPUs can compute on that memory size fine (any decent GPU has > 1GB of ram and a quite nice cacheing hierarchy). Clearly its desirable to have modest memory usage on a CPU or if it fill L3 cache the CPU will slow down significantly for other applications. Even 128kB is going to fill L1 and half of L2 which has to cost generic performance. Anyway in the bitcoin context that coincidentally was fine because then FPGAs & ASICs became the only way to profitably mine hashcash based bitcoin, and so GPUs were freed up to mine scrypt based litecoin. Also for bitcoin purposes higher memory scrypt parameters increase the validation phase (where all full nodes check all hashes and signatures, a double SHA256 is a lot faster than a scrypt at even 128KB, changing that to eg 128MB will only make it worse. Also the PBKDF2 / scrypt happens on the client side - how do you think your ARM powered smart phone will compare to a 9x 4096 core GPU monster. Not well :) So yes I stand by that. One could use higher memory scrypt parameters, and so the claim goes with memory bound functions that memory IO is less dissimilar between classes of machines than CPU speed (smartphone vs GPU). However you have to bear in mind also that scrypt actually has CPU memory tradeoffs, known about and acknowledged by its designer. I believe its realtively easy to construct a tweaked scrypt that doesnt have this problem. Also for the bitcoin/litecoin side of things I heard a rumor that there were people working on a litecoin ASIC. Bitcoin FTW in terms of proving the vulnerability of crypto password focussed KDFs to ASIC hardware. The scrypt time memory tradeoff issue maybe useful for efficient scrypt ASIC design. But there is a caveat which is the client/server imbalance is related to the difference in CPU power between mobile devices and server GPU or ASIC farms. While it is true that moore's law seems to have slowed down in terms of clock rates and serial performance the number of cores and memory architectures are still moving forward, and for ASICs density, clock rates and energy efficiency are increasing, and thats what counts for password cracking. But yes the longer term picture depends on the trend of the ratio between server GPU/ASIC performance vs mobile CPU. Another factor also is the mobiles are more elastic (variable clock, more cores) but to get full perf you end up with power drain and people dont thank you for draining their phone battery. It is possible for ARM eg to include an scrypt or a new ASIC unfriendly password KDF on the die perhaps if there was enough interest. The ready availability of cloud is another dynamic where you dont even have to own the GPU farm to use it. You can rent it by the hour or even minute, or use paid password cracking services (with some disclaimer that it better be for an account owned by you). Anyway and all that because we are seemingly alergic to using client side keys which kill the password problem dead. For people with smart phones to hand all the time eg something like oneid.com (*) can avoid passwords (split keys between smart phone and server, nothing on server to grind, even stolen smart phone cant have its encrypted key store offline ground to recover encrypted private keys (they are also split so you nee