ソートアルゴリズムといえば、計算機科学で最も研究された分野の一つです。クイックソートやマージソートなど、速度を追求するアルゴリズムは数え切れないほどあります。でも、「ソートが情報を漏洩する」と言われたら、ちょっと意外に感じませんか。

実は、ポスト量子暗号のようなセキュリティクリティカルな分野では、ソートアルゴリズムの実行時間がデータに依存すること自体がセキュリティホールになり得ます。この問題を解決するのがブランチレスソーティングネットワークという手法で、最近その実装と性能に関する詳細な記事が話題になりました。

なぜソートが情報を漏洩するのか

クイックソートを例に考えてみましょう。ピボットの選択、パーティションの結果、再帰の深さ——これらはすべて配列の中身に依存します。異なる入力は異なる分岐パターン、異なるメモリアクセス、異なる実行時間を生み出すんですね。

攻撃者がこの実行時間の差を測定できれば（ネットワーク越しでも可能な場合があります）、ソートされているデータの情報を推測できてしまいます。これがタイミングサイドチャネル攻撃です。

この問題はクイックソートに限りません。マージソートのマージステップも比較で分岐しますし、挿入ソートの内部ループの長さもデータに依存します。制御フローがデータに依存するソートはすべて脆弱ということになります。

ソーティングネットワークとは

ソーティングネットワークは、比較と交換の操作を固定的な回路として配線したものです。各コンパレータは2つの値を受け取って、小さい方を一方のワイヤに、大きい方をもう一方のワイヤに出力します。

重要なのは、ネットワーク全体が構築時に決定されるという点です。データを見る前に、どのワイヤとどのワイヤを比較するかがすべて決まっています。つまり、攻撃者が実行を観察しても、入力に関係なくまったく同じ操作の列が見えるだけですね。

バブルソートは実はソーティングネットワーク

意外なことに、バブルソートはそれ自体がソーティングネットワークです。各パスで隣接するペアを左から右に比較していくパターンは、配列の値に関係なく常に同じです。固定スケジュールの比較交換操作、これはまさにソーティングネットワークの定義そのものですね。

ただし効率の面では問題があります。O(n²)のコンパレータが必要になるので、大きな配列には向きません。

奇偶転置ソートと並列化

バブルソートの自然な改良として、奇偶転置ソートがあります。奇数フェーズと偶数フェーズを交互に実行し、それぞれのフェーズ内では独立したペアの比較交換を並列に行えます。

SIMDやGPUを活用すると、この並列性を直接活かせるため、実用的なパフォーマンスが得られる場合があります。サイバーセキュリティの最新動向でもサイドチャネル攻撃への対策は重要なテーマになっています。

ブランチレス実装のポイント

ソーティングネットワークのコンパレータをブランチレスに実装することが重要です。条件分岐（if文）を使わず、条件付きムーブ命令（cmov）やビット演算で比較交換を行います。

具体的には、2つの値の最小値と最大値を分岐なしで計算する方法が使われます。コンパイラの最適化に頼ることもできますが、暗号用途では明示的にブランチレスなコードを書くのが安全です。

この分野はRustのようなシステムプログラミング言語との相性が良く、unsafe blockを使った低レベル最適化が可能です。

実用的な性能は？

驚くべきことに、適切に最適化されたソーティングネットワークは、小〜中規模の配列で従来のソートを上回ることがあります。固定的なメモリアクセスパターンが分岐予測ミスをゼロにし、SIMDとの組み合わせでさらに高速化できるためです。

特にClassic McElieceやNTRU Primeのようなポスト量子暗号では、ソートがコアのサブルーチンとして使われているため、ここでの性能改善は暗号全体のパフォーマンスに直結します。WebAssemblyのような実行環境でも、ブランチレスなコードは一定の実行時間を保ちやすいという利点があります。

まとめ

ブランチレスソーティングネットワークは、セキュリティとパフォーマンスを両立する興味深いアルゴリズムです。制御フローをデータから完全に独立させることで、タイミングサイドチャネル攻撃を根本から防ぎます。

ポスト量子暗号の実装に関わる方はもちろん、アルゴリズムに興味がある方にとっても、ソーティングネットワークの世界は掘り下げてみる価値があると感じました。詳しくは原文の記事がおすすめです。