독일 경찰의 이중 상자 무선 전보, 1942년

요약. 1942년 독일 질서경찰은 무선 통신을 육군의 이중 상자 체계로 암호화했다. 5×5 상자 두 개를 쓰며, 각 글자 쌍을 같은 상자들로 두 번 암호화한다. Weierud는 감청문 여섯 건을 공개했다. 1942년 6월 16일 Mogilev에서 보낸 메시지에는 평문이 있다. Hanyok이 Eavesdropping on Hell에 실은 Bletchley 해독문으로, Bobruisk–Mogilev 도로에서 제51경찰대대원 16명이 전사했고, Borki 마을이 파괴되고 주민이 “liquidated”되었다는 내용이다. 1942년 2월 27일의 메시지 다섯 건에는 평문이 없다. 판별 그룹을 보면 다섯 건 모두, 즉 일곱 부분 970글자가 하나의 일일 키로 암호화되어 있다. 여기서 시도한 모든 암호문 단독 공격이 이들에 대해 실패한다. 단일 암호화는 완전히 배제되며, 이중 암호화에 대해서는 담금질 기법, 단계적 채점, 템퍼링, 완화법, EM이 키를 아는 970글자 합성 텍스트에서도 모두 실패하므로, 실제 텍스트에서의 실패는 평문에 대해 아무것도 말해 주지 않는다. 원인은 측정되었다. 진짜 키는 폭이 스왑 8–10번에 불과한 분지 안에 있고, 두 번째 통과 때문에 그 바깥에서는 탐색이 오를 언덕이 없다. 알려진 평문 솔버는 평문–암호문 쌍 약 80개로 상자를 복원한다. 쌍을 얻을 수 있는 뻔한 출처인 6월 메시지의 Bletchley 텍스트는 시도한 어떤 철자, 배열, 길이로도 암호문과 정렬되지 않는다. 따라서 암호화된 단어는 해독문의 단어와 같지 않았다. 키는 복원되지 않았다. 필요한 것은 한 키에 대한 알려진 쌍 약 80개다. 즉 2월 27일 통신에 대한 Bletchley의 해독문(TNA HW 16/17, 온라인에 없음)이나, 6월 메시지의 정확한 독일어 문구다.

01 메시지

Weierud의 논문 German Police Doppelkastenschlüssel Messages는 메시지 여섯 건을 전사하고, NARA, RG 457, Historic Cryptographic Collection, Box 1386(NR. 4417, “German WWII Police and SS Traffic”)과 Box 202(NR. 976, “Study of German Police Traffic”)의 텔레프린터 사본과 W/T Red Form을 수록한다. 여기서는 각 메시지를 Beaumanor 일련번호(BMR A115, D33 등)로 부른다. 각 부분의 첫 다섯 글자 그룹은 판별자로, 키의 이름을 나타내며 텍스트의 일부가 아니다. 아래 글자 수는 판별자를 제외한 것이다.

제51감청소의 W/T Red Form, 6월 16일: 경찰, SQF에서 DQH로, 3742 kHz, 머리말 SQF NR 14 2325 228 ALQ, 그리고 첫 암호 그룹 ARTTN FMXBW OIYSU OGILL — 1942년 6월 16일 메시지에 대한 제51감청소의 Red Form: SQF(Mogilev)에서 DQH(베를린)로, 3742 kHz, 전문 머리말 *NR 14 2325 228 ALQ*, 이어서 판별자 ARTTN과 본문. 이미지: NARA, RG 457, HCC, Box 202, F. Weierud, CryptoCellar (2020) 수록본.

