标签：00 x0b MAC 0b SHA 第五 消息 第六章

第5章 散列函数

定义：一类将任意长度的输入位（或字节）串转换为固定长度的输出的函数

数字签名应用：消息长，公钥运算代价大，牺牲部分安全性（碰撞）取散列做签名
混淆！数据结构中的访问散列表，有相似特点但缺乏特殊的安全性质
应用：伪随机生成器&隔离系统不同部分
新标准候选SHA-3：类似AES选取过程，提供了更多选择

5.1散列函数的安全性

基本要求：单向函数——>重要性质：抗碰撞性&随机映射
定义：理想的散列函数是从所有可能的输入值得到所可能的有限输出值集合的一个随机映射。
攻击定义：对散列函数的攻击是一个区分散列函数与理想散列函数的非通用（non-generic）的方法。
较低的安全等级：一个512位的散列函数拥有128 位的安全等级

5.2实际的散列函数

好的散列函数：SHA系列SHA-1、SHA-224、SHA-256和SHA-512。已经过关注和研究的考验保证其安全性
迭代方式：
    先将输入分成固定长度的分组序列m1，⋯，mk，最后一个分组要进行填充以使其达到固定的长度，分组的长度一般为512 位，最后一个分组通常包含一个表示输入长度的位串。
    然后使用一个压缩函数和固定大小的中间状态对这些消息分组按顺序进行处理，这个过程由固定的值H开始，随后计算H0=h‘(Hi-1,mi)，最后一个值Hk便为散列函数的输出。
优势：易于规定和实现（相对直接处理可变长度）&启动快（收到第一部分后立即开始计算）

5.2.1 一种简单但不安全的散列函数

全0密钥，128位分组的AES？？？

5.2.2 MD5

128位，相对MD4强化了抗攻击能力但同样脆弱
步骤：将消息分为512 位的序列分组，对最后一个分组要进行填充，消息的长度信息也在其中。MD5有128位的状态变量，它们被分为4个32位的字。压缩函数h'共有4 轮，在每一轮中，消息分组和状态变量进行混合，这种混合运算由32位的字上的加法、异或、与、或、轮转运算组合而成。每一轮将整个消息分组都混合在状态变量中，因此每个消息字都使用了4次。在4轮的压缩加'完成之后，将结果与输入状态相加得到h'的输出。
缺点：长度不够，264次计算后就会碰撞，王小云教授证明可以少于264次

5.2.3 SHA-1

NSA设计，NIST标准化，最早版本SHA|SHA-0，160位，同样基于MD4，相对MD5慢但更安全
缺陷：长度不够，280次计算后就会碰撞，王小云教授证明可以少于80次

5.2.4 SHA-224、SHA-256、SHA-384和SHA-512

同属SHA-2系列，同SHA-1结构相似，不同长度分别与长度减半的AES和3DES配合使用
缺陷：时间更慢更保守

5.3散列函数的缺陷

5.3.1长度扩充

一个消息m被分成消息分组序列m1，⋯，mk，得到散列的值为H。现在选择消息m'，它对应的消息分组序列为m1，⋯，mk，mk+1，由于m'的前k个块与m相同，散列值h(m)是在计算h(m')时的一个中间值，即有h(m')=h'(h(m),mk+1)

原因：散列函数计算的最后一步缺少一个特殊的处理，结果导致h(m)恰好是计算 h(m')时完成前k个块计算的中间状态。
危害：劫持者可以在消息后任意扩充信息而不被发现

5.3.2部分消息碰撞

当使用h进行散列处理时可以通过生日攻击用大约2n/2步找到两个发生碰撞的消息m和m'，并使系统对消息m进行认证，然后用消息m'代替。

原因：由于散列函数的迭代计算结构，只要出现了碰撞而且余下的输入一样，那么散列值就一定相同。而消息m和m'有相同的散列值，因此对任意的X，有h(m||X)=h(m'|X)。注意该攻击与X无关，同一对m和 m'对任何X都适用。
危害：劫持者可以制造经认证的无效明文感染通信

5.4修复缺陷

缺陷难以避免，但必须修复。缺陷组合叠加暴露问题：聚是一坨屎，散是满天星

5.4.1一个临时的修复方法

hDBL法：用m→h(h(m)m)代替m→h(m)，保证迭代运算与消息的每一位有关

安全性：n位有n位安全性，解决长度扩充缺陷问题
问题：耗时长（2倍）&启动慢（需完全读取）

5.4.2一个更有效的修复方法

hd法：用m→h(h(0b||m))代替m→h(m)，在散列前先在消息之前添加一个全0的分组

