ローカルミキシングによるコード難読化

ダークモードトグル難読化 (パート III): ローカルミキシング 2026年8月21日 すべての投稿を見る 難読化 (パート III): ローカルミキシング Nicholas Ho、Ran Canetti、Janmajaya Mall によるフィードバックとレビューに特別感謝します。 このシリーズの過去2つのパートでは、暗号技術における難読化 (iO) プロトコルの2つの主要なファミリーを扱ってきました。一つは、標準的な暗号化の仮定からやや近いものから構築しようとする主流で保守的なラインですが、膨大なオーバーヘッドを犠牲にしています。もう一つは、より斬新な格子ベースの仮定を追加し、オーバーヘッドを大幅に削減しましたが、それでも実行するには十分ではありませんでした。この投稿では、現在取り組まれている3番目の主要なファミリーである「ローカルミキシング」について説明します。 ローカルミキシングについて最初に注意すべき点は、これが暗号化の全く異なる方法であるということです。楕円曲線も、素因数分解も、格子もここにはありません。実際、「通常の」暗号技術でここで行われていることに最も近いものは、対称暗号技術 — 暗号化とハッシュ関数の設計です。対称暗号化とハッシュ関数の設計では、「これを解読できれば、非常に大きな数を素早く素因数分解できる」といった、構造化された数学的問題へのクリーンな還元はありません。代わりに、人々が擬似乱数となる関数を作成しようとし、数学者がそれに攻撃を仕掛け、そして全体が安定するまで、そしてSHAやBLAKEのような安全なハッシュが得られるまで、設計上のトリックを見つけ出すという50年間の伝統があります。ローカルミキシングの目標は、その伝統を取り入れ、そのアイデアを回路に適用し、対称暗号技術者がそのコアビルディングブロックが必要とすることを学んだプロパティを達成すること — 機能性を維持しながらです。これはワイルドでリスクの高い賭けです。ホワイトボックス暗号化の失敗例の墓場にあります。ローカルミキシングの著者の希望は、この方向にもっと多くの努力を注ぎ、より賢く行い、ハッシュ関数が安定するのにかかった30年をAIを使って数年で加速し、同時に高いオーバーヘッドを受け入れることで、機能するものを作れるということです。 ローカルミキシングはどのように機能しますか？ ローカルミキシングの目標は、回路 C (XOR、AND、NOTなどの論理ゲートで構成される) を取り、その機能を維持しながら、内部ロジックを見る能力を徐々に除去する一連の変換を適用することです。 難読化パイプライン 左から右に6つの色のボックスが結合されています: 元の回路、可逆性の追加、強化、ガジェット化、ミキシング、難読化された回路。 元の回路 -> 可逆性の追加 -> 強化 -> ガジェット化 -> ミキシング -> Obf(C) 生成 ミキシング -> 分割と横断 -> ウォーク -> 最終圧縮 大まかに言うと、最も重要なアイデアは、まさに名前「ローカルミキシング」から推測できること、つまり、大量のジャンクゲートを追加し、すべてをシャッフルし、同じ機能を持つ異なるゲートセットで小さな部分を繰り返し置き換えることです。しかし、ご覧のとおり、それはパイプラインの1つのステップにすぎません — ミキシングステップです。巧妙さの大部分は、パイプラインの他のステップにあります — 回路をミキシングに適したものにするためのセットアップステップ、およびミキシングが完全に対処するのが難しい基盤となる回路の情報漏洩をいくつか除去するように最適化されたステップです。これらのステップを一つずつ見ていきましょう。ミキシングとサンドイッチの準備段階として必要な可逆性の追加から始めます。次に、ミキシングがどのように機能するかを説明します。その後、現在のミキシングの限界について話し、それを補うために追加された主要なヘルパーであるガジェット化について説明します。 可逆性の追加 例として、このシリーズの早い段階で見たことがあるかもしれない同じ回路、2ビット加算器を使用します。最初のステップは、回路 C を可逆回路に変換することです。これは、順方向と逆方向の両方に実行できる回路です。これを行う主な理由は、可逆回路がミキシングにより適しているためです。単一の可逆ゲートは、元のゲートと同じ機能を持つように合計される、任意の数の他の可逆ゲートで置き換えることができます。たとえば、ANDとORでこれを行うのははるかに困難です。その主な理由の1つは、非可逆計算がエントロピーを崩壊させることです: ANDは00、01、10を同じ出力に崩壊させ、ORも01、10、11と同様です。したがって、非可逆ゲートの長いチェーンは、デフォルトで回路の長さに比例して大量の情報を破壊します。十分に大きなランダムな可逆回路は、安全な暗号化置換である可能性が高く、十分に大きなランダムな非可逆回路は、数個の可能な出力しか持たないように退化します。このプロパティを持たない大きな非可逆回路を生成する方法はあります。たとえば、上記の2ビット加算器が a+b と b 自体を両方返し、a+b の x100 桁を返さないようにした場合 (加算がラップアラウンドになる)、それは非可逆ゲートで作られた可逆回路になります。各出力には、単一の有効な対応する入力があります。しかし、そのような技術は基本的に可逆回路を再発明することになり、直接可逆回路を基本媒体として使用する方が簡単です。 可逆回路を選択することは、対称暗号化からの古くからの知恵を反映しています。ハッシュ関数のような非可逆なアプリケーションでさえ、コアとなる基盤となるビルディングブロックは可逆な置換であり、非可逆性は、回路の完全な「状態空間」が実際に到達可能である限り、できるだけ長く確実に保つために、 precisamente 上の薄い層から来ています。 私たちの2ビット加算器の場合、それを可逆にする方法は次のようになります。 2ビット加算器は完全にr57ゲートから構築されています 14本の水平ワイヤ: 4つの入力ビット、1に固定されたワイヤ、0に固定されたワイヤ、およびゼロで始まる8つのアンシラワイヤ。16個のr57ゲートは、元の加算器の各ゲートごとに2つのゲートの8つの点線ボックスにグループ化されています。下3本のワイヤが3つの合計ビットを運びます。 XOR AND XOR OR AND XOR AND OR a [x1] a [x10] b [x1] b [x10] 1 0 0 0 0 0 0 0 0 0 a [x1] a [x10] b [x1] b [x10] 1 0 a₁∧b₁ a₁₀⊕b₁₀ a₁₀∨b₁₀ a₁₀∧b₁₀ c₁∧(a₁₀∨b₁₀) a+b [x1] a+b [x10] a+b [x100] ポジティブコントロール ネガティブコントロール アクティブピン ポジティブコントロールが1またはネガティブコントロールが0の場合、アクティブピンを反転させます。 点線ボックス = 元の加算器の1つのゲート、現在は2つのr57ゲート。 ここでいくつかの点に注意してください: 新しい回路は、「r57」ゲートの多くのコピーで構成されており、3つの入力と3つの出力があります。コアロジックは次のとおりです。ワイヤAが0でワイヤBが1である場合を除き、ワイヤCを反転させます。ワイヤAとBの出力は同じままです。各「標準」2入力1出力ゲートは、2つのr57ゲートで実装できます。 数学的に理解しやすいスタイルで回路を描画します。実行の各時点には明確に定義された「状態」があります — 回路を垂直に切断すると、それはその垂直線と交差する各ワイヤの値です。ゲートは左から右に順序付けられています。各ゲートには、それが作用する3つのワイヤの位置を表す3つの座標があります。回路は、そのうち1つが1、残りが0と期待される、たくさんの余分な「ジャンク」入力が必要です。これらのジャンク入力のうち2つ (最上位の0と1) は、r57ゲートを介して「標準」ゲートを構築するのに役立ちます。他のものは中間計算の結果を保持します。そして下部にあるものは、出力が書き込まれるスペースです。 これで、順方向と逆方向の両方に実行できる2ビット加算器が得られました — ある意味で。出力位置に101を、他の位置にゼロを入れて、ゲートを右から左に歩いても、入力位置に010 + 011、または100 + 001にはなりませんが、それは...