密码学导论˙第8章 消息认证及其算法 12学时 李卫海

本章内容 第五节 数字签名协议 第一节 认证的概念 第二节 消息认证的实现 第六节 身份认证 第三节 消息认证算法 第七节 认证应用实例 消息认证、数字签名、身份认证 第二节 消息认证的实现 消息加密、消息认证码MAC、散列函数 MAC和散列函数的基本使用方式 散列函数和MAC的安全性，生日攻击 第三节 消息认证算法 MD5、SHA RIPEMD-160、Whirlpool HMAC、CMAC 第四节 数字签名的实现 直接数字签名、仲裁数字签名 时间标记、多重签名、签名与加密的顺序 第五节 数字签名协议 RSA签名、ElGamal签名 ECC签名、数字签名标准DSS 第六节 身份认证 口令认证、挑战-响应身份认证、零知识身份认证 单向认证、双向认证 针对认证的攻击 第七节 认证应用实例 Kerberos 密码学导论--中国科学技术大学

第一节 认证的概念 密码学导论--中国科学技术大学

网络环境中常见攻击 Disclosure 泄露 Traffic analysis 流量分析 Masquerade 伪装 确定连接频率、持续时间、消息量 Masquerade 伪装 身份假冒 Content modification 内容篡改 插入、删除、转换、修改 Sequence modification 顺序篡改 插入、删除、重排序 Timing modification 计时篡改 延时、重放 Source repudiation 信源抵赖 Destination repudiation 信宿抵赖 加密 认证 密码学导论--中国科学技术大学

认证服务和功能 认证是证实信息交换过程有效性和合法性的一种手段，包括对通信对象的认证(身份认证)和报文内容的认证(报文认证)，起到数据完整性的保护。包括 信息的真实性 存储数据的真实性 接收方提供回执 发送方不可否认 时效性和公证可能性 认证的目的 防篡改、防伪装、防重放、防抵赖等等 密码学导论--中国科学技术大学

认证包括两种 消息认证（也称报文认证） 身份认证（也称实体认证） 在产生消息时进行： MAC、Hash、数字签名 涉及的是特定实体所声称的特定消息 可以兼具认证信源身份 身份认证（也称实体认证） 在协议执行时进行：身份认证协议 通常涉及的是特定实体所具有某些信息，而非传递的消息 密码学导论--中国科学技术大学

1、消息认证 消息认证包括： 通常与实际的安全需求结合起来考虑 三种操作可以提供消息认证： 消息内容的认证：保护报文的完整性 消息源的认证：确认原始发报人身份，不可抵赖 消息时间性认证：确认消息的即时性 需要协议来完成，在下一章详细讨论 通常与实际的安全需求结合起来考虑 三种操作可以提供消息认证： 消息加密 消息认证码message authentication code (MAC) Hash函数 密码学导论--中国科学技术大学

例: TCP包结构 TCP头结构提供了额外的特定结构，保证密文不被篡改 密码学导论--中国科学技术大学

帧校验码(FCS) 用来提供特定结构，确保密文不被篡改 FCS和加密函数的顺序很关键 密码学导论--中国科学技术大学

2、数字签名 接收者可以凭借消息上所附加的某种东西，确认发信人的身份。这种东西，就是签名 签名一般应具有的性质： 签名是独一无二的，是发信人所专有的 签名一般应具有的性质： 签名应当是可信的：签名者知道他所签名的内容 避免不知情签名。例如，夹在大量文件当中；垫复写纸 签名应当是不可伪造的：确实是签名者所为 模仿他人的笔迹 签名应当是不可重用的：不能被移做它用 扫描的签名图像可以复制-粘贴 签名的文件应当是不可改变的：不能篡改内容 文件中的空白区域；甚至空白签名 签名应当是不可抵赖的：不能否认其行为 声称他人伪造自己的签名而抵赖 密码学导论--中国科学技术大学

数字签名应当拥有的额外性质： 数字签名应满足以下条件： 实现方式：私钥相关运算 接收方能够验证签名人、签名日期和时间 可以由第三方仲裁，以解决争执 认证被签名的消息内容，即认证完整性、真实性 数字签名应满足以下条件： 必须与消息相关 必须使用发送者唯一拥有的信息——防止伪造和否认 产生签名、识别和验证是容易的 伪造在计算上是不可行的，无论是给定签名伪造消息，或是给定消息伪造签名 可以存储、拷贝 实现方式：私钥相关运算 密码学导论--中国科学技术大学

3、身份认证 身份认证协议的内容 身份认证协议关注： 识别：明确访问者身份 验证：确认访问者声称的身份 验证已知事物：口令（或密钥）、个人识别码（PIN）、在挑战－响应协议中被证实的秘密或私钥 已拥有的事物：磁卡、IC卡、智能卡、口令生成器 固有事物：生物特征（指纹、唇纹、虹膜）、下意识行为（笔迹） 身份认证协议关注： 确认通信各方身份，并交换会话密钥（需要的话） 单向认证或相互认证 关键问题包括： 及时性——防止重放攻击 机密性——保护私钥和会话密钥 密码学导论--中国科学技术大学

身份认证协议的设计目标： A可以成功地向B认证他自己，即B完成协议接受A的身份； （不可传递性）B不能利用和A身份认证过程的数据来成功地向第三方C假冒A； （不可假冒）任何不同于A的实体C，假冒A执行协议，使得B完成协议并接受A的身份的概率可忽略不计； 上述3点恒为真，即使 敌手C观察到大量A和B之间的认证 敌手C参与了A和B中一方或双方的身份认证协议的执行 敌手C可以发起并行攻击，同时运行多个实例 密码学导论--中国科学技术大学

身份认证协议的性能： 身份认证的实现方法： 身份认证的交互性： 通信效率：传输的步数和需要的带宽或总传输量 计算效率：执行协议所需要的操作数 单向认证、相互认证、群认证、可信中继 通信效率：传输的步数和需要的带宽或总传输量 计算效率：执行协议所需要的操作数 第三方（若有）的可信程度和是否需要实时参与 安全保证性：认证信息不被泄漏 身份认证的实现方法： 口令（弱认证） 挑战－响应身份认证（强认证） 零知识的身份认证 密码学导论--中国科学技术大学

第二节 消息认证的实现 密码学导论--中国科学技术大学

三种操作可以提供消息认证： 消息加密 消息认证码message authentication code (MAC) Hash函数 密码学导论--中国科学技术大学

一、消息加密 消息加密本身能够提供一定的认证功能 使用对称密钥： 使用公钥密码： 发报人身份确认 报文完整性确认 仅有收发双方拥有密钥 报文完整性确认 当报文中有足够的格式信息、冗余或校验时，修改密文会破坏这些信息 使用公钥密码： 公钥加密提供报文保密性确认，不能提供身份确认 任何人都可以拥有公钥 私钥签名提供信源身份确认，不提供保密性 也需要报文具有特定格式、冗余或校验 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

二、消息认证码MAC 使用密钥产生短小的定长数据分组，即所谓的密码校验MAC，将它附加在报文中。 通信双方共享密钥k，发送方计算MAC=C(k,m)并附在报文后。接收方根据m重新计算MAC，并与接收到的MAC比较。若密钥不公开且MAC匹配，则： 接收方可以确信报文未被更改； 接收方可以确信报文来自声称的发送者。 MAC函数类似加密，但非加密，也无需可逆 报文鉴别不提供保密 常将MAC直接与明文并置，然后加密传输 密码学导论--中国科学技术大学

MAC的性质 MAC是一种密码校验和：MAC = C(k,m) 显然，MAC是多对一的映射 用于对可变长消息m编写摘要 使用密钥k 产生一个定长的认证码 显然，MAC是多对一的映射 多个消息可能具有相同的MAC 但根据指定MAC构造消息很难 密码学导论--中国科学技术大学

MAC的基本使用方式 密码学导论--中国科学技术大学

MAC的应用场合 对称加密同时提供保密和认证，为什么还要用只提供认证的MAC？ 将一条非秘密消息广播给很多人时——不需要加密，也不需要每个人都做认证 信息传输速度过快，没时间逐个解密——可以随机选择认证 计算机程序的防篡改——每次运行都解密是很麻烦的 用户不希望做认证的人/机构得到明文——不让外人解密 认证和保密性的分开，有利于系统的层次化设计 密码学导论--中国科学技术大学

对MAC的攻击 对MAC密钥的穷举攻击 若密钥长度(k)大于MAC长度(n) 若密钥长度(k)小于MAC长度(n) 对消息m1及对应MAC1尝试密钥，平均会有2k-n个匹配密钥 对消息m2及对应MAC2尝试上面得到的密钥，平均会有2k-2n个匹配密钥 重复下去，直到得到唯一密钥 若密钥长度(k)小于MAC长度(n) 很可能第一次尝试就得到唯一密钥 密码学导论--中国科学技术大学

消息构造攻击 MAC必须仔细设计 例：假设一个MAC算法为： m=X1||X2||…||Xm， Δ(m)=X1X2…Xm, MAC=C(k,m)=E(k,Δ(m)) 攻击者可以构造： m'=Y1||Y2||…||Ym， Ym=Y1Y2…Ym-1Δ(m) 密码学导论--中国科学技术大学

对MAC的要求 应考虑对MAC函数的各种类型的攻击 当密钥k保密时，MAC函数应满足： 抗基于选择明文的穷举攻击 MAC函数应当等概地使用消息的所有比特位 密码学导论--中国科学技术大学

数据认证算法(DAA)FIPS PUB 113 待认证数据为D1||D2||…||DN MAC值为DAC 以密码分组链接(CBC)为操作方式，又称为CBC-MAC 用0作为初始化向量 基于DES加密算法 待认证数据为D1||D2||…||DN MAC值为DAC 密码学导论--中国科学技术大学

三、散列函数Hash function 散列函数对任意长度报文m，产生定长的散列码h=H(m)，亦称报文摘要Message Digest，收缩函数、操作检验码、信息完整性校验(MIC)、哈希值等 是报文所有比特的函数值，具有差错检测能力 哈希值是明文的“指纹”或是摘要。对哈希值的数字签名，可以视为对此明文的数字签名 可以用来提高数字签名的效率 通常认为hash函数是公开的，无密钥的 MAC是有密钥的 密码学导论--中国科学技术大学

对避免加密的方法重视的原因 散列函数的应用 加密过程很慢，硬件开销，传输量问题，专利问题，出口限制等等 利用散列函数进行双向鉴别，如确认双方是否共享KAB 用作消息完整码MIC (Message Integrity Code) 用于加密：将分组加密转换成序列加密，产生流密钥。有OFB和CFB方式。 密码学导论--中国科学技术大学

Hash函数的基本使用方式 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

简单散列函数 经度（垂直）冗余校验 带循环移位的冗余校验 安全性差 每分组对应位异或 数据格式可能影响有效性 每处理一分组，散列值循环移位一次 可以保护数据完整性 安全性差 很容易构造假消息 只需在假消息后附加一个特定分组 分组顺序可以改变 密码学导论--中国科学技术大学

对散列函数的要求 应用要求： 安全性要求： 对任意明文m，哈希函数H(m)由软/硬件容易实现； 单向性：对任意哈希值h，要找到一个明文m与之对应，即h=H(m)，在计算上不可行； 抗伪造攻击 抗弱碰撞：给定明文m1，要找到另一明文m2，具有相同哈希值，即h(m1)=h(m2)，在计算上不可行； 抗强碰撞：要找到任意一对具有相同哈希值的明文，即(m1,m2)，h(m1)=h(m2)，在计算上不可行。 抗生日攻击 应用在数字签名上的哈希函数必须是强哈希函数 弱哈希函数 强哈希函数 密码学导论--中国科学技术大学

用密文分组链接CBC对整个消息和散列码加密，得 Y1,Y2,…,YN,YN+1 例：美国国家标准局曾用过的一种方法： C=XN+1=X1X2…XN 用密文分组链接CBC对整个消息和散列码加密，得 Y1,Y2,…,YN,YN+1 不安全。注意， XN+1=X1X2…XN =[IVDK(Y1)][Y1DK(Y2)]…[YN-1DK(YN)] 密文分组的顺序改变，对散列码没有影响 密码学导论--中国科学技术大学

典型的安全散列函数链接结构 若压缩函数具有抗碰撞能力，那么迭代散列函数也具有抗碰撞能力 密码学导论--中国科学技术大学

四、基于生日悖论的攻击 数学背景——生日悖论： k要多大，才能使得在k个人中，至少有两个人生日相同的概率大于1/2？ k个人生日的总排列数是365k，k个人有不同生日的总排列数为N = Pk365 = 365!/(365-k)! k个人有不同生日的概率： Q(365,k)=[365!/(365-k)!]/365k=365!/(365k(365-k)!) k个人中至少有两个人有相同生日的概率是： P(365, k) = 1- Q(365, k) 密码学导论--中国科学技术大学

计算得P(365, 23) = 0.5073，即k = 23 P(365,50)=0.9744; P(365, 100)=0.999 999 8 密码学导论--中国科学技术大学

生日悖论的推广（元素重复的一般情形）： 生日悖论的函数形式： 给定一个在1到n之间均匀分布的随机整数变量和k个实例，那么至少有一个重复的概率： P(n,k)=1-[n!/(n-k)!]/nk > 1-exp[-k(k-1)/(2n)] 当k ≈ 1.18n1/2时，P(n,k)>0.5 生日悖论的函数形式： 若一个函数可能有n个函数值，且已知一个函数值h(x)，任选k个数作为函数输入值，问：k必须多大才能保证找到至少一个满足h(x)=h(y)的输入值y的概率大于1/2？ P(n,k) = 1-(1-1/n)k ≈ 1-k/n 当k=n/2时，P(n,k)>0.5 密码学导论--中国科学技术大学

对输出n比特的hash函数，生日攻击的代价为2n/2 两个集合中元素的重复： 给定一个在1到n之间均匀分布的随机整数变量和它的两个实例集，每个集中有k个元素，那么这两个集相交（即至少有一个元素同属于两个集）的概率： R(n,k) = 1-((1-1/n)k)k = 1-(1-1/n)k2 > 1-e-k2/n 当k ≈ 0.83n1/2时，R(n,k)>0.5 当k = n1/2时，R(n,k)>0.6321 对输出n比特的hash函数，生日攻击的代价为2n/2 只要散列码较短，或散列码很长但可以分解为独立的子码，就存在生日攻击 密码学导论--中国科学技术大学

Yuval于1979年提出一种基于生日悖论的攻击： 攻击者需要在消息进行Hash前就介入。 假设消息签名方法是对m位散列码加密后附于消息之后 攻击者产生该消息的2m/2种同义变形，再产生伪造消息的2m/2种同义变形，并分别计算它们的散列值； 根据生日悖论，这两个集合以大于0.5的概率存在相同元素，即伪造消息变形和真实消息变形中以大于0.5的概率存在一对的散列值相同 攻击者将该真实消息的变形提交，进行散列运算及签名，之后，将伪造消息替代真实消息。因为它们的散列值相同，其加密签名的结果也相同。 对64位散列码，所需代价仅为232 密码学导论--中国科学技术大学

一封具有237种变形的信 密码学导论--中国科学技术大学

恶意程序的伪装？ 目前多数软件提供MD5验证，而MD5已被攻破 Windows上的应用程序多是PE格式。 PE程序一般由以下几部分构成： 可以制作两个Hash相同的程序，其一是很吸引人的某种正常用途，其二实现某种恶意攻击，会发生什么？ Windows上的应用程序多是PE格式。 PE程序一般由以下几部分构成： PE header，PE文件头 .text section，代码段 .data section，数据段 other sections (.reloc, .rdata, .tls, etc) 密码学导论--中国科学技术大学

伪装过程： 编写应用程序，在其中实现你想要的两种不同功能。 手工调整PE文件，使得其结构如下： PE header reserved block1 .text section reserved block2 .data section other sections 以PE header为前导(preamble)，搜索随机碰撞(collision)，使得： X1 = PE header || R1; X2 = PE header || R2; MD5(X1) = MD5(X2) 密码学导论--中国科学技术大学

将R1内容填入reserved block2，然后将R1和R2内容分别添入reserved block1处，得到两个应用程序文件： 文件1 文件2 PE header PE header R1 R2 .text section .text section R1 R1 .data section .data section other sections other sections 后续部分相同，因此MD5保持相同 在应用程序的开始代码处，拿reserved block2处的内容和reserved block1处的内容比较，如果相等后面的流程实现功能一，如果不相等实现功能二。这样就实现了任意功能的两个程序，并保持他们的MD5相同。 密码学导论--中国科学技术大学

如何利用碰撞骗得老板的签名？ 过程： 打开Y1，看到的是T1；打开Y2，看到的是T2。 选择一种高级文档语言（比如postscript）； 基于postscript的要求构造preamble，寻找MD5随机碰撞： X1 = preamble; put(R1); X2 = preamble; put(R2); MD5(X1) = MD5(X2) 给X1和X2添加相同后缀S：MD5(X1||S) = MD5(X2||S) 准备两份文本T1和T2，T1是正常文本（用来骗取签名），T2是其他用途文本。 最后形成两份postscript文档： Y1 = preamble; put(R1); put(R1); if(=) then T1 else T2 Y2 = preamble; put(R2); put(R1); if(=) then T1 else T2 打开Y1，看到的是T1；打开Y2，看到的是T2。 密码学导论--中国科学技术大学

分组链接技术 Rabin于1978年提出一种算法： 安全么？ 消息M=M1||M2||…|MN 使用对称分组加密体制（如DES），分组长度m H0=初始值 Hi=E(Mi,Hi-1) 散列码G=HN 安全么？ 密码学导论--中国科学技术大学

生日攻击能成功地攻击任何使用密文分组链接但不使用密钥的散列方法 基于生日悖论的“中间相遇”攻击 计算消息的散列值G 构造消息Q1||Q2||…||QN-2，并计算HN-2， 产生2m/2个随机分组，对每一分组X，计算E(X,HN-2)；再产生2m/2个随机分组，对每一分组Y，计算D(Y,G) 根据生日悖论，存在X和Y满足E(X,HN-2)=D(Y,G)的概率较大 构造消息Q1||Q2||…||QN-2||X||Y，其散列码也为G 生日攻击能成功地攻击任何使用密文分组链接但不使用密钥的散列方法 密码学导论--中国科学技术大学

散列函数和MAC的安全性 穷举攻击 MAC的结构种类多，对它进行攻击的研究少 散列函数 报文鉴别码 2n/2将决定散列码抗击强行攻击（生日攻击）的强度 攻击单向性，代价2n；攻击抗弱碰撞性，代价2n；攻击抗强碰撞性，代价2n/2 报文鉴别码 攻击密钥空间，代价2k 攻击MAC值（给定消息求MAC，或给定MAC求对应消息），代价2n MAC的结构种类多，对它进行攻击的研究少 密码学导论--中国科学技术大学

第二节 消息认证算法 密码学导论--中国科学技术大学

散列函数安全性 有算法可以将MD4的抗强碰撞能力降到220 已有对RIPEMD-128,MD5和SHA-1的攻击，降低其抗强碰撞能力 2012年选出SHA-3优胜者Keccak，采用海绵结构 散列函数 分组长度 摘要长度 抗单向性 抗强碰撞 MD2 128 2128 264 MD4 512 MD5 RIPEMD-128 SHA-1 160 2160 280 SHA-256 256 2256 SHA-384 1024 384 2384 2192 SHA-512 2512 密码学导论--中国科学技术大学

一、信息摘要算法MD5(RFC 1321) 输入：长度小于264的明文， 输出：128位的报文摘要。 MD5报文摘要流程 明文分成L块，每块512位，每块再分成16份，每份32位子明文块(sub block)，M[k], k = 0, 1, 2…, 15 步骤1：增加填充位，使长度模512等于448 填充由一个1和后续的0组成 步骤2：填充长度，用64位表示原始消息长度，低位在前 步骤3：初始化MD缓冲区 步骤4：以512位的分组(16个字)为单位处理消息 步骤5：输出 密码学导论--中国科学技术大学

MD5结构 密码学导论--中国科学技术大学

每分组的运算 HMD5由四轮运算组成 每轮16步，共64步，每步对4个32位寄存器中的数据进行处理 4个32位的寄存器初始值(存储时低字节在前）是： A = 67452301; B = EFCDAB89; C = 98BADCFE; D = 10325476; 经过64步处理后，ABCD中的值即为128位摘要 密码学导论--中国科学技术大学

单步的操作(压缩函数) {a,b,c,d}{d,((a+g(b,c,d)+M[k]+T[i])<<<s)+b,b,c} a,b,c,d是寄存器ABCD的四个字，它按一定次序变化 bcd寄存器的内容以非线性函数 g处理。g是每轮对应的非线性 函数F,G,H,I 结果与寄存器a 、32位子明文 块M[k]、一个固定数T[i]相加。 “+”是模232加法 结果左移s位，再与寄存器b相加 最后的32位结果重新存入abcd 密码学导论--中国科学技术大学

T[i]=232×abs(sin(i))的整数部分，i是弧度 密码学导论--中国科学技术大学

各轮非线性函数运算 轮 表 示 定 义 1 F(b, c, d) (b&c) | ((~b)&d) 2 G(b, c, d) 表 示 定 义 1 F(b, c, d) (b&c) | ((~b)&d) 2 G(b, c, d) (b&d) | (c&(~d)) 3 H(b, c, d) bcd 4 I(b, c, d) c(b|(~d)) 密码学导论--中国科学技术大学

各步中abcd、及 k、s、i的取值 密码学导论--中国科学技术大学

与MD4的比较 多一轮操作 每一步都使用不同的常数T[i] 比MD4多一种逻辑运算 每一步都有一个取代一个寄存器值的操作，加快了雪崩效应。 密码学导论--中国科学技术大学

MD5的强度 MD5的每一位都依赖于消息的所有位 逻辑函数F,G,H,I的使用增加了混淆程度 MD5可能是128位Hash码中最强的算法 生日攻击代价为264数量级 王小云的碰撞攻击算法效率很高 密码学导论--中国科学技术大学

二、安全散列算法SHA SHA由美国标准与技术研究所NIST于1993年设计 算法称为SHA，对应标准称为SHS 标准FIPS 180-1，及互联网中RFC3174 算法称为SHA，对应标准称为SHS SHA-1建立在MD4算法之上 产生160比特消息摘要 2005年NIST宣布将逐步废止SHA-1 此后不久，王小云公开攻击算法，寻找碰撞的计算量为269 至2011年，寻找碰撞的计算量为263 密码学导论--中国科学技术大学

概述 要求输入小于264位，输出为160位 处理过程与MD5类似。用同样方式填充明文，并分成512位的定长块，每一块与当前信息摘要值结合，产生信息摘要的下一个中间结果，直到处理完毕。 共扫描5遍，效率略低于MD5（4遍），强度略高 使用5个寄存器：A, B, C, D, E。 密码学导论--中国科学技术大学

基本算法 初值： A=67452301; B=EFCDAB89; C=98BADCFE; D=10325476; E=C3D2E1F0 A、B、C、D、E被复制到AA、BB、CC、DD、EE，进行四轮迭代，每轮20步运算，每一步对三个寄存器进行非线性操作，然后移位。每轮有一个常数k。 密码学导论--中国科学技术大学

消息扩展 Wt=Mt(输入的相应消息字)，0<=t<=15 Wt=Wt-3  Wt-8  Wt-14  Wt-16，16<=t<=79 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

单步操作(压缩函数) 基本运算 {A,B,C,D,E}{(CLS5(A)+ft(B,C,D)+E+Wt+Kt),A,CLS30(B),C,D} 其中，A, B, C, D, E为寄存器 t：步数 ft：基本逻辑函数 CLSx：左循环移位x位 Wt：由输入导出的32位字 kt：常数 +：模232的加运算 密码学导论--中国科学技术大学

步 常数Kt ft(B, C, D) 0~19 5A827999 (B&C) | ((~B)&D) 20~39 6ED9EBA1 BCD 40~59 8F1BBCDC (B&C) | (B&D) | (C&D) 60~79 CA62C1D6 密码学导论--中国科学技术大学

SHA-1与MD-5的比较 抗强行攻击的安全性 抗密码分析的安全性 速度 简单性和紧凑性 低字节在前(MD5)和高字节在前结构(SHA-1) 都是32位加法运算 SHA-1执行80步，缓冲区160位 MD5执行64步，缓冲区128位 简单性和紧凑性 都易于实现 低字节在前(MD5)和高字节在前结构(SHA-1) 没有本质区别 密码学导论--中国科学技术大学

修订版本 2002年，NIST发布修正版FIPS 180-2 增加三个新版本：SHA-256, SHA-384, SHA-512 最初目的是与由于使用AES而增加的安全性相应 SHA-224、SHA-256、SHA-384、SHA-512合称为SHA-2 2012年3月发布FIPS 180-4 密码学导论--中国科学技术大学

SHA-512 密码学导论--中国科学技术大学

SHA-512 密码学导论--中国科学技术大学

SHA-512 密码学导论--中国科学技术大学

SHA-512 密码学导论--中国科学技术大学

常量与函数定义 密码学导论--中国科学技术大学

三、RIPEMD-160 RIPEMD-160由欧洲RIPE计划下一组研究人员于1996年设计 与MD5/SHA算法结构类似 算法核心具有两个并行组，每组5轮，每轮16步 输出160位消息摘要 比MD5慢，比SHA-1快 安全性略高于MD5和SHA-1 密码学导论--中国科学技术大学

算法步骤 增加填充位，使长度模512余448 填充长度，附加原始消息长度，64比特 初始化5个32位寄存器(A,B,C,D,E) A=67452301; B=efcdab89; C=98badcfe; D=10325476; E=c3d2e1f0 每个分组10轮操作，每轮16步 分为2组，每组5轮操作，使用5个逻辑函数f1,f2,f3,f4,f5 计算结果加上输入寄存器值作为新的寄存器值 输出消息摘要为最终寄存器值 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

步 ft(B, C, D) 0 <= j <= 15 f1=BCD 16 <= j <= 31 f2=(B&C) | ((~B)&D) 32 <= j <= 47 f3=(B|(~C))D 48 <= j <= 63 f4=(B&D) | (C&(~D)) 64 <= j <= 79 f5=B(C|(~D)) 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

RIPEMD-160 vs. MD5 & SHA-1 密码学导论--中国科学技术大学

四、Whirlpool 2003年提出 得到欧盟支持的“新欧洲签名、完整性和加密计划”认可 使用修改了的AES内部结构作为压缩函数 基于分组密码的散列函数的缺点有： 密码是可逆的，随机性缺失 分组密码常会有其它规则性和弱点 速度慢 长度受限：消息摘要长度为密文分组长度（或其两倍） AES刺激人们利用强分组密码来设计安全散列函数 密码学导论--中国科学技术大学

散列函数单循环模型 散列码长度等于密码分组长度 密码学导论--中国科学技术大学

Whirlpool优点： 设计目标： 消息摘要长度为512比特 总体结构可以防止针对“基于分组密码的散列函数”的常见攻击 基于AES结构，适于软硬件实现，效率高 设计目标： 单向性：2n 抗弱碰撞：2n 抗强碰撞：2n/2 抗线性分析和差分分析 密码学导论--中国科学技术大学

整体结构 密码学导论--中国科学技术大学

Whirlpool分组密码 Whirlpool使用一个专为散列函数设计的分组密码 不能独立用于加密 具有与AES相似的安全性和效率 分组长度512比特 结构与函数与AES类似，但 输入以行优先映射到矩阵 10轮操作 不同的素多项式，GF(28) S盒子的设计不同 密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

总体结构 第r轮操作可写为： RF(Kr)=AK[Kr]◦MR◦SC◦SB 密码学导论--中国科学技术大学

状态矩阵 密码学导论--中国科学技术大学

字节代换 与AES算法相同 增加非线性 S盒子构造： 密码学导论--中国科学技术大学

列移位：第i列，向下循环移位i-1个字节 行混淆：[B]=[A][C] [C]=[01 01 04 01 08 05 02 09 09 01 01 04 01 08 05 02 02 09 01 01 04 01 08 05 05 02 09 01 01 04 01 08 08 05 02 09 01 01 04 01 01 08 05 02 09 01 01 04 04 01 08 05 02 09 01 01 01 04 01 08 05 02 09 01] 运算取模素多项式10011101 密码学导论--中国科学技术大学

密钥扩展 运用轮常数，通过算法本身，将512比特的密钥K扩展为轮密钥序列K0,K1,…,K10 第r轮的轮常数是一个矩阵RC[r]，其中只有第一行是非零的（每个元素是S盒的一个值），定义为 RC[r]0,j=S[8(r-1)+j], 0≤j≤7, 1≤r≤10 RC[r]i,j=0, 0≤i≤7, 0≤j≤7, 1≤r≤10 密码学导论--中国科学技术大学

Whirlpool性能与安全性 Whirlpool是个很新的算法，实现方面经验很少 拥有与AES相似的性能和空间特性 便于软硬件实现 占内存少 高效 与SHA-512相比，Whirlpool需要更多硬件资源，但性能更好 密码学导论--中国科学技术大学

五、消息验证码算法 可以用分组密码或带密码的散列函数来设计MAC 最初的方案： 最终导致了HMAC的出现 更倾向于使用带密码的散列函数 一般而言散列函数执行速度快 散列函数不象分组密码那样受出口限制 AES的广泛使用，使得上述意义消弱 最初的方案： KeyedHash = Hash(Key|Message) 存在缺陷 最终导致了HMAC的出现 Key摆在前面时，其作用就相当于一个初始向量。攻击者可以在后面追加内容而不被发现。 密码学导论--中国科学技术大学

1、HMAC HMAC的设计目标 RFC 2104、FIPS 198 不修改现有的散列函数，直接使用它们 可以很容易地更换新的散列函数 保持散列函数的原有性能，不能过分降低其性能 对密钥的使用和处理应较简单 根据嵌入散列函数的强度，进而分析抗密码分析的强度 RFC 2104、FIPS 198 密码学导论--中国科学技术大学

定义HMACK=Hash[(K+opad)||Hash[(K+ipad)||M)]] K+ 是K用0填充扩展，使其与分组长度一致 opad, ipad是填充常数。 ipad：00110110重复b/8次，使得K+的一半位发生变化 opad：01011100重复b/8次，使得K+的一半位发生变化 散列压缩函数的计算次数仅比消息分组数多3次 Hash可选MD5, SHA-1, RIPEMD-160, Whirlpool等 密码学导论--中国科学技术大学

总体结构 Hash、H：散列函数 IV：初始向量 M：消息 Yi：M的第i个分组 L：M中的分组数 b：每分组的比特数 n：散列码长 K：密钥，建议长度≥n K+：用0填充K左侧 ipad：00110110重复b/8次 opad：01011100重复b/8次 密码学导论--中国科学技术大学

预运算 等价于产生两个密钥相关的初始向量 f即是Hash函数中的散列压缩函数 经过预运算后，实际操作仅多执行一次散列压缩函数 密码学导论--中国科学技术大学

安全性 HMAC的安全性取决于嵌入的散列算法的强度 对HMAC的攻击方式可等价为： Hash函数的选择应在安全性和速度上做一个折中 对密钥的穷举攻击 生日攻击 由于密钥的存在，攻击者不易反复地、独自地任选一对明文进行散列运算，只能大量观察用同一密钥产生的MAC来进行攻击 MD5，SHA-1还是可以用在这里的，密钥是要经常更换的 Hash函数的选择应在安全性和速度上做一个折中 密码学导论--中国科学技术大学

2、CMAC CBC-MAC曾被政府和工业界广泛使用 为解除限制，提出了基于密文的消息认证码CMAC 但安全性有限制：消息长度仅为mn，n是密文分组长度，m是固定常数 例： 消息X（仅包含一个分组）， T=MAC(K,X)， 则有MAC(K,X||XT)=T 为解除限制，提出了基于密文的消息认证码CMAC 在NIST SP800-38B中有此规范 使用一个加密密钥，及两个由加密密钥导出的常数 X E(K, X) XT T 中间也可以插入更多个分组，只需保证最后一个分组与T的异或等于X 密码学导论--中国科学技术大学

总体结构 密码学导论--中国科学技术大学

密钥的长度：由加密算法确定 常数K1,K2的长度：分组长度n 常数K1,K2的计算：域GF(2n)中的运算 L=EK(0n) K1=L·x K2=L·x2=(L·x)·x 域的素多项式p(x)为： 64位分组：x64+x4+x3+x+1，即100…011011 128位分组：x128+x7+x2+x+1，即100…010000111 计算方法：将L左移一位，与p||0异或 密码学导论--中国科学技术大学

第四节 数字签名的实现 密码学导论--中国科学技术大学

数字签名的基本形式 对消息签名的两种方法 两类数字签名 数字签名的方法： 对消息整体签名，消息整体经过密码变换得到签名； 对消息摘要签名，附在被签消息之后，或嵌在某一特定位置上作一段签名图样。 两类数字签名 确定性数字签名，明文与签名一一对应 概率性数字签名，同一明文有多个合法签名 数字签名的方法： 直接数字签名 仲裁数字签名 仲裁者的安全性必须高度重视！ 仲裁者被攻破，或仲裁者与其中某一方合谋，都将破坏公平性 密码学导论--中国科学技术大学

一、直接数字签名 直接数字签名仅涉及通信双方(信源、信宿) 签名与加密的顺序 弱点：有效性依赖于信源私有密钥的安全性 假定信宿知道信源的公开密钥，数字签名通过信源对整个报文，或对报文的摘要用私有密钥加密来实现。 签名与加密的顺序 先签名后加密： 消息内容和签名信息都被保护；仲裁前需解密 先加密后签名： 只保护消息内容；仲裁时只需提供密文 弱点：有效性依赖于信源私有密钥的安全性 可以假称私钥丢失 加时间戳？时间戳也可以是假的 密码学导论--中国科学技术大学

使用对称密码系统的数字签名 Alice和Bob间已共享密钥k Alice用k对消息进行加密，同时完成保密和签名 缺点： 密钥是Alice和Bob共享的，Bob可以确认文件来自Alice，即确认签名 缺点： Alice可以假称密钥丢失，否认签名 签名和加密绑定，能验证签名，就能阅读文件 Bob不能聘请秘书来替他验证签名 不适用于多人系统。 Alice需要与N个人分别共享密钥，并分别加密N次 密码学导论--中国科学技术大学

使用公钥密码系统的数字签名 在公钥密码系统中 优点 私钥：只有签名者本人拥有，并用它加密消息 公钥：开放给所有人。任何人都可以用公钥解密，获得明文，并同时确认消息来自签名人 无需仲裁者存在，每个人都可以自行验证签名 优点 签名是不可伪造的 签名是不可重用的 签名的文件是不可改变的 通过加密算法，签名与密文捆绑在一起 密码学导论--中国科学技术大学

缺点： 解决办法： 计算量大，速度慢 不验证签名就无法获得消息明文，不适用于特殊场合 专门的数字签名算法 用私钥加密较短的消息摘要 例如，地震警报是要广播给所有人的，但并不需要所有人都去验证警报的来源，只有少数专门部门才去验证。 需要将加密与签名分开。根据保密程度决定是否加密；验证签名时并不需要了解消息明文。 解决办法： 专门的数字签名算法 用私钥加密较短的消息摘要 利用单向散列函数 密码学导论--中国科学技术大学

二、仲裁数字签名 为解决直接数字签名中私钥安全带来的问题 仲裁者作用至关重要，通信各方必须对仲裁者适度的信任 可以用对称密码或公钥密码实现 签名方的签名报文首先送给仲裁者A，仲裁者对报文和签名进行测试以检验出处和内容，然后注上日期和仲裁说明后发给接收方。 仲裁者作用至关重要，通信各方必须对仲裁者适度的信任 可以用对称密码或公钥密码实现 仲裁者可以读取消息，也可以不读取 密码学导论--中国科学技术大学

仲裁签名的例子 Alice的签名由Trent进行验证，Bob不能直接读取 双方对Trent应高度信任 消息是公开的 Bob相信Trent只有验证签名正确后，才会向Bob发送消息 Alice和Bob都相信Trent不会泄露密钥，不会伪造签名 消息是公开的 可以在第一步中，将M移至加密函数内，保护明文消息 Alice Bob Trent (1) M || E(KTA, IDA || H(M)) (2) E(KTB, IDA || M || E(KTA, IDA || H(M)) || T) (1) (2) 密码学导论--中国科学技术大学

仲裁签名的例子 Trent处理的是加密后的数据，不能读取明文消息 如果仲裁者不公正怎么办？ Trent和Alice共同否认一个已签名的消息 Trent和Bob共同伪造发送者的签名 (1) IDA || E(KAB, M) || E(KTA, IDA || H(E(KAB, M))) (2) E(KTB, IDA || E(KAB, M) || T) || E(KTA, IDA || H(E(KAB, M))) || T) Alice Bob Trent (1) (2) 密码学导论--中国科学技术大学

