BETHASH官方网站

　　第十讲 密码Hash函数 本讲提要 分类与架构 基本构造 修改发现码(MDC) 消息认证码(MAC) 1 分类与架构 定义1 Hash函数(在不严格意义下)是至少满足下列两条性质的函数h。 (1) 压缩：h将任意有限比特长度的输入x映射为固定长度为n的输出h(x)。 (2) 容易计算：给定h和输入x，容易计算出h(x)。 1 分类与架构(续) 密码中使用的Hash函数主要为两类： (1) 修改发现码(MDC)：不带密钥的Hash函数，主要用于提供消息完整性检查。 (2) 消息认证码(MAC)：带密钥的Hash函数，主要用于认证消息源及保证其完整性。 1 分类与架构(续) 定义2 修改发现码(MDC)是Hash函数h，对于输入x和x?以及相应输出y和y?满足如下性质： (1) 原像不可逆：对于几乎所有的Hash输出不可能计算出其的Hash输入。也就是，在不知道输入的情况下给定任意一个输出y，找到任意一个输入x?满足h(x?)=y是计算不可能的。 (2) 二次原像不可逆：对于任何一个给定的输入x，找到另一个输入x??x，且满足h(x)=h(x?)，在计算上不可能。 (3) 抵抗碰撞：找到两个不同的输入x和x?，满足h(x)=h(x?)，在计算上不可能(注意：这里两个输入可以自由选择)。 1 分类与架构(续) 定义1和定义2的说明： (1) “容易”和“计算上不可能”都留下来没有准确定义。“容易”意味着多项式时间和空间；“计算上不可能”意味着超越多项式的计算需求。 (2) 一般认为，抗原像?单向；抗二次原像?抗弱碰撞；抵抗碰撞?抗强碰撞。 1 分类与架构(续) 定义3 单向Hash函数(OWHF)是满足定义1以及定义2中(1)和(2)的Hash函数。 定义4 抗碰撞Hash函数(CRHF)是满足定义1以及定义2中(2)和(3)的Hash函数。 #虽然几乎所有实际使用的CRHF都有抗原像攻击的性质，但由于技术原因定义4并未给出。 1 分类与架构(续) 1.1 基本性质与定义(续) 攻击者攻击 MDC的主要目标如下： (1) 给定Hash值y，发现原像x满足y=h(x)；或者给定对(x，h(x))发现另一个像x?满足 h(x)=h(x?)。 (2) 发现两个Hash输入x和x?满足h(x)=h(x?)。 1 分类与架构(续) 定义5 消息认证码(MAC)算法是带有密钥k的函数族hk，其具有如下性质： (1) 易于计算：对于任何已知函数hk，给定值k和输入x，值hk(x)容易计算出来。这个值被称做MAC值或MAC。 1 分类与架构(续) (2) 压缩：函数hk可以将任意有限比特长度的输入x映射为固定n比特长度的位串。进一步，给出函数族h的算法描述，对于任何一个固定符合要求的密钥值k(攻击者不知其值)，需要满足如下性质： (3) 计算抵抗：给定0个或多个消息-MAC值对(xi，hk(xi))，找到任意消息-MAC值对(x，hk(x))满足x?xi在计算上不可能(当然也包括某些i满足hk(x)=hk(xi)的可能性)。 1 分类与架构(续) 评述. (1) 计算抵抗隐含了密钥k是不可恢复的性质，但密钥不可恢复并不意味着计算抵抗。 (2) 定义5并没有显示攻击者知道密钥k的情况下是否要抗原像和抗碰撞，但对不知道密钥k的情况下，应该满足这些性质。 攻击者攻击MAC的目标为： 在不知道密钥k的情况下，给定一个或多个消息-MAC值对(xi，hk(xi))，计算出一个或多个新消息-MAC值对(x，hk(x))，满足x?xi。 攻击者潜在的能力有： (1) 已知消息攻击。 (2) 选择消息攻击：掌握一个或多个由攻击者选择的xi对应的消息-MAC值对(xi，hk(xi))。 (3) 适应性选择消息攻击：允许根据前面的询问结果连续做出消息选择。 在实际中造成的破坏程度取决于攻击者控制消息x并伪造其MAC值的程度，依此可以做如下分类。 (1) 选择性伪造攻击：攻击者可以根据选择，控制消息的内容伪造出消息-MAC值对(或者至少为部分控制消息内容)。 (2) 存在性伪造攻击：攻击者虽然可以伪造出消息-MAC值对，但无法控制消息的内容。 与特定性质联系在一起的是开销，如CRHF一般比OWHF要难于构造，且其Hash值应是OWHF的比特长度的两倍。 因此，考虑具体应用十分重要。假如可由不可信方控制Hash函数的输入的准确内容，则可能需要CRHF，如数字签名。假如只是可信方的单方应用，使用OWHF就足够了，如口令表的应用。 事实1 Hash函数的抗碰撞隐含抗二次原像。 事实2 Hash函数抗碰撞不能保证抗原像。 事实3 Hash函数抗二次原像不能保证抗原像，抗原像也不能保证抗二次原像。 事实4 hk是MAC，hk符合计算抵抗性质。若攻击者不知道密钥k，hk抗选择消息攻击，则应该抗二次原像、抗碰撞、抗原像。 MDC的其他应用 (1) 知识确认。 (2) 密钥产生。 (3) 伪随机数发生。 # 这些MDC可能需要满足一些超过之前定义的附加性质。 高级视图 详细视图 Hi表示第i步的部分结果，输入为x=x1x2…xt的迭代函数的一般模型为 H0=IV； Hi=f(Hi-1, xi)，1?i?t ；h(x)=g(Ht)。 Hi-1表示第i-1步和第i步之间的n比特链变量，H0是预定义的开始值或初始值(IV)。最后一步用可选的输出变换g将n比特链变量映射为m比特结果g(Ht)，通常g(Ht)=Ht。 事实5 一个n比特输出的不带密钥Hash函数是理想安全的，如果：(1) 给定一个Hash输出，产生一个原像和二次原像需要大约2n次操作规模；(2) 产生一个碰撞需要大约2n/2次操作规模。 事实6 假定n比特输出的Hash函数，280次操作在计算上不可能，则有：(1) OWHF要求n?80；(2) CRHF要求n?160；(3) MAC对大部分环境要求n?64以及64-80比特的密钥，如果有特别控制，可小到n=32或64。 3.1 基于分组密码的Hash函数：MDC-2 在分组密码基础上建立Hash函数的主要动机是：如果系统已经拥有了非常有效的分组密码，那么以分组密码作为实现Hash函数的主要部件，将既可以提供Hash函数的功能，又能使额外开销最小。 3.1 基于分组密码的Hash函数：MDC-2 (续) 3.1 基于分组密码的Hash函数：MDC-2 (续) 3.1 基于分组密码的Hash函数：MDC-2 (续) 3.2 定制的Hash函数：SHA-1 安全Hash算法(SHA)是美国国家标准技术研究所(NIST)设计，并于1993年作为联邦信息处理标准(FIPS180)发布的。后做修改，于1995年再次公布修订后的SHA，通常称为SHA-1。 3.2 定制的Hash函数：SHA-1(续) SHA-1算法的输入为小于264比特长的任意消息，输出为160比特的消息摘要，算法处理过程如下图。 3.2 定制的Hash函数：SHA-1(续) SHA-1消息处理过程： (1) 消息填充。填充使得消息的比特长度为512比特的某个倍数减64，即使原始消息已满足要求，仍要填充。这样填充的比特数在1到512。填充方式是第一位为1其他位是0。最后64比特位用来填充消息被填充前的长度。这形成了长度为512比特的一系列分组Y0， Y1，… ，YL-1。 3.2 定制的Hash函数：SHA-1(续) (2) 初始化。 SHA-1使用160比特的缓冲区存储中间和最终Hash值，可用5个32比特寄存器A，B，C，D，E表示，初始值为(十六进制) AB=efcdab89，C=98badcfe，DE=c3d2e1f0。 3.2 定制的Hash函数：SHA-1(续) (3) 处理。每个分组Yq经过压缩函数处理，压缩函数由4轮处理过程构成。每一轮又由20步迭代组成。4轮处理结构一样，但基本逻辑函数不同，分别为f1，f2，f3，f4 。每轮处理消息分组Yq和缓冲区A、B、C、D、E的当前值，输出仍放在对应缓冲区。每一轮处理有一个加法常量Ki，其中t表示迭代步数，0≤t≤79。第4轮的输出与第1轮的输入CVq依5个缓冲区对应进行模232相加得到CVq+1。消息的L个分组都按上述计算处理完成后，最后一个分组的输出就是160比特消息摘要。 3.2 定制的Hash函数：SHA-1(续) 3.2 定制的Hash函数：SHA-1(续) SHA-1的压缩函数 各个20步迭代运算的每一步运算可以表示为 A，B，C，D，E←(E+fi(B，C，D)+CLS5 (A)+Wt+Ki)，A，CLS30(B)，C，D 其中，t是迭代的步数(0≤t≤79)，+是模232相加，fi是i (1≤i≤4)轮的基本逻辑函数，CLSs表示循环左移s位，Wt是当前512比特分组导出的一个32比特字。 3.2 定制的Hash函数：SHA-1(续) SHA-1的压缩函数(续) 基本逻辑函数f1，f2，f3，f4分别定义为： f1(X，Y，Z)=(X?Y)?(?X?Z) f2(X，Y，Z)=f4(X，Y，Z)=X?Y?Z f3(X，Y，Z)=(X?Y)?(X?Z)?(Y?Z) 其中，?是与，?是或，?是异或，?是非。 3.2 定制的Hash函数：SHA-1(续) SHA-1的压缩函数(续) 加法常量(十六进制) K1 =5a827999，对应0≤t≤19 K2 =6ed9eba1，对应20≤t≤39 K3 =8f1bbcdc ，对应40≤t≤59 K4 = ca62c1d6，对应60≤t≤79 字扩展 前16个字W0，W1，…，W15，直接由输入得到。其余由公式Wt=CLS1(Wt-3?Wt-8 ?Wt-14?Wt-16)依次得到。 3.3 定制的Hash函数：MD5 MD5是1992年由Rivest提出的无密钥Hash函数。MD5是MD4(1990年提出)的增强版本。MD5对任意长度的消息产生128比特的Hash值。MD4在280次压缩函数计算下已经找到了碰撞，因此，不在被推荐用做抗碰撞的Hash函数。近年来，MD5也发现了一些弱点。 3.3 定制的Hash函数：MD5(续) MD5算法的输入为任意比特长的消息，输出为128比特的消息摘要，算法处理过程如下图。 3.3 定制的Hash函数：MD5(续) MD5消息处理过程： (1) 消息填充。填充使得消息的比特长度为512比特的某个倍数减64，即使原始消息已满足要求，仍要填充。这样填充的比特数在1到512。填充方式是第一位为1其他位是0。最后64比特位用来填充消息被填充前的长度。如果消息长度大于264，则以264取模。这形成了长度为512比特的一系列分组Y0， Y1，… ，YL-1。 3.3 定制的Hash函数：MD5(续) (2) 初始化。MD5使用128比特的缓冲区存储中间和最终Hash值，可用4个32比特寄存器A，B，C，D表示，初始值为(十六进制) AB= 89abcdef，C=fedcba98，D 3.3 定制的Hash函数：MD5(续) (3) 处理。每个分组Yq经过压缩函数处理，压缩函数由4轮处理过程构成。每一轮又由16步迭代组成。4轮处理结构一样，但基本逻辑函数不同，分别为F，G，H，I 。每轮处理消息分组Yq和缓冲区A、B、C、D的当前值，输出仍放在对应缓冲区。每一轮处理有一个常量T[i]，其中i表示迭代步数，1≤i≤64。第4轮的输出与第1轮的输入CVq依4个缓冲区对应进行模232相加得到CVq+1。消息的L个分组都按上述计算处理完成后，最后一个分组的输出就是128比特消息摘要。 3.3 定制的Hash函数：MD5(续) 3.3 定制的Hash函数：MD5(续) 3.3 定制的Hash函数：MD5(续) MD5的压缩函数(续) 逻辑函数F，G，H，I分别定义为： F(X，Y，Z)=(X?Y)?(?X?Z) G(X，Y，Z)=(X?Y)?(Y?? Z) H(X，Y，Z)=X?Y?Z I(X，Y，Z)=Y?(X?? Z) T[i]定义为： T[i]=?232sin(i)?，i=1, 2,…,64，这里，i是弧度。 3.3 定制的Hash函数：MD5(续) MD5的压缩函数(续) MD5压缩的每个512比特消息分组要经过4轮处理，第1轮以其32比特连续分组的初始顺序使用，而第2至4轮处理按如下三个置换计算出的顺序使用： p2(i)=(1+5i)mod 16 p3(i)=(5+3i)mod 16 p4(i)=7i mod 16， 这里 i=0, 1,…,15。 3.3 定制的Hash函数：MD5(续) MD5的压缩函数(续) 4轮中每一步的循环左移位数见下表。 4.1 基于分组密码的Hash函数：CBC的MAC 4.1 基于分组密码的Hash函数：CBC的MAC(续) 4.1 基于分组密码的Hash函数：CBC的MAC (续) 评论. (1) 很明显，在生成CBC-MAC值(由运行CBC模式的分组密码构造的MAC)的计算中包括了不可求逆的数据压缩(本质上，CBC-MAC是整个消息的“短摘要”) ，因此CBC-MAC是一个单向变换。所有的分组密码加密算法的混合变换性质为这个单向函数变换增加了一个杂凑特点(也就是说，将MAC分布到MAC空间与分组密码加密算法将密文分布到密文空间同样均匀)。 (2) 如果考虑穷举密钥搜索攻击，可以考虑最后仅输出n比特中的m比特作为MAC数值。 (3) 单分组消息x1，x2的两个文本消息-MAC对(x1, H1)和(x2, H2)。对一个2分组的第三个消息x1z请求MAC值M，产生文本消息-MAC对(x1z, M)。由此，知新2分组的消息X=x2(H1?z?H2)的MAC值也是M。 (4) 可选处理减少了穷举密钥搜索攻击的威胁，阻止了选择文本攻击的存在性伪造，由于没有在整个过程中使用三重加密，所以不会特别影响效率。 由MDC算法构造MAC算法的一个建议是简单地把秘密密钥k作为MDC的输入的一部分。但因为MDC和MAC的定义并不完全一致，因此这种设计必须细致分析。 (1) 消息为x=x1x2…xt和使用迭代函数f的迭代MDC h：定义H0=IV；Hi=f(Hi-1, xi)，1?i?t；h(x)=Ht。 (1.1) 如果建议的MAC对x的值是M=h(kx)，则攻击者可以计算M?=h(kxy)=f(My)作为xy的MAC值。(1.2) 如果建议的MAC对x的值是M=h(xk)输出是n比特，则产生x和x?满足M=h(x?k)=h(xk)的复杂度为O(2n/2)，n是h函数的输出比特长度。 (2) 对密钥为k和MDC为h，可按如下方式计算消息x的MAC值hk(x)=h(kpxk)。其中p将用于将k填充为一个分组长度，从而保证内部至少进行两次分组计算。 (3) 对密钥为k和MDC为h，另一种计算消息x的MAC值的方式是hk(x)=h(kp1h(kp2x))。其中p1，p2用于将k填充为一个分组长度。 谢谢 ! 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) HMD5 IV (128比特) Y0(512比特) HMD5 Y1 CV1 (128比特) … HMD5 CVq Yq … CV2 HMD5 CVL-1 YL-1 消息摘要 3 无密钥密码Hash函数：MDC(续) 需要产生Hash值的消息 100…0 消息长度K mod 264 填充长度1-512比特 K比特 L×512比特=N×32比特 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) CVq128位 Yq512位 F, T[1…16], X[i], 16步 B A D C B A D C B A D C B A D C + + + + CVq+1128位 G, T[17…32], X[p2(i)], 16步 H, T[33…48], X[p3(i)], 16步 I, T[49…64], X[p4(i)], 16步 3 无密钥密码Hash函数：MDC(续) MD5的压缩函数 一步迭代压缩函数如下图。 A C B D + + + s + R A C B D X[k] T[i] R表示函数F、G、H、I中的一个，它们依次在连续16步中使用 s表示循环左移s比特 X[k] 表示在第q个长度为512比特分组中的第k个32比特分组 T[i] 表示常数中的第i个字 + 表示模232相加 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 21 15 10 6 21 15 10 6 21 15 10 6 21 15 10 6 4 23 16 11 4 23 16 11 4 23 16 11 4 23 16 11 4 3 20 14 9 5 20 14 9 5 20 14 9 5 20 14 9 5 2 22 17 12 7 22 17 12 7 22 17 12 7 22 17 12 7 1 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 步数 轮数 4 带密钥密码Hash函数：MAC M1 0 Ek H1 M2 Ek H2 … Ht-1 Mt Ek Ht Ek Dk Ht 可选 4 带密钥密码Hash函数：MAC(续) 4 带密钥密码Hash函数：MAC(续) 4 带密钥密码Hash函数：MAC(续) 4.1 基于分组密码的Hash函数：CBC的MAC(续) 4 带密钥密码Hash函数：MAC(续) 4.2 由MDC构造的MAC 4 带密钥密码Hash函数：MAC(续) 4.2 由MDC构造的MAC(续) * 1.1 基本性质与定义 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1.1 基本性质与定义(续) 1 分类与架构(续) 1.1 基本性质与定义(续) 1 分类与架构(续) 1.1 基本性质与定义(续) 1 分类与架构(续) 1.2 特定应用需要的性质 1 分类与架构(续) 1.3 性质之间的关系 1 分类与架构(续) 1.4 其他应用 2 基本构造 2.1 迭代结构的一般模型 输出 可选输出变换 迭代压缩函数 任意长度输入 固定长度输出 2 基本构造(续) 2.1 迭代结构的一般模型(续) f Hash函数h 初始输入x 预处理 附加长度分组 附加填充比特 迭代处理 压缩函数f Hi Hi-1 Ht g xi 输出h(x)=g(Ht) 格式化输入x=x1x2…xt 2 基本构造(续) 2.1 迭代结构的一般模型(续) 2 基本构造(续) 2.2 实际安全需要的输出比特大小 3 无密钥密码Hash函数：MDC 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) Eg(Hi-1) Eg(Hi-1) Mi CLi CRi CLi CRi CLi CRi CLi CRi Hi Hi 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) YL-1 3 无密钥密码Hash函数：MDC(续) HSHA IV (160比特) Y0(512比特) HSHA Y1 CV1 (160比特) … HSHA CVq Yq … CV2 HSHA CVL-1 消息摘要 需要产生Hash值的消息 100…0 消息长度K 填充长度1-512比特 K比特 L×512比特 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC(续) 3 无密钥密码Hash函数：MDC (续) 3 无密钥密码Hash函数：MDC(续) CVq160位 Yq512位 f1, K1, W[0…19] 20步 B A D C E f2, K2, W[20…39] 20步 B A D C E f3, K3, W[40…59] 20步 B A D C E f4, K4, W[60…79] 20步 B A D C E + + + + CVq+1160位 + 3 无密钥密码Hash函数：MDC(续) *