代数消しゴム

Algebraic Eraser ( AE ) ^{[注 1]}は、それぞれが AE 公開鍵と秘密鍵のペアを持つ 2 つのパーティが、安全でないチャネルを介して共有秘密を確立できるようにする匿名鍵合意プロトコルです。^[1]この共有秘密は、鍵として直接使用することも、対称鍵暗号を使用して後続の通信を暗号化するために使用できる別の鍵を導出することもできます。 Algebraic Eraser は、Iris Anshel、Michael Anshel、 Dorian Goldfeld、Stephane Lemieuxによって開発されました。 SecureRF はプロトコル^{[2]をカバーする}特許を所有しており、無線周波数識別デバイスとワイヤレスセンサーネットワークを保護するための標準である ISO/IEC 29167-20 ^[3]の一部としてプロトコルを標準化しようとしましたが、失敗しました (2019 年 7 月現在) 。

キーセットパラメータ

2 つの当事者がキーを確立する前に、まずキーセットパラメータと呼ばれる一連のパラメータについて合意する必要があります。これらのパラメータは次のもので構成されます。

$N$ 、編み込みのストランド数、
$q$ 、有限体の大きさ、 $\mathbb {F} _{q}$
$M_{*}$ 、初期のNxNシード行列、 $\mathbb {F} _{q}$
$\mathrm {T}$ 有限体上の要素の集合（T値とも呼ばれる）、および $N$ $\mathbb {F} _{q}$
$A,B$ 互いに可換となるように設計された編組群内の共役集合。

E乗算

代数消しゴムの基本的な操作は、E 乗算と呼ばれる一方向関数です。行列、順列、編組群の Artin 生成子、および T 値が与えられた場合、生成子を色付き Burau 行列と編組順列に変換し、順列と T 値を適用してから、行列と順列を乗算することで、E 乗算を適用します。E 乗算の出力は、それ自体が行列と順列のペアです。 $\beta$ $(CB(\beta ),\sigma _{\beta })$ $(M',\sigma ')=(M,\sigma _{0})*(CB(\beta ),\sigma _{\beta })$

鍵確立プロトコル

次の例は、キーの確立方法を示しています。AliceがBobと共有キーを確立したいが、利用可能な唯一のチャネルが第三者によって盗聴される可能性があるとします。最初に、Alice と Bob は、使用するキーセットパラメータについて合意する必要があります。

各当事者は、キーセットから派生したキーペアを持っている必要があります。キーペアは、秘密キー (たとえば、アリスの場合) で構成されます。ここで、はシードマトリックスのランダムに選択された多項式であり、ブレイドはキーセットパラメーター (アリスの場合は A、ボブの場合は B、ただし (アリスの場合) ) からランダムに選択された共役と逆のセットです。 $(m_{A},\mathrm {B} _{a})$ $m_{A}$ $m_{A}=\sum _{i=0}^{N-1}{a_{i}M_{*}^{i}}$ $\mathrm {B} _{a}=\prod _{i=1}^{k}A_{i}^{\pm 1}$

アリスとボブは、秘密鍵情報からそれぞれ公開鍵とを計算します。ここで、例えば、これは秘密行列の E 乗算と秘密編組との恒等順列の結果です。 $(Pub_{A},\sigma _{a})$ $(Pub_{B},\sigma _{b})$ $(Pub_{A},\sigma _{a})=(m_{A},id)*b_{a}$

プロトコルを実行する前に、各当事者は相手方の公開鍵を知っている必要があります。

共有秘密を計算するために、アリスはを計算し、ボブはを計算します。共有秘密は行列/順列のペアであり、と等しくなります。共役集合とが交換可能になるように選択され、アリスとボブの両方が同じシード行列と T 値を使用するため、共有秘密は等しくなります。 $(S_{ab},\sigma _{ab})=(m_{A}Pub_{B},\sigma _{b})*\mathrm {B} _{a}$ $(S_{ba},\sigma _{ba})=(m_{B}Pub_{A},\sigma _{a})*\mathrm {B} _{b}$ $(S_{ab},\sigma _{ab})$ $(S_{ba},\sigma _{ba})$ $A$ $B$ $M_{*}$ $\mathrm {T}$

アリスが最初に公開する秘密鍵に関する情報は、公開鍵のみです。したがって、編組群同時共役分離探索問題を解決できない限り、アリス以外の当事者はアリスの秘密鍵を特定できません。ボブの秘密鍵も同様に安全です。アリスまたはボブ以外の当事者は、ディフィー・ヘルマン問題を解決できない限り、共有秘密を計算できません。

公開鍵は、静的（証明書などによって信頼されている）か、一時的のいずれかです。一時的鍵は一時的なもので、必ずしも認証されているわけではありません。そのため、認証が必要な場合は、他の手段で真正性の保証を得る必要があります。認証は、中間者攻撃を回避するために必要です。アリスまたはボブの公開鍵の 1 つが静的であれば、中間者攻撃は阻止されます。静的公開鍵は、高度なセキュリティ特性の中でも、前方秘匿性や鍵侵害のなりすまし耐性を提供しません。静的秘密鍵の保持者は、もう一方の公開鍵を検証し、静的秘密鍵に関する情報の漏洩を回避するために、生の Diffie-Hellman 共有秘密に安全な鍵導出関数を適用する必要があります。

安全

AEの安全性は、編組群内の一般化同時共役探索問題（GSCSP） ^{[4]に基づいています。これは、}編組群暗号と呼ばれるものにおける中心的な難問である共役探索問題（CSP）とは異なる明確な難問です。^[5] CSPが均一に破られたとしても（現在までに行われたことはありませんが）、それがどのようにしてGSCSPの破りを容易にするかはわかっていません。

既知の攻撃

Kalka、 Teicher、Tsabanによる最初の攻撃は、またはがランダムに選択された場合の弱い鍵のクラスを示しています。 ^[6] Algebraic Eraserの著者は、攻撃を受けにくいパラメータを選択する方法に関するプレプリントを発表しました。^[7] Ben-Zvi、Blackburn、Tsabanは最初の攻撃を改良し、著者によると、公開されているセキュリティパラメータ（128ビットのセキュリティを提供すると主張）を8CPU時間未満、64MB未満のメモリで破ることができるとのことです。^[8] Anshel、Atkins、Goldfeldは2016年1月にこの攻撃に対応しました。^[9] $M_{*}$ $m_{A}$

プレプリントとして発表されたMyasnikovとUshakovによる2番目の攻撃では、短すぎる共役編組で選択された共役は分離され、システムが破壊される可能性があることを示しています。^[10] この攻撃はGunnellsによって反駁され、適切なサイズの共役編組は分離できないことが示されました。^[4]

2016年、サイモン・R・ブラックバーンとマシュー・JB・ロブショーは、 2016年1月のISO/IEC 29167-20無線プロトコル草案に対する一連の実用的な攻撃を公開した。これには、わずかな時間とメモリでターゲットタグを偽装することや、249の^時間と^248のメモリを必要とする完全な秘密鍵の回復などが含まれていた。^{[11]アトキンスとゴールドフェルドは、ドラフトプロトコルに}ハッシュまたはメッセージ認証コードを追加することで、これらの攻撃を阻止できると反論した。^[12]

参照

注記

^ カラー Burau 鍵共有プロトコル( CBKAP )、Anshel–Anshel–Goldfeld–Lemieux 鍵共有プロトコル、Algebraic Eraser 鍵共有プロトコル( AEKAP )、Algebraic Eraser Diffie–Hellman ( AEDH )とも呼ばれます。

参考文献

^ Anshel, I.; Anshel, M.; Goldfeld, D .; Lemieux, S. (2006). 「鍵合意、代数的消去法、軽量暗号化」(PDF)。暗号化における代数的手法。第 418 巻。現代数学: アメリカ数学会。pp. 1–34。ISBN 978-0-8218-4037-5。
^ Goodin, Dan (2015 年 11 月 17 日)。「Algebraic Eraser がこれまで聞いたことのない最も危険な暗号システムである理由」Ars Technica。
^ ISO/IEC AWI 29167-20 – 情報技術 – 自動識別およびデータキャプチャ技術 – パート20：無線インターフェース通信用の暗号スイートAlgebraic Eraserセキュリティサービス。作業草案。
^ ab Gunnells, PE (2011). 「一般化同時共役探索問題の暗号解析と代数的消去法のセキュリティについて」arXiv : 1105.1141 [cs.CR].
^ Dehornoy, Patrick (2004). 「Braid-based cryptography」.群論、統計、および暗号化. Contemporary Mathematics. Vol. 360. American Mathematical Society. pp. 5–33. CiteSeerX 10.1.1.10.1759 . doi :10.1090/conm/360/06566. ISBN 9780821834442MR 2105432 。
^ Kalka A, Teicher M , Tsaban B (2012). 「Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser」. Advances in Applied Mathematics . 49 (1): 57–76. arXiv : 0804.0629 . Bibcode :2008arXiv0804.0629K. doi :10.1016/j.aam.2012.03.001. S2CID 10040122.
^ Goldfield, D. ; Gunnels, PE (2012). 「Algebraic Eraser に対する Kalka-Teicher-Tsaban 線形代数攻撃の無効化」. arXiv : 1202.0598 [cs.CR].
^ Ben-Zvi, A, Blackburn, Simon R, Tsaban B (2016). 「代数的消しゴムの実用的な暗号解析」。暗号学の進歩 - CRYPTO 2016。コンピュータサイエンスの講義ノート。 Vol. 9814。 Springer。 pp. 179–189。arXiv : 1511.03870。CiteSeerX 10.1.1.738.4755。doi :10.1007/978-3-662-53018-4_7。ISBN 978-3-662-53018-4. S2CID 1277023。
^ Anshel, I.; Atkins, D .; Goldfeld, D.; Gunnels, PE (2016). 「Ben-Zvi、Blackburn、および Tsaban による Algebraic Eraser への攻撃の阻止」. arXiv : 1601.04780 [cs.CR].
^ Myasnikov AD、Ushakov A (2008)。「Anshel-Anshel-Goldfeld-Lemieux鍵合意プロトコルの暗号解析」。arXiv : 0801.4786 [ math.GR]。
^ Blackburn, Simon R.; Robshaw, MJB (2016). 「代数消去タグ認証プロトコルのセキュリティについて」(PDF) .応用暗号とネットワークセキュリティ.コンピュータサイエンスの講義ノート。第9696巻。pp. 3–17。arXiv : 1602.00860。doi : 10.1007 / 978-3-319-39555-5_1。ISBN 978-3-319-39554-8. S2CID 371335。
^ Derek Atkins ; Dorian Goldfeld (2016-02-25). 「代数消去型ディフィー・ヘルマン無線プロトコルへの対応」Cryptology ePrint Archive . IACR.

