1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
|
"""
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'
_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',
]
_MARKER_PATTERNS = [re.compile(f'(?={m})') for m in _GERMAN_MARKERS]
_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:
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()
|