密钥分发和密钥协商 Key Distribution & Key Negotiation,祝烈煌 北京理工大学计算机学院 liehuangzbit.edu.cn 2010年,密钥分发,解决秘密密钥建立问题的常见方法包括：密钥预分发 会话密钥分发 密钥协商,密钥分发,密钥预分发密钥预分发方案中，TA以一种安全的方式为网络中的每个用户“提前”分发密钥信息，注意密钥分发时需要一个安全信道。此后，所有的网络用户可以使用这些秘密密钥来加密其在网络中传输的消息。该方案本质是网络中的每一对用户都能够根据他们掌握的密钥信息来确定一个密钥，且该密钥只有他们二人知道。,密钥分发,会话密钥分发在会话密钥分发中，当网络用户请求会话密钥时，一个在线的TA选择会话密钥并通过一个交互协议分发给他们。这样的协议称为会话密钥分发方案并记为SKDS。,密钥分发,密钥协商密钥协商是指网络用户通过一个交互协议来建立会话密钥的情形。这样的协议称为密钥协商方案，并且记为KAS。密钥协商可以基于对称密码体制，也可以基于公钥密码体制，通常不需要一个在线的TA。,密钥分发,长期密钥和会话密钥长期密钥(Long Live Key)指预先计算并安全存储的密钥。或者说，长期密钥可以根据需要由安全存储的秘密信息非交互地计算出来。长期密钥可以是秘密密钥，为一对用户共同拥有，或者为一个用户与TA共同拥有。也可以是一个私钥，它与存储在用户证书中的公钥相对应。,密钥分发,长期密钥和会话密钥会话密钥指在特定的会话中，一对用户经常使用的秘密的短期会话密钥，当会话结束时就会把该会话密钥丢弃。会话密钥通常是秘密密钥(也称对称密钥)，用于对称密码体制或者MAC。长期密钥通常用于协议中传输加密的会话密钥。,密钥预分发,Diffie-Hellman KPS公开的域参数包括：群 ，一个阶为 的元素利用 的证书中的公钥 和他自己的私钥 计算3. 利用 的证书中的公钥 和他自己的私钥 计算,密钥预分发,Diffie-Hellman KPS注意：这个密钥预分发方案并未进行任何交互，并且假定用户的私钥是安全的，所以不需要考虑主动敌手的可能性。显然，如果DDH问题是困难的，那么该方案就是计算安全的。,密钥预分发,Blom KPS 素数p公开，用户 公布一个元素 。TA选择三个随机数 ，并构造多项式TA为用户 计算并通过安全信道向 发送 。 4. 和 进行安全通信，分别计算密钥,会话密钥分发,Needham-Schroeder会话密钥方案1) Alice选择一个随机数 ，向TA发送 ， 和TA选择一个随机的会话密钥 。然后计算票据以及 并发送 给Alice(这里假设TA与每个用户都共享一个秘密密钥)Alice使用密钥 解密 得到 和 ，然后发送 给Bob Bob使用密钥 解密 得到 ，然后Bob选择随机数 并发送 给BobAlice使用密钥 解密 得到 ，然后发送,会话密钥分发,Needham-Schroeder会话密钥方案,A,B,TA,会话密钥分发,对NS方案的Denning-Sacco攻击(已知会话密钥攻击)假设敌手以某种方式得到了会话 的会话密钥 ，那么敌手攻击会话 流程如下：,C,B,会话密钥分发,Kerberos密钥分发方案 Kerberos是MIT于20世纪80年代后期和90年代早期开发出来的一个系列会话密钥分发方案。这里给出该方案的第5版简化形式。,A,TA,B,L是密钥K的有效期或者说是使用期限 这用于防止重放攻击，但所有用户要有一个同步时钟,time是Alice的当前时间,会话密钥分发,NS方案 VS Kerberos方案NS方案中，TA通过Alice给Bob的票据 需要利用Alice的密钥重新进行加密，这没有任何益处，因为Alice发送该票据给Bob后，其他人都可以看到这条票据；Kerberos方案中并未对该票据进行双重加密。NS方案存在Denning-Sacco攻击，但Kerberos方案通过检查时间和有效期来限定了实施Denning-Sacco攻击的时间周期。Kerberos方案中，第三步和第四步利用 加密时间的目的是发送方向接收方证明自己知道密钥。,密钥分发,Bellare-Rogaway方案 1995年，Bellare和Rogaway提出了一个会话密钥分发方案,A,B,TA,会话密钥分发,Bellare-Rogaway方案注意事项：TA中生成的挑战是采用完美的随机数生成器产生的。该方案没有实现密钥确认。也就是说，Alice/Bob在收到会话密钥后无法确认Bob/Alice也获得了会话密钥。该方案可以保证任何其他人都不能计算出新的会话密钥。否则，就存在一个多项式时间算法要么可以攻陷加密算法，要么可以攻陷MAC算法。,会话密钥分发,Bellare-Rogaway方案证明思路：BR是一个密钥分发方案，因此攻陷该方案就是敌手执行协议并使得双方被分发得到两个不同的会话密钥。首先，在协议的多次(总次数是密钥长度的一个多项式)执行过程中，Alice/Bob选择的随机挑战出现重复的概率可以忽略不计，因为挑战长度与密钥长度是同一个数量级的。,会话密钥分发,Bellare-Rogaway方案证明思路：其次，在Alice/Bob选择的随机挑战没有重复的情况下，为了攻陷协议，敌手在不知道TA与Alice/Bob共享密钥的情况下，要么找到一个 ，使得 或者；要么对某个 或者 伪造出对应的MAC值。也就是说，敌手要么攻陷了加密算法，要么攻陷了MAC算法。最后，由于加密算法和MAC算法是安全的，所以BR方案是安全的。,密钥协商,密钥预分发方案和会话密钥分发方案都需要一个可信权威机构TA来选取密钥，并将他们分发给网络用户。下面我们讨论密钥协商方案，这类方案不需要TA的参与，而是通过一个交互协议来共同确定一个新的会话密钥。我们主要是在公钥环境下来讨论密钥协商方案。,密钥协商,Diffie-Hellman 密钥协商方案公开的域参数包括：群 ，一个阶为 的元素选取一个随机数 ， 然后计算并发送选取一个随机数 ， 然后计算并发送计算计算,密钥协商,对Diffie-Hellman密钥协商方案的中间人攻击安全的密钥协商协议： 协议执行完成后，双方协商出的密钥相同 敌手实施任何攻击流程后，诚实参与者会“接受”的概率 可忽略,U,W,V,密钥协商,认证密钥协商方案，也被称为端-端密钥协商方案(STS)，是由Diffie, vanOorschot, Wiener提出的。其思想是将Diffie-Hellman密钥协商方案和一个安全的交互识别方案结合在一起。通过对随机挑战进行签名提供了交互认证。简化的端-端密钥协商协议,U,V,密钥协商,简化的端-端密钥协商方案可抵抗中间人攻击,U,W,V,密钥协商,密钥协商方案的三层保证机制：1. 隐式密钥认证 如果U可以被确保除了V之外，没有人能计算出K（特别是敌手），则该方案提供了隐式密钥认证。 2. 隐式密钥确认 如果U可以被确保V可以计算出K（假设V按照规定执行了方案），并且除了V之外，没有人能计算出K，则该方案提供了隐式密钥确认。 3. 显式密钥确认 如果U可以被确保V已经计算出了K，除了V之外没有人能计算出K，则该方案提供了显式密钥确认。,密钥协商,Bellare-Rogaway会话密钥方案提供了隐式密钥认证。在该方案中双方都不能确认对方是否已经收到(或者能够计算出)会话密钥。端-端密钥协商方案对交换的指数进行了数字签名，在DDH问题是难解的假设条件下，该方案为双方提供了隐式密钥确认特性。Kerberos和Needham-Schroeder协议都提供了显式密钥确认。,密钥协商,已知会话密钥攻击当实际的具有多个用户的网络环境下，可能会同时有多个端-端方案的会话发生。我们需要考虑不同的会话之间可能造成的影响。因此，我们研究已知会话密钥攻击下端-端方案的安全性。即 假设敌手可以被告知某些会话的会话密钥，如 ，敌手希望借助这些会话密钥来得到其他会话的会话密钥。,密钥协商,下面我们证明如果DDH问题是难解的，那么端-端密钥协商方案在已知密钥攻击下是安全的。现在我们来说明Oscar如何构造一个模拟 的。 Oscar选取 Oscar选取一个随机值 ，并计算 Oscar计算 Oscar定义,密钥协商,无论是Oscar同伴选取 还是Oscar自身选取 ， 都是均匀 选取的。所以有：又由于DDH问题的难解性，给定 对于敌手的攻击具有不可区分性，否则可以利用敌手的攻击来解决DDH问题。因此，无论Oscar利用已知会话密钥攻击做什么，他也可以使用一个完全的被动攻击做同样的事情。,密钥协商,MTI/A0密钥协商方案 该方案由Matsumoto，Takashima和Imai构造。公开的域参数包括：群 ，一个阶为 的元素 每个用户 有一个秘密指数 ，其中 对应 的公开值为 ， 被包含在T的证书中并被TA签名。选取一个随机数 ， 计算然后 将 和 发送给选取一个随机数 ， 计算然后 将 和 发送给,密钥协商,MTI/A0密钥协商方案计算出会话密钥 ，其中 从 中获得。计算出会话密钥 ，其中 从 中获得。会话结束时， 和 计算出相同的会话密钥,密钥协商,对于MTI/A0的已知会话密钥攻击1,V,W,U,密钥协商,对于MTI/A0的已知会话密钥攻击2 (Burmester三角攻击),V,W,U,S,S1,S2,密钥协商,对于MTI/A0的已知会话密钥攻击2 (Burmester三角攻击)会话 的密钥 分别如下：给定 ，W可以计算：,密钥协商,使用自认证密钥的密钥协商Girault公钥生成 注： 是公开的， 是仅由TA所知道的秘密值。选取一个秘密指数 ，计算将 和 给TATA计算TA将 给,密钥协商,Girault密钥协商方案选取一个随机数 ，计算然后 将 和 发送给 。选取一个随机数 ，计算然后 将 和 发送给 。计算计算,群组密钥协商,群组密钥协商(Group Key Agreement)群组的多个成员一起参与密钥生成 群组中的密钥是由每个成员提供的参数以及密钥生成算法共同决定的 群组中任何成员均不能事先确定密钥。,群组密钥协商,群组密钥协商的常见算法：CKD（Centralized Group Key Distribution） BD（Burmester-Desmedt） GDH（Group Diffie-Hellman） TGDH（Tree-Based Group Diffie-Hellman） ECDH（Elliptic Curve Diffie-Hellman） 。,