扩展长度攻击

ustcsse308

CSer

【课后有同学提出了很好的问题，就是文中给出的两个例子的应用场景不够合理；譬如如果已经知道了root密码，就可以直接Login；下载文件的时候怎么能保证一定能找到/etc/passwd。这里使用这个两个例子主要是用于演示扩展长度攻击的过程和原理，可以说是为了攻击而攻击。如果对实际的场景感兴趣，可以阅读 Flickr真实场景的长度攻击。】

在密码学之哈希一文中介绍了SHA256。希望大家对这种哈希算法在流程上比较熟悉。接下来，我们结合 CTF题目来看一下针对基于Merkle-Damgard构造的哈希算法的一种攻击形式，扩展长度攻击。

在介绍扩展长度攻击之前，首先澄清一个概念，hash和MAC（message authentication code）的区别：

主要区别在于概念：虽然哈希用于保证数据的完整性，但MAC保证了完整性和身份验证。

怎么理解呢？哈希码是在没有任何外部输入的情况下从消息中生成的，得到的是可用于检查消息在其传输期间是否有任何更改的内容。

而MAC在生成时会使用一个密钥附加在消息之前：这确保不仅消息未被修改，而且发送者也是我们所期望的：否则攻击者无法知道用于生成的code的密钥。【考虑发送方和接收方共享一个密钥，在hash时附上密钥一起进行哈希】

根据维基百科：虽然MAC功能类似于加密哈希函数，但它们具有不同的安全性要求。MAC必须能够抵御指定明文攻击【？？】。

首先，介绍攻击场景。攻击场景在CTF比赛中比较常见：

