パスワードを紛失して開けなくなったZIPファイルを30年越しにクラックした方法とは？

CloudflareでCTOを務めるジョン・グラハム＝カミング氏が、30年前のZIPファイルをクラックして解読に成功し、その方法についてブログに記しました。
John Graham-Cumming's blog: Cracking an old ZIP file to help open source the ANC's "Operation Vula" secret crypto code
https://blog.jgc.org/2024/09/cracking-old-zip-file-to-help-open.html

南アフリカで反アパルトヘイト活動をしていたティム・ジェンキン氏は、かつてアフリカ民族会議(ANC)の暗号化通信システムを構築しました。その通信システムのソースコードはパスワード付きのZIP形式で保存されていたものの、ジェンキン氏はパスワードを忘れてしまったとのこと。
ジェンキン氏は「パスワードは決して忘れないだろうと思っていましたが、数年後にデコードしようとしたときには思い出せませんでした」「暗号化通信システムのソースコードが復号できればオープンソースにしたいです。コードの解読を何回か試したものの、今のところ成功していません」と述べ、CloudflareのCTOであるカミング氏に解読を依頼しました。
問題のファイルは「ALLBAS.ZIP」「CODMAY93.ZIP」という2つ。両者ともにPKZIPの初期バージョンで作成されていました。幸い、PKZIPの初期バージョンに使用されている暗号化方式のZipCryptは「既知平文攻撃」が有効であることが知られています。
既知平文攻撃は暗号化されたZIPファイルの中身のうち、少しでも「暗号化前のデータ」が判明していれば暗号化後のデータと比較することでZIPファイル全体を保護しているパスワードが割り出せるというもの。既知平文攻撃を行うため、カミング氏はZIPファイル内のデータのうちどの部分に既知のデータが保存されているかを予測することにしました。
ZIPファイルの中身はこんな感じ。含まれている「.BAS」形式のファイルのうちいくつかはジェンキン氏が暗号化されていない状態で保有していたため、カミング氏はそのデータを使用して既知平文攻撃を試みたものの、ZIPファイルの中身とデータが異なり解読は失敗しました。

続いてカミング氏は圧縮されていない「Store」状態のデータに着目しました。ZIPファイルや実行ファイルなど、すでに圧縮されていたりバイナリファイルで圧縮する価値がなかったりするファイルがStore状態でZIPファイルに保存されており、こうしたデータは圧縮がかかっていないためデータの内容と位置を予測する際には扱いやすいとのこと。

幸い、問題の暗号化されたZIPファイルである「ALLBAS.ZIP」に含まれている「OLDCOD.ZIP」というZIPファイルをジェンキン氏が別の場所で保存しており、OLDCOD.ZIPの最初のファイルの名前が「COMKEY.BAS」であることが判明。カミング氏は下図のZIPのヘッダー構造を元にファイル名の場所で「COMKEY.BAS」と一致するであろう箇所を予測し、既知平文攻撃のオープンソース実装であるbkcrackを使用して解読を試みました。

解読開始から約23分でALLBAS.ZIPファイルのキーが生成され、復号に成功。もう一つの暗号化されていたZIPファイルの「CODMAY93.ZIP」も同じキーで復号できたとのこと。カミング氏は「同様のことをする必要がある場合は、平文について時間をかけて考える価値がある」と述べました。
なお、今回のZIPファイルに保存されていた1990年頃にANCで使用されていた暗号化通信システムについてはGitHubのTim Jenkin氏のリポジトリで公開されています。