e909c7c133
Nothing here changes what a tool computes; it changes where tools look. - tools/re-capture: 33 censuses globbed /work/sylph_extract, a path that has existed nowhere since /work became a clone, so they matched nothing and printed empty results. They now resolve the disc through a new disc.py from $SYLPHEED_DISC and exit loudly without it (the #44 fix, generalised). Nine scripts that imported siblings from the retired Reborn checkout or an old session scratchpad now import from their own directory. unitgroup.py only needs the variable when --pak is not given. - sylpheed-xex: the loader only ever uses the XEX2 retail key. The dead devkit key and a doc comment claiming a devkit fallback that does not exist are gone; Project Sylpheed is a retail XEX2, so no XEX1 key either. - sylpheed-viewer: real_font_rasterizes looked for /tmp/sylph_extract and so always skipped. It reads $SYLPHEED_DISC now, and passes against the disc. - Comments and docs that named xenia-rs, the Reborn repository or /work/*.pe as places to look now name sylpheed.db, Canary's ppc_context.h and the flat .pe; docs/re/README.md no longer says the native Canary build does not run. Historical records keep their original paths: findings that were measured against /work/xenia-rs/sylpheed.db still say so. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
538 lines
22 KiB
Python
538 lines
22 KiB
Python
#!/usr/bin/env python3
|
|
r"""Census -- and preimage attack -- for IDXD field keys that carry no name.
|
|
|
|
Pure static work: reads the extracted disc, runs no emulator.
|
|
|
|
python3 tools/re-capture/idxd_unnamed_keys.py census > docs/re/data/idxd-unnamed-field-keys.txt
|
|
python3 tools/re-capture/idxd_unnamed_keys.py crack # corpus + brute-force attack
|
|
python3 tools/re-capture/idxd_unnamed_keys.py idtbl # dump the 42 hash-shaped keys in context
|
|
|
|
An IDXD field entry is `(key, name_off, value_off)`. When `name_off` is
|
|
0xFFFFFFFF the field has no name in the pool, and the reader must know what the
|
|
`key` means from somewhere else. This tool answers "how many such keys are
|
|
there, what do they look like, and can the names be recovered from the hash?"
|
|
|
|
The headline measurement (see docs/re/structures/idxd-unnamed-keys.md):
|
|
|
|
2 757 039 field entries in 7 750 IDXD objects
|
|
1 271 462 named, 1 485 577 unnamed
|
|
7 094 distinct keys that are never named ANYWHERE on the disc
|
|
7 052 of them are < 0x10000 -- author-assigned ordinals / element ids
|
|
42 of them are >= 0x01000000 -- genuine tag_hash values
|
|
|
|
`SYLPHEED_DISC` (required) points at the extracted disc.
|
|
"""
|
|
import argparse, collections, glob, os, re, struct, sys, zlib
|
|
from disc import disc_root
|
|
|
|
DISC = disc_root()
|
|
|
|
# --------------------------------------------------------------------------- hashes
|
|
|
|
TAG_MODULUS = 0x00FFFFDF # 2^24 - 33, prime
|
|
TAG_MAGIC = 0x2101 # floor(2^56/M)+1, the guest's divide magic
|
|
|
|
|
|
def tag_hash(s):
|
|
"""IDXD record key / field tag -- `sub_82447DF0`.
|
|
|
|
Transcribed in docs/re/structures/idxd-tag-hash.md and implemented three
|
|
times in this tree (here, tools/re-capture/unitgroup.py, and
|
|
sylpheed_formats::hash::tag_hash). Case-SENSITIVE, bytes sign-extended.
|
|
"""
|
|
a = b = 0
|
|
for byte in s.encode('latin-1', 'replace'):
|
|
c = (byte - 256) if byte > 127 else byte # extsb
|
|
a = ((a << 8) & 0xFFFFFFFF)
|
|
a = (a + c) & 0xFFFFFFFF
|
|
b = (b + c) & 0xFFFFFFFF
|
|
hi = ((a * TAG_MAGIC) >> 32) & 0xFFFFFFFF # mulhwu
|
|
q = ((hi + (((a - hi) & 0xFFFFFFFF) >> 1)) & 0xFFFFFFFF) >> 23
|
|
a = (a - q * TAG_MODULUS) & 0xFFFFFFFF
|
|
return (((b << 24) & 0xFF000000) | (a & 0x00FFFFFF)) & 0xFFFFFFFF
|
|
|
|
|
|
NAME_MODULUS, NAME_RECIP = 0x00FFF9D7, 0x80031493
|
|
|
|
|
|
def _rotl(v, n):
|
|
return ((v << n) | (v >> (32 - n))) & 0xFFFFFFFF
|
|
|
|
|
|
def name_hash(s):
|
|
"""IPFB TOC path hash -- lowercased, a different modulus. `sub_82455C78`."""
|
|
bs = bytearray(s.encode('latin-1', 'replace'))
|
|
for i, x in enumerate(bs):
|
|
if 65 <= x <= 90:
|
|
bs[i] = x + 0x20
|
|
a = b = 0
|
|
for byte in bs:
|
|
c = ((byte - 256) if byte > 127 else byte) & 0xFFFFFFFF
|
|
a = ((_rotl(a, 8) & 0xFFFFFF00) + c) & 0xFFFFFFFF
|
|
b = (b + c) & 0xFFFFFFFF
|
|
q = _rotl(((a * NAME_RECIP) >> 32) & 0xFFFFFFFF, 9) & 0x1FF
|
|
a = (a - (q * NAME_MODULUS)) & 0xFFFFFFFF
|
|
return (((b << 24) & 0xFF000000) | (a & 0x00FFFFFF)) & 0xFFFFFFFF
|
|
|
|
|
|
# --------------------------------------------------------------------------- pak / IDXD
|
|
|
|
def pak_entries(pak):
|
|
"""yield (toc_key, payload) for every entry of an IPFB pak + its .pNN segments."""
|
|
idx = open(pak, 'rb').read()
|
|
data = b''.join(open(p, 'rb').read()
|
|
for p in sorted(glob.glob(pak[:-4] + '.p[0-9][0-9]')))
|
|
for i in range(struct.unpack_from('>I', idx, 4)[0]):
|
|
k, off, csize = struct.unpack_from('>III', idx, 16 + i * 12)
|
|
s = data[off:off + csize]
|
|
if s[:2] == b'Z1':
|
|
try:
|
|
s = zlib.decompress(s[10:])
|
|
except zlib.error:
|
|
continue
|
|
yield k, s
|
|
|
|
|
|
def parse_idxd(b):
|
|
"""-> [(record_key, record_name, [(tag, name|None, value, field_index)])]"""
|
|
u = lambda o: struct.unpack_from('>I', b, o)[0]
|
|
nrec = u(0x04)
|
|
npool_off = 0x08 + nrec * 16
|
|
npool = u(npool_off)
|
|
pool = npool_off + 4
|
|
strsize_off = pool + npool * 12
|
|
STR = strsize_off + 4
|
|
strsize = u(strsize_off)
|
|
if STR + strsize != len(b):
|
|
raise ValueError('string-pool trailer mismatch')
|
|
|
|
def s(o):
|
|
if o >= strsize:
|
|
raise ValueError('string offset out of pool')
|
|
return b[STR + o:b.index(b'\x00', STR + o)].decode('latin-1')
|
|
|
|
out = []
|
|
for i in range(nrec):
|
|
key, nm, lo, hi = (u(0x08 + i * 16 + j * 4) for j in range(4))
|
|
fields = []
|
|
for j in range(lo, hi):
|
|
o = pool + j * 12
|
|
tag, noff, voff = u(o), u(o + 4), u(o + 8)
|
|
fields.append((tag, s(noff) if noff != 0xFFFFFFFF else None, s(voff), j - lo))
|
|
out.append((key, s(nm), fields))
|
|
return out
|
|
|
|
|
|
def all_paks():
|
|
return sorted(glob.glob(DISC + '/dat/*.pak') + glob.glob(DISC + '/hidden/*.pak'))
|
|
|
|
|
|
def walk(counter=None):
|
|
"""yield (pak_basename, obj_toc_key, record_key, record_name, fields)."""
|
|
for pak in all_paks():
|
|
base = os.path.basename(pak)
|
|
for h, payload in pak_entries(pak):
|
|
if payload[:4] != b'IDXD':
|
|
continue
|
|
try:
|
|
recs = parse_idxd(payload)
|
|
except Exception as exc: # noqa: BLE001
|
|
print('PARSE FAIL %s %08x %s' % (base, h, exc), file=sys.stderr)
|
|
continue
|
|
if counter is not None:
|
|
counter['objects'] += 1
|
|
schema = recs[0][1] if recs else ''
|
|
for key, rname, fields in recs:
|
|
yield base, h, schema, key, rname, fields
|
|
|
|
|
|
# --------------------------------------------------------------------------- value profile
|
|
|
|
_FLOAT = re.compile(r'^-?(\d+\.\d*|\.\d+|\d+)([eE][-+]?\d+)?$')
|
|
_INT = re.compile(r'^-?\d+$')
|
|
_HEX = re.compile(r'^(0[xX])?[0-9a-fA-F]+$')
|
|
_FILE = re.compile(r'^[\w\\/. -]+\.[A-Za-z0-9]{2,4}$')
|
|
|
|
|
|
def classify(values):
|
|
"""A coarse type label for a bag of field values."""
|
|
if not values:
|
|
return 'empty'
|
|
kinds = set()
|
|
for v in values:
|
|
if v == '':
|
|
kinds.add('empty')
|
|
elif _INT.match(v):
|
|
kinds.add('int')
|
|
elif _FLOAT.match(v):
|
|
kinds.add('float')
|
|
elif _FILE.match(v):
|
|
kinds.add('file')
|
|
elif v in ('True', 'False', 'Yes', 'No', 'ON', 'OFF'):
|
|
kinds.add('bool')
|
|
elif _HEX.match(v) and len(v) >= 6:
|
|
kinds.add('hex')
|
|
else:
|
|
kinds.add('id')
|
|
order = ['file', 'id', 'hex', 'bool', 'float', 'int', 'empty']
|
|
return '+'.join(k for k in order if k in kinds)
|
|
|
|
|
|
# --------------------------------------------------------------------------- census
|
|
|
|
def census():
|
|
named = collections.defaultdict(collections.Counter)
|
|
unnamed = collections.Counter()
|
|
key_objs = collections.defaultdict(set)
|
|
key_recs = collections.defaultdict(collections.Counter)
|
|
key_idx = collections.defaultdict(lambda: [1 << 30, -1])
|
|
key_vals = collections.defaultdict(list)
|
|
key_nval = collections.Counter()
|
|
# per (object-schema, record-name) family, for the ordinal population
|
|
fam = collections.defaultdict(lambda: {'keys': set(), 'n': 0, 'vals': [], 'recs': 0})
|
|
tot = collections.Counter()
|
|
schema_of = {}
|
|
|
|
for base, h, schema, rkey, rname, fields in walk(tot):
|
|
tot['records'] += 1
|
|
# the object's schema hash is the key of its first record; use record name
|
|
fam_id = None
|
|
for tag, name, val, fidx in fields:
|
|
tot['fields'] += 1
|
|
if name is not None:
|
|
tot['named'] += 1
|
|
named[tag][name] += 1
|
|
else:
|
|
tot['unnamed'] += 1
|
|
unnamed[tag] += 1
|
|
key_objs[tag].add((base, h))
|
|
key_recs[tag][rname] += 1
|
|
lohi = key_idx[tag]
|
|
lohi[0] = min(lohi[0], fidx)
|
|
lohi[1] = max(lohi[1], fidx)
|
|
key_nval[tag] += 1
|
|
if len(key_vals[tag]) < 40:
|
|
key_vals[tag].append(val)
|
|
if fam_id is None:
|
|
fam_id = (base, schema)
|
|
f = fam[fam_id]
|
|
f['keys'].add(tag)
|
|
f['n'] += 1
|
|
if len(f['vals']) < 60:
|
|
f['vals'].append(val)
|
|
if fam_id is not None:
|
|
fam[fam_id]['recs'] += 1
|
|
|
|
return dict(named=named, unnamed=unnamed, key_objs=key_objs, key_recs=key_recs,
|
|
key_idx=key_idx, key_vals=key_vals, key_nval=key_nval, fam=fam, tot=tot)
|
|
|
|
|
|
def report(c, out=sys.stdout):
|
|
named, unnamed = c['named'], c['unnamed']
|
|
never = sorted(set(unnamed) - set(named))
|
|
hashy = [k for k in never if k >= 0x01000000]
|
|
ordinal = [k for k in never if k < 0x01000000]
|
|
both = sorted(set(unnamed) & set(named))
|
|
w = out.write
|
|
|
|
w('# IDXD field keys that carry no name\n')
|
|
w('#\n')
|
|
w('# Generated by tools/re-capture/idxd_unnamed_keys.py census\n')
|
|
w('# Disc: %s (all dat/*.pak + hidden/*.pak, .pNN segments joined, Z1 inflated)\n' % DISC)
|
|
w('# Companion write-up: docs/re/structures/idxd-unnamed-keys.md\n')
|
|
w('#\n')
|
|
w('# A field entry is (key, name_off, value_off). name_off == 0xFFFFFFFF means the\n')
|
|
w('# pool holds no name for it, so the reader must already know what `key` means.\n')
|
|
w('\n')
|
|
w('== TOTALS ==\n')
|
|
w('IDXD objects walked : %d\n' % c['tot']['objects'])
|
|
w('IDXD records walked : %d\n' % c['tot']['records'])
|
|
w('field entries : %d\n' % c['tot']['fields'])
|
|
w(' named (name_off != 0xFFFFFFFF) : %d\n' % c['tot']['named'])
|
|
w(' unnamed (name_off == 0xFFFFFFFF) : %d\n' % c['tot']['unnamed'])
|
|
w('distinct keys seen named somewhere : %d\n' % len(named))
|
|
w('distinct keys seen unnamed somewhere : %d\n' % len(unnamed))
|
|
w('distinct keys NEVER named anywhere on disc : %d\n' % len(never))
|
|
w(' of those, < 0x00010000 (ordinal-shaped) : %d\n' % len([k for k in never if k < 0x10000]))
|
|
w(' of those, in [0x10000, 0x1000000) : %d\n' % len([k for k in never if 0x10000 <= k < 0x1000000]))
|
|
w(' of those, >= 0x01000000 (hash-shaped) : %d\n' % len(hashy))
|
|
w('keys that are named in one place and unnamed in another: %d %s\n'
|
|
% (len(both), ['%08x' % k for k in both]))
|
|
w('unnamed FIELD ENTRIES whose key is hash-shaped : %d\n'
|
|
% sum(c['key_nval'][k] for k in hashy))
|
|
w('unnamed FIELD ENTRIES whose key is an ordinal : %d\n'
|
|
% sum(c['key_nval'][k] for k in ordinal))
|
|
w('unnamed FIELD ENTRIES with key 0x00000000 : %d (ordinal 0; the key is\n'
|
|
% sum(c['key_nval'][k] for k in both))
|
|
w('# "named" elsewhere only because tag_hash("") == 0, so it is counted apart)\n')
|
|
w('# The first of those two is the "504 hash-keyed fields disc-wide" already in\n')
|
|
w('# INDEX.md. It is 504 ENTRIES, not 504 distinct keys: %d keys x 6 language\n' % len(hashy))
|
|
w('# copies of the same object x 2 records (FILE and OFFSET) = %d.\n'
|
|
% sum(c['key_nval'][k] for k in hashy))
|
|
w('\n')
|
|
w('# Why the split at 0x01000000 is not arbitrary: a tag_hash puts the byte-sum\n')
|
|
w('# checksum in the top byte, so a hash lands below 0x01000000 only when the name\n')
|
|
w('# byte-sum is 0 mod 256 (1/256 of names) AND its low 24 bits are also tiny. Of\n')
|
|
zerotop = sorted(k for k in named if (k >> 24) == 0 and k != 0)
|
|
w('# the %d keys that DO carry a name, %d have a zero top byte, and the smallest of\n'
|
|
% (len(named), len(zerotop)))
|
|
w('# those is 0x%06x -- far above the ordinal band, which tops out at 0x%x.\n'
|
|
% (zerotop[0], max(ordinal)))
|
|
w('\n')
|
|
|
|
w('== PART 1: the %d HASH-SHAPED never-named keys ==\n' % len(hashy))
|
|
w('# key n objects record field value\n')
|
|
for k in hashy:
|
|
recs = ','.join(sorted(c['key_recs'][k]))
|
|
lo, hi = c['key_idx'][k]
|
|
vals = sorted(set(c['key_vals'][k]))
|
|
w('%08x %3d %2d %-13s %2d-%-2d %s\n'
|
|
% (k, c['key_nval'][k], len(c['key_objs'][k]), recs, lo, hi, '|'.join(vals)))
|
|
w('\n')
|
|
w('# All %d live in the six copies of <lang>\\script\\ID.tbl inside\n' % len(hashy))
|
|
w('# dat/GP_READY_ROOM.pak (eng jpn fra deu ita esp). Each copy has two records,\n')
|
|
w('# FILE and OFFSET, with the SAME 42 keys in the same order -- i.e. the object is\n')
|
|
w('# a column store: key -> (which .isb file, what offset inside it).\n')
|
|
w('\n')
|
|
|
|
w('== PART 2: the ordinal population, by (pak, object schema) ==\n')
|
|
w('# The schema is the name of the object\'s FIRST record -- the string whose\n')
|
|
w('# tag_hash is the object header word. `recs` counts records with >=1 unnamed field.\n')
|
|
w('# pak schema recs fields keys keymin-keymax valuetype sample\n')
|
|
rows = []
|
|
for (base, rname), f in c['fam'].items():
|
|
ks = f['keys']
|
|
rows.append((base, rname, f['recs'], f['n'], len(ks), min(ks), max(ks),
|
|
classify(f['vals']), f['vals'][0] if f['vals'] else ''))
|
|
for r in sorted(rows, key=lambda r: (-r[3], r[0], r[1])):
|
|
w('%-28s %-17s %5d %7d %5d %6x-%-6x %-10s %s\n'
|
|
% (r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7], r[8][:40]))
|
|
w('\n')
|
|
|
|
w('== PART 3: every never-named ordinal key ==\n')
|
|
w('# key occurrences distinct-records fieldidx-lo-hi valuetype sample-value\n')
|
|
for k in ordinal:
|
|
lo, hi = c['key_idx'][k]
|
|
w('%08x %8d %6d %4d-%-4d %-10s %s\n'
|
|
% (k, c['key_nval'][k], len(c['key_recs'][k]), lo, hi,
|
|
classify(c['key_vals'][k]), (c['key_vals'][k] or [''])[0][:40]))
|
|
w('\n')
|
|
w('== PART 4: the ID.tbl script-symbol call graph ==\n')
|
|
try:
|
|
idtbl(out)
|
|
except Exception as exc: # noqa: BLE001
|
|
w('# unavailable: %s\n' % exc)
|
|
|
|
|
|
# --------------------------------------------------------------------------- ID.tbl
|
|
|
|
READY_ROOM = DISC + '/dat/GP_READY_ROOM.pak'
|
|
LANGS = ('eng', 'jpn', 'fra', 'deu', 'ita', 'esp')
|
|
|
|
|
|
_RR_CACHE = {}
|
|
|
|
|
|
def readyroom_file(path):
|
|
"""Read one file out of GP_READY_ROOM.pak by its (lowercased) path."""
|
|
if not _RR_CACHE:
|
|
_RR_CACHE.update(dict(pak_entries(READY_ROOM)))
|
|
return _RR_CACHE.get(name_hash(path))
|
|
|
|
|
|
def idtbl(out=sys.stdout):
|
|
"""The 42 keys with their FILE/OFFSET columns, plus the .isb cross-check."""
|
|
payload = readyroom_file('eng\\script\\ID.tbl')
|
|
recs = {r[1]: r[2] for r in parse_idxd(payload)}
|
|
files = recs['FILE']
|
|
offs = recs['OFFSET']
|
|
out.write("# eng\\script\\ID.tbl -- key -> (defining .isb file, offset), plus every\n")
|
|
out.write('# .isb whose bytecode contains the key as a little-endian word (= a call site).\n')
|
|
out.write('# idx key defined-in offset referenced-from\n')
|
|
isb = {}
|
|
for name in sorted({v for _, _, v, _ in files}):
|
|
b = readyroom_file('eng\\script\\' + name)
|
|
if b:
|
|
isb[name] = {struct.unpack_from('<I', b, o)[0] for o in range(0, len(b) - 3)}
|
|
for i, (tag, _n, val, _f) in enumerate(files):
|
|
seen = sorted(f for f, s in isb.items() if tag in s)
|
|
out.write('%3d %08x %-24s %-6s %s\n'
|
|
% (i, tag, val, offs[i][2], ','.join(seen) or '-'))
|
|
|
|
|
|
# --------------------------------------------------------------------------- attacks
|
|
|
|
def _poly(s):
|
|
a = 0
|
|
for ch in s.encode('latin-1', 'replace'):
|
|
a = (a * 256 + ch) % TAG_MODULUS
|
|
return a
|
|
|
|
|
|
def corpus_attack(targets, words):
|
|
"""Straight dictionary attack. Returns {tag: [names]} and the corpus size."""
|
|
hits = collections.defaultdict(list)
|
|
n = 0
|
|
for w in words:
|
|
n += 1
|
|
h = tag_hash(w)
|
|
if h in targets:
|
|
hits[h].append(w)
|
|
return hits, n
|
|
|
|
|
|
def compose_attack(targets, tokens, suffixes=('',), seps=('', '_', '-')):
|
|
"""Two-token composition attack: name = t1 + sep + t2 + suffix.
|
|
|
|
Returns (hits, effective search space). The space is what matters: with a
|
|
32-bit tag, expected FALSE hits per target is space / 2**32.
|
|
"""
|
|
right = collections.defaultdict(list)
|
|
for t in tokens:
|
|
for sep in seps:
|
|
for suf in suffixes:
|
|
r = sep + t + suf
|
|
right[(len(r), _poly(r))].append(r)
|
|
lens = sorted({k[0] for k in right})
|
|
p256 = {l: pow(256, l, TAG_MODULUS) for l in lens}
|
|
hits = collections.defaultdict(list)
|
|
for left in tokens:
|
|
pl = _poly(left)
|
|
for l in lens:
|
|
for tag in targets:
|
|
want = ((tag & 0xFFFFFF) - pl * p256[l]) % TAG_MODULUS
|
|
for r in right.get((l, want), ()):
|
|
cand = left + r
|
|
if tag_hash(cand) == tag:
|
|
hits[tag].append(cand)
|
|
space = len(tokens) * sum(len(v) for v in right.values())
|
|
return hits, space
|
|
|
|
|
|
def brute_force(target, suffix='', maxlen=6, alphabet=None):
|
|
"""Meet-in-the-middle preimage search: all P over `alphabet` with
|
|
tag_hash(P + suffix) == target and len(P) <= maxlen.
|
|
|
|
Needs numpy. The honest limit is maxlen 6: the expected number of FALSE
|
|
preimages is |alphabet|**maxlen / 2**32, which is ~15 at 63**6 and ~58 000
|
|
at 63**8, so anything past 6 returns noise, not names.
|
|
"""
|
|
import numpy as np
|
|
if alphabet is None:
|
|
alphabet = ([chr(c) for c in range(48, 58)] + [chr(c) for c in range(65, 91)]
|
|
+ [chr(c) for c in range(97, 123)] + ['_'])
|
|
A = len(alphabet)
|
|
codes = np.array([ord(c) for c in alphabet], dtype=np.int64)
|
|
tabs = []
|
|
polys = np.zeros(1, dtype=np.int64)
|
|
sums = np.zeros(1, dtype=np.int64)
|
|
tabs.append((polys, sums))
|
|
for _ in range(maxlen // 2 + maxlen % 2):
|
|
polys = ((polys[:, None] * 256 + codes[None, :]) % TAG_MODULUS).ravel()
|
|
sums = (sums[:, None] + codes[None, :]).ravel()
|
|
tabs.append((polys, sums))
|
|
|
|
def decode(idx, k):
|
|
s = ''
|
|
for _ in range(k):
|
|
s = alphabet[idx % A] + s
|
|
idx //= A
|
|
return s
|
|
|
|
ps = _poly(suffix)
|
|
inv = pow(pow(256, len(suffix), TAG_MODULUS), -1, TAG_MODULUS)
|
|
need_sum = ((target >> 24) - sum(suffix.encode('latin-1'))) & 0xFF
|
|
out = []
|
|
for L in range(maxlen + 1):
|
|
v = L // 2
|
|
u = L - v
|
|
if u >= len(tabs) or v >= len(tabs):
|
|
continue
|
|
pu, su = tabs[u]
|
|
pv, sv = tabs[v]
|
|
order = np.argsort(pv, kind='stable')
|
|
pv_s = pv[order]
|
|
need = (((target & 0xFFFFFF) - ps) * inv) % TAG_MODULUS
|
|
want = (need - (pu * pow(256, v, TAG_MODULUS)) % TAG_MODULUS) % TAG_MODULUS
|
|
lo = np.searchsorted(pv_s, want, side='left')
|
|
hi = np.searchsorted(pv_s, want, side='right')
|
|
for i in np.nonzero(hi > lo)[0]:
|
|
for j in range(lo[i], hi[i]):
|
|
vi = order[j]
|
|
if ((su[i] + sv[vi]) & 0xFF) != need_sum:
|
|
continue
|
|
cand = decode(int(i), u) + decode(int(vi), v) + suffix
|
|
if tag_hash(cand) == target:
|
|
out.append(cand)
|
|
return out
|
|
|
|
|
|
# --------------------------------------------------------------------------- main
|
|
|
|
def main():
|
|
ap = argparse.ArgumentParser(description=__doc__,
|
|
formatter_class=argparse.RawDescriptionHelpFormatter)
|
|
ap.add_argument('mode', choices=('census', 'idtbl', 'crack', 'selftest'))
|
|
ap.add_argument('--maxlen', type=int, default=6)
|
|
ap.add_argument('--pe', default=os.environ.get('SYLPHEED_PE'),
|
|
help='flat VA dump of default.xex; its strings widen the corpus')
|
|
args = ap.parse_args()
|
|
|
|
if args.mode == 'census':
|
|
report(census())
|
|
elif args.mode == 'idtbl':
|
|
idtbl()
|
|
elif args.mode == 'selftest':
|
|
# tag_hash must reproduce the key of every NAMED field on the disc.
|
|
ok = bad = 0
|
|
for _b, _h, _sc, _rk, _rn, fields in walk():
|
|
for tag, name, _v, _i in fields:
|
|
if name is None:
|
|
continue
|
|
if tag_hash(name) == tag:
|
|
ok += 1
|
|
else:
|
|
bad += 1
|
|
if bad < 5:
|
|
print('MISMATCH %r %08x != %08x' % (name, tag, tag_hash(name)))
|
|
print('tag_hash reproduces %d / %d named field keys (%d wrong)' % (ok, ok + bad, bad))
|
|
else:
|
|
c = census()
|
|
targets = {k for k in set(c['unnamed']) - set(c['named']) if k >= 0x01000000}
|
|
print('targets: %d hash-shaped never-named keys' % len(targets))
|
|
words = set()
|
|
for b, h, _sc, _rk, rname, fields in walk():
|
|
words.add(rname)
|
|
for _t, name, val, _i in fields:
|
|
if name:
|
|
words.add(name)
|
|
words.add(val)
|
|
if args.pe and os.path.exists(args.pe):
|
|
blob = open(args.pe, 'rb').read()
|
|
words |= {m.decode('latin-1') for m in re.findall(rb'[ -~]{3,}', blob)}
|
|
hits, n = corpus_attack(targets, words)
|
|
print('disc-string corpus : %d strings, %d hits, E[false]=%.4f'
|
|
% (n, len(hits), n * len(targets) / 2 ** 32))
|
|
for t, v in hits.items():
|
|
print(' %08x %s' % (t, v[:6]))
|
|
toks = collections.Counter()
|
|
for w in words:
|
|
for part in re.split(r'[^A-Za-z0-9]+', w):
|
|
for p in re.findall(r'[A-Z]+(?![a-z])|[A-Z][a-z]+|[a-z]+', part):
|
|
if 2 <= len(p) <= 14:
|
|
toks[p] += 1
|
|
tokens = [t for t, _ in toks.most_common()]
|
|
hits, space = compose_attack(targets, tokens)
|
|
print('2-token composition: space=%d, %d hits, E[false]=%.3f'
|
|
% (space, len(hits), space * len(targets) / 2 ** 32))
|
|
for t, v in hits.items():
|
|
print(' %08x %s' % (t, v[:6]))
|
|
for t in sorted(targets)[:3]:
|
|
r = brute_force(t, '', args.maxlen)
|
|
print('brute force <=%d chars %08x: %d candidates %s'
|
|
% (args.maxlen, t, len(r), r[:6]))
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|