ローカルミキシングによるコード難読化
Code Obfuscation via Local Mixing (vitalik.eth.limo)
要約
この記事は、暗号技術における難読化(iO)の第三の主要なアプローチである「ローカルミキシング」について解説しています。ローカルミキシングは、楕円曲線や素因数分解、格子などの数学的困難性に基づかず、対称暗号(暗号化、ハッシュ関数)の設計思想を回路に応用するアプローチです。回路の機能を維持しつつ、内部ロジックを隠蔽するために、ダミーゲートの追加、シャッフリング、機能的に等価なゲートセットへの置換といった変換を繰り返し適用します。この手法は、ホワイトボックス暗号化における過去の失敗例を踏まえつつ、AIを活用して設計プロセスを加速し、より高いオーバーヘッドを受け入れることで、実用的な難読化の実現を目指しています。
全文翻訳
Obfuscation (Part III): Local Mixing
ダークモードトグル
2026年8月21日 全投稿を見る
Obfuscation (Part III): Local Mixing
Special thanks to Nicholas Ho, Ran Canetti and Janmajaya Mall for feedback and review
このシリーズの過去2回(パート1とパート2)では、暗号学的難読化(iO)の主要な2つのファミリーについて説明しました。一つは、標準的な暗号学的仮定に近いものから構築しようとする主流で保守的なアプローチですが、膨大なオーバーヘッドを犠牲にします。もう一つは、より新しい格子ベースの仮定を追加し、オーバーヘッドを大幅に削減しましたが、それでも実用的には不十分でした。この記事では、現在取り組まれている3番目の主要なファミリーである「ローカルミキシング」について説明します。
[画像: ローカルミキシングの概念図]
ローカルミキシングについて最初に注目すべき点は、これは全く異なる暗号化の方法であるということです。楕円曲線も、素因数分解も、格子も一切使用しません。実際、「通常の」暗号技術でこれに最も近いのは対称暗号技術、つまり暗号化とハッシュ関数の設計です。
対称暗号化やハッシュ関数の設計では、「これを解読できれば、非常に大きな数の素因数分解が迅速にできることを意味する」といった、構造化された数学的問題へのクリーンな還元はありません。代わりに、擬似乱数的な関数を作成しようとする人々、それらを攻撃する数学者、そしてそれらの攻撃から保護するための設計上の工夫を見つけ出す人々との50年間の伝統があり、最終的にSHAやBLAKEのような安全なハッシュが確立されました。ローカルミキシングの目標は、その伝統を取り入れ、そのアイデアを回路に適用することです。対称暗号学者が、そのコアビルディングブロックが必要とすることを学んだプロパティを達成しつつ、機能性を維持することを目指します。
これは非常に大胆でリスクの高い賭けです。過去のホワイトボックス暗号の失敗例の墓場の上に成り立っています。ローカルミキシングの著者たちの希望は、この方向により多くの努力を注ぎ、より賢く取り組むことで、ハッシュ関数が安定化するのにかかった30年をAIを使って数年で短縮し、同時に高いオーバーヘッドを受け入れることで、機能するものを作れるということです。
ローカルミキシングはどのように機能するか?
ローカルミキシングの目標は、回路 (C)(論理ゲート、例えばXOR、AND、NOTで構成される)を取り、その機能性を維持しながら、内部ロジックを見る能力を徐々に排除する一連の変換を適用することです。
難読化パイプライン:左から右へ結合された6つの色のボックス:元の回路、可逆性の追加、ハードニング、ガジェット化、ミキシング、難読化された回路。
高レベルで見ると、最も重要なアイデアは、名前「ローカルミキシング」から推測できることと全く同じです。つまり、大量のジャンクゲートを追加し、すべてをシャッフルし、同じ機能を持つ異なるゲートセットで小さな部分の回路を繰り返し置き換えることです。
しかし、ご覧のように、それはパイプラインのミキシングステップにすぎません。巧妙さの大部分は、他のステップにあります。それは、回路をミキシングに適したものにし、ミキシングが完全に対処するのが難しい基盤となる回路の情報漏洩をいくつか排除するように最適化されたステップです。
これらのステップを一つずつ見ていきましょう。まず可逆性の追加から始めます。これはミキシングの準備段階として必要であり、その後にサンドイッチングを行います。次に、ミキシングがどのように機能するかを説明します。その後、現在のミキシングの限界について話し、それを補うために追加された主要なヘルパーであるガジェット化について説明します。
可逆性の追加
例として、このシリーズで以前にも見たことのある2ビット加算器の回路を使用します。
[画像: 2ビット加算器の回路図]
最初のステップは、回路 (C) を可逆回路に変換することです。これは、前後に実行できる回路です。
これを行う主な理由は、可逆回路がミキシングに対してはるかに友好的であるためです。単一の可逆ゲートは、元のゲートと同じ機能を持つように合計される、任意の数の他の可逆ゲートで置き換えることができます。例えば、ANDやORでこれを行うのははるかに困難です。
その主な理由は、非可逆計算はエントロピーを崩壊させるためです。ANDは00、01、10を同じ出力に崩壊させ、ORも同様です。したがって、非可逆ゲートの長い連鎖は、デフォルトで回路の長さに比例して大量の情報(エントロピー)を破壊します。十分に大きいランダムな可逆回路は、安全な暗号的置換である可能性が高いですが、十分に大きいランダムな非可逆回路は、数個の可能な出力しか持たない状態に退化します。
この特性を持たない大きな非可逆回路を生成する方法はあります。例えば、上記の2ビット加算器が (a+b) と (b) 自体の両方を返し、(a+b) の100の位を返さない(加算がラップアラウンドになる)ようにすると、非可逆ゲートで構成された可逆回路になります。各出力には、単一の有効な対応する入力が存在するためです。しかし、そのような技術は基本的に可逆回路を再発明することになり、直接可逆回路を基本媒体として使用する方が簡単です。
可逆回路を選択することは、対称暗号技術からの古くからの知恵を反映しています。ハッシュ関数のような非可逆なアプリケーションでさえ、コアとなる基盤となるビルディングブロックは可逆な置換であり、非可逆性はその上に薄い層として追加されます。これは、回路の「状態空間」全体が可能な限り長く実際に到達可能であることを保証するためです。
2ビット加算器の場合、それを可逆にするには次のようになります。
[画像: r57ゲートのみで構築された2ビット加算器。14本の水平ワイヤ、4つの入力ビット、1に固定されたワイヤ、0に固定されたワイヤ、および0から始まる8つのアンシラワイヤ。16個のr57ゲートが8つのドット付きボックスにグループ化されており、各ボックスは元の加算器のゲート1つに対応。一番下の3本のワイヤが3つの合計ビットを運びます。]
ここでいくつかの点に注意してください。
- 新しい回路は、「r57」ゲートの多くのコピーで構成されています。このゲートは3つの入力と3つの出力を持っています。コアロジックは次のとおりです。ワイヤAが0でワイヤBが1の場合を除き、ワイヤCを反転させます。ワイヤAとBの出力は同じままです。各「標準」2入力1出力ゲートは、2つのr57ゲートで実装できます。
- 回路は、数学的に推論しやすいスタイルで描画されます。実行の各時点には明確に定義された「状態」があります。回路を垂直に切断すると、その線が交差する各ワイヤの値が状態となります。ゲートは左から右へ順に配置されます。各ゲートには、それが作用する3つのワイヤの位置を表す3つの座標があります。
- 回路には、多くの追加の「ジャンク」入力が必要です。そのうち1つは1、残りは0であることが期待されます。これらのジャンク入力のうち2つ(一番上の0と1)は、「標準」ゲートをr57ゲートで構築するのに役立ちます。他のものは中間計算の結果を保持します。そして一番下のものは、出力が書き込まれるスペースです。
これで、前後に実行できる2ビット加算器が得られました。ただし、それは「 sort of 」です。出力位置に101を、他の位置にゼロを入れて、ゲートを右から左へ歩かせても、入力位置に010 + 011や100 + 001が得られるわけではなく、完全にジャンクな結果になります。元の計算を実際に逆方向に実行できるかどうかは、最終出力だけでなく、回路の中間ワイヤの最終値にも依存します。
このステップで得られた主な利点は、(C) と同じことを行うオブジェクトですが、ミキシングに自然に非常に適した形式であることです。
ハードニング
次のステップはハードニングです。可逆化ステップの出力、または「ネイティブに可逆な」回路である可逆回路 (C) を出発点として取ります。目標は、ゲートを操作することなく、回路を実行して (C) を何らかの入力で実行し、出力を得る以外のことは何もできないように変換することです。
この条件が侵害される方法は2つあります。
- 可逆化は(上記のように)ヘルパーワイヤ(しばしば「アンシラ」と呼ばれる)を作成することがよくありますが、これらはゼロである必要があります。アンシラが非ゼロに設定されていると、(C) の内部動作が任意の方法で漏洩するリスクがあります。
- (C) の可逆化されたバージョンは、逆方向に実行できます。実際にはこれを望んでいません。可逆回路を媒体として使用したいのですが、(C) が逆方向に実行されることは望んでいません。
これに対処する主な技術はハードened Toffoli(ハード化されたトフォリ)技術と呼ばれ、次のように機能します。
2つの新しいワイヤセットを追加します。
- 1つの追加のアンシラワイヤ (u o ext{delta}) と、そのヘルパー (u_1 ... u_j)。この構成は、(u o ext{delta}) の値について何も仮定しません。それは0または1として入ってきて、入ってきたのと同じ値で出ていきます。 (u_1 ... u_j) は任意の値を入力として受け取り、変更されずに残ります。
- 出力ワイヤ、出力がコピーされる新しいワイヤ (y_1 ... y_k)。ここでも、この構成はこれらのワイヤの内容について何も仮定しません。単に (C(inputs)) をこの位置にXORするだけなので、(y_1 ... y_k = X) として入ってきた場合、(y_1 ... y_k = X \oplus C(inputs)) として出てきます。
ゲートの見た目は次のとおりです。
- (C) を実行する
- (u o ext{delta} = 0) の場合、(y_1 ... y_k) に (C(inputs)) をXORする
- (C) を逆方向に実行し、すべてのヘルパーワイヤをクリアする
- ゼロである必要があるすべてのヘルパーワイヤがゼロであり(ゼロでない必要があるすべてのヘルパーワイヤが1である)、(u o ext{delta}) を反転させる。そうでない場合は、そのままにする。
- 上記の4つのステップを再度繰り返す
または、図で示すと次のようになります。
[画像: ハード化されたトフォリゲートの構造図]
通常のケースと、各「異常」ケースでの動作を歩いてみましょう。
- 通常のケース:
- (u o ext{delta}) は0または1として入ってきます。
- すべてのヘルパーワイヤが正しい値を持っている場合、中間で反転します。
- したがって、2つの (S') ブロックのいずれかで、(C(inputs)) が出力ワイヤにXORされます。もう一方では何も起こりません。
- 各 (S') ブロックでは、まず (C(inputs)) が計算され、次に(2回の実行のうちの1回で)出力ワイヤにXORされ、次に「非計算」されて、出力ワイヤ以外のすべてのワイヤが元の値に戻り、中間ブロックがそれらを忠実にチェックできるようになります。
- いずれかのヘルパーに不正な値がある場合:
- (u o ext{delta}) は中間で反転せず、したがって2回0または2回1になります。
- したがって、(C(inputs)) 、あるいはヘルパーワイヤが反転した (C(inputs)) のマンブルされた実行は、出力ワイヤにXORされることはありません。または2回XORされて、コピーが互いにキャンセルされます。
- 逆方向に実行した場合:
- 回路全体を逆方向に実行すると、順方向に実行した場合と全く同じ動作をします!
- 各 (S') ブロックは完全な回文です。
- 各 (T) ブロックはゲート配置において回文ではありませんが、順方向と逆方向で同じように動作するように設計されています。
- 逆方向に実行したときに2番目の (T) ブロックが (S') の前に実行されるという事実は問題ありません。なぜなら、それは単に (u o ext{delta}) を反転させるだけであり、これは最終的な結果を変更しないことがわかっています(単に発火する2つの (S') ブロックのどちらかを反転させるだけです)。
- 回路全体を逆方向に実行すると、順方向に実行した場合と全く同じ動作をします!
著者たちの2026年の研究には、サンドイッチングと呼ばれる別の方法が含まれています。サンドイッチングは、可逆化ステップがなく、ランダムな置換を直接難読化する(最も直接的なユースケースは公開鍵暗号の構築です)ユースケースに最適化されたハード化されたトフォリの一形態と考えることができます。
[画像: スライスされたサンドイッチにラップされたランダムな置換。28本のワイヤが2つの半分に分かれています。上の半分はランダムな置換Cとスライスゲートが交互に配置された自由入力xを運び、次に独立したランダムな回路Dとさらにスライスゲートが交互に配置されます。その間、14個のCNOTが上の半分をスライスレジスタにコピーし、それはゼロに固定されます。]
サンドイッチングは (\approx 2x) のオーバーヘッドを持ち、(\approx 4x) ではなく、追加の (u o ext{delta}) ワイヤを必要としません。それは (S') のようなステップを1回だけ実行します。ゼロに固定されたアンシラを持たないランダムな置換を操作することを意図しているため、入力上のゼロでないアンシラに対して防御する必要はありません。ただし、出力ワイヤ上のゼロでない入力に対しては防御しますが、それにはより単純なトリックを使用します。ランダムな「スライス」ゲートのセットは、これらのワイヤがゼロでない値で入ってきた場合、入力が完全にマンブルされることを保証します。「(C) を逆方向に計算する」ステップも、任意のランダムな回路 (D) に置き換えられます。
ミキシング
ミキシングは概念的に非常に理解しやすいです。それは、回路の小さな部分に繰り返し変換を加えることです。各変換は機能性を維持しながら、構造に関する可視情報の量を破壊します(あるいは、混乱と拡散させます)。数百万回の変換ラウンドの後、元の回路の各ゲートは、ミキシングステップを数百回経験することになります。
現在のコードでは、ミキシングはいくつかの技術の組み合わせによって行われます。それらを順に説明します。
生成ミキシング
生成ミキシングは次のように機能します。
- 同じ機能を持つすべての小さな回路の巨大なテーブルを作成します(注意:これには、互いに全く相互作用しないサブブロックのペアを含む「小さな回路」が必然的に含まれます)。
- 回路から、連続しているか、機能に干渉するゲートがないセットを繰り返し取得します。
- テーブルで、選択したゲートセットがどの「クラス」に属するかを確認し、同じクラスの別のランダムな小さな回路で置き換えます。
- 新しいサブ回路が、機能性が壊れるほど遠くに移動する前に、合法的な位置の範囲を決定します(例:入力がそれを最後に更新した出力ワイヤの前に移動する)。そのゲートをその範囲内のランダムな位置に移動させます。
- 繰り返す
ローカルミキシングリポジトリの作業の大部分は、この手順を最適化することにあります。テーブルの前でも同じ小さな回路を自動的に識別するためのいくつかのトリックを使用する正規化ステップ、次に多項式形式への変換、そしてすべてをスペース効率よく格納し、クエリを高速化するための「レインボーテーブル」メカニズムがあります。
生成ミキシングがどのように機能するかを示す簡単な図です(本番バージョンは〜7〜10ゲートのグループを取り、レインボーテーブルは数百ギガバイトですが、はるかに小さい「キュレーションされたテーブル」も利用可能です)。
[画像: 4ゲートウィンドウのレインボーテーブル置換。5つのレイヤー:生の4ゲート回路、正規化されたクラス、バケットにソートされた多項式状態、一致したバケットのレインボーテーブルエントリ、およびスプライスされた置換。選択されたパスは青色。同じクラスまたはバケットに収束する兄弟パスは青みがかった灰色。]
生成ミキシングは、パイプラインの中で最も強力なステップです。ウィンドウ内の値の表現方法を全体的に変更することができます。これにより、元の回路の任意の値 (x) が、難読化された回路の値の非線形関数のみによって表されるようになるまで到達するのに最も効果的なステップとなります。生成ミキシングはまた、元の計算グラフで離れた2つの部分を「接着」し、それらの2つの部分の組み合わせであるサブ回路を、それらをインターリーブするサブ回路で置き換えることができます。そして、さらに世代のミキシングによって、インターリーブを検出して逆転させるのが困難になります。
パイプラインは、回路の各ゲートが何度もカバーされることを目標に、大量の生成ミキシングラウンドを実行します。また、複数のフェーズで実行されます。1つは回路の拡張を優先し、もう1つはサイズを維持することを優先し、最後にはわずかに縮小します。
スプリッティング
スプリッティングは、r57ゲートを、より広範な1コントロールおよび2コントロールゲートのセットで置き換えます。ここには多くの技術があります。
((\oplus) はXOR、(\lor) はOR、(\land) はAND、(\neg) はNOTを意味します)
まず、(a\ {\oplus}{=}\ b \lor \neg c) を (a\ {\oplus}{=}\ b;\ a\ {\oplus}{=}\ \neg b \land \neg c) または (a\ {\oplus}{=}\ \neg c;\ a\ {\oplus}{=}\ b \land c) のいずれかで置き換えることができます。
[画像: r57ゲートの2つのスプリット。左は単一のr57ゲート、右はそれに対応する2つのゲート分解。]
次に、任意のワイヤについて、次のことができます。
- ワイヤが変更される2つの位置AとBを選択します。
- 位置AとBで、ワイヤを反転させます。ワイヤを変更するゲートを、そのワイヤが読み取られる状況の全く反対のセットでそのワイヤを変更するゲートに置き換えます。
- AとBの間で、ワイヤが読み取られるあらゆるケースでそのワイヤの役割を否定します。もしそれがポジティブコントロールだったなら、ネガティブコントロールにし、その逆も行います。
[画像: 単一ワイヤに沿った遠い結合。左はワイヤwが多くのゲートによって書き込まれ読み取られる8ワイヤ回路。右は、wをターゲットとする2つのブラケットゲートが否定され、その間のwを読み取るすべてのコントロールが反転されています。]
スプリッティングは、個々のワイヤとゲートの意味に関する可視情報の特定の種類を破壊するのに役立ちます。十分なラウンドの後、あるワイヤが「x」を表し、別のワイヤが「not-x」を表すことを区別するのは実用的ではなくなります。
使用されるゲートのセットを広げることで、スプリッティングは、次のステップを実装するために必要な条件も作成します。これにより、はるかに少ない制限でゲートの順序を入れ替えることができます。
クロッシングウォーク
互いに「衝突」しない2つのゲート(一方のゲートが他方が読み取る値を書き込むという意味で)は自由に並べ替えることができます。しかし、衝突する2つのゲートも並べ替えることができます。ただし、読み取りと書き込みの場所が入れ替わるのを補償するために新しいゲートを追加する必要があります。
これがどのように機能するかを3つのケースに分けて説明します。
[画像: 3つのクロッシングルール。各パネルは左に2ゲートの衝突、右にそれと等価な3ゲートの書き換えを示しています。]
原理的には、ゲートをどれだけ遠くにでも移動させることができ、「残渣」をそれが通過する各ゲートのために残すことができます。
このステップは、(k) コントロールを持つゲート(上記の図は (k = 2) を示していますが、(k \ge 3) もサポートされています)から、最大 (2k-1) コントロールを持つゲートを出力することに注意してください。
これはクロッシングウォーク自体にとっては深刻な問題ではありません。多くのラウンドの後、多くのコントロールを持つゲートが得られる可能性があるだけです。さらに、より高いコントロール数では、クロッシングごとに複数の「残渣」ゲートを作成する必要がある場合があります。
しかし、生成ミキシングの最中にクロッシングウォークを行うことにした場合、現在のレインボーテーブルにはr57ゲートしか含まれていないため、問題となります。より高いコントロール数を持つゲートを含むレインボーテーブルを作成することも可能ですが、これは同じレベルのカバレッジに対してレインボーテーブルのサイズが指数関数的に増加するリスクがあります。最も簡単な解決策は、3つ以上のコントロールを持つ各ゲートを、2コントロールゲートのシリーズに還元することです。
fcompress
このステップは、ワイヤが読み取られる前にワイヤを変更する一連のゲートを単純化します。
これは主に、さらなる隠蔽のためではなく、プログラムを縮小するために行われます。もしこれを行わなければ、攻撃者は自分でそれを行い、より小さなオブジェクトを扱うことができるようになるという議論があります。したがって、正当なユーザーにも同じ効率上の利点を与えるのが良いでしょう。
以下にいくつかの単純化を示します。
[画像: ゲートの単純化の例]