0

What is the chance that my WiFi passphrase has the same WPA2 hash as a password present in an adversary's character based brute force password search space, after a 30% is searched.

WiFi PSK WPA2 uses my secret (randomly chosen words) passphrase, my SSID (not random), and a 32-bit iteration counter to derive a base key through PBKDF2.

Suppose an adversary uses a simple character based exhaustive search in a search space that covers all SHA1 hashes, in order to guess my WiFi key (PSK). My long passphrase is not within that password search space. Given the assumption of an exhaustive search, the hash of my passphrase (+SSID+counter) must clash with at least one hash of guesses tried within the search space of my adversary.

What is the chance that, if my adversary searches through, for example, 30% of that character based brute force search space, my passphrase's hash is found because it has the same (clash) hash as a member within that 30% space? Does the fact that my phrase is not a member of my adversary's space, influence the calculations given in What is the collision chance of a 128-bit hashing function if it is always fed with 256-bits of data?

The reason I know my passphrase is not within the password based search space is the following: A simple brute force exhaustive search on a 160 bits hash would at most test a 25 char length password like uAQn]uG#{3iM1r^jyxL5!uB@*, which corresponds to around 160 bits, if chars are randomly chosen

My passphrase exist of 6 randomly chosen words, the minimum that Diceware recommends currently, such as ListChaferInsureFinnDipperManger containing 32 characters.

Improve this question
7
  • You haven't specified the length of the passwords in the adversary's search space. 30% of a million-bit search space is still a lot; 30% of all 6-character strings is embarrassingly small.
    – Reid Rankin
    Nov 17, 2016 at 4:21
  • @ Reid Rankin That's right. For the question it just counts that the adversary's space contains all passwords that generate all possible 160bit-hashes. And since the assumption is simple brute force to fill that space, it will contain all passwords up to about 26 characters/symbols (ignoring collisions, but perhaps collisions should not be ignored for the question)
    – Dick99999
    Nov 17, 2016 at 12:12
  • Why would an attacker try a brute-force character based search first, as opposed to a dictionary-based attack with combinations and transformations?
    – Ben
    Feb 9, 2017 at 16:32
  • @Ben What is the relation to the question posted? What I can imagine is that both methods generate password candidates and in that sense the question could be asked for dictionary attacks too. In that case 'first' is not applicable, I think,
    – Dick99999
    Feb 13, 2017 at 18:01
  • Because assessing the strength of your password by assuming an idiotic attacker is useless. The question "what are the chances of finding my word-based password using character-based search?" is irrelevant, because nobody will ever try to do that. It's MUCH easier (but still not feasible) to just cycle through all the 6-word diceware passwords.
    – Ben
    Feb 13, 2017 at 23:49

2 Answers 2

Reset to default
1