일련번호	날짜	경로	글자 수	판별자
A115	1942년 6월 16일	SQF Mogilev (HSSPF Russland Mitte) → ALQ, DQH 베를린 경유	223	ARTTN
D33	1942년 2월 27일	SRS1 Rovno → DQH 베를린	74	KFWOJ
D34	1942년 2월 27일	SQF Mogilev → DSO, Kommandostab RFSS	160 + 86	DNOSX / DRANR
E72	1942년 2월 27일	SRS3 Proskurov → SRS1, SRS2 Brest	178 + 144	SBWYY / LENRA
D67	1942년 2월 27일	SRS3 Proskurov → SRS1, SRS2	170 + 158	OWQWJ / WNSXO
C43	1943년 2월 28일 자	SRS 키이우 → SRS1	138	SRXOS

C43의 두 번째 부분은 간섭으로 소실되었다(“2TL SWAMPED QRM”). E72 2부의 두 그룹은 일부 판독이 어렵다. Weierud는 사본에서 O와 Q를 구별하기 어렵다고 경고한다. D67에서 2행의 두 번째 그룹은 통신수 자신의 확인 줄(“CTN 2/6 ZAVGO”)에 따라 ZAVGO로 읽는다. 사용한 전사는 다음에 있다: msgs.txt.

02 A115와 Bletchley 해독문

A115는 Mogilev에서 보낸 Nr. 14로, 호출부호 SQF는 중부 러시아 친위대 및 경찰 고위 지도자(Höherer SS- und Polizeiführer Russland Mitte) 본부의 무선국이다. 머리말에 따르면 1942년 6월 16일 2325시에 접수되었고, Beaumanor에서 3742 kHz로 수신되었다. 제51, 제43감청소가 모두 이를 받아 적었다. Hanyok의 Eavesdropping on Hell(NSA, 2005)은 이 메시지 하나를 감청부터 해독까지 추적하며, Bletchley의 해독문을 그날 독일 경찰 해독문의 21번 항목으로 수록한다:

타자로 친 해독문: 21. DQH de SQF, SQF Nr 14 2325 228. An Rf SS und Chef Orpo. An Strasse Bobruisk-Mogilew, Partisanenkampf: 16 Mann von Pol. Batl. 51 gefallen. Das Dorf Borki, in dem Waffen und Munition gefunden wurden, wurde dem Erdboden gleichgemacht. Die Einwohnerschaft liquidiert. Von Hoeheren SS und Pol.fuehrer Russland Mitte. — A115의 Bletchley 해독문, 21번 항목. 이미지: NARA, RG 457, HCC, Box 1386, R. J. Hanyok, Eavesdropping on Hell (NSA, 2005) 수록본.

An Rf SS und Chef Orpo. An Strasse BOBRUISK–MOGILEW, Partisanenkampf: 16 Mann von Pol. Batl. 51 gefallen. Das Dorf BORKI, in dem Waffen und Munition gefunden wurden, wurde dem Erdboden gleichgemacht. Die Einwohnerschaft liquidiert. Von Höheren SS und Pol.führer Russland Mitte.

친위대 전국 지도자 겸 질서경찰 총수에게: Bobruisk–Mogilev 도로에서 파르티잔과 교전 중 제51경찰대대원 16명 전사. 무기와 탄약이 발견된 Borki 마을은 완전히 파괴되었고, 주민은 청산되었다. 중부 러시아 친위대 및 경찰 고위 지도자로부터. Hanyok은 오늘날 벨라루스에 Borki라는 마을이 여럿 있다며 이곳의 위치를 특정하지 않지만, 이곳은 잘 알려져 있다. Mogilev 주 Kirovsk 지구의 Borki로, 1942년 6월 15일 주변 정착촌들(Zakrinichye, Krasny Pakhar, Dzerzhinsky, Proletary, Dolgoe Pole, Khvatovka)과 함께 파괴되었다. 이 작전은 Mogilev–Bobruisk 도로에서 파르티잔 공격이 있은 뒤 Dirlewanger 친위대 특수대대가 제8특무대(Einsatzkommando 8) 및 경찰 부대와 함께 수행했다. Dirlewanger 자신의 보고서는 사망자를 2,027명으로 집계하며, 현재 그 자리에는 기념비가 서 있다. Dirlewanger 부대에 관한 Zhukov의 역사서는 해독문과 같은 제51경찰대대 전사자 16명을 인용하므로, 6월 16일 메시지는 Borki 학살에 대한 친위대 및 경찰 고위 지도자의 보고다. (독자 Ilya의 식별, 2026년 9월: Zhukov, Mogilev 주 집행위원회, partizany.by.) 이 해독문 때문에 Schmeh의 2021년 제2차 세계대전 암호 목록은 이 메시지군을 “partially solved”로 표시한다.