仲裁签名的例子 通信前各方不共享任何信息，避免联合欺诈 时间戳由Trent添加并签名，其他人不能伪造 消息是保密的 Alice Bob (1) (2) (1) IDA || E(PRA, IDA || E(PUB, E(PRA, M))) (2) E(PRT, IDA || E(PUB, E(PRA, M)) || T) 密码学导论--中国科学技术大学

三、时间标记与抗抵赖 私钥签名本身不能抗抵赖 签名时，对消息摘要和时间戳共同进行签名 数字时间标记协议应有如下性质 签名者可以声称私钥在较早时期丢失 签名时，对消息摘要和时间戳共同进行签名 需要专门机构记录并发布公钥有效情况 但时间戳不能由签名者加入。为什么？ 窃取私钥的人，在签名时，可以附上一个较早的时间。而抵赖者可以声称发生了这样的事。 数字时间标记协议应有如下性质 数据本身（无论何种介质）必须有时间标记 改变文件的任何1个位都会引起文件的明显变化 只能用当前日期和时间来标记文件 密码学导论--中国科学技术大学

仲裁提供时间标记 由仲裁者Trent提供可信的时间标记服务 存在的问题： 文件M没有保密性，Trent的数据库的保密性也有潜在危险 Alice Trent (1) M (2) M || T (2) 保留副本 密码学导论--中国科学技术大学

改进的仲裁提供时间标记 利用散列函数和数字签名 散列函数的使用保证了文件M的保密性 Trent不再保存文件副本，无需维护数据库 Trent可以和Alice合谋 Trent可以和其他人合谋欺骗Alice么？ Alice Trent (1) H(M) (2) E(PRT, H(M) || T) 不可以，Alice可以用Trent的公钥解开签名查看时间的正确性 密码学导论--中国科学技术大学

链接协议 将当前时间标记同过去产生的时间标记链接起来 若有人对Alice的时间标记提问，则Alice可以和IDn-1和IDn+1联系出具证据 若要Alice和Trent欲合谋，只能在Alice的文件前后创建一个虚拟的文件链，该链长度足以回答任何人对时间标记链的提问 Alice Trent (1) Hn=H(M) (2) E(PRT, n||IDA||Hn ||Tn||IDn-1||Hn-1||Tn-1||Ln) (3) IDn+1 Ln=H(IDn-1, Hn-1,Tn-1, Ln-1) 密码学导论--中国科学技术大学

分布式协议 若Alice无法找到IDn-1或IDn+1，则链接协议无法进行 分布式协议： Alice使用Hn作为输入，用密码学意义上安全的伪随机序列发生器产生一串随机数，视为k个人的标记ID1,ID2,ID3,…, IDk Alice将Hn发送给这k个人 每个人都将时间附在Hn之后，签名并送回给Alice Alice收集所有签名作为时间标记 密码学意义上安全的伪随机序列发生器可以保证Alice无法预测到她将选择哪些人进行签名 密码学导论--中国科学技术大学

四、多重签名 有时需要多方共同对一个文件进行签名，验证者可以选择验证其中一部分或全部 各方分别进行签名，然后将所有的签名一起发布 签名长度是单个签名的N倍 签名各方顺序地、在前人的基础上进行签名操作。 若将加密就作为签名的话，长度不变；若签名是附加的一段数据，则长度也是单个签名的N倍 可以实现分级别的管理 需要专门的算法才能保证验证者可以任意验证签名 密码学导论--中国科学技术大学

五、加密与签名的顺序 先签名后加密 先加密后签名 对明文签名，再加密，再对密文签名 可以确保签名不被替换 不解密就不能验证签名 先加密后签名 签名者未必知道签的是什么——骗取签名、非法解密 密文的签名可能被替换 可以对密文进行签名验证 对明文签名，再加密，再对密文签名 对签名和加密使用两组密钥，可以避免很多威胁，但也使得管理更加复杂 某些算法对顺序有数学上的特殊要求 密码学导论--中国科学技术大学

六、利用签名过程的攻击 设想一个自动回复收据的系统 Eve窃取消息——进行重放攻击： Eve可以窃取Bob的签名 AliceBob: E(PUB,D(PRA,M)) Bob: M= E(PUA,D(PRB, E(PUB,E(PRA,M)) )) BobAlice: E(PUA,D(PRB,M)) 发送收据 Alice: M= E(PUB,D(PRA, E(PUA,D(PRB,M)) )) 确认 Eve窃取消息——进行重放攻击： EveBob: E(PUB,D(PRA,M))。Bob将用Eve的公钥验证签名，得到乱码M'=E(PUE,D(PRA,M))。此时如自动回复，则会根据Eve的公钥进行加密BobEve: E(PUE,D(PRB,M'))。Eve将得到M'，并进而算出M。 也可以将Bob的收据在某个时刻发给Alice，并期待Alice的回复 Eve可以窃取Bob的签名 密码学导论--中国科学技术大学

解决办法： 不要随意回复乱码，明码也要看明白再回复 永远不回复原文，而只回复原文的摘要值(hash) 在消息中嵌入发送者ID，而非由地址默认 Alice  E(PUB, IDA || D(PRA,M)) 在消息中嵌入ID是一个好习惯，即使这个ID可以从其他地方推测得到。需要时甚至考虑将发送者和接收者ID都嵌入。 嵌入时间戳（或随机数+数据库）也是个解决办法，但如何确定消息有效时限并不总是那么容易 密码学导论--中国科学技术大学

七、应用实例 对禁止核试验条约的监控 美国和前苏联互相允许将地震测试仪放入对方的领土内，对核试验行监控 将监测数据签名后发送 东道国需要确认测试仪发送的只是必要的监测数据 监督国需要确认监测数据没有被篡改 将监测数据签名后发送 东道国只能读取，但不能篡改 密码学导论--中国科学技术大学

第五节 数字签名协议 密码学导论--中国科学技术大学

一、基于RSA方法的数字签名 给定n=pq，p和q是大素数，ed mod φ(n)=1，公开密钥为(n,e)，秘密密钥为(p,q,d) 加密：c=me mod n 解密：m=cd mod n =med mod n =m 签名：s=md mod n 验证：m=se mod n =med mod n =m 密码学导论--中国科学技术大学

例：n=55=11×5，(n)=40，选d=11，则e=11，m=3 签名：s = 311 mod 55 =47 验证：m = s11 mod 55 = 4711 mod 55 = 3 例：n=65=13×5，(n)=48，选d=5，则e=29，m=3 签名：s = 35 mod 65 = 48 验证：m = 4829 mod 65 = 3 密码学导论--中国科学技术大学

设用户A:nA,eA,dA；B:nB,eB,dB；A→B：m 同时实现报文的保密和认证 设用户A:nA,eA,dA；B:nB,eB,dB；A→B：m c=E(PUB,D(PRA,m)) =(mdA mod nA)eB mod nB m=E(PUA,D(PRB,c)) =(cdB mod nB)eA mod nA =m 或 c=D(PRA,E(PUB,m)) =(meB mod nB)dA mod nA m=D(PRB,E(PUA,C)) =(CeA mod nA)dB mod nB =m 密码学导论--中国科学技术大学

特别注意： 若nA<nB，则必须 A：c = E(PUB, D(PRA,m)) B：m = E(PUA, D(PRB,c)) 若nB<nA，则必须 A：c = D(PRA, E(PUB,m)) B：m = D(PRB, E(PUA,c)) 密码学导论--中国科学技术大学

例：用户Alice(nA, eA)=(15, 3)，Bob(nB, eB)=(35, 5)， A发送m=11给B，要求既保密又认证地传送。 dA=3, dB=5 nA<nB，因此先签名，后加密；先解密，后验证 C=(113 mod 15)5 mod 35=16 m=(165 mod 35)3 mod 15=11 若先加密，后签名 C=(115 mod 35)3 mod 15=163 mod 15=1 m=(13 mod 15)5 mod 35=1 出错 密码学导论--中国科学技术大学

二、基于ElGamal方法的数字签名 共享大素数p,本原元α; 私钥x,公钥Y=αx mod p 加密： 0≤m≤ p-1，随机选取k，1<k<p-1 (c1,c2), c1=αk mod p, c2=mYBk mod p 解密： K=c1xB mod p, m=c2K-1 mod p 签名：随机选取k，1<k<p-1，且GCD(k,p-1)=1 (r,s), r=αk mod p, s满足：m = (xAr + ks) mod p-1 验证：检验αm mod p = YArrs mod p是否成立 αm mod p = α(xAr + ks) mod p = YArrs s=0会泄露私钥 密码学导论--中国科学技术大学

例：p=17,α=3, xA=2, xB=5, m=11, k=5, 签名并验证 签名：r = αk mod p = 35 mod 17 = 5, 11 = (2×5 + 5s) mod 16 = (10 + 5s) mod 16 5s mod 16 = 1, s = 13. 所以，签名为(5, 13)。 验证：αm mod p = 311 mod 17 = 16×9×3 mod 17 = 7 YArrs mod p = (32)5×513 mod 17 = 7 验证通过 密码学导论--中国科学技术大学

三、基于ECC的数字签名 共享GF(p)上的椭圆曲线E(a,b)，基点G及其阶n；私钥d；公钥Q=dG 签名： 任选k, 1<k<n 计算kG=(x1,y1), r=x1，若r=0则返回第一步重选k 计算k-1 mod n 计算s=k-1(m+dr) mod n 若s=0，则返回第一步重选k 则m的签名为(r,s) 密码学导论--中国科学技术大学

