1、1身份鉴别协议身份鉴别协议现代密码学现代密码学第十章第十章2上章内容回顾上章内容回顾n密钥管理简介密钥管理简介n密钥分配密钥分配n密钥协商密钥协商nPKIPKI及数字证书简介及数字证书简介n秘密共享秘密共享3本章主要内容本章主要内容n身份鉴别的定义n口令认证协议n挑战应答协议n对身份识别协议的攻击和对策4身份鉴别的定义身份鉴别的定义n身份鉴别鉴别：又称为身份识别、实体认证。又称为身份识别、实体认证。它是这样一个过程，即其中一方确信参与协它是这样一个过程，即其中一方确信参与协议的第二方的身份，并确信第二方真正参与议的第二方的身份，并确信第二方真正参与了该过程。了该过程。n用户的身份识别是许多应用
2、系统的用户的身份识别是许多应用系统的第一道防线，其目的在于识别用户的合法性，从而阻，其目的在于识别用户的合法性，从而阻止非法用户访问系统。身份识别（认证）对止非法用户访问系统。身份识别（认证）对确保系统和数据的安全保密是极其重要的。确保系统和数据的安全保密是极其重要的。5身份鉴别的定义身份鉴别的定义Alice?BobEve?6身份鉴别的定义身份鉴别的定义n已知事物：口令、个人识别码口令、个人识别码(PIN)、挑战、挑战-响应协议中已被证实的秘密或私钥。响应协议中已被证实的秘密或私钥。n已拥有的事物：通常是物理配件。如，磁卡、通常是物理配件。如，磁卡、智能卡智能卡(或或IC卡卡)、口令生成器、口
3、令生成器n固有事物(对某个人)：利用人类物理特征和利用人类物理特征和无意行为。如，手写签名、指纹、声音、视无意行为。如，手写签名、指纹、声音、视网膜模式、手的几何形状等。（非密码学的）网膜模式、手的几何形状等。（非密码学的）7身份鉴别的定义身份鉴别的定义身份鉴别的定义：身份鉴别的定义：1、在诚实的情况下，声称者、在诚实的情况下，声称者A能向验证者能向验证者B证明他确实是他确实是A；2、在声称者、在声称者A向验证者向验证者B声称他的身份后，声称他的身份后，验证者验证者B不能获得任何有用的信息，任何有用的信息，B也也不能模仿A向其他第三方证明他就是向其他第三方证明他就是A。3、任何不同于、任何不同
4、于A的实体的实体C以以A的身份，让的身份，让B相相信信C是是A的概率可忽略不计的概率可忽略不计8身份鉴别的定义身份鉴别的定义n用于实现身份识别的协议。n协议：是一系列步骤，它包括两方和多方，设计它的目的是要完成一项任务。n协议是从开始到结束的一个协议是从开始到结束的一个序列，每步必须依，每步必须依次执行次执行n完成协议完成协议至少需要两个人n协议的协议的目的是为了做一些事情是为了做一些事情9身份鉴别的定义身份鉴别的定义分析和评价身份认证协议应考虑如下几个方面：（1）交互性：是单方还是双方的身份认证；是单方还是双方的身份认证；（2）计算的有效性；（3）通信的有效性；（4）是否需要第三方的实时参与
5、；（5）对第三方的可信度的要求；（6）安全保证（可证明安全、零知识证明）；（7）用来存储共享秘密数据的地方和方法。10身份鉴别的定义身份鉴别的定义Passwords（weak authentication）：系统检查口令是否与系统拥有的相应用户数据相匹配，批准声明的身份访问资源n用户ID是声称的身份n口令是支持声称的证据：固定口令、PIN和通行密钥Challenge-response identification（strong authentication）：通过向验证者展示与证明者实体有关的秘密知识来证明自己的身份，但在协议中并没有向验证者泄露秘密本身。身份鉴别技术分类身份鉴别技术分类11口
6、令认证协议口令认证协议固定口令n1）存储的口令文件n以明文形式将用户口令存储在系统口令文件中n口令文件需读保护和写保护n2）“加密的”口令文件n存储口令的单向函数值n口令文件需写保护IDA,PWPassWordPWAB检查口令和身份窃听？存储安全？12口令认证协议口令认证协议n服务器端的字典攻击：在这种攻击中，Eve只对找到口令有兴趣，并不关心用户的ID。例如，如果口令是六位数，Eve可以创建一个六位数(000000999999)的列表，然后对每一个数使用散列函数，结果就是一个一百万个散列的列表。她就可以得到口令档案并搜索条目中的第二列，找出一个与之相匹配的。这可以被编程并且在Eve的个人计算
7、机上脱机运行。找到匹配以后，伊夫就可以再上线，用口令来访问系统。13口令认证协议口令认证协议3）口令加盐(Salting Passwords)n第一环节：口令字段字符串的生成：s=Agen(Dsalt,Dpw)给口令Dpw撒盐：Dpw=Asalt(Dsalt，Dpw)；用撒盐结果做密钥：K=Dpw；用一个64位的全0位串构造一个数据块Dp；设循环次数：i=0；对数据块加密：Dc=Acrypt(K,Dp)；Dp=Dc，i=i+1；如果i B:rB A-B:hK(rB,A)n双向认证30挑战挑战-应答身份鉴别协议应答身份鉴别协议n使用手持通行码生成器的实现A是用户的私钥是用户的私钥;f是单向函数是
8、单向函数;312）使用公钥技术的挑战-应答声称者证明他知道私钥的方式有两种：n声称者解密用它的公钥加密的挑战n声称者数字签署一个挑战挑战挑战-应答身份鉴别协议应答身份鉴别协议32挑战挑战-应答身份鉴别协议应答身份鉴别协议n单向认证：n双向认证：r为随机数为随机数r1,r2为随机数为随机数基于公钥加密的挑战基于公钥加密的挑战-响应响应33挑战挑战-应答身份鉴别协议应答身份鉴别协议n带时戳的单向认证：n带随机数的单向认证：n带随机数的双向认证：certA,certB为公钥证书为公钥证书;SA,SB为私钥为私钥;基于数字签名的挑战基于数字签名的挑战-响应响应34挑战挑战-应答身份鉴别协议应答身份鉴别
9、协议3）基于零知识证明的挑战-应答n零知识零知识(Zero-knowledge)(ZK)证明的起源证明的起源Alice：我知道肯德基的土豆泥的配方以及做法。我知道肯德基的土豆泥的配方以及做法。Bob：不，你不知道。不，你不知道。Alice：我知道。我知道。Bob：你不知道。你不知道。Alice：我确实知道！我确实知道！Bob：请你证实这一点！请你证实这一点！Alice：好吧，我告诉你！（她悄悄地说出了土豆泥的秘方）好吧，我告诉你！（她悄悄地说出了土豆泥的秘方）Bob：太有趣了！现在我也知道了。我要告诉太有趣了！现在我也知道了。我要告诉华盛顿邮报华盛顿邮报Alice：啊呀！啊呀！35挑战挑战-应
10、答身份鉴别协议应答身份鉴别协议n不幸的是，不幸的是，Alice用常用的方法给用常用的方法给Bob证明她知道证明她知道的秘密。这样一来，的秘密。这样一来，Bob也知道了这些秘密了，也知道了这些秘密了，现在现在Bob要告诉其他人，要告诉其他人，Alice对此毫无办法。对此毫无办法。n问题：有没有一种有效的办法，让有没有一种有效的办法，让Alice能向能向Bob证明她知道这些秘密，使得证明她知道这些秘密，使得Bob可以确信可以确信Alice的的确知道这些，但确知道这些，但Bob根本不能获得这些秘密的任根本不能获得这些秘密的任何信息呢？何信息呢？36挑战挑战-应答身份鉴别协议应答身份鉴别协议n零知识证
11、明的思想零知识证明的思想Alice要向Bob证明她知道某些秘密：nBob：问：问Alice一系列问题一系列问题nAlice：若知道那个秘密，她就能正确回答所有：若知道那个秘密，她就能正确回答所有问题。如果她不知道，她仍有问题。如果她不知道，她仍有50的机会回答的机会回答每一个问题。但要猜对每个问题的机会实在太每一个问题。但要猜对每个问题的机会实在太小了（几乎不可能）。小了（几乎不可能）。n大约大约10个问题之后个问题之后nBob确信确信Alice是否知道那个秘密。然而所有回是否知道那个秘密。然而所有回答都没有给答都没有给Bob提供提供Alice所知道的所知道的秘密的任何秘密的任何信息。信息。3
12、7挑战挑战-应答身份鉴别协议应答身份鉴别协议ABC D38挑战挑战-应答身份鉴别协议应答身份鉴别协议(1)Bob站在 A 点；(2)Alice进入洞中任一点 C 或 D；(3)当Alice进洞之后，Bob走到 B 点；(4)Bob叫Alice：(a)从左边出来，或(b)从右边出来；(5)Alice按要求实现(以咒语，即解数学难题帮助)；(6)Alice和Bob重复执行(1)(5)共n次。39挑战挑战-应答身份鉴别协议应答身份鉴别协议n若 Alice 不知咒语，则在 B 点，只有50%的机会猜中 Bob的要求，协议执行 n 次，则只有 2-n 的机会完全猜中，若 n=16，则若每次均通过 Bob
13、 的检验，B受骗机会仅为1/65536。n如果Bob用摄像机记录下他所看到的一切，他把录像给Carol看，Carol会相信这是真的吗？Carol是不会相信这是真的。n这说明了两件事情：其一，Bob不可能使第三方相信这个证明；其二，它证明了这个协议是零知识的。Bob在不知道咒语的情况下，显然不能从录像中获悉任何信息。40挑战挑战-应答身份鉴别协议应答身份鉴别协议n零知识(Zero-knowledge)(ZK)证明:是一种是一种交互式证明系统系统n声称者（证明者）和验证者声称者（证明者）和验证者交换多个信息，这，这些信息的生成些信息的生成依赖于保密的随机数n证明者P(Prover)：知道某一秘密知
14、道某一秘密s，使，使V相信自相信自己掌握这一秘密；己掌握这一秘密；n验证者V(Verifier)：验证验证P掌握秘密掌握秘密sn每轮每轮V向向P发出一询问，发出一询问，P向向V作应答（需要有作应答（需要有s的知的知识才能正确应答）。识才能正确应答）。nV检查检查P是否每一轮都能正确应答。是否每一轮都能正确应答。41挑战挑战-应答身份鉴别协议应答身份鉴别协议n交互证明与数学证明的区别n数学证明：证明者可自己证明者可自己独立完成证明完成证明(绝对)n交互证明：由由P产生证明产生证明(响应响应)，V验证证明验证证明(响应）的响应）的有效性有效性（概率上）来实现，双方之间要有通信来实现，双方之间要有通
15、信n交互系统应满足交互系统应满足n完备性：如果：如果P知道某一秘密，知道某一秘密，V将接收将接收P的证明的证明n正确性：如果如果P能以一定的概率使能以一定的概率使V相信相信P的证明，则的证明，则P知道相应的秘密（冒充者伪造成功的概率可忽略不计）知道相应的秘密（冒充者伪造成功的概率可忽略不计）42挑战挑战-应答身份鉴别协议应答身份鉴别协议nNeedham-Schroeder协议：是基于对称密钥加密的挑战-响应n计算模n平方根的困难性nFiat-Shamir身份识别协议nFiege-Fiat-Shamir身份识别协议n离散对数的困难性：Schnorr协议43挑战挑战-应答身份鉴别协议应答身份鉴别协
16、议2.4.)|(|1AsKBsKIDKERIDKEBAKDCAB1.IDA|IDB|R13.|AsKIDKEB2RESK5.)(2RfESK如果敌手获得了旧会话如果敌手获得了旧会话密钥，则可以冒充密钥，则可以冒充A A重重放放3 3，并且可回答，并且可回答5 5，成，成功的欺骗功的欺骗B BKs为随机会话密钥为随机会话密钥1 NeedhamSchroeder协议协议44挑战挑战-应答身份鉴别协议应答身份鉴别协议2.4.)|(|TIDKETIDKEAsKBsKBAKDCAB1.IDA|IDB3.|TIDKEAsKB1NESK5.)(1NfESK以时戳替代随机数，用以向A，B保证Ks的新鲜性|Cl
17、ockT|t1+t2 Clock:本地时钟t1：本地时钟与KDC时钟误差估计值t2：网络延迟时间要求各方时钟同步要求各方时钟同步如果发方时钟超前如果发方时钟超前B B方时钟，可能方时钟，可能导致等待重放攻击导致等待重放攻击NeedhamSchroeder改进协议（改进协议（1）45挑战挑战-应答身份鉴别协议应答身份鉴别协议KDCAB3.1.AANID|4.|BKBSAKNETKIDESB2.|BAAKBBTNIDENIDBBBSAKBSABKNTKIDETKNIDEBA|会话密钥的截止时间NeedhamSchroeder改进协议（改进协议（2）46挑战挑战-应答身份鉴别协议应答身份鉴别协议n如
18、果 A 保留由协议得到的票据，就可以在有效期内可不通过KDC直接认证AB,|1ABSAKNTKIDEB、,2AKBNENS、3BKNES、B B在第一步收到票据后，可以通过在第一步收到票据后，可以通过BT检验票据是否过时检验票据是否过时，而新产生的一次随机数新产生的一次随机数则向双方保证了没有重放攻击则向双方保证了没有重放攻击。BANN,47挑战挑战-应答身份鉴别协议应答身份鉴别协议参数的选择：n可信中心可信中心T选择两个素数选择两个素数p和和q(保密，最好保密，最好用完丢弃用完丢弃)，计算类似，计算类似RSA的模数的模数m=pq、并公开并公开m。n证明者选择与证明者选择与m互素的互素的私钥私
19、钥s(1sm)，计，计算算v=s2 mod mn证明者在可信中心证明者在可信中心T中注册中注册公钥公钥v2 Fiat-Shamir身份识别协议身份识别协议48挑战挑战-应答身份鉴别协议应答身份鉴别协议协议执行：迭代t轮(连续地、独立地)(1)Alice 取随机数 r(m)，计算x=r2 mod m，并发送给Bob；(2)Bob将一随机比特e=0或1作为挑战发给 Alice；(3)Alice计算响应值y并发给Bobn若e=0，则Alice 将y=r送给Bob；n若e=1，则Alice将y=rs mod m送给Bob；(4)若y=0，则Bob拒绝证明；反之，验证y2xve mod m？n若e=0，
20、则Bob 证实y2=x mod mn若e=1，则 Bob 证实 y2=xv mod m 若t轮都成功，则Bob就接收Alice的身份Fiat-Shamir身份识别协议身份识别协议49挑战挑战-应答身份鉴别协议应答身份鉴别协议n完备性n如果Alice和Bob遵守协议，且Alice知道s，则响应值 y2=(rse)2 mod m xve mod m，Bob接收Alice的证明，所以协议是完备的。n正确性nAlice不知道s，他也可取r，送y2=r2 mod m给Bob；Bob送e 给Alice；Alice将r作为响应值；当b=0时则Alice可通过检验使得Bob受骗，当b=1时，则Bob可发现Al
21、ice不知s。Bob受骗概率为1/2，但连续t轮受骗的概率将仅为2-tnBob无法知道Alice的秘密(s)，因为s没有被传送过，且Bob只能随机选取一个比特位作为挑战。50挑战挑战-应答身份鉴别协议应答身份鉴别协议参数的选择：n可信中心可信中心T选择两个素数选择两个素数p和和q(保密，最好用完丢保密，最好用完丢弃弃)，计算类似，计算类似RSA的模数的模数n=pq、并公开、并公开n。n证明者选择证明者选择k个与个与n互素的随机整数作为互素的随机整数作为私钥私钥s1,s2,sk(1sin)n证明者选择证明者选择k个随机比特个随机比特b1,b2,bk(1ik)，计算计算vi=(-1)bi(si2)
22、-1 mod n(1ik)n证明者在可信中心证明者在可信中心T中注册中注册公钥公钥(v1,v2,vk;n)3 Fiege-Fiat-Shamir身份识别协议身份识别协议51挑战挑战-应答身份鉴别协议应答身份鉴别协议协议执行：迭代t轮(连续地、独立地)(1)Alice 取随机数 r(n)和一个随机比特b，计算x=(-1)br2 mod n，并发送给Bob；(2)Bob将一随机比特序列(e1,ek),ei0,1 作为挑战发给 Alice；(3)Alice计算响应值y并发给Bob:(4)Bob计算 ，并验证z=x和z0 若t轮都成功，则Bob就接收Alice的身份Fiege-Fiat-Shamir身
23、份识别协议身份识别协议52挑战挑战-应答身份鉴别协议应答身份鉴别协议nShnorr 身份认证协议融合了ELGamal协议、Fiat-Shamir协议、和Chaum-Evertse-Van de Graff交互协议等协议的思想，是一种计算量、通信量均少，特别适合智能卡上用户身份识别的方案。n其安全性建立在计算离散对数问题的困难性上。4 Shnorr 身份认证协议身份认证协议53挑战挑战-应答身份鉴别协议应答身份鉴别协议nShnorr 身份认证协议需要一个可信中心 TA。TA为协议选择下列参数：(1)p 及及 q 是两个大素数，且是两个大素数，且 q|(p-1);的生成元。）为，阶元（如可取为pq
24、ppggqZZ)2(/)1(*(3)选择安全参数选择安全参数t54挑战挑战-应答身份鉴别协议应答身份鉴别协议n每个用户自己选定个人秘钥s，并计算公钥v。其中n每位用户必须到TA 注册其公开密钥v。TA 验明用户身份后，对每位用户指定一识别名I。I中包括用户的姓名、性别、生日、职业、电话号码、指纹信息等识别信息。TA 对(I,v)的签名为ST(I,v)。n在身份认证过程中，不需要 TA 介入。pvqssmod,1,1 55挑战挑战-应答身份鉴别协议应答身份鉴别协议n证明者A向验证者B证明他身份（Schnorr 认证协议）),(,(1ATAvISvI、AB用用 TA 的数字签名来的数字签名来验证验
25、证 A 的公开密钥的公开密钥pZr*任选pXrmod2、2,1 te任选整数3、eqserymod4、pvXeymod.5验证56挑战挑战-应答身份鉴别协议应答身份鉴别协议nSchnorr 协议的安全的基础是离散对数计算困难性。n从v求s就是求离散对数，在计算上是不可行的。nr 和s都是用户的秘密，假冒者 Eve 是无法从 y 中得到用户的秘密，当然也就无法假冒证明者A。pvqssmod,1,1 57身份鉴别与数字签名身份鉴别与数字签名n身份识别方案可转换为数字签名方案n数字签名：n包含可变的消息摘要n通常提供不可抵赖性，以允许事后法官来解决争端n签署的消息通常是可公开验证的n身份识别：n消息
26、的语义基本固定（在当前时刻及时地声称身份）n声称可以立即确证或拒绝，从而实时保证或解除相关的特权或访问n仅通信双方可以验证对方身份58转换为签名方案转换为签名方案n利用H(x|m)代替验证者的随机挑战enx：证据nm：要签署的消息nH：hash函数n挑战e的比特大小要足够大，以排除对杂凑函数的离线攻击59对身份识别协议的攻击和对策对身份识别协议的攻击和对策n假冒（impersonation)：一个实体声称是另一个实体n重放攻击(replay attack)：n利用从以前执行的协议中获得的信息进行假冒或其他欺骗。n对策：用挑战-响应技术；用临时值；在响应值中嵌入目标身份60对身份识别协议的攻击和
27、对策对身份识别协议的攻击和对策n交织攻击(interleaving attack)：n从一个或多个以前的或同时正在执行的单个协议中获得的信息进行有选择地组合，以实现假冒或欺骗n对策：使用链接的临时值61对身份识别协议的攻击和对策对身份识别协议的攻击和对策n反射攻击(reflection attack)：n从正在执行的协议将信息发送回该协议的发送者的交织攻击n对策：在挑战-响应中嵌入目标的标识符；避免消息的对称性；单向密钥的使用n强迫延时(forced delay)：n使协议的过程暂时终止，在延迟一段时间后，再使协议继续进行n对策：随机数与短响应延时结合使用；时戳加上适当的附加技术62对身份识别
28、协议的攻击和对策对身份识别协议的攻击和对策n选择文本攻击(chosen-text attack)n是对挑战-响应的攻击，敌手有策略地选择挑战以尝试提取声称者的长期密钥的信息n对策：用零知识技术，在每个挑战-响应中嵌入自选择随机数63本节要点回顾本节要点回顾n身份鉴别的定义n口令认证协议n挑战应答协议n对身份识别协议的攻击和对策64作业作业1证明证明Fiege-Fiat-Shamir身份鉴别协议的正身份鉴别协议的正确性及完备性。确性及完备性。2 证明证明Shnorr身份鉴别协议的正确性和完备身份鉴别协议的正确性和完备性。性。思考：上述身份认证协议，哪些满足不可转移性？即“任何不同于任何不同于A的实体的实体C以以A的身份，的身份，让让B相信相信C是是A的概率可忽略不计的概率可忽略不计”？65THE END！
