信息安全专题讲座-08

第八章信息认证和散列函数（MessageAuthenticationandHashFunctions)1信息认证网络系统安全要考虑两个方面。一方面，用密码保护传送的信息使其不被破译；另一方面，就是防止对手对系统进行主动攻击，如伪造，篡改信息等。认证（authentication）则是防止主动攻击的重要技术，它对于开放的网络中的各种信息系统的安全性有重要作用。认证的主要目的有二：第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。保密和认证同时是信息系统安全的两个方面，但它们是两个不同属性的问题，认证不能自动提供保密性，而保密性也不能自然提供认证功能。一个纯认证系统的模型如下图所示：窜扰者信宿信源认证编码器认证译码器信道安全信道密钥源在这个系统中的发送者通过一个公开的无扰信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过篡改。系统中的密码分析者不仅要截收和破译信道中传送的密报，而且可伪造密文送给接收者进行欺诈，将其称为系统的窜扰者(tamper)更加合适。实际认证系统可能还要防止收方、发方之间的相互欺诈。上述标出的认证编码器和认证译码器可抽象为认证函数。一个安全的认证系统，首先要选好恰当的认证函数，然后在此基础上，给出合理的认证协议(AuthenticationProtocol)。2认证函数（AuthenticationFunctions)可用来做认证的函数分为三类：(1)信息加密函数(Messageencryption)用完整信息的密文作为对信息的认证。(2)信息认证码MAC(MessageAuthenticationCode)是对信源消息的一个编码函数。(3)散列函数(HashFunction)是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。对于（1），用信息加密函数作认证的方式，教材P239-242，给出明白的叙述。信息加密函数分二种，一种是常规的对称密钥加密函数，另一种是公开密钥的双密钥加密函数。下图的通信双方是，用户A为发信方，用户B为接收方。用户B接收到信息后，通过解密来判决信息是否来自A，信息是否是完整的，有无窜扰。信源信宿MEEk(M)DMA方B方kkDk(Ek(M))(a)常规加密：具有机密性，可认证KUb(B方的公钥)MEEKUb(M)DMA方B方DkRb(b)公钥加密：具有机密性MEEkRa(M)DMA方B方KRaKUa(c)公钥加密：认证和签名MEEkRa(M)EEKUb(EkRa(M))A方KRaKUbDEkRa(M)DMB方KRbKUa(d)公钥加密：机密性，可认证和签名对于（2），信息认证码(MAC)设S为通信中的发方A发送的所有可能的信源集合。为了达到防窜扰的目的，发方A和收方B设计一个编码法则。发方A根据这个法则对信源S进行编码，信源经编码后成为消息，M表示所有可能的消息集合。发方A通信时，发送的是消息。用简单的例子说明：设S={0,1},M={00,01,10,11},定义四个不同的编码法则e0,e1,e2,e3:00011011e001e101e201e301这样就构成一个认证码MAC。发方A和收方B在通信前先秘密约定使用的编码法则。例如，若决定采用e0，则以发送消息00代表信源0；发送消息10代表信源1，我们称消息00和10在e0之下是合法的。而消息01和11在e0之下不合法，收方将拒收这二个消息。信息的认证和保密是不同的两个方面，一个认证码可具有保密功能，也可没有保密功能。认证编码的基本方法是要在发送的消息中引入多余度，使通过信道传送的可能序列集Y大于消息集X。对于任何选定的编码规则(相应于某一特定密钥):发方从Y中选出用来代表消息的许用序列，即码字；收方根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是Y中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码(AuthenticationCode),使接收者受骗概率极小化。令x∈X为要发送的消息，k∈K为发方选定的密钥，y=A(x,k)∈Y是表示消息X的认证码字，Ak={y=A(x,k)|x∈X}为认证码。Ak是Y中的许用(合法)序列集，易见Y=Ak∪Ak。接收者知道认证编码A(.,.)和密钥k,故从收到的y,唯一确定出消息x。窜扰者虽然知道X,Y,y,A(.,.),但不知具体密码k,他的目的是想伪造出一个假码字y*，使y*∈Ak,以使接收者收到y*后可用密钥k解密，得到一个合法的消息x*。这样，窜扰者欺诈成功。消息认证消息认证是使意定的消息接收者能够检验收到的消息是否真实的方法。检验内容应包括：(1)证实报文的源和宿；(2)报文内容是否曾受到偶然的或有意的篡改；(3)报文的序号和时间栏。总之，消息认证使接收者能识别：消息的源，内容的真伪，时间性和意定的信宿。这种认证只在相应通信的双方之间进行，而不允许第三者进行上述认证。认证不一定是实时的。可用消息认证码MAC对消息做认证。.利用函数f和密钥k，对要发送的明文x或密文y变换成rbit的消息认证码f(k,x)(或f(k,y))，将其称为认证符附加在x(或y)之后发出，以x//As(或y//As)表示，其中“//”符号表示数字的链接。接收者收到发送的消息序列后，按发方同样的方法对接收的数据(或解密后)进行计算，应得到相应的rbit数据。两种实用的MAC算法(一)十进制移位加MAC算法Sievi于1980年向ISO提出一项消息认证法的建议[Davies等1984]，这种认证法称为十进制移位加算法(DecimalShiftandAddAlgorithm)，简记为DSA。它特别适用于金融支付中的数值消息交换业务。消息按十位十进制数字分段处理，不足十位时在右边以0补齐，下面举例说明。令x1=1583492637是要认证的第一组消息，令b1=5236179902和b2=4893524771为认证用的密钥。DSA算法是以b1和b2并行对x1进行运算。先算x1+b1,x1+b2(mod1010),而后根据b2的第一位数值4对x1+b2循环左移4位，记作R(4)(x1+b1)再与(x1+b1)相加得R(4)(x1+b1)+(x1+b1)P1(mod1010)类似地，右路在b1的第一位数值5控制下运算结果为R(5)(x1+b2)+(x1+b2)=Q1(mod1010)表：左路右路第b1=5236179902b2=4893224771一+x1=1583492637+x1=1583492637轮b1+x1=6819672539b2+x1=6477017408+R(4)(b1+x1)=2539681976+R(5)(b2+x1)=1740864770P1=9359354506Q1=8217882178第+x2=5283586900+x2=5283586900二P1+x2=4642941406Q1+x2=3501469078轮+R(8)(P1+x2)=4294140646+R(9)(Q1+x2)=7835014690P2=8937082052Q2=1336483768….….第P10=7869031447Q10=3408472104十P10+Q10=1277403551(mod1010)轮403551+1277认证符404828(mod1010)将第二组消息x2=528358586900分别与P1和Q1相加，其结果又分别以P1和Q1的第一位控制循环移位后进行相加得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。计算P10+Q10(mod1010),并将结果的后6位数与前4位数在(mod1010)下相加，得6位认证符！(二)采用DES的认证算法：有二种基于DES的认证算法，一种按CFB模式，一种按CBC模式运行。在CBC模式下，消息按64bit分组，不足时以0补齐，送入DES系统加密，但不输出密文，只取加密结果最左边的r位作为认证符。(64bit)x1,..xnAs(24bitor32bit)64比特寄存器DES选左r位+y1,y2,…,yn(64bit数组)yn利用CBC模式下DES的认证法r取大小可由通信双方约定。美国联邦电信建议采用24bit[见FTSC-1026],而美国金融系统采用32bit[ABA,1986]64bit寄存器DES选左边k位选左边r位As+yixi利用工作于CFB模式下DESk对于（3），散列函数(HashFunction)若对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按160比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。解决的办法：引入可公开的密码散列函数(Hashfunction)。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列函数h是这样使用的：消息：x任意长消息摘要：Z=h(x)160bits签名：y=sigk(Z)320bits(签名一个消息摘要)验证签名:(x,y),其中y=sigk(h(x))，使用公开的散列函数h，重构作Z'=h(x)。然后检验Verk(Z,y),来看Z=Z'。(一)无碰撞的散列函数用以认证的散列函数，能否减弱认证方案的安全性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。(a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y=sigk(h(x))。首先他计算Z=h(x)，并企图找到一个x'=x满足h(x')=h(x)。若他做到这一点，则(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到异与x的x'∈X使h(x)=h(x')。(b)伪造方式二：Oscar首先找到两个消息x=x',满足h(x)=h(x'),然后Oscar把x给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x',y)是一个有效的伪造。定义2(强无碰撞)散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。注：强无碰撞自然含弱无碰撞！(c)伪造方式三：在某种签名方案中可伪造一个随机消息摘要Z的签名。若h的逆函数h-1是易求的，可算出h-1(Z)=x,满足x=h(Z)，则(x,y)(其中y=sigk(h(x)))为合法签名。定义3(单向的)称散列函数h为单向的，是指计算h的逆函数h-1在计算上不可行。下面要证明“强无碰撞特性包含有单向性”。为此，先对散列函数h做一规范说明：首先h:XZ，这里设X,Z为有限集且|X|=2|Z|。这是一个合理的假设：若X中的元素编码长度为log2|X|的比特串，Z中的元素编码长度为log2|Z|的比特串。那么消息摘要Z=h(x)至少比源消息X短一个比特。定理：假设h:XZ为一个散列函数，这里|X|和|Z|是有限的且|X|=2|Z|。若h-1为h的逆函数，那么存在一个概率的LasVegas算法，它能找到h的一个碰撞的概率至少为1/2。证明：利用h的逆函数h-1来寻找h的碰撞的LasVegas概率算法：(1)随机选择x∈X(2)计算Z=h(x)(3)计算X1=h-1(Z)(4)若X1=X,那么X1和X在h下碰撞成功。否则，往复再来。来看成功的概率：首先定义X中元素关于h的等价，若x1,x∈X,有h(x)=h(x1),则称x1与x等价；记为x等价于x1。等价类[x]={x1∈X|x等价于x1}因为，每一个等价类[x]由Z的元素的原象组成，所以等价类的数目至多为|Z|。记等价类的集合为C。现假设x是第一步选择的X中的元素。对这个x,在第(3)步中将返回|[x]|个可能的x1值，而|[x]-1|个x1值将与x不同。于是在[x]类内成功的概率为(|[x]-1)/|[x]|。对于前述算法成功的概率是通过