09密码学---密码协议选讲

1 .密码学 导论˙第 9 章 密码 协议选讲 李卫海

2 .本章内容 密码学导论 -- 中国科学技术大学 2

3 .第一节 密码协议概述 密码学导论 -- 中国科学技术大学 3

4 .一、密码协议的概念 协议 protocol ：是指两个或两个以上的参与者为完成某项特定的任务而采取的一系列步骤。 一系列步骤：必须依次完成的序列 包括两方或多方 目的是完成一项任务 协议被执行的条件 协议中的每个人都必须了解协议，预先知道所要完成的步骤 协议中的每个人都必须同意并遵循它 协议必须是清楚的，每一步定义明确，不会引起误解 协议必须是完整的，没有可能的情况都必须规定具体的动作 密码学导论 -- 中国科学技术大学 4

5 .密码协议是使用密码学的协议 密码协议的例子： 密钥协商协议 密钥分配协议 认证协议 盲签名协议 不经意传输协议 电子商务协议 等等 密码学导论 -- 中国科学技术大学 5

6 .一个简单的例子： Alice 与 Bob 之间通过一个可靠但好奇的 Postman 通信。 Alice 和 Bob 事先没有什么共享的秘密。 Alice 有一把锁和对应的钥匙 Bob 有另一把锁和对应的钥匙 Alice 上锁，送给 Bob Bob 也上锁，送给 Alice Alice 解锁，送给 Bob Bob 解锁，看到消息 密码学导论 -- 中国科学技术大学 6 Alice Bob Postman

7 .当使用密码技术完成上述协议时， Alice -> Bob: E( K a ,M ) Bob -> Alice: E( K b ,E ( K a ,M )) Alice -> Bob: D( K a ,E ( K b ,E ( K a ,M )))=E( K b ,M ) Bob: D( K b ,E ( K b ,M ))=M 注意协议的第 3 步要求加密 / 解密算法具有可交换性！ 指数运算可用 ——RSA 按位异或不可用 —— 信息泄露 密码学导论 -- 中国科学技术大学 7 Alice Bob Postman

8 .当采用按位异或加密时 Alice -> Bob: M⊕K A Bob -> Alice: (M⊕K A )⊕K B Alice -> Bob: (M⊕K A ⊕K B )⊕K A =M⊕K B Bob: (M⊕K B )⊕K B =M Postman: ( M⊕K A ) ⊕ [(M⊕K A )⊕K B ] ⊕ (M⊕K B )=M 密码学导论 -- 中国科学技术大学 8

9 .Postman 的诡计：截获消息，并欺骗 Bob 这就是中间人攻击。解决办法是利用签名技术 Alice Postman Bob M  E a (M) P  E p (P)  E p E a (M)  E b E p (P)  E p (M) M  E b (P) P 密码学导论 -- 中国科学技术大学 9 Alice Bob Postman

10 .二、密码协议的种类 仲裁协议 由仲裁者帮助互不信任的双方完成协议 裁决协议 每次都要完成的非仲裁子协议 有争议时才执行的裁决子协议 自动执行协议 协议本身就保证了公平性 密码学导论 -- 中国科学技术大学 10

11 .仲裁协议 Trent ：可信第三方，仲裁者 仲裁者在协议中没有既得利益，与通信人没有利害关系 所有人都接受： 仲裁者说的都是真实的 仲裁者做的都是正确的 仲裁者会忠实地完成协议中涉及他的部分 密码学导论 -- 中国科学技术大学 11 Alice Bob Trent

12 .例： Alice 想用支票从 Bob 处购买汽车 请律师做仲裁人 Bob 把车给律师 Alice 将支票交给 Bob Bob 兑现支票 经过规定时间，律师将车交给 Alice 。若在此时间内 Bob 未能兑现支票，则 Bob 向律师提交证据，并取回车 由银行做仲裁人 Alice 开支票给银行 银行验证 Alice 存款后，将保付支票交给 Alice Alice 将保付支票给 Bob ， Bob 将车给 Alice Bob 兑现保付支票 由公证人做仲裁人 密码学导论 -- 中国科学技术大学 12

