代數橡皮擦密鑰交換的狀態？
Algebraic Eraser™ 是一種相對較新的非對稱密鑰協商協議（也稱為 Colored Burau密鑰協商協議），它基於編織組中的同時共軛搜尋問題。
最初的論述是：Iris Anshel、Michael Anshel、Dorian Goldfeld、Stephane Lemieux、Key agreement、Algebraic Eraser™ 和輕量級密碼學，在當代數學 418 (2006)中（稍後免費 pdf）。有兩個早期的並發攻擊：
- Arkadius Kalka、Mina Teicher、Boaz Tsaban，*作為產品的排列的短表達式和代數橡皮擦的密碼分析，*應用數學進展第 49 卷，第 1 期（2012 年 7 月）；arXiv:0804.0629（2008 年 4 月 - 2012 年 3 月；由 Kalka 和 Tsaban 在 2008 年 1 月 13 日 Bar-Ilan 大學的 CGC 研討會上首次提出）上的免費可能更早的 pdf 。 選擇某個固定矩陣的不同建議方法回答了這個問題：Dorian Goldfeld、Paul E. Gunnells，在arXiv:1202.0598（2012 年 2 月）中擊敗 Kalka-Teicher-Tsaban 線性代數攻擊對代數橡皮擦。
- Alex D. Myasnikov、Alexander Ushakov，Anshel-Anshel-Goldfeld-Lemieux 密鑰協議協議的密碼分析，在 Groups-Complexity-Cryptology 第 1 卷第 1 期（2009 年）中，預出版為arXiv:0801.4786（2008 年 1 月 30 日）。
對該攻擊的反駁是：Paul E. Gunnells，關於廣義同時共軛搜尋問題的密碼分析和代數橡皮擦的安全性，arXiv:1105.1141（2011 年 5 月）。
這是最近的一篇介紹性論文：Derek Atkins，Algebraic Eraser™：一種輕量級、高效的非對稱密鑰協議協議，用於無功耗、低功耗和物聯網設備，在2015 年輕量級密碼學研討會上被接受，由 Paul E.岡內爾。
Algebraic Eraser™ 已被提議作為ISO/IEC 29167-20（目前是批准的工作項目）進行標準化。該公司顯然申請標準化並持有一些相關專利，提供了一份描述為標準提案（2015 年 10 月）的描述，以及其他幾份技術論文。
最近有一個聲稱的攻擊，改進了 Kalka-Teicher-Tsaban 攻擊：Adi Ben-Zvi、Simon R. Blackburn、Boaz Tsaban，A Practical Cryptanalysis of the Algebraic Eraser，arXiv:1511.03870和eprint（2015 年 11 月 12 日） ; 根據這篇Ars Technica 文章，還有一些關於它的爭議。上述公司對此次攻擊進行了初步分析. 他們承認它適用於為標準化而提議的兩個配置文件之一，並恢復共享密鑰（但不是私鑰；因此我的理解是，攻擊“僅”損害了過去記錄會話的機密性，或目前會話，如果它可以被凍結足夠長的時間來進行攻擊）。
免責聲明：我沒有深入研究上述參考資料。
我在問密碼系統的狀態。尤其是：
- 5 個挑戰聲稱的安全級別是多少（有 $ q = 256 $ 和 $ n = 16 $ )在最近的攻擊中解決了嗎？
- 攻擊是否適用於 2015 年 10 月描述中規範性附錄 C.1 中的 B10F256 鍵集參數？據說
使用具有 10 股的編織層和 256 (2 8 )的區域提供 2 80的安全級別
- 生成這些 Keyset 參數的方法是公開的嗎？它們似乎包括矩陣 $ m\in GL(n,\mathbb F) $ 哪個謹慎的選擇被認為對於擊敗 Kalka-Teicher-Tsaban 攻擊至關重要，我在Atkins 介紹性論文的第 7 節中讀到這些是$$ emphasis mine $$
通過專有方法選擇
- 鑑於根據第 2 節的描述，它與另一個配置文件的區別僅在於將公鑰作為證書的一部分獲得，怎麼可能只有第二個配置文件受到影響？$$ emphasis mine $$
輪廓
$$ ii $$（標籤上的證書）：
詢問器首先獲得標籤的證書 (CERT_t)。標籤將其包含其公鑰 (PUB_t) 的證書發送給詢問器。詢問器從 CERT_t 獲得 PUB_t。然後協議遵循 Profile$$ i $$. 該協議允許通過標籤的固定 CERT_t 跟踪標籤。
- 2015 年 10 月的描述與 2014 年提出的標準化建議之間是否存在顯著差異？
這個部分自我回答的第一部分使用了我從最近攻擊的作者之一Simon R. Blackburn 教授那裡收到的附加資訊。
用於生成參數的方法不是公開的，例如對於矩陣 $ m\in GL(n,\mathbb F) $ 這種謹慎的選擇被認為對於擊敗早期版本的攻擊至關重要。因此，新攻擊的作者要求支持 Algebraic Eraser 密鑰交換標準化的公司提供“在實踐中提出的樣本參數”；那是在2015 年 10 月的標準提案公開之前，該提案本身早於攻擊的發布。
在對攻擊的初步分析中，指出攻擊的作者“可能已經辨識出一組薄弱的參數和密鑰”。據稱，這個弱集是由發表聲明的公司提供的。
此前有人聲稱，參數與 $ q=256 $ 和 $ n=16 $ ，在作為挑戰提供的參數集中使用（全部由單個 CPU 和未優化的程式碼在 8 小時內解決），相當於 128 位安全性（NIST 2015 年輕量級密碼學研討會上展示的幻燈片的第 13 頁）。
Simon R. Blackburn 教授沒有立即看到為什麼攻擊不適用於提議標準中的B10F256 密鑰集參數的原因（據我所知，該標準聲稱 80 位安全級別，對於 $ q=256 $ 和 $ n=10 $ ）。他希望一個好的實現中的詳細程式碼會有所不同，以利用較小的參數大小。
對於提議標準中profile的含義，我沒有發現任何支持在攻擊的初步分析中提出的“只有第二個profile受到（the）攻擊”的斷言。
現在，我不能相信提議標準中任何配置文件的安全性，因為：
- 該密碼系統在其支持者定義的實驗挑戰中失敗了，其安全級別推測遠高於為標準化提出的建議。
- 這是對先前中斷的修復，並宣布了另一個修復；因此該方法處於中斷和修復循環中，並且處於中斷狀態。
- 參數生成方式不公開；因此，不可能排除這種方法的知識將允許更好的攻擊。
PS：Ars Technica引用了支持 Algebraic Eraser 密鑰交換以實現標準化的公司的代表寫道：
很明顯，我們可能提供了用於內部測試的“弱參數”，並在要求時發送給研究人員（..）我們正在解決這個參數領域和我們批准安全參數的過程。但他的攻擊並沒有聲稱“破壞”了我們的方法或恢復了任何秘密材料。它聲稱能夠恢復計算的共享秘密。如果屬實，那麼像 RSA 和其他人一樣，我們將需要向我們的合作夥伴辨識這些弱參數並確保它們不被使用。
這種說法在學術上是站不住腳的：在密鑰交換協議中，“共享秘密”是“秘密材料”；恢復它就構成了休息。
在 Iris Anshel、Derek Atkins、Dorian Goldfeld 和 Paul E. Gunnells在Cryptology ePrint 檔案(2016-01-18)中擊敗 Ben-Zvi、Blackburn 和 Tsaban 對代數橡皮擦的攻擊後更新。
在這個反駁中，我發現了一個單一的論據來支持這樣的斷言，即攻擊不適用於為標準化而提議的第一個配置文件：
在其中一個配置文件中，一方可以訪問包含另一方的公鑰材料的數據庫。具體來說，在此配置文件中，攻擊者永遠無法訪問其中一個公鑰，因此無法發起攻擊以獲取共享密鑰。
來吧！公鑰中的九個字母中有六個致力於說明每個人，包括攻擊者，都知道該密鑰；這正是推動公鑰密碼學的假設。在相反的假設下，我們可以使用更簡單、更輕量級的密鑰協議。提議的標準本身將公鑰定義為：“可以公開的非對稱對的公共數據項”。
給出的另一個論點是：
在計算能力和記憶體有限的受限設備中，BBT 攻擊通常比 AEDH 協議的執行時間慢數千倍（在 4 GHz 處理器上）。ISO 29167-20 草案中的第二個配置文件是一種身份驗證協議，在該協議中，輕量級加密設置中的兩個使用者執行 AEDH 密鑰協商協議並獲得公開披露的共享機密以完成身份驗證。如果 BBT 攻擊在洩露和認證完成後恢復共享秘密，則沒有任何後果。因此，攻擊失敗，因為資訊不再相關。
甚至懷疑攻擊的持續時間是否充分保護了第二個配置文件（認證的公鑰可以從標籤中自由讀取）或第一個配置文件（否則相同），因為：
密鑰建立協議的一個常見用途是建立用於傳統密碼學的秘密會話密鑰，因此要考慮的攻擊時間範圍超出了身份驗證時間：只要知道任何加密數據仍然存在，密鑰仍然是目標對於攻擊者來說是可取的，並且至少在經過身份驗證的會話的整個持續時間內都是如此。
提議的標準沒有描述時間限制；並且在 RF 認證協議的典型實現中，很容易延長協議，從而為攻擊提供更多時間：
- 典型的 RF 閱讀器實施允許重試的通信協議（例如 ISO/IEC 14443-4），沒有規定的限制。
- 典型的射頻標籤不測量它們等待數據幀的時間，並允許在該時刻無限期暫停。即使閱讀器實施了時間限制，僅此一項就可能使標籤容易受到未經授權的寫入。
該攻擊目前尚未優化，並且使用的參數比為標準化提出的要大得多，因此完全有可能大大加快為標準化提出的參數變得實時（既不承認也不承認）否認該攻擊在實踐中對假設的 128 位安全級別提出的 5 個挑戰參數中的 5 個有效 $ N=16 $ , 當標準提出 $ N=10 $ ).
其他論點歸結為：攻擊做出了僅在大多數情況下成立的假設；我們可以選擇使這個假設無效的新參數，從而使攻擊變得不可能。我們正在研究細節；參數值 $ N $ “一定會比” $ 16 $ 攻擊，“但是通過應用與奇異的第一私有矩陣相關的合適的投影運算元，該方法在計算上是可行的”。
這試圖在2016 年 1 月凍結的其他答案之後概述更新。
Simon R. Blackburn 和 MJB Robshaw 進一步揭露了對擬議標準中的協議之一的批評，即關於代數橡皮標籤身份驗證協議的安全性；在密碼學 ePrint 存檔（2016-02-02，更新於 2016-06-02）中。
D. Atkins 和 D. Goldfeld 撰寫了解決代數橡皮擦 Diffie-Hellman 無線協議；在Cryptology ePrint Archive (2016-02-25) 中，回答了這個問題。他們
幾乎承認 2015 年 10 月的標準草案存在漏洞；
以匆忙出局為藉口（具體情況參見論文）；
將攻擊與對 Diffie-Hellman ECC 協議的無效橢圓曲線攻擊進行比較；
注意到這些攻擊嚴重依賴於在與冒充真正驗證者的流氓設備互動時恢復由經過身份驗證的標籤計算的共享秘密；
提出兩種可能的“對標籤身份驗證協議的直接更改”，以防止該共享秘密洩露：
- 散列它，並使用散列代替；
- 將其用作 MAC 的密鑰以進行身份驗證。
正如聲稱的那樣，這些對策是有道理的，並且令人信服地阻止了布萊克本和羅布肖的攻擊。但
- 這些都是重要的變化，
- 沒有降低安全性，
- 沒有對 Ben-Zvi、Blackburn 和 Tsaban 的襲擊提出任何索賠。
Adi Ben-Zvi、Simon R. Blackburn、Boaz Tsaban 的代數橡皮擦實用密碼分析；在Cryptology ePrint Archive中已更新 (2016-06-02)，並在 Crypto 2016 會議記錄中發布了一個版本。
到 2016 年底，SecureRF 推廣 IronwoodKAP（一種關鍵協議協議，被描述為 Algebraic Eraser™ 的衍生產品，使用 1 中的雜湊生成共享密鑰）；WalnutDSA（一種數字簽名算法）；和 Hickory Hash II（一種加密雜湊函式）；參見SecureRF 網站上的Iris Anshel、Derek Atkins、Dorian Goldfeld、Paul E. Gunnells：Post Quantum Group Theoretic Cryptography (2016-12-05) 。
到 2017 年 7 月，Ironwood 已成為一個家庭設備和多個其他設備之間的元密鑰協議和身份驗證協議。對單個 HD（或其相同副本）的限制是為了抵抗 Ben-Zvi、Blackburn 和 Tsaban 的攻擊，而不會增加密鑰大小或影響性能。該協議因此具有具有持久HD主密鑰和OD唯一持久多樣化密鑰的對稱密碼學的功能，用於HD和OD的相互認證，以及協商或每會話共享密鑰；加上聲稱的量子抗性，並聲稱不可能使用 HD 中的內容來模擬 OD。見身份證；Ironwood 元密鑰協議和身份驗證協議(2017-07)。