验证： 证明： 检查是否0<r,s<n 计算w=s-1 mod n 计算t1=mw mod n, t2=rw mod n 计算t1G+t2Q=(x0,y0), v=x0 mod n 若v=r，则签名被认可 证明： t1G+t2Q =mwG+rwQ =w(mG+rQ) =s-1(mG+drG) =s-1(m+dr)G =[k-1(m+dr)]-1(m+dr)G =kG 因此x坐标相等 密码学导论--中国科学技术大学

四、数字签名标准DSS 美国国家标准与技术协会(NIST)发布的FIPS 186，被称为数字签名标准(DSS) 1991年提出，1993年、1996年两次修改，2000年发布FIPS 186-2，2007年发布FIPS 186-3 DSS指标准, DSA指算法 使用了安全散列算法SHA 是ElGamal方案和Schnorr方案的改进 典型签名长度320 bits，安全强度512-1024 bits 安全性依靠离散对数求解难题 密码学导论--中国科学技术大学

DSS签名与RSA签名的比较 PUG为一组用户共有的参数，称为全局公钥 k是随机数，对每次签名是唯一的 密码学导论--中国科学技术大学

DSA密钥产生 全局公开密钥 (p,q,g): 用户密钥 选择N比特的素数q（典型值N=160） 选择大素数 2L-1 ≤ p ≤ 2L q是p-1的素因子 选择g = h(p-1)/q 其中1<h<p-1， h(p-1)/q (mod p) ≠ 1 即g是q模p的阶 用户密钥 选择私钥x<q 计算公钥y = gx (mod p) 密码学导论--中国科学技术大学

DSA签名及验证 r=f2(k,p,q,g) =(gk mod p) mod q s=f1(H(M),k,x,r,q) =k-1(H(M)+xr) mod q w=f3(s',q) =(s')-1 mod q v=f4(y,q,g,h(M'),w,r') =((g(H(M')w)mod qyr'w mod q) mod p) mod q 密码学导论--中国科学技术大学

证明：s'=s, M'=M, r'=r r=f2(k,p,q,g)=(gk mod p) mod q s=f1(H(M),k,x,r,q)=k-1(H(M)+xr) mod q w=f3(s',q)=(s')-1 mod q v=f4(y,q,g,h(M'),w,r')=((g(H(M')w)mod q yr'w mod q) mod p) mod q 证明：s'=s, M'=M, r'=r w=(s)-1 mod q=(k-1(H(M)+xr))-1 mod q ∴wk-1(H(M)+xr)=1 mod q w(H(M)+xr)=k mod q ∴v=((g(H(M)w)mod q yrw mod q) mod p) mod q =((g(H(M)w)mod q gxrw mod q) mod p) mod q =((g(H(M)+xr)w mod q) mod p) mod q =(gk mod p) mod q =r 密码学导论--中国科学技术大学

如果s=0，则必须重新选择k进行计算 如果k泄露，则私钥必须重选 s=k-1(H(M)+xr)=0 mod q x=-H(M)/r，会泄露私钥 如果k泄露，则私钥必须重选 s=k-1(H(M)+xr) mod q x=(sk-H(M))/r 密码学导论--中国科学技术大学

第六节 身份认证 密码学导论--中国科学技术大学

身份认证的实现方法： 口令（弱认证） 挑战－响应身份认证（强认证） 零知识的身份认证 密码学导论--中国科学技术大学

一、口令(弱认证) 口令：用户和系统共享的秘密 必须防护的威胁包括： 传统的口令方案因而归类为单向认证 口令重放、口令泄漏（系统外）和搭线窃听（系统内） 口令蛮力搜索 口令猜测 字典攻击 密码学导论--中国科学技术大学

固定口令方案 存储的口令文件：明文存储，读写保护 加密的口令文件：存储口令的单向函数值 口令规则：口令的长度、字符集等等 口令时效 放慢口令映射：迭代运算，不影响正常使用下增加试探口令的攻击时间 口令加盐：降低字典攻击的效率，防止口令重复 口令的散列值和盐值均记录在文件中 通行短语 密码学导论--中国科学技术大学

带盐的口令加密存储方案 口令表 口令A 用户A h() = Y N 接收 拒绝 … A 盐值 h(口令A) 基于口令的密码PBE：将h(口令)视为密钥加密密钥（KEK），用于加密会话密钥，将密文存储在表中，丢弃h(口令) 。解密时重建h(口令)，解密获得会话密钥。 密码学导论--中国科学技术大学

PIN和通行密钥 个人识别码PIN 两阶段认证和通行密钥 属于固定口令 通常很短（例如4～8位十进制数） 为防止穷举，一般辅助以程序限制。例如只准连续三次错误 两阶段认证和通行密钥 用户很难记住好的密钥。为此，有两种方案： 方案一：用PIN向标记验证用户，而标记包含向系统认证的其他独立信息 方案二：使用单向杂凑函数将口令映射为密码意义上的密钥，即通行密钥 注意：此时口令应当足够复杂，以挫败口令穷举攻击 密码学导论--中国科学技术大学

一次口令 每个口令只用一次，以防止重放攻击 一次口令的共享列表 顺序更新一次口令 基于单向函数的一次口令序列 共享口令序列或口令集 只共享一个口令，每次通信更新口令 基于单向函数的一次口令序列 Lamport一次口令方案：wi=H(wi-1)=Hi-1(w1) 密码学导论--中国科学技术大学

二、挑战－响应身份认证(强认证) 主要思想：声称者通过向验证者展示与该实体相关联的秘密知识来“证明”他的身份，但在协议中并没有展示秘密本身 通过对时变挑战做出响应来完成 时变参数：临时交互号nonce 随机数：提供唯一性、及时性，不可预测性；生成麻烦 序列号（或版本号或计数值）：提供唯一性；需要记忆 时间戳：提供唯一性、及时性，及实现有时间限制的访问特权以及检测强迫延时；时间需要“松散的同步” 密码学导论--中国科学技术大学

基于对称密码的挑战－响应 单向认证： A→B: E(K,tA) 或 A←B: rB A→B: E(K,rB) 相互认证： A→B: E(K,rA||rB) A←B: E(K,rA) 密码学导论--中国科学技术大学

基于公钥密码的挑战－响应 单向认证 B→A: H(r), E(PUB,r) H是散列函数 A→B: r 相互认证 A→B: E(PUB,rA) A←B: E(PUA,rA||rB) A→B: E(PUB,rB) 密码学导论--中国科学技术大学

基于数字签名的挑战－响应 单向认证 相互认证 A→B: CA,tA,SA(tA) CA是公钥证书，SA是数字签名 或 B→A: rB A→B: CA,rA,SA(rA||rB)　rA是为防止选择明文攻击 相互认证 A←B: rB A→B: CA, rA, SA(rA||rB) A←B: CB, rA, SA(rB||rA) 密码学导论--中国科学技术大学

手持通行码生成器 手持设备，象个计算器 生成器中存储有密钥 使用过程： 必须给存储在系统中的用户密码提供保密性 系统给用户一个挑战 用户将挑战输入生成器 生成器根据密钥和挑战计算通行码，并显示 用户将通行码输入系统 系统根据存储的用户密码也计算一个通行码 两个通行码若一致，则系统放行用户 必须给存储在系统中的用户密码提供保密性 密码学导论--中国科学技术大学

可信中继参与的挑战－响应 1、相互认证 (1) 基于对称加密 Needham-Schroeder协议： A→KDC: IDA || IDB || N1 KDC→A: E[Ka, Ks || IDB || N1 || E[Kb, Ks || IDA]] A→B: E(Kb, Ks || IDA) B→A: E(Ks, N2) A→B: E(Ks, f(N2)) 假定攻击者已知一个旧会 话密钥，它可以从第③步 开始假冒A并重放 Denning方法，Neuman方法 密码学导论--中国科学技术大学

Denning方法 A→KDC: IDA || IDB KDC→A: E[Ka, Ks || IDB ||T|| E[Kb, Ks||IDA||T]] A→B: E[Kb, Ks ||IDA ||T] B→A: E[Ks, N1] A→B: E[Ks, f(N1)] A和B通过下式来验证及时性： |Clock – T| < Δt1 + Δt2 Δt1：KDC与本地的时钟差 Δt2：网络延时 问题：过于依赖时钟同步 密码学导论--中国科学技术大学

Neuman方法 A→B: IDA||NA B→KDC: IDB||NB||E[Kb,IDA||NA||Tb] KDC→A: E[Ka,IDB||NA||Ks||Tb]||E[Kb,IDA||Ks||Tb]||NB A→B: E[Kb,IDA||Ks||Tb]||E[Ks,NB] 在Ks有效时限内，A与B建立新的会话： A→B: E[Kb,IDA||Ks||Tb]||N'a B→A: N'b||E[Ks,N'a] A→B: E[Ks,N'b] 密码学导论--中国科学技术大学

(2) 基于公钥密码 使用认证服务器来提供可信的公钥 Denning方法 A→AS: IDA || IDB AS→A: E(PRas,IDA||PUa||T) || E(PRas,IDB||PUb||T) A→B: E(PRas,IDA‖PUa||T) || E(PRas,IDB||PUb||T) || E(PUb,E(PRa,Ks||T)) 会话密钥由A选择，与AS无关 使用时间戳来防止重放攻击 需要时钟同步 密码学导论--中国科学技术大学