13 .仲裁者的问题： 互相信任的双方，很容易找到仲裁者；互相怀疑的双方，很可能也怀疑仲裁者 仲裁者的劳务费 仲裁必定带来延迟 仲裁者需要处理每一次会话，成为网络瓶颈 破坏者更愿意攻击仲裁者 密码学导论 -- 中国科学技术大学 13

14 .裁决协议 裁决人不直接参与每一次会话 通信双方发生争议时，仲裁者才出场 仲裁协议是为了发现欺骗，而不是阻止欺骗 密码学导论 -- 中国科学技术大学 14 Trent 证据 证据 Alice Bob

15 .例：合同－签字协议 非仲裁子协议 Alice 和 Bob 谈判合同条款 Alice 签署合同 Bob 签署合同 裁决子协议 Alice 和 Bob 出现在法官面前 Alice 和 Bob 提交自己的证据 —— 合同 法官根据证据做出裁决 密码学导论 -- 中国科学技术大学 15

16 .自动执行协议 是最好的协议 很不幸，一般不存在自动执行协议 密码学导论 -- 中国科学技术大学 16 Alice Bob

17 .三、对密码协议的攻击 攻击目标通常有三个： 协议中采用的密码算法 实现该算法和协议的密码技术 协议本身 被动攻击： 窃听 主动攻击： 中间人攻击、重放攻击、类型攻击、交织攻击、与实现相关的攻击、绑定攻击、封装攻击，等等 局外人，或协议参与者（骗子） 窃取信息、欺骗、阻碍合法使用等 密码学导论 -- 中国科学技术大学 17

18 .重放攻击： 捕获过往协议或当前协议中的消息，在当前协议中重播 获取非法权限、伪造密钥等等 防止方法：添加 nonce 、时间戳，不同阶段的消息在结构上不对称（例如前面用 { A,msg } ，后面用 { msg,A } ） 类型攻击： 协议双方对消息成分的位序列有不同的解释 例如：密钥和随机数 nonce 都是随机比特串，攻击者可能把加密的密钥挪到加密的 nonce 的位置，诱使协议方将密钥误认为 nonce 而公布出来 防止方法：协议中不同成分采用不同的形式 密码学导论 -- 中国科学技术大学 18

19 .交织攻击： 同时运行多次协议，将其中某些的消息用于形成另一次运行中的消息 例如国际象棋大师、黑手党协议、电子锁中继等 目前没有非常有效的防止方法 与实现相关的攻击： 与实现时具体采用的技术有关 例如： A →B: E(K, N) B→A: E(K, N-1) 如果采用按位加密算法，且 N 碰巧是奇数（末位为 1 ），则 E(K,N) 与 E(K,N-1) 的差别仅仅是末位相反，因而可以攻击 防止方法：选择合适的密码算法和密码体制 密码学导论 -- 中国科学技术大学 19

20 .绑定攻击： 假冒身份 / 公钥 防止方法：在消息中添加主体的身份信息，并签名 封装攻击： 攻击者做为协议参与一方，将它所需要的消息封装为合法消息的一部分，诱使另一方解密、签名等 防止方法：添加完整性校验 密码学导论 -- 中国科学技术大学 20

21 .设计密码协议的注意事项 尽量用一次性随机数代替时间戳 回避时钟同步 具备抵抗常见攻击的能力 明确使用于网络结构的哪个协议层 明确所需的数据处理能力 明确所采用的密码算法 便于进行功能扩充 最少的安全假设 密码学导论 -- 中国科学技术大学 21

22 .第二节 公平计算 密码学导论 -- 中国科学技术大学 22

23 .一、位承诺 例 1 ：预测纸牌的魔术 Alice 写下预测并装入信封； Bob 随机抽牌，出示； Alice 打开信封，验证她的预测 例 2 ： Alice 和 Bob 在网上玩猜拳 Alice 说：告诉我你出的是什么，我不会变，相信我 例 3 ：“分歧争端机” 《 非诚勿扰 》 位承诺 ： Alice 想对 Bob 做一个承诺（一个位或位序列），但要直到某个时间 / 事件后才揭示她的承诺；另一方面， Bob 希望确信 Alice 做出承诺后，没有改变承诺的内容 密码学导论 -- 中国科学技术大学 23

