bit slicingのユースケース

skyScheme

今後も拡充予定。。

テーブル参照の置換

DESやAESのような暗号化をbit slicingで実装した！というものは、要するにS-Boxの参照処理を論理ゲートに置き換えていく。
S-Boxとはランダムな対応表で、単純な換字暗号を実現する。"S-Boxから数字を取り出して演算する"というのが、暗号のアルゴリズム記述に有るところのガロア体上の逆元を求めるとかなにかすごそうな演算に直結している。
S-BoxのSはSubstitutionのS。つまり、暗号の単純な実装では、S-Boxの参照は配列の参照になる。
OpenSSLだと、この表は

のようになっている。表は本来64要素の4bit表x8だが、実装の都合で32bit wordになっている。本来の表はFIPSにある。

PRIMITIVE FUNCTIONS FOR THE DATA ENCRYPTION ALGORITHMのS1からS8。
論理ゲートに置き換えるというのは要するに、ANDとかORとかXORのような、CPUがサポートしている論理演算だけをつかって、これら8つのS-Boxを表現するという仕事になる。
表現したものはこれ。

ランダムな対応であっても、無理やり関連性を見出すことは不可能な仕事ではない。

NOT取ってANDしてOR、要するに、最初の数ビットは単純なマルチプレクサで構築すれば良いということになる。イメージとしては、表の数を増やしてbit数を減らすこと。

AESやCamellia、DESは静的なS-Boxを用いるが、BlowfishやRC4のように鍵によってS-Boxが変化する暗号もある。Blowfishは円周率を基にしたオリジナルのS-boxを鍵によって変形して用いる。このような動的なS-Boxを持つ暗号は鍵によって弱い暗号になることがあり、特にRC4とWEPの組み合わせが有名。
逆に、このようなbit-slicingによるS-Box実現を前提に設計されたSerpent(AESファイナリストの一)のような暗号も有る。
bit-slicingによる実装効率は今後重要になる可能性が有る。例えば

では、AESやCamelliaについて以下を報告している

  • 通常の実装ではAESの方がCamelliaよりも早い(AESの方がアルゴリズムの並列度が高いため)
  • bit-slice実装ではCamelliaの方が早い(S-Boxの要素が少ないため)
  • Core2以降のプロセッサではbit-slice実装の方が通常の実装よりも早い(Athlon64とかPen4の世代では通常実装の方が倍早かった)

検索/正規表現

非常に単純な応用例はParabixのやっているように、single-byteの検索。

ある処理を行うと、'<'の文字が有るところだけビットが立つ　　　というのを色々と生成しておいて1 byteの検索に使う(たとえば'\0'の検索なら、bit stream8本すべてのORを取ってNOTする)。この手のCPUにはbit scan操作が有るので、"あるビットが立っている最初の位置"は1命令で求めることが出来る。
上のPDFでは正規表現に関しても扱っている。つまり、キャラクタクラスに応じてbitが立つ演算(!) - 例えばASCII数字であれば1が立つ演算をあらかじめ生成しておいて、マッチした文字の位置を表すbit streamを作る。
連続した1の終端を求めるのにはADDやSUBのような演算が使えるが、そのような演算の有効範囲は長くても当該CPUの演算長に制限されるので、はじっこの特別な処理がどうしても必要になる。
より複雑な応用例も多分探せばある。例えば、

では編集距離の導出を行っている(これもbitwiseアルゴリズムでありながら、スカラ加算も利用している)。

bit-slicingが苦手なこと

  • (通常の数での)加算や乗算など算術演算

これは非常にあたりまえだけれど、重要なポイント。
まず、プロトコル/アルゴリズム中に本当に加算が入っている場合はbit-slicingではなく普通のSIMDを使うべき。例えばMD5とかTCPチェックサムのような演算。MD5のような関数と、暗号化アルゴリズムは多くの人にとっておなじ箱に入っていると思われるが、加算の有無はbit-slice化においては非常に大きなインパクトを持つ。
bit-slicing中における加減算の正しい意味は、連続したbitに対する処理ということになる。これは、編集距離や正規表現の例で見られるように"物理的に隣接した要素への処理"に使える。加算器みたいな名前はやめて、ビット伝播器とでも改称しよう。
乗算も同様。素直にSIMDを使う。乗算はbit-shiftとADDの合成として使うことができるが、積極的な活用がなかなか思いつかない。
また、通常の算術演算に持って行く命令は大概C言語の枠で記述できない。例えばpopcntとかbit-scanの類。

  • 表引き

散々暗号化のところで表引きを紹介しておいても表引きはbit-slicingにとって敵であり続ける。
例えばblowfishのように動的なS-Boxを持つ暗号や、圧縮アルゴリズムの類はbit-slicingによる実装が難しい。静的なS-Boxであっても非常に規模が大きい場合は意味が無くなる。
なんとかツリーのようなデータ構造も難しいが、これに関しては何か逃げ方が有るような気がするので今必死に考えている。