Woo-Lam方法 A→AS: IDA||IDB AS→A: E(PRas,IDB||PUb) A→B: E(PUb,Na||IDA) B→AS: IDA||IDB||E(PUas,Na) AS→B: E(PRas,IDA||PUa)||E(PUb,E(PRas,Na||Ks||IDB)) B→A: E(PUa,E(PRas,Na||Ks||IDB)||Nb) A→B: E(Ks,Nb) 修改：抗第5步时可能的交织攻击 AS→B: E(PRas,IDA||PUa)||E(PUb,E(PRas,Na||Ks||IDA||IDB)) B→A: E(PUa,E(PRas,Na||Ks||IDA||IDB)||Nb) IDA的添加将Na与IDA绑定在一起，说明Na是IDA的 密码学导论--中国科学技术大学

2、单向认证 基于对称密码 基于公钥密码 A→KDC: IDA||IDB||N1 KDC→A: E[Ka, Ks||IDB||N1 || E[Kb, Ks||IDA]] A→B: E[Kb, Ks||IDA] || E[Ks,M] 不能防止重放攻击 基于公钥密码 若关心保密性：A→B: E(PUb,Ks) || E[Ks,M] 若关心真实性：A→B: M||E(PRa,H(M))，或附加证书 M||E(PRa,H(M))||E(PRas,T||IDA||PUa) 为避免他人替换签名：A→B: E(PUb,M||E(PRa,H(M))) 密码学导论--中国科学技术大学

四、零知识的身份认证 零知识（ZK）协议：声称者在不泄漏他所掌握的秘密的情况下，向验证者证明他是否拥有该秘密 与公钥技术相比， 即证明一个断言的真实性。除了它的真实性之外，不泄漏任何关于断言本身的信息 与公钥技术相比， 不降低安全性 许多ZK避免加密，提供政治上的优点（不受出口限制） 计算开销通常更高 同样依赖于未经证明的难题 往往是近似的，而非真正的零知识在实际中应用 因为效率的参数选择或其他技术因素 密码学导论--中国科学技术大学

零知识证明≠挑战响应认证 例：“芝麻开门”的咒语——零知识证明 Alice可以用PRA解密Bob用PUA加密的随机数N来证明自己 这是挑战响应认证，但不是零知识证明 PUA(N)和N之间，蕴含了关于私钥PRA的信息，虽然利用这个信息恢复PRA在数学上是个难题，但信息仍是泄露了 例：“芝麻开门”的咒语——零知识证明 洞穴中的摄影机：无法区分真假记录 ，不能向第三方证明 A B C D 密码学导论--中国科学技术大学

Hamiltonian cycle 通过图中每个顶点一次的回路，称为汉密尔顿回路。 Alice欲向Bob证明，她知道图G的一个汉密尔顿回路 Alice制作图G的同构图H（G和H仅仅是顶点的名字不同） Alice向Bob出示H的承诺H' 承诺，不出示H的情况下声称是H，并能在必要时证明它 Bob要求Alice： 并证明H与G同构 或者，出示H的一条汉密尔顿回路 Alice： 揭示H（由H'恢复H），并证明H与G同构 揭示H’中汉密尔顿回路所在的边 以上过程反复执行n次 密码学导论--中国科学技术大学

原图 承诺的同构图 揭示的同构图 揭示的回路 密码学导论--中国科学技术大学

Fiat-Shamir身份认证协议(基本版本) Alice向Bob证明拥有知识s 一次设置 可信中心T选择素数p和q，公布n=pq 每个A选择与n互素的秘密s，计算v=s2 mod n，将v向T注册为自己的公钥 有限域的二次方根运算是个数学难题 协议执行t轮 A选择随机数r，发送x=r2 mod n给B（证据） B随机选择比特e=0或1，发送e给A（挑战） A计算y=r (e=0)，或y=rs mod n (e=1)，发送y给B（响应） 若y=0，B拒绝证明；否则，验证y2=xve mod n接受证明 密码学导论--中国科学技术大学

解释： 挑战e=1是验证他关于s的知识，挑战e=0是防止欺骗 知道s的声称者A可以回答每个问题，其他人至多只能回答两个问题中的一个 若假冒A的敌手任选r，取x=r2 mod n来试图进行欺骗，则它能“正确”地回答挑战e=0 (y=r)；但不能回答挑战 e=1 若假冒A的敌手任选r，设x=r2/v mod n来试图进行欺骗，则它能“正确”地回答挑战e=1 (y=r)；但不能回答挑战e=0 知道s的声称者A可以回答每个问题，其他人至多只能回答两个问题中的一个 执行1次协议被欺骗的概率为1/2 执行t次协议被欺骗的概率为2-t 密码学导论--中国科学技术大学

A泄漏的秘密信息： 回答e=0时，A响应了x=r2, y=r，没有泄露s的信息 回答e=1时，A响应了x=r2, y=rs，也没有提供s的任何信息 但该协议还是泄露了1比特信息：当协议执行t次后，B接收A的证明，则提供了v的确是模n的二次剩余的证据 密码学导论--中国科学技术大学

非交互式零知识证明 协议： 特点：用单向散列函数的不可预测性代替交互协议中的随机提问 Alice用n个随机数产生难题的n个同构新问题，并公开 若第i位为0，则证明第i个问题与原难题同构 若第i位为1，则公布第i个问题的解法 任何感兴趣的人可以自行验证散列值和第2步的结果 特点：用单向散列函数的不可预测性代替交互协议中的随机提问 n至少128以上，保证Alice不能尝试获得特定提问 密码学导论--中国科学技术大学

五、对身份认证协议的攻击 假冒攻击 重放攻击 反射攻击： 应对策略 从正在执行的协议将信息发送回该协议的发起者 用挑战－响应技术 用nonce 在响应中嵌入目标身份 反射攻击： 从正在执行的协议将信息发送回该协议的发起者 在挑战－响应中嵌入目标实体的标识符； 用每个不同形式的消息构造协议（避免消息的对称性） 单向密钥的使用 密码学导论--中国科学技术大学

强迫延时攻击： 选择文本攻击： 截取消息，并延迟一段时间后重新将消息放入协议，使协议继续 应对策略 随机数与短响应超时结合使用 时戳加上适当的附加技术 选择文本攻击： 有策略地选择挑战以尝试提取声称者的长期密钥信息 用零知识技术 在每个挑战－响应中嵌入自选择随机数 密码学导论--中国科学技术大学

交织攻击： 从一个或多个以前的或同时正在执行的协议得来的信息进行有选择的组合，从而假冒或进行其他欺骗 例： 应对策略 国际象棋大师问题 黑手党骗局 应对策略 从协议运行链接所有消息（如使用链接的临时值） 法拉第罩——阻止通信和走动 精确时钟——限制响应时间 房间A 房间B 收款1元 付款1万元 密码学导论--中国科学技术大学

身份真实性的维持 身份认证后，敌手立即“切进”通信线路 应对措施有： 周期性地进行重认证 将身份认证过程连接到正在进行的完整性服务 身份认证应与密钥建立机制整合 密码学导论--中国科学技术大学

第七节 认证应用实例 密码学导论--中国科学技术大学

一、认证加密 同时考虑认证与加密两种安全机制 先Hash再加密(HE) 先认证再加密(AE) 先加密再认证(EA) E(K, M||H(M)) 先认证再加密(AE) E(K2, M||MAC(K1,M)) 先加密再认证(EA) MAC(K1,E(K2,M)) 独立加密和认证(E+A) E(K2,M) || MAC(K1,M) 存在安全缺陷，不恰当的使用会导致安全漏洞 例如WEP协议使用HE方案，密钥固定且初始向量仅为24位 密码学导论--中国科学技术大学

分组密码链-消息认证码模式CCM NIST SP 800-38C，E+A方案的改进 用于IEEE 802.11 WiFi无线局域网安全 B0 B1 B2 Br • • • 格式函数 CMAC K Tag Ctr0 MSB(Tlen) AES CTR-AES Ctr1, Ctr2, …, Ctrm 密文C2 密文C1 认证部分 加密部分 密码学导论--中国科学技术大学

Galois/计数器模式GCM NIST SP 800-38D EA方案的改进 并行化设计，高吞吐率，适于高速网络 认证部分主要计算是GF(2128)上的乘法，便于硬件实现 密码学导论--中国科学技术大学

二、密钥封装 NIST SP 800-38F 新的分组密码工作模式：密钥封装模式 用途：通过事先共享的对称密钥（密钥加密密钥KEK）交换新的对称密钥，并认证完整性 鲁棒的加密模式，输出的每一位都无规律地受到输入每一位的值的影响 使用AES或3DES作为底层加密算法 密码学导论--中国科学技术大学

初始化A=ICV=A6A6A6A6A6A6A6A6; R()=明文密钥数据分组 执行6n个阶段，t=1,2,…,6n 明文密钥数据以64位进行分组 初始化A=ICV=A6A6A6A6A6A6A6A6; R()=明文密钥数据分组 执行6n个阶段，t=1,2,…,6n 密文C={A,R(1),R(2),…,R(n)} 若解密得到的A≠ICV，认证失败，拒绝新密钥 加密 K MSB64 LSB64 t A R(1) R(2) R(n) … || 密码学导论--中国科学技术大学

