linuxhash演算法

1. 密碼學系列之:bcrypt加密演算法詳解

簡介

今天要給大家介紹的一種加密演算法叫做bcrypt,bcrypt是由NielsProvos和DavidMazières設計的密碼哈希函數，他是基於Blowfish密碼而來的，並於1999年在USENIX上提出。

除了加鹽來抵禦rainbowtable攻擊之外，bcrypt的一個非常重要的特徵就是自適應性，可以保證加密的速度在一個特定的范圍內，即使計算機的運算能力非常高，可以通過增加迭代次數的方式，使得加密速度變慢，從而可以抵禦暴力搜索攻擊。

bcrypt函數是OpenBSD和其他系統包括一些Linux發行版（如SUSELinux）的默認密碼哈希演算法。

bcrypt的工作原理

我們先回顧一下Blowfish的加密原理。blowfish首先需要生成用於加密使用的K數組和S-box,blowfish在生成最終的K數組和S-box需要耗費一定的時間，每個新的密鑰都需要進行大概4KB文本的預處理，和其他分組密碼演算法相比，這個會很慢。但是一旦生成完畢，或者說密鑰不變的情況下，blowfish還是很快速的一種分組加密方法。

那麼慢有沒有好處呢？

當然有，因為對於一個正常應用來說，是不會經常更換密鑰的。所以預處理只會生成一次。在後面使用的時候就會很快了。

而對於惡意攻擊者來說，每次嘗試新的密鑰都需要進行漫長的預處理，所以對攻擊者來說要破解blowfish演算法是非常不劃算的。所以blowfish是可以抵禦字典攻擊的。

Provos和Mazières利用了這一點，並將其進一步發展。他們為Blowfish開發了一種新的密鑰設置演算法，將由此產生的密碼稱為"Eksblowfish"（"expensivekeyscheleBlowfish"）。這是對Blowfish的改進演算法，在bcrypt的初始密鑰設置中，salt和password都被用來設置子密鑰。然後經過一輪輪的標准Blowfish演算法，通過交替使用salt和password作為key，每一輪都依賴上一輪子密鑰的狀態。雖然從理論上來說，bcrypt演算法的強度並不比blowfish更好，但是因為在bcrpyt中重置key的輪數是可以配置的，所以可以通過增加輪數來更好的抵禦暴力攻擊。

bcrypt演算法實現

簡單點說bcrypt演算法就是對字元串OrpheanBeholderScryDoubt進行64次blowfish加密得到的結果。有朋友會問了，bcrypt不是用來對密碼進行加密的嗎？怎麼加密的是一個字元串？

別急，bcrpyt是將密碼作為對該字元串加密的因子，同樣也得到了加密的效果。我們看下bcrypt的基本演算法實現：

FunctionbcryptInput:cost:Number(4..31)log2(Iterations).e.g.12==>212=4,096iterationssalt:arrayofBytes(16bytes)randomsaltpassword:arrayofBytes(1..72bytes)UTF-8encodedpasswordOutput:hash:arrayofBytes(24bytes)////P:arrayof18subkeys(UInt32[18])//S:Foursubstitutionboxes(S-boxes),S0...S3.EachS-boxis1,024bytes(UInt32[256])P,S<-EksBlowfishSetup(cost,salt,password)//Repeatedlyencryptthetext"OrpheanBeholderScryDoubt"64timesctext<-"OrpheanBeholderScryDoubt"//24bytes==>three64-bitblocksrepeat(64)ctext<-EncryptECB(P,S,ctext)////24-(cost,salt,ctext)

上述函數bcrypt有3個輸入和1個輸出。

在輸入部分，cost表示的是輪循的次數，這個我們可以自己指定，輪循次數多加密就慢。

salt是加密用鹽，用來混淆密碼使用。

password就是我們要加密的密碼了。

最後的輸出是加密後的結果hash。

有了3個輸入，我們會調用EksBlowfishSetup函數去初始化18個subkeys和4個1K大小的S-boxes，從而達到最終的P和S。

然後使用P和S對"OrpheanBeholderScryDoubt"進行64次blowfish運算，最終得到結果。

接下來看下EksBlowfishSetup方法的演算法實現：

