Linuxをフルディスク暗号化するとブートがとても遅くなる

先日公開したスクリプトを使ってLinuxをフルディスク暗号化インストールしていますが、GRUBが暗号の解除にものすごく時間をかけることに気が付きました。

注意:私は暗号の素人です。以下の文章は眉に唾をつけて読んでください。

正確に言えば、この現象についてはVMWare上で数えきれないくらい試験インストールを繰り返したときに気が付いていました*1。が、実機ではこんな現象は起きないだろう*2と高を括っていました。

蓋を開けてみると、ThinkPad x220上で毎回暗号化の解除に20秒近く待たされています。

LUKSボリュームとパスフレーズハッシュ値

なぜこのようなことが起きているかを理解するにはLinuxのLUKS暗号化仕様について概要を理解する必要があります。きちんとしたシステムにおいては、ユーザーのパスワードやパスフレーズがそのまま*3保存されることはありません。これらは「ハッシュ化」という処理をされて記録されます。

ハッシュ化とは、例えば"hello"という文字列を"5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03"のような「ごちゃごちゃした」文字列に変換する処理です。helloから生成したこのごちゃごちゃした文字列をハッシュ値と呼びます。この変換は数学的な変換で、helloからhelloのハッシュ値を求めるのは(コンピュータには)簡単ですが、逆にhelloのハッシュ値からhelloを求めることは現実的な時間内では困難になっています。ですので、仮にパスワード・パスフレーズハッシュ値が漏洩したとしても即座にアカウントに侵入されるわけではありません。

LUKSは、(暗号化していない)ヘッダー領域にパスフレーズハッシュ値を記録しており、ユーザーがパスフレーズをたたくとソフトウェアがそのハッシュ値と照合して正しいパスフレーズか否かを調べます。一致していた場合はそのパスフレーズを使って暗号化を解除します。

さて、ハッシュ値からパスフレーズを求めるのは先に述べたように困難ですが、強力な計算機を使って力づくで攻撃すれば、いつかは突破されます。つまり、PCが盗まれた場合には、攻撃者はLUKSボリュームからパスフレーズハッシュ値を取り出し、パスフレーズを総当たりでハッシュ化するという攻撃をすることができます。ハッシュ値の計算はコンピュータには簡単なのでこれができるわけです。

このような攻撃に対抗するために、LUKS仕様()ではパスフレーズをハッシュ化する際に、ストレッチングと呼ばれる手法を採用しています。これはハッシュ関数のに対して繰り返しハッシュ関数を適用する方法です。例えば、ハッシュ関数パスフレーズに1000回繰り返して掛ければ、攻撃者の負担も1000倍になります。この理屈で、LUKS標準*4では、最初のボリューム暗号化時に

「ハッシュの計算に1秒かかるようようなストレッチ回数」

を求めて、その回数と一緒にパスフレーズハッシュ値を記録しています。典型的なデスクトップPCへのインストール作業では、インストール作業をインストール対象となるPC上で行いますので、この計算1秒かかるストレッチ回数を求めるPCと、インストール対象が同じと言うことです。

つまり、インストール先ではパスフレーズ入力からハッシュ照合に1秒かかります。

何が起きているのか

ところが、この照合に1秒どころが数秒、あるいはそれ以上かかっているようだ、というのが今回の問題です。

調べてみると、この問題はよく知られているGRUBの問題だとわかりました。

まず、この問題はUbuntuに同梱されているインストーラをつかって暗号化インストールをした場合には起きません。この標準インストーラによる暗号化は/bootディレクトリが暗号化されておらず、そのためGRUBは暗号化ディスクに触れずにLinuxカーネルをロードします。パスフレーズを受け取ってハッシュ値と照合するのはLinux自体*5の仕事であり、このライブラリはLUSKボリュームを暗号化するときにハッシュのストレッチ回数を計算するときに使ったライブラリそのものです。つまり、期待通り1秒でハッシュの計算を終えます。

ところが、フルディスク暗号化をすると、/bootディレクトリも暗号化ボリュームに入っており、結果としてGRUBが自分自身でパスフレーズハッシュ値を計算しなければなりません。もうお分かりだと思いますが、どうやらGRUBはこの計算ルーチンがLinuxのライブラリとは異なるらしく、数分の一かそれ以下の速度しか出ないようです。そのため、/bootまで暗号化するフルディスク暗号化インストールではパスフレーズの照合にとてつもない時間がかかることになります。

銀の弾丸はない

さすがに毎回10秒近くも待つのは苦痛です。ましてや長いパスフレーズを設定した場合は打ち間違いもおきます。苦痛は文字通り倍増します。

海外のディスカッションを見てみても、考えられる対策には一長一短があります。

ストレッチ回数を少なくする ハッシュ値に対するブルートフォース攻撃に対して線形に弱くなる。
/boot暗号化をあきらめる トロイの木馬による攻撃に対して弱くなる。
GRUBによる長いハッシュ照合時間を我慢する

長いパスフレーズを間違えた時にとても苦痛。

パスフレーズを短くする ショルダーハッキングに弱くなる。攻撃者のブルートフォース攻撃に指数関数的に弱くなる。

といったところです。

では、現実的な解はどれでしょうか。私は興味本位でこの問題を見ていますが、この中で技術的に最も安全な選択肢は「我慢する」です。しかしながら、私は「他者に苦痛を与えることで目の前の問題が解決したと言い張る」という行動様式が嫌いなので却下します。そもそもこの方針は、一度苦痛を覚えた人が「パスフレーズを短くする」に走りがちです。

ハッシュへの攻撃を一番下で支えているのはブルートフォース攻撃であり、攻撃者の負担はパスフレーズの長さとともに指数関数的に増えます。したがってパスフレーズを短くすることはセキュリティ上もっともまずい選択です。

仮に「1文字増えるごとに、攻撃者の負担は文字の種類分*6だけ増える」とすると、チェーンの長さを1000分の1にしてもパスフレーズを2文字増やすだけでカバーできそうです。

まとめ

この問題に関しては「苦痛に耐える」という根性論か、何らかの形で脆弱性を受け入れるかの二者択一を迫られることになります。しかしながら、苦痛とセキュリティのバランスを考えると

「ストレッチ回数を短くしてでも長いパスフレーズを使う」

という方針が合理的のように思えます。

さて、このエントリで述べたことはGRUBの遅さに起因する問題です。とはいえ、海外のディスカッションを見るとあしざまにGRUBをののしる人もいて、「それはOSSの考え方として違うだろう」などということも感じます。そこまで言うのであれば、不満のある人が手を挙げて修正するべきでは、と感じます。

 

*1:インストールの実験は毎回ものすごく時間がかかる。そしてやり直しがきかないのでVMWareのスナップショット機能を使って何度も繰り返すことになる

*2:起きないといいな

*3:平文で

*4:LUKS1

*5:の暗号化ライブラリ

*6:例えば英子文字なら26種