WeChall - The Nap

Challenge

You wake up at 4 a.m. and sadly realise, that it is another day to work. You make your breakfast, and read your favourite newspaper "Der Angriff". The date is 5th June 1944. The news predicts there will be no invasion for several days. Even your boss is away for vacation. You arrive zur Wehrmacht at 5 a.m., and the night shift collegaues greets you. He gives you the daily codes and leaves immediately the communication station. He is really a lazy guy and havent established the enigma settings yet. You really think its gonna be a lazy day - alone. You drink some beer and wait for incoming messages. As nothing happens, you happen to fall asleep. You dream very well but suddenly the radio begins to ring. As you wake up from your deep dream you knock your beer and it soaks the daily codebook. You say some round oath, pick up the radio and record the encrypted message:

U17 DE U101 0600 = 4 = VRS SDX = JSPK NIPN OZTR CYEW QICZ PDNO KRBU AXKE VTIS HIDE WZOY PGZN ERCY ADWI FTOB FYSL SKTD MLJX XVSZ JXCW BKNV IJMG RFOV YWYZ CKOZ ZPIV JLEN ZUUX NEAP QGOV

After the conversation you realise that the keys for today were partially destroyed. You imagine how angry your superior will be after returning, if you don't decrypt the message immediately. The wasted codebook is here: codebook;

Your job is to decipher the encrypted message, and the solution is the last original german word in lowercase concatenated with the total number of possible configurations in bits - if the wiring of the rotors is secret.

For example AES128 has 128 bits. So if the last original german word is "WeChall" and the total number of possible configurations in bits is 128 the solution is: wechall128 Not a single beer-drop has been wasted during the making of this challenge :)

The Nap

题面给出的报文：

U17 DE U101 0600 = 4 = VRS SDX =
JSPK NIPN OZTR CYEW QICZ PDNO KRBU AXKE VTIS
HIDE WZOY PGZN ERCY ADWI FTOB FYSL SKTD MLJX
XVSZ JXCW BKNV IJMG RFOV YWYZ CKOZ ZPIV JLEN
ZUUX NEAP QGOV

答案格式：

<last original german word lowercase><total config bits>

Codebook

codebook.jpg 是 1217×672 JPEG。水渍从右下角向上蔓延，Tag 越小的行越难读。完整转写如下，[?] 表示水渍遮挡或无法可靠读取。

#	Tag	UKW	Walzenlage	Ringstellung	Steckerverbindungen	Kenngruppen
1	30	B	II IV III	23 08 12	AU EG HL IN MV OY QS RT XZ	IYP NMA BAO HVJ
2	29	C	III I II	11 09 08	AX BP DG EW HM IR JT KL NV UY	MBM ECB BBR SHA
3	28	B	I II V	20 08 23	AL BK CX DF EJ GP MQ OV RS YZ	MID ZYF XFD HAF
4	27	B	I V IV	03 09 02	BK [?] EP GS JX LQ NV OZ PW	SWF GQD DMM MXE
5	26	C	III II IV	06 08 04	[?] FM HP IW JX KY LS OZ	NHQ YSH FBD CXV
6	25	C	III IV V	04 21 11	[?] FS GL IN MX PW RT UY	TBX PKD VMU CQY
7	24	C	I V II	[?] 15 [?]	[?] CH DX FM KQ OY PT RV SZ	KTM NOG FAI LOM
8	23	C	V III IV	[?]	DJ FZ GL HV KS NU PY QW	ZIL YSL OND UNR
9	22	C	IV III [?]	[?]	[?] DM EX GV HQ KW RT SU	BYP AFI YND GIK
10	21	B	III IV [?]	[?]	[?] GN IQ KM LU PT QV SZ	QYP XII GRA QMZ
11	20	B	III IV [?]	[?]	[?] DW EH IL KO PQ RU XZ	JYD FKC GFO KFX
12	19	C	I II [?]	[?]	[?] HO KZ MU NT PX QS WY	NMB IAF DIT IEK
13	18	C	II V [?]	[?]	[?] OV EZ HP JW KU MY NQ OR	VUS CZE KQU WAX
14	17	B	V III [?]	[?]	AD BY EG FX HK IU JW LN QR SZ	AOM QHJ JHN AMZ
15	16	C	II II [?]	[?]	AT BQ CM DL ER FH GZ JY KO SX	FAU NYZ MUK EFT
16	15	B	I [?] [?]	[?]	AR BD CN EW FI HT KP LY OU VX	BTP YDY YKS WPK
17	14	C	[?] [?] [?]	[?]	AG CH EL IY JQ KR MN PU TZ VX	MPS TGB GMP ZAY
18	13	C	[?] [?] [?]	18 10 12	AK CT ES FN GW IU JZ LM OX PQ	BCA IME CEV QMB
19	12	B	[?] [?] [?]	07 08 05	AI BP CR DJ EQ FU KT LN OV WX	LXQ RZW EIR HWP
20	11	C	[?] [?] [?]	04 14 09	AF BQ GZ IR KN LV MU OW SY TX	XZI AKU CKQ GSX
21	10	B	[?] [?] III	15 06 06	AK BT EH FQ GU IL JZ MP NW OS	FTB WTD CLG DSU
22	09	[?]	[?] III I	12 10 03	BT EZ FO GX HR IY JP LV QU SW	AWV GCQ KYC RND
23	08	[?]	[?] V IV	14 13 04	AX BY CM DG FS JQ KO LP NW TZ	YJP EMT OCO YDL
24	07	[?]	[?] II III	03 11 20	BR DS EG FV HJ IQ KX LO NF YZ	SWW RIS KCF YJN
25	06	[?]	[?] V III	18 10 10	AT BN CF DR GI HY KM OX QV SU	ZLY KDP VDA YXN
26	05	[?]	[?] I IV	22 24 11	AN CF DZ EJ HX KT LY MQ OP SV	WEC HAL LRU LZX

Tag=05 对应 6 月 5 日。

Field	Value	Status
UKW	[?]	水渍覆盖，需要枚举 B/C
Walzenlage	[?] I IV	第一个 rotor 未知；理论上可枚举 II/III/V，也可以直接枚举全部 60 种排列
Ringstellung	22 24 11	可见
Steckerverbindungen	AN CF DZ EJ HX KT LY MQ OP SV	可见
Kenngruppen	WEC HAL LRU LZX	可见

Solution

把每个 AAA 到 ZZZ 当成 message key，枚举全部 rotor order 和 reflector。

搜索空间：

Parameter	Values	Count
Rotor order	5P3 = 5×4×3	60
Reflector	B/C	2
Message key	AAA-ZZZ	26³ = 17,576
Ringstellung	22 24 11	fixed
Plugboard	AN CF DZ EJ HX KT LY MQ OP SV	fixed
Total	60×2×26³	2,109,120

直接用 German trigram score 排名，比 IC 更可靠。随机文本偶尔有较高 IC，但不会同时命中 DER/DIE/DAS/UND/SCH/UNG 等多个德语片段。

最佳结果：

score=14  IC=0.0605  rotors=II I IV  ref=B  key=ENI
VRSSDXDERHIMMELISTOFTNEBELHAFTUNDZEITWEISEISTMITREGENZUREQNENXDERWINDWEHTSTARKER...

完整解密参数：

Parameter	Value	Source
UKW / Reflector	B	brute force
Walzenlage	II I IV	brute force
Ringstellung	22 24 11	codebook visible
Plugboard	AN CF DZ EJ HX KT LY MQ OP SV	codebook visible
Message key	ENI	brute force
Grundstellung	not needed	skipped by direct message-key brute force

原始 plaintext：

VRSSDXDERHIMMELISTOFTNEBELHAFTUNDZEITWEISEISTMITREGENZUREQNENXDERWINDWEHTSTARKERAUSNORDWESTXDIENAQTWIRDKLARMITVOLLMONDXX

解析规则：

Symbol	Meaning
leading VRSSDX	transmitted indicator text appearing at the start of the decrypted body; not a German word
X	sentence/group separator
XX	message terminator
Q	CH, as in REQNEN -> RECHNEN, NAQT -> NACHT

可读德语：

DER HIMMEL IST OFT NEBELHAFT UND ZEITWEISE IST MIT REGEN ZU RECHNEN.
DER WIND WEHT STARKER AUS NORDWEST.
DIE NACHT WIRD KLAR MIT VOLLMOND.

最后一个 original German word 是 VOLLMOND，小写为 vollmond。

Complete solve script

#!/usr/bin/env python3
"""
WeChall - The Nap

Reproduce the complete solution:
- Brute-force Enigma rotor order / reflector / message key
- Score German plaintext candidates with overlapping trigram matching
- Parse raw plaintext into readable German and extract the last word
- Compute the bit value accepted by the challenge: floor(log2(3e114)) = 380

Run:
    cd /home/kita/ctf/workspace
    .venv/bin/python3 challenges/wechall/the-nap/solve_new.py
"""
import itertools
import math
import re
from collections import Counter
from enigma.machine import EnigmaMachine

ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ALL_ROTORS = ['I', 'II', 'III', 'IV', 'V']

CIPHER = (
    'JSPKNIPNOZTRCYEWQICZPDNOKRBUAXKEVTISHIDEWZOYPGZNERCYADWIFTOB'
    'FYSLSKTDMLJXXVSZJXCWBKNVIJMGRFOVYWYZCKOZZPIVJLENZUUXNEAPQGOV'
)

RING_SETTINGS = '22 24 11'
PLUGBOARD = 'AN CF DZ EJ HX KT LY MQ OP SV'

# Common German trigrams/fragments for language scoring.
_GERMAN_MARKERS = [
    'DER', 'DIE', 'DAS', 'UND', 'IST', 'EIN', 'ICH', 'NIC', 'MIT', 'AUF',
    'SCH', 'UNG', 'END', 'TER', 'STE', 'ERE', 'AND', 'DEN', 'VON', 'ZUR',
    'ABE', 'GEN', 'TEN', 'DES', 'DEM', 'WIR', 'SIE', 'SEI', 'WAR', 'WUR',
    'BEI', 'KEI', 'HAB', 'KAN', 'WOR', 'MEN', 'HTS', 'LIC', 'VER', 'TUN',
]
# Precompile regex patterns for overlapping trigram matching.
_MARKER_PATTERNS = [re.compile(f'(?={m})') for m in _GERMAN_MARKERS]

# Compact German word list for plaintext segmentation.
_GERMAN_WORDS = {
    'DER', 'DIE', 'DAS', 'DEN', 'DEM', 'DES', 'EIN', 'EINE', 'EINEN', 'EINER',
    'ICH', 'WIR', 'SIE', 'ER', 'ES', 'IHN', 'IHM', 'IHR', 'SEIN', 'SEINE',
    'MIT', 'VON', 'ZU', 'AUS', 'IN', 'AN', 'AUF', 'BEI', 'NACH', 'VOR',
    'UEBER', 'UNTER', 'DURCH', 'FUER', 'GEGEN', 'OHNE', 'UM', 'SEIT', 'BIS',
    'UND', 'ODER', 'ABER', 'DENN', 'WEIL', 'WENN', 'DASS', 'OB', 'SO',
    'DOCH', 'NUR', 'AUCH', 'NOCH', 'SCHON', 'SEHR', 'IMMER', 'NICHT', 'KEIN',
    'IST', 'SIND', 'WAR', 'WIRD', 'WURDE', 'HAT', 'HABEN', 'KANN', 'MUSS',
    'SOLL', 'WILL', 'KOMMT', 'GEHT', 'STEHT', 'MACHT', 'GIBT', 'SAGT',
    'HIMMEL', 'NEBELHAFT', 'REGEN', 'RECHNEN', 'WIND', 'WEHT', 'STARK',
    'STARKER', 'NORD', 'WEST', 'NORDWEST', 'NACHT', 'KLAR', 'VOLL', 'MOND',
    'VOLLMOND', 'ZEIT', 'WEISE', 'ZEITWEISE', 'OFT',
    'TAG', 'JAHR', 'LAND', 'STADT', 'HAUS', 'WEG', 'MANN', 'FRAU', 'KIND',
    'GUT', 'GROSS', 'KLEIN', 'ALT', 'NEU', 'HOCH', 'TIEF', 'WEIT', 'NAH',
    'HIER', 'DORT', 'DA', 'WO', 'WIE', 'WAS', 'WER',
}


def ic(text: str) -> float:
    """Index of Coincidence.  German prose ~0.076; random ~0.038."""
    n = len(text)
    if n < 2:
        return 0.0
    counts = Counter(text)
    return sum(v * (v - 1) for v in counts.values()) / (n * (n - 1))


def german_score(text: str) -> int:
    """
    Overlapping trigram count against common German fragments.

    Uses regex lookahead (?=MARKER) so that e.g. 'ERERE' counts 'ERE' twice
    (positions 0 and 2), unlike str.count() which only finds non-overlapping
    occurrences.
    """
    return sum(len(pat.findall(text)) for pat in _MARKER_PATTERNS)


def _segment_german(compound: str, words: set[str]) -> list[str]:
    """Greedy longest-match left-to-right segmentation of a compound string."""
    result = []
    i = 0
    n = len(compound)
    while i < n:
        best_len = 0
        for length in range(min(12, n - i), 0, -1):
            if compound[i:i + length] in words:
                best_len = length
                break
        if best_len > 0:
            result.append(compound[i:i + best_len])
            i += best_len
        else:
            result.append(compound[i])
            i += 1
    return result


def _extract_last_word(compound: str, words: set[str]) -> str:
    """Extract the last German word by scanning from the right for the
    longest dictionary match."""
    n = len(compound)
    best_word = ''
    for start in range(n - 1, -1, -1):
        for length in range(min(12, n - start), 0, -1):
            candidate = compound[start:start + length]
            if candidate in words:
                if length > len(best_word):
                    best_word = candidate
                break
        if best_word:
            # Extend left for compound words (e.g., VOLLMOND vs MOND)
            left = start - 1
            while left >= 0:
                found_longer = False
                for length in range(min(12, n - left), len(best_word), -1):
                    candidate = compound[left:left + length]
                    if candidate in words and len(candidate) > len(best_word):
                        best_word = candidate
                        found_longer = True
                        break
                if not found_longer:
                    break
                left -= 1
            return best_word
    return ''


def decode_plaintext(raw: str) -> tuple[str, str]:
    """
    Parse raw Enigma plaintext into readable German and extract the last word.

    - First 6 chars (VRSSDX) are the transmitted indicator, not German.
    - 'X' separates sentences; 'XX' terminates the message.
    - 'Q' represents 'CH' (no CH key on Enigma keyboard).
    """
    body = raw[6:]
    segments = [s.replace('Q', 'CH') for s in body.split('X') if s]

    last_word = ''
    readable_lines = []
    for seg in segments:
        words = _segment_german(seg, _GERMAN_WORDS)
        if words:
            readable_lines.append(' '.join(words).upper() + '.')
            last_word = words[-1]

    return '\n'.join(readable_lines), last_word.upper()


def accepted_bit_value() -> int:
    """Published Enigma secret-wiring keyspace: ~3e114 ~ 2^380."""
    return math.floor(math.log2(3 * 10**114))


def _build_machines() -> dict[tuple[str, str], EnigmaMachine]:
    """Pre-build all 120 (60 × 2) machine objects.  Reuse via set_display()."""
    machines = {}
    for rotors_tuple in itertools.permutations(ALL_ROTORS, 3):
        rotors = ' '.join(rotors_tuple)
        for reflector in ('B', 'C'):
            machines[(rotors, reflector)] = EnigmaMachine.from_key_sheet(
                rotors=rotors,
                reflector=reflector,
                ring_settings=RING_SETTINGS,
                plugboard_settings=PLUGBOARD,
            )
    return machines


def brute_force_message_key() -> list[tuple[int, float, str, str, str, str]]:
    """Search: 60 rotor orders × 2 reflectors × 26³ keys = 2,109,120."""
    machines = _build_machines()
    keys = [''.join(p) for p in itertools.product(ALPHABET, repeat=3)]
    hits = []

    for (rotors, reflector), machine in machines.items():
        for key in keys:
            machine.set_display(key)
            plain = machine.process_text(CIPHER)
            score = german_score(plain)
            if score > 3:
                hits.append((score, ic(plain), rotors, reflector, key, plain))

    hits.sort(key=lambda row: (-row[0], -row[1]))
    return hits


def main() -> None:
    hits = brute_force_message_key()

    print('Top German-scored candidates:')
    print('score   IC      rotors      ref  key  plaintext-prefix')
    print('-' * 86)
    for score, ici, rotors, reflector, key, plain in hits[:20]:
        print(f'{score:>5}  {ici:.4f}  {rotors:<10}  {reflector:<3}  {key:<3}  {plain[:80]}')

    score, ici, rotors, reflector, key, plain = hits[0]
    readable, last_word = decode_plaintext(plain)
    bits = accepted_bit_value()

    print('\nWinning settings:')
    print(f'rotors      = {rotors}')
    print(f'reflector   = {reflector}')
    print(f'rings       = {RING_SETTINGS}')
    print(f'plugboard   = {PLUGBOARD}')
    print(f'message key = {key}')
    print(f'score       = {score}')
    print(f'IC          = {ici:.4f}')
    print(f'last word   = {last_word}')

    print('\nRaw plaintext:')
    print(plain)

    print('\nReadable German:')
    print(readable)

    print('\nBit value:')
    print(f'floor(log2(3 * 10^114)) = {bits}')

    print('\nSolution:')
    print(f'{last_word.lower()}{bits}')


if __name__ == '__main__':
    main()

Top German-scored candidates:
score   IC      rotors      ref  key  plaintext-prefix
--------------------------------------------------------------------------------------
   14  0.0605  II I IV     B    ENI  VRSSDXDERHIMMELISTOFTNEBELHAFTUNDZEITWEISEISTMITREGENZUREQNENXDERWINDWEHTSTARKER
    7  0.0389  III I II    B    UDG  YBTYENICPMICTBAKRDUESFJRDZEYQGCVQCVCDPENDPWBEINOGLHIIKCCYVGHCSOUMEYYTWSRBPYHFTVI
    6  0.0466  III II V    B    AQU  BEWEYFJXUDASKFTCXAAANZMNFLHAHANOGKFHAWBFBBEHWMHRPGEJPFXLMYZLAKFEQHMABEINQKDHVAND
    ...

Winning settings:
rotors      = II I IV
reflector   = B
rings       = 22 24 11
plugboard   = AN CF DZ EJ HX KT LY MQ OP SV
message key = ENI
score       = 14
IC          = 0.0605
last word   = VOLLMOND

Raw plaintext:
VRSSDXDERHIMMELISTOFTNEBELHAFTUNDZEITWEISEISTMITREGENZUREQNENXDERWINDWEHTSTARKERAUSNORDWESTXDIENAQTWIRDKLARMITVOLLMONDXX

Readable German:
DER HIMMEL IST OFT NEBELHAFT UND ZEITWEISE IST MIT REGEN ZU RECHNEN.
DER WIND WEHT STARKER AUS NORDWEST.
DIE NACHT WIRD KLAR MIT VOLLMOND.

Bit value:
floor(log2(3 * 10^114)) = 380

Solution:
vollmond380

Bit count

Z 在论坛里贴的这段提示，逐字抄自一篇 NSA 论文：

The Enigma cipher machine consists of five variable components:
1. a plugboard which could contain from zero to thirteen dual-wired cables
2. three ordered (left to right) rotors which wired twenty-six input contact points to twenty-six output contact points positioned on alternate faces of a disc
3. twenty-six serrations around the periphery of the rotors which allowed the operator to specify an initial rotational position for the rotors
4. a moveable ring on each of the rotors which controlled the rotational behavior of the rotor immediately to the left by means of a notch
5. a reflector half-rotor (which did not in fact rotate) to fold inputs and outputs back onto the same face of contact points

Your goal is to calculate the total number of possible configurations for such an Enigma machine,
where you can make your own rotors, etc.

And finally a hint: If you cant solve this part by yourself, google is your best friend

来源：NSA 论文 The Cryptographic Mathematics of Enigma

• 作者：Dr. A. Ray Miller, Center for Cryptologic History, NSA
• 这篇论文首次算出了 Enigma 的完整理论 keyspace
• 论文给出的精确数字（三转子、单 notch、已知 reflector wiring，即 secret wiring 的前提）：

3,283,883,513,796,974,198,700,882,069,882,752,878,
379,955,261,095,623,685,444,055,315,226,006,433,615,
627,409,666,933,182,371,154,802,769,920,000,000,000

≈ 3 × 10^114

获取：

• NSA 官方 PDF（需从 NSA History 页面导航，直链 403）： https://media.defense.gov/2021/Jul/13/2002761536/-1/-1/0/CRYPTOMATHENIGMA_MILLER.PDF
• Internet Archive 镜像（可直接下载）： https://web.archive.org/web/20090117030740/http://www.nsa.gov/about/_files/cryptologic_heritage/publications/wwii/engima_cryptographic_mathematics.pdf
• Cornell 大学密码学课件也引用了同一篇论文

题目要求的是 "total number of possible configurations in bits" = floor(log2(3×10^114)) = 380。

vollmond380