6

I'm trying to brute-force my own WiFi, and from my own research, I know that all default passwords for this specific model of router I'm trying to hack follow the following rules:

  1. password length = 8

  2. The character set [a-zA-Z0-9]

  3. Each character can only be used once in the password

  4. A minimum of 2 lowercase, 2 uppercase and 2 numbers are present.

Examples of possible passwords: r3wN4HTl, 5j3Wkl5Da, etc...

How can I proceed with this brute-force, how many combinations will there be, and what would be the estimated time to successfully crack the password?

MiaoHatola
  • 2,284
  • 1
  • 14
  • 22
MaskyS
  • 89
  • 2
  • 2
  • 3

3 Answers3

7

If we assume that your passphrase was randomly generated (not influenced by human selection factors), then some basic math and a couple of tools can get you most of the way there. Your restriction #3 (each character can be used only once) is the harder one, but probably wouldn't really reduce the total combinations space very much, so I recommend setting it aside for now.

Capturing the complexity

First, take a look at the policygen tool from the PACK toolkit. You can generate a set of masks that match your length and minimums.

You can also inform time estimation using policygen's --pps parameter. This tells policygen how many passwords per second your target platform can attempt.

For example, if you have a GPU similar to my GTX 970 SC (which can do 185 kH/s for WPA/WPA2 using hashcat), you'll get something like the following:

$ policygen --pps=185000 --minlength=8 --maxlength=8 \
  --mindigit=2 --minlower=2 --minupper=2 --maxspecial=0 -o test.masks
                       _
     PolicyGen 0.0.2  | |
      _ __   __ _  ___| | _
     | '_ \ / _` |/ __| |/ /
     | |_) | (_| | (__|   <
     | .__/ \__,_|\___|_|\_\
     | |
     |_| iphelix@thesprawl.org


[*] Saving generated masks to [test.masks]
[*] Using 185,000 keys/sec for calculations.
[*] Password policy:
    Pass Lengths: min:8 max:8
    Min strength: l:2 u:2 d:2 s:None
    Max strength: l:None u:None d:None s:0
[*] Generating [compliant] masks.
[*] Generating 8 character password masks.
[*] Total Masks:  65536 Time: >1 year
[*] Policy Masks: 2940 Time: >1 year

$ wc -l test.masks
2940 test.masks

The resulting set of 2940 masks covers the set of all possibilities that match your constraints.

Estimating the time

Notice that policygen estimates the time to be more than 1 year. For closer estimation, you may not be able to predict when your specific passphrase would be cracked, but you can establish an upper bound and an average (half of that upper bound).

Using hashcat's maskprocessor tool, you can get the total number of combinations for a given mask. Running that against each mask, and summing the results:

for mask in `cat test.mask`; do \
    mp64 --combinations $mask; done \
    | awk '{s+=$1} END {print s}'

... yields the following number:

5.84746e+13

or roughly 58474600000000 combinations. Assuming 185,000 hashes per second, that's (5.84746e+13 / 1985000) / 60 / 60 / 24 = 340,95 days, or about one year to exhaust the entire keyspace. The average passphrase would be cracked within half a year (half of time needed to traverse the total keyspace).

Of course, this time estimate is tied directly to the compute power available. As you add more GPUs to the mix, performance will scale linearly with their performance.

Starting the attack

To try to crack it, you would simply feed your WPA2 handshake and your list of masks to hashcat, like so. Note that this rig has more than one GPU.

$ ./hashcat -w 4 -a 3 -m 2500 [your-wpa2-hccapx-filename] test.masks

hashcat (v3.5.0) starting...

OpenCL Platform #1: NVIDIA Corporation
======================================
* Device #1: GeForce GTX 1080, 2028/8113 MB allocatable, 20MCU
* Device #2: GeForce GTX 1080, 2028/8114 MB allocatable, 20MCU
* Device #3: GeForce GTX 1080, 2028/8114 MB allocatable, 20MCU
* Device #4: GeForce GTX 1080, 2028/8114 MB allocatable, 20MCU
* Device #5: GeForce GTX 970, 1009/4037 MB allocatable, 13MCU
* Device #6: GeForce GTX 970, 1009/4037 MB allocatable, 13MCU

OpenCL Platform #2: Advanced Micro Devices, Inc.
================================================
* Device #7: AMD FX(tm)-8350 Eight-Core Processor, skipped.

Hashes: 1 digests; 1 unique digests, 1 unique salts
Bitmaps: 16 bits, 65536 entries, 0x0000ffff mask, 262144 bytes, 5/13 rotates

Applicable optimizers:
* Zero-Byte
* Single-Hash
* Single-Salt
* Brute-Force
* Slow-Hash-SIMD

Watchdog: Temperature abort trigger set to 90c
Watchdog: Temperature retain trigger disabled.

[s]tatus [p]ause [r]esume [b]ypass [c]heckpoint [q]uit =>


Session..........: hashcat
Status...........: Running
Hash.Type........: WPA/WPA2
Hash.Target......: 8381533406003807685881523 (AP:ae:f5:0f:22:80:1c STA:98:7b:dc:f9:f9:50)
Time.Started.....: Sun Apr  9 07:30:31 2017 (1 sec)
Time.Estimated...: Sun Apr  9 08:08:54 2017 (38 mins, 22 secs)
Guess.Mask.......: ?d?d?d?d?l?l?u?u [8]
Guess.Queue......: 1/2940 (0.03%)
Speed.Dev.#1.....:   401.7 kH/s (403.50ms)
Speed.Dev.#2.....:   402.4 kH/s (405.15ms)
Speed.Dev.#3.....:   405.4 kH/s (402.24ms)
Speed.Dev.#4.....:   403.3 kH/s (400.39ms)
Speed.Dev.#5.....:   187.0 kH/s (283.22ms)
Speed.Dev.#6.....:   185.3 kH/s (285.72ms)
Speed.Dev.#*.....:  1985.0 kH/s
Recovered........: 0/1 (0.00%) Digests, 0/1 (0.00%) Salts
Progress.........: 0/4569760000 (0.00%)
Rejected.........: 0/0 (0.00%)
Restore.Point....: 0/456976000 (0.00%)
Candidates.#1....: 1234maMA -> 1618pqAN
Candidates.#2....: 1218pqAN -> 1667yzMA
Candidates.#3....: 1242yzMA -> 1631tgBA
Candidates.#4....: 1771seGO -> 1558paAN
Candidates.#5....: 1784jaAN -> 1816blON
Candidates.#6....: 1261tgBA -> 1523reGO
HWMon.Dev.#1.....: Temp: 63c Fan: 90% Util:100% Core:1822MHz Mem:4513MHz Bus:8
HWMon.Dev.#2.....: Temp: 55c Fan: 90% Util:100% Core:1809MHz Mem:4513MHz Bus:4
HWMon.Dev.#3.....: Temp: 56c Fan: 90% Util:100% Core:1822MHz Mem:4513MHz Bus:16
HWMon.Dev.#4.....: Temp: 50c Fan: 90% Util:100% Core:1822MHz Mem:4513MHz Bus:4
HWMon.Dev.#5.....: Temp: 54c Fan: 60% Util:100% Core:1379MHz Mem:3004MHz Bus:1
HWMon.Dev.#6.....: Temp: 58c Fan: 60% Util:100% Core:1366MHz Mem:3004MHz Bus:1

hashcat will start working through your list of masks, one at a time. Since policygen sorts masks in (roughly) complexity order, the fastest masks appear first in the list. So each mask will tend to take (roughly) more time than the previous ones.

You'll probably not want to wait around until it's done, though. :)

Tom K.
  • 7,913
  • 3
  • 30
  • 53
Royce Williams
  • 9,128
  • 1
  • 31
  • 55
  • And that's why WPA2 is still considered quite secure :p – Walfrat Apr 10 '17 at 07:42
  • That's assuming, of course, that brute force is required. Most passwords are based on non-random password patterns that are well-known to crackers, and fall much sooner. – Royce Williams Apr 10 '17 at 13:43
  • Any idea for how much non random pattern fall faster ? (10, 100 times ?)Assuming better than @zerty12 ? 5 years / 100 is still 19 days. – Walfrat Apr 10 '17 at 14:06
  • That question falls into the realm of password strength estimation, which is tricky. Passwords from well-known dictionaries ("123456", "password123", etc.) fall first. Well-known patterns like 'September2017!", "[kidsname][birthyear]", etc. fall very quickly, too. Perhaps a thousand times faster or more. Human-generated strings are more likely to fall early and are generally bad password choices. Even phrases like "itsmypartyandillcryifiwantto" is poor. You can mitigate this by using slow hashes (bcrypt, scrypt, PBKDF2) with high work factors, but the difference is huge. – Royce Williams Apr 10 '17 at 19:07
  • Of course I didn't expect an exact estimation, I just wanted a rough idea, and I was talking about WPA2 which seems to be too fast to compute now ? – Walfrat Apr 11 '17 at 07:17
  • What exactly is that estimated time in your listing? It seems too low. :) – Elias Apr 11 '17 at 10:48
  • That's just the time estimate for the first mask in the list (?d?d?d?d?l?l?u?u). :) – Royce Williams Apr 12 '17 at 03:21
  • So roughly speaking your rig would take around 90-100 days? – MaskyS Apr 29 '17 at 16:26
  • More than that - look at the estimates and aggregate speeds shown above. On my rig, it would take on the order of 9 to 10 *years*. – Royce Williams Apr 30 '17 at 05:16
  • Hmmm, pardon me if I'm wrong, but that just doesn't sound right to me. Your rig has a total cracking speed of 1895 kH/s. Given the number of possible combinations are 5.84746e+13, the estimated time would be 5.84746e+13 / (1895000 / 60 / 60 / 24) = ~357, wouldn't it? Or if we go by the masks it would roughly take (lots of guesswork here) ~240 days max? – MaskyS Apr 30 '17 at 18:52
  • Masky, you're right - I was confusing my per-card speed with my full-rig speed. Your numbers are on the right order. – Royce Williams May 01 '17 at 17:45
  • 1
    Actually it's not `1895000` but `1985000` (the value after `Speed.Dev.#*`) so the result is 340,95 days. – Tom K. Feb 07 '18 at 15:47
  • Good catch, and good edit! – Royce Williams Feb 07 '18 at 19:45
  • @RoyceWilliams Maybe you could shed some light on the calculation of the quantity of permutations? See answer by user unknown. – Tom K. Feb 08 '18 at 07:58
  • Honestly not sure where the gap is - my method was admittedly back-of-the-napkin, though unless there's a bug in policygen, I would expect it to be accurate. For what it's worth, here are the masks generated (if someone else wants to try to reproduce or analyze): https://gist.github.com/roycewilliams/619be2ed18322f5b6e826c911cc82a0d – Royce Williams Feb 08 '18 at 17:22