外部リンク

SecureRFホームページ

[1] カラー Burau 鍵共有プロトコル( CBKAP )、Anshel–Anshel–Goldfeld–Lemieux 鍵共有プロトコル、Algebraic Eraser 鍵共有プロトコル( AEKAP )、Algebraic Eraser Diffie–Hellman ( AEDH )とも呼ばれます。

[2] Anshel, I.; Anshel, M.; Goldfeld, D .; Lemieux, S. (2006). 「鍵合意、代数的消去法、軽量暗号化」(PDF)。暗号化における代数的手法。第 418 巻。現代数学: アメリカ数学会。pp. 1–34。ISBN 978-0-8218-4037-5。

[arstechnica-3] Goodin, Dan (2015 年 11 月 17 日)。「Algebraic Eraser がこれまで聞いたことのない最も危険な暗号システムである理由」Ars Technica。

[4] ISO/IEC AWI 29167-20 – 情報技術 – 自動識別およびデータキャプチャ技術 – パート20：無線インターフェース通信用の暗号スイートAlgebraic Eraserセキュリティサービス。作業草案。

[gscsp-5] Gunnells, PE (2011). 「一般化同時共役探索問題の暗号解析と代数的消去法のセキュリティについて」arXiv : 1105.1141 [cs.CR].

[6] Dehornoy, Patrick (2004). 「Braid-based cryptography」.群論、統計、および暗号化. Contemporary Mathematics. Vol. 360. American Mathematical Society. pp. 5–33. CiteSeerX 10.1.1.10.1759 . doi :10.1090/conm/360/06566. ISBN 9780821834442MR 2105432 。

[7] Kalka A, Teicher M , Tsaban B (2012). 「Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser」. Advances in Applied Mathematics . 49 (1): 57–76. arXiv : 0804.0629 . Bibcode :2008arXiv0804.0629K. doi :10.1016/j.aam.2012.03.001. S2CID 10040122.

[8] Goldfield, D. ; Gunnels, PE (2012). 「Algebraic Eraser に対する Kalka-Teicher-Tsaban 線形代数攻撃の無効化」. arXiv : 1202.0598 [cs.CR].

[9] Ben-Zvi, A, Blackburn, Simon R, Tsaban B (2016). 「代数的消しゴムの実用的な暗号解析」。暗号学の進歩 - CRYPTO 2016。コンピュータサイエンスの講義ノート。 Vol. 9814。 Springer。 pp. 179–189。arXiv : 1511.03870。CiteSeerX 10.1.1.738.4755。doi :10.1007/978-3-662-53018-4_7。ISBN 978-3-662-53018-4. S2CID 1277023。

[10] Anshel, I.; Atkins, D .; Goldfeld, D.; Gunnels, PE (2016). 「Ben-Zvi、Blackburn、および Tsaban による Algebraic Eraser への攻撃の阻止」. arXiv : 1601.04780 [cs.CR].

[11] Myasnikov AD、Ushakov A (2008)。「Anshel-Anshel-Goldfeld-Lemieux鍵合意プロトコルの暗号解析」。arXiv : 0801.4786 [ math.GR]。

[12] Blackburn, Simon R.; Robshaw, MJB (2016). 「代数消去タグ認証プロトコルのセキュリティについて」(PDF) .応用暗号とネットワークセキュリティ.コンピュータサイエンスの講義ノート。第9696巻。pp. 3–17。arXiv : 1602.00860。doi : 10.1007 / 978-3-319-39555-5_1。ISBN 978-3-319-39554-8. S2CID 371335。

[13] Derek Atkins ; Dorian Goldfeld (2016-02-25). 「代数消去型ディフィー・ヘルマン無線プロトコルへの対応」Cryptology ePrint Archive . IACR.