Adiantum : 低廉な端末でも効率的に使える暗号化技術
2019年3月20日水曜日
この記事は Android セキュリティ & プライバシー チーム、Paul Crowley、Eric Biggers による Google Online Security Blog の記事 "Introducing Adiantum: Encryption for the Next Billion Users" を元に翻訳・加筆したものです。詳しくは元記事をご覧ください。
ストレージを暗号化しておけば、スマートフォンが誰かの手に渡ったとしても、データを守ることができます。Adiantum は、暗号化におけるイノベーションです。暗号化アクセラレーション機能を搭載していない端末でも効率的にストレージを暗号化できるように設計されており、 あらゆる 端末を暗号化できます。
現在の Android では、Advanced Encryption Standard(AES)によるストレージ暗号化が提供されています。新しい Android 端末のほとんどは、ARMv8 Cryptography Extensions による AES 暗号化がハードウェアでサポートされています。しかし、Android はさまざまな端末で実行されています。最新のフラッグシップ スマートフォンやミッドレンジ スマートフォンだけでなく、主に発展途上国で販売されているエントリーレベルの Android Go スマートフォンや、スマートウォッチ、スマート TV などもあります。安価な選択肢を提供するため、端末メーカーがローエンド プロセッサを使うこともあります。たとえば、AES をハードウェアでサポートしていない ARM Cortex-A7 などです。こういった端末では、AES は遅すぎるため、アプリの起動に時間がかかる、端末全般の動作が遅くなるなど、ユーザー エクスペリエンスの低下につながります。そのため、ストレージ暗号化は 2015 年に Android 6.0 以降のほとんどの端末で必須となっているものの、AES パフォーマンスが低い(50 MiB/s 以下の)端末はこの要件が免除されています。私たちは、暗号化は誰でも使えるべきだと考えているため、この点に対応する作業を進めてきました。
HTTPS 暗号化では、この問題は解消されています。ハードウェア アクセラレーションが利用できない場合、ChaCha20 ストリーム暗号化は AES よりもはるかに高速です。一方で、この暗号化はきわめて安全です。高速さの秘訣は、あらゆる CPU がネイティブでサポートしている演算のみ(加算、循環、XOR)を使っている点にあります。そのため Google は、HTTPS インターネット接続を保護するための新しい TLS 暗号スイートとして、2014 年に ChaCha20 と、同じくソフトウェアで高速に処理できる Poly1305 認証を選択しました。ChaCha20-Poly1305 は RFC7539 として標準化されており、AES 命令が搭載されていない端末の HTTPS パフォーマンスを大きく向上させています。
ただし、ディスクとファイルの暗号化には、固有の問題があります。ストレージ デバイス上にあるデータは、「セクタ」に分割されています。現在のセクタの一般的なサイズは、4096 バイトです。ファイルシステムがデバイスにセクタの読み込みまたは書き込みのリクエストを行うと、暗号化レイヤーがそのリクエストをインターセプトし、プレーンテキストと暗号テキストの変換処理を行います。つまり、4096 バイトのプレーンテキストと 4096 バイトの暗号テキストを相互に変換しなければなりません。しかし、RFC7539 を使うと、暗号テキストはプレーンテキストよりもわずかに大きくなります。暗号の nonce とメッセージの整合性情報を格納するために、わずかな領域が必要になるからです。この追加情報を格納する場所をソフトウェアで探すテクニックも存在しますが、効率が落ち、ファイルシステムの設計も大幅に複雑化する可能性があります。
AES でディスクを暗号化する際によく使われるソリューションは、サイズが変わらない XTS モードまたは CBC-ESSIV モードを利用する方式です。現在の Android は、ディスク全体の暗号化には AES-128-CBC-ESSIV を、ファイルベースの暗号化には AES-256-XTS を利用しています。しかし、AES のパフォーマンスが不十分な場合は、ローエンド ARM プロセッサでも十分なパフォーマンスを出せる代替方式として広く普及しているものはありません。
この問題を解決するために、Adiantum という新しい暗号化モードを設計しました。Adiantum を使うと、サイズを変えないモードで ChaCha ストリーム暗号を使えるようになります。これは、HCTR や HCH など、サイズを変えない AES ベースの暗号化として提案されている方式の考え方を取り入れることによって実現しています。ARM Cortex-A7 は、4096 バイトのセクタに対する Adiantum による暗号化と復号化を、1 バイト当たり約 10.6 サイクルで実行できます。これは、AES-256-XTS より約 5 倍高速です。
Adiantum は、XTS や CBC-ESSIV などのモードとは異なり、真のワイドブロック モードを実現しています。つまり、プレーンテキスト内のどのビットを変更しても、暗号テキストのすべてが変更され、判別できなくなります。その逆も同じことが言えます。動作の仕組みは、以下のようになっています。最初に、Poly1305 および別の非常に高速な鍵つきハッシュ関数である NH に基づく鍵つきハッシュ化によって、プレーンテキストのほぼ全体をハッシュ化します。また、「tweak」と呼ばれる値もハッシュ化します。これは、セクタごとに異なる暗号化を行うようにするためのものです。次に、このハッシュを使い、ChaCha 暗号化に使う nonce を生成します。復号化でも暗号化と同じ強度を実現できるように、暗号化の後、再度ハッシュ化を行います。この処理は、暗号化したものを復号化できるように、ファイステル ネットワークという形で構造化されています。16 バイトのブロックに対して AES-256 を 1 回実行する必要もありますが、4096 バイトの入力に比べれば、パフォーマンス的に大きな影響はありません。
ChaCha のような暗号プリミティブは、「ラウンド」として扱われています。このラウンドを繰り返すたびに、スピードと引き替えに安全性が高まります。多種多様な端末で十分高速にディスクを暗号化できるように、一般的に使われている 20 ラウンドの ChaCha ではなく、12 ラウンドの方式を選択しています。ラウンドを繰り返すたびに、攻撃の難易度は大幅に上がります。7 ラウンドの方式は 2008 年に破られており、多くの論文も発表されて攻撃方法も向上していますが、8 ラウンドを破ることができる攻撃方法は今のところ見つかっていません。実は、繰り返すラウンド数と現在破られているラウンド数の比率で見れば、AES-256 よりも ChaCha12 の方が優れています。
Adiantum はまだ生まれたばかりですが、私たちはその安全性に強い自信を持てる立場にあります。私たちの論文では、ChaCha12 と AES-256 が安全であるという前提のもと、Adiantum が優れたセキュリティ特性を持つことを証明しています。ChaCha や AES のような「プリミティブ」から XTS、GCM、Adiantum などの「構造」を作るというのは、暗号の世界では標準的な技法です。プリミティブが安全であるかどうかについては、私たちが説得力のある主張を行えることは多いものの、その証拠を提供することはできません。ただし、プリミティブが安全であれば、そこから作った構造も安全であることは証明できます。NH および Poly1305 ハッシュ関数については、前提とする必要はありません。必要な暗号特性("ε-almost-∆-universality")を持っていることが証明されているからです。
Adiantum は、ホウライシダという植物にちなんで名付けられました。ヴィクトリア時代の花言葉では、誠実さと慎みを表す植物とされています。
Adiantum の一般的な実装および ARM に最適化された実装は、Android 共通カーネル v4.9 以降およびメインライン Linux カーネル v5.0 以降で利用できます。リファレンス コード、テストベクトル、ベンチマーク スイートは、https://github.com/google/adiantum で公開されています。
Android 端末メーカーは、AES のパフォーマンスが 50 MiB/秒以下かつ Android Pie を搭載する端末で、ディスク全体またはファイルベースの暗号化に Adiantum を利用することができます。AES がハードウェアでサポートされている場合は、Adiantum よりも AES の方が高速です。AES のパフォーマンスが 50 MiB/s を超える場合は、AES の使用が必須である点は変わりません。Android Q では、Adiantum が Android プラットフォームの一部となる予定です。今後、すべての新しい Android 端末で、許可されているいずれかの暗号化アルゴリズムを使った暗号化が必須となるように、Android Compatibility Definition Document(CDD)を更新する予定です。
謝辞: 本投稿は、Greg Kaiser および Luke Haviland による寄稿に基づいています。Adiantum は、Paul Crowley と Eric Biggers が設計し、Eric Biggers と Greg Kaiser が Android に実装しました。命名は、Danielle Roberts によって行われました。
Reviewed by Eiji Kitamura - Developer Relations Team
ストレージを暗号化しておけば、スマートフォンが誰かの手に渡ったとしても、データを守ることができます。Adiantum は、暗号化におけるイノベーションです。暗号化アクセラレーション機能を搭載していない端末でも効率的にストレージを暗号化できるように設計されており、 あらゆる 端末を暗号化できます。
現在の Android では、Advanced Encryption Standard(AES)によるストレージ暗号化が提供されています。新しい Android 端末のほとんどは、ARMv8 Cryptography Extensions による AES 暗号化がハードウェアでサポートされています。しかし、Android はさまざまな端末で実行されています。最新のフラッグシップ スマートフォンやミッドレンジ スマートフォンだけでなく、主に発展途上国で販売されているエントリーレベルの Android Go スマートフォンや、スマートウォッチ、スマート TV などもあります。安価な選択肢を提供するため、端末メーカーがローエンド プロセッサを使うこともあります。たとえば、AES をハードウェアでサポートしていない ARM Cortex-A7 などです。こういった端末では、AES は遅すぎるため、アプリの起動に時間がかかる、端末全般の動作が遅くなるなど、ユーザー エクスペリエンスの低下につながります。そのため、ストレージ暗号化は 2015 年に Android 6.0 以降のほとんどの端末で必須となっているものの、AES パフォーマンスが低い(50 MiB/s 以下の)端末はこの要件が免除されています。私たちは、暗号化は誰でも使えるべきだと考えているため、この点に対応する作業を進めてきました。
HTTPS 暗号化では、この問題は解消されています。ハードウェア アクセラレーションが利用できない場合、ChaCha20 ストリーム暗号化は AES よりもはるかに高速です。一方で、この暗号化はきわめて安全です。高速さの秘訣は、あらゆる CPU がネイティブでサポートしている演算のみ(加算、循環、XOR)を使っている点にあります。そのため Google は、HTTPS インターネット接続を保護するための新しい TLS 暗号スイートとして、2014 年に ChaCha20 と、同じくソフトウェアで高速に処理できる Poly1305 認証を選択しました。ChaCha20-Poly1305 は RFC7539 として標準化されており、AES 命令が搭載されていない端末の HTTPS パフォーマンスを大きく向上させています。
ただし、ディスクとファイルの暗号化には、固有の問題があります。ストレージ デバイス上にあるデータは、「セクタ」に分割されています。現在のセクタの一般的なサイズは、4096 バイトです。ファイルシステムがデバイスにセクタの読み込みまたは書き込みのリクエストを行うと、暗号化レイヤーがそのリクエストをインターセプトし、プレーンテキストと暗号テキストの変換処理を行います。つまり、4096 バイトのプレーンテキストと 4096 バイトの暗号テキストを相互に変換しなければなりません。しかし、RFC7539 を使うと、暗号テキストはプレーンテキストよりもわずかに大きくなります。暗号の nonce とメッセージの整合性情報を格納するために、わずかな領域が必要になるからです。この追加情報を格納する場所をソフトウェアで探すテクニックも存在しますが、効率が落ち、ファイルシステムの設計も大幅に複雑化する可能性があります。
AES でディスクを暗号化する際によく使われるソリューションは、サイズが変わらない XTS モードまたは CBC-ESSIV モードを利用する方式です。現在の Android は、ディスク全体の暗号化には AES-128-CBC-ESSIV を、ファイルベースの暗号化には AES-256-XTS を利用しています。しかし、AES のパフォーマンスが不十分な場合は、ローエンド ARM プロセッサでも十分なパフォーマンスを出せる代替方式として広く普及しているものはありません。
この問題を解決するために、Adiantum という新しい暗号化モードを設計しました。Adiantum を使うと、サイズを変えないモードで ChaCha ストリーム暗号を使えるようになります。これは、HCTR や HCH など、サイズを変えない AES ベースの暗号化として提案されている方式の考え方を取り入れることによって実現しています。ARM Cortex-A7 は、4096 バイトのセクタに対する Adiantum による暗号化と復号化を、1 バイト当たり約 10.6 サイクルで実行できます。これは、AES-256-XTS より約 5 倍高速です。
Adiantum は、XTS や CBC-ESSIV などのモードとは異なり、真のワイドブロック モードを実現しています。つまり、プレーンテキスト内のどのビットを変更しても、暗号テキストのすべてが変更され、判別できなくなります。その逆も同じことが言えます。動作の仕組みは、以下のようになっています。最初に、Poly1305 および別の非常に高速な鍵つきハッシュ関数である NH に基づく鍵つきハッシュ化によって、プレーンテキストのほぼ全体をハッシュ化します。また、「tweak」と呼ばれる値もハッシュ化します。これは、セクタごとに異なる暗号化を行うようにするためのものです。次に、このハッシュを使い、ChaCha 暗号化に使う nonce を生成します。復号化でも暗号化と同じ強度を実現できるように、暗号化の後、再度ハッシュ化を行います。この処理は、暗号化したものを復号化できるように、ファイステル ネットワークという形で構造化されています。16 バイトのブロックに対して AES-256 を 1 回実行する必要もありますが、4096 バイトの入力に比べれば、パフォーマンス的に大きな影響はありません。
ChaCha のような暗号プリミティブは、「ラウンド」として扱われています。このラウンドを繰り返すたびに、スピードと引き替えに安全性が高まります。多種多様な端末で十分高速にディスクを暗号化できるように、一般的に使われている 20 ラウンドの ChaCha ではなく、12 ラウンドの方式を選択しています。ラウンドを繰り返すたびに、攻撃の難易度は大幅に上がります。7 ラウンドの方式は 2008 年に破られており、多くの論文も発表されて攻撃方法も向上していますが、8 ラウンドを破ることができる攻撃方法は今のところ見つかっていません。実は、繰り返すラウンド数と現在破られているラウンド数の比率で見れば、AES-256 よりも ChaCha12 の方が優れています。
Adiantum はまだ生まれたばかりですが、私たちはその安全性に強い自信を持てる立場にあります。私たちの論文では、ChaCha12 と AES-256 が安全であるという前提のもと、Adiantum が優れたセキュリティ特性を持つことを証明しています。ChaCha や AES のような「プリミティブ」から XTS、GCM、Adiantum などの「構造」を作るというのは、暗号の世界では標準的な技法です。プリミティブが安全であるかどうかについては、私たちが説得力のある主張を行えることは多いものの、その証拠を提供することはできません。ただし、プリミティブが安全であれば、そこから作った構造も安全であることは証明できます。NH および Poly1305 ハッシュ関数については、前提とする必要はありません。必要な暗号特性("ε-almost-∆-universality")を持っていることが証明されているからです。
Adiantum は、ホウライシダという植物にちなんで名付けられました。ヴィクトリア時代の花言葉では、誠実さと慎みを表す植物とされています。
参考資料
設計の詳細、安全性の証明については、論文 Adiantum: length-preserving encryption for entry-level processors をご覧ください。IACR Transactions on Symmetric Cryptology に掲載されています。この論文は、3 月の Fast Software Encryption カンファレンス(FSE 2019)で発表される予定です。Adiantum の一般的な実装および ARM に最適化された実装は、Android 共通カーネル v4.9 以降およびメインライン Linux カーネル v5.0 以降で利用できます。リファレンス コード、テストベクトル、ベンチマーク スイートは、https://github.com/google/adiantum で公開されています。
Android 端末メーカーは、AES のパフォーマンスが 50 MiB/秒以下かつ Android Pie を搭載する端末で、ディスク全体またはファイルベースの暗号化に Adiantum を利用することができます。AES がハードウェアでサポートされている場合は、Adiantum よりも AES の方が高速です。AES のパフォーマンスが 50 MiB/s を超える場合は、AES の使用が必須である点は変わりません。Android Q では、Adiantum が Android プラットフォームの一部となる予定です。今後、すべての新しい Android 端末で、許可されているいずれかの暗号化アルゴリズムを使った暗号化が必須となるように、Android Compatibility Definition Document(CDD)を更新する予定です。
謝辞: 本投稿は、Greg Kaiser および Luke Haviland による寄稿に基づいています。Adiantum は、Paul Crowley と Eric Biggers が設計し、Eric Biggers と Greg Kaiser が Android に実装しました。命名は、Danielle Roberts によって行われました。
Reviewed by Eiji Kitamura - Developer Relations Team