If I understand you Correct you ask the likelihood of a successful SHA1 Second-Preimage attack at a Brute Force Search with 30% of the Search space … (German dude). (Assume your Password is in the Search Space) The General Input/Output length is 160 Bit=log2(n) if we calculate the search space for a Random Permutation function like SHA1 we can assume that it is n*(1-(1/e)), n*(1-(1 - 1/n)^n)), Recourse e = lim(1+1/n)^n so if he try x Password’s he has the Possibility n*(1-(1 - 1/n)^x)), so if he has searched 30% of a 160 Bit (Random Permutation Injective) Search-space. he has searched an average space of n*(1-((1-1/(n))^(x = n *0.3))) / (n * (1-(1/e)) =~= 0.41 for x = 2^160*0.3, n = 2^160. the likelihood for the Breaking of your Random SHA1 Hash with a (Bijective Random) Brute-Force attack is (30% Search-space) 41%.

(Assume your Password is not in the Search Space)

We can derivate that likelihood with the (Gesetz der kleinen Zahlen)

• 36.3 % *0 in the Search space

• 37.3 % *1 in the Search space

• 18.6 % *2 in the Search space

• 6.0 % *3 in the Search space

• 1.7 % *4 in the Search space

So the likelihood for your Input to have a second Primage is (1/(1-0.363))*(100-37.3%) = (41%)(100/1,57…) this means what the likelihood for you to have a password with a second Primage and in the 30% search space is about: Summe:

0.373 * 1.57  = 58.56 % = 0.5856 (*1) (Not in Search space)

0.186 * 1.57  = 29.20 % = 0.2920(*2)

0.060 * 1.57 = 9.57 % = 0.0956(*3)

0.017 * 1.57 = 2.71  % = 0.0271(*4)

…. With this Values we can Calculate the likelihood of encounter a Second Preimage of your input We use the Above value n*(1-((1-1/(n))^(x = n *0.3))) / (n * (1-(1/e)) =~= 0.41 and Calculate the Possibility of a found (0.41 * 2 * 0. 2920) + (0.41 * 3 * 0.0956) + (0.41 * 4 * 0.0271) … =~= 0.162.. So the likelihood is about 16.2% … with my really bad rounding it’s likely to be not so Precise. If you now it has a Second Preimage (With the Count of Collisions) its (0.41 * (Collison count)) if I am not wrong ….

The values are not really Precise so I would recommend to Calculate the whole thing yourself  If I have a Calculation Error Please write it down below & Don’t hit me … (Its my First Post so :/).

Oh and if you mean that the Input is larger than the output, yes it relativate it self for the Search space ... the Possibility of a Second existing Preimage in a Case like 256/160 is likely to be 100%. (Depending on the mode of the Hashing)

Improve this answer
5
  • Thanks for the math. I have refined my question, so it's clearer that my passphrase is not in the search space of passwords of my adversary (your second case).
    – Dick99999
    Nov 16, 2016 at 17:27
  • @Somedude, Welcome to Security Stack Exchange!
    – 700 Software
    Nov 16, 2016 at 17:51
  • @Somedude Do you mean with (Gesetz der kleinen Zahlen) that you tried a small number of cases and think that the listed percentages will somewhat hold in the general case? Or has it a different meaning in German?
    – Dick99999
    Nov 16, 2016 at 20:51
  • en.wikipedia.org/wiki/Poisson_distribution
    – Somedude
    Nov 17, 2016 at 13:31
  • It Calculates the probability of m hits on a random value in the range n with n try's. And this Values convergence to Constants. the (Gesetz der kleinen Zahlen) is a Spezial case for Roulette with n = 37 (That is Relativ good for small Calculation's)
    – Somedude
    Nov 17, 2016 at 13:37
1

Since you've defined the password search space to be 160 bits large, and the hash is 160 bits itself, you're just talking about a scenario in which the attacker has tried 30% of all hashes. The chance that they will have found yours is thus 30% (very slightly less, but collisions within the attacker's search space are negligible, so you can ignore them safely).

However, I'd note that searching 30% of a 160-bit space is a 158.26-bit problem. As such, there is no attacker on the planet that can accomplish this, nor will there be until we start building Dyson spheres.

Improve this answer
5
  • Sounds very simple indeed. Thanks. I take it that it's true because of the uniform distribution of the SHA 1 hashes themselves? Even if my passphrase is (partly) not a randomly chosen one? You're right about the 30%. That was just an example.
    – Dick99999
    Nov 17, 2016 at 15:46
  • Correct. And since you're hashing your password, only the entropy matters, not how you chose the specific string of characters. I recommend Diceware passwords for wireless networks quite regularly.
    – Reid Rankin
    Nov 17, 2016 at 15:56
  • 1
    Also note that an attacker will not actually ever perform this attack. They might as well skip the expensive hashing step and just brute force the key directly.
    – Reid Rankin
    Nov 17, 2016 at 15:58
  • An off-topic? I understand that my passphrase is the PSK. That is somehow transformed into a PMK by using PBKDF2. That PMK is used to generate the PTK (802 session key). One catches that session key, but still has to guess the PSK and execute the expensive hashing step when cracking. If not, wouldn't Hashcat be much faster for cracking WPA2?
    – Dick99999
    Nov 17, 2016 at 21:09
  • 1
    If you were planning to brute-force a 160-bit keyspace anyway, you'd brute force the PMK instead of the passphrase and skip the hashing step. The reason noone does this is because noone can actually complete a 160-bit brute force attack. I'm just pointing out that the idea of an attacker that can search any appreciable percentage of a 26-character alphanumeric space is ludicrous, and that an attacker who could do so could also break some of our must trusted cryptographic primitives.
    – Reid Rankin
    Nov 17, 2016 at 21:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .