Silk Road forums
Discussion => Security => Topic started by: bitfool on August 16, 2013, 03:01 am
-
How many times per second can an AES key from something like truecrypt be tried?
(I understand that the question depends on what hardware is being used, so you can give a rough description of it)
-
Look up supercomputer's like the Jaguar, that will tell you want you want to hear.
-
They wouldn't be cracking the AES key, they'd be cracking the passphrase protecting it in most cases.
And it's a huge number of attempts per second if they're doing it right. GPU's have dramatically sped up password cracking, and thanks to a few billion user passwords being leaked on the Internet, dictionary attacks have a really good idea of how people structure passwords.
That's why lots of folks here say things like "at least 30 characters, preferably more".
-
They wouldn't be cracking the AES key, they'd be cracking the passphrase protecting it in most cases.
Well, in that case, how many passphrases per second can be tried?
And it's a huge number of attempts per second if they're doing it right.
So, how many attempts per second?
-
Using the Amazon computer cloud they could guess millions of passwords per second.
-
I'd expect people trying to crack TC or a similar system to use FPGAs or GPUs or some kind of custom hardware, which rules out "amazon computer cloud"
edit :
looks like amazon's "cloud" has GPUs in it. Still, the original question hasn't been answered.
-
Looks like Trucrack does about 230,000 attempts per minute on a top-end graphics card (GTX Titan) so I think about a million per minute is reasonable for a hacker with a large botnet of machines with good GPUs.
If your adversary is the NSA and has, say $1M of ASICs pointed at the problem, assuming you get 1000x as much power as a high-end graphics card for about $20k then call it about 150M/sec.
-
A year is 60x60x24x365 seconds. We can use 2^25 to represent a year (that's actually ~388 days in seconds)
Assume machine W does something like a million tries per second, that is 2^20.
So machine W can try 2^25 x 2^20 --> 2^45 keys per year.
If the keyspace is 2^60 then it would take 2^(60-45) --> 2^15 --> 32768 years to find a key.
Did I get the math right?
-
A year is 60x60x24x365 seconds. We can use 2^25 to represent a year (that's actually ~388 days in seconds)
Assume machine W does something like a million tries per second, that is 2^20.
So machine W can try 2^25 x 2^20 --> 2^45 keys per year.
If the keyspace is 2^60 then it would take 2^(60-45) --> 2^15 --> 32768 years to find a key.
Did I get the math right?
Pretty much. It is a general rule of thumb that keys are usually found via searching approaximatley half of the keyspace. That said, 2^60, however is not a very large keyspace. Even in the mid-90s it was recommended that keys be used that would provide at least 90 bits of entropy, versus 60 in your scenario.
You have to realize that brute-forcing is the absolute LAST option that anyone will use, because it is so often a waste of time. The authorities will almost never use brute-force as a option, unless all other methods have failed first. The basic problem boils down to this: people are lazy; people will all too often, not use proper methods because they are "too hard to remember".
The authorities know this, and indeed, count on it. People choose passphrases that are meaningful to them, which makes them more predictable (i.e less random).
If you want a good system, try Diceware: http://www.diceware.com/
Diceware uses a specialized dictionary, the entries for which are paired with dice rolls. The dice rolls are a truly random physical process, thus it is impossible to predict which words were chosen, much less in what order. 10 Diceware words will yield a passphrase with 129 bits of entropy -- even given the fact that keys are usually found in only searching half the keyspace, that means that a potential attacker would have to go through 128-bits of the keyspace to potentially find what they're looking for.
Nightcrawler
4096R/BBF7433B 2012-09-22 Nightcrawler <Nightcrawler@SR>
PGP Key: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0xB8F1D88EBBF7433B (MIT clearnet keyserver)
PGP Key: https://keys.indymedia.org/pks/lookup?op=get&search=0xB8F1D88EBBF7433B (IndyMedia https: clearnet keyserver)
PGP Key: http://qtt2yl5jocgrk7nu.onion/pks/lookup?op=get&search=0xB8F1D88EBBF7433B (IndyMedia .onion keyserver)
PGP Key: http://dkn255hz262ypmii.onion/index.php?topic=174.msg633090#msg633090 (Silk Road Forums PGP Key Link)
PGP Key Fingerprint = 83F8 CAF8 7B73 C3C7 8D07 B66B AFC8 CE71 D9AF D2F0
-
They have a new quantum computer they just installed at NASA, various government departments, google and NASA are time-sharing it... but it could potentially crack shit lickety-split.
-
@AfternoonDelight
I don't think quantum computers can be used to crack anything, yet.
-
One other variable is that I believe Truecrypt is relying on PBKDF functions (which basically, make it more expensive in CPU terms, to attack the password).
So while a cheap ($<5k) password cracking GPU rig might be crunching 20-30+ billion hashed NTLM passwords a second, the number for TC passwords would be much, much lower. Just guessing that might be as low as 1000 passwords/sec, but that's just a wild guess. I could be off by a few digits in either direction. :)
-
One other variable is that I believe Truecrypt is relying on PBKDF functions (which basically, make it more expensive in CPU terms, to attack the password).
So while a cheap ($<5k) password cracking GPU rig might be crunching 20-30+ billion hashed NTLM passwords a second, the number for TC passwords would be much, much lower. Just guessing that might be as low as 1000 passwords/sec, but that's just a wild guess. I could be off by a few digits in either direction. :)
Came here to say this. Truecrypt certainly uses a Password Based Key Derivation Function (PBKDF) which greatly slows down the speed with which passwords can be guessed. You should expect a well funded attacker can guess trillions of passwords per second. A quick search reveals a cluster of 25 AMD graphics cards got up to 348 billion passwords per second, and the best card in their cluster was a 7970 not even any 7990. I think the cost of that must have been no more than about $12,000 since several of the cards they used are fairly old.
It seems to me that they are making exponential gains in password cracking technology because the last time I looked into it the commercially available solutions were guessing about twenty billion passwords per second but now I find people making their own clusters getting into the hundreds of billions.
PBKDF slows down such attacks depending on how many iterations the PBKDF is set to use. Cracking a password created with PBKDF with 10,000 iterations takes 10,000 times as long as cracking a password with no PBKDF iterations. So if an attacker can guess 1 trillion hashes per second they can only guess 100 million passwords created with PBKDF with 10,000 iterations. The problem with PBKDF is the more iterations there are the slower it is for a legitimate user to obtain their key with their password. If the user was willing to wait sixty seconds after typing in a password before anything happened, we could add more and more iterations and more and more security for the user. I think in the future the best option is to let the user set their own number of PBKDF iterations, so they can decide the trade off they want to make between ease of use and security. For most applications they try to make it so the user cannot even notice a delay from PBKDF but that it adds up to a big delay when someone tries to guess trillions of passwords. If a user was willing to wait for 100,000 password iterations on whatever CPU they have, the password cracker that can guess 1 trillion hashes per second would only be able to guess 10 million passwords a second. There are techniques for using RAM to limit password attempts as well.
-
Why not use a Yubikey?
~ kmfkewm
Wihtout going in depth, LUKS uses more iterations so I'd consider using it instead.
-
people are lazy; people will all too often, not use proper methods because they are "too hard to remember".
Yes. But I'm assuming a long and random key for argument's sake.
As to passphrases, I'm not sure how one should define the per word keyspace.
If you use words out of a list that is 2^13 words long (~8000 words) then it would seem obvious that the per word keyspace is 2^13, but in principle an attacker doesn't know how long your word list is. so he may have to assume a (much) bigger keyspace? (for instance, you're using words from two different languages?)
Anyway, assuming 13 bits per word, a 5 word passphrase gets you 65 bits. Seven words is 91.
One other variable is that I believe Truecrypt is relying on PBKDF functions (which basically, make it more expensive in CPU terms, to attack the password).
As I understand it, you can do two things.
One : Try AES keys directly.
Two : Use a dictionary. And that means, get a word from the dictionary, derive an AES key (expensive) and try it.
What is still missing is how many tries per second can different hardware do...
last time I looked into it the commercially available solutions were guessing about twenty billion passwords per second
But what kind of passwords were they cracking? Finding a TC password is not the same thing as just generating a hash.
Also, there's a hashing algo that in theory has been designed in a way to avoid efficient hardware implementation (it's the hash algo used in litecoins)
-
As I understand it, you can do two things.
One : Try AES keys directly.
Two : Use a dictionary. And that means, get a word from the dictionary, derive an AES key (expensive) and try it.
Yeah those are the two options, short of actual cryptanalysis. Directly guessing AES keys is always going to be the least effective way as it will have a key space of 2^128 or 2^256 whereas the effective key space of the password is not likely to have this much entropy. Even if the password has more entropy I think brute force on the password will brute force the key in no more time than it takes to brute force the encryption key directly, because of the pigeon hole principle. The KDF can produce outputs of 256 bits, if the password has 300 bits of entropy that means it will take 2^300 guesses to certainly break the password, each password given to the KDF produces a unique output if there are not collisions (there ARE collisions but they should be super rare), by the time you guess 2^256 passwords the KDF should output about 2^256 unique keys exhausting its key space, which means future password inputs can only produce a key output that has already been obtained (there are collisions but they are super rare), which means that you will almost certainly brute force the AES key prior to brute forcing the 300 bit password.
On the other hand if you brute force the AES key directly you can guess each key as soon as you generate it, if you use a PBKDF with 100,000 iterations you need to generate 100,000 keys prior to having one for testing (although you could test each key on the path to the one mapping to the password as well). You can calculate the entropy PBKDF iterations add with the following formula:
log2(2^password_entropy * pbkdf_iterations) == entropy of password WITH pbkdf iterations
so with 10,000 pbkdf iterations an 80 bit password turns into a 96 bits of security, and a 256 bit password turns into 272 bits of security. But with PBKDF or not you are still only guessing 2^256 passwords, it just takes as long to guess that many passwords as it normally would take to guess 2^272 passwords, so actually in this case I think it could be slower to brute force the password than it is to brute force the key directly, unless you guess each of the iterations the password produces when run through the PBKDF all the way up to the final iteration. In cases where a PBKDF is used this is probably the best strategy if you plan to do non stop brute force, because either it will break the key because the password is correct, or it will break the key because it has tried 2^256 unique inputs into a KDF that can only produce 2^256 outputs and which is highly collision resistant.
Please correct any of what I just said if I am wrong but I think it is correct, and it pretty much means that it is virtually always best to try to crack the password instead of the AES key directly (because not only is the password likely to be much easier to crack than the key, but even if it is not you will crack the key in the process of trying to crack the much harder to crack password, due to the collision resistance of the KDF and the pigeon hole property).
What is still missing is how many tries per second can different hardware do...
This can be answered easily in millions of hashes per second, when it comes to PBKDF you take millions of hashes per second / PBKDF iterations.
Also, there's a hashing algo that in theory has been designed in a way to avoid efficient hardware implementation (it's the hash algo used in litecoins)
I always assume when they give figures about passwords per second that they mean hashes per second unless otherwise specified. Yeah I know TC password is not the same thing as generating a hash, it uses a PBKDF, read my post. I think litecoin tries to be RAM intensive right? That is a cool technique. PBKDF2 (the standard PBKDF and what Truecrypt uses) tries to be CPU intensive.
-
Actually the quantum Grovers algorithm would result in it sometimes making more sense to attack the key directly than attacking the password, since it halves the key space of the symmetric key (turning AES-128 into AES-64, which is hopefully easier to break than many passwords). But I think direct attacks on the key only make sense in the quantum rather than classical world.
-
Please correct any of what I just said if I am wrong but I think it is correct
Well, I haven't studied all the details, you seem to know more about them than I.
Regardless, my overall take is this :
If the attacker is using a dictionary and your passphrase/word is in the dictionary, you had it.
The other possibility is, you're using a random passhprase that can go from something like ~60 bits to...as much as you like.
Then we need to figure out how many keys (AES or similar) can be tried per second.
A simple hardware counter running at 4 ghz (2^32) would count up to 2^57 in 388 days (~1.06 years)
The questions remain, what can off the shelf hardware do? What could custom hardware do?
For starters trying a key is going to take more than a clock cycle...