现代密码学09---安全协议.ppt
,现代密码学,安全协议,2,3,9.1 安全协议概述9.2 认证协议9.3 秘密共享9.4 零知识证明,4,5,在日常生活中，几乎所有的事情都有非正式的协议电话订货下棋、玩扑克选举投票没有人认真考虑过这些协议，它们随时间的推移而发展，人们都知道怎样使用它们，而且它们也很有效,6,7,协议必须把所有 不利条件 事先都估计到，而 不能假定 一切都是正常的和非常理想的。看一个协议是否正确，不能光看在正常情况下是否正确，而且还必须非常仔细地检查这个协议 能否应付各种异常情况。,8,这样的协议无法实现！,两军问题（拜占庭将军问题）,9,结论这样无限循环下去，两边的蓝军都始终无法确定自己最后发出的电文对方是否已经收到。没有一种协议能使蓝军 100%获胜。,10,庄子盗跖：尾生与女子期于梁下，女子不来，水至不去，抱梁柱而死。,11,12,机密性 完整性 认证性非否认性公平性匿名性,13,电子商务 信用卡交易 电子支票,电子货币 电子拍卖 网上银行 电子政务 电子选举,14,协议参与者 攻击者内部/外部攻击者被动/主动攻击者可信第三方(TTP,Trusted Third Party)用户都信任的实体，通常与每个用户共享密钥功能：使用户之间确认彼此身份 或 共享会话密钥,15,16,攻击者能做到的事：能截获经过网络的任何消息以合法参与者身份，发起与任何用户的对话有机会成为任何主体发出消息的接收者能够冒充任何别的主体给任意主体发消息,17,攻击者不能做到的事：不能猜到从足够大的空间中选出的随机数没有正确的密钥，不能由给定的密文恢复出明文；也不能从给定的明文构造出正确的密文不能从公钥计算出相应的私钥 不能控制计算环境中的许多私有区域，如离线的存储器,18,在现实世界中，你会交给陌生人一叠现金替你买东西吗？你没看到别人洗牌和发牌，会和他玩三国杀吗？没有匿名的保证，你会在选举中投反对票吗？网络上的协议参与者可能是完全信任的人，也可能是攻击者和完全不信任的人。假设使用网络的人都是诚实的想法，是天真的。天真的想法还有：假设网管是诚实的，假设网络设计者是诚实的。,19,安全目标本身的微妙性表面上十分简单的目标，实际上十分微妙运行环境的复杂性实际上,当安全协议运行在一个十分复杂的公开环境时,攻击者处处存在攻击者模型的复杂性必须形式化地描述攻击者的能力，对攻击者和攻击行为进行分类和形式化的分析安全协议本身具有“高并发性”,20,满足目标(应用目标,安全目标)易于实现各参与者所需计算量小、存储量小通信负载小(延迟小,占用带宽小)交互轮数少,21,22,确认通信实体的真实身份,确认数据发送者的真实身份,23,目的 向别人证明你是谁？弄清楚他是谁？,24,实体认证可分为：单向认证：通信一方认证另一方的身份 双向认证：通信双方彼此认证身份,25,方法 Know sth:他知道什么可用于识别他的东西?Have sth：他拥有什么可用于识别他的东西?Be sth：他有什么特征？,26,口令是最常用的认证机制，但安全性较差 易受到泄露、猜测、窃听、社会工程学等形式的攻击 什么是弱口令？短口令 常见单词 生日 电话号码 系统预设口令,27,口令管理措施口令应具有一定的长度，包含多种字符类型口令不应使用易猜测的数字或字母组合口令应具有一定的生存期口令不应使用一定时间内的历史口令用户登录不同系统应使用不同的口令系统应设定口令登录失败次数限制,口令空间,口令时间,口令保护,28,与“基于口令的加密(PBE)”的区别基于口令的加密：利用口令推导出密钥基于口令的认证：利用口令进行实体认证例如：登录电子邮箱、进入网上银行,29,需解决的关键问题口令的存储直接明文存储口令？一旦得到存储口令的数据库，就可得到全体人员的口令。风险很大！常用解决方法Needham口令认证协议(利用Hash函数存储口令)一次性口令机制,30,原理利用Hash函数存储口令，防范攻击者偷取数据库后得到口令简单有效，广泛应用于各种系统中UNIX：使用DES代替Hash函数Discuz！,31,数据库,password,H,6tT$2%,比较,username,Alice,缺点无法防范攻击者在线窃听口令无法防范离线字典攻击,32,为防范在线窃听口令，可使用一次性口令机制每次认证使用不同的口令要求用户和系统共享很多口令但管理和保护大量的口令在技术上很困难为克服这一缺点，Lamport提出利用多次Hash的方法实现一次性口令机制,33,方法举例系统保存P100用户保存P99、P98、P97认证过程用户提交P99系统计算 if（P100=Hash(P99)）验证通过;保存P99;用户丢弃P99,初始秘密值w,P1=H(w),P2=H(P1),P100=H(P99),系统保存,计算完销毁,用户保存,34,Lamport方案的缺点必须保持同步但可能因为不可靠信道或死机出现丢失同步的情况(有可能是攻击者的破坏所致),35,在WEB应用中，可以利用SSL建立安全信道，再进行基于口令的认证方法先使用HTTPS协议，与服务器建立安全连接(服务器必须支持HTTPS)再将用户名和口令传送到服务器进行认证应用方便，安全保护对用户透明比如：用浏览器登录电子邮件服务器,36,点击“登录”，浏览器地址栏会闪过一个以“https”开头的地址，这说明正用SSL安全连接传送用户名和口令,37,存储卡：在磁卡上保存用户信息；与PIN配合使用智能卡：由一个或多个集成电路芯片组成，包含CPU和存储器，具有数据存储能力和逻辑处理功能,38,生物特征指纹、掌纹、虹膜、视网膜、手形、面部特征、声音特征动态特征签名特征键盘特征,39,40,41,宝藏问题海盗们把宝藏藏在一个安全的地方，只有用地图才能找到。但地图如何分配呢？各拿一份地图肯定不行，因为他们彼此不信任各拿地图的一部分也不行，因为有人丢失他那份的话，就无法复原地图如何解决 秘密共享技术,42,秘密共享是什么将秘密分割存储的密码技术秘密共享的目的防止秘密过于集中，以达到分散风险和容忍入侵的目的,43,提出时间Shamir 1979年(m,n)门限方案将秘密SK拆成n份任意m(mn)份或更多份都可以恢复SK任何少于m份都不能得到关于SK的任何有用信息其中，每一份都称为一个share（或 shadow）,44,(3,5)门限方案,45,拉格朗日插值多项式 给定有限域Fp中互不相同的整数x1,xn+1,和任意不全为零的整数k1,kn+1，公式 满足f(xi)=ki，i=1,n+1 f(x)是一个n次多项式，称为拉格朗日插值多项式,46,方案描述分割秘密设待共享秘密为K,令a0=K随机产生m-1次多项式 f(x)=(am-1xm-1+a1x+a0)mod p依次计算 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),48,安全性原理对于m-1次多项式，只需给出m个点就可以唯一地重构，少于m个share则不能。由此保证K可从m个share中获得，而少于m个办不到。,49,举例：(3,5)的门限方案设 m=3，n=5，p=17，K=13，分割秘密构造随机多项式 f(x)(2x2+10 x+13)mod 17k1=f(1)=(2+10+13)mod 17=8k2=f(2)=(8+20+13)mod 17=7k3=f(3)=(18+30+13)mod 17=10k4=f(4)=(32+40+13)mod 17=0k5=f(5)=(50+50+13)mod 17=11k1,k5便是share,每个用户一人一个,50,重构f(x)给定k1=8,k3=10,k5=11,重构如下：恢复K=f(0)=13,51,提出者 Shamir 等目的 将写有秘密信息的图片拆分成n张,至少m张(mn)才能恢复原来的图片优点安全性高：相当于“一次一密”计算开销低：恢复原图片时，用幻灯机即可，无需计算机参与,52,(2,3)的视觉密码方案,天王盖地虎宝塔镇河妖,53,一个实际的例子,54,55,Peter：我知道瑞士银行计算机系统的口令Victor：我才不信，你不知道Peter：我就知道Victor：拉倒吧，别忽悠Peter：我确实知道Victor：你怎么证明Peter悄悄说出了口令Victor：艾玛，现在我也知道了，我去告诉小红Peter 一脸黑线-_-|,56,我知道某个秘密我想向别人证明“我确实知道这个秘密”除此之外，我不想让别人获得 关于该秘密的任何知识应该怎么办？零知识证明,57,58,59,设Peter(证明者)知道可打开C和D之间暗门的咒语，不知道者都将走进死胡同Peter向Victor(校验者)证明自己知道咒语，但不让Victor知道关于咒语的任何知识,零知识洞穴,60,解决咒语问题的零知识证明协议Victor站在A点Peter进入洞中任一点C或DPeter进洞后，Victor走到B点Victor随机叫Peter：从左边或右边出来Peter按要求执行(可借助咒语)Peter和Victor重复执行共n次,61,分析：完备性如果Peter知道咒语，他总能正确回答Victor的提问。正确性如果Peter不知道咒语，他只能从原路返回到B点，因此每一轮他欺骗Victor的概率是1/2，n轮成功欺骗的概率是 1/2n,是可以忽略的。零知识从协议执行可知，与Peter交互后，Victor无法获得关于咒语的任何知识,62,零知识洞穴问题可以转化为数学问题，Peter知道解决某个难题的秘密（相当于咒语），而Victor通过与Peter交互以验证其真实性。,63,结论 如果单向函数是存在的，任何一个NP问题都存在零知识证明相关论文Goldwasser,Micali,Rackoff.The knowledge complexity of interactive-proof systems.Proc.of 17th ACM Sym.on Theory of Computation,pp.291-304,1985.,证明两个图 G0 和 G1 是同构的（置换为）Alice 向Bob证明：他知道两个图是如何同构的 也即 证明自己知道,基本原理,o,证明过程如下,C,x,C,x,C,n 轮,72,协议描述：Alice 如下执行：Alice 随机选择图G0或G1(c=0 or 1)Alice 构造其同构图G(置换为)，并发给BobBob随机让Alice证明G与G0或G1同构(c=0 or 1)Alice 产生 x，将x发送给Bobx=if c=cx=o if ccBob校验Gc是否能在置换x的变换下等于G重复执行 1-4 共 n 次,73,分析：完备性如果G0与G1确实同构，且Alice知道同构置换，她总能正确回答Bob的提问。正确性如果Alice不知道,或者G0与G1不同构，她只能以1/2概率正确回答Bob的提问，n轮成功欺骗的概率是 1/2n,是可以忽略的。零知识Bob能从交互中获得的知识吗？,74,分析（续）：其实，即使不与Alice交互，Bob也可以自己产生交互数据。Bob可以这么做：随机选择一个 c=0 or 1构造图Gc的同构图G，设同构置换为x生成交互数据（G,c,x）这就说明，“产生交互数据”这件事，即使不与Alice交互，Bob自己也可以干，所以他没从Alice处获得任何知识。,75,76,掌握安全协议的相关概念、Dolev-Yao攻击者模型掌握实体认证的分类方法掌握Needham口令认证协议、Lamport的一次性口令机制掌握秘密共享的基本概念、Shamir的方案掌握零知识证明的基本概念,
