Crypto入门-密码学杂谈

Diffie-Hellman密钥交换

在双方先前没有任何共同知识的情况下通过不安全信道协商出一个对称密钥。

DH密钥交换算法：双方选择一个 $p \in P$ 和 $Z p *$ 的一个生成元 $g$ ，在不安全的信道上发送。A选择一个秘密 $a \in Z$ ，计算 $A = g^{a} mod p$ 并发送给B。B选择一个秘密 $b \in Z$ ，计算 $B = g^{b} mod p$ 并发送给A。A与B可共同得出密钥 $k = A^{b} mod p = B^{a} mod p = g^{a b} mod p$ 。

当中间人截获信息但不能修改时，知道 $A, B, g, p$ 而不知道 $a, b$ ，计算 $\log_{a} A, \log_{b} B$ 很困难。

DH中间人攻击

当中间人可以截获并修改信息时。

中间人获取到 $p$ 和 $g$ 。现在A正要把 $A$ 发给B，此时中间人截获 $A$ ，自己选定一个随机数 $e_{1}$ ，将 $A$ 换成 $E_{1} = g^{e_{1}} mod p$ 发给B。B把 $B$ 发给A时同理，选定随机数 $e_{2}$ ，将 $B$ 换成 $E_{2} = g^{e_{2}} mod p$ 转发给A。

此时A计算出的密钥为 $k_{1} = E_{2}^{a} mod p = g^{e_{2} a} mod p = A^{e_{2}} mod p$ ，而B计算出的密钥为 $k_{2} = E_{1}^{b} mod p = g^{e_{2} a} mod p = B^{e_{1}} mod p$ 。此时中间人也可通过 $A, B, e_{1}, e_{2}$ 计算出 $k_{1}, k_{2}$ ，A向B发送加密消息时中间人拦截用 $k_{1}$ 解密，并用 $k_{2}$ 再次加密转发给B。

Hash长度扩展攻击

先了解基础知识：

以SHA-1举例，哈希函数拿到字符串后，将字节长度整除 $64$ 取余数，如果正好等于 $56$ ，则在字符串最后添上 $8$ 字节长度描述符。如果不等于 $56$ ，就先填充，填充的第一个字节为 $0 x 80$ ，其他字节均用 $0 x 00$ ，填充至余数为 $56$ 后同样增加 $8$ 个字节的长度描述符，这称为补位。

补位后，字符串每 $64$ 字节为一组进行分组，每次进行一次逻辑函数序列后产生一组新的 $H$ 值供下一次使用。当全部分组被处理完后， $H$ 中的值作为最终结果。

一般选择形如 $H (key ∣ message)$ 的Hash函数，即在消息前固定一个密钥。但在MD型Hash算法（MD5、SHA-1等）的密钥长度已知、消息可控时易受到Hash长度扩展攻击。

具体攻击没看懂，挖坑待填。

例题：

php

<?php
    $secret="XXXXXXXXXXXXXXX"; // This secret is 15 characters long for security!
    $username="admin";
    $password = $_POST["password"];
    if($COOKIE["getmein"] === md5($secret . urldecode($username . $password))){
        echo "Congratulations! You are a registered user.\n";
        die ("The flag is ". $flag);
    }
    else{
        die("Your cookies don't match up! STOP HACKING THIS SITE.");
    }
    //md5($secret."adminadmin")的值为571580b26c65f306376d4f64e53cb5c7
?>

将$secret看成密钥，第一个“admin”当作密钥后半部分的可控制部分，这样一来密钥总长度为 $20$ ，数据为第二个“admin”。

数据随便篡改为“pcat”，使用工具HashPump：

plaintext

# hashpump
Input Signature: 571580b26c65f306376d4f64e53cb5c7
Input Data: admin
Input Key Length: 20
Input Data to Add: pcat

得到结果：

plaintext

1
2

3e67e8f0c05e1ad68020df30bbc505f5
admin\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\xc8\x00\x00\x00\x00\x00\x00\x00pcat

第一行塞Cookies的getmein中，第二行把“\x”改成“%”然后POST。

HashPump不好使，建议用pip安装hashpumpy，用法：

python

1
2
3

import hashpumpy
result=hashpumpy.hashpump('112bba932266ca5df55eb36dcd7050ec','This_is_salt','xx',28)
print(result[0],result[1])

Shamir门限方案

一种秘密共享方案，将秘密信息分成 $n$ 份，只要有其中的 $k$ 份即可将秘密解出。

设需要 $k$ 份解出秘密消息 $m$ ，选择 $k - 1$ 个随机数 $a_{1}, \dots, a_{k - 1}$ 和大数 $p \in P, p > m$ ，列出模 $p$ 多项式 $f (x) = m + \sum_{i = 1}^{k - 1} a_{i} x^{i} mod p$ 。随机选择 $n$ 个整数 $x$ ，代入上式得到 $n$ 个数 $(x_{1}, f (x_{1})), (x_{2}, f (x_{2})), \dots, (x_{n}, f (x_{n}))$ 。恢复秘密信息时只需要 $k$ 个 $(x_{i}, f (x_{i}))$ 对，利用拉格朗日插值法或矩阵乘法可求得秘密信息 $m$ 。