Hashing Security - Timing attack section clarification about crackstation HOT 4 OPEN

• He sends each string to the on-line system, recording the amount of time it takes the system to respond.
• The string that takes the longest will be the one whose hash's first byte matches the real hash's first byte.
• The attacker now knows the first byte, and can continue the attack in a similar manner on the second byte, then the third, and so on.

Assuming that each attempt to login has a reliable delta between the successful and unsuccessful byte matches (which is probably quite small, the server especially if reasonably active and doing more than just logins; in addition to the network involved.. is going to add quite a bit of jitter. You'd realistically need much more samples than 1 per byte permutation), this still seems impractical?

I'm aware that the salt and hash type etc are known as the article states earlier to the quote, but the only way I see this having any likelihood of working is that you have chosen a wordlist that contains the password of the user being attacked.. that would defeat the need for this attack though.

I say this because the inputs themselves for this attack only have relevance if they're generating the hash outputs with the byte sequences you're interested in, so their content can be random and is unimportant to you. The problem is getting those hash byte sequences.

You're either looking these up from a wordlist you compute in advance (storage requirements), or doing the computation on the fly as you find a match for each byte (time will bottleneck you). Initially it's a non issue, find 256 strings for the 1st byte, when you know the 2nd byte, generate more strings until you have 256 permutations on the 2nd byte with the same 1st byte... it reads small but as the requirement for the byte sequence constraint gets more strict, you're taking much longer to produce each new input to test.

32 bytes, the full SHA-256 hash is such a large amount of permutations 2^256 (or 256^32 if you prefer) that it's near the estimated amount of atoms in the observable universe (approx ~10^80, where 2^256 is ~10^77, that's 77 zeroes!).

The way you describe the attack it, it's easy to think about just the subset, at 31 bytes, all you need is 256 more and you're good right? But you can't use prior inputs to speed that up, you've got to keep generating/iterating inputs that match the initial 31 bytes, and then one of your 256 permutation bytes for the 32nd... that's massive! 🤯

128-bit of entropy (16 bytes of your SHA-256 hash, all permutations) requires enough energy for this sort of attack that it'd be sufficient to boil all the oceans on Earth. 128-bits of entropy (2^128) is approx 3.4e38 (3.4 * 10^38), still a pretty big number 😬

One of us is misunderstanding something here, leaking 32 bytes of a hash this way does not seem feasible in the slightest due to the nature of hashing. Can you help point out where I've misunderstood?

would let you filter down the list to a small number of candidates. Then you could try those candidates on the live system.

This seems to imply you're computing the candidates with proper byte sequence permutations up front which would take a while if you really meant 32 bytes (perhaps you meant the first 4?), but without knowing the sequence upfront the storage and time requirements to produce such a list is considerably higher.

If you're able to not only compute 1 million hashes each second and they're unique values for our 2^32 range (which will get more difficult over time due to non-unique byte sequence, effectively collisions slowing this rate), we'd manage computing this lookup in a little over an hour: ((2^32 / 1e6) / (60*60) = ~1.19).

I don't know how to calculate the time offset from the overhead of filtering out collisions but it's presumably optimistic to average the rate out at 1,000 unique hashes/sec which shifts it to about 50 days. 24-bits is a little over 4 hours at this reduced rate and 16-bits a mere minute, that's something you could benchmark against for better metric I suppose?

Regardless, the time requirement is still going to be problematic? At best we're optimizing by filtering candidates to try against the live validation rate limit.

For reasons covered in my prior message, the partial hash knowledge isn't providing much of a practical benefit, unless the target has a password that fits within in a subset of candidates backed by statistics (eg password leaks/patterns) that you can lookup with your partial hash as a key?

At least that's the only way I see you truncating the first 32-bits, as a lookup to an existing set (good for low hanging fruit), or filtering generated hashes so the rate limit isn't wasted (but the chance of success is infeasible).

My math might be wrong below, not sure.

At the 1 second rate limit there is roughly 16 bits of entropy (~65k attempts) covered in a single day, or 25 bits (~33 million) for a year of attempts. If the attacker can leverage Kerckhoff's principle against the target, then we know how soon we can get success especially if we know the subset of entropy that has been filtered by the partial hash from the timing attack?

Average entropy of user passwords is a little over 40 bits. For a set of values where 1 of them is the target password value unhashed; if we assumed all values mapped to uniform distribution of their hashed equivalents.. knowing the first 32 bits reduces down to <0.4% ((1 / (2^40 / 2^32)) * 100 = ~0.39) or 256 values to check.

Still need to compute the 40-bit wordlist to hash in advance for lookup though, at 1 million per sec, that'll take almost 13 days (((2^40 / 1e6) / (60*60*24) = ~12.7). Then about 17 minutes to derive the 4 byte sequence for partial hash at the 1 second rate limit ((256*4) / 60 = ~17) and then <5 minutes if we only had 255 values left to test (255 / 60 = ~4.3).

In contrast the first 4 bytes of the 32 bytes SHA-256 hash would be <3.7e-66% (1 / (2^256 / 2^32)) * 100 = ~3.7e-66) or about 1 in 2.7e67 (2^224). Not going to make a meaningful difference without a wordlist of much lower entropy..

For context an nvidia RTX 3080 can do bcrypt approx 1,000 hashes/sec at work factor 11 (10-12 should be reasonable to expect on servers today), which would take that above 13 days attack time (where the attacker has plenty of advantages due to Kerckhoff's principle) to almost 35 years (((2^40 / 1e3) / (60*60*24*365) = ~34.9).