网络与信息安全-密码学基础(3)

密码学基础（3）胡建斌北京大学网络与信息安全研究室E-mail:[e-mail]~hjbin目录1.消息鉴别与散列函数2.散列算法3.数字签名消息鉴别与散列函数MessageAuthenticationandHasFunctions网络通信的攻击威胁泄露：把消息内容发布给任何人或没有合法密钥的进程流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等伪装：从一个假冒信息源向网络中插入消息内容篡改：消息内容被插入、删除、变换、修改顺序修改：插入、删除或重组消息序列时间修改：消息延迟或重放否认：接受者否认收到消息；发送者否认发送过消息鉴别和认证鉴别：authentication真伪性(1)Aprocessusedtoverifytheintegrityoftransmitteddata,especiallyamessage用来验证发送的数据,特别是一个信息的完整性的过程(2)Theactofestablishingtheidentityofuserswhentheystarttousethesystem在用户开始使用系统时对其身份进行的确认认证：Certification资格审查Incomputersecurity,thetechnicalevaluationmadeaspartofandinsupportoftheaccreditationprocess,thatestablishedtheextenttowhichaparticularcomputersystemornetworkdesignandimplementationmeetprespecifiedsecurityrequirements计算安全学用语,指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估鉴别的结构任何消息认证或数字签名机制可以看到两个层次：底层必须有某种函数产生一个认证标识：一个用于认证一个报文的值高层认证协议以底层函数为原语，使接收者完成报文的鉴别鉴别的目的信源识别：验证信息的发送者是真正的，而不是冒充的验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等鉴别模型鉴别系统的组成鉴别编码器和鉴别译码器可抽象为鉴别函数一个安全的鉴别系统，需满足（1）指定的接收者能够检验和证实消息的合法性、真实性和完整性（2）消息的发送者和接收者不能抵赖（3）除了合法的消息发送者，其它人不能伪造合法的消息鉴别函数分类消息加密：整个消息的密文作为认证标识消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识鉴别函数分类消息加密：整个消息的密文作为认证标识消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识消息加密对称加密－保密和鉴别AB:():()kkABkAEMBBDMM与共享密钥，查看是否为有意义的明文对称加密－保密和鉴别A提供保密－仅A和B共享k提供一定程度的鉴别－仅来自－传输中不会被更改－需要某种结构和冗余不提供签名－接收人可以伪造报文－发送人可以伪造报文明文M的自动确定M定义为有意义的明文序列，便于自动识别强制定义明文的某种结构，这种结构是易于识别但又不能复制且无需借助加密的可以在加密前对每个报文附加检错码，即所谓的帧检验序列号或检验和FCS内部差错控制和外部差错控制差错控制更难于构造公钥加密－保密性ABbKUb提供保密－仅B有KR能解密不提供鉴别－任何一方均可以使用加密报文而假称它是发自A的公钥加密－鉴别和签名ABaAa提供鉴别和签名－仅有KR可进行加密－传输中不会被更改－需要某种结构或冗余－任何一方均能使用KU验证签名公钥加密－保密、鉴别和签名ABabKR提供鉴别和签名KU可提供保密性消息鉴别码MAC消息鉴别码使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称MAC，或密码校验和（cryptographicchecksum）1、接收者可以确信消息M未被改变2、接收者可以确信消息来自所声称的发送者3、如果消息中包含顺序码（如HDLC,X.25,TCP），则接收者可以保证消息的正常顺序MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少消息鉴别ABkkMACC(M)kABMAB:MC(M)＝；为和共享的密钥，为明文提供鉴别－仅A和B共享密钥k消息鉴别与保密，鉴别与明文连接ABk2k1AB:E[MC(M)]12提供鉴别－仅A和B共享密钥k提供保密－仅A和B共享密钥k消息鉴别与保密，鉴别与密文连接ABk2k1k2AB:E[MC(E(M))]12提供鉴别－仅A和B共享密钥k提供保密－仅A和B共享密钥k消息鉴别VS常规加密保密性与真实性是两个不同的概念根本上,信息加密提供的是保密性而非真实性加密代价大(公钥算法代价更大)鉴别函数与保密函数的分离能提供功能上的灵活性某些信息只需要真实性,不需要保密性–广播的信息难以使用加密(信息量大)–网络管理信息等只需要真实性–政府/权威部门的公告散列函数HashFunction散列函数H(M):输入为任意长度的消息M;输出为一个固定长度的散列值，称为消息摘要(MessageDigest）H(M)是消息M的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致该散列值的变化H(M)又称为：哈希函数、数字指纹（Digitalfingerprint)、压缩（Compression)函数、数据鉴别码（Dataauthenticationcode）等散列函数基本用法(1)kAB:E[MH(M)]提供鉴别－加密保护H(M)提供保密－仅A和B共享密钥k散列函数基本用法(2)kAB:ME[H(M)]提供鉴别－加密保护H(M)散列函数基本用法(3)aKR提供鉴别和数字签名－加密保护H(M)－仅A能生成E[H(M)]散列函数基本用法(4)akKRAB:E[ME[H(M)]]提供鉴别和数字签名提供保密－仅A和B共享密钥k散列函数基本用法(5)AB:MH(MS)]]提供鉴别－仅A和B共享消息S散列函数基本用法(6)kAB:E[MH(MS)]]提供鉴别－仅A和B共享S提供保密－仅A和B共享密钥k消息鉴别码MACMKMAC函数域：任意长度的报文值域：所有可能的MAC和所有可能的密钥MAC一般为多对一函数函数域：任意长度的报文值域：所有可能的MAC和所有可能的密钥假设假设攻击者使用强行攻击，且已经获得报文的明文和相应的MAC,即222nnkMACnMACNNk长度为比特个可能的个报文，其中密钥的长度为个可能的密钥对MAC的强行攻击11(,)MMAC假设假设攻击者已经获得报文的明文和相应的MAC,即假设222nnkMACnMACNNk长度为比特个可能的个报文，其中密钥的长度为个可能的密钥对MAC的强行攻击11(,)MMACkn对MAC的强行攻击11111,()(),ikkMMACCMMACCMk(k-n)第1轮给定：fori=1to2:试探＝匹配数2无法确定真正的密钥k22222,()(),ikkMMACCMMACCM(k-n)(k-2n)第2轮给定：fori=1to2:试探＝匹配数2无法确定真正的密钥kkana若，则需要进行轮，比寻找等长度的解密密钥强度还高对MAC的强行攻击如果k≤n，则第一轮就可以产生一个唯一对应。仍然可以有多于一个key产生这一配对，这时攻击者只需对一个新的(message,MAC)进行相同的测试由此可见，强力攻击企图发现authenticationkey不小于甚至大于对同样长度的解密key的攻击对MAC的其它攻击设M=(X1||X2||…||Xm)是一个由64位Xi数据块连接而成定义(M)=X1X2...XmCK(M)=EK[(M)]其中为异或操作；E为ECB工作模式的DES算法则•Keylength=56bit•MAClength=64bit•强力攻击需要至少256次加密来决定K对MAC的其它攻击设M’=(Y1||Y2||…||Ym-1||Ym)其中Y1,Y2,…,Ym-1是替换X1,X2,…,Xm-1的任意值，而Ym=Y1Y2,…,Ym-1(M)则CK(M’)=EK[(M’)]=EK[Y1Y2,…,Ym-1Ym]=EK[Y1Y2,…,Ym-1(Y1Y2,…,Ym-1(M))]=EK[(M)]这时消息M’和MAC=CK(M)=EK[(M)]是一对可被接收者认证的消息用此方法，任何长度为64(m-1)位的消息可以被插入任意的欺骗性信息MAC应具备的性质如果一个攻击者得到M和CK(M)，则攻击者构造一个消息M’使得CK(M’)=CK(M)应具有计算复杂性意义下的不可行性CK(M)应均匀分布，即：随机选择消息M和M’，CK(M)=CK(M’)的概率是2-n，其中n是MAC的位数令M’为M的某些变换，即：M’=f(M)，（例如：f可以涉及M中一个或多个给定位的反转），在这种情况下，Pr[CK(M)=CK(M’)]=2-n基于DES的报文鉴别码基于DES的报文鉴别码算法来源FIPSpublication(FIPSPUB113)ANSIstandard(X9.17)使用CBC(CipherBlockChaining)方式，初始向量为IV=0基于DES的报文鉴别码算法来源FIPSpublication(FIPSPUB113)ANSIstandard(X9.17)使用CBC(CipherBlockChaining)方式，初始向量为IV=0基于DES的报文鉴别码将数据按64位分组，D1,D2,…,DN，必要时最后一个数据块用0向右填充运用DES算法E，密钥K数据认证码(DAC)的计算如下：O1=EK(D1)O2=EK(D2O1)O3=EK(D3O2)…ON=EK(DNON-1)FIPSPUB113目录1.消息鉴别与散列函数2.散列算法3.数字签名散列函数散列函数的定义散列函数：M:变长报文H(M):定长的散列值主要用于为文件、报文或其它分组数据产生指纹()hHM散列函数的要求H能用于任意大小的分组H能产生定长的输出对任何给定的x，H(x)要相对易于计算，使得硬件和软件实现成为实际可能对任何给定的码h，寻找x使得H(x)=h在计算上是不可行的，即单向性对任何给定的分组x，寻找不等于x的y，使得H(x)=H(y)在计算上是不可行的，即弱抗冲突性寻找对任何的(x,y)对使得H(x)=H(y)在计算上是不可行的，即强抗冲突性HashvsMACMAC需要对全部数据进行加MAC速度慢Hash是一种直接产生鉴别码的方法Hash函数通用结构由RonRivest于1990年提出MD4几乎被所有hash函数使用具体做法:–把原始消息M分成一些固定长度的块Yi–最后一块padding并使其包含消息M长度–设定初始值CV0–压缩函数f,CVi=f(CVi-1,Yi-1)–最后一个CVi为hash值MD5MD5描述Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest完成MD5(RFC1321)在最近数年之前,MD5是最主要的hash算法现行美国标准SHA-1以MD5的前身MD4为基础MD5描述输入：任意长度的报文输入分组长度：512bit输出：128bit报文MD5描述－step1附加长度值对报文进行填充，使其比特数与448模5