安全性&问题：n位有n/2位安全性，解决长度扩充缺陷问题

5.4.3其他修复方法

截断输出法：如果散列函数是n位输出，那么只取其前面的n-s位（s为某个正整数）作为散列值。

应用：SHA-224将SHA-256丢弃32位输出，SHA384将SHA512丢弃128位输出
安全性：SHA-512截断输出256位可满足128位安全设计目标

5.5散列算法的选择

建议使用SHA系列、SHAd系列、SHA-512的截断输出函数
2012年10月，美国NIST选择了Keccak算法作为SHA-3的标准算法，详细介绍可参考全新的 SHA-3 加密标准 —— Keccak

5.6习题

5.1 使用软件工具生成两个消息M和M，M≠M，请使用一个已知的针对 MD5的攻击方法，产生
一个针对MD5的碰撞。产生 MD5 碰撞的代码样例请参阅http://www.schneier.com/cehtml。

答：网页失效。

0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef

0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef

5.2 使用现有的密码库，编写一段程序来计算以下十六进制消息序列的 SHA-512 散列值∶
48 65 6C 6C 6F 2C 20 77 6F 72 6C 64 2E 20 20 20

答：由于使用python中的hashlib库，由于库加密默认会将字符转为16进制ASCII码，所以我先将16进制转为ASCII字符，即为Hello, world. 转换后得SHA-512散列值为85027f3fa308b4f070b566ca4da26daffa65d861e6a26430d69a5ab7670a56f9a1668b802e6dfd4ddc992b93f752f29d76ce32777a3234f6a47db5aa4dc57185，同网站上比对后结果正确

import hashlib
hash = hashlib.sha512()
hash.update('Hello, world. '.encode('utf-8'))
print(hash.hexdigest())

5.3 考虑算法SHA-512-n，此散列函数是指首先运行SHA-512算法，输出取前n位作为结果。请编写程序采用生日攻击找到对 SHA-512-n的碰撞。其中。n是8到48之间的8的倍数。程序可以使用现有密码库。分别计算当n为8、16、24、32、40、48时程序所需的时间，对于每一个n值运行5次以上来进行统计。分别计算SHA-512-256、SHA-512-384、SHA-512算法执行该程序所需的时间。

5.4 使用前一小题的SHA-512-算法，请编写程序，分别恢复下列散列函数算法的散列值的原像。
采用 SHA-512-8算法的散列值（十六进制）∶
A9
采用 SHA-512-16 算法的散列值（十六进制）∶
3D4B
采用 SHA-512-24算法的散列值（十六进制）∶
3A 7F 27
采用 SHA-512-32 算法的散列值（十六进制）∶
c3 c0 35 7C
分别计算当n为8、16、24、32时程序所需的时间，对于每一个π值运行5次以上来进行统计。
程序可以使用现有密码库。分别计算SHA-512-256、SHA-512-384、SHA-512算法执行该程序所
需的时间。
5.5 在5.2.1节中，提到消息m和m'经过散列运算得到相同的值M，请给出证明。
5.6 选择两个SHA-3 候选散列函数，比较它们的性能，以及在当前最好的攻击下的安全性。SHA-3
候选算法的信息请参阅http∶/ww.schneier.com/cehtml。

问题