24 .一、位承诺 例 1 ：预测纸牌的魔术 Alice 写下预测并装入信封； Bob 随机抽牌，出示； Alice 打开信封，验证她的预测 例 2 ： Alice 和 Bob 在网上玩猜拳 Alice 说：告诉我你出的是什么，我不会变，相信我 例 3 ：“分歧争端机” 《 非诚勿扰 》 位承诺 ： Alice 想对 Bob 做一个承诺（一个位或位序列），但要直到某个时间 / 事件后才揭示她的承诺；另一方面， Bob 希望确信 Alice 做出承诺后，没有改变承诺的内容 密码学导论 -- 中国科学技术大学 23

25 .使用单向函数的位承诺 承诺部分： Alice 产生两个随机位串 R 1 ， R 2 Alice 产生想承诺的位（串） b ，组成消息 M=R 1 ||R 2 ||b Alice 计算 h=H(M), A→B ： h, R 1 揭示部分： A→B: M Bob 对比 R 1 ，计算并对比 h ，如匹配，则接受位承诺 b R 2 的作用是避免 Bob 做穷举攻击 哈希函数应抗强碰撞 密码学导论 -- 中国科学技术大学 25

26 .使用伪随机序列发生器的位承诺 承诺部分： Bob 产生随机位串 R B ， B →A: R B Alice 产生想承诺的位（串） b Alice 产生随机种子 s ，用伪随机数发生器产生串 R A 对 R B 的每一位， Alice 将 ( R B &b )  R A 发送给 Bob ： 若 R B 的位为 0 ，则为 R A 若 R B 的位为 1 ，则为 R A 与 b 的异或 揭示部分： A →B: s Bob 验证 Alice 的行为是合理的 R B 应足够长，伪随机数发生器不可预测 密码学导论 -- 中国科学技术大学 26

27 .模糊点 (blob) ： Alice 发送给 Bob 用来做承诺的串 模糊点的特性： Alice 能够对模糊点承诺，以此来承诺一个位 Alice 能够揭示她所承诺的任何模糊点。模糊点被承诺后， Alice 无法改变该模糊点所承诺的位值。 因而 Bob 才能相信 Alice 没有作弊 Bob 不知道 Alice 将如何揭示未被打开的模糊点，即使他看见 Alice 揭示别的模糊点 Bob 不能作弊 模糊点除了 Alice 承诺的位外，不携带任何有用信息 密码学导论 -- 中国科学技术大学 27

28 .二、公平的硬币抛掷 懒人 Alice 和 Bob 住在一起，一天没水喝了。于是两人想通过掷硬币的方式决定谁去打水。可是没有实际的物理东东让他们抛掷。两人决定用思维来抛掷硬币，然后将两人的结果异或 两人都不相信对方会遵守协议，都努力窃取对方结果 一个解决办法是写下来再出示（不会被掉包？） 可以用位承诺协议来辅助完成： Alice 做一个随机位的承诺 Bob 来猜测这个位 Alice 揭示结果，若 Bob 猜中，则 Bob 赢，否则 Bob 输 密码学导论 -- 中国科学技术大学 28

29 .二、公平的硬币抛掷 懒人 Alice 和 Bob 住在一起，一天没水喝了。于是两人想通过掷硬币的方式决定谁去打水。可是没有实际的物理东东让他们抛掷。两人决定用思维来抛掷硬币，然后将两人的结果异或 两人都不相信对方会遵守协议，都努力窃取对方结果 一个解决办法是写下来再出示（不会被掉包？） 可以用位承诺协议来辅助完成： Alice 做一个随机位的承诺 Bob 来猜测这个位 Alice 揭示结果，若 Bob 猜中，则 Bob 赢，否则 Bob 输 密码学导论 -- 中国科学技术大学 28