三、基于认证算法的PRNG 基于Hash函数的PRNG 基于MAC的PRNG data=V种子 repeat Wi=H(data) data=(data+1)mod 2len 基于MAC的PRNG SP 800-90：Wi=MAC(K,Wi-1) IEEE 802.11i：Wi=MAC(K,V||i) TLS/WTLS：A(i)=MAC(K,A(i-1)); Wi=MAC(K,A(i)||V) 密码学导论--中国科学技术大学

四、物联网上访问控制的例子 在每个设备上存储合法用户的密钥是不安全的 在每个设备上存储合法用户的密钥的摘要，可行，但对设备的计算能力要求较高 Alice Bob Carol 在每个设备上存储合法用户的密钥是不安全的 在每个设备上存储合法用户的密钥的摘要，可行，但对设备的计算能力要求较高 用户存储所有可访问设备的密钥是繁琐的 密码学导论--中国科学技术大学

利用散列函数的方案 设备上仅存储自己的访问密钥 合法用户利用智能设备（例如手机），与自己的密钥，计算得到设备的访问密钥 用户密钥 Bob Hash256 Chop128 (a+bX) 用户密钥 设备密钥Y X Bob Carol a+bXbob=Y a+bXcarol=Y 计算a,b，绑定在设备上 密码学导论--中国科学技术大学

五、Kerberos 开放的分布式网络中 服务器可以提供服务，并鉴别服务请求的种类 工作站无法判断终端用户及其所请求的服务是否合法 存在威胁：非授权用户可能获得未授权服务或数据 伪装身份操作工作站 改变工作站网络地址，从该机发起伪造的请求 监听或重放攻击，以获得或破坏服务 密码学导论--中国科学技术大学

服务与数据的保护 单机无网络： 集中式分时系统： 登录认证 分时操作系统 通过登录过程来认证用户 基于用户身份的操作控制 终端向主机认证 密码学导论--中国科学技术大学

分布式体系： 方案一：客户端认证用户身份，服务器提供基于用户标识的安全策略 方案二：客户端向服务器提供身份认证，相信客户端提供的用户身份 小型、封闭网络 方案二：客户端向服务器提供身份认证，相信客户端提供的用户身份 方案三：用户和服务器互相提供身份认证 互联网络，Kerberos支持 密码学导论--中国科学技术大学

Kerberos 最早且被最广泛使用的可信第三方密钥分配系统之一 作为MIT的Athena计划的认证服务而开发 允许用户访问分布式网络服务 无需信任所有工作站 所有结点信任一个集中式授权服务器 密码学导论--中国科学技术大学

1988年Kerberos第一份报告中提出的需求分析： 安全性： 高可靠性：使用分布式服务器结构，可以备份其它系统 透明性：用户只需输入口令 可伸缩性：支持大量客户端，需要模块化、分布式的体系结构 目前常用的有两个版本：4 & 5 密码学导论--中国科学技术大学

Kerberos版本4 Kerberos的使用模式 方法：使用集中式的认证服务器 主体是Client/Server 服务器：包括提供识别服务的Kerberos服务器和提供应用的各类服务器 客户机：用户 用户和服务器首先都到Kerberos服务器注册，与Kerberos服务器实现秘密共享，识别过程中Kerberos服务器为通信双方建立一个通信密钥。 方法：使用集中式的认证服务器 (Authentication Server, AS),为用户和应用服务器提供识别服务。AS与用户共享口令，与其他服务器共享密钥，在注册时以特别安全的方式分配给各方。 密码学导论--中国科学技术大学

一个简单的认证会话 各应用服务器在每次客户与的服务器交互中都进行认证？ 例如： C向AS发出使用V的请求 AS将C的认证信息发给V AS将V的认证信息发给C C与V相互认证 缺点： AS很忙 AS C V 密码学导论--中国科学技术大学

AS统一存储用户口令、权限，发放票据 缺点： 用户口令PC明文传送：不安全 为换得不同的通行票，用户口令要反复使用：很不安全 Ticket只能用一次，否则易遭重播攻击：很麻烦，用户需要经常的输入口令 (1)IDC||PC||IDV (2)Ticket (3)IDC || Ticket AS C V Ticket = E[KV,IDC || ADC || IDV] IDC：用户C的ID IDV：服务器V的ID ADC：用户C的网络地址 KV：服务器V与AS共享的密钥 PC：用户C的口令 密码学导论--中国科学技术大学

一个更安全的认证会话 引入票据授权服务器TGS(Ticket-Granting Server) AS中存储与用户和与TGS共享的密钥，负责识别用户身份，发放TGT(Ticket-Granting Ticket票据授权票据)，用户据此获得TGS的服务 TGS中存储与其它服务器共享的密钥，产生SGT(Service-Granting Ticket服务授权票据)，用户据此获得其他服务器的服务。 密码学导论--中国科学技术大学

C→TGS: IDC || Tickettgs||IDV TGS→C: TicketV C→V: IDC || TicketV AS TGS DB ① ② ③ ④ ⑤ 用户一次登录，获取TGT C→AS: IDC || IDtgs AS→C: E(KC, Tickettgs) C→TGS: IDC || Tickettgs||IDV TGS→C: TicketV C→V: IDC || TicketV TGT：Tickettgs=E[Ktgs, IDC||ADC||IDtgs||TS1||Lifetime1] SGT：TicketV =E[KV, IDC||ADC||IDV||TS2||Lifetime2] TS: 时间戳，Lifetime: 生命期 缺点： 票据的生命期如何确定？ 网络服务如何确定票据的使用者和所有者一致？ 用户如何确认服务器？ 每种服务类型进行一次，获取SGT 每次会话进行一次 密码学导论--中国科学技术大学

Kerberos4的认证会话协议 获取TGT，建立C与TGS的共享密钥 C→AS: IDC||IDtgs||TS1 AS→C: E[KC, KC,tgs||IDtgs||TS2||Lifetime2||Tickettgs] Tickettgs=E[Ktgs, KC,tgs||IDC||ADC||IDtgs||TS2||Lifetime2] 获取SGT，建立C与V的共享密钥 C→TGS:IDV||Tickettgs||AuthenticatorCT TGS→C:E[KC,tgs, KC,V||IDV||TS4||TicketV] AuthenticatorCT=E[KC,tgs, IDC||ADC||TS3] TicketV=E[KV,KC,V||IDC||ADC||IDV||TS4||Lifetime4] C与V相互认证 C→V: TicketV||AuthenticatorCV V→C: E[KC,V,TS5+1] AuthenticatorCV=E[KC,V, IDC||ADC||TS5] AS TGS DB ① ② ③ ④ ⑤ ⑥ 密码学导论--中国科学技术大学

Kerberos域 Kerberos环境包括： 这称为一个Kerberos域 Kerberos主体 一个Kerberos服务器 若干客户端 存放用户标识UID和用户口令的数据库 若干客户端 都在Kerberos服务器上注册 若干应用服务器 都在Kerberos服务器上注册，并共享密钥 这称为一个Kerberos域 Kerberos数据库必须物理上安全 Kerberos主体 Kerberos系统注册的服务或用户 主体名称包括三：服务或用户名称、实例名、域名 密码学导论--中国科学技术大学

多个域存在时，各域Kerberos服务器必须互相注册并信任 域不易扩充 AS TGS DB ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ Realm A Realm B 密码学导论--中国科学技术大学

Kerberos5 90年代中期提出，是Kerberos4的改进 RFC 1510 环境上的改进： 加密系统依赖性： 版本4：使用DES 版本5：用加密类型标记密文，可以使用任何加密技术 Internet协议依赖性： 版本4：限制为IP地址 版本5：用类型和长度标记网络地址 票据的生命期： 版本4：生命期8比特表示，每单位5分钟 版本5：包含精确的起始时间和终止时间 密码学导论--中国科学技术大学

消息字节顺序： 向前认证： 域间认证： 版本4：发送者用标记说明规定消息的字节顺序 版本5：消息结构按照抽象语法表示（ASN.1）和基本编码规则（BER）规定 向前认证： 版本4：票据专用，不能用于相关工作 版本5：提供该功能 域间认证： 版本4：N个域的两两交互需要N2个Kerberos服务器间关系 版本5：有较少的连接方法 密码学导论--中国科学技术大学

技术上的改进： 两次加密： PCBC加密： 会话密钥： 口令攻击： 给客户端的服务凭证票据经过了两次加密，不是必需的 DES的非标准PCBC链接模式，易受交换密文块攻击 会话密钥： 客户端多次使用同一个会话密钥加密认证信息，会增加攻击者破译的可能 口令攻击： 口令是不安全的。版本5的预认证机制使得口令攻击难一些。 密码学导论--中国科学技术大学

Kerberos5认证会话 新增元素： Realm：域标识 Options：客户端请求在返回的票据中设置标识位 Times：客户端请求在返回的票据中设置时间 from：请求票据的起始时间 till：请求票据的过期时间 rtime：请求till更新时间 Nonce：临时交互号 密码学导论--中国科学技术大学

过程： 密码学导论--中国科学技术大学

Kerberos5标志 密码学导论--中国科学技术大学

Kerberos的安全问题 Kerberos的安全性问题 使用Time Stamp防止重放攻击 使用口令做密钥 集中式管理，使用AS和TGS 需要时间同步，网络延迟不易控制 使用口令做密钥 口令密钥的强度不足够安全 集中式管理，使用AS和TGS 容易出危险 密码学导论--中国科学技术大学