Silk Road forums
Discussion => Security => Topic started by: SelfSovereignty on April 18, 2013, 07:42 pm
-
May not be of great concern for SR specifically, but I think it's an interesting article and the knowledge might help a few people out there: have a look.
http://arstechnica.com/security/2013/04/yes-design-flaw-in-1password-is-a-problem-just-not-for-end-users/
-
By the by: scrypt, which may or may not suffer the same issue, is what Litecoin uses. :-X
-
OpenSSL allows PBKDF2 to output as many bytes as you tell it to with a single function call, but I am not sure exactly how they achieve that. I should test it and see if it is just hashing x times and discarding the remainder. Considering the OpenSSL implementation of PBKDF2 is likely by far the most commonly used, it seems like this could very well be a flaw in OpenSSL that extended to 1Password.
After reading a bit more about the technical details of this attack, it becomes apparent that it is hardly really a flaw in PBKDF2 though. It is a flaw in the way they used it. If they used it with a cipher in CTR mode this attack would not be possible. It is really a pretty subtle attack, I would have definitely overlooked it myself because I always thought in CBC mode the IV influences every single block, but looking at the Wikipedia diagram of it I can see now that this is only the case for encryption, not for decryption where only the first block is affected by the IV. I would expect a professional cryptographer to never make such a mistake though, or even someone implementing something using CBC mode, as I would hope they look at the diagrams on wikipedia first at least. In CTR mode the IV influences every single output byte, for encryption and decryption. So their mistake was in using two calls to PBKDF2, with one for the IV, when the IV is not required to determine if the key is correct in CBC mode decryption.
Also it seems like he could have used the first set of output bytes of the KDF as the IV and the second set as the key. Then attackers would need to generate the IV associated with a password before they could generate the key associated with it. Or he could have even not generated the IV from the password, and doubled the number of KDF iterations. the IV doesn't need to be secret, and probably shouldn't be based on the same password that is used to derive the key anyway.
-
I really wish I knew more technical details of how they have used the PBKDF, because the more I think of it the more I think they must have done something really bizarre to be susceptible to this attack. I would imagine they are at least using the PBKDF to generate enough output by increasing the iterations by one, and taking 256 of the 320 bits this outputs with SHA1, 128 to be used as key and 128 to be used as IV. If they are doing this, even though only the key is required to see if the password is correct, assuming they use the first 128 bits for the key, the lack of requirement of generating the IV on the attackers part would only remove 1 iteration per password. Considering they were using 1,000 iterations per password, having to do one less will not halve the number of required iterations. I think what they were doing was probably using one salt for the IV and one salt for the key, and doing 500 iterations of PBKDF2 for each of them, with the same password seed input. That is the only way I can imagine this attack as halving the number of iterations. If that is the case then it was a stupid implementation error on the part of 1Password, because even if they thought that CBC mode used the IV for every step of encryption AND decryption, they should have just used a single call to the PBKDF2 function and output 256 bits by sequentially iterating beyond the number of brute force protection iterations. Or they could have just used SHA256 to begin with, and doubled the number of iterations they were using. It is even more dumb because they don't even need to keep the IV secret, they could generate a random 128 bit IV and stored it in plaintext, then generated the encryption key from the password with the number of iterations they wanted. There is no real reason to generate the IV the way they were, and they were counting on iterations from PBKDF2 to generate the IV to slow down brute force attacks, which failed for them because CBC mode doesn't require the IV to confirm the key is correct.
So they made a number of mistakes.
The primary mistake they made was:
A. Assuming CBC mode requires the IV for every step of decryption. This is a mistake I would forgive them for, simply because I thought the same thing until I heard about this and looked at the diagram on wikipedia. The IV influences every block of encryption, but only the first block of decryption.
However, the attack could still have been prevented if they didn't:
B. Think they needed to generate the IV from a password, or keep it secret at all. IV does not need to be secret, and there is no reason to generate it from a password. By generating it from a password, and counting on the side effect of PBKDF2 iterations in this step as part of their total number of iterations, they screwed themselves.
C. Use SHA1 for some reason, even though they wanted 256 bits of total keying material. SHA256 is the logical choice here, and they could have split the output of PBKDF2 into two 128 bit sections , one for the IV and one for the key. Then they would have set the iterations in a single function call, and at worst the attacker would need to do one less iteration, if they use the first 128 bits as the key. If they did this and used the last 128 bits as the key, the attack would not be possible.
D. Use two calls to the PBKDF. I am not 100% sure they did this, but it is the only thing that makes sense to me for how the attacker could halve the number of iterations. My educated guess is that they started with two salts, one for key and one for IV, then ran through 500 iterations of PBKDF2 with the salt for IV + password to get the IV, and 500 iterations of PBKDF2 with the salt for the key + password to get the key. Even using SHA1, if they simply ran 1002 iterations of PBKDF2 and took the last two iterations 320 bits and used 128 bits of it for IV and 128 bits of it for the key, they would not be vulnerable to this attack or only vulnerable to 1 lost iteration per password attempt, depending on the order they use the output bits in.
So in summary, this flaw is the result of a combination of them not correctly understanding how the block cipher mode of operation they used works, and misusing PBKDF2. I think I would be hesitant to use their products.
-
Isn't this why you don't roll your own encryption and stick with the standards, or is there a problem with one of the standards?
-
It's my understanding that their implementation wasn't questionable. Perhaps a touch more obscure than one might expect, but not vulnerable or weak -- though a 2-4 fold decrease in time required to crack it isn't really broken or anything, but you get my gist.
I believe they're ultimately hashing twice; the first time yields 122 bits. I think they then after several other steps are performed repeat the hash and use the result to pad those 122 bits, discarding any unnecessary remainder. Apparently it's this specific method of going about constructing the AES-256 image that the issue arises from: apparently it's done in such a way that it's only necessary to crack that first hash.
Repeating adds no uncertainty at all: it's deterministic without salting. End up matching the output of the first hash through trial and error, and you can be positive that it'll match the output of the second hash as well -- which makes the second pass completely useless, just ignore those bits entirely. So basically, their AES-256 is as hard to crack as AES-128 is supposed to be, in a nutshell.
I didn't read the whole article... meant to come back to it. Still haven't yet. But that's my understanding of it; it wasn't a radically non-standard implementation or anything though. There's often a great deal of leeway when implementing something like this, especially since the design of every program tends to be ever so slightly different here or there. You don't really end up with identical code even when implementing identical, standard algorithms. Besides... what's the fun in that?
You go crazy doing shit like mechanically copying algorithms from references. It has its place, sure, but it sucks all the fun out of it. The coding is the good stuff. Copying things out of a book is mind numbingly boring.
The point is though that these guys know what they're doing, they've had experience with such things and aren't the sort to blunder foolishly. But their code is vulnerable to this, and no one seems to be sure yet whether it can be extended to all implementations or only theirs. Like I said... I didn't even finish the article, so I can't say either.
-
Isn't this why you don't roll your own encryption and stick with the standards, or is there a problem with one of the standards?
Well they used the standards (AES-128-CBC, PBKDF2, SHA1) , and didn't strictly speaking roll their own encryption (although they did roll their own cryptosystem), but they used the standards incorrectly. It would be like using seeded SHA256 for a PRNG, but only hashing out from the seed, without concatenating the seed to each output iteration before rehashing to get the next output iteration. Although that would be rolling your own PRNG, so it is not a perfect analogy.
At least they knew to use a PBKDF, an even worse situation would happen if they had simply used SHA1 for the key without combining it with a PBKDF. In either case they would have used the standards, but it would be a misuse in either case. In their case the number of iterations was halved, from 1,000 to 500, had they used SHA1 with no PBKDF there would have only been one iteration.
But even though this shows that they didn't know how the mode of operation they used worked, or how to correctly use PBKDF2, the effect on end users should be fairly minimal. PBKDF stands for password based key derivation function. It is used to derive a key, for use in encryption operations, from a password. Generally it works like this:
You provide a salt, a hash function and a number of iterations. Let's say your salt is 'abc' , your hash function is SHA1, your number of iterations are set at 2 (way too low!), and your password is 'def'.
So the first iteration will produce the SHA1 hash of 'abcdef'
bdc37c074ec4ee6050d68bc133c6b912f36474df
the next iteration will produce the SHA1 hash of the first iteration
e3cd537dc0c5da5cc5360dab38faf6fcee29a2f8
and this is the key derived from your password run through that KDF. This is beneficial when you have a lot of iterations, because it makes it so the attacker must use more computational power, which translates into more time, in order to brute force your password. It also protects from rainbow tables because of the salt. Assuming the attacker guesses your password correctly the first time, if there are two iterations of the KDF, it means they must do two hash operations to derive your key. Without a KDF, they would only need to perform one hash operation to derive your key. Since they have to do two operations with the KDF, it doubles the amount of time required for them to crack your password. If you use 1,000 iterations, it multiplies the amount of time required by 1,000.
This is really nice for slowing down brute force attacks, but it isn't a replacement for a good password. It may make a very bad password into a bad password, but it will not make a okay password into a strong password.
An 8 bit password has a key space of 256, 2 ^ 8. That means without using a KDF, the attacker has to do at most 256 hash operations to crack your password. With a KDF that uses 2 iterations, they need to do at most 512 hash operations to crack your password.
log2(2 ^ password_strength * KDF_iterations) = password_strength with KDF
Keep in mind that it gets unrealistically slow for a user to generate their keys as you go up orders of magnitude in the number of iterations. Most programs use somewhere in the area of 1,000 iterations.
log₂(2^8×1000) = 17.96 bits with 1000 iterations
log₂(2^8×10000) = 21.28 bits with 10,000 iterations
log₂(2^8×100000) = 24.60 bits with 100,000 iterations
log₂(2^8×1000000) = 27.93 bits with one million iterations
log₂(2^128×1000) = 137.00 bits with 1000 iterations
log₂(2^128×10000) = 141.28 bits with 10,000 iterations
log₂(2^128×100000) = 144.60 bits with 100,000 iterations
log₂(2^128×1000000) = 147.93 bits with one million iterations
As you can see, adding a single random 8 bit character to a password is more effective at increasing password strength than going up two orders of magnitude in the number of PBKDF iterations you use. Adding 1000 iterations to an 8 bit password more than doubles the bit strength of the password, but adding 1000 iterations to a 128 bit password doesn't anywhere near double the bit strength.
So even though it is best to use a PBKDF to give some extra bit strength to the password, even not using one at all isn't the end of the world if the user has a good password. And adding orders of magnitude more iterations greatly increases the amount of time it takes for the user to generate their key, and is less effective than the user adding a single additional character to their password.
I am pretty sure that 1Password used PBKDF2 twice, once with a salt for the IV and once with a salt for the encryption key. So lets say once they call it with
'1PasswordIV' + 'Password' , for 500 iterations with sha1
and once with
'1PasswordKey' + 'password' , for 500 iterations with sha1.
They were banking on CBC mode requiring the IV for all steps of decryption to see if the password was correct, so they assumed that they were using PBKDF2 with 1,000 iterations. The attacker saw that they didn't understand CBC correctly, and that they used PBKDF2 weirdly, and so they entirely ignored the '1PasswordIV' + 'Password' for 500 iterations step, cutting the amount of effective iterations in halve.
The problem would not have arisen if the 1Password people correctly understood CBC mode decryption, or if they did something like
'1Passwordsinglesalt' + 'password', for 1002 iterations with sha1
and took 256 bits from the last two iterations as their output, using the first 128 for the IV and the last 128 for the key.
Or if they didn't generate the IV from the password at all, and used 1000 iterations for the key. Or if they used sha256 and a single call the PBKDF2, then split the final iteration as I described previously.
-
Way over my head. KeyPass is still ok though?
-
Way over my head. KeyPass is still ok though?
Actually, 1Password is even still okay. Just weaker than it was thought to be. Never heard of KeyPass, but I don't believe this has any effect on it -- so if it was safe before, it's still safe now :)