홀수 글자 수

이 메시지는 두 감청문과 독일어 머리말 모두에서 228글자다. 판별자를 빼면 223글자가 남는데, 이 암호는 쌍 단위로 작동하므로 암호화된 텍스트의 길이는 모두 짝수다. 따라서 독일 측 서기가 글자를 하나 더하거나 빠뜨렸거나, 전송 중에 한 글자가 소실되었다. 그 위치는 측정할 수 있다. 이중 상자 암호는 쌍에 대해 결정적이므로, 배열의 같은 위치에 반복된 평문 쌍은 반복된 암호 쌍을 낳으며, 쌍을 올바른 시작점에서 셀 때만 반복이 드러난다. 끝에서부터 세면 A115에는 19종의 반복 이중자가 25개 있다. 처음부터 세면 8개로, 우연 수준이다. 따라서 남는 글자는 처음 9개 남짓 안에 있고, 나머지 텍스트는 정상적으로 쌍을 이룬다.

03 2월 27일의 단일 키

Weierud는 판별자를 그룹의 마지막 세 글자(순서 무관)로 읽고, 일일 키마다 판별자 네 개가 발행되었다는 Bletchley의 메모를 인용한다. 그렇게 보고 한 그룹에서 O/Q 혼동을 허용하면, 2월 27일의 일곱 부분은 정확히 네 개를 사용한다:

판별자	부분
WOJ	D33 (KFWOJ); D67 1부 (OWQWJ, OWOWJ로 읽음)
OSX	D34 1부 (DNOSX); D67 2부 (WNSXO)
ANR	D34 2부 (DRANR); E72 2부 (LENRA)
WYY	E72 1부 (SBWYY)

한 메시지의 두 부분이 서로 다른 판별자를 달고 있고, Mogilev와 Proskurov의 통신이 판별자를 공유한다. 따라서 이 넷은 하나의 키를 가리키는 네 이름이며, 일곱 부분 970글자를 모두 함께 공격할 수 있다. C43의 XOS도 OSX이므로, 날짜가 1년 잘못 기재되었거나 키가 하루 넘게 쓰였음을 시사한다. Weierud는 이미 이 공유 지시자를 알아챘다. C43은 통합 텍스트에서 제외했다.

04 체계

교범 두 권이 남아 있으며 여기서 둘 다 참조했다. 1940년 12월 2일 자 OKH 초안 Schlüsselanleitung zum Doppelkastenschlüssel과 1941년 12월 OKW 발행본이다. 둘은 일치한다. 5×5 상자가 두 개 있다. 평문은 17글자짜리 이중 행으로 쓰고, 위아래로 놓인 글자들이 쌍이 된다. 이중 행을 채우기에 부족한 나머지는 반으로 나눈다. 각 쌍은 같은 상자들로 두 번 암호화된다. 쌍의 두 글자가 같은 행에 있으면 각 암호 글자는 오른쪽에서 취한다. 철자 규칙은 CH → Q, ß → SZ, 하이픈은 STRIQ로 쓴다. 참조 구현 dk.py은 두 교범의 예제를 글자 하나하나까지 그대로 암호화한다(1941년 교범은 p. 6에서 올바르게 적은 tvlhu를 p. 5에서는 tylhu로 인쇄했다).

