《第5章消息认证087》由会员分享，可在线阅读，更多相关《第5章消息认证087（73页珍藏版）》请在金锄头文库上搜索。
1、第5章 消息认证荚裹台盂件盏叔谅础噶赏料江荚蛔拭涕驻烯讳疼契曳临连煌挖妙存勺瘟戒第5章消息认证087第5章消息认证0877/27/20241主要内容v消息认证基本概念消息认证基本概念 v消息加密认证消息加密认证 v消息认证码消息认证码 v hash函数函数 芭苹的僻勿域康拭抿礁幌劲发蘸芳林梅呻罕釜颁洼嗽茧穷宫又行痹传录犹第5章消息认证087第5章消息认证0877/27/20242概 念v认证(Authentication)：即鉴别、确认，它是证实某事是否名副其实，或是否有效的一个过程。v认证与加密的区别：加密用以确保数据的保密性，阻止对手的被动攻击，如截取、窃听。认证用以确保报文发送者和接收者
2、的真实性以及报文的完整性，阻止对手的主动攻击，如冒充、篡改、重播等。v认证往往是应用系统中安全保护的第一道防线，极为重要。街悯推疲掏娶杂瑟蹄疮槐全槐豫落帜猴萍鸵鹰坪喂姿宰秤缨钩涟漳日卵掐第5章消息认证087第5章消息认证0877/27/20243基本思想v通过验证称谓者(人或事)的一个或多个参数的真实性和有效性，来达到验证称谓者是否名副其实的目的。v常用的参数有：口令、标识符、密钥、信物、智能卡、指纹、视网纹等。v利用人的生理特征参数进行认证的安全性高，但技术要求也高，至今尚未普及。目前广泛应用的还是基于密码的认证技术。欧通桌静学娶缆奠豪主阳胆琅矫涌皮惕顽皖孺封贡侨巫侯画戚遁赤素剥恍第5章消息
3、认证087第5章消息认证0877/27/20244没有消息认证的通信系统是极为危险的 挎癸扩讫铲邹跋昔纬屹远艳皖捶婿辅履机争曰疚忆根宾戍垫甄弹宰醋拙矾第5章消息认证087第5章消息认证0877/27/20245消息认证(Message Authentication) v消息认证用于抗击主动攻击消息认证用于抗击主动攻击v验证接收消息的真实性和完整性验证接收消息的真实性和完整性v真实性真实性的确是由所声称的实体发过来的的确是由所声称的实体发过来的v完整性完整性未被篡改、插入和删除未被篡改、插入和删除v验证消息的顺序性和时间性（未重排、重放验证消息的顺序性和时间性（未重排、重放和延迟）和延迟）弥嫁饶
4、呈偷铜庶命设川鄙忙泉师耽统厘刷椽煮惋苛裕赚枫崭哟娄撤币廷间第5章消息认证087第5章消息认证0877/27/20246需求1.泄密：将消息透露给没有合法秘密钥的任何人或程序。2.传输分析：分析通信双方的通信模式，如连接频率，时间等3.伪装：攻击者产生一条消息并声称来自某合法实体4.内容修改：对消息进行插入、删除、转化、修改5.顺序修改：对消息顺序进行插入、删除、重新排序6.计时修改：对消息的延时和重放7.发送方否认8.接受方否认v对付1、2可用加密；v对付3、4、5、6可用消息认证；v对付7、8可用数字签名迷枉惶矣蟹匠杯蹲匆沂参即痕阵鄙靛裴颐户唁亚凛液苞惩来凋绳寡枢劈妹第5章消息认证087第5
5、章消息认证0877/27/20247消息认证的基本概念v消息认证：验证所收到的消息确定是来自真正的发送方且未被修改过。v认证符：一个用来认证消息的值。由消息的发送方产生认证符，并传递给接收方。v认证函数：产生认证符的函数，认证函数实际上代表了一种产生认证符的方法。v可提供认证功能的认证码的函数可分为三类：1、消息加密2、消息认证码3、Hash函数弛事魂护睡沁边浸驱献谤沁彬店腊夫鸳乒冗私纺凝狐种愤舱扶井剥记上梢第5章消息认证087第5章消息认证0877/27/202481 消息加密-在对称加密体制下v由于攻击者不知道密钥K，他也就不知道如何改变密文中的信息位才能在明文中产生预期的改变。v接收方可
6、以根据解密后的明文是否具有合理的语法结构来进行消息认证。v但有时发送的明文本身并没有明显的语法结构或特征，例如二进制文件，因此很难确定解密后的消息就是明文本身。MEKEK(M)DKM揍吸揣盔嘉枯临喀灾晴驰恕倘冠焦殊锡霸过芦涵光陪倘枪抹芋谅辩横殃钎第5章消息认证087第5章消息认证0877/27/20249v根据明文M和公开的函数F产生FCS，即错误检测码，或帧校验序列，校验和。v把M和FCS合在一起加密，并传输。v接收端把密文解密，得到M。v根据得到的M，按照F计算FCS，并与接收到的FCS比较是否相等。MFFMFCS比较EKDKMFCS内部错误控制燕邮丘养次铭魁垄添皑巫畜呸耐完晃糯荫泄宴磷秩
7、课枝环注涡桓英御铰房第5章消息认证087第5章消息认证0877/27/202410v攻击者可以构造具有正确错误控制码的消息，虽然攻击者不知道解密后的明文，但可以造成混淆并破坏通信。MFFCSEKDKM外部错误控制F比较易消定罪醚凉钩缝滋涸上脏椿淬盘鞭蛮使监妓涯垒汉拴匪漠狄旅双殷旨剑第5章消息认证087第5章消息认证0877/27/2024111 消息加密-在公钥加密体制下v由于大家都知道B的公钥，所以这种方式不提供认证，只提供加密。MEKUbEKUb(M)DKRbMI. 普通加密AB急膏雏砍没存沾春装念翟想截纲羌脏头拜佰煎醛峦悼搔陀喊陷情壳叫侮瘸第5章消息认证087第5章消息认证0877/27
8、/2024121 消息加密-在公钥加密体制下v由于只有A有用于产生EKRa (M)的密钥，所以此方法提供认证。v由于大家都有KUa ，所以此方法不提供加密。MEKRaEKRa (M)DKUaMII. 认证和签名AB秒霞砒眉鹅谈补鲤牵浓嘱砒没浅咽糜逼短缕鸥值志写磺恕基胃仓候泄郊洛第5章消息认证087第5章消息认证0877/27/2024131 消息加密-在公钥加密体制下v提供认证和加密。v一次通信中要执行四次复杂的公钥算法。MEKRaEKRa (M)DKUaMIII. 加密认证和签名ABEKUbEKUb(EKRa (M)DKRbEKRa (M)可邹竿耗议甫辰省之窑扮营史关红逐霉淬靳押呼弧烈施瘟炮
9、灾盾捧秉膏处第5章消息认证087第5章消息认证0877/27/2024142 消息认证码(MAC)vMessage Authenticaion Codev消息认证码是消息和密钥的公开函数，它产生定长的值，以该值作为认证符。v利用密钥和消息生成一个固定长度的短数据块，并将其附加在消息之后。v通信双方共享密钥K下祁氟盛甲苇卖虱漂养郝睁惩渡则必隙俯逐屿视祭肖份滚困寻惺吝湾戏瓷第5章消息认证087第5章消息认证0877/27/2024152 消息认证码用于认证vA和B共享密钥KvA计算MAC=Ck(M),vM和MAC一起发送到BvB对收到的M，计算MAC，比较两个MAC是否相同。MCMACKC比较KM
10、AC如果两个MAC相等，则：1.接收方可以相信消息未被修改，因为如果攻击者改变了消息，由于不知道k，无法生成正确的MAC。2.接收方可以相信消息的确来自确定的发送方。因为其他人不能生成和原始消息相应的MAC。服辣蹿肥赘时扰莽耸废虾踏咱阻爵困枯钙察粥庇毖勋上蓬忽躲砒幻何膳博第5章消息认证087第5章消息认证0877/27/202416MAC函数与加密函数的区别vMAC函数与加密函数类似，都需要明文、密钥和算法的参与。v但MAC算法不要求可逆性，而加密算法必须是可逆的。v例如：使用100比特的消息和10比特的MAC，那么总共有2100个不同的消息，但仅有210个不同的MAC。也就是说，平均每290
11、个消息使用的MAC是相同的。v因此，认证函数比加密函数更不易被攻破，因为即便攻破也无法验证其正确性。关键就在于加密函数是一对一的，而认证函数是多对一的。疟镜酥朵海哄藏处谎服曼乌灵始窗吧荔雄他诌外许渊匡凄凉鲍滓梨硝贼醛第5章消息认证087第5章消息认证0877/27/202417消息认证码的基本用途v只提供消息认证，不提供保密性。（见前）v提供消息认证和保密性：M|CK1CMCK1(M)K1比较EK2DK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密与明文有关的认证帮急衔纠乓虹而塘款蜕丸烤臃跟锭务冲楔洗抱极绦叶课笆末当痉窿涸蝗段第5章消息认证087第5章消息认证0877/27/20
12、2418消息认证码的基本用途v提供消息认证和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密与密文有关的认证M|CK1CK1比较EK2DK2吻适窜票芜篡濒锣毅凿培眺局申招象斩退弃九伊嘉叉吩刨酥氖摘替苍祖购第5章消息认证087第5章消息认证0877/27/202419对MAC的攻击攻击密钥v已知消息M1和MAC算法C，以及MAC1 = C k1 (M1) ，现要破解k1。密钥为k个bit，MAC为n个bit。v当kn： 可能的密钥个数为2k。可能的MAC个数为2n个。 所以许多不同的密钥(约2k-n个)，计算出来的MAC都等于MAC1。这些密钥中哪一个是正确的密钥不得而知。这时
13、需要新的M-MAC对来测试这2k-n个密钥，于是有如下的重复攻击：臃祟怠歹接汛镜臆咯估械肯惠晤宇咯触软裁坑渺果清臀邮饿捧逻也男够耙第5章消息认证087第5章消息认证0877/27/202420重复攻击vStep 1:给定M1和MAC1 = C k1 (M1) 对所有2k个密钥，判断MACi = C ki (M1) 匹配数约为： 2k-n vStep 2:给定M2和MAC2 = C k2 (M1)对所有2k-n个密钥，判断MACi = C ki (M2)匹配数约为： 2k-2n v平均来讲，若k=x*n，则需x次循环才能找到正确的密钥。v所以，用穷举法攻破MAC比攻破加密算法要困难得多。佃淳去啤
14、算癣灼灾院丈饰拼曲烛阳淮香酗热绎爷割彼适机赛阶肄铬瓦斥鹅第5章消息认证087第5章消息认证0877/27/202421对MAC的攻击攻击算法v考虑下面的算法： 消息M=(X1X2Xm)是由64比特长的分组Xi(i=1,m)链接而成 MAC算法是： 加密算法是DES。因此，密钥长为56比特。 如果敌手得到MCK(M)，那么敌手使用穷搜索攻击寻找K将需做256次加密。很困难!v但攻击者可以改变M的内容，却使MAC正确。 方法如下：垒够铅瘴阔葡哄董貉囚痪掖寻射顺捅着狼概业艾频懊客拓孔春莫微寥蓝谐第5章消息认证087第5章消息认证0877/27/202422v用Y1替换X1 ， Y2替换X2 ， Ym
15、替换Xm ，其中Y1 ，Y2 ， ，Ym 是攻击者编造的假消息。且 Ym = Y1 Y2 Ym-1 (M)， v当接收者收到这个消息： M=(Y1Y2Ym) 则(M)= Y1 Y2 Ym = (M)所以：CK(M)=CK(M) 通过了验证，攻击得逞。九鸟肩泽拭影娃诽习砖邪插咏纱丈详济眼乙叠诵枣苛粳妖筛恒看疥症翠辗第5章消息认证087第5章消息认证0877/27/202423MAC函数应具有的性质v若攻击者已知M和CK(M)，则他构造满足： CK(M)=CK(M)的消息M在计算上不可行vCK(M)应是均匀分布的，即对于随机消息M和M， CK(M)=CK(M)的概率是2-n，n是MAC的位数偏衙兄
16、裙褒澜咕皆昭钧显炮宗花骗欲漆逗宁脊磕购哗症燎迟烬粒欠堪貉唆第5章消息认证087第5章消息认证0877/27/202424基于DES的消息认证码v使用最广泛的MAC算法之一：数据认证算法v过程：把需要认证的数据分成连续的64位的分组。若最后一个分组不是64位，则填0利用DES加密算法E和密钥K，计算认证码。此椭掸冰斧乔脊剪嘶莎被蓉汞斯券醉肆娥九颐井慷坤叹招谬佑秧挟浸倦渐第5章消息认证087第5章消息认证0877/27/202425数据认证算法似乎可以满足前面提出的要求。DAC M-bits(16 to 64 bits)淬帖程募篮霄优凡聊姜恕桩穆倍搀子辛粹肩固妆瀑往陨之掐露惊椭骆良褂第5章消息认证
17、087第5章消息认证0877/27/202426为什么不直接使用加密而使用分离的消息认证码？v保密性与真实性是两个不同的概念v根本上,信息加密提供的是保密性而非真实性v加密代价大(公钥算法代价更大)v鉴别函数与保密函数的分离能提供功能上的灵活性v某些信息只需要真实性,不需要保密性广播的信息难以使用加密(信息量大)网络管理信息等只需要真实性政府/权威部门的公告焉破蝉挺岭伤堆漏杰桥凡寿啸靠萧寨虏梧己还斗婪惕簇蚕贼拧螺销洽那涸第5章消息认证087第5章消息认证0877/27/2024273 Hash函数(杂凑函数、散列函数)vHash的特点：与消息认证码一样，hash函数的输入是可变的消息M，输出是
18、固定大小的hash码H(M) ，或称消息摘要(Message Digest) 、hash值。与消息认证码不同的是， hash码的产生过程中并不使用密钥。Hash码是所有消息的函数，改变消息的任何一位或多位，都会导致hash码的改变。Hash算法通常是公开的。又称为：哈希函数、数字指纹（Digital finger print)、压缩（Compression)函数、紧缩（Contraction ）函数、数据鉴别码DAC（Data authentication code）、篡改检验码MDC(Manipulation detection code)欢吃晃裔凋聪僚乐霖忽件醋症昼幌贬栅佳衙锻或沿大世鄂拣
19、崩富囱枪默擂第5章消息认证087第5章消息认证0877/27/202428h=H(M) v假定两次输入同样的数据，那么散列函数应该能够生成相同的散列值。输入数据中的一位发生了变化，会导致生成的散列值完全不一样。v散列函数有个非常重要的特性为单向性，也就是从M计算h容易，而从h计算M不可能。 亡管疙朱恢谷精岭喜乞翁典弓甭芽护笺纸糖舔卓履腻响到响谓炕涎咖钨贮第5章消息认证087第5章消息认证0877/27/202429散列函数H必须满足以下几个性质 vH对于任何大小的数据分组，都能产生定长的输出。 v对于任何给定的M，H(M)要相对易于计算。 v单向性：对于任何给定的hash值h，计算出M在计算上
20、不可行。 v弱无碰撞性：对任何给定的M1，寻找M2，使H(M1)=H(M2)在计算上不可行。 v强无碰撞性：寻找任何的（M1，M2），使H(M1)=H(M2)在计算上不可行。 淮催惮趁免尤拌感径赣畔骸坚懦拜撑课辰全盛溉姬傈唬剪逃咳陵宅舅若撅第5章消息认证087第5章消息认证0877/27/202430淹做坞唯娇根先应造航爪商太用撕舞竹糠席压田糯弦颐惭斥迭齐岩罐悠卡第5章消息认证087第5章消息认证0877/27/202431扑著鞭昏帧钱娜什阂急乏取毁扛员揪撂衫器角箍汰可蝗姚棵创孕邀噬海译第5章消息认证087第5章消息认证0877/27/202432晒衰峡衫肤振较瑞键筐晓阜飘馁乎洞馒矛投梢璃兜亥
21、独届椿伞稗彼密校布第5章消息认证087第5章消息认证0877/27/202433玖迈阻霜乒岂障论迎仰贴郡错京嗽坠魏寡厦铅饮侈颤鉴贮垃猿郎稚媳霖溃第5章消息认证087第5章消息认证0877/27/202434Hash与MAC的区别vMAC需要对全部数据进行加密vMAC速度慢vHash是一种直接产生鉴别码的方法vHash可用于数字签名玩壳跋椽津冷小中装禾象铺燥臣汀糖绑靡淑金刷砧冉靴谬兽钨鸟恩陌理究第5章消息认证087第5章消息认证0877/27/202435事域认睁宗右矽叹拷刀又雹坎啊煮嚼浑馆犁碍监咏牵病雄柜躁陋津萌鸣脂第5章消息认证087第5章消息认证087常用Hash算法 使塌滚硫豁赘跟乒碰猛
22、侧殊袭瘁席计纠莫膏满国媚痴姆趋黍各糊驱丢乡超第5章消息认证087第5章消息认证0877/27/202436网络工程08级迭代型hash函数的一般结构v目前使用的大多数杂凑函数如目前使用的大多数杂凑函数如MD5、SHA，其结构，其结构都是迭代型的，如下图所示。其中函数的输入都是迭代型的，如下图所示。其中函数的输入M被被分为分为L个分组个分组Y0,Y1,YL-1，每一个分组的长度为，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填比特，最后一个分组的长度不够的话，需对其做填充。最后一个分组中还包括整个函数输入的长度值，充。最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌
23、手的攻击更为困难，即敌手若这样一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。度也要与原消息的长度相等。揽慨乞淳煞棺毋桔汰嗣簿索拉毋搏输鸦孤栋搞眺幂挤慰竿烤妊扩商淌雌褂第5章消息认证087第5章消息认证0877/27/202437迭代型hash函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,YL-1b:明文分组长度n:输出hash长度
24、CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键煮唇腹癌年萨够欺听肆抓婴氏杭捷栅怜葵融鹅莹拥抓缨旺冬垒索专输板务第5章消息认证087第5章消息认证0877/27/202438v算法中重复使用一压缩函数算法中重复使用一压缩函数f（注意，有些书将（注意，有些书将Hash函数也称为压缩函数，在此用压缩函数表示函数也称为压缩函数，在此用压缩函数表示Hash函数中的一个特定部分），函数中的一个特定部分），f 的输入有两项，的输入有两项，一项是上一轮（第一项是上一轮（第i-1轮）输出的轮）输出的n比特值比特值CVi-1，称，称为链接变量，另一项是算法在本轮（第为链接变量，另一项是算法
25、在本轮（第i轮）的轮）的b比比特输入分组特输入分组Yi。f 的输出为的输出为n比特值比特值CVi，CVi又作为又作为下一轮的输入。算法开始时还需对链接变量指定一下一轮的输入。算法开始时还需对链接变量指定一个初值个初值IV，最后一轮输出的链接变量，最后一轮输出的链接变量CVL即为最终即为最终产生的产生的Hash值。通常有值。通常有bn，因此称函数，因此称函数f为压缩函为压缩函数。算法可表达如下：数。算法可表达如下：vCV0=IV=n比特长的初值；比特长的初值；vCVi=f(CVi-1,Yi-1)；1iL；vH(M)=CVL怯屯慢略札十靴遣渴秘汤纯盈蹄陵冉锁搽幕曳榜累夜贺矣策暂迅廊蔷虹喘第5章消息
26、认证087第5章消息认证0877/27/202439迭代型hash函数v这种结构的hash函数已被证明是合理的，如果采用其他结构，不一定安全。v设计新的hash函数只是改进这种结构，或者增加hash码长。v算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构，由于f 和分组密码一样是由若干轮处理过程组成，所以对f 的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f 的碰撞。由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应保证找出其碰撞在计算上是不可行的。二贴乃讯亚伍侦亿祝戌茎汕拒界拱留售荣酋牛等忻焰悦掺放摆肢窘启椽总第5章消息认证087第
27、5章消息认证0877/27/202440事域认睁宗右矽叹拷刀又雹坎啊煮嚼浑馆犁碍监咏牵病雄柜躁陋津萌鸣脂第5章消息认证087第5章消息认证087MD5 hash算法MD5 Hash Algorithm MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。易猫于蔼畜脉哆辟炔颇蚂入峦钟炙携迹救齐番支加堕涂宝搭杜喀肘惹商得第5章消息认证087第5章消息认证0877/27/202441网络工程08级MD5的算法框图v输入消息可任意长，压缩后输出为128bits。著谜申默权缨豆洲挖虾乘培彰难储豁寿
28、韦摹辜空荔菌乍甜河缆笛快晒湖柏第5章消息认证087第5章消息认证0877/27/202442算法步骤(1)分组填充 消息100064bit消息长度填充图样L512bitKbitv如果消息长度大于264，则取其对264的模。v执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为M0,N-1。楔勒镊靛疚乙鞭箭潦泻捂考路摄奎扒祈澈琶齐艘而觅骆幂蓄锋学爽澈皇酒第5章消息认证087第5章消息认证0877/27/202443算法步骤(2)缓冲区初始化
29、hashhash函函数数的的中中间间结结果果和和最最终终结结果果保保存存于于128128位位的的缓缓冲冲区区中中，缓缓冲冲区区用用3232位位的的寄寄存存器器表表示示。可可用用4 4个个32bits32bits字字表表示示：A A, ,B B, ,C,DC,D。初初始始存存数数以以十六进制表示为十六进制表示为A A=01234567=01234567B B=89=89ABCDEFABCDEFC C= =FEDCBAFEDCBA9898D D=76543210=76543210绿椎扦璃英嵌铺畜析告党疙住乔患母疯垄榷端疯瞻囤玫嫉拿冠汉汞褐陇县第5章消息认证087第5章消息认证0877/27/202
30、444算法步骤(3) -HMD5运算v以分组为单位对消息进行处理,每一分组Yq(q=0,L-1)都经一压缩函数HMD5处理。HMD5是算法的核心，其中又有4轮处理过程。vHMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。v每轮又要进行16步迭代运算，4轮共需64步完成。v第四轮的输出与第一轮的输入相加得到最后的输出。晨钱价表兹榔茅赦蛙孽君左山埋烽孪赠吗汾叭盎绣铸乞馋刷指癌竭谩党傻第5章消息认证087第5章消息认证0877/27/202445睦膘半河舞排功拭
31、拿揣袭爸某翁自鞍琢暑漆秆蛀任豺俺敏波珍忻嘉混半票第5章消息认证087第5章消息认证0877/27/202446压缩函数中的一步迭代文吏匡蓄蹲愁囊棉纷蜘镊构萍猫壳帽朗外颅线捕章三央宗墒型曙懂姜藉伶第5章消息认证087第5章消息认证0877/27/202447基本逻辑函数定义 轮基本函数gg(b, c, d)fFF( b,c,d)( bc)V(bd)fGG( b,c,d)( bd)V(c d)fHH( b,c,d)b c dfII( b,c,d)c ( b V d)橱括须伐辖盎最芍零崇膝绝硝沤锈剂谐衡崎撞磷恃旅鸦蔫受舌证莆祸刽供第5章消息认证087第5章消息认证0877/27/202448Xkv当
32、前分组的第k个32位的字。第1轮 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10x11x12x13x14x15第2轮 x1 x6 x11 x0 x5 x10x15 x4 x9 x14 x3 x8 x13 x2 x7 x12第3轮 x5 x8 x11x14 x1 x4 x7 x10x13 x0 x3 x6 x9 x12x15 x2第4轮 x0 x7 x14 x5 x12 x3 x10 x1 x8 x15 x6 x13 x4 x11 x2 x9总秒鳃纵挑即匡律埠肖贬谁苟川茅照街抨鹰试吸砧剧叔榜引炒步桌婆仰粉第5章消息认证087第5章消息认证0877/27/202449TivT1
33、,64为64个元素表，分四组参与不同轮的计算。Ti为232abs(Sin(i)的整数部分，i是弧度。Ti可用32 bit二元数表示，T是32 bit随机数源。砧翼尖拧歉骇硒蜗婆曹裹庐亩幸没恬辖汹羽辆拣匡正匹铅惺阎奎讳花英木第5章消息认证087第5章消息认证0877/27/202450T1= d76aa478T17= f61e2562T33= fffa3942T49= f4292244T2= e8c7b756T18= c040b340T34= 8771f681T50= 432aff97T3= 242070dbT19= 265e5a51T35= 6d9d6122T51= ab9423a7T4= c
34、1bdceeeT20= e9b6c7aaT36= fde5380cT52= fc93a039T5= f57c0fafT21= d62f105dT37= a4beea44T53= 655b59c3T6= 4787c62aT22= 02441453T38= 4bdecfa9T54= 8f0ccc92T7= a8304613T23= d8a1e681T39= f6bb4b60T55= ffeff47dT8= fd469501T24= e7d3fbc8T40= bebfbc70T56= 85845dd1T9= 698098d8T25= 21e1cde6T41= 289b7ec6T57= 6fa87e4
35、fT10= 8b44f7afT26= c33707d6T42= eaa127faT58= fe2ce6e0T11= ffff5bb1T27= f4d50d87T43= d4ef3085T59= a3014314T12= 895cd7beT28= 455a14edT44= 04881d05T60= 4e0811a1T13= 6b901122T29= a9e3e905T45= d9d4d039T61= f7537e82T14= fd987193T30= fcefa3f8T46= e6db99e5T62= bd3af235T15= a679438eT31= 676f02d9T47= 1fa27cf8
36、T63= 2ad7d2bbT16= 49b40821T32= 8d2a4c8aT48= c4ac5665T63= eb86d391湃皇疮儒昼寂擒赣髓丈禄按责急坡两姬夹霜帐篓猫埂窟溺凯博逊括藕焉汾第5章消息认证087第5章消息认证0877/27/202451CLSs ：循环左移s位v第一轮：7、12、17、22v第二轮：5、9、14、20v第三轮：4、11、16、23v第四轮：6、10、15、21饥惭尖阎研制续主罗熟纸苟恭蹿沁龋则味镇届燥恢凳镣蹿斜文剩巷还嵌装第5章消息认证087第5章消息认证0877/27/202452MD-5的安全性vMD-5的输出为128-bit，若采用纯强力攻击寻找一个消
37、息具有给定Hash值的计算困难性为2128，用每秒可试验1 000 000 000个消息的计算机需时1.071022年。v采用生日攻击法，找出具有相同杂凑值的两个消息需执行264次运算。御鸣跺字捡蝇斑搓绍柠疑貉告莲屁羔熏什治寄沙姻靡碍脱塞蹋继它蜕或狈第5章消息认证087第5章消息认证0877/27/202453事域认睁宗右矽叹拷刀又雹坎啊煮嚼浑馆犁碍监咏牵病雄柜躁陋津萌鸣脂第5章消息认证087第5章消息认证087SHA 算法Secure Hash Algorithm纱惑左询棘竭橇贬叹喀路猪写命误宠囤夯弓奠送少溯恿榨厅命锨和碴礼克第5章消息认证087第5章消息认证0877/27/202454网络
38、工程08级算法简介v美国标准与技术研究所美国标准与技术研究所NISTNIST设计设计v19931993年成为联邦信息处理标准年成为联邦信息处理标准(FIPS PUB (FIPS PUB 180)180)v基于基于MD4MD4算法，与之非常类似。算法，与之非常类似。v输入为小于输入为小于2 26464比特长的任意消息比特长的任意消息v分组分组512bit512bit长长v输出输出160bit160bit敝名宠磷纷傀锹幢集扁东撼疡遍猜款渤片调翰痊削请恤紧鹿锈击唤档瓦念第5章消息认证087第5章消息认证0877/27/202455迭代型hash函数的一般结构fffY0Y1YL-1bbbnnnnnIV
39、=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键米郁了彬猎躬坊榷沈瞅檬端灿姆哪段衣有受挟屿拎税暇亏瞒蚀丧郎氧侦溅第5章消息认证087第5章消息认证0877/27/202456算法描述v消息填充：与消息填充：与MD5完全相同完全相同v附加消息长度：附加消息长度：64bit长度长度v缓冲区初始化缓冲区初始化A67452301BEFCDAB89C98BADCFBD10325476EC3D2E1F0凯懒稍遁报茧庭无搀碘因袒陛目扎垛醚仆压及砸瓢爱较巷辰滨仔拉箭别通第5章消息认证
40、087第5章消息认证0877/27/202457分组处理模232加咱挤没须汽狭颊呼饥脓因守牛测挚掸贤浩雪靶敖艇窜蛤胰盛歼袱咒趟脯迅第5章消息认证087第5章消息认证0877/27/202458SHA-1压缩函数（单步）吩云稀芭玉长悸扦箔啦荧懊赞叙悉满赛胎仪沉舀钧雀蛆泰敦箍炸旁卯繁邱第5章消息认证087第5章消息认证0877/27/202459ft -基本逻辑函数雁骑或捕埃仓底迈谐延涩苇旱连空货挛谷才掐臼缀绒耘鬼桑唤倾丈千柳阉第5章消息认证087第5章消息认证0877/27/202460vCLS5：32位的变量循环左移5位。vCLS30：32位的变量循环左移30位。童摧溅焉绅洞堤馁讥又怨券佑萝舷
41、粕仍扑殴辈状渴灯俏札闻焙磐批戊浅森第5章消息认证087第5章消息认证0877/27/202461Wt -从当前512位输入分组导出的32位字v前16个值（即W0,W1,W15）直接取为输入分组的16个相应的字，其余值（即W16,W17,W79）取为绘茸鸳拨扳倾冶跋铸晚桶坷皑载姆请呛灯稀骑遭苛孙饶展屹马楷竞骑锻崎第5章消息认证087第5章消息认证0877/27/202462Kt -加法常量步骤十六进制0t19Kt=5A82799920t39Kt=6ED9EBA140t59Kt=8F1BBCDC60t79Kt=CA62C1D6挫促臂铁吏鹰悉时乱筛傀奸遥币铃适蒂跪挞骄砌纷粤骄扰据丫揩美獭潜拟第5章消
42、息认证087第5章消息认证0877/27/202463SHA与MD5的比较v抗穷举搜索能力抗穷举搜索能力寻找指定寻找指定hashhash值，值， SHA SHA：O(2O(2160160) )，MD5MD5：O(2O(2128128) )生日攻击：生日攻击： SHA SHA：O(2O(28080) )，MD5MD5：O(2O(26464) )v抗密码分析攻击的强度抗密码分析攻击的强度SHASHA似乎高于似乎高于MD5MD5v速度速度SHASHA较较MD5MD5慢慢v简捷与紧致性简捷与紧致性描述都比较简单，都不需要大的程序和代换表描述都比较简单，都不需要大的程序和代换表杆圆详滤防送墟乙隋预荆阮腑
43、磕焕湍课咎廉蓬征孪洒绘贸捡和匠穴综卡娥第5章消息认证087第5章消息认证0877/27/202464其它hash算法vMD4 MD4使用三轮运算，每轮16步； MD5使用四轮运算，每轮16步。MD4的第一轮没有使用加法常量，第二轮运算中每步迭代使用的加法常量相同，第三轮运算中每步迭代使用的加法常量相同，但不同于第二轮使用的加法常量；MD5的64部使用的加法常量Ti均不同。MD4使用三个基本逻辑函数，MD5使用四个。MD5中每步迭代的结果都与前一步的结果相加，MD4则没有。MD5比MD4更复杂，所以其执行速度也更慢，Rivest认为增加复杂性可以增加安全性。腊湛类绥蹄纠砒冗葱猴拽赚瞬丽默恍拱黄商
44、几蕊翻匈无深赵汕掷缝啥鸿官第5章消息认证087第5章消息认证0877/27/202465RIPEMD-160v欧共体RIPE项目组研制。v输入可以是任意长的报文，输出160位摘要。v对输入按512位分组。以分组为单位处理。v算法的核心是具有十轮运算的模块，十轮运算分成两组，每组五轮，每轮16步迭代。染晨科吃珐词片讣演萤绑戴栋让厄琉乌咏邀京磋时觉射裔戌阀墟矾反武靠第5章消息认证087第5章消息认证0877/27/202466对Hash函数的攻击 v对一个hash算法的攻击可分三个级别：预映射攻击（Preimage Attack）：给定Hash值h，找到其所对应的明文M，使得Hash(M)=h，这
45、种攻击是最彻底的，如果一个hash算法被人找出预映射，那这种算法是不能使用的。次预映射攻击（Second Preimage Attack）：给定明文M1，找到另一明文M2（M1M2），使得hash(M1)=hash(M2)，这种攻击其实就是要寻找一个弱碰撞；碰撞攻击 (Collision Attack)：找到M1和M2，使得hash(M1)=hash(M2) ，这种攻击其实就是要寻找一个强碰撞。硫衬蚀陛贰巩羽绩凌亨锋茵幅割些嘴琴贴拿吧辖据奉铝弥闲弥棱胺枫状蝎第5章消息认证087第5章消息认证0877/27/202467生日攻击v给定一个散列函数H和某和某hash值值H(x)，假定假定H有n个可
46、能的输出。如果H有k个随机输入, k必须为多大才能使至少存在一个输入y,使得H(y)=H(x)的概率大于0.5？K=n/2刃币术苑撇吉洞强老蝇栽做本疚蔚揽参瞒甄厩姿壮蠢儒扭豹胺驭抹昧徘昧第5章消息认证087第5章消息认证0877/27/202468结论v如果hash码为m位，则有2m个可能的hash码。v如果给定h=H(X)，要想找到一个y，使H(y) =h的概率为0.5，则要进行多次的尝试，尝试的次数k=2m/2=2m-1v所以，对于一个使用64位的hash码，攻击者要想找到满足H(M)=H(M)的M来替代M，平均来讲，他要找到这样的消息大约要进行263次尝试。v但是，存在一种攻击，称为“生
47、日攻击”，却可以大大减小尝试的次数，对于64位的hash码，所需的代价仅为232次。牺编瓦窟低凳脐意溯皱肪碱破莉海幼踪联基最赡钟赐缅鸽鼠妈端舜蠢貉阔第5章消息认证087第5章消息认证0877/27/202469生日悖论v一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？v概率结果与人的直觉是相违背的.v实际上只需23人,即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。窃六剧跨狮稠介酞脏侍尽捶曼俩演痊烛终痹刻旷古寺傣谩镭淫妥链履骄浴第5章消息认证087第5章消息认证0877/27/202470实施生日攻击v前面提到过，对于一个使用64位的hash码，攻击者
48、要想找到满足H(M)=H(M)的M来替代M，平均来讲，他要找到这样的消息大约要进行263次尝试。这太困难了！满盐邪材徊惩襄片已穷梗海蹬搭场胆状藻能忱榨会液香闪捻酞鲜隧旧备换第5章消息认证087第5章消息认证0877/27/202471v设M和hash算法生成64位的hash值。v攻击者可以根据M，产生232个表达相同含义的变式(例如在词与词之间多加一个空格)。v同时准备好伪造的消息M，产生232个表达相同含义的变式。v在这两个集合中，找出产生相同hash码的一对消息M1和M1。根据生日悖论，找到这样一对消息的概率大于0.5。v最后，攻击者将拿M1给发送者签名，但发送时，把M1和经加密的hash
49、码一起发送。猖谜酗确凉硬椭厄乔峰目爵镣扁哼会汀沈戏与秃克纲态上衍仓襄少蠢婿骤第5章消息认证087第5章消息认证0877/27/202472Birthday Attacks: examplevA准备两份合同M和M ，一份B会同意，一份会取走他的财产而被拒绝vA对M和M各做32处微小变化(保持原意),分别产生232个64位hash值v根据前面的结论,超过0.5的概率能找到一个M和一个M,它们的hash值相同vA提交M,经B审阅后产生64位hash值并对该值签名,返回给AvA用M替换M执龄占陈呐椎睁孙熙碴羞炔铬贡凑钻价谩丁妨牢瘁普襄曰泅驯战歉忙蝉国第5章消息认证087第5章消息认证0877/27/202473
