Salsa序列算法分析研究

劉鶯迎

（河南牧業經濟學院，鄭州 450001）

1 引言

Salsa20算法屬于序列密碼算法[1]。序列密碼，也稱流密碼，是密碼學的重要分支，它利用初始密鑰產生一條密鑰流序列，與明文簡單異或進行加密。Salsa20算法是歐洲著名密碼計劃eSTREAM[2]的入選算法。該計劃旨在征集軟件或者硬件性能優于AES的序列密碼算法。Salsa20算法[3]是由美國學者Daniel J.Bernstein提出的序列密碼算法。于2005年5月提交作為eSTREAM候選算法，同時提供了算法的速度，安全性分析以及設計原則介紹[4]。經過三輪的算法評估，最終Salsa20/12算法成功入選，它在軟件組中排名第二，另外它支持的密鑰長度為256比特或者是128比特（比較傾向于256比特）。

2 算法實現

Salsa20算法的基本處理單位為32比特字，最基本的函數為quarterround函數，采用的運算為模232的整數加法，異或和循環移位運算的復合，軟件處理速度非常快。Salsa20算法的核心是輸入輸出都是512比特的hash函數。這512比特輸入以32比特字為單位排成一個4階方陣，初始矩陣用密鑰，IV，nonce和常數值進行填充。填充后對該矩陣用quarterround函數交替進行10次列變換和10次行變換，得到的矩陣與原矩陣模232加輸出密鑰流序列。

3 算法混淆效果分析

通過以上對Salsa20算法結構的介紹以及實現過程，可以發現其混淆效果很好。這里通過模擬實驗構造所需輸入對分析一下Salsa20算法的混淆效果究竟如何。為說明Salsa20算法的混淆效果極佳，這里構造兩個輸入矩陣，它們只在一個字的一個比特上有差分。并在此基礎上分析這一個比特在不同位置上所發生的混淆效果有什么不同。通過模擬實驗結果發現，在Salsa20算法的16個字輸入差分當中，僅僅有一個字存在一個非零比特，就可以使得三輪輪函數作用后此非零比特擴散到16個字的所有比特。

在這里把一次運算后兩個狀態在同一個位置出現的不同比特記作“活躍比特”。以上只對輸入差分做了4輪Salsa20算法輪函數作用，混淆效果就已經如此巨大，接下來的16輪輪函數作用后還將有更多的活躍比特。

4 5輪Salsa20截斷差分攻擊

本節考慮的是Paul Crowley等簡化至5輪的Salsa20的截斷差分攻擊及其改進[5][6]，其主要思路是：先是對n輪差分進行反向分析，得到n-2輪差分特征，然后按一定方法對密鑰進行窮舉，以達到密鑰恢復的效果。

5 差分鏈的驗證與計算

對于任何算法，進行差分攻擊時最重要的一步就是尋找高概率差分鏈，這一步往往需要耗費很大的資源。根據ARX密碼的模加差分概率計算方法[7]，可以對各論文中出現的3輪差分鏈進行理論概率計算，然后進行大數據模擬實驗驗證差分鏈的輸入輸出正確性和差分概率正確性。

假設三輪差分鏈表示為以下形式：

6 結束語

本文對Salsa20算法進行了深入探究，主要工作包括對Salsa20算法結構的介紹與分析、對算法特性的分析，對Salsa20算法的Python語言編程實現、對5輪Salsa20算法的差分攻擊，以及對攻擊算法復雜度的分析，最后是對現有差分鏈的驗證和差分鏈概率的計算。

本文主要有以下幾個重點內容：第一點是在深入分析Salsa20算法的各組成函數以及對其擴展函數和加密函數的前提下，對其進行了Python語言的編程實現以及對其安全性進行了一定的分析。第二點是對Salsa20算法進行了5輪的截斷差分攻擊，包括對差分鏈選擇標準的判斷、在Paul Crowley提出的關于Salsa20算法差分攻擊的基礎上進行了改進和優化，并且提出了具體的分析算法，同時進行了算法的復雜度分析。第三點是對現有差分鏈進行了有效的驗證，并且對這些差分鏈進行了理論概率的計算，最后通過模擬實驗判斷了它們是否符合高概率的條件。