Lastpass cracking speed

[pragmatic]

Presumably people have been seeing the lastpass breach news around. I was confused on one point about the hashing mechanism they are using and the speed at which oclhashcat can attack it, so I'm hoping someone might be able to point out where i'm going wrong.

The reports say this is 100,000 rounds of PBKDF2-HMAC-SHA256. I was under the impression this is analogous to oclhashcat mode 10900. I saw reports from our own epixoip that the cracking speed for this set up would be < 10 H/s even on the TitanX, however i'm seeing different numbers so I was curious to get some clarification.

From the below (bogus hash abbreviated output):

$ ./oclHashcat64.bin -a 3 -m 10900 sha256:99999:2u/ADvs2B8VuxUO/+4PmpxjZ/fn+b/9mc1o8cBmd2M8WWhh5WTgSKArGUw0NaJ8 ?a?a?a?a?a?a

Session.Name...: oclHashcat
Status.........: Running
Input.Mode.....: Mask (?a?a?a?a?a?a) [6]
Hash.Target....: sha256:99999:2u/ADvs2B8VuxUO/+4PmpxjZ/fn+...
Hash.Type......: PBKDF2-HMAC-SHA256
Speed.GPU.#1...: 1980 H/s

I am using 99,999 iterations because oclhashcat doesn't seem to support 100,000 iterations, but obviously the speed difference should be negligent between 99,999 and 100,000.

The speed I'm seeing here, just under 2000 H/s, is obviously way more than 10. I trust epixiop alot more than I trust myself in this space, so i'm wondering what i'm doing wrong here.

Is this?

1. Not an equivalent mode to what lastpass is using?
   
2. Not how you specify iterations? (i.e. i'm not really doing 99,999 iterations here)
   
3. Something else I'm doing wrong?
   

Any feedback would be welcome.

[Sc00bz]

I saw reports from our own epixoip that the cracking speed for this set up would be < 10 H/s even on the TitanX, however i'm seeing different numbers so I was curious to get some clarification.

I think he meant <10 kH/s. Just looking at benchmarks for 8 Titan X on https://hashcat.net/oclhashcat/ for SHA256 it's 16904 MH/s so 16,904,000,000 / 8 GPUs / 2 HMAC / 100,000 rounds = 10,565 H/s but it's probably a little lower do to other factors.

(Note this is a rough estimate)

[epixoip]

You're right, ol epixoip done fucked up on this one. Thank you for catching this error!

I was being lazy and didn't benchmark with 99999 iterations, I just took the the -b speed (1000 iterations) and divided it by 100. Or at least that's what I intended to do -- I actually divided by 100,000 by accident! Got that number 100,000 stuck in my head...

So while I should have done 938850 / 100 = 9.38 KH/s, I actually did 938850 / 100000 = 9.38 H/s!

The cool thing is even being off by three orders of magnitude, it's still over 32x slower than WPA2 for a single salt. Oh and don't forget that there's still an additional 5000+ PBKDF2-HMAC-SHA256 rounds and an additional SHA256 operation in the mix:

938850 / 105.001 = 8.9 KH/s

So yeah, not as slow as I incorrectly thought, but still proper slow

[atom]

I've the feeling I need to clarify the following:

Speed.GPU.#1...: 1980 H/s

You are clearly missing -w 3

and

for SHA256 it's 16904 MH/s so 16,904,000,000 / 8 GPUs / 2 HMAC / 100,000 rounds = 10,565 H/s

Things are alot different. For a raw estimation it's ok, but from this numbers it looks like oclHashcat would be inefficient and loose like 10 times the speed just by pbkdf2 operations between the sha256 transformation calls. That's not the case!

For a very bad reference, this is the 290x speed cracking sha256 with oclHashcat:

Speed.GPU.#1...: 1550.6 MH/s

But to reach such a high guessing speed, oclHashcat uses alot of optimizations. The thing is that only some of them can be used within pbkdf2-hmac-sha256, but the most important ones can not.

When oclHashcat starts up you get a list of optimization applied to raw sha256:

* Zero-Byte
* Precompute-Init
* Precompute-Merkle-Demgard
* Early-Skip
* Not-Salted
* Not-Iterated
* Single-Hash
* Single-Salt
* Brute-Force
* Scalar-Mode
* Raw-Hash

The most important ones are:

* Zero-Byte
* Precompute-Init
* Precompute-Merkle-Demgard
* Early-Skip

For details what they do, please refer to: https://hashcat.net/events/p13/js-ocohaaaa.pdf

But none of them can be used for pbkdf2. Well Zero-Byte can partially, not not as efficient as in raw sha256. This is mostly because of the HMAC, which fills a first buffer with the size of the blocksize of the hash. This is not a fixed data and it depends on the password, so we can not do Precompute-Init and because this we can also not do Precompute-Merkle-Demgard. We could do Early-Skip but in comparison to raw sha256 where you save a bit over 3 steps of 64. it would be only for the last of the 200000 iterations so its nearly nothing.

We can do a special attack to remove the effect of the zero byte optimizations like this:

/oclHashcat64.bin -m 1400 hash.sha256 -a 3 -w 3 ?b?b?b?b?b?b?baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa -d 1

Now, the speed drops from 1550MH to the following number:

Speed.GPU.#1...: 1466.0 MH/s

That's still without the early exits which is worth 3 of 64 steps. The Precompute-Init also saves roughly 2 of 64 steps on the start, so we have to reduce the 1466 * (59/64) which is ~ 1351 MH/s. Now with this value (which still includes Precompute-Merkle-Demgard optimization) we can do the division of 200000. That would be a final speed of 6750 H/s.

Now, if take a look at what oclHashcat makes:

root@et:~/oclHashcat-1.37# ./oclHashcat64.bin -m 10900 hash -w 3 -a 3 ?b?b?b?b?b?b -d 1
...
Speed.GPU.#1...: 6556 H/s

In other words, it's really close to the maximum performance. Also note the candidates already includes markov-chain based optimizations so its not just AAA, AAB, etc. this also takes a bit of time.

PS: Actually for pbkdf2-hmac we have 4 calls to the hashing function per iteration but we can precompute the first block (ipad) so that we end up with 2 * number of iterations.

[pragmatic]

Thanks for the feedback, lots of great info there.

The -w 3 certainly made a huge difference, a single 7970 went from just under 2k H/s to just under 5k H/s.

/Looking forward to seeing people at PasswordsCon!

[forumhero]

anyone know if cracking that master password allows them to unlock all the user's passwords offline? or would they need to sign-on to lastpass's app?

[undeath]

Retrieving the master password would generally allow someone to decrypt the vault but lastpass claims the attackers did not gain access to the vaults. Hence they'd need to use the online login. Therefore the recommendation to change the master password.