FunctionEksBlowfishSetupInput:password:arrayofBytes(1..72bytes)UTF-8encodedpasswordsalt:arrayofBytes(16bytes)randomsaltcost:Number(4..31)log2(Iterations).e.g.12==>212=4,096iterationsOutput:P:arrayofUInt32arrayof18per-roundsubkeysS1..S4:;eachSBoxis256UInt32(i.e.1024KB)//InitializeP(Subkeys),andS(Substitutionboxes)withthehexdigitsofpiP,S<-InitialState()//,S<-ExpandKey(P,S,salt,password)//Thisisthe"Expensive"partofthe"ExpensiveKeySetup".//.repeat(2cost)P,S<-ExpandKey(P,S,0,password)P,S<-ExpandKey(P,S,0,salt)returnP,S

代碼很簡單，EksBlowfishSetup接收上面我們的3個參數，返回最終的包含18個子key的P和4個1k大小的Sbox。

首先初始化，得到最初的P和S。

然後調用ExpandKey，傳入salt和password，生成第一輪的P和S。

然後循環2的cost方次，輪流使用password和salt作為參數去生成P和S，最後返回。

最後看一下ExpandKey的實現：

FunctionExpandKeyInput:password:arrayofBytes(1..72bytes)UTF-8encodedpasswordsalt:Byte[16]randomsaltP:..S4:UInt32[1024]Four1KBSBoxesOutput:P:arrayofUInt32Arrayof18per-roundsubkeysS1..S4:UInt32[1024]Four1KBSBoxes//<-1to18doPn<-Pnxorpassword[32(n-1)..32n-1]//treatthepasswordascyclic//Treatthe128-bitsaltastwo64-bithalves(theBlowfishblocksize).saltHalf[0]<-salt[0..63]//Lower64-bitsofsaltsaltHalf[1]<-salt[64..127]//Upper64-bitsofsalt//Initializean8-byte(64-bit)bufferwithallzeros.block<-0//MixinternalstateintoP-boxesforn<-1to9do//xor64-bitblockwitha64-bitsalthalfblock<-blockxorsaltHalf[(n-1)mod2]//[0],andsaltHalf[1]//<-Encrypt(P,S,block)P2n<-block[0..31]//lower32-bitsofblockP2n+1<-block[32..63]//upper32-bitsblock//-boxesofstatefori<-1to4doforn<-0to127doblock<-Encrypt(state,blockxorsalt[64(n-1)..64n-1])//asaboveSi[2n]<-block[0..31]//lower32-bitsSi[2n+1]<-block[32..63]//upper32-bitsreturnstate

ExpandKey主要用來生成P和S，演算法的生成比較復雜，大家感興趣的可以詳細研究一下。

bcrypthash的結構

我們可以使用bcrypt來加密密碼，最終以bcrypthash的形式保存到系統中，一個bcrypthash的格式如下：

$2b$[cost]$[22charactersalt][31characterhash]

比如：

$2a$10$\__//\____________________/\_____________________________/AlgCostSaltHash

上面例子中，$2a$表示的hash演算法的唯一標志。這里表示的是bcrypt演算法。

10表示的是代價因子，這里是2的10次方，也就是1024輪。

N9qo8uLOickgx2ZMRZoMye是16個位元組（128bits）的salt經過base64編碼得到的22長度的字元。

最後的是24個位元組（192bits）的hash，經過bash64的編碼得到的31長度的字元。

hash的歷史

這種hash格式是遵循的是OpenBSD密碼文件中存儲密碼時使用的MolarCryptFormat格式。最開始的時候格式定義是下面的：

$1$:MD5-basedcrypt('md5crypt')

$2$:Blowfish-basedcrypt('bcrypt')

$sha1$:SHA-1-basedcrypt('sha1crypt')

$5$:SHA-256-basedcrypt('sha256crypt')

$6$:SHA-512-basedcrypt('sha512crypt')

但是最初的規范沒有定義如何處理非ASCII字元，也沒有定義如何處理null終止符。修訂後的規范規定，在hash字元串時：

String必須是UTF-8編碼

必須包含null終止符

因為包含了這些改動，所以bcrypt的版本號被修改成了$2a$。