NSA의 Cryptologic Quarterly가 설명하는 육군의 “NI” 야전 암호는 행이 21글자이고 같은 행 쌍에 왼쪽 이웃을 쓴다는 점 외에는 같은 방식이다. 그 예제들(EU → VR → QZ, en → FL → NC, ea → HK → TT)도 정확히 재현된다. 경찰이 어느 변형을 썼는지는 문서로 남아 있지 않으므로, 여기서의 모든 공격은 두 변형 모두에서 실행했다. 1942년 2월이 애초에 이중 상자 시기라는 것은 Hanyok에 근거한다. 경찰은 1941년 9월부터 11월 초 사이에 이중 전치에서 이중 Playfair로 바꾸었고, Bletchley는 새 체계가 해독하기 더 쉽다고 보았다.

교차 행 항등식

중요한 것은 이중 통과다. 첫 번째 통과 후 쌍의 첫 글자는 상자 B에서 취해졌지만, 두 번째 통과는 이를 상자 A에서 찾는다. 따라서 각 글자는 두 상자 모두에서의 위치로 쓰인다. 각 글자를 네 좌표, 즉 A에서의 행과 열, B에서의 행과 열로 쓰자. 교차 행의 경우 암호 쌍 (c1, c2)를 복호하면 중간 쌍

v1 = A[ B-row of c1 ][ A-col of c2 ]      v2 = B[ A-row of c2 ][ B-col of c1 ]

과 평문 쌍

p1 = A[ B-row of v1 ][ A-col of v2 ]      p2 = B[ A-row of v2 ][ B-col of v1 ]

이 나온다. 모든 단계가 A 좌표와 B 좌표를 섞는다. 두 통과 사이에는 각 글자의 상자 A 칸에서 상자 B 칸으로 가는 사상, 즉 25칸의 무작위 순열이 있다. 06절은 공격을 막는 것이 이 순열이지 키의 크기가 아님을 보여 준다.

05 시도한 것

대조 실험 없는 실패한 탐색은 아무것도 증명하지 못하므로, 이중 암호화에 대한 각 공격은 먼저 합성 텍스트에서 실행했다. 독일어 텍스트 970글자를 무작위 상자로 두 번 암호화한 것으로, mksyn.py 및 dk.py로 만들었고 실제와 같은 길이의 부분들로 나누었다. 점수는 25글자 독일어 표(build_lm.py)에 따른 글자당 4-gram 로그 확률이다. 독일어 텍스트는 약 −3.9, 무작위 글자는 약 −6이다.

가설 또는 방법	결과	판정
단일 암호화, 일곱 부분 전체 통합, 행 길이 1–30, 쌍은 쓴 순서와 역순	최고 글자당 −5.91, 독일어는 약 −3.9	배제
단일 암호화, 부분별 및 판별자 그룹별, 행 길이 1, 17, 21, 두 쌍 순서 모두	−5.0에서 −5.6, 짧은 텍스트가 잡음에 과적합하는 수준	배제
이중 암호화, 4-gram 기반 담금질 기법(`dksolve2.cs`)	합성 970글자 텍스트에서 잡음 수준(−6.0)을 벗어나지 못함. 진짜 키에서 스왑 네 번 떨어진 곳에서 시작해도 되돌아오지 못함	대조 실험에서 실패
단계적 unigram → bigram → 4-gram 채점; 최급 상승 반복 국소 탐색; 병렬 템퍼링; 재라벨링 이동; 행/열 곱 점수; GPU상의 Sinkhorn 완화(`relax.py`); 평문을 변수로 둔 hard EM(`emsolve.cs`)	합성 텍스트에서 모두 실패. 무작위 시작점은 unigram 점수 −1.39에서 −1.42에 멈추며, 진짜 키의 점수는 −1.221	대조 실험에서 실패
같은 방법에 진짜 A칸 → B칸 순열을 주고 글자 라벨링만 탐색	여전히 −1.42에서 멈춤	대조 실험에서 실패
알려진 쌍 20–37개로 SAT 풀이(z3)	어떤 경우에도 15분 안에 답 없음	결론 없음
알려진 평문, 중간 일치 점수(`kpsolve.cs`): 평문 쌍을 한 번 암호화하고 암호 쌍을 한 번 복호한 뒤, 두 중간값의 행별·열별 일치도를 채점	무작위 시작점에서 합성 쌍 111개로 약 1분 만에 상자 복원(111개 중 111개 일치); 80쌍이면 거의 복원(80개 중 68개); 60쌍 이하이거나 쌍의 10%가 틀리면 실패	대조 실험에서 작동
Bletchley의 A115 텍스트를 키 없이 암호문에 정렬(`align115c.py`, `align115h.py`): 반복된 암호 쌍은 반복된 평문 쌍과 맞아야 함. 철자, X 구분자, 문자로 풀어 쓴 숫자, 수신처와 서명 위치, Borki / Mohilew / Bobruiisk 변형, 222 또는 224글자, 행 길이 1–24에 걸친 정확한 역추적	일관된 정렬 없음. 같은 탐색이 합성 철자는 35초 만에 복원	정렬 없음

