はじめに
AESは現在デファクトスタンダードのブロック暗号アルゴリズムで、だいたい使用する時は第一選択になります。
そのデファクトスタンダードであるAESを高速に実装するために、x64系CPUではAES-NI命令が実装されています。(AES-NI命令のメリットは高速化だけではなく、キャッシュ攻撃という攻撃に対する安全性があります)
さて、あまり素人には推奨されないのですが、オリジナルのブロック暗号、ストリーム暗号またはハッシュ関数を設計する際に、高速実装のために、AES-NIの命令を利用したいことがあります。そこで、ここではAES-NI命令をうまく使ってどのようなことができるかを示します。
AESの各関数
AESは複数の関数の組み合わせで出来ています。FIPS197によると
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
- SubWord
- RotWord
です。また、これらの関数のうち、SubBytes、ShiftRows、MixColumnsは復号のために逆関数が定義されています。この記事では、 - InvSubBytes
- InvShiftRows
- InvMixColumns
と記載します。
AddRoundKeyは逆関数が関数と一致するため、SubWordとRotWordは復号でも逆関数は使用しないため、定義されていません。関数の中身は詳しくはFIPS197で。
ここで、少しだけ簡単な説明をします。
SubBytes
16バイトの内部状態S[0,0]~S[3,3]に対して、変換テーブルを使って変換します。逆関数は元に戻します。
ShiftRows
内部状態を4×4のテーブルと見なして、各行で巡回シフト(ローテート)します。ローテートのパラメータは行ごとに違います。
逆関数は元に戻すため、ローテートの方向が逆になります。
MixColumns
内部状態を4×4のテーブルと見なして、各列で計算します。この計算はちょっとややこしいのでここでは省略します。逆関数は元に戻します。
ShiftRowsで行をシャッフルし、MixColumnsで列を混合することにより、SubBytesの効果を内部状態全体に広げます。
AddRoundKey
内部状態に対して秘密鍵生成された拡大鍵を排他的論理和します。
SubWord
拡大鍵生成に使います。4バイトの値をバイトごとに変換テーブルを使って変換します。変換テーブルはSubBytesと同じです。
RotWord
拡大鍵生成に使います。4バイトの値を8ビット右ローテートします。
AES-NI命令
AES-NI命令は
- AESENC
- AESENCLAST
- AESDEC
- AESDECLAST
- AESKEYGENASSIST
- AESIMC
の6命令で構成されています。それぞれの中身を説明します。
AESENC
AESENCは内部状態128bitと拡大鍵128ビットを引き数に持ち、SubBytes, ShiftRows, MixColumns, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの暗号化1ラウンド分に相当します。
AESENCLAST
AESENCLASTは内部状態128bitと拡大鍵128ビットを引き数に持ち、SubBytes, ShiftRows, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの暗号化最終ラウンドに相当します。AESENCとの違いはMixColumnsを実行しない点です。
AESDEC
AESDECは内部状態128bitと拡大鍵128ビットを引き数に持ち、InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの復号1ラウンド分に相当します。
AESDECLAST
AESDECは内部状態128bitと拡大鍵128ビットを引き数に持ち、InvSubBytes, InvShiftRows, AddRoundKeyを連続して実行した結果の内部状態を返します。AESの復号最終ラウンドに相当します。AESDECとの違いはInvMixColumnsのみです。
AESKEYGENASSIST
AESKEYGENASSISTは現在のラウンドの拡大鍵を引き数に持ち次のラウンドの拡大鍵を生成します。SsubWordとRotWordが使用されていますが、それだけではありません。
AESIMC
AESIMCは内部状態128ビットを引き数に持ち、InvMixColumnsを実行します。暗号化用拡大鍵から復号用拡大鍵を生成します。
AES-NI命令をちょっとマニアックに使う
というわけで、応用編です。いくつかの関数を組み合わせた命令を使って、存在しない組み合わせを作り出せないか？という話です。
SubBytes+ShiftRows+MixColumns
AESENCから、AddRoundKeyを抜いたものです。AddRoundKeyは単に排他的論理和ですので、オール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。
SubBytes+ShiftRows
SubBytes+ShiftRows+MixColumnsがあるのだから、MixColumnsはInvMixColumnsで打ち消せば...と思ってしまいそうですが、AESENCLASTを使えばより高速に実装できます。つまり、AESENCLASTにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。
SubBytes
SubBytesを単独で実装するのなら、仕様書通りに実装したほうが良いと思いがちですが、16回のテーブル参照を行う位なら、InvShiftRows(4回のローテート)を実装してやったほうがよさげです。（テーブル参照はキャッシュ攻撃という弱点を引き込む可能性もあります。
つまり、前項のSubBytes+ShiftRowsにInvShiftRowsを組み合わせるのです。
ただ、当然処理はSubBytes+SfitRowsより遅くなります。何かを設計するのなら、SubBytesを単独で使うのは良くないと言えます。
ShiftRows+SubBytes
SubBytesとShiftRowsを入れ替えても結果は変わりません。これは何かに使えそうです。
InvSubBytes+InvShiftRows+InvMixColumns
これも、AESDECにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。
InvSubBytes+InvShiftRows
これも、AESDECにオール0を拡大鍵128ビットとして渡してやれば、この処理は可能です。
InvSubBytes
SubBytes同様、ShiftRowsを実装してやるほうが速そうです。
InvShiftRows+InvSubBytes
InvSubBytesとInvShiftRowsは入れ換え可能ですので、InvShiftRows+InvSubBytesも計算可能です。
MixColumns
さて、単体でMixColumnsを抽出してみましょう。使うものは二つ、
- InvShiftRows+InvSubBytes
- SubBytes+ShiftRows+MixColumns
です。
この二つを連結してやると、
InvShiftRows+InvSubBytes+SubBytes+ShiftRows+MixColumns
になります。ところが、InvSubBytesとSubBytesは逆変換なので、この二つを連結すると無変換になります。つまり
InvShiftRows+ShiftRows+MixColumns
ですね。
さらに、InvShiftRows+ShiftRowsも逆変換なので消えます。つまり、
MixColumns
が残ります。
結論
以下の関数の連結はAES-NI命令一つで実装可能
- SubBytes+ShiftRows+MixColumns
- SubBytes+ShiftRows
- InvSubBytes+InvShiftRows+InvMixColumns
- InvSubBytes+InvShiftRows
以下の関数はAES-NI命令二つで実装可能
- MixColumns
逆に、SubBytesやShiftRowsをAES-NI命令のみで実装するのは困難です。うまくこの組み合わせを利用すれば、AES-NIを用いて高速実装可能なブロック暗号・ハッシュ関数等が設計可能と言えます。