Salsa20

Salsa20是一種流加密演算法，由丹尼爾·J·伯恩斯坦提交到。它建立在基於add-rotate-xor。這使Salsa20具有了不同尋常的優勢，使用者可以在恆定時間內尋求輸出流中的任何位置。它可以在現代x86處理器中提供約每4–14次迴圈週期一位元組的速度，並具有合理的硬體效能。它沒有註冊專利，並且Bernstein還撰寫了幾篇對常見架構最佳化的公有領域實現。一個相關的密碼演算法ChaCha，具有類似的特點，但有不同的迴圈移位函式，已在2008年由伯恩斯坦釋出。結構.在其內部，該演算法採用模加⊕。只使用add-rotate-xor操作避免了軟體實現中計時攻擊的可能性。基本的Salsa20迴圈函式 codice_1是b ⊕= (a ⊞ c) «&lt; k;初始狀態是根據金鑰的8個word、流位置的2個word、nonce的兩個word和4個固定word製成。20輪迴圈混合製成16個word的流密碼輸出。一個quarter-round會使用四個word的輸入並製成四個word的輸出。內部的16-word狀態被佈置為一個4x4矩陣；偶數迴圈應用quarter-round操作到四行的每項，奇數迴圈應用quarter-round操作到四列的每項。連續兩輪迴圈被稱為double-round。更精確的規範已在下方呈現為虛擬碼，儘管這種行/列模式更難看出⊞是模加232，«&lt;是左旋操作，及⊕是異或。codice_2是codice_3的縮寫。x[ 4] ⊕= (x[ 0] ⊞ x[12])«&lt;7; x[ 9] ⊕= (x[ 5] ⊞ x[ 1])«&lt;7;x[14] ⊕= (x[10] ⊞ x[ 6])«&lt;7; x[ 3] ⊕= (x[15] ⊞ x[11])«&lt;7;x[ 8] ⊕= (x[ 4] ⊞ x[ 0])«&lt;9; x[13] ⊕= (x[ 9] ⊞ x[ 5])«&lt;9;x[ 2] ⊕= (x[14] ⊞ x[10])«&lt;9; x[ 7] ⊕= (x[ 3] ⊞ x[15])«&lt;9;x[12] ⊕= (x[ 8] ⊞ x[ 4])«&lt;13; x[ 1] ⊕= (x[13] ⊞ x[ 9])«&lt;13;x[ 6] ⊕= (x[ 2] ⊞ x[14])«&lt;13; x[11] ⊕= (x[ 7] ⊞ x[ 3])«&lt;13;x[ 0] ⊕= (x[12] ⊞ x[ 8])«&lt;18; x[ 5] ⊕= (x[ 1] ⊞ x[13])«&lt;18;x[10] ⊕= (x[ 6] ⊞ x[ 2])«&lt;18; x[15] ⊕= (x[11] ⊞ x[ 7])«&lt;18;x[ 1] ⊕= (x[ 0] ⊞ x[ 3])«&lt;7; x[ 6] ⊕= (x[ 5] ⊞ x[ 4])«&lt;7;x[11] ⊕= (x[10] ⊞ x[ 9])«&lt;7; x[12] ⊕= (x[15] ⊞ x[14])«&lt;7;x[ 2] ⊕= (x[ 1] ⊞ x[ 0])«&lt;9; x[ 7] ⊕= (x[ 6] ⊞ x[ 5])«&lt;9;x[ 8] ⊕= (x[11] ⊞ x[10])«&lt;9; x[13] ⊕= (x[12] ⊞ x[15])«&lt;9;x[ 3] ⊕= (x[ 2] ⊞ x[ 1])«&lt;13; x[ 4] ⊕= (x[ 7] ⊞ x[ 6])«&lt;13;x[ 9] ⊕= (x[ 8] ⊞ x[11])«&lt;13; x[14] ⊕= (x[13] ⊞ x[12])«&lt;13;x[ 0] ⊕= (x[ 3] ⊞ x[ 2])«&lt;18; x[ 5] ⊕= (x[ 4] ⊞ x[ 7])«&lt;18;x[10] ⊕= (x[ 9] ⊞ x[ 8])«&lt;18; x[15] ⊕= (x[14] ⊞ x[13])«&lt;18;Salsa20在其輸入上實行20輪混合，然後新增最終陣列到原數陣列來獲得64位元組輸出塊。但是，使用8輪和12輪的縮減迴圈的變體Salsa20/8和Salsa20/12也已分別被引入。這些變體被引入以補充原有的Salsa20，但不是取代它，甚至在eSTREAM的基準測量中比Salsa20表現更好[""]，儘管它相應有著較低的安全餘量。eSTREAM選用.Salsa20已被選擇作為eSTREAM專案“Profile 1”的第二階段，但最終沒有晉級到“Profile 2”的第三階段，因為eSTREAM覺得這對於極其資源受限的硬體環境可能不是一個好的候選。密碼分析.截至2015年，沒有已知的對Salsa20/12或完整Salsa20/20的攻擊被髮布；已知的最佳攻擊是打破12輪或20輪迴圈中的8輪。在2005年，Paul Crowley報告了一個對Salsa20/5的攻擊，預計時間複雜度2165，並贏得Bernstein的1000美金 “最有趣Salsa20密碼分析”獎勵。此次攻擊及所有後續的攻擊都是基於截斷差分分析。在2006年，Fischer、Meier、Berbain、Biasse和Robshaw報告了一個對Salsa20/6的攻擊，預計時間複雜度2177，以及一個對Salsa20/7的相關金鑰攻擊，預計時間複雜度2217。在2007年，Tsunoo 等人公佈了一個Salsa20的密碼分析，在2255次操作中，使用211.37對金鑰流，打破8/20輪來恢復256位的私鑰。但是，這種攻擊似乎沒有比蠻力攻擊更好。在2008年，Aumasson、Fischer、Khazaei、Meier和Rechberger報告了一個追對Salsa20/7的密碼分析攻擊，時間複雜度2153，並且他們報告了首個對Salsa20/8用預計時間複雜度2251的攻擊。此攻擊使用了對中性金鑰位進行截斷差分機率檢測的新概念。此攻擊可以打破使用128位金鑰的Salsa20/7。在2012年，Aumasson 等人的攻擊使Shi 等人將Salsa20/7。在2013年，Mouha和Preneel釋出了一則證明，敘述使用15輪迴圈的Salsa20在128位的安全差分分析。具體來說，它沒有比2−130更高機率的差分特徵，因此差分分析會比用盡128位金鑰更困難。ChaCha變種.在2008年，丹尼爾·J·伯恩斯坦釋出了一個密切相關的“ChaCha”密碼家族，其目的是增加每一輪的擴散以實現相同或稍微提升的效能。 Aumasson et al. paper也攻擊過ChaCha，實現了少一輪迴圈：256位ChaCha6有複雜性2139，ChaCha7有複雜性2248。128位ChaCha6在2107以內，但據稱攻擊128位的ChaCha7失敗。ChaCha替換了基本的Salsa20迴圈函式codice_1b ⊕= (a ⊞ c) «&lt; k;修改後的計算方法：b ⊞= c;a ⊕= b;a «&lt;= k;迴圈移位量也被更新。一個完整的quarter-round，codice_5變為：a ⊞= b; d ⊕= a; d «&lt;= 16;c ⊞= d; b ⊕= c; b «&lt;= 12;a ⊞= b; d ⊕= a; d «&lt;= 8;c ⊞= d; b ⊕= c; b «&lt;= 7;這除了使其在雙運算元指令集上更有效率，也使其在每次quarter-round中更新每個word兩次。在事實上，8輪的兩次迴圈允許一些最佳化。此外，輸入格式可以被重新佈置，以支援高效的SSE實現最佳化，這對Salsa20已被發現。相比逐行、逐列下移置換，還可以沿對角線進行。這樣ChaCha中的兩輪迴圈是：QR (0, 4, 8, 12)QR (1, 5, 9, 13)QR (2, 6, 10, 14)QR (3, 7, 11, 15)QR (0, 5, 10, 15)QR (1, 6, 11, 12)QR (2, 7, 8, 13)QR (3, 4, 9, 14)其中的數字是十六個32位state word。ChaCha20使用兩輪10次迭代。ChaCha是BLAKE雜湊演算法的基礎，NIST雜湊演算法競爭的一個入圍者，並且繼任者BLAKE2調整為更高的速度。它還定義了一個使用16個64位word的變種，具有相應調整的迴圈移位常數。ChaCha20.Google選擇了伯恩斯坦設計的，帶Poly1305訊息鑑別碼的ChaCha20與Google網站之間的通訊。不久之後，Google在TLS中採用它，ChaCha20-Poly1305演算法也以chacha20-poly1305@openssh.com成為OpenSSH中的一個新密碼套件。後來，透過編譯時選項避免它依賴於OpenSSL也成為可能。ChaCha20也被用在OpenBSD和NetBSD作業系統中的arc4random隨機數生成器，取代已經脆弱的RC4，在DragonFly BSD中核心的CSPRNG子程式中也是如此。ChaCha20已經在RFC 中標準化。它在IKE和IPsec中的使用已在RFC 中標準化。在RFC 中，ChaCha20-Poly1305已經被加入TLS擴充套件標準。若CPU或軟體不支援AES指令集，ChaCha20可提供比AES更好的效能。WireGuard協定使用了帶Poly1305訊息鑒別碼的ChaCha20。