密码学基础 课件 第7章　消息认证与Hash函数

2学时消息认证与Hash函数——公钥密码的应用消息认证概述认证函数消息认证码Hash函数和MAC的安全性Hash算法主要内容机密性（Confidentiality）：确保信息不暴露给未经授权的人或应用进程。完整性（Integrity）：只有得到允许的人或应用进程才能修改数据，并且能够判别出数据是否已被更改。可用性（Availability）：只有得到授权的用户在需要时才可以访问数据，即使在网络被攻击时也不能阻碍授权用户对网络的使用。三种基本安全需求认证系统由认证编码器和认证译码器组成条件：指定的接收者能检验和证实消息的合法性、真实性和完整性发送者和接收者不能抵赖除了合法的发送者，其它人不能伪造消息认证系统第一节消息认证认证函数的特点：必须是单向函数对于一个特定消息，很难找到另外一个消息与其具有相同的认证码很难找到一对具有相同认证码的消息认证函数第一节消息认证认证函数可分为三类：消息加密：将整个消息的密文作为认证符；消息认证码（MAC）：是消息和密钥的公开函数，产生定长的认证符；Hash函数：将任意长的消息映射为定长的hash值的公开函数，该hash值则作为认证符。认证函数第一节消息认证消息认证码（MessageAuthenticationCode）：利用密钥生成固定长度的短数据块（MAC），将其附加在消息之后，也称为密码校验和（cryptographicchecksum）。MAC函数与加密的区别：不要求可逆性多对一不能用于数字签名第一节消息认证用消息认证码实现认证通过MAC，可以认证以下内容：

a.接收者可以确信所收到的消息M未被篡改；

b.接收者可以确信消息来自真实的发送者；

c.如果消息中包含顺序码(如X.25,TCP)，接收者可以确认消息的正常顺序。消息认证码第一节消息认证已知M和Ck(M)时，构造满足Ck(M’)=Ck(M)的消息M’在计算上不可行；Ck(M)应是均匀分布的，即对任何随机选择的消息M和M’，Ck(M’)=Ck(M)的概率是2-n，其中n是MAC的位数；设M’是M的某个已知的变换，即M’=f(M)，例如可令f

表示对M的一位或多位取反，那么

Pr[Ck(M’)=Ck(M)]=2-n

对MAC的要求第一节消息认证十进制移位加MAC算法

1980年，Sievi提出，称为十进制移位加算法(DecimalShiftandAddAlgorithm)简记为DSA，适用于金融支付中的数值消息交换业务，消息按十位十进制数字分段处理，不足十位时在右边以0补齐基于DES的MAC算法

两种：CBC模式和CFB模式。CBC模式是使用最广泛的一种，被美国作为数据认证算法(DataAuthenticationAlgorithm)，已被FIPS(FIPSPUB113)和ANSI(X9.17)作为标准。MAC算法第一节消息认证消息按64bit分组M1,M2,…,MN，不足时以0补齐，DES加密，设密钥为K，初始向量为0，计算如下：

O1=EK(M1)

O2=EK(M2XORO1)

O3=EK(M3XORO2) …

ON=EK(MNXORON-1)取加密结果最左边的r位作为认证码。r的大小由通信双方约定。第二节消息认证码MAC算法——CBC模式散列函数（HashFunction）：也称哈希函数，对任意长度的明文进行变换，得到相对应的函数值，称为散列值，或称散列值、消息摘要（MessageDigest）、指纹（Fingerprint），变换的过程称为散列变换。散列值的长度一般是固定的。用途：（1）消息鉴别码；（2）数字签名之前的预处理第二节散列函数第二节散列函数要求：对任意长度输入进行变换，得到固定长度输出求逆不可行对给定x，很难找到x’≠x，使得h(x’)=h(x)很难找到一对不同的x,x’，使得h(x’)=h(x)第二节散列函数对hash函数的要求满足条件（1）（2）的称之为单向散列函数(One-WayHashFunction)满足条件（1）~（3）的称之为弱散列函数（WeakHashFunction）或弱无碰撞的散列函数满足条件（1）~（4）的称之为强散列函数（StrongHashFunction）或强无碰撞的散列函数。对hash函数的要求第二节散列函数1978年，Rabin的方法利用DES的密码分组链接模式设计将明文M按M=m1m2…mn进行分组，mi为64bit，按DES的CBC模式依次对每个分组进行加密，令h0=初始向量，hi=Emi[hi-1]，加密过程不使用任何密钥，G=hn为最终得到的散列值。第二节Hash函数Hash函数举例散列函数用于签名时，假设签名消息为(x,y)，y=sigk(h(x))，则攻击者可用如下方式伪造攻击者计算Z=h(x)，找到x’≠x，但h(x’)=h(x)，则（x’,y）构成有效的签名；攻击者找到任意两个不同消息x’，x，满足h(x’)=h(x)，令签名者对h(x)签名，则（x’,h(x)）也是有效签名；攻击者伪造一个签名Z，若能计算h-1(Z)=x，则(x,h(x))为有效签名。对Hash函数的攻击第二节散列函数对hash函数的攻击可以看作是寻找碰撞的过程，攻击者的主要目标不是恢复原始的明文，而是用非法消息替代合法消息进行伪造和欺骗，。攻击方法：生日攻击、中间相遇攻击、穷举攻击第二节Hash函数对Hash函数的攻击攻击者通过一对已知的明文和散列值，就可以任意伪造其它明文的散列值，步骤如下：第一步，对已知明文M产生散列值G；第二步，将非法明文Q按Q=Q1Q2…Qn-2进行分组，每个分组长度为64bit；第三步，计算hi=EQi[hi-1]，1≤i≤n-2；第二节Hash函数中间相遇攻击第四步，产生232个不同的x，对每个x计算Ex[hn-2]，再任意产生232个不同的y，对每个y计算Dy[G]，D是对应于E的解密函数；第五步，找到一对对应的x和y，使得Ex[hn-2]=Dy[G]；第六步，生成新的明文Q′=Q1Q2…Qn-2xy。第二节Hash函数中间相遇攻击Merkle在1989年提出了散列函数的通用结构：

