長度擴充攻擊

在密碼學和電腦安全中，長度擴充攻擊（英語：Length extension attacks）是指一種針對特定加密雜湊函數的攻擊手段，攻擊者可以利用H（訊息₁）和訊息₁的長度，不知道訊息₁內容的情形下，將攻擊者控制的訊息₂計算出H（訊息₁ ‖ 訊息₂）。

該攻擊適用於在訊息與金鑰的長度已知的情形下，所有採取了 H(金鑰 ∥ 訊息) 此類構造的雜湊函數^[1]。MD5和SHA-1等基於Merkle–Damgård構造（英語：Merkle–Damgård_construction）的演算法均對此類攻擊顯示出脆弱性^[2]^[3]^[4]。注意，由於金鑰雜湊訊息鑑別碼（HMAC）並未採取 H(金鑰 ∥ 訊息) 的構造方式，因此不會受到此類攻擊的影響（如HMAC-MD5、HMAC-SHA1）^[5]。SHA-3演算法對此攻擊免疫^[6]。

解釋

對此類攻擊脆弱的雜湊函數的常規工作方式是：取得輸入訊息，利用其轉換函數的內部狀態；當所有輸入均處理完畢後，由函數內部狀態生成用於輸出的雜湊摘要。因而存在着從雜湊摘要重新構建內部狀態、並進一步用於處理新數據（攻擊者偽造數據）的可能性。如是，攻擊者得以擴充訊息的長度，並為新的偽造訊息計算出合法的雜湊摘要。

範例

一個用於向指定地點的用戶遞送指定種類窩夫（即下面代碼中的waffle）的伺服器，可處理如下格式的請求：

原始数据: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
原始签名: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

若且唯若該用戶給出的簽章對於其當前請求（向指定地點的用戶1遞送10個Eggo窩夫）而言合法時，伺服器才會實際處理該業務。該簽章是一個訊息鑑別碼（MAC），由某個攻擊者不可知曉的金鑰簽發。（事實上，這個例子對於重放攻擊同樣脆弱，攻擊者亦可能通過二次傳送同樣的請求和簽章來實施攻擊。）

攻擊者可能篡改該請求，在上述例子中，假設某攻擊者把窩夫的種類從「eggo」改為「liege」，這可以藉助於訊息格式本身的靈活性達到：對於請求字串中重複的參數域，總是處理最後的參數。這樣的靈活性並不能算作是訊息格式本身的安全漏洞，因為訊息格式在設計之初並未以安全性為前提；安全性需要通過簽章演算法的輔助來達到。

攻击者希望篡改的新数据: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

為了給此新資訊加上合法的簽章，攻擊者通常需要知道用於簽章資訊的金鑰，並由此金鑰生成一個新的MAC來作為新簽章。然而，藉助於長度擴充攻擊手段，攻擊者可以將雜湊（如上給出的簽章）傳遞給雜湊函數作為原始狀態，而從原請求處開始繼續處理，這只需知道原請求的長度即可；在該請求中，原金鑰的長度為14位元組，這可以通過試探不同長度的偽造請求、並檢查何種長度的請求被伺服器接受而得到。

傳遞給雜湊函數的資訊通常是填充（Padding）後的，因為許多演算法只接受長度為指定大小倍數的輸入。填充的內容是由採用的雜湊函數決定的。攻擊者在新資訊中除了包含原資訊和偽造資訊之外，還應當包含必需的填充位。因而，攻擊者利用填充規則可以構造出如下資訊：

新数据: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x02&waffle=liege

該資訊包含了雜湊函數中添加到原訊息的填充位（在此範例中，是一個0x80，隨後是若干0x00，最後是訊息長度）。攻擊者知道原訊息的雜湊金鑰/訊息對所對應的狀態直到最後一個「&」為止，均和新訊息是相同的；攻擊者此時亦知道其雜湊摘要，這意味着雜湊函數的內部狀態已經被完全偽造。此時，初始化一個雜湊演算法就非常簡單了，給定剩餘的字串作為輸入，即可生成一個用於簽章的新摘要，而根本無須知曉原金鑰。

新签名: 0e41270260895979317fff3898ab85668953aaa2

通過連接新簽章和新數據成為一個新請求，伺服器將把該偽造的請求視作一個有效的請求，因為其簽章和在知道密碼情況下生成的簽章完全等效。

該攻擊主要用於偽造已簽章的訊息，但亦可能存在其他用途。^[7]

實現

目前實現該類型攻擊的工具並不多。一個藉助於OpenSSL實現了針對多種雜湊函數的攻擊的工具是 HashPump （頁面存檔備份，存於互聯網檔案館）。該工具支援針對MD5、SHA1、SHA256和SHA512的長度擴充攻擊。^[7]SHA224和SHA384受此攻擊的影響相對較小，由於這兩個函數的輸出分別是更長的雜湊函數（分別是256及512位元）的前224位元和前384位元，因此其輸出並不包含雜湊內部狀態的全部長度，不能直接使用雜湊值進行長度擴充攻擊。然而，SHA224和SHA384畢竟輸出了更長雜湊的很大一部分，因此攻擊者仍然可以輕易地首先窮舉得到剩下的部分（缺失長度僅為32位元和128位元）後，再實施長度擴充攻擊。因此，不能依賴截取部分雜湊來實現訊息驗證碼。

參考

^ Hoàng Vũ. MD5 Length Extension Attack Revisited. [31 January 2013]. （原始內容存檔於2014-10-29）.
^ White Hat Security. Hash Length Extension Attacks. [31 January 2013]. （原始內容存檔於2014-02-26）.
^ Flickr API Signature Forgery Vulnerability (PDF). [2014-01-30]. （原始內容存檔 (PDF)於2021-04-09）.
^ Christopher Meyer. Hash Length Extension Attacks. [31 January 2013]. （原始內容存檔於2021-04-14）.
^ Nate Lawson. Stop using unsafe keyed hashes, use HMAC. [31 January 2013]. （原始內容存檔於2021-05-06）.
^ Keccak team. Strengths of Keccak - Design and security. [30 January 2013]. （原始內容存檔於2017-06-06）. Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
^ ^7.0 ^7.1 Wallace, Brian. Hash Length Extension Attack. （原始內容存檔於2013-05-03）.

[1] Hoàng Vũ. MD5 Length Extension Attack Revisited. [31 January 2013]. （原始內容存檔於2014-10-29）.

[2] White Hat Security. Hash Length Extension Attacks. [31 January 2013]. （原始內容存檔於2014-02-26）.

[3] Flickr API Signature Forgery Vulnerability (PDF). [2014-01-30]. （原始內容存檔 (PDF)於2021-04-09）.

[4] Christopher Meyer. Hash Length Extension Attacks. [31 January 2013]. （原始內容存檔於2021-04-14）.

[5] Nate Lawson. Stop using unsafe keyed hashes, use HMAC. [31 January 2013]. （原始內容存檔於2021-05-06）.

[6] Keccak team. Strengths of Keccak - Design and security. [30 January 2013]. （原始內容存檔於2017-06-06）. Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

[Wallace-7] 7.0 ^7.1 Wallace, Brian. Hash Length Extension Attack. （原始內容存檔於2013-05-03）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]