※こちらの記事は2020年10月19日公開note版「ラック・セキュリティごった煮ブログ」と同じ内容です
こんにちは、セキュリティエンジニア見習いのA#です。
セキュリティ関係の仕事をしていると、「暗号」という言葉を目にしない日がありません。
暗号(暗号化)とは何かということを改めて説明する必要はないかもしれませんが、「情報を文字列として伝達する際に、その情報の発信者と受信者以外の第三者が読んでも意味がわからないようにすること」です。謎のひらがなの文字列の横にたぬきの絵が描かれた「たぬき暗号」などを見かけたことがある人は多いのではないでしょうか。
暗号には強度というものがあり、正しい暗号の読み方を知らない第三者が短時間で解読できてしまうならその暗号は弱い(脆弱)と言います。
セキュリティ診断の作業の中で、診断対象のアプリケーションなどで使用されている暗号化方式を見て「この暗号化方式は安全、この暗号化方式は脆弱性あり」という判断をする場面があります。ある暗号が安全かどうかの判断は公的機関から出されているガイドラインに沿って行うのですが、ふと、脆弱性がある暗号というのは、実際にはどのくらい脆弱なんだろう、というのが知りたくなったのです。どのくらい、というのはつまり自分が普段使用するごく普通の性能のPCで暗号を解読することが可能かどうか、可能なのであればどれくらい時間を必要とするのか、といったようなことです。
暗号化されたファイルをテキストエディタなどで開いてみたことがある人ならお分かりかと思いますが、まるで意味のわからない文字の羅列です。
鮎a巳ﾘﾊ�4'ｯﾘｧ=?K�8O\eｴ;/Rjｷ�)s｡@ｬﾇ�Vnm:ｷ張4GDLbJ萃ｲ寥庶熟5ﾇ�i臭 ｦR*@3ｭﾝﾚmﾄ�艘Nﾘ5｡M[k�甥ﾁｯﾈ��$nJﾑ:aZ|�m燧ﾂ*MﾕT_9� "ｹｲ\�O�<Zv�B:t喆A _閹ズ�oツV�ｧaｼ�6ﾜd樔p0謗ﾛJ7ｮ�
例えばこんな感じ。これは「DES(Data Encryption Standard)」という暗号化方式で適当な英文を暗号化したものをそのままメモ帳で開いたところです。
DESは1970年代に開発され、1990年代まで安全な暗号として使用されていたものです。現在はAES(Advanced Encryption Standard)やDESを応用したトリプルDESといった方式にとってかわられており、DES自体は安全ではないとみなされています。今回のテーマではこのDESを解読することを目標にします。
実際に手元で動かしてみるため、Sebastien Rannou氏のGitHubページのCプログラムを使用させていただきました。(https://github.com/aimxhaisse/des/blob/master/des.c)
それにしても上の文字列、たぬき暗号の発想の延長でどれだけ頭をひねったところで、100年かかっても解読できそうにありません。
暗号解読のとっかかりとして知っておくべき基礎知識が1つあります。それは「暗号は暗号化方式と鍵によって作られていて、暗号化方式自体は基本的に公開されている」ということです。なぜわざわざ公開するかというと、主に暗号化方式はより多くの研究者によって検証されることでその安全性が証明される、という考え方に基づいているためです(詳しく知りたい方は「ケルクホフスの原理」でググってください)。
今回は暗号化方式としてDESを使用しているということがわかっている、という状況を前提として話を進めます。この場合、あとは鍵さえ見つければこの暗号を元の文章に戻せるはずです。
DESの仕組みについて詳しい説明は省きますが、鍵は56bitのデータとなっています。ということは一番単純に考えると、コンピュータで総当りで解読しようとするなら000…(0を56個分)から順番に2の56乗(約7.2京)通りの鍵で復号を試してみれば、その中に正しく復号された文字列が1つ存在するはずです。
ではこの回数の復号を行うのにどのくらい時間がかかるのか、先程のCプログラムで試算してみます。
まず適当な英文を用意します。
You will rejoice to hear that no disaster has accompanied the commencement of an enterprise which you have regarded with such evil forebodings. I arrived here yesterday, and my first task is to assure my dear sister of my welfare and increasing confidence in the success of my undertaking.
これは小説「フランケンシュタインの怪物」の冒頭の一節ですが、特にこのチョイスに意味はありません。テキストのデータサイズは290バイトです。
このテキストをinput.txt、鍵を「abcdefg」として暗号化しました。
$ ./des -e -i input.txt -o encode.txt -k abcdefg
出力(暗号化)されたencode.txtは以下のようになります。
(実は先程の例で上げた文字列がこれです)
鮎a巳ﾘﾊ�4'ｯﾘｧ=?K�8O\eｴ;/Rjｷ�)s｡@ｬﾇ�Vnm:ｷ張4GDLbJ萃ｲ寥庶熟5ﾇ�i臭 ｦR*@3ｭﾝﾚmﾄ�艘Nﾘ5｡M[k�甥ﾁｯﾈ��$nJﾑ:aZ|�m燧ﾂ*MﾕT_9� "ｹｲ\�O�<Zv�B:t喆A _閹ズ�oツV�ｧaｼ�6ﾜd樔p0謗ﾛJ7ｮ�
これを、「1」から「1000」の鍵で1000回復号してみます。
$ date 2020年 xx月 xx日 XX曜日 00:36:30 JST $ for i in `seq 1000` > do > ./des -d -i output.txt -o decode$i.txt -k$i > done $ date 2020年 xx月 xx日 XX曜日 00:36:37 JST
大体7秒かかりました。
このやり方ではどう考えてもディスクI/Oがネックになっていそうですが、とりあえず気にせずに進めます。
1000回の復号に7秒なら、7.2京回の復号には…と計算すると約500兆秒、およそ1600万年です。多少改良の必要がありそうです。
ただ、その前に1000回実行した時点で(頭のいい人はそれ以前に)大抵の人はこのやり方の問題点に気づくでしょう。
PC上には1000回復号を試したことで1000個のテキストファイルが出力されているわけですが、仮にこの中に正しく復号されたものがあるとして、それを一体どうやって確かめるのか、ということです。復号の処理の中ではその鍵が正しいかどうかの検証はしないので、鍵の正しさはあくまで出力されたテキストファイルから判断するしかありません。
特定の文字列が含まれていることがあらかじめわかっているならそれでディレクトリを検索するというのも手ですが、今回はそういう手がかりはありません。
1000個なら人力でもなんとか全部のテキストファイルを開いて確認というのもできそうですが、7.2京個となると現実的ではありません。おそらく1600万年より多くかかるでしょう。
個人ではこのあたりが限界なので先人の知恵に頼ることにします。
DESの脆弱性を指摘した研究者たちは、この問題をどうやって解決してきたのでしょうか。「暗号が正しく復号されたかどうか」をどうやって判断するか、というのはおそらくコンピュータで暗号解読を試みるなら必ず突き当たる問題のはずです。
適当に「暗号 解読 判定」でググってみましたが出てくるのはソシャゲの攻略サイトらしきものばかりでなかなか探しているものは見つかりません。
いろいろ検索ワードを変えて小一時間、ようやくそれらしき記述を見つけました。
電子政府行政情報化事業 将来の暗号技術に関する安全性要件調査 調査報告書
(https://www.ipa.go.jp/security/fy15/reports/crypt_requirement/documents/crypt_requirement.pdf)
このPDF文書の14ページに知りたかった情報がほとんど書かれていました。
平文の持つ何らかの特徴によって、ランダムなデータから区別することを、有意性検定という。
だそうです。
有意性検定の具体的な方法についても同じページ内で触れられています。
今回の件で特に知りたかった点を抜き出してポイントをまとめると以下のようになります。
・データの有意性は、それぞれのバイトがASCIIのプリント可能文字、あるいは日本語コードの文字列などとして解釈可能かどうかによって判断できる
・DESの復号ではデータの先頭から8バイトずつ切り出して変換を行うので、8バイト復号を行うごとに有意性検定を行い、それをクリアした場合のみ次の8バイトを変換するという方式にすることで有意性検定のコストをほとんど無視できるようになる(言い換えると、総当りで復号を行う際にかかる時間は、暗号文の長さとは関係なく「先頭の8バイトの復号にかかる時間×全ての鍵の数」にほぼ等しくなる)
これを踏まえて、先程の時間測定を以下の条件でやり直します。
・復号の対象とするテキストファイルは、元の290バイトの文章の先頭8バイト("You will")を暗号化したものを使用する
・出力されるファイルは使用しない(必要なのは有意性検定をクリアしたもののみ)ので、ディスク書き込みの時間を省略するため(/dev/nullに)捨てる
もちろん今回のCプログラムには有意性検定の処理はまだ実装していませんが、実際に暗号を突破したいのではなく時間の見積もりがしたいだけなのでそこのコスト(処理時間)は「無視」します。
まず8バイト分の文字列(input8.txt)を先程と同様に暗号化します。
$ ./des -e -i input8.txt -o output8.txt -k abcdefg
output8.txtの中身は以下のようになりました。
鮎a巳ﾘﾊ
次にこの暗号化した8バイトのファイルを1000回復号します。
今回は所要時間が1秒を切ることが予想されたので、ナノ秒まで測るオプションをつけました。
$ date +%s:%N 1602440335:073364660 $ for i in `seq 1000` > do > ./des -d -i output8.txt -o /dev/null -k$i > done $ date +%s:%N 1602440335:875981852
約0.8秒になりました。7.2京回の復号には約57兆秒、183万年。
だいぶ短縮できたとはいえまだライフワークとしても長すぎます。
オーバーヘッドを考えると、1回の処理ごとにプロセスを終了して作り直しているのも入力をディスクから読み込んでいるのも無駄なのでプログラムのそのあたりを修正すればもっと早くなるはずですが、そのあたりを考慮に入れても「DESを個人PCで解読する」というのは事前に考えていたほど甘くはなさそうですね。アメリカの国家機密に使用されていたというのは伊達ではないです。
念の為に書くと、DESが現在すでに安全ではないというのは事実で、20年ほど前の研究では22時間で解読できたという結果もあるようです。
とりあえずコマンドラインでささっとできるレベルではこんな感じです。
じゃあ全てオンメモリでGPUも使って並列処理で…とやったらどれくらいまでいけるのか、次回(あれば)挑戦してみるかもしれません。
