1918년 11월의 훼손된 ADFGVX 메시지 스물두 통

01 목록은 무엇인가

1918년 프랑스군에 배속된 미국 암호 분석가 James Rives Childs는 동부 전선에서 가로챈 독일 ADFGVX 통신의 사본을 보관했다. 2017년 George Lasry, Ingo Niebel, Nils Kopal, Arno Wacker는 전치에 대한 언덕 오르기 공격으로 이 코퍼스를 해독하여, 1918년 9월부터 12월까지 열네 개의 3일 단위 키로 암호화된 암호문 618개를 복원했다. 이어서 Lasry는 그 키들 어느 것으로도 복호화되지 않는 메시지 목록을 Klaus Schmeh에게 건넸고, Schmeh는 이를 키와 함께 “Unsolved ADFGVX messages from World War I”로 발표했으며, 나중에 자신의 Top 50에 no. 46으로 올렸다.

그 페이지에 있는 Lasry 자신의 메모가 문제가 무엇인지 말해 준다. 키들은 “most certainly all the keys used during the period”이므로 “the challenge is to understand how the cryptograms were mutilated”라는 것이다. ADFGVX는 길이에 대해 가차 없다. 열 전치는 글자 흐름을 키 길이에 따라 나누므로, 글자 하나가 빠지거나 더해지면 그 뒤의 모든 열 경계가 움직여 메시지의 나머지가 잡음이 된다. 훼손이 두 군데 있는 메시지는 키를 알고 있어도 더 이상 그 키로 복호화할 수 없다.

2017년 2월부터 9월 사이에 게시물 아래의 댓글 스레드가 일의 대부분을 해냈다. Norbert Biermann, Armin, Thomas, Max Baertl, 그리고 Lasry 자신이 메시지를 하나하나 복호화했다. Schmeh는 이를 정리하는 글을 예고했지만 끝내 쓰지 않았기에, 그 복호문들은 흩어진 댓글로만 존재했고, 인쇄물이나 온라인 어디에서도 결과를 정리한 표는 찾을 수 없었다. 이 보고서가 가장 먼저 하는 일은 그 표를 공개하는 것이다.

02 기계가 읽을 수 있게 만든 키

Lasry의 목록은 각 키를 전치 순열과 36자 치환 정사각형으로 제시하며, 칸은 A D F G V X의 행 순서로 배열된다. 열네 개 정사각형 가운데 세 개에는 끝내 복원되지 않은 칸을 나타내는 하이픈 연속이 있는데, PDF의 텍스트 층이 이 연속을 엔 대시와 엠 대시로 뭉개 버려 정사각형이 34자나 35자만 남았다. 각 대시를 36자가 되는 길이의 하이픈 연속으로 되돌리면 세 개 모두 복구된다. 열네 개 모두 다음 파일에 있다: keys.json.

키 숫자는 두 가지로 해석할 수 있다. 하나는 perm[i] 가 i번째로 출력되는 열이라는 해석이고, 다른 하나는 i번째 열이 출력되는 위치라는 해석이다. 둘 다 왕복 변환에서 자기 일관적이므로, 암호화-복호화 시험으로는 구별할 수 없다. 실제 메시지를 복호화해 보면 구별된다. 두 번째 해석이 맞다.

목록에 없는 키

2017년 5월 3일 Lasry는 스레드에서, 두 부분으로 된 메시지, 즉 11월 13일의 FFVXV 암호문과 그것을 잇는 AFAFF 단편이 열네 기간 어디에도 없는 키로 함께 복호화되었다고 보고했다. 전치 단어는 CMBLAKOHIDENFJGP, 길이 16이다. 그는 합친 평문 173자를 제시하면서, 자신의 프로그램이 길이 16의 키를 복원하는 데 암호문 글자 356개 전부가 필요했다고 적었다. 치환 정사각형은 발표되지 않았다. 여기서는 두 암호문의 전치되지 않은 이중자를 그의 평문(Norbert의 수정 반영)과 정렬하여 이를 재구성했다. 36칸 중 24칸이며, 숫자와 글자 M, Q, Y는 메시지가 한 번도 쓰지 않으므로 복원되지 않았다. 이것이 다음 파일의 열다섯 번째 항목이다: keys.json 그리고 저장소의 노트에서는 이것이 암호화한 메시지의 머리글을 따서 CHI 키라고 부른다.

