2010-2011年度北京大学研究生课程网络与信息安全第四讲密码学基础(三)陈钟教授北京大学信息科学技术学院软件研究所--信息安全研究室chen@infosec.pku.edu.cn2011/03/08 NISC-04 ©CZ@PKU回顾上次课的内容•对称密码的两个基本运算–代替和置换(Substitution & permutation)•对称密码分析的两个基本方法–系统分析法（统计分析法）–穷举法•对称密码的两个基本设计原则:–混乱和扩散•密码分析攻击的方式1讨论议题¾比DES更好的现代常规分组加密算法•Triple DES•IDEA•RC5、RC6•AES•……¾加密的位置部署：•链路方式和端到端的方式分组密码的操作模式•电子密码本ECB (electronic codebook mode)•密码分组链接CBC (cipher block chaining)•密码反馈CFB (cipher feedback)•输出反馈OFB (output feedback)•计数器模式CTR(Counter )¾美国NSB在[FIPS PUB 74和81]中规定¾ANSI 在[ANSI X3.106]中规定¾ISO和ISO/IEC在[ISO 9732 ISO/IEC 10116]中规定2电子密码本（ECB）¾Ci= EK(Pi) ⇔Pi= DK(Ci) ECB特点•简单和有效•可以并行实现•不能隐藏明文的模式信息–相同明文Ö相同密文–同样信息多次出现造成泄漏•对明文的主动攻击是可能的–信息块可被替换、重排、删除、重放•误差传递：密文块损坏Ö仅对应明文块损坏¾适合于传输短信息3密码分组链接CBC•Ci=EK(Ci-1⊕Pi) ⇔Pi=EK(Ci)⊕Ci-1CBC特点•没有已知的并行实现算法•能隐藏明文的模式信息–需要共同的初始化向量IV–相同明文Ö不同密文–初始化向量IV可以用来改变第一块•对明文的主动攻击是不容易的–信息块不容易被替换、重排、删除、重放–误差传递：密文块损坏Ö两明文块损坏•安全性好于ECB•适合于传输长度大于位的报文，还可以进行用户鉴别,是大多系统的标准如SSL、IPSec 4密码反馈CFB•CFB:分组密码Ö流密码Si为移位寄存器,j为流单元宽度加密: Ci=Pi⊕(EK(Si)的高j位)Si+1=(Si<T[n] = data[ n % len]; •for (n=0; n<=255; n++) // S[256]: 0,1,2,3,...,255•key->S[n] = n;•for (n=0; n<=255; n++) // 把K混淆和扩散到S中•{i=n;•j += key->S[i]+key->K[i];•temp = key->S[i];•key->S[i] = key->S[j];•key->S[j] = temp;•}•key->i = 0;•key->j = 0;•}14myrc4.c•void RC4(RC4_KEY *key, unsigned long len, const unsigned char *indata, unsigned char *outdata)•{•unsigned long l=0;•unsigned char i, j, k, temp;•i = key->i; j = key->j;•while (lS[i];•temp = key->S[i];•key->S[i] = key->S[j];•key->S[j] = temp;•temp = key->S[i] + key->S[j];•k = key->S[temp];•outdata[l] = indata[l] ^ k;•l++;•}•key->i = i; key->j = j;•}速度比较（Pentium II）•CipherKey LengthSpeed (Mbps)DES5693DES1683RC2variable0.9RC4variable4515攻击•802.11 WEP 攻击–FluhrerS. McGrew D. “Statistical Analysis of the Alleged RC4 Key Stream Generator”Proc. Fast Software Encryption 2000–Fluhrer,S. MantinI. Shamir A. “Weakness in the Key Scheduling Algorithm of RC4”Proc. Workshop in Selected Areas of Cryptography 2001–密钥产生途径有漏洞现代常规分组加密算法一种是对DES进行复合，强化它的抗攻击能力；另一种是开辟新的方法，既象DES那样加解密速度快，又具有抗差分攻击和其他方式攻击的能力。16现代常规分组加密算法•1. Triple DES•2. IDEA•3. RC5•4. RC6•5. AES•其他一些较实用的算法，如Blowfish，CAST，以及RC2。1 . TRIPLE DES•由于已经证明DES不能成为群，见K.W.Campbell and M.J.WienerProof that DES is not a groupIn Advances in Cryptology——Crpto’92.Springer-Verlag, New York,1993.于是多重DES，尤其是三重DES还在普遍使用。17双重DES (Double DES)•C = EK2(EK1(P)) ⇔P = DK1(DK2(C))双重DES的讨论•假设对于DES和所有56比特密钥，给定任意两个密钥K1和K2E，都能找到一个密钥K3,使得K2(EK1(P)) = EK3 (P) 。如果这个假设是事实，则DES的两重加密或者多重加密都将等价于用一个56比特密钥的一次加密。•从直观上看，上面的假设不可能为真。因为DES的加密事实上就是做一个从比特分组到一个分组的置换，而比特分组共有2可能的状态，因而可能的置换个数为2!>10347380000000000000000>101020•另一方面，DES56的每个密钥确定了一个置换，因而总的置换个数为2<1017。•直到1992年才有人证明了这个结果。18中间相遇(meet-in-the-middle)攻击C = EK2(EK1(P)) ⇒X = EK1(P) = DK2(C)•给定明文密文对(P,C)n对所有256个密钥,加密P,对结果排序o对所有256个密钥,解密C,对结果排序p逐个比较,找出K1,K2使得EK1(P) = DK2(C)对双重DES的中间相遇攻击的分析•已知，给定一个明文P，经二重DES加密有2个可能的密文。而二重DES所用密钥的长度应是112 bits，所以选择密钥有2112个可能性。于是对给定一个明文P加密成密文有2112/2=248种可能。给定两个明密文对,错误结果的概率降为248-=2-16。换句话说，对已知2个明文-密文对的中间相遇攻击成功的概率为1-2-16。•攻击用的代价{加密或解密所用运算次数} ≦2 ×256需要大量的存储器: 256 ×=1017字节19Triple-DES的四种模型•DES-EEE3：三个不同密钥，顺序使用三次加密算法•DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法•DES-EEE2：K1=K3，同上•DES-EDE2：K1=K3，同上Tuchman的双密钥的三重DES（Triple DES with Two Keys)•C=EK1(DK2(EK1(P))) ⇔P=DK1(EK2(DK1(C)))20对双密钥的三重DES的分析-i•该模式由IBM设计, 可与常规加密算法兼容•这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（The Key Manager Standards ANS X9.17和ISO8732).•交替使用(EK1和K2可以抵抗中间相遇攻击.如果C=EK2K1(EK1(P))) ,只需要256+2次加密•到目前为止，还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行穷尽搜索，那么由于空间太大为2112=5×1033，这实际上是不可行的。若用差分攻击的方法，相对于单一DES来说复杂性以指数形式增长，要超过1052。对双密钥的三重DES的分析-ii•目前还没有针对两个密钥三重DES的实用攻击方法。但对两个密钥三重DES的攻击有一些设想，以这些设想为基础将来可能设计出更成功的攻击技术。•MerkleR. and Hellman,M. “On the security of multiple encryption”. Communication of the ACM, July 1981•Oorschot,P and Wiener, M. “A Known-plaintext attack on two-key triple encryption”Proceedings, EUROCrypt’90,1990: published by Springer-Verlag21三密钥的三重DES（Triple DES with Three Keys)•C=EK3(DK2(EK1(P))) ⇔P=DK3(EK2(DK1(C)))三密钥的三重DES分析•密钥的有效长度为168位•与DES的兼容性可以通过令K3=K2或K1=K2得到•许多基于Internet的应用里用到：PGP和S/MIME22现代常规分组加密算法•1. Triple DES•2. IDEA•3. RC5•4. RC6•5. AES国际数据加密IDEA（International Data Encryption Algorithm)算法•1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节•设计目标从两个方面考虑–加密强度–易实现性•强化了抗差分分析的能力，PGP23IDEA算法特点•位分组,128位密钥•运算: XOR ⊕,模216（65536）加+,模(216+1)（65537）•乘•三种运算均不满足分配律与结合律•有大量弱密钥•难以直接扩展到128位块IDEA设计思想•得到confusion的途径–按位异或–以216(65536)为模的加法–以216+1(65537)为模的乘法–互不满足分配律、结合律•得到diffusion的途径–乘加(MA)结构•实现上的考虑–软件和硬件实现上的考虑24IDEA加密算法IDEA每一轮25IDEA输出变换阶段IDEA的子密钥26•现代常规分组加密算法•1. Triple DES•2. IDEA•3. RC5•4. RC6•5. AESRC5•作者为Ron Rivest1994设计、1995公开1. 适用于软件或者硬件实现2. 运算速度快3. 能适应于不同字长的程序（一个字的bit数是RC5的一个参数；）4.加密的轮数可变（轮数是RC5的第二个参数）5.密钥长度是可变的（密钥长度是RC5的第三个参数）6. 对内存要求低7. 依赖于数据的循环移位（增强抗攻击能力）27RC5参数•三个参数–参数w：表示字长，RC5加密两字长分组，可用值为16、32、–参数r：表示轮数，可用值0,1,…,255–参数b：表示密钥K的字节数，可用值0,1,…,255•RC5版本：RC5-w/r/b•算法作者建议标定版本为RC5-32/12/16RC5基本运算整个加密使用了下述3个基本运算和它们的逆运算：•模2w加法运算，表示为“+”；•逐比特异或运算，表示为“⊕”；•字的循环左移运算：字x循环左移y比特，表示为x<<>>y如（a0,a1,a2, …,an-1)<<<3=(a3,a4, …,an-1,a0,a1,a2)28密钥扩展•总计产生t=2r+2个子密钥，每个密钥的长度为一个字长（w bits)。密钥的初始化对于给定的参数r和w，开始初始化运算Pw=Odd((e-2)2w)Qw=Odd((Φ-1)2w)这里e =2.718281828459…(自然对数的底）Φ=1.618033988749…（黄金分割比率）并且Odd[x]表示最接近x且可左可右的奇整数。例：Odd[e]=3, Odd[Φ]=1用上述两个常数，按下述方式得到初始化的阵列S:S[0]=PwFor i=1 to t-1 doS[i]=S[i-1]+Qw其中的加法是模2w的加法运算。29密钥扩展1*.为了增强复杂性，可对阵列S,L做多次处理：i=j=x=y=0do 3×max(t,c) times:{S[i]=(S[i]+X+Y)<<<3；X=S[i]；i=(i+1)(mod t);L[j]=(L[j]+X+Y)<<<(X+Y)；Y=L[j]；j=(j+1)(mod c);}2*. Rivest声称，这个扩张函数具有单向性。加解密运算图30加密算法•加密：将明文分组为左右A,B；用变量Lei，Rei参与•运算程序为：LE0=A+S[0]RE0=B+S[1]for i=1 to r doLEi= ((LEi-1⊕REi-1)<<>>LDi) ⊕LDi);LDi-1=((LDi-S[2*i]>>>RDi-1) ⊕RDi-1);B=RD0-S[1];A=LD0-S[0].•RC5操作模式[RFC2040] Baldwin, R.,and Rivest,R. The RC5,RC5-CBC,RC5-CBC-Pad, and RC5-CTS algorithms. Oct.1996P96~9631现代常规分组加密算法•1. Triple DES•2. IDEA•3. RC5•4. RC6•5. AESRC6•被选为21世纪加密标准算法。RC6是RC5的进一步改进。像RC5那样，RC6实际上是利用数据的循环移位。•RC5自1995年公布以来，尽管至今为止还没有发现实际攻击的有效手段，然而一些理击的文章先后也分析出RC5的一些弱点。•RC6的加密程序：RC6-w/r/b32Design Philosophy•Leverage our experience with RC5: use data-dependent rotationsto achieve a high level of security.•Adapt RC5 to meet AES requirements •Take advantage of a new primitive for increased security and efficiency: 32x32 multiplication, which executes quickly on modern processors, to compute rotation amounts.Description of RC6•RC6-w/r/b––Word sizein bits: wparameters:•Key Expansion: –Number of Number of roundskey bytes: r( 32 )( lg(w) = 5 ): b ( 16, 24, or 32 )( 20 )–Produces array S[ 0 round keys.…2r+ 3 ] of w-bit •Encryption and Decryption:–Input/Output in 32-bit registers A,B,C,D33RC6的基本运算A + BAddition modulo 2wA -BSubtraction modulo 2wA ⊕BExclusive-Or5CA <<< BRotate Aleft by amount in Rlow-order lg(w) bits of BA >>> BRotate A right, similarly(A,B,C,D) = (B,C,D,A) Parallel assignmentA x BMultiplication modulo 2wRC6-w/r/b加密图，其中f(x)=x×(2x+1):ABCD+S[0]+S[1]⊕<<>> t ) ⊕uA = ( ( A -S[ 2i ] ) >>> u ) ⊕t}D = D -S[ 1 ] B = B -S[ 0 ]Key Expansion (Same as RC5’s)••Input: array L[ 0 …c-1 ] of input key words•Output: array S[ 0 Procedure:…43 ] of round key wordsS[ 0 ] = 0xB7E15163for i = 1 to43 doS[i] = S[i-1] + 0x9E3779B9A = B = i = j = 0fors = 1 to132 do{ A = S[ i ] = ( S[ i ] + A + B ) <<< 3B = L[ j ] = ( L[ j ] + A + B ) <<< ( A + B )i = ( i + 1 ) mod 44j = ( j + 1 ) mod c }36Security of Key Expansion•Key expansion is identical to that of RC5; no known weaknesses.•No known weak keys.•No known related-key attacks.•Round keys appear to be a “random”function of the supplied key.•Bonus: key expansion is quite “one-way”---difficult to infer supplied key from round keys.RC6小结•RC6 more than meets the requirements for the AES; it is–simple,–fast, and–secure.37Speed on Pentium PCAlgorithm Cycle/round # of round cycle/byteBlowfish 9 16 18RC5 12 16 23DES 18 16 45IDEA 50 8 503DES 18 48 108Speed on Pentium-IIAlgorithm key-length Speed(Mbps)DES 56 93DES 168 3RC2 vary 0.9RC4 vary 45 38现代常规分组加密算法•1. Triple DES•2. IDEA•3. RC5•4. RC6•5. AESAES背景-i•1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。•1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。39AES背景-ii•1998年8月12日，在首届AES会议上指定了15个候选算法。•1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。•2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。•2000年10月2日，NIST宣布了获胜者—Rijndael算法，2001年11月出版了最终标准FIPS PUB197。The 15 accepted submissions•CAST-256 Entrust(CA)•CryptonFuture Systems(KR)•E2 NTT(JP)•Frog Deutsche Telekon(DE)•Mars IBM(USA)•RC6 RSA(USA)•SAFER+ Cylink(USA)•TwofishCounterpane(USA)•DEAL Outerbridge, Knudsen(USA-DK)•DFC ENS-CNRS(FR)•HPC Schroeppel(USA)•LOKI97 Brown et al. (AU)•RijndaelDaemenand Rijmen(BE)•Serpent Anderson, Biham, Knudsen(UK-IL-DK)40Selection of the Finalists•安全问题：DEAL,Frog,HPC,LOKI97,Magenta•Very slow: DEAL,Frog,Magenta,SAFER+,(Serpent)•‘Copy’: Crypton•‘Losers’: CAST-256, DFC, E2 No problems, but not good enoughRijndael简介•不属于Feistel结构•加密、解密相似但不对称•支持128/32=Nb数据块大小•支持128/192/256(/32=Nk)密钥长度•有较好的数学理论作为基础•结构简单、速度快41AES参数42SP网络结构在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数S作用，然后再对所得结果用置换（或可逆线性变换）P作用。S和P分别被称为混乱层和扩散层，主要起混乱和扩散作用。AES算法结构-i•AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层，–线性混合层：确保多轮之上的高度扩散。–非线性层：具有最优最差-情形非线性性的S-盒的并行应用。–密钥加层：轮密钥简单地异或到中间状态上。43AES算法结构-iiAES-128加解密过程44AES算法描述•假设：State表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥•算法如下：–第一轮之前执行AddRoundKey(State,RoundKey)–Round(State,RoundKey) {ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); }–FinalRound(State,RoundKey) {ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey); }状态、密钥•状态/密钥的矩阵表示S00S01S02S03k00k01k02k03S04S05S06S07k10k11k12k13S08S09S10S11k20k21k22k23S12S13S14S15k30k31k32k3345字节代替(Substitute Bytes )变换•字节代替是一个非线性的字节代替，地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个16×16的矩阵。46example行移位(Shift Row)变换简单的置换47example列混合Mix Column变换•代替操作，将状态的列看作有限域GF（28）上的4维向量并被有限域GF（28）上的一个固定可逆方阵A乘48example49轮密钥加（Add Round Key)一个简单地按位异或的操作AES的密钥调度•轮密钥是通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取。基本原理如下：–所有轮密钥比特的总数等于分组长度乘轮数加1。（如128比特的分组长度和10轮迭代，共需要1408比特的密钥）。–将密码密钥扩展成一个扩展密钥。–轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始Nb个字组成，第二个轮密钥由接下来的Nb个字组成，如此继续下去。50AES的密钥扩展密钥扩展的伪代码51伪代码之二52G变换•Rotword执行一字节循环左移[b0,b1,b2,b3] [b1,b2,b3,b0]•Subword执行使用S-盒实行字节替换•前两步的结果XOR与轮常数Rcon[j]example53Rijndael安全性•没有发现弱密钥或补密钥•能有效抵抗目前已知的攻击算法–线性攻击–差分攻击先进对称分组加密算法的特点•可变的密钥长度: RC5•混合的运算IDEA•数据相关的圈数RC5•密钥相关的圈数CAST-128•密钥相关的S盒: Blowfish•冗长密钥调度算法：Blowfish•可变的F：CAST-128•可变长明文/密文块长度•可变圈数•每圈操作作用于全部数据54分组密码的一般设计原理•针对安全性的一般原则:–混乱–扩散•重要的设计原理:必须能抵抗现有的攻击方法•针对实现的原则–软件–硬件分组密码的整体结构•Feistel网络•SP网络55S盒的设计准则•S-盒首次出现在Lucifer算法中,因DES的使用而流行.•S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度.•提供了密码算法所必须的混乱作用.•如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题.•非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门P置换的设计准则•P置换的目的是提供雪崩效应（明文或密钥的一点小的变动都引起密文的较大变化）56轮函数的设计准则•安全性•速度•灵活性：能在多种平台实现轮函数的构造•加法、减法和异或•固定循环/移位•数据依赖循环•乘法57密钥扩展算法的设计•设计目标：子密钥的统计性和灵活性•实现简单•速度•不存在简单关系：( 给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)•种子密钥的所有比特对每个子密钥比特的影响大致相同•从一些子密钥比特获得其他的子密钥比特在计算上是难的•没有弱密钥用对称密码实现保密性易受攻击的位置58链路加密和端到端加密存储转发通信的加密覆盖范围59各种加密策略包含的内容End-to-End encryption•The source host encrypts the data.•The destination host decrypts it.•The packet head is in the clear.•The user data are secure.•The traffic pattern is insecure.•Require one key per user pair•A degree of user authentication.•在较高的网络层次上实现60Link encryption•Data exposed in sending node•Data exposed in intermediate node•The packet head almost in secure.•The traffic pattern is secure to some dgree.•Require one key per host to node and node to node•A degree of host authentication.•在较低的网络层次上实现Placement of encryption小结•两种方式共同使用有更高的安全性•The amount of traffic can be observed.•Traffic padding is useful.•源与目的地需有共享密钥61Reference•http://csrc.nist.gov/encryption/aes/•http://www.rsasecurity.com/rsalabs/rc6/•http://williamstallings.com/Crypto3e.html•William Stallings, Cryptography and network security: principles and practice, Second Edition.阅读与思考•Paper Reading Assignment–AES Attacking （download from website)62