web系统的密码验证逻辑为：
$auth = false;
if (isset($_COOKIE["auth"])) {
   $auth = unserialize($_COOKIE["auth"]);
   $hsh = $_COOKIE["hsh"];
   if ($hsh !== md5($SECRET . strrev($_COOKIE["auth"]))) {    //$SECRET is a 8-bit salt
     $auth = false;
} else {
  $auth = false;
  $s = serialize($auth);
  setcookie("auth", $s);
  setcookie("hsh", md5($SECRET . strrev($s)));
}

访问页面会返回一个cookie

Cookie: auth=b%3A0%3B; hsh=32efdc967fcaebc6853b75cacfb80c5f

为了验证方便，改写成以下的python代码：

import hashlib
import sys
from urllib import unquote
def login(password, hash_val):
    m = hashlib.md5()
    secret_key = "message"               # secret_key is a salt
    m.update(secret_key + password)
    if(m.hexdigest() == hash_val):
        print "Login Successful!"
    else:
        print "Login Failed"
if __name__ == "__main__":
    password = unquote(sys.argv[1])
    hash_val = unquote(sys.argv[2])
    login(password, hash_val)

以上代码需要用户提供密码和一个哈希值，这个哈希值本身是服务端通过将一个密钥放在密码之前生成的。也即，网站需要确认的是，第一，用户确实知道密码；第二，用户确实是之前访问过网站并且获得了使用了密钥的哈希值的用户。作为攻击者，如果要想成功Login，那么就需要提供一个密码，同时还需要提供跟这个密码相配对的哈希值。而且这个哈希值还得是使用了服务端的密钥的哈希值。

已知系统中用户user1的密码为root，对应的salt为message，md5(salt || password)=md5(messageroot)=f3c36e01c874865bc081e4ae7af037ea。

第一次login是正常的login，成功；

$ python example.py root f3c36e01c874865bc081e4ae7af037ea
Login Successful!

第二次是攻击者构造的。利用“哈希长度扩展攻击”，我们可以算出一个密码和相应hash值，它们可以通过上面的密码验证逻辑，测试如下：

$ python example.py %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%00
%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%38%00%00%00%00%00%00%00admin 
e53a681a30ff99e3f6522270ca7db244
Login Successful!

尝试一下：

【上面的字符串的输入中不能有换行。尝试的同学请看参考9 】

【上面的例子有问题。等讲完之后请大家讨论。】

通过上面的输出可知，攻击者使用伪造的密码和hash值进入了系统。

另一个例子是：

假设有一个网站，在用户下载文件之前需验证下载权限。这个网站会用如下的算法产生一个关于文件名的MAC：

def create_mac(key, fileName)
   return Digest::SHA1.hexdigest(key + fileName)
End

最终产生的URL会是这样：

http://example.com/download?file=report.pdf&mac=563162c9c71a17367d44c165b84b85ab59d036f9

当用户发起请求要下载一个文件时，必须提供下载的文件名字和相对应的mac值；在服务端将会执行下面这个函数：

def verify_mac(key, fileName, userMac)
    validMac = create_mac(key, filename)
    if (validMac == userMac) do
        initiateDownload()
        displayError()
End

这样，只有当用户没有擅自更改可以下载的文件名时服务器才会执行initiateDownload()开始下载。实际上，这种生成MAC的方式，给攻击者在文件名后添加自定义字串留下可乘之机。

继续上面的例子，对文件下载的功能进行长度扩展攻击：

http://example.com/download?file=report.pdf%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%00%00%00%00%00%00%00%00%00%00%00%00%00%A8/../../../../../../../etc/passwd&
mac=ee40aa8ec0cfafb7e2ec4de20943b673968857a5

Length Extension Attacks 长度扩展攻击

哈希摘要算法，如MD5、SHA1、SHA2等，都是基于Merkle–Damgård结构。这类算法有一个很有意思的问题：如果你知道message和MAC，只需再知道key的长度，尽管不知道key的值，也能在message后面添加信息并计算出相应MAC。如果攻击者掌握了Hash(message)的值以及message的长度，那么在不知道message的情况下，可以获取Hash(message||padding||message′)的值，其中message′为任意值，padding通过message长度计算决定。

总结一下，“哈希长度扩展攻击”需要应用具备下面条件：

使用hash(key || message)这种方式，且使用了MD5或SHA-1等基于Merkle–Damgård构造的哈希函数生成哈希值；
让攻击者可以提交数据以及哈希值，虽然攻击者不知道密钥；
服务器把提交的数据跟密钥构造成字符串，并经过哈希后判断是否等同于提交上来的哈希值。

来讨论一下原理。【以下内容翻译自参考文献10 】

一步步来看一下。

let secret = "secret"
let data = "data"
let H = md5()
let signature = hash(secret || data) = 6036708eba0d11f6ef52ad44e8b74d5b
let append = "append"

服务器将 data 和 signature 发送给攻击者。攻击者猜测 H 是 MD5 ，譬如可以通过MAC码的长度 (MD5是最常用的128位的哈希算法)。

攻击者的目的是在仅知道 data , H , 和 signature 的情况下，将 append 附加到 data 上，然后生成正确的signature。而且这个很容易做到。

Padding

在讨论攻击之前，首先看一下padding。

在计算 H ( secret + data )时，字符串 ( secret + data ) 首先进行了填充，以 '1' 开始，后面的全部是0，然后以字符串的长度结束（MD5中这个长度本身占8个字节）。也就是说，在十六进制中，填充是0x80字节，后跟一些0x00字节，然后是字符串的长度。 0x00字节的数量、为长度保留的字节数以及长度的编码方式取决于特定的算法和块大小。

对于大多数算法（包括MD4、MD5、RIPEMD-160、SHA-0、SHA-1和SHA-256），在进行填充时，会使得字符串的长度为模64余56个字节。或者，换句话说，它被填充直到长度比完整（64字节）块少8个字节（8个字节是长度字段的大小）。在hash_extender【作者实现的进行长度攻击的工具】中实现了两个不使用这些值的哈希：SHA-512使用128字节的块大小并为长度字段保留16个字节，而WHIRLPOOL使用64字节的块大小并为长度字段保留32个字节。

长度字段的字节顺序也很重要。 MD4、MD5和RIPEMD-160是little-endian，而SHA系列和WHIRLPOOL是big-endian。这也非常重要，作者花了好几天才搞定这个问题。

在我们的示例中，length（secret || data）= length（“secretdata”）是10（0x0a）字节或80（0x50）位。因此，我们有10个字节的数据（“secretdata”），46个字节的填充（80 00 00 ...）和一个8字节的小端长度字段（50 00 00 00 00 00 00 00）总共64个字节（或一个块）。放在一起，它看起来像这样：

  0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
  0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......

解析一下，得到

"secret" = secret
"data" = data
80 00 00 ... — The 46 bytes of padding, starting with 0x80
50 00 00 00 00 00 00 00 — The bit length in little endian

这是H在原始示例中hash的确切数据。

【补充强调一下，长度是以bit为单位的；也即，50=5*16=80，80bit，也即10个字节；secretdata是10个字节；】

【另一个例子，如果原始数据是512比特，也即64字节，那么在大端的情况下填充部分如下：

80 000000000000000000000000000000000000000000000 0000000000000200

其中，200=2*256=512比特】

攻击过程

既然我们有H哈希的数据，那么让我们来看看如何执行实际的攻击。

首先，让我们将附加追加到字符串中。够容易！这是它的样子：

  0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
  0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......
  0040  61 70 70 65 6e 64                                append

该块的哈希是我们最终想要a）计算，以及b）让服务器计算。可以通过两种方式计算该数据块的值：

通过将其粘贴在buffer中并执行H（buffer）
通过从第一个块结束开始，使用我们已经从签名中获知的状态，并从该状态开始追加哈希

第一种方法是服务器将执行的操作，第二种方法是攻击者将执行的操作【攻击者也没办法使用第一种方法进行计算，因为不知道secret的值】。让我们先看一下服务器，因为它更简单。

服务器的计算

我们知道服务器会在字符串前加上秘密，所以我们发送字符串减去秘密值：

  0000  64 61 74 61 80 00 00 00 00 00 00 00 00 00 00 00  data............
  0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0030  00 00 50 00 00 00 00 00 00 00 61 70 70 65 6e 64  ..P.......append

不要被这恰好是64字节（块大小）所欺骗 - 这只是因为secret和append是相同的长度而发生的。也许作者不应该选择那个作为例子，但作者不会重新开始！

服务器将为该字符串添加secret，创建：

  0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
  0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......
  0040  61 70 70 65 6e 64                                append

哈希的结果是:

  6ee582a1669ce442f3719c47430dadee

对于想自己尝试的同学，可以将下面的代码拷贝到terminal中：

  echo '
  #include <stdio.h>
  #include <openssl/md5.h>
  int main(int argc, const char *argv[])
    MD5_CTX c;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    int i;
    MD5_Init(&c);
    MD5_Update(&c, "secret", 6);
    MD5_Update(&c, "data"
                   "\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"
                   "\x50\x00\x00\x00\x00\x00\x00\x00"
                   "append", 64);
    MD5_Final(buffer, &c);
    for (i = 0; i < 16; i++) {
      printf("%02x", buffer[i]);
    printf("\n");
    return 0;
  }' > hash_extension_1.c
  gcc -o hash_extension_1 hash_extension_1.c -lssl -lcrypto
  ./hash_extension_1

好的，所以服务器将检查我们发送的能够生成signature 6ee582a1669ce442f3719c47430dadee的数据。现在，作为攻击者，我们需要弄清楚如何生成该signature！

客户端的计算

那么，我们如何在不实际知道secret的情况下计算上面显示的数据的哈希值呢？

嗯，首先，我们需要看一下我们要处理的内容：data，append，H和H（secret || data）。

我们需要定义一个新函数H'，它使用与H相同的散列算法，但其起始状态是H（secret || data）的最终状态，即signature。一旦我们有了，我们只需计算H'（append），该函数的输出就是我们的哈希值。这听起来很容易（而且是！）; 看看这段代码：

  echo '
  #include <stdio.h>
  #include <openssl/md5.h>
  int main(int argc, const char *argv[])
    int i;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    MD5_CTX c;
    MD5_Init(&c);
    MD5_Update(&c, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64);
    c.A = htonl(0x6036708e); /* <-- This is the hash we already had */
    c.B = htonl(0xba0d11f6);
    c.C = htonl(0xef52ad44);
    c.D = htonl(0xe8b74d5b);
    MD5_Update(&c, "append", 6); /* This is the appended data. */
    MD5_Final(buffer, &c);
    for (i = 0; i < 16; i++) {
      printf("%02x", buffer[i]);
    printf("\n");
    return 0;
  }' > hash_extension_2.c
  gcc -o hash_extension_2 hash_extension_2.c -lssl -lcrypto
  ./hash_extension_2

结果正是上面所看到的:

  6ee582a1669ce442f3719c47430dadee

所以我们知道signature是正确的。不同的是，我们根本没有使用secret！发生了什么！？

好吧，我们从头开始创建MD5_CTX结构，就像正常的一样。然后我们采用64个'A'的MD5。我们采用'A'的完整（64字节）块的MD5来确保除了散列本身的状态之外的任何内部值都设置为我们期望的值。

然后，在完成之后，我们将c.A，c.B，c.C和c.D替换为签名中的值：6036708eba0d11f6ef52ad44e8b74d5b。这使得MD5_CTX结构处于与最初完成时相同的状态，并且意味着我们散列的任何其他内容（在本例中为append）将产生与我们以常规方式对其进行哈希处理时相同的输出。

我们在设置状态变量之前对值使用htonl（），因为MD5 - 是little-endian - 也以little-endian输出它的值。

结果

我们得到了字符串:

  0000  64 61 74 61 80 00 00 00 00 00 00 00 00 00 00 00  data............
  0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0030  00 00 50 00 00 00 00 00 00 00 61 70 70 65 6e 64  ..P.......append

以及所需的哈希值 H(secret || data || append) :

  6ee582a1669ce442f3719c47430dadee

我们可以在不知道secret的情况下生成signature！因此，我们将字符串与我们的新signature一起发送到服务器。验证通过。

在第一个例子中到底存在什么问题呢？参考文献9有一个细节应该是弄错了。攻击者需要知道除了密钥之外的data部分。在演示中，提供的padding没有data部分，也就意味着第一步测试的时候不能提供‘root’。通过验证，作者在例子中给出的第一个哈希值f3c36e01c874865bc081e4ae7af037ea实际上并不能协助生成第二个哈希值e53a681a30ff99e3f6522270ca7db244。相反，如果对代码进行一点修改，可以进行验证：

import hashlib
import sys
from urllib import unquote
def login(password, hash_val):
    m = hashlib.md5()
    secret_key = "message"               # secret_key is a salt
 #   m.update(secret_key + password)
    m.update(secret_key)
    print m.hexdigest()
    if(m.hexdigest() == hash_val):
        print "Login Successful!"
    else:
        print "Login Failed"
if __name__ == "__main__":
    password = unquote(sys.argv[1])
    hash_val = unquote(sys.argv[2])
    login(password, hash_val)

在仅有message（密钥）的情况下，生成的哈希值是

将这个哈希值作为IV，“admin”作为数据，则恰好可以生成e53a681a30ff99e3f6522270ca7db244。

#include <stdio.h>
#include <openssl/md5.h>
  int main(int argc, const char *argv[])
    int i;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    MD5_CTX c;
    MD5_Init(&c);
    MD5_Update(&c, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64);
   // c.A = htonl(0x6036708e); /* <-- This is the hash we already had */
   // c.B = htonl(0xba0d11f6);
   // c.C = htonl(0xef52ad44);
   // c.D = htonl(0xe8b74d5b);
   // c.A = htonl(0xf3c36e01); /* <-- This is the hash we already had */
   // c.B = htonl(0xc874865b);
   // c.C = htonl(0xc081e4ae);
   // c.D = htonl(0x7af037ea);
    c.A = htonl(0x78e73102); /* <-- This is the hash we already had */
    c.B = htonl(0x7d8fd50e);
    c.C = htonl(0xd642340b);
    c.D = htonl(0x7c9a63b3);
    //MD5_Update(&c, "append", 6); /* This is the appended data. */
    MD5_Update(&c, "admin", 5); /* This is the appended data. */
    MD5_Final(buffer, &c);
    for (i = 0; i < 16; i++) {
      printf("%02x", buffer[i]);
    printf("\n");
    return 0;

可以继续做练习，在使用输入root的情况下，应该构造怎么样的攻击串。此时需要重新计算新串的哈希：

#include <stdio.h>
#include <openssl/md5.h>
  int main(int argc, const char *argv[])
    int i;
    unsigned char buffer[MD5_DIGEST_LENGTH];
    MD5_CTX c;
    MD5_Init(&c);
    MD5_Update(&c, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64);
   // c.A = htonl(0x6036708e); /* <-- This is the hash we already had */
   // c.B = htonl(0xba0d11f6);
   // c.C = htonl(0xef52ad44);
   // c.D = htonl(0xe8b74d5b);
    c.A = htonl(0xf3c36e01); /* <-- This is the hash we already had */
    c.B = htonl(0xc874865b);
    c.C = htonl(0xc081e4ae);
    c.D = htonl(0x7af037ea);
   // c.A = htonl(0x78e73102); /* <-- This is the hash we already had */
   // c.B = htonl(0x7d8fd50e);
   // c.C = htonl(0xd642340b);
   // c.D = htonl(0x7c9a63b3);
    //MD5_Update(&c, "append", 6); /* This is the appended data. */
    MD5_Update(&c, "admin", 5); /* This is the appended data. */
    MD5_Final(buffer, &c);
    for (i = 0; i < 16; i++) {
      printf("%02x", buffer[i]);
    printf("\n");
    return 0;

得到一个哈希值：

然后构造扩展的串：

注：使用Python3的话，上面的代码需要修改：

import hashlib
import sys
from urllib.parse import unquote
def login(password, hash_val):
    m = hashlib.md5()
    secret_key = "message"               # secret_key is a salt
 #   m.update(secret_key.encode('utf-8') + password)
    m.update(secret_key)
    print m.hexdigest()
    if(m.hexdigest() == hash_val):
        print "Login Successful!"
    else:
        print "Login Failed"