Skip to content

Instantly share code, notes, and snippets.

@bryanward-net

bryanward-net/shortssided.py

Last active February 18, 2023 16:20
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bryanward-net/3787585868d2c14cadea9958e6145b4c to your computer and use it in GitHub Desktop.
Save bryanward-net/3787585868d2c14cadea9958e6145b4c to your computer and use it in GitHub Desktop.
Download ZIP
A CRC-32 Reverser, intended for use in translating the ShortSSID subfield in the TBTT of the RNR of the 802.11 beacon frame. See https://bryanward.net/wp/2022/11/30/short-ssid-ed/ for details
Raw
shortssided.py
#!/usr/bin/env python3
#####
##### shortssided.py
##### A CRC-32 Reverser, intended for use in translating the ShortSSID subfield in the TBTT of the RNR of the 802.11 beacon frame.
#####
##### Usage:
##### ./shortssided.py reverse 0x4FF8348A
##### Produces a list of source values that result in that ShortSSID value.
#####
##### See https://bryanward.net/wp/2022/11/29/short-ssid-ed/ for more details.
##### Based on work from https://github.com/theonlypwner/crc32
##### and http://www.danielvik.com/2013/07/rewinding-crc-calculating-crc-backwards.html
#####
import argparse
import os
import sys
# Limit to the following characters. Sorry if you use emoji in your SSIDs...
permitted_characters = set(
map(ord, 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890_- '))
args = None
def get_poly():
poly = parse_dword(args.poly)
if args.msb:
poly = reverseBits(poly)
check32(poly)
return poly
def get_input():
if args.instr:
return tuple(map(ord, args.instr))
with args.infile as f: # pragma: no cover
return tuple(map(ord, f.read()))
def out(msg):
args.outfile.write(msg)
args.outfile.write(os.linesep)
table = []
table_reverse = []
def init_tables(poly, reverse=True):
global table, table_reverse
table = []
# build CRC32 table
for i in range(256):
for j in range(8):
if i & 1:
i >>= 1
i ^= poly
else:
i >>= 1
table.append(i)
assert len(table) == 256, "table is wrong size"
# build reverse table
if reverse:
table_reverse = []
found_none = set()
found_multiple = set()
for i in range(256):
found = []
for j in range(256):
if table[j] >> 24 == i:
found.append(j)
table_reverse.append(tuple(found))
if not found:
found_none.add(i)
elif len(found) > 1:
found_multiple.add(i)
assert len(table_reverse) == 256, "reverse table is wrong size"
if found_multiple:
out('WARNING: Multiple table entries have an MSB in {0}'.format(
rangess(found_multiple)))
if found_none:
out('ERROR: no MSB in the table equals bytes in {0}'.format(
rangess(found_none)))
def calc(data, accum=0):
accum = ~accum
for b in data:
accum = table[(accum ^ b) & 0xFF] ^ ((accum >> 8) & 0x00FFFFFF)
accum = ~accum
return accum & 0xFFFFFFFF
def rewind(accum, data):
if not data:
return (accum,)
stack = [(len(data), ~accum)]
solutions = set()
while stack:
node = stack.pop()
prev_offset = node[0] - 1
for i in table_reverse[(node[1] >> 24) & 0xFF]:
prevCRC = (((node[1] ^ table[i]) << 8) |
(i ^ data[prev_offset])) & 0xFFFFFFFF
if prev_offset:
stack.append((prev_offset, prevCRC))
else:
solutions.add((~prevCRC) & 0xFFFFFFFF)
return solutions
def findReverse(desired, accum):
solutions = set()
accum = ~accum
stack = [(~desired,)]
while stack:
node = stack.pop()
for j in table_reverse[(node[0] >> 24) & 0xFF]:
if len(node) == 4:
a = accum
data = []
node = node[1:] + (j,)
for i in range(3, -1, -1):
data.append((a ^ node[i]) & 0xFF)
a >>= 8
a ^= table[node[i]]
solutions.add(tuple(data))
else:
stack.append(((node[0] ^ table[j]) << 8,) + node[1:] + (j,))
return solutions
# Tools
def parse_dword(x):
return int(x, 0) & 0xFFFFFFFF
def reverseBits(x):
# http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
# http://stackoverflow.com/a/20918545
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
return x & 0xFFFFFFFF
# Compatibility with Python 2.6 and earlier.
if hasattr(int, "bit_length"):
def bit_length(num):
return num.bit_length()
else:
def bit_length(n):
if n == 0:
return 0
bits = -32
m = 0
while n:
m = n
n >>= 32
bits += 32
while m:
m >>= 1
bits += 1
return bits
def check32(poly):
if poly & 0x80000000 == 0:
out('WARNING: polynomial degree ({0}) != 32'.format(bit_length(poly)))
out(' instead, try')
out(' 0x{0:08x} (reversed/lsbit-first)'.format(poly | 0x80000000))
out(' 0x{0:08x} (normal/msbit-first)'.format(reverseBits(poly | 0x80000000)))
def reciprocal(poly):
''' Return the reversed reciprocal (Koopman notatation) polynomial of a
reversed (lsbit-first) polynomial '''
return reverseBits((poly << 1) | 1)
def print_num(num):
''' Write a numeric result in various forms '''
out('num: {0}'.format(num))
out('hex: 0x{0:08x}'.format(num))
out('dec: {0:d}'.format(num))
out('oct: 0o{0:011o}'.format(num))
out('bin: 0b{0:032b}'.format(num))
out('txt: {0}'.format(bytearray.fromhex(format(num,'x'))))
import itertools
def ranges(i):
for kg in itertools.groupby(enumerate(i), lambda x: x[1] - x[0]):
g = list(kg[1])
yield g[0][1], g[-1][1]
def rangess(i):
return ', '.join(map(lambda x: '[{0},{1}]'.format(*x), ranges(i)))
# Parsers
def get_parser():
''' Return the command-line parser '''
parser = argparse.ArgumentParser(
description="Reverse, undo, and calculate CRC32 checksums")
subparsers = parser.add_subparsers(metavar='action')
poly_flip_parser = argparse.ArgumentParser(add_help=False)
subparser_group = poly_flip_parser.add_mutually_exclusive_group()
subparser_group.add_argument(
'-m', '--msbit', dest="msb", action='store_true',
help='treat the polynomial as normal (msbit-first)')
subparser_group.add_argument('-l', '--lsbit', action='store_false',
help='treat the polynomial as reversed (lsbit-first) [default]')
desired_poly_parser = argparse.ArgumentParser(add_help=False)
desired_poly_parser.add_argument(
'desired', type=str, help='[int] desired checksum')
default_poly_parser = argparse.ArgumentParser(add_help=False)
default_poly_parser.add_argument(
'poly', default='0xEDB88320', type=str, nargs='?',
help='[int] polynomial [default: 0xEDB88320]')
accum_parser = argparse.ArgumentParser(add_help=False)
accum_parser.add_argument(
'accum', type=str, help='[int] accumulator (final checksum)')
default_accum_parser = argparse.ArgumentParser(add_help=False)
default_accum_parser.add_argument(
'accum', default='0', type=str, nargs='?',
help='[int] starting accumulator [default: 0]')
outfile_parser = argparse.ArgumentParser(add_help=False)
outfile_parser.add_argument('-o', '--outfile',
metavar="f",
type=argparse.FileType('w'),
default=sys.stdout,
help="Output to a file instead of stdout")
infile_parser = argparse.ArgumentParser(add_help=False)
subparser_group = infile_parser.add_mutually_exclusive_group()
subparser_group.add_argument('-i', '--infile',
metavar="f",
type=argparse.FileType('rb'),
default=sys.stdin,
help="Input from a file instead of stdin")
subparser_group.add_argument('-s', '--str',
metavar="s",
type=str,
default='',
dest='instr',
help="Use a string as input")
subparser = subparsers.add_parser('flip', parents=[outfile_parser],
help="flip the bits to convert normal(msbit-first) polynomials to reversed (lsbit-first) and vice versa")
subparser.add_argument('poly', type=str, help='[int] polynomial')
subparser.set_defaults(
func=lambda: print_num(reverseBits(parse_dword(args.poly))))
subparser = subparsers.add_parser('reciprocal', parents=[outfile_parser],
help="find the reciprocal (Koopman notation) of a reversed (lsbit-first) polynomial and vice versa")
subparser.add_argument('poly', type=str, help='[int] polynomial')
subparser.set_defaults(func=reciprocal_callback)
subparser = subparsers.add_parser('table', parents=[outfile_parser,
poly_flip_parser,
default_poly_parser],
help="generate a lookup table for a polynomial")
subparser.set_defaults(func=table_callback)
subparser = subparsers.add_parser('reverse', parents=[
outfile_parser,
poly_flip_parser,
desired_poly_parser,
default_accum_parser,
default_poly_parser],
help="find a patch that causes the CRC32 checksum to become a desired value")
subparser.set_defaults(func=reverse_callback)
subparser = subparsers.add_parser('undo', parents=[
outfile_parser,
poly_flip_parser,
accum_parser,
default_poly_parser,
infile_parser],
help="rewind a CRC32 checksum")
subparser.add_argument('-n', '--len', metavar='l', type=str,
default='0', help='[int] number of bytes to rewind [default: 0]')
subparser.set_defaults(func=undo_callback)
subparser = subparsers.add_parser('calc', parents=[
outfile_parser,
poly_flip_parser,
default_accum_parser,
default_poly_parser,
infile_parser],
help="calculate the CRC32 checksum")
subparser.set_defaults(func=calc_callback)
return parser
def reciprocal_callback():
poly = parse_dword(args.poly)
check32(poly)
print_num(reciprocal(poly))
def table_callback():
# initialize tables
init_tables(get_poly(), False)
# print table
out('[{0}]'.format(', '.join(map('0x{0:08x}'.format, table))))
def reverse_callback():
# initialize tables
init_tables(get_poly())
# find reverse bytes
desired = parse_dword(args.desired)
accum = parse_dword(args.accum)
# 4-byte patch
patches = findReverse(desired, accum)
for patch in patches:
text = ''
if all(p in permitted_characters for p in patch):
text = '{}{}{}{} '.format(*map(chr, patch))
out('4 bytes: {}{{0x{:02x}, 0x{:02x}, 0x{:02x}, 0x{:02x}}}'.format(text, *patch))
checksum = calc(patch, accum)
out('verification checksum: 0x{:08x} ({})'.format(
checksum, 'OK' if checksum == desired else 'ERROR'))
def print_permitted_reverse(patch):
patches = findReverse(desired, calc(patch, accum))
for last_4_bytes in patches:
if all(p in permitted_characters for p in last_4_bytes):
patch2 = patch + last_4_bytes
out('{} bytes: {} ({})'.format(
len(patch2),
''.join(map(chr, patch2)),
'OK' if calc(patch2, accum) == desired else 'ERROR'))
# 5-byte alphanumeric patches
for i in permitted_characters:
print_permitted_reverse((i,))
# 6-byte alphanumeric patches
for i in permitted_characters:
for j in permitted_characters:
print_permitted_reverse((i, j))
# 7-byte alphanumeric patches
for i in permitted_characters:
for j in permitted_characters:
for k in permitted_characters:
print_permitted_reverse((i, j, k))
# 8-byte alphanumeric patches
for i in permitted_characters:
for j in permitted_characters:
for k in permitted_characters:
for l in permitted_characters:
print_permitted_reverse((i, j, k, l))
#If you want longer, add more code here...
def undo_callback():
# initialize tables
init_tables(get_poly())
# calculate checksum
accum = parse_dword(args.accum)
maxlen = int(args.len, 0)
data = get_input()
if not 0 < maxlen <= len(data):
maxlen = len(data)
out('rewinded {0}/{1} ({2:.2f}%)'.format(maxlen, len(data),
maxlen * 100.0 / len(data) if len(data) else 100))
for solution in rewind(accum, data[-maxlen:]):
out('')
print_num(solution)
def calc_callback():
# initialize tables
init_tables(get_poly(), False)
# calculate checksum
accum = parse_dword(args.accum)
data = get_input()
out('data len: {0}'.format(len(data)))
out('')
print_num(calc(data, accum))
def main(argv=None):
''' Runs the program and handles command line options '''
parser = get_parser()
# Parse arguments and run the function
global args
args = parser.parse_args(argv)
args.func()
if __name__ == '__main__':
main() # pragma: no cover
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment