みなさんこんにちは。本シリーズ「FPGAで作る暗号は危険?」では、FPGAで暗号機能を実現する方法とその危険性を解説していきます。
第1回は一般的な「暗号」について解説し、暗号には「共通鍵暗号」と「公開鍵暗号」があることを紹介しました。第2回は「共通鍵暗号」について詳しく紹介していきます。
ストリーム暗号
共通鍵暗号は「暗号化と復号で同じ鍵を使用する暗号」でした。高速に動作出来ること、公開鍵暗号に比べて小さな回路規模で実装できることが共通鍵暗号の特徴です。
鍵の使い方によって暗号が「共通鍵暗号」と「公開鍵暗号」に分けられると第1回で解説しましたが、暗号化 / 復号時の動作によって「ストリーム暗号」と「ブロック暗号」に分けることもできます。
ストリーム暗号はデータを1ビットや1バイト単位で取り扱う暗号であり、入力データを順次処理できるため高速な動作が可能です。第1回で古典的な共通鍵暗号として紹介したシーザー暗号 (文字を決まった数シフトさせることで暗号化する換字式暗号) がストリーム暗号です。1 文字入力するたびに暗号化 / 復号の処理 (文字シフト) ができるため、高速な処理が可能です。シーザー暗号は古典的な暗号ですが、現在のストリーム暗号は平文と鍵を排他的論理和 (XOR) することで暗号化する方法が多く使用されています。
暗号化が XOR で行われるため、同じ鍵で再度 XOR すれば元の平文に戻すことができます。つまり、暗号化＝「平文 XOR 鍵」、復号＝「暗号文 XOR 鍵」と簡単な変換のみなので回路規模も小さく高速な動作が可能です。
とても使い易そうに思えますが、安全性を確保するためには難しい問題があります。
暗号文は平文と共通鍵の XOR なので、全て0の平文を暗号化すると共通鍵そのものが暗号文になってしまうことを考えると安全性に問題が出そうなことが分かると思います。
また、共通鍵を繰り返し使用した場合に、周期性から共通鍵を割り出すことができます。そのため、安全性を確保するためには同じ鍵を繰り返さない = 平文と同じサイズの共通鍵を使用することが必要になり、疑似乱数 (ある乱数の次の乱数が計算で求まる乱数) の初期値を共有して算出した値 (乱数) を共通鍵とする方法などが使用されています。
ブロック暗号
ブロック暗号はストリーム暗号と異なりデータを128ビットや256ビットといったブロック単位で暗号化 / 復号する暗号です。
ブロック暗号の暗号化 / 復号には規定数のデータが必要であり、規定数のデータ入力後に処理が開始されるため、暗号化 / 復号の処理速度はストリーム暗号に比べて遅くなります。しかし、AES 暗号に代表されるブロック暗号は世界中の研究者が攻撃方法を研究している中で生き抜いてきた暗号であり、高い安全性を持っています。
暗号にはストリーム暗号とブロック暗号があると紹介しましたが、共通鍵暗号の主流はブロック暗号です。ストリーム暗号は小さな回路規模で高速に動作するため無線 LAN 用のプロトコル (WEP) などで採用されているケースもありますが、共通鍵暗号で使用されている数はブロック暗号である AES 暗号が圧倒的に多い状況です。これは、暗号を使用する際に安全性が最も重視されるためであると考えられます。
AES 暗号
前置きが長くなってしまいましたが、今回のメインである AES 暗号の登場です。AES 暗号は世界で最も多く使用されている共通鍵ブロック暗号であり、FPGA でも比較的簡単に機能を実装することができます。
AES (Advanced Encryption Standard) 暗号は、1997年にアメリカ国立標準技術研究所 (NIST) が行った公募に採用された暗号であり、2001年に NIST が「FIPS PUB 197」として仕様を公開しています。現在の電子政府推奨暗号リスト (CRYPTREC 暗号リスト) にも共通鍵暗号128ビットブロック暗号として記載されていて、安全に使用できる暗号です。FIPS PUB 197には、128ビットの他に192ビットと256ビットもありますが、128ビットの「AES-128」を解説していきます。
共通鍵ブロック暗号は基本的に「データをゴチャゴチャに混ぜる」暗号であり、AES 暗号も同様です。この「ゴチャゴチャに混ぜる」方法によって安全性 (= 解読される危険性) に違いがあり、AES 暗号で定義されている混ぜ方は少なくとも現時点では安全な方法です。もちろん、この先もずっと安全というわけではなく、攻撃方法の発見や計算速度の向上により、いずれ安全でなくなる可能性もあります。
暗号動作の概要
暗号の攻撃方法に「線形解読法」というものがあります。線形解読法を簡単に言えば、平文・暗号文・鍵を使って線形な方程式を立てていくことで、鍵を見つける攻撃方法です。
線形解読法という攻撃方法があるということは、暗号の入出力に線形性があると攻撃される危険性があるということです。「線形性があると…」という表現は数学が苦手な技術者にとっては分かったような、分からないような表現ですが簡単に言ってしまうと、「入出力を y = ax + b で表現できるような暗号は危険」ということだと考えて良いと思います。
線形性を避けるため、AES 暗号を含めた多くの暗号では「非線形変換」を行います。
上の図は AES 暗号の動作をザックリと表現した図です。非線形変換部は一般的に「S-Box」と呼ばれ、AES 暗号以外でも同じ構造を持っている暗号が多くあります。図中で S-Box が複数使用されていますが、これは入力データ (128 ビット) を小さな塊に分けて処理するためです。AES 暗号の場合、8ビット入出力の S-Box を使用して変換するため、128ビットを一度に変換するには16個の S-Box が必要になります。
また、図中に複数回実行と記載しているように、一通りの処理を繰り返します。この繰り返し処理をラウンドと呼びます。AES 暗号の場合、128ビットでは10ラウンド、256ビットでは14ラウンド処理を繰り返します。尚、各ラウンドの処理は全て同一ではない場合があり、AES 暗号では最初と最後のラウンドが他と異なる処理を行います。ラウンド処理はより複雑にデータを混ぜるための処理です。
複数ラウンドの処理を行う際、同じ鍵を使用するよりもラウンド毎に異なる鍵を使用した方がより複雑にデータを混ぜることができます。そのため、ラウンド処理を行う暗号の多くは、AES 暗号も含めて共通鍵を使用して各ラウンド用の鍵を準備します。ラウンド用の鍵をラウンド鍵、ラウンド鍵を準備することを鍵拡張 (Key Expansion)、ラウンド鍵を生成するアルゴリズムを鍵スケジュール (Key schedule) と呼び、ラウンド鍵の生成方法も仕様書 (FIPS PUB 197 / NIST) で決められています。
AES 暗号の処理フロー
AES 暗号の暗号化処理フローを以下の図に示します。SubBytes 処理が非線形化処理であり、続く ShiftRows とMixColumns がデータを混ぜる処理です。AddRoundKey は暗号データに鍵の要素を入れるための処理で具体的には鍵 (ラウンド鍵) を XOR します。
各処理の内容は仕様書に記載されています。仕様書に記載されている処理は数式や行列で書かれているため一見難しく見えますが、AES 暗号はデータの入れ替えと排他的論理和 (XOR) のみで実装できます。
SubBytes
AES 暗号では S-Box を使用した非線形変換処理のことを「SubBytes」と呼び、SubBytes 処理を「データの置換」とだけ書いてある解説が多くあります。SubBytes 処理は8ビットの入力を8ビットの出力に1対1で置き換える変換なので、まさに「データの変換」なのですが、これだけだと何のために行う変換なのかが分かりません。
そんな疑問を解消するため、AES の詳しい解説を探すといきなり数式が羅列された解説になります。SubBytes 処理は数学的に算出された変換であるため、その変換処理を理解するためには数学力が必要になってきます。特に、SubBytes 処理は演算処理を小さく実装できるように数学の「群論」という理論を使用しているため、「ガロア体」や「逆元変換」といった聞き慣れない数学用語が次々に出てきて「暗号は難しい」、「暗号は数学が分からないと実装出来ない」となった方も多くいらっしゃるのではないでしょうか。
演算を使用して SubBytes 処理を実装する場合には算出方法を理解する必要がありますが、単純なデータ変換テーブルを使用すればとても簡単に実装出来ます。SubBytes 処理の入力 (8ビット ) を16進数の 0xXY とすると、以下の表に従って変換するだけです。
入力が 0x00 の場合は出力が 0x63 になり、0x01 であれば 0x7c になるといった具合です。つまり、FPGA が得意とする処理なので、特別な理由がなければ、演算ではなくテーブル変換による SubByte 処理を採用すれば良いと思います。
SubByte 処理が何のために行われているのかが分からないままデータ変換を実装すると、1対1のデータ変換にしか見えず「この処理って必要 ?」という疑問が残ってしまいます。そこで、SubByte 処理が線形性を避けるために行う非線形変換であることを解説しました。もう少し詳しくいえば、AES 暗号の SubBytes 処理は「y = x-1」に変換することで非線形化しています。変換の目的は線形性を避けるためなので、数学的な背景が無い変換でも構いませんが、数学的な裏付けがある変換を用いることで、安心して線形性を取り除いているということができるわけです。
暗号の安全性を高める目的で非線形変換しているのが SubBytes 処理であることを知っていれば、一見無意味に見えるデータ変換の重要性が分かると思います。
MixColumns
暗号処理の内容を数学的に理解して実装することは、数学が苦手な技術者にとって難しいものですが、どういった変換をすれば良いかが分かると実装する上では問題ありません。但し、設計した機能を見直す場合や上手く動かなかった時に原因を探るために少しだけ仕様書の記述と変換機能の関連を理解しておくと便利です。
ここでは、MixColumns について仕様書の記述と変換の関係を説明します。
仕様書に記載されている MixColumns の変換式は以下になります。分かり易くするため、仕様書の記述にスペースや括弧を追加していますが、同じ処理です。
変換式には ( x )、( {02} ・ x )、( {03} ・ x )の 3 種類があります。( x ) はそのままの値を使用し、( {02} ・ x ) は 2 倍なので 1 ビットシフト、( {03} ・ x ) は 3 倍なので、2 倍 + 1 倍と考えます。
ここで、桁が溢れる変換をした場合には少し処理を追加する必要があります。MixColumns で桁が溢れた時の処理は数学の表現で「既約多項式を使用して剰余を取る」ことになるのですが、難しいことは置いておいて、「桁が溢れた場合は 0x1B を XOR する」と考えてしまえば大丈夫です。この 0x1B が既約多項式というものから算出される値であり、XOR することで剰余を取ることに相当します。なんだかややこしいですが時刻25時 = 時刻1時と同じことを行っています。つまり、0x1B が24時に相当し、時刻25時から24時を引く部分が XOR だと考えれば分かり易いと思います。
MixColumns の変換式を HDL で記述した例を以下に示します。
数式の色分けに合わせてコードも色分けしています。黄色が「 x 」、緑色が「 {02}・x 」、赤色が「 {03}・x 」です。桁溢れが発生する (最上位が1) 時は 0x1Bを XOR しています。
まとめ
今回は、共通鍵暗号である AES 暗号の詳細を解説しました。
AES 暗号を実装するために必要な全ての処理は解説しませんでしたが、数学的な解説が多くて難しいと思われがちな SubBytes と MixColumns について処理内容を紹介しました。解説に出てこなかった ShiftRows は単純なデータ入れ替えなので仕様書通りに動作を実装することは難しくありませんし、AddRoundKey は鍵を XOR するのみです。AES 暗号はデータの入れ替えと XOR のみで実装できるので、動作さえ分かれば簡単に組み込むことが可能です。
組み込むこと自体は簡単な AES 暗号ですが、安易に組み込むと暗号で最も重要な安全性が脅かされる危険があります。次回は、FPGA に実装した AES 暗号に対する「サイドチャネル攻撃」を解説する予定です。
株式会社ゴフェルテック 川西紀昭