Length extension attack

2017-04-25 security Cryptography Hash

在 CTF 算是常見的 crypto 題型，但是現實生活中卻幾乎沒看過實際應用例子 . . .

主要受影響的 hash 演算法為 MD5 及 SHA1, 本文以 MD5 為例

弱點成因

  • MD5, SHA1 使用同一種壓縮演算法(Merkle–Damgård construction)

利用情境

  • 已知 md5(secret || message) 結果
  • 未知 secret 的前提下，可以計算出 md5(secret || message || append)

原理解析

  • MD5 會將訊息以 64 bytes 為一個 block 做分區，每個 block 做完 某種複雜的計算 後得到該回合(round) 的狀態值
  • 使用 A, B, C, D 四個 register 儲存䅮一回合的狀態
  • 以 0x80 表示 message 結尾，利用 0x00 padding 直到滿足 len(message) % 64 bytes = 56 bytes
  • 第 57 個 byte 用來表示 message 長度，hex(len(message) * 8) # 以 bit 為單位
  • 用 0x00 補滿直到 64 bytes

攻擊原理

  • 其實所謂的狀態值就是該 block 的 hash 結果，最終的 md5 輸出亦同
  • 每八個 digits 一組以 little endian 方式排列分別賦值給 A, B, C, D
  • padding 到下一個 block
  • 加上額外訊息

PoC

#include <stdio.h>
#include <openssl/md5.h>
#include <arpa/inet.h>

int main(void) {
    MD5_CTX c;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    int i;

    MD5_Init(&c);
    MD5_Update(&c, "secret", 6);                                                // secret # 6
    MD5_Update(&c, "haha",                                                      // message # 4
                   "\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"   // 14
                   "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"   // 14
                   "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"   // 14
                   "\x00\x00\x00\x00"                                           // 4
                   "\x50\x00\x00\x00\x00\x00\x00\x00"                           // 8
                   "append", 64);

    MD5_Final(buffer, &c);
    
    for(i=0; i < 16; i++) printf("%02x", buffer[i]);

    return 0;
}

#include <stdio.h>
#include <openssl/md5.h>
#include <arpa/inet.h>

int main(void) {
    MD5_CTX c;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    int i;

    MD5_Init(&c);
    MD5_Update(&c, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64); // 64 個 A 之後會被覆蓋不重要

    //e80f10c8 273e04a5 9b5edda6 cd3722da # md5(secrethaha) 

    c.A = htonl(0xe80f10c8);
    c.B = htonl(0x273e04a5);
    c.C = htonl(0x9b5edda6);
    c.D = htonl(0xcd3722da);

    MD5_Update(&c, "append", 6);

    MD5_Final(buffer, &c);
    
    for(i=0; i < 16; i++) printf("%02x", buffer[i]);

    return 0;
}

使用 gcc -lssl -lcrypto 編譯以後，兩個程式的輸出都是 fae9e4890b4ba03881c2a009bccc8bc8

修補方式

  • 將 secret 後置
    • hash(message || hash)
  • 使用 HMAC
    • hash(secret || hash(secret || message))

現實中利用的例子

Recent Posts