现代密码学09---安全协议

现代密码学林喜军中国海洋大学信息安全实验室安全协议第9章2本章内容39.1安全协议概述9.2认证协议9.3秘密共享9.4零知识证明9.1安全协议概述45两个或两个以上的参与者为完成某项特定任务而采取的一系列步骤什么是协议•在日常生活中，几乎所有的事情都有非正式的协议–电话订货–下棋、玩扑克–选举投票•没有人认真考虑过这些协议，它们随时间的推移而发展，人们都知道怎样使用它们，而且它们也很有效6①协议自始至终是个有序的过程，每个步骤必须执行，在前一步没有执行完之前，后面的步骤不可能执行②协议至少需要两个参与者③通过协议必须能够完成某项任务协议的主要特点①参与者必须了解协议，并且预先知道所要完成的所有步骤②参与者必须同意遵循协议③每一步必须明确定义，并且不会引起误解④必须是完整的，对每种可能的情况必须规定具体的动作协议的其他特点7•协议必须把所有不利条件事先都估计到，而不能假定一切都是正常的和非常理想的。•看一个协议是否正确，不能光看在正常情况下是否正确，而且还必须非常仔细地检查这个协议能否应付各种异常情况。协议很复杂考虑不利条件不能假定一切正常能否应付异常情况8明日正午进攻，如何？同意收到“同意”收到：收到“同意”………………这样的协议无法实现！两军问题（拜占庭将军问题）9•结论–这样无限循环下去，两边的蓝军都始终无法确定自己最后发出的电文对方是否已经收到。–没有一种协议能使蓝军100%获胜。有些问题考虑太全面则无法解决10《庄子·盗跖》：尾生与女子期于梁下，女子不来，水至不去，抱梁柱而死。有些问题考虑不全面会导致严重后果11又称密码协议，使用密码技术完成某项特定任务，并满足安全需求的协议。什么是安全协议在安全协议中，经常使用对称密码、公钥密码、Hash函数、伪随机序列发生器等密码工具。12•机密性•完整性•认证性•非否认性•公平性•匿名性…安全协议的安全性要求这些要求根据应用场合不同进行组合13安全协议的应用•电子商务–信用卡交易–电子支票,电子货币–电子拍卖–网上银行•电子政务•电子选举…14安全协议中的角色•协议参与者•攻击者–内部/外部攻击者–被动/主动攻击者•可信第三方(TTP,TrustedThirdParty)–用户都信任的实体，通常与每个用户共享密钥–功能：使用户之间确认彼此身份或共享会话密钥15Dolev-Yao攻击者模型攻击者能做哪些事，不能做哪些事在设计和分析安全协议时，必须明确一点：16•攻击者能做到的事：–能截获经过网络的任何消息–以合法参与者身份，发起与任何用户的对话–有机会成为任何主体发出消息的接收者–能够冒充任何别的主体给任意主体发消息17•攻击者不能做到的事：–不能猜到从足够大的空间中选出的随机数–没有正确的密钥，不能由给定的密文恢复出明文；也不能从给定的明文构造出正确的密文–不能从公钥计算出相应的私钥–不能控制计算环境中的许多私有区域，如离线的存储器18•在现实世界中，–你会交给陌生人一叠现金替你买东西吗？–你没看到别人洗牌和发牌，会和他玩三国杀吗？–没有匿名的保证，你会在选举中投反对票吗？•网络上的协议参与者可能是完全信任的人，也可能是攻击者和完全不信任的人。•假设使用网络的人都是诚实的想法，是天真的。天真的想法还有：–假设网管是诚实的，假设网络设计者是诚实的。19安全协议设计与分析的困难性①安全目标本身的微妙性–表面上十分简单的目标，实际上十分微妙②运行环境的复杂性–实际上,当安全协议运行在一个十分复杂的公开环境时,攻击者处处存在③攻击者模型的复杂性–必须形式化地描述攻击者的能力，对攻击者和攻击行为进行分类和形式化的分析④安全协议本身具有“高并发性”20好的安全协议应满足的条件①满足目标(应用目标,安全目标)②易于实现③各参与者所需计算量小、存储量小④通信负载小(延迟小,占用带宽小)⑤交互轮数少9.2认证协议2122认证的分类实体认证(身份认证)数据源认证(消息认证)确认通信实体的真实身份确认数据发送者的真实身份23实体认证•目的•向别人证明你是谁？•弄清楚他是谁？24实体认证•实体认证可分为：①单向认证：通信一方认证另一方的身份②双向认证：通信双方彼此认证身份25实体认证•方法①Knowsth:他知道什么可用于识别他的东西?②Havesth：他拥有什么可用于识别他的东西?③Besth：他有什么特征？26实体认证knowsth•口令是最常用的认证机制，但安全性较差•易受到泄露、猜测、窃听、社会工程学等形式的攻击•什么是弱口令？•短口令•常见单词•生日•电话号码•系统预设口令……27•口令管理措施·口令应具有一定的长度，包含多种字符类型·口令不应使用易猜测的数字或字母组合·口令应具有一定的生存期·口令不应使用一定时间内的历史口令·用户登录不同系统应使用不同的口令·系统应设定口令登录失败次数限制口令空间口令时间口令保护28•与“基于口令的加密(PBE)”的区别·基于口令的加密：利用口令推导出密钥·基于口令的认证：利用口令进行实体认证•例如：登录电子邮箱、进入网上银行…实体认证knowsth:基于口令的认证机制29•需解决的关键问题–口令的存储•直接明文存储口令？一旦得到存储口令的数据库，就可得到全体人员的口令。风险很大！！！•常用解决方法–Needham口令认证协议(利用Hash函数存储口令)–一次性口令机制……30•原理–利用Hash函数存储口令，防范攻击者偷取数据库后得到口令•简单有效，广泛应用于各种系统中–UNIX：使用DES代替Hash函数–Discuz！……实体认证knowsth:Needham口令认证协议31用户名口令散列值zhangxtR$^42@Alice6tT$^2%%……数据库passwordH6tT$^2%%比较usernameAlice•缺点–无法防范攻击者在线窃听口令–无法防范离线字典攻击32•为防范在线窃听口令，可使用一次性口令机制–每次认证使用不同的口令•要求用户和系统共享很多口令•但管理和保护大量的口令在技术上很困难•为克服这一缺点，Lamport提出利用多次Hash的方法实现一次性口令机制实体认证knowsth:一次性口令机制33•方法举例–系统保存P100–用户保存P99、P98、P97……–认证过程①用户提交P99②系统计算if（P100==Hash(P99)）{验证通过;保存P99;}③用户丢弃P99初始秘密值wP1=H(w)P2=H(P1)P100=H(P99)系统保存计算完销毁用户保存实体认证knowsth:Lamport的一次性口令机制34•Lamport方案的缺点–必须保持同步–但可能因为不可靠信道或死机出现丢失同步的情况(有可能是攻击者的破坏所致)35•在WEB应用中，可以利用SSL建立安全信道，再进行基于口令的认证•方法–先使用HTTPS协议，与服务器建立安全连接(服务器必须支持HTTPS)–再将用户名和口令传送到服务器进行认证•应用方便，安全保护对用户透明–比如：用浏览器登录电子邮件服务器实体认证knowsth:利用SSL建立安全信道传输口令36•点击“登录”，浏览器地址栏会闪过一个以“https”开头的地址，这说明正用SSL安全连接传送用户名和口令37实体认证havesth.•存储卡：在磁卡上保存用户信息；与PIN配合使用•智能卡：由一个或多个集成电路芯片组成，包含CPU和存储器，具有数据存储能力和逻辑处理功能……38实体认证besth.•生物特征–指纹、掌纹、虹膜、视网膜、手形、面部特征、声音特征•动态特征–签名特征–键盘特征39扩展阅读对实体认证协议的典型攻击中间人攻击旧消息重放交错攻击平行会话攻击反射攻击409.3秘密共享41•宝藏问题–海盗们把宝藏藏在一个安全的地方，只有用地图才能找到。但地图如何分配呢？•各拿一份地图肯定不行，因为他们彼此不信任•各拿地图的一部分也不行，因为有人丢失他那份的话，就无法复原地图•如何解决——秘密共享技术42•秘密共享是什么–将秘密分割存储的密码技术•秘密共享的目的–防止秘密过于集中，以达到分散风险和容忍入侵的目的43•提出时间–Shamir1979年•(m,n)门限方案–将秘密SK拆成n份–任意m(m≤n)份或更多份都可以恢复SK–任何少于m份都不能得到关于SK的任何有用信息–其中，每一份都称为一个share（或shadow）门限方案解决秘密共享问题最常用的方法44(3,5)门限方案SKSK3SK5SKSKSK1SK2SK445•拉格朗日插值多项式给定有限域Fp中互不相同的整数x1,…,xn+1,和任意不全为零的整数k1,…,kn+1，公式满足f(xi)=ki，i=1,…,n+1f(x)是一个n次多项式，称为拉格朗日插值多项式Shamir的门限方案基于拉格朗日插值多项式1111111111()()()()()mod()()()()niiiniiiiiiinkxxxxxxxxfxpxxxxxxxxLLLL46•方案描述①分割秘密–设待共享秘密为K,令a0=K–随机产生m-1次多项式f(x)=(am-1xm-1+…+a1x+a0)modp–依次计算ki=f(xi)，i=1,…,n•易知K=f(0),且每一对(xi,ki)都是f(x)函数曲线上的一个点–ki是每个参与者的share,必须保密(xi无需保密)47②重构f(x)给定k1,k2,…,km共m个share，对应的分别是x1,x2,…,xm。f(x)可由拉格朗日插值多项式给出：③恢复秘密K=f(0)1111111()()()()()mod()()()()miiimiiiiiiimkxxxxxxxxfxpxxxxxxxxLLLL48•安全性原理–对于m-1次多项式，只需给出m个点就可以唯一地重构，少于m个share则不能。–由此保证K可从m个share中获得，而少于m个办不到。49•举例：(3,5)的门限方案–设m=3，n=5，p=17，K=13，①分割秘密–构造随机多项式f(x)＝(2x2+10x+13)mod17–k1=f(1)=(2+10+13)mod17=8–k2=f(2)=(8+20+13)mod17=7–k3=f(3)=(18+30+13)mod17=10–k4=f(4)=(32+40+13)mod17=0–k5=f(5)=(50+50+13)mod17=11–k1,…,k5便是share,每个用户一人一个50②重构f(x)给定k1=8,k3=10,k5=11,重构如下：③恢复K=f(0)=132(3)(5)(1)(5)(1)(3)()81011(13)(15)(31)(35)(51)(53)(3)(5)(1)(5)(1)(3)81011848(3)(5)104(1)(5)1115(1)(3)(3)(5)6(1)(5)12(1)(3)1992xxxxxxfxxxxxxxxxxxxxxxxxxxx2281271321013(mod17)xxxxx51门限方案的图形化—视觉密码•提出者Shamir等•目的将写有秘密信息的图片拆分成n张,至少m张(m≤n)才能恢复原来的图片•优点–安全性高：相当于“一次一密”–计算开销低：恢复原图片时，用幻灯机即可，无需计算机参与52(2,3)的视觉密码方案写有秘密信息的原图片天王盖地虎宝塔镇河妖53一个实际的例子9.4零知识证明5455•Peter：我知道瑞士银行计算机系统的口令•Victor：我才不信，你不知道•Peter：我就知道•Victor：拉倒吧，别忽悠•Peter：我确实知道•Victor：你怎么证明•Peter悄悄说出了口令•Victor：艾玛，现在我也知道了，我去告诉小红•Peter一脸黑线-_-|||一个小故事56我知道某个秘密我想向别人证明“我确实知道这个秘密”除此之外，我不想让别人获得关于该秘密的任何知识应该怎么办？——零知识证明57什么叫“获得知识”：本来有些事Victor自己干不了，但通过与Pet