a.将原始消息M分成固定长度的分组(Block)Mi；

b.对最后一个分组MN填充，并附上原始消息M的长度，

使其长度等于固定长度；

c.设定链接变量(chainingvalue)的初始值CV0；

d.定义压缩函数f，CVi=f(CVi-1,Mi-1)；

e.循环操作N次，最后一个CVN为散列值。第二节Hash函数Hash函数的通用结构对hash函数的密码分析主要集中在f的内部结构进行分析，并试图找到能与f的执行产生碰撞的有效方法。第二节Hash函数密码分析2004年8月17日，美国加州圣巴巴拉，Crypto’2004。来自山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。第二节Hash函数密码分析CollisionsforHashFunctionsMD4,MD5,HAVAL-128andRIPEMDMD5SHA-1RIPEMD-160HMAC第三节Hash算法Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest完成MD5(RFC1321)现行美国标准SHA-1以MD5的前身MD4为基础第三节Hash算法MD5输出：128bit分组长度：512bit算法细节：填充→轮函数MD5总体特征第三节Hash算法Step1:Padding，

M→M’ |M’|448mod512 |M’|>|M|→

如果|M|448mod512,则|M’|=|M|+512

Padding内容:100…0第三节Hash算法MD5算法细节Step2:Append64-bitMessagelength，M’→M’’

若|M|>264,则仅取低64位

低字节在前(little-endian) |M’’|为512的倍数:M0,M1,…,ML-1第三节Hash算法MD5算法细节第三节Hash算法MD5paddingMessage1000…064bit(消息长度)512n+448bitStep3InitializeMDBuffer计算消息摘要时用到四个字的缓冲区(A，B，C，D)。A、B、C、D均为32-bit的寄存器。第一个分组进行第一轮运算时，用以下16进制数来初始化这四个寄存器：

A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210第三节Hash算法MD5算法Step44RoundDepression

定义四个非线性逻辑函数，每一轮用一个。这四个函数分别以3个32bit的变量为输入值，输出一个32bit的值。第1轮：F(X,Y,Z)=(XandY)or(not(X)andZ)

第2轮：G(X,Y,Z)=(XandZ)or(Yandnot(Z))

第3轮：H(X,Y,Z)=XxorYxorZ

第4轮：I(X,Y,Z)=Yxor(Xornot(Z))第三节Hash算法MD5算法第一轮的第一步开始时，将四个链接寄存器中的值复制到另外四个存储单元中：A到AA，B到BB，C到CC，D到DD。设M[k]表示消息的第k个子分组（从0到15），<<<s表示循环左移s位。每次操作对A、B、C和D中的三个作一次非线性函数运算，然后将所得结果加上第四个变量。再将所得结果向右循环移位，并加上A、B、C、D中的一个，用该结果取代A、B、C、D中的一个。第三节Hash算法MD5算法Step5output

第4轮的最后一步完成后，再作运算：

A=A+AA

B=B+BB

C=C+CC

D=D+DD

以上“+”均指mod232的加法运算。A、B、C、D的值作为下一个消息分组运算时的初始值；最后一个消息分组得到的输出A、B、C、D级联成为128bits的消息散列值。第三节Hash算法MD5算法MD5SHA-1RIPEMD-160HMAC第三节Hash算法SecureHashAlgorithm（安全hash算法）1992年NIST制定了SHA(128位)1993年SHA成为标准（FIPSPUB180）1994年修改产生SHA-1(160位)1995年SHA-1成为新的标准,作为SHA-1(FIPSPUB180-1)SHA-1要求输入消息长度<264输入分组长度为512，输出消息摘要长度为160位基础是MD4第三节Hash算法SHA-1Step1:PaddingM

M1|M1|448mod512|M1|>|M|

如果|M|448mod512,则|M1|=|M|+512Padding内容:100…0Step2:Append64-bitlengthM1

M2|M|<264高字节在前(big-endian)|M2|为512的倍数:Y0,Y1,…,YL-1第三节Hash算法SHA-1算法步骤Step3:InitializeMDbuffer(big-endian)

A=67452301(0x67452301) B=EFCDAB89(0xEFCDAB89) C=98BADCFE(0x98BADCFE) D=10325476(0x10325476) E=C3D2E1F0(0xC3D2E1F0)Step4:Compression CV0=IV

CVi=HSHA-1(CVi-1,Yi)Step5:Output MD=CVL第三节Hash算法SHA-1算法步骤SHA-1压缩函数第三节Hash算法Step4:CV0=IV, CVi=HSHA-1(CVi-1,Yi)(A0,B0,C0,D0,E0)(A,B,C,D,E),t0Round(A,B,C,D,E,K[t],W[t]) 0t<80(A,B,C,D,E)(A+A0,B+B0,C+C0,D+D0,E+E0)整个Round包含80次循环,每次处理32-bitW[t]=Yi[t] 0t<16W[t]=(W[t-16]W[t-14]W[t-8]W[t-3])<<<1 16t<80每组(16个)W[t]可由前一组W[t]直接计算第三节Hash算法SHA-1step4:overviewFourrounds: 0t<80

EE+f(t,B,C,D)+(A<<<5)+W[t]+K[t] BB<<<30 (A,B,C,D,E)(A,B,C,D,E)>>>32 f(t,B,C,D)=(B&C)|(B&D) 0t<20 K[t]=230sqrt(2) f(t,B,C,D)=BCD 20t<40 K[t]=230sqrt(3) f(t,B,C,D)=(B&C)|(B&D)|(C&D) 30t<60 K[t]=230sqrt(5) f(t,B,C,D)=BCD 60t<80 K[t]=230sqrt(10)第三节Hash算法SHA-1step4:overviewABCDABCD++++ftT[i]EES5WtKtS30第三节Hash算法SHA-1压缩函数A,B,C,D,E(E+f(t,B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D

其中，

A,B,C,D,E=缓冲区的5个字

t =步数，0<=t<=79 f(t,B,C,D)=步t的基本逻辑函数；

Sk =循环左移k位给定的32位字

Wt=一个从当前512数据块导出的32位字

Kt=一个用于加法的常量，四个不同的值，如前所述

+ =模232加第三节Hash算法SHA-1压缩函数SHA-1使用big-endian抵抗生日攻击:160位hash值没有发现两个不同的512-bit块,它们在SHA-1计算下产生相同的“hash”速度慢于MD5安全性优于MD5第三节Hash算法SHA-1总结欧洲RIPE(RACEIntegrityPrimitivesEvaluation)项目的结果RIPEMD为128位更新后成为RIPEMD-160基础是MD5第三节Hash算法RIPEMD-160输入为任意长度，分为512bit的组输出为160位算法步骤与MD5类似，包括5个步骤第三节Hash算法RIPEMD-160Step1:PaddingM

M1|M1|448mod512|M1|>|M|

如果|M|448mod512,则|M1|=|M|+512Padding内容:100…0Step2:Append64-bitlengthM1

M2|M|<264低字节在前(little-endian)|M2|为512的倍数:Y0,Y1,…,YL-1第三节Hash算法RIPEMD-160算法步骤Step3:InitializeMDbuffer(little-endian)

A=01234567(0x67452301) B=89ABCDEF(0xEFCDAB89) C=FEDCBA98(0x98BADCFE) D=76543210(0x10325476) E=F0E1D2C3(0xC3D2E1F0)Step4:Compression CV0=IV

CVi=HRIPE(CVi-1,Yi)Step5:Output MD=CVL第四节Hash算法RIPEMD-160算法步骤利用hash函数代替分组密码来设计MAC：Hash函数的执行速度比对称密码快可利用密码hash函数代码库美国或其他国家对hash函数没有出口限制，而对分组密码有出口限制第六节HMAC——基于hash函数的消息认证码HMACHMAC的设计目标