7

For the purposes of evaluating a hashing algorithm against the threat of a nation state adversary, are there accepted estimates of the password cracking abilities of nation states - or is there an accepted benchmark to estimate the impact of such a threat?

For instance, it has been proven that FPGAs can accelerate attacks on BCrypt. Are there any known, reliable sources which estimate how much more of an advantage an entity like NSA would or could have, with access to custom hardware and scientific computing power?

A concise answer as to why this is impossible calculate / infer is acceptable if the question is not, in fact, possible to answer. I imagine, you could come up with a worst case scenario by cross referencing published budgets against known scientific computing power in less secretive fields, but I don't know if that is something that has been done in the past.

  • This type of thing is not measured by "Nation State" but by computing power over time. – schroeder Oct 21 '15 at 18:05
  • 1
    Here is one way of doing that (SHA-1 analysis): schneier.com/blog/archives/2012/10/when_will_we_se.html – schroeder Oct 21 '15 at 18:06
  • To add to that, it's not all that difficult to do an analysis of cracking rates per dollar. "Nation States" vary widely in their budget, so it's more useful to think in terms of costs, and then come up with some number you think a particular country might have to throw at the problem. That's why you see the high level analysis in Schroeders link talk about cost, not capabilities of attackers. – Steve Sether Oct 21 '15 at 18:49
  • 1
    How would you calculate the cost of cracking per dollar with something like an ASIC or an FPGA? Would the power consumption still be the same? I think the kind of back of the envelope calculation like the one in Schneiers article would more difficult with those advantages in mind. – baordog Oct 21 '15 at 19:15
  • @baordog That's much harder to calculate of course since you're suddenly dealing with a highly specialized chip you have to develop yourself rather than a commodity available on the open market. Power requirements would be lower, but your costs are going to be driven by the manpower to develop the ASIC, as well as chip fab. You'd need a person trained in both to even estimate the cost. – Steve Sether Oct 21 '15 at 19:24
4

It is in fact doubtful that "Nation States" are really interested in cracking bcrypt. Cracking bcrypt is what you do when you purloined a list of password hashes from a Web site, and want to obtain some of the passwords to be able to log into these accounts, on that site, or on other sites under the assumption that people tend to reuse passwords. Logging into accounts is active: it tends to leave traces. Spy agencies who deal with some "serious customers" (people who plant bombs, not people who send spam emails), usually, abhor leaving traces of their activities.

What a Nation State would really love is to be able to break password-based encryption, the usual suspects being then GnuPG (with the command-line option -c to password-protect a file) and TrueCrypt (for the people who still use it). Neither uses bcrypt as password-based key derivation function; GnuPG uses its own construction called Iterated and Salted S2K, while TrueCrypt relies on PBKDF2 with 1000 or 2000 iterations (depending on the underlying hash function). There are various estimates of how fast one can go about cracking passwords with these functions; this depends on the number of iterations, which may vary (especially with GnuPG, where this is done with a simple command-line option). See for instance this question for some discussion and pointers.

Basically, both for GnuPG and TrueCrypt, the easy, efficient, and above all discreet hardware to use is GPU, because these are off-the-shelf and benefit from very high production volumes, thus allowing for heavy cost reduction. While theoretically some dedicated ASIC would be even better (almost by definition), it would take a huge number of units (think millions) to actually make it worthwhile from the attacker's point of view. In the case of bcrypt, we often talk about FPGA because bcrypt is quite GPU-unfriendly; but this does not extend to PBKDF2 and OpenPGP's S2K, both hugely benefiting from GPU and making FPGA, comparatively, less attractive.


In my experience, governments are very good at spending money, but not necessarily at getting their money's worth. This partially comes from the fact that a government is not a business, and thus does not have much incentive in terms of cost reduction and RoI. However, let's suppose that, by extraordinary, some big Nation State actually achieved efficient usage of taxpayer money. Then we can make estimates.

