ジェイコブ・ジヴさんが開発したLempel-Ziv-Welch（LZW）アルゴリズムとは？
2023年3月26日、Lempel-Ziv-Welch（LZW）アルゴリズムの開発者の一人であるジェイコブ・ジヴ（Jacob Ziv）博士が逝去されたとのニュースがありました。博士の実績を振り返り今後に生かす知見をと今回記事にすることにしました。
早速ですが本題のLempel-Ziv-Welch（LZW）アルゴリズムは、効率的で信頼性が高い圧縮手法の一つであり皆さんも良くなじみがあります。
代表的なところではPNG、GIF、ZIPなどで利用されています。
✅PNG(Portable Network Graphics)
PNGがWeb上での画像の配信に利用できるのはLZWアルゴリズムを使用して画像データを圧縮しているからです。
✅GIF(Graphics Interchange Format)
GIFがWeb上でアニメーション機能を提供できるのも画像データをLZWアルゴリズムで圧縮しているからです。
✅ZIP(Zipped Format)
Lempel-Ziv-Welch（LZW）アルゴリズムは、符号化によってデータの圧縮を行う圧縮アルゴリズムの一種です。LZWアルゴリズムは、入力データの中にある重複部分を検出、それらを辞書として保存します。そして、その辞書の中で最長の文字列に対して、一意な符号を割り当て、その符号で置き換えることで、データを圧縮しています。
GIFでは「LZWを用いてGIFを生成する機能を持つすべて商用ソフトウェアにライセンス利用の支払いを求める」の事件(1994年)の方がピンとくるかもしれません。
ZIPはあとでも解説しますがLZWアルゴリズムとDEFLATEアルゴリズムを組み合わせ圧縮することで息の長い技術となっています。さらに博士はPDFやMP3などのフォーマット開発にも関わってます。博士の開発した技術使わないで企業活動する方が現代では困難かもしれません。
その中でセキュリティ的にはZIPに関して深掘りしたいと思います。
良い機会なのでZIP圧縮の仕組みを復習しましょう。
全体の流れはまずLZWアルゴリズムで圧縮を行い、その後、DEFLATEアルゴリズムでさらに圧縮を行うことで、高い圧縮率を実現しています。
これが以下解説を読み終えることろには辞書式の弱点をハフマン法で補完していると理解できているはずです。
Zip圧縮では、複数のファイルを一つのアーカイブファイルにまとめた後、LZWアルゴリズムを使用して、入力データの中にある重複部分を検出し、それらを辞書として保存します。そして、その辞書の中で最長の文字列に対して、一意な符号を割り当て、その符号で置き換えることで、データを圧縮します。
すももももももももものうちは辞書式でどのように圧縮されるのか？
まず、LZWアルゴリズムでは、データの中で繰り返し出現する部分を辞書として保持します。
次に、圧縮対象のデータを一定の単位（例えば、1文字）で区切ります。そして、データの先頭から順に、登録されている最長の辞書エントリにマッチするまでの文字列を読み込みます。
このように、データを先頭から順に読み込み、マッチする最長の辞書エントリを出力していくことで、圧縮されたデータを生成します。最終的には、元のデータよりも圧縮されたデータが短くしようと言うことです。
「すももももももももものうち」というフレーズをLZWアルゴリズムで圧縮する場合、辞書に「す」、「も」、「もも」、「ももも」、「の」、「う」、「ち」のエントリが登録され、数字は各エントリのインデックスを表した場合、最終的に「6 3 5 3 4 3 6 7」という圧縮されたデータが生成されます。このケースでは13字が８文字なので2/3くらいになった訳です。
ハフマン符号化の原理と辞書式の弱点をハフマン法がどう補完しているのか？
ハフマン符号化は、頻出する文字やパターンに対して短い符号を割り当て、それ以外の出現頻度が低い文字やパターンには長い符号を割り当てることで、圧縮率を高める方法です。ハフマン符号化によって得られた圧縮データは、ビットストリームとして保存されます。
辞書式だけの場合、256種類ならちょうど8ビットであらわせていたのですが、種類が増えると1記号あたりのビット数が長くなってしまうだけでなく、種類が2のべき乗個でなくなることでビット効率も落ちてしまいます。そこでハフマン符号化を組み合わせるとハフマン符号は記号の種類が2のべき乗個でなくても作れます。偶数個である必要さえありません。
実はZIPと互換性がある拡張子
iOSアプリケーションのipaファイルは、.zipとすると中身が解凍可能です。つまりipaはzipと互換性を持つ拡張子の一つです。
他にもAndroidアプリケーションのapk、Microsoft Officeシリーズのdocx, xlsx, pptx、Java Archiveファイルのjar、マニアックなところでは３Ｄプリンター向けの.3mfなども互換性があります。
ZIPの仕様とセキュリティ上の知識
ZIPファイル内のファイル名は例え暗号化していてもZIPの仕様では隠せません。
unzipコマンドでも-Zオプションで見ると解凍しなくとも中身は見えてしまいます。
zipinfoコマンドの-lオプションで見るとファイルサイズが分かります。
勘のいい人なら、説明資料やREADMEなどの共通で入れているファイルのオリジナルファイルが手に入り先の２つのコマンドで確認できた場合、既知平文攻撃でZIP暗号化を破ることができてしまいます。確認する場合、PkCrackなどで簡単にできてしまうので初めての方は驚かれると思います。
実はZIPが既知平文攻撃に脆弱であることは1994年から知られています。
少し歴史を振り返ります。ZIPが生まれたのは1989年、フィルカッツによりLempel-Ziv-Welch（LZW）アルゴリズムによる圧縮によるデータ圧縮に対応したアーカイブフォーマットとして世に出てきました。暗号化の要望に応えるためTraditional PKWARRE Encryptionによる暗号化が組み込まれます。
もちろん対策としてより強固な暗号化は選択できるようになっているのですが初期値ではありません。変更できることをそもそも知っている人自体が少ないのではないでしょうか。対策としてはオプションを変更すること、ファイル名の暗号化は7-zipオプションのオプションとしては存在しているのでファイル名も暗号化する、共通のファイルを入れないようにするなどが考えられますがZIP暗号化ではなくメール上のリンクからSSOやMFAの認証で守られたファイルストレージアクセスが望ましいでしょう。
ファイルの改ざんに関しても脆弱なためデジタル署名やハッシュ値の検証が行われない場合、解凍したファイル群に悪意あるファイルが仕込まれ、解凍時にスクリプトやバッチファイルなどの実行を防げません。暗号化されたZIPファイルに対してウイルススキャンを行ってもメタデータを分析する程度はできますが完全にリスクを抑えるところまでは達成はできません。
ZIPはあくまでもアーカイブの技術と捉えてユースケースを考えるのが幸せかもしれません。
可能性があるから悪用もあるのです。広くひろまったからこそ、悪用があるのです。
ZIPばかり取り上げましたがPDFもPNGも攻撃に幅広く利用されているのはジェイコブ・ジヴ（Jacob Ziv）博士のある種との偉業と讃えられるべきかもしれません。
以上です。参考になれば幸いです。