但是在2011年6月，因為PHP對bcypt的實現crypt_blowfish中的一個bug，他們建議系統管理員更新他們現有的密碼資料庫，用$2x$代替$2a$，以表明這些哈希值是壞的（需要使用舊的演算法）。他們還建議讓crypt_blowfish對新演算法生成的哈希值使用頭$2y$。當然這個改動只限於PHP的crypt_blowfish。

然後在2014年2月，在OpenBSD的bcrypt實現中也發現了一個bug，他們將字元串的長度存儲在無符號char中（即8位Byte）。如果密碼的長度超過255個字元，就會溢出來。

因為bcrypt是為OpenBSD創建的。所以當他們的庫中出現了一個bug時,他們決定將版本號升級到$2b$。

最通俗的解讀，最深刻的干貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！

歡迎關注我的公眾號:「程序那些事」,懂技術，更懂你！

2. Linux入門之sha256sum指令詳解

在Linux系統中，文件的完整性和數據的安全性是用戶和系統管理員非常關心的問題。為了驗證文件的完整性，Linux提供了一個強大的工具——sha256sum命令。這個命令可以生成一個文件的SHA-256哈希值，從而幫助用戶確認文件是否被篡改過。本文將詳細介紹sha256sum命令的使用方法和一些實用的場景。

什麼是SHA-256哈希函數？SHA-256（Secure Hash Algorithm 256-bit）是一種加密哈希函數，屬於SHA-2家族。它將任何字元串轉換成一個固定長度（256位）的哈希值。SHA-256的特點是，即使是微小的數據變化也會導致生成的哈希值發生巨大的變化，這使得它非常適合用於數據完整性校驗。

如何使用sha256sum命令？sha256sum命令的基本語法如下：

這里，[options]是可選的參數，[file...]是要計算哈希值的一個或多個文件。

基本使用：要計算一個文件的SHA-256哈希值，可以使用以下命令：

將filename替換為你想要計算哈希值的文件名。例如，如果有一個名為example.txt的文件，可以使用以下命令：

執行後，系統會輸出example.txt文件的SHA-256哈希值。

計算多個文件的哈希值：如果要同時計算多個文件的哈希值，可以將文件名依次列出：

輸出哈希值到文件：有時，我們可能需要將哈希值保存到一個文件中，而不是直接顯示在終端上。可以使用重定向操作符>>來實現：

這樣，file1.txt和file2.txt的哈希值就會被寫入hash_values.txt文件中。

校驗哈希值：除了生成哈希值，sha256sum還可以用於校驗文件的哈希值是否與已知的哈希值相匹配。這可以通過在命令後添加--check（或-c）選項來實現：

如果hash_values.txt中列出的哈希值與實際文件的哈希值相匹配，命令會顯示OK；如果有不匹配的，會顯示相應的錯誤信息。

從哈希值文件中校驗文件：如果有一個包含哈希值的文件（通常稱為哈希值清單），可以使用以下命令來校驗文件：

--status選項會讓sha256sum在每個文件校驗後顯示OK或ERROR，而不是在所有文件校驗完成後一次性顯示。

顯示幫助信息：如果需要獲取更多關於sha256sum命令的信息，可以使用--help選項：

常見問題解答：Q: 如何加快sha256sum命令的執行速度？答案：可以通過--parallel選項來指定同時運行的線程數，從而加快計算速度。例如：

這會讓sha256sum使用4個線程來計算哈希值。

Q: 如果文件很大，sha256sum命令會消耗很多資源嗎？答案：sha256sum命令在計算哈希值時，其資源消耗相對較小。但是，如果文件非常大，可能會佔用較多的CPU和內存資源。可以通過調整--parallel選項來優化資源使用。

Q:sha256sum命令可以用於加密文件嗎？答案：不可以。sha256sum命令用於生成文件的哈希值，而不是加密文件。哈希函數是單向的，不能用來解密或還原原始數據。

結語：sha256sum命令是Linux系統中一個非常實用的工具，它可以幫助用戶驗證文件的完整性和一致性。通過本文的介紹，初學者應該能夠快速掌握這個命令的使用方法，並在實際工作中有效地利用它來保護數據安全。記住，數據的完整性和安全性是至關重要的，而sha256sum正是維護這一關鍵要素的強大工具。