03 2017년의 결과를 한 표로

스레드의 댓글 70개를 모두 살펴보았다. 페이지 번호는 Schmeh가 인쇄한 대로의 Childs 사본 페이지이며, 두 메시지는 목록에 페이지 번호가 없다. 글자 수는 수신된 암호문의 것이고, 인쇄된 전사에 표시된 빈칸은 따로 셌다. 각 복호화는 처음 그것을 게시한 사람의 공으로 돌렸다.

아홉 통은 복호화되었고, 세 통은 부분적으로 복호화되었으며, 열 통은 어디에서도 복호문이 발견되지 않았다. 사본 페이지 하나, 인쇄본상 187(SELLV…, “Stellv. Gen. Kom. 9 AK Breslau”)은 카셀 팀이 이미 해독한 메시지로, 목록에 들어갈 것이 아니었다. Lasry가 스레드에서 그렇게 말했다. 두 CHI 메시지는 발표된 키로는 복호화할 수 없다고 목록에 올랐는데, 이는 사실이다. 이것들은 Lasry가 발표되지 않은 키를 복원한 뒤에 복호화되었다.

04 Norbert의 방법, 다시 구현하다

Norbert는 자신의 방법을 한 문장으로 설명했다. 서로 다른 두 위치에서 최대 다섯 글자를 넣거나 빼고, 전수 탐색을 하고, n-그램 가치 함수로 결과의 순위를 매긴다는 것이다. blocks.py 는 바로 그 일을 한다. 열다섯 개의 키 각각에 대해, 그리고 사본의 다섯 글자 묶음 경계에서 한 글자에서 다섯 글자까지의 블록을 삽입하거나 삭제하는 최대 두 번의 블록 편집 선택 각각에 대해, 복호화를 한 뒤 그 결과를 Gutenberg 독일어 텍스트 360만 글자로 만든 독일어 4-그램 모델로 채점한다 (lm_de.py). 숫자나 복원되지 않은 칸을 포함한 창은 하한 점수를 받고, X 구분자를 가로지르는 창은 쓰레기 문자열보다는 덜, 본문보다는 더 많은 비용을 치른다. 이 모델에서 독일어 산문은 창당 약 −3.3 nats, 무작위 글자는 약 −7을 얻는다.

평문에 대한 아무런 힌트도 주지 않았는데, 탐색은 105, 109, 146, 171페이지, 176페이지의 “missing 10 letters” 메시지, 그리고 두 CHI 메시지를 다시 도출한다. 146페이지에서 Norbert가 10번째 묶음 앞에 삽입했던 다섯 글자 블록은 다음과 같이 나온다: (45, 5). 176페이지 메시지에서는 다섯 글자 블록 두 개가 다음과 같이 나온다: (10, 5), (130, 5). 100페이지는 두 글자 삽입 한 번으로 같은 탐색에 풀린다. 탐색은 또한 페이지 번호가 없는 VGADA 메시지의 11월 22–24일 부분 해독도 찾아낸다. 인쇄된 전사가 빈칸을 표시한 곳에서는, gaps.py 가 빈칸을 제 묶음으로 되돌리고 남은 한 글자 손실을 담금질 기법으로 처리한다. 132페이지에서는 아무 유도 없이 Norbert의 텍스트에 도달한다.

다시 도출한 페이지들의 점수(실행 로그 기준)를, 미해결 메시지들이 얻은 최고 점수와 비교하면:

해독된 페이지들은 블록 편집이 완전히 맞지 않은 곳에서도 한눈에 독일어임을 알아볼 수 있으며, 남은 훼손은 두 번째 처리에서 고쳐지는 한 글자 손실들이다. 105와 109의 줄이 다른 것들보다 낮은 점수를 받는 것은 두 블록 탐색이 그 훼손을 근사할 뿐이기 때문이다. 그럼에도 두 텍스트 모두 원시 출력에서 읽을 수 있으며, 둘 다 Norbert의 2017년 복호문과 일치한다.

05 미해결 메시지 열 통, 검사하다

블록 편집 두 번, 키 열다섯 개

열 통 모두를 최대 두 번의 블록 편집으로 열다섯 개 키 전부에 대해 돌렸다. 각각의 최고 결과는 다음에서 가져왔다: blocks_out.txt:

−6.7을 넘는 것은 하나도 없다. 같은 실행에서 해독된 메시지들은 −4.4에서 −6.0 사이로 나오고, 무작위 글자는 약 −7.3이다. 따라서 열 통 가운데 어느 것도 열다섯 개 키 중 하나에 블록 훼손이 두 군데 이하인 경우가 아니며, 이는 정확히 2017년의 독자들이 도달하여 멈춘 경계다. 숫자가 많은 출력은 대개 틀린 키의 징후다. 이곳의 실제 통신은 대부분 글자이며, 틀린 정사각형은 이중자를 숫자 칸들에 흩뿌린다.

153페이지의 두 메시지에 대한 CHI 키

2017년 9월 Norbert는 153페이지의 두 메시지가 같은 시기의 것이므로 CHI 키에 속할 수도 있다고, 시험해 보지 않은 채 제안했다. 홀짝 보정을 곁들인 직접 복호화와 블록 탐색 모두 두 메시지에 대해 잡음만 반환한다. 원인은 목록에 없는 또 다른 키이거나, 블록 두 개보다 심한 손실이다.

키 없는 공격, 그리고 그것이 실패하는 이유

미해결 메시지 일부가 코퍼스에 없는 키로 암호화되었다면, 그 키는 암호문만으로 복원해야 할 것이다. keyless.py 가 시도하는 방법은 이렇다. 올바른 역전치는 단일 문자 치환의 이중자를 짝지어 주므로, 후보 길이마다 역전치가 만들어 내는 글자 쌍의 일치 지수를 목표로 열 순서를 담금질한 다음, 독일어 모델로 36기호 치환을 푼다. 미해결 메시지에 돌리기 전에, 심어 둔 대조 실험에 먼저 돌렸다. 같은 설계의 길이 19 키로 암호화한 독일어 224글자다.

실제 길이는 두드러지지 않는다. 19에서의 정점은 21, 22, 23에 밀리며, 치환 단계는 어떤 길이에서도 수렴하지 않는다. 대조 실험은 복원되지 않는다. 바로 이 목적으로 만든 Lasry 자신의 프로그램도 길이 16의 키를 복원하는 데 356글자가 필요했다. 미해결 메시지 열 통의 길이는 84에서 240글자다. 따라서 이 길이에서 키 없는 복원은 손이 닿지 않는다. 예외가 하나 있는데, 알려지지 않은 키를 공유하는 미해결 메시지가 둘 이상이라면, 두 CHI 메시지처럼 함께 풀 수 있다. 암호문에는 그것이 어느 것인지 표시가 없으며, 가장 자연스러운 후보인 153페이지의 두 메시지는 함께 시도해도 아무것도 나오지 않는다.

06 현황, 그리고 무엇이 그것을 바꿀 수 있는가

아홉 통은 복호화되었고, 세 통은 부분적으로, 열 통은 미해결이다. 열 통은 2026년 9월에 검사했으며, 블록 편집 최대 두 번으로 알려진 모든 키에서 실패한다. 세 가지가 이를 바꿀 수 있다.

그중 하나가 나타나기 전까지 쓸모 있는 산출물은 위의 표, 손상된 정사각형 세 개를 복구하고 CHI 정사각형을 재구성한 기계 판독용 키 열다섯 개, 그리고 평문을 주지 않아도 2017년의 복호문을 재현하는 디코더다.

07 파일