1

I have a different method to calculate this thing, and unfortunately reach another value.

You have to use 2 digits at least, so for the first one, there are 10 possibilities, for the second 9, which makes 90 possible pairs.

Analog for letters 26*25 combinations upper and lowercase.

After chosing 6 characters this way, we have freedom for the last two, which is (26+26+10-6)=(62-6)=56 and 55 for the last one.

In combination this is ((10*9*26*25*26*25*56*55)) combinations, just for the characters, the password might consist of, without knowing the right order.

That's 117 117 000 000 (117 Billion, 1.2e12).

Multiplied the 8!=(40320) shufflings per combination possible, I reach therefore 

4 722 157 440 000 000 (4.7e16)

I don't know where the difference is coming from, especially not, what binom(26, lower) means.

If I factorize both results, I get this: 

factor $((10*9*26*25*26*25*56*55*40320)) 
4722157440000000: 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 5 5 5 5 5 5 5 7 7 11 13 13

factor 58474600000000
58474600000000: 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 61 4793

I don't understand where the 4793 is coming from - as well, as the 61. For my result, I think it looks reasonable: 2x26 can be factorized to 2x(2x13), the 11 is from 5x11=55 and so on.

user unknown
  • 484
  • 5
  • 11
  • "or **roughly** 58474600000000". Probably not all decimal places are shown in the value in the accepted answer, that's why the factorization shows weird numbers like 4793. – Tom K. Feb 07 '18 at 15:38
  • As you can see, my number is not rounded but precise and has only one Zero less (lots of 10s and 5 and 2 in multiplication involved). However, maybe it showed up as 5.84746e13. But can you explain the big difference between 5e13 and 4e16? Elias is in the same range as Royce and explains the small diffrence (repetition not allowed). – user unknown Feb 07 '18 at 15:48
  • The value was calculated with [maskprocessor](https://hashcat.net/wiki/doku.php?id=maskprocessor), so I don't know how exactly it was calculated. But to be honest, I don't understand the steps you are taking either. There can, for example, be more than two digits. I don't understand why you subtract `6` from `10` in paragraph 4. I guess this refers to digits, but I don't know how you got to that conclusion. And last but not least, I'm not even sure it was worth necroing this post over a calculation of the possible amount of possible passwords. – Tom K. Feb 07 '18 at 15:57
  • I first fill a bucket of length 8 with possible combinations. First, there are 2 digits out of 10 without repetition, which is 10*9 possibilities. Then I fill 4 mandatory characters. In the end, there are two positions left. For the first one, there are 8 digits left, 24 lower and 24 upper case, which makes a total of 56 choices (or (26+26+10-6), the type does not longer matter. For the last one there are 55 choices. After chosing all elements, the order is selected by shuffling. Clearer now? Necroing: Well I found it, and so do others. And I think the answers so far aren't right. – user unknown Feb 07 '18 at 17:03
0

I dream of a future where all questions to teach combinatorics are "How many passwords following these criteria exist?".

Let's have some fun.

First, you have 62 characters, 8 of those make about 2.18e14 possibilities. So that's an upper bound. Since we also use every character at most once according to condition 4 this comes down to 62 * 61 * ... * 55 possibilities or about 1.36e14.

Second, we need at least 2 lowercase, 2 uppercase and 2 numbers. If we only count how many times each category occurs all passwords fall into 2 out-of 4 = 6 categories.

  1. 4L + 2U + 2D or 2L + 4U + 2D
  2. 2L + 2U + 4D
  3. 3L + 3U + 2D
  4. 3L + 2U + 3D or 2L + 3U + 3D

For each category we have binom(26, lower) * binom(26, upper) * binom(10, digits) possible selections of letters and 8! permutations of the selection. (The fact that letters are not allowed to repeat make things a lot easier here.)

That gives a total of about 3.90e13 possible passwords. (The policygen tool that Royce used doesn't allow specifying that every letter can be used only once so this number is slightly lower.)

Elias
  • 1,915
  • 1
  • 9
  • 17
  • Well, it's not even a factor of 2 lower. I don't think you'll find a better answer than Royce's if you want to practically do it. Adding a condition to avoid repetitions to hashcat might be pretty easy. – Elias Apr 11 '17 at 10:50
  • I'm not aware of a toolset that allows specifying that a character can only be used once. I also do not expect that such a restriction would materially reduce the cracking time. – Royce Williams Jun 06 '17 at 02:57