为什么长度扩充问题有h(m')=h'(h(m),mk+1)而不是h(m')=h(m,mk+1)，h'(m)是什么意思?

实践

不使用库完成了SHA-256算法，并可以对字符和十六进制进行hash

a=0
class SHA256:
def init(self):
#64个常量
#图中Kt
self.constants = (
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2)
#迭代初始值，h0,h1,...,h7
self.h = (
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19)

#x循环右移b个bit
#rightrotate b bit
def rightrotate(self, x, b):
    return ((x >> b) | (x << (32 - b))) & ((2**32)-1)

#信息预处理。附加填充和附加长度值
def Pad(self, W ,a):
    if(a==1):
        return bytes(W, "ascii") + b"\x80" + (b"\x00" * ((55 if (len(W) % 64) < 56 else 119) - (len(W) % 64))) + (
            (len(W) << 3).to_bytes(8, "big"))
    else:
        return W+ b"\x80" + (b"\x00" * ((55 if (len(W) % 64) < 56 else 119) - (len(W) % 64))) + (
            (len(W) << 3).to_bytes(8, "big"))


def Compress(self, Wt, Kt, A, B, C, D, E, F, G, H):
    return ((H + (self.rightrotate(E, 6) ^ self.rightrotate(E, 11) ^ self.rightrotate(E, 25)) + (
                (E & F) ^ (~E & G)) + Wt + Kt) + (
                        self.rightrotate(A, 2) ^ self.rightrotate(A, 13) ^ self.rightrotate(A, 22)) + (
                        (A & B) ^ (A & C) ^ (B & C))) & ((2**32)-1), A, B, C, (D + (
                H + (self.rightrotate(E, 6) ^ self.rightrotate(E, 11) ^ self.rightrotate(E, 25)) + (
                    (E & F) ^ (~E & G)) + Wt + Kt)) & ((2**32)-1), E, F, G

def hash(self, message,a):
    message = self.Pad(message,a)
    digest = list(self.h)

    for i in range(0, len(message), 64):
        S = message[i: i + 64]
        W = [int.from_bytes(S[e: e + 4], "big") for e in range(0, 64, 4)] + ([0] * 48)

        #构造64个word
        for j in range(16, 64):
            W[j] = (W[j - 16] + (
                        self.rightrotate(W[j - 15], 7) ^ self.rightrotate(W[j - 15], 18) ^ (W[j - 15] >> 3)) + W[
                        j - 7] + (self.rightrotate(W[j - 2], 17) ^ self.rightrotate(W[j - 2], 19) ^ (
                        W[j - 2] >> 10))) & ((2**32)-1)

        A, B, C, D, E, F, G, H = digest

        for j in range(64):
            A, B, C, D, E, F, G, H = self.Compress(W[j], self.constants[j], A, B, C, D, E, F, G, H)

    return "".join(format(h, "02x") for h in b"".join(
        d.to_bytes(4, "big") for d in [(x + y) & ((2**32)-1) for x, y in zip(digest, (A, B, C, D, E, F, G, H))]))

def main():
encoder = SHA256()
while True:
a = int(input("输入模式：\n1.字符串\n2.16进制码\n"))
if(a==1):
message = input("Enter string: ")
print(f"Output: {encoder.hash(message,a)}\n")
else:
message = str(input("Enter string: "))
b=bytes.fromhex(message)
print(b)
print(f"Output: {encoder.hash(b,a)}\n")

if name == "main":
main()

image-20210328185253357

第6章 消息认证码

消息认证码，或者MAC、用于检测对消息的篡改。

6.1MAC的作用

输入：固定长度的密钥K&任意长度的消息m
输出：产生固定长度的 MAC 值
过程：Alice——>Bob:m&MAC(K,m)（tag）， Bob检验T=MAC（K，m'）是否成立。

6.2理想MAC与MAC的安全性

理想MAC定义：一个从所有可能的输入到n位输出的随机映射。
安全性定义：对于MAC的攻击是区分 MAC函数和理想MAC函数的非通用方法。
攻击者并不能够完全获取密钥K的值，当然系统其他部分的缺陷可能会泄露密钥K的部分信息。

6.3CBC-MAC和CMAC

CBC-MAC

消息m用CBC模式进行加密，而只保留密文的最后一个分组，其余全部丢弃。

计算过程

H0:=IV

H1:=Ek(Pi⊕Hi-1)

MAC:=Hk

由结构导致的缺陷：已知M(a)=M(b)，则对任意的c都有M(a||c)=M(b||c)。

攻击手段1：
    攻击者收集大量消息的 MAC 值，直到产生碰撞。
    若攻击者从发送者那里得到对消息a||c的认证码，他就可以用b||c代替消息a||c而无须改变MAC值，这个值完全可以通过接收者对 MAC值的验证，从而使接收者接到一个伪造的消息。

攻击手段2：假设c为一个分组长度的消息，且满足M(a||c)=M(b||c)。那么对任意分组d有M(a||d)=M(b||d)
    攻击者收集大量消息的MAC值，直到产生碰撞，得到产生碰撞的a和b。
    攻击者从发送者获取a||d的认证码，就可以用 b||d代替消息 a||d而无须改变 MAC 值

合适使用方式：
    从l||m 构造位串s，其中1是消息m在固定长度格式下的编码长度。
    对s进行填充使得其长度为分组长度的整数倍。
    对填充后的位串s应用 CBC-MAC。
    输出最后一个密文分组或它的一部分，切记不要输出任何中间值。

优点：与分组密码加密模式有相同模块，效率更高

缺点：方法难以使用

CMAC

基于CBC-MAC由NIST标准化
相比CBC-MAC只对最后一个分组的处理有所区别：在进行最后一次分组密码加密之前，CMAC将两个特殊值中的一个与最后一个分组进行异或。这些特殊值从 CMAC的密钥产生，被 CMAC 用到的那个值取决于消息的长度是否为分组块长度的倍数。在 MAC运算中引入对这些值的异或可以防御在不同长度的消息中使用 CBC-MAC 所面临的攻击。

6.4 HMAC

散列函数构造MAC：h(K⊕a||h(K⊕b||m)
由于HMAC对消息的头部进行散列运算时基于一个密钥，所以基于SHA-1的HMAC算法不会比 SHA-1算法差
安全性：n/2位的安全性，但需要和系统进行2n/2次交互
结构清晰，易于实现

6.5 GMAC

针对128位分组密码设计
三个输入：密钥、待认证消息、瞬时值，其中瞬时值是经传输或是隐含的（如包计数器）
攻击模型：攻击者选择n个不同的消息，然后得到每个消息对应的 MAC 值。攻击者如果不能够提出与前面选择的n个消息不同的第n+1个消息和相应的有效 MAC 值，那么这样的 MAC 就是不可伪造的。
问题：减少长度会将降低安全性，提供瞬时值有风险

6.6如何选择MAC

推荐HMAC-SHA-256：以 SHA-256 作为散列函数的HMAC。

6.7MAC的使用

Horton 原则：认证消息所包含的含义而不是消息本身。
MAC认证的不仅是消息m，还包括Bob解析消息m以获取含义所需要的所有信息
进行认证时，总要仔细考虑哪些信息应该包含在认证的范围内，确保将包括消息本身
在内的所有信息编码为一个字节串，而且编码应保证能以唯一的方式解析为原先的各个数据
域。这

6.8习题

6.1 试描述一个使用CBC-MAC进行消息认证的真实系统，并分析对于CBC-MAC进行长度扩充攻
击下的系统脆弱性
6.2 假设c为一个分组长度，a和b是多个分组长度的位串，且有M（ae）=M（be），这里M为CBC.MAC 函数。试证明对于任意分组d。有M（@小）-M（b】d小。
6.3 假设消息a和b的长度为一个分组大小，发送者分别对消息a，b、qb进行CBC-MAC运算。攻
[97击者截获经过 MAC运算后的标签，然后伪造消息抓（M（b）田M（a）④b），这个伪造后的消息标签
为 M（ab），也即消息 apb的标签。试用数学方法证明。
6.4 假设消息a的长度是一个分组的大小。假设攻击者截获MAC值r，这个值是消息a通过随机密
钥下的CBC-MAC进行计算得出的值，密钥是攻击者未知的。试解释如何选取一个长度为2个分
组的消息并伪造相应的MAC。试解释为何伪造的标签对于所选取的消息来说是有效的。
6.5 使用现有的密码库，使用基于AES的CBC-MAC算法，采用如下256位密钥∶
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 01
计算如下消息的 MAC 值∶
4D 41 43 73 20 61 72 65 2076 65 72 79 20 75 73
65 66 75 6c 20 69 6E 20 63 72 79 70 74 6F 67 72
61 7058 79 21 20 20 20 2020 20 20 20 20 20 20
6.6 使用现有的密码库，使用基于SHA-256的HMAC算法和如下密钥∶
0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b
0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b
计算如下消息的 MAC 值∶
4D 41 43 73 20 61 72 65 2076 65 72 79 20 75 73
65 66 75 6c 20 69 6E 20 63 72 79 70 74 6F 67 72
61 70 68 79 21

消息对应字符为MACs are very useful in cryptography!

import hmac
import hashlib
def hmac_sha256(key, value):
message = value.encode('utf-8')
return hmac.new(key.encode('utf-8'), message, digestmod=hashlib.sha256).hexdigest()
print(hmac_sha256('\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b', "MACs are very useful in cryptography!"))

计算得到mac值db8b895abc88a59cf8776a233ee1457c7239380347ef4dca8e48bc88433167eb

6.7 使用现有的密码库，采用基于AES的GMAC算法和如下256位密钥;
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 01
计算如下消息的 MAC 值∶
4D 41 43 73 20 61 72 65 20 76 65 72 79 20 75 73
65 66 75 6C 20 69 6E 20 63 72 79 70 74 6F 67 72
61 70 68 79 21
其中瞬时值为
00 00 00 00 00 00 00 00 00 00 00 01.

答：消息对应字符为MACs are very useful in cryptography!没有找到GMAC的实现方法
问题

为什么在6.3中说对于理想的 MAC 函数，找到了碰撞并不是问题，即使得到了满足条件M（a）= M（b）的两个消息a和b时，也不能够为新消息伪造一个 MAC 值？

标签：00,x0b,MAC,0b,SHA,第五,消息,第六章
From： https://www.cnblogs.com/charliecza/p/17204513.html