For really serious attackers who think in the long term, the dominant cost is electrical power; that cost exceeds the cost of buying and replacing the hardware. For computing centres, the relevant notion is that of Power Usage Effectiveness, which qualifies how much extra energy is needed when feeding your hardware (for cooling, lighting and so on); a PUE of about 1.2 would be already quite good (that's about what Amazon, Microsoft and Google say they achieve). For some discussion on PUE, see this report, especially section 4.

Let's throw some figures at it. An AMD R9 290X can compute about 4 billions of SHA-1 per second (see this site); a 2000-round PBKDF2 with SHA-1 involves 4000 SHA-1 invocations (2000 HMAC/SHA-1 calls), so that's 1 million per second on that GPU. That beast is rated at 250W of Thermal Design Power, a figure that we will use for our estimates (in fact, GPU involved in such compute-intensive tasks tend to consume more than their advertised TDP). Thus, in one hour, the system will hash 3.6 billions of passwords, and consume 300 W·h (250 W·h for the GPU, but this becomes 300 with a PUE of 1.2). Average electricity cost in the USA is about 0.10$ per kW·h, so this put the cost at 0.03$ for hashing 3.6 billions of password. Said otherwise, for 1$, you get to hash 120 billions of password. This is close to 237 so let's keep that figure.

Now, the NSA has an annual budget estimated to a bit more than 10 billions of US dollars (the real budget is classified, but the money comes from taxes so it can still be estimated quite accurately). Assuming that they spend all of it on cracking TrueCrypt passwords, and do so very efficiently (both notions being quite preposterous), then this would allow them to crack up to 10 billions of passwords with an average entropy of 38 bits, per year (38 and not 37, because on average brute force explores half of the space before succeeding). I find it utterly improbable that they could really achieve even 1/100th of that performance, though -- both because they have a lot more other things to do with their budget, and because I don't believe that they would achieve Google-like efficiency. That would put them at 100 millions of passwords per year, as long as the passwords have 38 bits of entropy on average.

While 100 millions if a huge figure, remember that entropy can bite them hard. If they stumble upon a password with 66 bits of entropy (e.g. a password generated with the correct horse method expanded to 6 words, thus still highly human-compatible), then it would take the NSA 2.5 years to crack that password (on average), and they would not be cracking other passwords during all that time. The password had better be valuable -- and the terrorists would also have to be courteous enough to delay the execution of their nefarious plans for a few years, so that the NSA has time to catch up.

Note that TrueCrypt is not very good, as far as password hashing is concerned. It uses PBKDF2, which can be very efficiently optimized on GPU (contrary to bcrypt). It uses only 2000 iterations, a very meagre value. And yet, a single human-compatible password can still defeat the whole of an idealized NSA that would have magically become more efficient than any other government agency in the World.

Presumably, an efficient government agency involved in cracking passwords would have made the same estimates as above, and concluded that they'd better not invest all their budget into password cracking, since it can be so easily defeated. From this I conclude that password-cracking abilities of Nation States are not as high as they are often cracked up to be.

  • I'm not sure I agree that a country wouldn't be interested in password cracking. I wouldn't guess it's very high on the radar, but consider that people do incredibly stupid things, like Hillary Clinton's private email server. Or the alleged cracking of the CIA chiefs AOL account, and him putting classified documents on it. If either of those two re-used passwords from a compromised account, password cracking would be a good tool to try to login to these accounts. Tracks are pretty easy to cover these days. – Steve Sether Oct 21 '15 at 19:50
  • But wouldn't you say that these figures are skewed by access to ASICs/FPGAs that might allow for even greater levels of efficiency? BCrypt may be particularly vulnerable to FPGA attacks: usenix.org/system/files/conference/woot14/woot14-malvoni.pdf – baordog Oct 21 '15 at 19:51
  • This post makes two assumptions I doubt: 1. the NSA is only using its own computers/hardware to crack crypto. 2. the NSA is hunting "terrorists" ;) – Noir Oct 22 '15 at 14:39
  • You may be interested in Bruce Schneier's latest post about "political doxing". Anyone with a political advantage to gain is going to be interested in Doxing, and that includes nation states. schneier.com/blog/archives/2015/11/the_rise_of_pol.html – Steve Sether Nov 2 '15 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.