1Password GPU brute-force with 3M hash/s(hashcat.net)
hashcat.net
1Password GPU brute-force with 3M hash/s
http://hashcat.net/forum/thread-2238.html
13 comments
In terms of security, any opinion on how KeePassX for Linux is compared vs 1Password?
Refreshingly honest and clear response from vendor:
http://hashcat.net/forum/thread-2238-post-13402.html#pid1340...
Here's a taste:
This design flaw is certainly real, and is one of the many reasons why we have started migrating to a new design. In short, when the Agile Keychain Format was designed (in 2008), we weren't aware of all of the various problems that come from using unauthenticated CBC mode encryption.
I could plead that we were in reasonably good company in making that kind of error, but as I've since learned, research in academic cryptography had been telling people not to use unauthenticated encryption for more than a decade. This is why today we aren't just looking at the kinds of attacks that seem practical, but we are also paying attention to security theorems.
http://hashcat.net/forum/thread-2238-post-13402.html#pid1340...
Here's a taste:
This design flaw is certainly real, and is one of the many reasons why we have started migrating to a new design. In short, when the Agile Keychain Format was designed (in 2008), we weren't aware of all of the various problems that come from using unauthenticated CBC mode encryption.
I could plead that we were in reasonably good company in making that kind of error, but as I've since learned, research in academic cryptography had been telling people not to use unauthenticated encryption for more than a decade. This is why today we aren't just looking at the kinds of attacks that seem practical, but we are also paying attention to security theorems.
The fact that AgileBit's rep Jeffrey Goldberg is speaking honestly and in plain english about the problem only galvanizes my decision to keep using and recommending their product. It builds trust, as in I trust they will fix the problem and fix it properly.
To be honest, it really isn't much of a vulnerability either. Without this attack, the speed would be 800 Khash/sec. It just speeds it up by a factor of four. If your passphrase is sufficiently good, you're safe.
No, the attack speeds it up by a factor of two (1 bit).
The other factor of two was a known and expected optimization for HMAC that the OCLHashcat developer(s) discovered the hard way. The defenders (1PW's users) may have already been taking advantage of this optimization, so it really doesn't count as an "attack".
The other factor of two was a known and expected optimization for HMAC that the OCLHashcat developer(s) discovered the hard way. The defenders (1PW's users) may have already been taking advantage of this optimization, so it really doesn't count as an "attack".
Hmm, which is the 1-bit attack you're referring to? I only see one. Also, which is the optimization they might be taking? I don't see any.
One of the factors-of-two comes from computing the first input block of the two SHA's in the HMAC calculation and re-using this. This optimization in HMAC was underdocumented, but it ought to have been used by PBKDF2 implementations.
The other factor-of-two, i.e., the 1-bit attack, comes from skipping the generation of the CBC mode IV and only generating 1 output block (160 bits) of PBKDF2 output for the key and using a later ciphertext block to check the candidate password. This saves the attacker half of the PBKDF2 work factor.
This is a weakness in PBKDF2 when used to generate key material longer than the underlying hash function output length. RFC 2898 explicitly endorses deriving multiple keys in the manner 1Password used it:
The other factor-of-two, i.e., the 1-bit attack, comes from skipping the generation of the CBC mode IV and only generating 1 output block (160 bits) of PBKDF2 output for the key and using a later ciphertext block to check the candidate password. This saves the attacker half of the PBKDF2 work factor.
This is a weakness in PBKDF2 when used to generate key material longer than the underlying hash function output length. RFC 2898 explicitly endorses deriving multiple keys in the manner 1Password used it:
For instance, one might derive a
set of keys with a single application of a key derivation function,
rather than derive each key with a separate application of the
function. The keys in the set would be obtained as substrings of the
output of the key derivation function. This approach might be
employed as part of key establishment in a session-oriented protocol.
I think you mean CBC mode IV, not CTR mode IV. If they'd been using CTR mode, not having the nonce would be a dealbreaker for the attack; no matter what the cracker did, it would never generate the right keystream.
(I don't think using CTR mode would have made a lot of sense and am not saying the use of CBC mode is a design weakness; it isn't.)
(I don't think using CTR mode would have made a lot of sense and am not saying the use of CBC mode is a design weakness; it isn't.)
D'oh! Thanks, corrected.
And I was just on everyone else for conflating CTR mode nonces and CBC mode IVs...
And I was just on everyone else for conflating CTR mode nonces and CBC mode IVs...
Ah, yes, you are quite right. It seems like gross negligence on the part of the document to not mention that, given that the work factor is basically exactly what PBKDF2 is used for.
The main "problem" seems to be, that increased GPU power and tools just make it easier to brute force the master passphrase. AgileBits will improve the situation in the future.
Please take care and pick a strong master phassphrase!
Please take care and pick a strong master phassphrase!
That was the one of the take aways when I first reviewed the password keychain services- use a strong master password.
No matter what the construction being used is, you always have to use a strong master password. Nothing can help you if your password is in the dictionary.
Really it is unrealistic to expect users to have a sufficiently long password entered on every operation on iOS to provide adequate protection.
There should be some iOS-specific system with a key in protected keystore/keybag on the phone, combined with your encrypted password db potentially living in dropbox/icloud/etc., and then a user passphrase or biometric or whatever to unlock the file. Then you at least are protected against brute force once someone steals the encrypted keyfile from dropbox or some other service.
I've suggested this to them ~10 times. A keyfile format that doesn't rely on the crazy Apple resource forks and works with a user-self-hostable sync server would also be nice.
There should be some iOS-specific system with a key in protected keystore/keybag on the phone, combined with your encrypted password db potentially living in dropbox/icloud/etc., and then a user passphrase or biometric or whatever to unlock the file. Then you at least are protected against brute force once someone steals the encrypted keyfile from dropbox or some other service.
I've suggested this to them ~10 times. A keyfile format that doesn't rely on the crazy Apple resource forks and works with a user-self-hostable sync server would also be nice.
Why not just turn on the emoji keyboard and use unicode symbols instead of regular characters the standard keyboard.
An emoji password like happyface heart pizza devil hospital trafficlight cow moon is probably going to be more secure than any word/number combination that could be dictionary attacked.
This obviously assumes the site properly encodes Unicode, but also somewhat limits use for most people to devices with the keyboard.
An emoji password like happyface heart pizza devil hospital trafficlight cow moon is probably going to be more secure than any word/number combination that could be dictionary attacked.
This obviously assumes the site properly encodes Unicode, but also somewhat limits use for most people to devices with the keyboard.
Interesting idea, but it would be harder for me to remember 30 characters of emoji on a keyboard I don't routinely use than 30 characters of text and symbols which have, to me, some internal order, on keyboards I have used for the past...18 years?
I don't know how you get to the emoji keyboard on iOS. It would also be a little annoying having to do this on multiple platforms (I have considered using 1p on Windows at some point; no real argument that a well configured win 7 or 8 is worse than OSX, now).
I don't know how you get to the emoji keyboard on iOS. It would also be a little annoying having to do this on multiple platforms (I have considered using 1p on Windows at some point; no real argument that a well configured win 7 or 8 is worse than OSX, now).
It's not that hard to remember a 10+ char password, just use a long phrase, a rhythmical combination or anything that makes sense.
It's trivial to remember a very long password.
It's obnoxious to have to enter it on an iPhone keyboard with one hand while trying to drive or whatever on every login to anything. Particularly bad since I'm on a platform with a secure element, protected by tamper-resistant hardware, and relatively decent OS provided APIs to handle this exact problem.
There are good rumors that iOS 7/iPhone 5++ is going to have at least a fingerprint sensor, too, which would then automatically give biometric protection to the keybag as well.
It's obnoxious to have to enter it on an iPhone keyboard with one hand while trying to drive or whatever on every login to anything. Particularly bad since I'm on a platform with a secure element, protected by tamper-resistant hardware, and relatively decent OS provided APIs to handle this exact problem.
There are good rumors that iOS 7/iPhone 5++ is going to have at least a fingerprint sensor, too, which would then automatically give biometric protection to the keybag as well.
While driving!? Why write that? Have you no shame?
Specifically, it is while at a gate, potentially blocking traffic (because I don't remember all the gate codes, I keep them in 1Password). It's not while actually driving, but close.
The implication of:
> with one hand while trying to drive
Give him a break! Commenting on HN using an iPhone while driving is hard enough and now you want him to proofread?
Gate codes might be more appropriately stored on a piece of paper that you keep in your car or with your keychain.
[deleted]
And they don't explicitly warn their users in the App about how critical a strong master password is.
When I asked them to allow me to use a key along with my passphrase they said it would confuse their users, and then acknowledge their users aren't going to pick good passwords and would be at risk:
http://discussions.agilebits.com/discussion/comment/25737/#C...
> A master password constructed with diceware of three or four words should be both strong and memorable, but I have to acknowledge that most users aren't going to use diceware to construct a master password. So I suppose that your point stands.
When I asked them to allow me to use a key along with my passphrase they said it would confuse their users, and then acknowledge their users aren't going to pick good passwords and would be at risk:
http://discussions.agilebits.com/discussion/comment/25737/#C...
> A master password constructed with diceware of three or four words should be both strong and memorable, but I have to acknowledge that most users aren't going to use diceware to construct a master password. So I suppose that your point stands.
I hope they roll out a new 1password version soon. I was just thinking of starting using it, after the linode incident, but now I might wait for the fixed version.
That's silly. Even in the least charitable interpretation of what's happened, 1Password's security margin went from N (where N was a hypothetical security level believed to have been achieved by 1Pw, not some objective standard) to N/2. N/2 in this case is still light years past salted hashes.
I'm actually seeing N/4 in that hashcat.net/forum thread. See hashcat.net/forum/thread-2238-post-13424.html#pid13424 , or alternately just the last line of the original TFA, which says "reduce [work required] from 8000 to 2002".
I'm not sure how this is "least charitable", it seems to be pretty much the only interpretation. Either way, I'm not seeing the significance at all. I look forward to a reply from atom to penultimate post in that thread (#24) in which guinndupont explicitly asks for the real-world significance.
And I agree with Thomas and miles, that the vendor response is wonderfully direct, informative, reasonable, helpful, non-weaselly, etc. Props to him.
I'm not sure how this is "least charitable", it seems to be pretty much the only interpretation. Either way, I'm not seeing the significance at all. I look forward to a reply from atom to penultimate post in that thread (#24) in which guinndupont explicitly asks for the real-world significance.
And I agree with Thomas and miles, that the vendor response is wonderfully direct, informative, reasonable, helpful, non-weaselly, etc. Props to him.
I used the word "charitable" because the "N" in this measurement is a hypothetical measurement of how much more secure 1Password could have been. But if that's a valid analysis, it's just as valid to say they should have been using scrypt. Which, sure, but who cares?
I hope they roll out a new version for better syncing between computers and phones, but I'm pretty comfortable with the security in 1Password 3 today.
There really isn't a good way for anyone except Apple to make a great password manager on iOS, though, without getting every single app vendor to write to a password manager's API. But 1Password on iOS is pretty good. (what doesn't work so well is that you have to manually cut and paste passwords into browser or other apps; I'm not comfortable running a browser inside 1password)
There really isn't a good way for anyone except Apple to make a great password manager on iOS, though, without getting every single app vendor to write to a password manager's API. But 1Password on iOS is pretty good. (what doesn't work so well is that you have to manually cut and paste passwords into browser or other apps; I'm not comfortable running a browser inside 1password)
Dropbox syncing works well for me.
I don't want the encrypted file containing ~all of my passwords in an unencrypted Dropbox folder somewhere. If I control access to my keyfile, I'm at least protected somewhat against brute force, weaknesses in the software, someone stealing my master passphrase casually, etc.
They also have a USB synching tool if you're not comfortable with Dropbox (I'm not).
http://discussions.agilebits.com/discussion/11935/first-publ...
http://discussions.agilebits.com/discussion/11935/first-publ...
I still use their wifi sync, but it never worked very well.
The problem I have (which isn't THAT MUCH of an outlier) is that I have an MBA, a MBP17-desktop, an iPad, and an iPhone. I want to be able to use all of my normal/boring/personal/medium-sec passwords from all of my devices, want to be able to add new services from any of those devices, and I want to be able to do password updates from any of those devices. Ideally without ever connecting cables -- my iPhone/iPad get plugged into a charger in the car or by the bed, but not connected to either of the Macs.
All of their sync seems to be built around one Mac, one or two iOS devices; the USB, the older wifi, etc. Dropbox is the only solution they offer which is many-to-many.
I'm also essentially terrified of corruption or losing the data file, so any but the most cautious and transparent sync scares me.
The problem I have (which isn't THAT MUCH of an outlier) is that I have an MBA, a MBP17-desktop, an iPad, and an iPhone. I want to be able to use all of my normal/boring/personal/medium-sec passwords from all of my devices, want to be able to add new services from any of those devices, and I want to be able to do password updates from any of those devices. Ideally without ever connecting cables -- my iPhone/iPad get plugged into a charger in the car or by the bed, but not connected to either of the Macs.
All of their sync seems to be built around one Mac, one or two iOS devices; the USB, the older wifi, etc. Dropbox is the only solution they offer which is many-to-many.
I'm also essentially terrified of corruption or losing the data file, so any but the most cautious and transparent sync scares me.
You can enable automatic backups to ~/Library/Application Support/1Password/Backups in Settings -> Backup on your Mac. It will then backup locally as well as do Dropbox syncing.
> I'm also essentially terrified of corruption or losing the data file, so any but the most cautious and transparent sync scares me.
I keep a recently updated (every few weeks or after I enter something especially important) copy on a flash drive. Worse comes to worse and something gets corrupted I can always use that version.
I keep a recently updated (every few weeks or after I enter something especially important) copy on a flash drive. Worse comes to worse and something gets corrupted I can always use that version.
Could the 66 Ghash/s Bitcoin ASIC's be easily repurposed for password cracking? It's something I've been wondering about.
When you get into ASICs (Application Specific Integrated Circuits), the answer to 'can it be repurposed?' is almost universally no. It's basically a purpose built circuit, built into a single package. This is cheap and fast, because you only put in the parts you need, but there's non-trivial engineering effort to design them.
I think initially some miners used FPGAs: these are reprogrammable and offer similar performance, but they're much more expensive.
I think initially some miners used FPGAs: these are reprogrammable and offer similar performance, but they're much more expensive.
I think ajross is (mostly) right, ASICs can be re-purposed for SHA256 calculations. To what extent they have baked in a whole round of SHA256 is a good question, they may just be developed around very parallel XORs (which is why some GPUs are faster at BTC mining than others—they have built in XOR logic).
I do believe seeing that (the mythical) Butterfly Labs intends on releasing software for all sorts of other parallel high-performance applications (or some kind of driver/API type of thing), but I could be hallucinating.
I do believe seeing that (the mythical) Butterfly Labs intends on releasing software for all sorts of other parallel high-performance applications (or some kind of driver/API type of thing), but I could be hallucinating.
I think ajross is (mostly) right, ASICs can be re-purposed for SHA256 calculations.
I know what you mean, but I think you should be more specific in your statement. Bitcoin mining ASICs might be re-purposable. Not all ASICs.
I know what you mean, but I think you should be more specific in your statement. Bitcoin mining ASICs might be re-purposable. Not all ASICs.
Good point. An ASIC could be completely non-repurposable. The commonly-available (soon) BTC ASICS should be damn good at SHA256 cracking, maybe other XOR-related applications too.
Re: FPGAs, don't forget their other major downfall for mining- power. An equivalent ASIC uses much less power.
No. The Avalon ASIC only does a double-SHA256, and only attempts to brute force 4 of the 80 bytes in the input data. It cannot do any password cracking at all.
If you want it to, you would have to produce new wafers with a modified chip logic.
If you want it to, you would have to produce new wafers with a modified chip logic.
As I understand it, an ASIC is custom hardware to solve a custom problem - so it would probably be easier to build a custom one from scratch than convert a Bitcoin one. (Right?)
[deleted]
Right.
Probably only if the hash is a variant on SHA256, which is what the bitcoin protocol specifies. More complicated key derivation functions likely won't fit the limits of the hardware, and of course scrypt is expressly designed to defeat massively parallel application of digital logic (it scales with storage bandwidth instead).
No. In theory the FPGA boards could be repurposed, in practice no-one's bothered yet.
Did a lot of miners buy pre-programmed FPGAs to do mining? If they're passe, they could probably recover a lot of the cost by selling them to students. Or donating them, since they're now rich (technically).
Avalon had a trade-back program when they sold their round 2 ASICs, though I'm not sure what they are doing with the old FPGA boards once they receive them.
This is making the rounds on Twitter. I think the narrative is pretty unfair to 1Password, and that they're bending over backwards to seem reasonable and attentive†.
The problem as I understand it is that 1Pw runs PBKDF2-HMAC-SHA1 twice. 1Pw stores encrypted passwords using AES-CBC. It derives a 128 bit AES key from the first run of PBKDF2, and the 128 bit CBC IV from the balance of the first and the first bits of the second. Based on that design, it appears that 1Pw believed that the secrecy of the IV would contribute to the difficulty of cracking the encrypted blob, but of course it doesn't, because the trailing bytes of the blob are known plaintext and an attacker can use the key without knowing the IV to check if their password guess is right.
This is not a great design. But it's bad in a way that wastes cycles for users. The fact that 1Pw does extra PBKDF2 work that doesn't bind on attackers don't make 1Pw meaningfully weaker than any other app that uses PBKDF2, because it was already weird that they were tapping PBKDF2 twice to begin with. A more idiomatic use of PBKDF2 in this situation would be to tap PBKDF2 once, and then expand it (say with SHA2) to 256 bits. That design, which is totally reasonable and would not be the subject of a news story, would be equivalently secure to the "flawed" approach 1Pw took.
There is another problem with the construction 1Pw uses, which is that they chose PBKDF2-HMAC-SHA1. PBKDF2 with SHA hashes are among the easiest KDFs to crack on GPUs††, because SHAx was designed to be fast in hardware. 1Pw would have been much better off with scrypt, or even bcrypt (which is still a pain to implement in GPUs). But PBKDF2 is an industry best practice; to ding someone for using it while the rest of the world still uses "salted hashes" seems unreasonable.
What's happening here, besides the echo-chamber effect, is that the implementation of the brute force cracker for this particular encrypt blob is clever. In a rush to applaud cleverness, Twitter seems to have lept to the conclusion that "clever attack" means "vulnerable target". That's usually a correct assumption, but it isn't in this case.
Corrections more than welcome.
† They deserve some kind of medal for that, by the way, because I have no dog in this fight at all and I can't seem to shut up about the unfairness of it all.
†† It turns out there's a clever way to optimize this on a GPU by precomputing the ipad/opad in HMAC, too, which sped the cracker up.
The problem as I understand it is that 1Pw runs PBKDF2-HMAC-SHA1 twice. 1Pw stores encrypted passwords using AES-CBC. It derives a 128 bit AES key from the first run of PBKDF2, and the 128 bit CBC IV from the balance of the first and the first bits of the second. Based on that design, it appears that 1Pw believed that the secrecy of the IV would contribute to the difficulty of cracking the encrypted blob, but of course it doesn't, because the trailing bytes of the blob are known plaintext and an attacker can use the key without knowing the IV to check if their password guess is right.
This is not a great design. But it's bad in a way that wastes cycles for users. The fact that 1Pw does extra PBKDF2 work that doesn't bind on attackers don't make 1Pw meaningfully weaker than any other app that uses PBKDF2, because it was already weird that they were tapping PBKDF2 twice to begin with. A more idiomatic use of PBKDF2 in this situation would be to tap PBKDF2 once, and then expand it (say with SHA2) to 256 bits. That design, which is totally reasonable and would not be the subject of a news story, would be equivalently secure to the "flawed" approach 1Pw took.
There is another problem with the construction 1Pw uses, which is that they chose PBKDF2-HMAC-SHA1. PBKDF2 with SHA hashes are among the easiest KDFs to crack on GPUs††, because SHAx was designed to be fast in hardware. 1Pw would have been much better off with scrypt, or even bcrypt (which is still a pain to implement in GPUs). But PBKDF2 is an industry best practice; to ding someone for using it while the rest of the world still uses "salted hashes" seems unreasonable.
What's happening here, besides the echo-chamber effect, is that the implementation of the brute force cracker for this particular encrypt blob is clever. In a rush to applaud cleverness, Twitter seems to have lept to the conclusion that "clever attack" means "vulnerable target". That's usually a correct assumption, but it isn't in this case.
Corrections more than welcome.
† They deserve some kind of medal for that, by the way, because I have no dog in this fight at all and I can't seem to shut up about the unfairness of it all.
†† It turns out there's a clever way to optimize this on a GPU by precomputing the ipad/opad in HMAC, too, which sped the cracker up.
In my experience they are pretty awesome at customer service. I emailed them a few months ago after someone published a weakness during the BlackHat Conference (https://media.blackhat.com/bh-eu-12/Belenko/bh-eu-12-Belenko...)
Jeffrey got back to me with a way-more-reasonable-than-expected answer:
---------------------------------------------
Hi Bernardo,
I'm sorry for not getting back to you earlier. I think I answered your question elsewhere, and so failed to get to the email followup.
The Belenko and Sklyorov analysis of a large number of password managers found that many of them (including 1Password) were vulnerable to a "padding oracle" attack.
We discussed the problem the day that the report came out, and released an update to 1Password for iOS (Mac and Windows versions were not affected) within a few weeks.
The specific vulnerability (that pretty much affected everyone who used the standard cryptographic libraries) is fascinating, and I'm hoping to write more about it some day. But for the moment, please see
http://blog.agilebits.com/2012/11/08/dont-trust-a-password-m...
which includes some links to the issue and what we did about it. The key paragraph is
"The [New York Times] article cites some of the research behind Elcomsoft’s scathing review (PDF) of password managers on mobile devices, which we wrote about last March. That report did included some issues in 1Password on iOS (which we quickly addressed), but it also shows that there is enormous variation in the quality of password managers. 1Password is clearly among the best."
It is hard to stay ahead of potential threats, and we slipped up in that case so had to play "catch up" instead. Although there was never a practical threat to people's data, as developing a practical tool to exploit the vulnerability would take some time. But the design flaw certainly opened the door for people to create such tools, so we did need to get this fixed quickly.
Still we try to look toward the future in our design and defend against potential threats that don't yet exist. We should have defended against all potential chosen ciphertext attacks (CCAs) no matter how "theoretical" before the padding oracle (a type of CCA attack) was actually discovered.
I hope that helps. Please let me know if you have further questions.
Cheers,
-j
–- Jeffrey Goldberg Chief Defender Against the Dark Arts @ AgileBits
---------------------------------------------
Jeffrey got back to me with a way-more-reasonable-than-expected answer:
---------------------------------------------
Hi Bernardo,
I'm sorry for not getting back to you earlier. I think I answered your question elsewhere, and so failed to get to the email followup.
The Belenko and Sklyorov analysis of a large number of password managers found that many of them (including 1Password) were vulnerable to a "padding oracle" attack.
We discussed the problem the day that the report came out, and released an update to 1Password for iOS (Mac and Windows versions were not affected) within a few weeks.
The specific vulnerability (that pretty much affected everyone who used the standard cryptographic libraries) is fascinating, and I'm hoping to write more about it some day. But for the moment, please see
http://blog.agilebits.com/2012/11/08/dont-trust-a-password-m...
which includes some links to the issue and what we did about it. The key paragraph is
"The [New York Times] article cites some of the research behind Elcomsoft’s scathing review (PDF) of password managers on mobile devices, which we wrote about last March. That report did included some issues in 1Password on iOS (which we quickly addressed), but it also shows that there is enormous variation in the quality of password managers. 1Password is clearly among the best."
It is hard to stay ahead of potential threats, and we slipped up in that case so had to play "catch up" instead. Although there was never a practical threat to people's data, as developing a practical tool to exploit the vulnerability would take some time. But the design flaw certainly opened the door for people to create such tools, so we did need to get this fixed quickly.
Still we try to look toward the future in our design and defend against potential threats that don't yet exist. We should have defended against all potential chosen ciphertext attacks (CCAs) no matter how "theoretical" before the padding oracle (a type of CCA attack) was actually discovered.
I hope that helps. Please let me know if you have further questions.
Cheers,
-j
–- Jeffrey Goldberg Chief Defender Against the Dark Arts @ AgileBits
---------------------------------------------
That's cool, but it's worth noting that was not a new attack at all. It was known for 10 years before that, and very well known for 2. Elcomsoft didn't even pretend it was new (though they didn't credit previous work or name it, oddly), they just pointed out that 1Password was vulnerable to it.
It was only around the time of the Elcomsoft report that we (at AgileBits) became aware of the importance of authenticated encryption. The theorems had been around for more than a decade, but news didn't filter down to application developers (or if it did it went in one ear and out the other). This is a big problem in general.
Part of the problem stems from the fact that application developers are also (correctly) reluctant to use things that aren't in standard libraries and that don't have standards behind them. Even today, Apple's CommonCrypto offers no authenticated encryption modes, and only documents CBC and ECB. (CTR is available, but not documented as such.) And back to the current issue, we would have moved to scrypt from PBKDF2 already if it were readily available in well-reviewed implementations.
But also this stuff is hard (fun, but hard). And not every development team is going to have the expertise on board to really follow this stuff. They are just going to go with what's in the most easily accessible libraries, and if we are lucky, they won't use their encryption keys as IVs for CBC.
Lots of people are talking about how to improve the situation. I'm "cautiously optimistic".
Part of the problem stems from the fact that application developers are also (correctly) reluctant to use things that aren't in standard libraries and that don't have standards behind them. Even today, Apple's CommonCrypto offers no authenticated encryption modes, and only documents CBC and ECB. (CTR is available, but not documented as such.) And back to the current issue, we would have moved to scrypt from PBKDF2 already if it were readily available in well-reviewed implementations.
But also this stuff is hard (fun, but hard). And not every development team is going to have the expertise on board to really follow this stuff. They are just going to go with what's in the most easily accessible libraries, and if we are lucky, they won't use their encryption keys as IVs for CBC.
Lots of people are talking about how to improve the situation. I'm "cautiously optimistic".
I don't see why you say that the problem is that they run it twice. As I understand it, the problem is that they use AES with an 128-bit key, and they use it in CBC mode, which gets easily defeated once you know the last plaintext.
As I can see, they had various courses of action (don't take this to mean that they were remiss in securing their product, as they used best practices everywhere):
* Use AES-256, maybe deriving the key from a first run of the KDF and the IV from a second one, although that might also make for an attack.
* Use CTR mode. Unless I'm mistaken, the attacker would then need to guess both the key and the nonce to verify the block, which is significantly higher complexity.
* Re-encrypt the last block with the IV. This way, the attacker would have to decrypt with the other 128-bit key, and would need to know both to decrypt the last block.
* Pad the beginning, rather than the end. Or, since the string is of known length, just make it a multiple of the block size, and use no padding.
I'm really a crypto novice, though, so I might be completely mistaken. That said, it's a bit too bad that they didn't spend a bit of time thinking how they would crack their own product, they might have come up with this attack and mitigated it.
At any rate, running the KDF twice isn't a problem, unless you mean that it wastes CPU cycles for no good reason. In that case, I agree.
As I can see, they had various courses of action (don't take this to mean that they were remiss in securing their product, as they used best practices everywhere):
* Use AES-256, maybe deriving the key from a first run of the KDF and the IV from a second one, although that might also make for an attack.
* Use CTR mode. Unless I'm mistaken, the attacker would then need to guess both the key and the nonce to verify the block, which is significantly higher complexity.
* Re-encrypt the last block with the IV. This way, the attacker would have to decrypt with the other 128-bit key, and would need to know both to decrypt the last block.
* Pad the beginning, rather than the end. Or, since the string is of known length, just make it a multiple of the block size, and use no padding.
I'm really a crypto novice, though, so I might be completely mistaken. That said, it's a bit too bad that they didn't spend a bit of time thinking how they would crack their own product, they might have come up with this attack and mitigated it.
At any rate, running the KDF twice isn't a problem, unless you mean that it wastes CPU cycles for no good reason. In that case, I agree.
You're not mistaken in that there are constructions they could have used that would tie both the first and the second PBKDF2 output to the whole decryption. Their construction doesn't, and that appears to have been a mistake.
But it's not a meaningful mistake, for two reasons: (1) they were being naive about how they used PBKDF2 to begin with (again: don't call it a second time to generate a key or a nonce) and the attack on their encrypted blobs still requires a brute force attack on the first output, and (2) we're discussing a minimal improvement on the complexity of an attack on their system, but there are much bigger improvements available to them if they move off PBKDF2.
But, really: deriving keys from PBKDF2 is just fine. If they had just used PBKDF2 (once!) to generate an AES key, and then used /dev/random to generate an IV, nobody would be talking about them right now.
(For what it's worth, a CTR nonce only gives you 64 more bits to play with).
But it's not a meaningful mistake, for two reasons: (1) they were being naive about how they used PBKDF2 to begin with (again: don't call it a second time to generate a key or a nonce) and the attack on their encrypted blobs still requires a brute force attack on the first output, and (2) we're discussing a minimal improvement on the complexity of an attack on their system, but there are much bigger improvements available to them if they move off PBKDF2.
But, really: deriving keys from PBKDF2 is just fine. If they had just used PBKDF2 (once!) to generate an AES key, and then used /dev/random to generate an IV, nobody would be talking about them right now.
(For what it's worth, a CTR nonce only gives you 64 more bits to play with).
I definitely agree with you on all your mentioned points, but I'm unclear on a few things:
* What do you mean that it requires a brute force attack on the first output? As I understand it, the attacker doesn't need to match all 256 bits of the derived key (only the first 128 bits), so the complexity is reduced by a lot. If those match, you can just run the KDF "properly" on the passphrase you guessed and get the rest of the bits, i.e. the IV. It thus weakens PBKDF2 to only need 2002 rounds of SHA, rather than 8000, and still allows you to decrypt the whole stream.
* If they used a random IV, they'd have to include it in the stream, which wouldn't really do anything more for security. The IV doesn't matter at all now either, but at least now it's secret. This attack doesn't use the key space of AES or the IV, though, so it's a bit moot.
* The CTR nonce would prevent the attacker from taking the 128-bit "shortcut", as they'd need all 256 bits of the derived key to decrypt the last block, which is the improvement I'm referring to.
Please correct me if I'm mistaken, I find crypto very interesting and would like to know where I'm wrong.
* What do you mean that it requires a brute force attack on the first output? As I understand it, the attacker doesn't need to match all 256 bits of the derived key (only the first 128 bits), so the complexity is reduced by a lot. If those match, you can just run the KDF "properly" on the passphrase you guessed and get the rest of the bits, i.e. the IV. It thus weakens PBKDF2 to only need 2002 rounds of SHA, rather than 8000, and still allows you to decrypt the whole stream.
* If they used a random IV, they'd have to include it in the stream, which wouldn't really do anything more for security. The IV doesn't matter at all now either, but at least now it's secret. This attack doesn't use the key space of AES or the IV, though, so it's a bit moot.
* The CTR nonce would prevent the attacker from taking the 128-bit "shortcut", as they'd need all 256 bits of the derived key to decrypt the last block, which is the improvement I'm referring to.
Please correct me if I'm mistaken, I find crypto very interesting and would like to know where I'm wrong.
IVs are not really meant to be secret, IIRC. They're just meant to be different each time, to avoid getting the same cypher text if you have to encrypt another plaintext that begins with the same block.
To clarify, not that this should ever matter for you because you should never work with these primitives directly, but a CBC IV needs not only to be unique but also unpredictable (which is a different property than "secret", of course).
This would be used in a chosen plaintext attack, right? If you saw a ciphertext C1 with IV1, and you were able to choose the following Pj and predict the corresponding IVj, then you could verify whether the plaintext of C1 was P1~ by choosing Pj = P1~ XOR IV1 XOR IVj, so that Cj = C1 iff Pj = P1~. This would allow you to test likely values of P1~ from a dictionary.
Indeed, that is the case.
I learn something from just about every single one of your comments. Usually several things.
I just left a comment on the hashcat forum asking if anyone could offer a better back-of-the-napkin calculation of the real-world implications of this. My understanding is that we're still looking at something like 10^27 years of cracking to exhaust the password space.
Any (more clever) HNers care to offer a interpretation and calcuation?
Any (more clever) HNers care to offer a interpretation and calcuation?
It depends on the size of the space your passwords are drawn from.
The dictionary files I have in /usr/share/dict/ have about half a million words. Mean length is 11 characters. And there are about 100 characters easily accessible on my keyboard (letters, numbers and common symbols).
Regular words, trying lower case, UPPER CASE or First Letter Capitalised. 3 * 0.5 million options = Half a second to search.
Same but with a two digit number before or after (e.g. Patio11): 2 * 100 * 3 * 0.5 million options = 100 seconds to search.
Single regular word with up to 4 standard keyboard characters before or after (e.g. Patio3&A@): 2 * 100^4 * 3 * 0.5 million = about 3.1 years to search.
Two regular words, same case options, with or without a space. (3 * 0.5 million)^2 * 2 = 17 days to search.
Single regular word, random capitalisation (e.g. paTIo) rough figure: 2^11 * 0.5 million = 6 minutes to search.
Single regular word, random capitalisation, 4 standard keyboard characters before or after (e.g. PaTio8#`¬): 2 * 100^4 * 2^11 * 0.5 million = 2163 years to search.
Four regular lower case words (e.g. correct battery horse staple): (0.5 million)^4 = 660000000 years to search.
Up to 10 letters or numbers, upper or lower case (e.g. nk7rFG9Ad9): 63^10 combinations = 10403 years to search.
Up to 8 letters or numbers, upper or lower case (e.g. Plfws0aX): 63^8 combinations = 2.6 years to search.
Assuming you could obtain the same 3M hashes/second on an Amazon EC2 cluster GPU instance (this isn't a given as they have nVidia GPUs instead of the ATI chip used in the test reported) 2.6 years of GPU time at the spot price of 35 cents an hour would cost $7976.85
Needless to say, if you had access to a whole load of people's 1password files, probably some of them would be following a weak password selection scheme and you'd break them within seconds. On the other hand, people with strong password selection schemes will still be safe.
The dictionary files I have in /usr/share/dict/ have about half a million words. Mean length is 11 characters. And there are about 100 characters easily accessible on my keyboard (letters, numbers and common symbols).
Regular words, trying lower case, UPPER CASE or First Letter Capitalised. 3 * 0.5 million options = Half a second to search.
Same but with a two digit number before or after (e.g. Patio11): 2 * 100 * 3 * 0.5 million options = 100 seconds to search.
Single regular word with up to 4 standard keyboard characters before or after (e.g. Patio3&A@): 2 * 100^4 * 3 * 0.5 million = about 3.1 years to search.
Two regular words, same case options, with or without a space. (3 * 0.5 million)^2 * 2 = 17 days to search.
Single regular word, random capitalisation (e.g. paTIo) rough figure: 2^11 * 0.5 million = 6 minutes to search.
Single regular word, random capitalisation, 4 standard keyboard characters before or after (e.g. PaTio8#`¬): 2 * 100^4 * 2^11 * 0.5 million = 2163 years to search.
Four regular lower case words (e.g. correct battery horse staple): (0.5 million)^4 = 660000000 years to search.
Up to 10 letters or numbers, upper or lower case (e.g. nk7rFG9Ad9): 63^10 combinations = 10403 years to search.
Up to 8 letters or numbers, upper or lower case (e.g. Plfws0aX): 63^8 combinations = 2.6 years to search.
Assuming you could obtain the same 3M hashes/second on an Amazon EC2 cluster GPU instance (this isn't a given as they have nVidia GPUs instead of the ATI chip used in the test reported) 2.6 years of GPU time at the spot price of 35 cents an hour would cost $7976.85
Needless to say, if you had access to a whole load of people's 1password files, probably some of them would be following a weak password selection scheme and you'd break them within seconds. On the other hand, people with strong password selection schemes will still be safe.
Thanks for all the responses everyone! But, isn't the point of BKDF2-HMAC-SHA1 in 1Password that it's a 320 bit key, that he reduced down to only 160 bits? Unless I'm totally missing something here, it doesn't much matter if the password you are attacking is 6, or 7, or 8 or 50 characters long, you'll still need to attack all 160 bits, right? (Ignoring rainbow tables, or hashing on password dictionaries, etc., in other words, just brute force cracking). Am I being stupid?
PBKDF2 is salted, you can't attack multiple hashes with one computation.
Yes, to attack multiple files you'd have to do multiple computations.
However, if you can try all dictionary words in 0.5 seconds, you can try that against 172800 files in a day.
Of course you'd need a security breach that gave you access to multiple files too!
However, if you can try all dictionary words in 0.5 seconds, you can try that against 172800 files in a day.
Of course you'd need a security breach that gave you access to multiple files too!
Like a breach on Dropbox, a company that 1Password has no control over?
It depends on how good your password is
"A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST" [1]
2^30/(3M attempts/s)=358s
A completely random 8-character password from a space of 64 characters (upper, lower, number + 2 symbols) is 48 bits:
3^48/(3M attempts/s) ~= 3 years
Multiply by 64^N for longer passwords (so >180 years for a 9 character password)
The reason for the difference is that user-selected passwords are (on average) not as good as random passwords.
[1]http://en.wikipedia.org/wiki/Password_cracking#Time_needed_f...
"A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST" [1]
2^30/(3M attempts/s)=358s
A completely random 8-character password from a space of 64 characters (upper, lower, number + 2 symbols) is 48 bits:
3^48/(3M attempts/s) ~= 3 years
Multiply by 64^N for longer passwords (so >180 years for a 9 character password)
The reason for the difference is that user-selected passwords are (on average) not as good as random passwords.
[1]http://en.wikipedia.org/wiki/Password_cracking#Time_needed_f...
> 3^48/(3M attempts/s) ~= 3 years
But that's just with 2 GPU's! Any larger bitcoin miner has a few hundred (up to many more) of these graphics cards running. 100 GPUs would require only 20 days! Any larger entity could easily setup 1000 GPUs which cuts it down to 2 days, etc.
Probably there will be password cracking pools, similar to altcoin mining pools, which pay for your GPU resources in bitcoins.
But that's just with 2 GPU's! Any larger bitcoin miner has a few hundred (up to many more) of these graphics cards running. 100 GPUs would require only 20 days! Any larger entity could easily setup 1000 GPUs which cuts it down to 2 days, etc.
Probably there will be password cracking pools, similar to altcoin mining pools, which pay for your GPU resources in bitcoins.
They will need to do something with their rigs once mining gets too hard and the payouts too small.
Hmm, what's the opportunity cost (in terms of average BTC not mined) for doing 2^48 attempts?
It takes on average 2^54 hashes to discover a block at the current difficulty. So 2^48 attempts is 2^-6 (1.5%) of a block on average. A block is currently worth ~$2000, so 1.5% of that is ~$30
The real-world implications are one of the world's leading password cracking projects is able to test candidate password guesses 50% more efficiently than they would have otherwise.
This amounts to the loss of almost exactly 1 bit of security. Yes, really.
The first letter of my password is lowercase, not uppercase. There, that's how much it matters. 1 bit.
This amounts to the loss of almost exactly 1 bit of security. Yes, really.
The first letter of my password is lowercase, not uppercase. There, that's how much it matters. 1 bit.
I'd suspect it's a problem for people who think that, since it uses $fancy_encryption_scheme_they_cant_pronounce_or_understand, they can just use a trivially easy password for a computer to guess. Utilizing encryption isn't helpful if your password is still just "password1". I'm not a cryptographer by any means, but my general understanding is that longer is better. Picking some random nonsense sentence like "Correct horse battery staple" and using it as your password, is better than using "p455w0rd!1".
There are multiple password cracking techniques. Under brute force longer is strictly better. However, there are sophisticated dictionary attack programs that are also seeded with leaked password lists and do a variety of clever substitutions to come up with many potential candidates from each base word. For that type of attack, a password like: passwordpasswordpasswordpassword may not be a great bet despite it's length.
However, I'd assume a password like:
thisisthepasswordthatiwilluseonhackernews
would still be relatively hard to crack?
thisisthepasswordthatiwilluseonhackernews
would still be relatively hard to crack?
@rorrr: You've been hellbanned for almost a month.
------------
His comment:
> It's nearly identical.
> There are around 170,000 english words (including all the obscure ones you've never heard and have no idea how to spell).
> Number of 4-word combinations:
> And if they start bruteforcing with the simpler words (which you used in the example), there are only 5,000 - 10,000 of them, the number of your combinations drops dramatically:
------------
His comment:
> It's nearly identical.
> There are around 170,000 english words (including all the obscure ones you've never heard and have no idea how to spell).
> Number of 4-word combinations:
170,000^4 = 8.35 * 10^20
98^10 = 8.17 * 10^19
> And if they start bruteforcing with the simpler words (which you used in the example), there are only 5,000 - 10,000 of them, the number of your combinations drops dramatically:
5,000^4 = 6.25 * 10^14
10,000^4 = 10^16
> You've been hellbanned for almost a month
For good reason; please check someone's comment history before advising them of this.
For good reason; please check someone's comment history before advising them of this.
Well 2^48 ~= 2.8 x 10^14, so it's not as bad as you think for the simple words version (which is the same as 8 characters chosen from 64 choices)
[deleted]
[deleted]
Use scrypt! http://www.tarsnap.com/scrypt.html
Denial of hardware attacks is built in.
Denial of hardware attacks is built in.
I'm not a 1Password user. What's a common number of PBKDF2 rounds to have it configured for? What's the default?
The RFC spec says 1000 is a minimum, which is what 1PW seems to have been using.
We use a minimum of 10000 iterations, and where available we use CCCalibratePBKDF
http://blog.agilebits.com/2011/12/01/staying-ahead-with-secu...
http://blog.agilebits.com/2011/12/01/staying-ahead-with-secu...
Very nice.
My default is generally "whatever takes about half a second on an average machine".
test
Regardless of the fact that the master password can be brute forced on a machine running a couple of powerful graphics cards, it's refreshing to see 1Password address the situation so openly without making excuses or denying anything. They've always had great customer support and I have no doubt they'll make this a priority to fix as they've so openly said. This doesn't make me feel any less safe, while the chance is there that an attacker could brute force my data, I find it highly unlikely it'll happen between now and when they implement the new cipher. Bravo to Atom for discovering this and coming up with an exploit that can guess 3 million times per second using a graphics card processing unit.
We didn't explicitly call PBKJDF2 twice. We called it once, but asked for 256 bits of data, while giving it SHA1 to work with. In these circumstances, PBKDF2 acts as if we'd called it twice.
Anyway, there is a blog post about this here: http://blog.agilebits.com/2013/04/16/1password-hashcat-stron... The final part of it contains my analysis of what did and didn't go wrong.