단일 암호화 결과는 그 가설을 배제한다. 통합 텍스트는 970글자로 단일 통과 이중 상자에 필요한 양을 훨씬 넘으며, 찾은 최선의 키는 독일어에 전혀 가깝지 않다. 이중 암호화 결과는 평문에 대해 아무것도 배제하지 않는다. 답을 아는 텍스트에서도 같은 방법들이 실패하기 때문이다. 이 결과는 공격 자체만을 측정한다.

정렬 결과는 유익하다. A115의 반복된 암호 쌍은 실재하며(02절), 정렬기는 자신이 시도하는 방식 중 하나로 철자를 쓴 합성 텍스트를 주면 이를 찾아낸다. A115에서는 철자, 구분자, 숫자, 배열, 길이를 어떻게 조합해도 반복된 암호 쌍이 모두 반복된 평문 쌍에 떨어지지 않는다. 암호화된 단어가 약어, 어순, 더 긴 수신처 같은 추가 내용 때문에 Bletchley의 텍스트와 다르거나, 경찰의 배열이 두 교범 모두와 다르다.

06 두 번째 통과가 국소 탐색을 무력화하는 이유

이는 공개된 기록과 일치한다. Lasry, Norbert 등의 언덕 오르기 솔버는 100–150글자의 단일 통과 이중 상자 텍스트를 해독하며, 그 단순화된 단일 통과 친척인 육군의 Truppenschlüssel은 남아 있는 메시지로부터 암호문만으로 해독되었다. 같은 상자를 두 번 통과하는 방식을 해독한 공개된 공격은 없다. 여기서의 합성 실행이 어려움이 어디에 있는지 보여 준다.

진짜 키는 최적점이지만 좁은 최적점이다. unigram 점수에서 진짜 키는 최선의 키다(−1.221). 그 분지의 폭은 스왑 8–10번 정도에 불과하다. 4-gram 점수에서는 더 좁다. 진짜 키에서 스왑 네 번 떨어진 곳에서 시작한 담금질 기법도 되돌아오지 못한다.
분지 바깥에는 오를 언덕이 없다. 무작위 시작점은 −1.39에서 −1.42에 멈춘다. 거기서 도달하는 국소 최적점은 진짜 상자와 행이나 열 구조를 전혀 공유하지 않는다. 행과 열 묶음의 정밀도를 키와 비교해 측정하면 약 6분의 1로, 우연 수준이다.
크기가 문제가 아니다. 솔버에 상자 A와 상자 B 사이의 진짜 칸 순열을 주어 글자 라벨링만 찾게 해도 도움이 되지 않는다. 여전히 −1.42에서 멈춘다. 어려움은 무작위 칸 순열을 통한 켤레 변환(04절)에 있다. 가능성 높은 메커니즘은 이렇다. 부분적으로 맞는 키는 틀린 중간 글자를 내놓고, 두 번째 통과가 이를 무관한 칸으로 보내므로, 부분적인 정확성이 점수로 이어지지 않는다.

알려진 평문은 이를 바꾼다. 채점에서 두 번째 통과를 제거하기 때문이다. kpsolve.cs 는 알려진 평문 쌍 각각을 앞으로 한 번 암호화하고 그 암호 쌍을 뒤로 한 번 복호한 뒤, 두 중간값이 행별·열별로 일치하도록 요구한다. 각 절반이 단일 통과이므로 국소 탐색에 기울기가 생긴다. 합성 대조 실험에서는 약 80쌍이면 충분하다.

07 무엇이 있으면 끝낼 수 있는가

미해독 종결. 암호문 단독 공격은 실패했다. 두 경로가 이를 다시 열 수 있다.

무엇	효과가 있을 이유
한 키에 대한 평문–암호문 쌍 약 80개	`kpsolve.exe` 가 상자를 복원하고, 그 키로 2월 27일의 일곱 부분을 모두 읽을 수 있다. 출처는 그날 통신에 대한 Bletchley 자신의 해독문이 될 것이며, 이는 TNA HW 16/17(독일 경찰 해독문 원문, HW 16/18은 1942년 5–6월)에 있을 것이나 온라인에 없다. 또는 메시지들에 공통된 길고 정형화된 머리말이나 수신처도 출처가 될 수 있다. A115의 경우 쌍을 얻으려면 실제로 암호화된 정확한 독일어 문구가 필요하다.
A115 정렬	이는 경찰의 배열(17글자 또는 21글자 행, 왼쪽 또는 오른쪽 이웃)도 확정하고, 경찰의 상자가 무작위였는지 키워드로 만들어졌는지도 보여 줄 것이다. 키워드로 만든 상자라면 2월 27일에 대한 키워드 탐색이 열린다.
같은 상자를 두 번 통과하는 방식에 대한 새로운 암호문 단독 아이디어	여기서 시도한 어떤 것도 그것을 제공하지 못하며, 공개된 것도 마찬가지다.

08 출처

Frode Weierud, German Police Doppelkastenschlüssel Messages, Crypto Cellar Research, 2020년 8월 5일, NARA, RG 457, HCC, Box 1386 (NR. 4417) 및 Box 202 (NR. 976)에서. 텔레프린터 사본, 제51·제43감청소의 Red Form, 머리말에 관한 Bletchley 메모 포함.
Klaus Schmeh, “Can you solve these double-box messages from WW2?”, Cipherbrain, 2020년 8월 30일.
OKH, Schlüsselanleitung zum Doppelkastenschlüssel (초안, 1940년 12월 2일), 및 OKW, Vorläufige Schlüsselanleitung zum Doppelkastenschlüssel (1941년 12월), 둘 다 cryptocellar.org의 스캔본.
Robert J. Hanyok, Eavesdropping on Hell: Historical Guide to Western Communications Intelligence and the Holocaust, 1939–1945 (NSA Center for Cryptologic History, 2005): A115 감청문, Red Form, 해독문, 그리고 1941년 가을 경찰의 이중 Playfair 전환.
“WWII German Army Field Cipher”, NSA Cryptologic Quarterly, Wayback Machine 경유: 육군 NI 변형과 그 예제.
Modern Cryptanalysis of the Truppenschlüssel (2021년 10월 22일): 육군의 단순화된 단일 통과 친척, 그리고 두 교범의 출처.

모든 것은 프로젝트 저장소의 targets/orpo1942/ 프로젝트 저장소에 있는 것: msgs.txt (판별자를 제거한 암호문), dk.py (두 교범으로 검증한 참조 구현), build_lm.py (25글자 독일어 n-gram 표), mksyn.py (합성 테스트 세트), dksolve2.cs (단계적 채점을 쓴 담금질 기법, 반복 국소 탐색, 템퍼링), kpsolve.cs (알려진 평문 솔버), emsolve.cs 및 relax.py (실패한 공격, 기록으로 보존), align115c.py 및 align115h.py (A115 정렬기), 원본 PDF, 그리고 NOTES.md. 여기에 이 시도의 전체 기록이 있다.