第八章 信息认证和散列函数 （Message Authentication and Hash Functions)

Presentation on theme: "第八章 信息认证和散列函数 （Message Authentication and Hash Functions)"— Presentation transcript:

1 第八章 信息认证和散列函数 （Message Authentication and Hash Functions)
1 信息认证 网络系统安全要考虑两个方面。一方面，用密码保护传 送的信息使其不被破译；另一方面，就是防止对手对系统进 行主动攻击，如伪造，篡改信息等。认证（authentication） 则是防止主动攻击的重要技术，它对于开放的网络中的各种 信息系统的安全性有重要作用。认证的主要目的有二： 第一，验证信息的发送者是真正的，而不是冒充的，此 为信源识别； 第二，验证信息的完整性，在传送或存储过 程中未被篡改，重放或延迟等。

2 保密和认证同时是信息系统安全的两个方面，但它们
是两个不同属性的问题，认证不能自动提供保密性，而 保密性也不能自然提供认证功能。一个纯认证系统的模 型如下图所示： 窜扰者 信源 认证编码器 认证译码器 信宿 信道 安全信道 密钥源

3 在这个系统中的发送者通过一个公开的无扰信道将消息
送给接收者，接收者不仅想收到消息本身，而且还要验证消 息是否来自合法的发送者及消息是否经过篡改。系统中的密 码分析者不仅要截收和破译信道中传送的密报，而且可伪造 密文送给接收者进行欺诈，将其称为系统的窜扰者(tamper) 更加合适。实际认证系统可能还要防止收方、发方之间的相 互欺诈。 上述标出的认证编码器和认证译码器可抽象为认证函数。 一个安全的认证系统，首先要选好恰当的认证函数，然后在 此基础上，给出合理的认证协议(Authentication Protocol)。

4 2 认证函数 （Authentication Functions)
可用来做认证的函数分为三类： (1) 信息加密函数(Message encryption) 用完整信息的密文作为对信息的认证。 (2) 信息认证码MAC(Message Authentication Code) 是对信源消息的一个编码函数。 (3) 散列函数(Hash Function) 是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。

5 对于（1），用信息加密函数作认证的方式，教材
P ，给出明白的叙述。信息加密函数分二种，一种 是常规的对称密钥加密函数，另一种是公开密钥的双密 钥加密函数。下图的通信双方是，用户A为发信方，用户 B为接收方。用户B接收到信息后，通过解密来判决信息 是否来自A，信息是否是完整的，有无窜扰。 信源 信宿 M E Ek(M) D A方 B方 k Dk(Ek(M)) (a) 常规加密：具有机密性，可认证

6 M E D A方 B方 DkRb (b) 公钥加密：具有机密性 M E D A方 B方 KRa KUa (c) 公钥加密：认证和签名
EKUb(M) D A方 B方 DkRb KUb(B方的公钥) (b) 公钥加密：具有机密性 M E EkRa(M) D A方 B方 KRa KUa (c) 公钥加密：认证和签名

7 M E EkRa(M) EKUb(EkRa(M)) A方 KRa KUb D B方 KRb KUa (d) 公钥加密：机密性，可认证和签名

8 对于（2），信息认证码(MAC) 设S为通信中的发方A发送的所有可能的信源集合。 为了达到防窜扰的目的，发方A和收方B设计一个编码法 则。发方A根据这个法则对信源S进行编码，信源经编码 后成为消息，M表示所有可能的消息集合。发方A通信时， 发送的是消息。用简单的例子说明：设S={0,1}, M={00,01,10,11}, 定义四个不同的编码法则e0,e1,e2,e3: e e e e

9 这样就构成一个认证码MAC。发方A和收方B在通信前先
秘密约定使用的编码法则。例如，若决定采用e0，则以 发送消息00代表信源0；发送消息10代表信源1，我们称 消息00和10在e0之下是合法的。而消息01和11在e0之下不 合法，收方将拒收这二个消息。 信息的认证和保密是不同的两个方面，一个认证码 可具有保密功能，也可没有保密功能。 认证编码的基本方法是要在发送的消息中引入多余 度，使通过信道传送的可能序列集Y大于消息集X。对于 任何选定的编码规则(相应于某一特定密钥):发方从Y中选 出用来代表消息的许用序列，即码字；收方根据编码规 则唯一地确定出发方按此规则向他传来的消息。窜扰者 由于不知道密钥，因而所伪造的假码字多是Y中的禁用序

10 列，收方将以很高的概率将其检测出来而被拒绝。认证
系统设计者的任务是构造好的认证码(Authentication Code),使接收者受骗概率极小化。 令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*。这样，窜扰者欺诈成功。

11 消息认证 消息认证是使意定的消息接收者能够检验收到的消 息是否真实的方法。检验内容应包括： (1)证实报文的源和宿； (2)报文内容是否曾受到偶然的或有意的篡改； (3)报文的序号和时间栏。 总之，消息认证使接收者能识别： 消息的源，内容的真伪，时间性和意定的信宿。 这种认证只在相应通信的双方之间进行，而不允许 第三者进行上述认证。认证不一定是实时的。 可用消息认证码MAC对消息做认证。

12 利用函数f和密钥k，对要发送的明文x或密文y变换成r bit的消息认证码f(k,x)(或f(k,y))，将其称为认证符附加在x(或y)之后发出，以x//As(或y//As)表示，其中“//”符号表示数字的链接。接收者收到发送的消息序列后，按发方同样的方法对接收的数据(或解密后)进行计算，应得到相应的r bit数据。 两种实用的MAC算法 (一)十进制移位加MAC算法 Sievi于1980年向ISO提出一项消息认证法的建议[Davies等1984]，这种认证法称为十进制移位加算法(Decimal Shift and Add Algorithm)，简记为DSA。它特别适用于金融支付中的数值消息交换业务。 消息按十位十进制数字分段处理，不足十位时在右边以0补齐，下面举例说明。令x1= 是要认证的第一组消息，令b1= 和b2= 为认证用的密钥。DSA算法是以b1和b2并行对x1进行运算。 .

13 先算x1+b1, x1+b2(mod 1010), 而后根据b2的第一位数值4
对x1+b2循环左移4位，记作R(4)(x1+b1)再与(x1+b1)相加得 R(4)(x1+b1)+(x1+b1)P1(mod 1010) 类似地，右路在b1的第一位数值5控制下运算结果为 R(5)(x1+b2)+(x1+b2)=Q1(mod 1010) 表： 左路 右路 第 b1= b2= 一 x1= x1= 轮 b1+x1= b2+x1= +R(4)(b1+x1)= R(5)(b2+x1)= P1= Q1=

14 结果又分别以P1和Q1的第一位控制循环移位后进行相加 得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。
第 x2= x2= 二 P1+x2= Q1+x2= 轮 R(8)(P1+x2)= R(9)(Q1+x2)= P2= Q2= …. …. 第 P10= Q10= 十 P10+Q10= (mod 1010) 轮 认证符 (mod 1010) 将第二组消息x2= 分别与P1和 Q1相加，其 结果又分别以P1和Q1的第一位控制循环移位后进行相加 得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。 计算P10+Q10 (mod 1010),并将结果的后6位数与前4位数在

15 有二种基于DES的认证算法，一种按CFB模式，一种 按CBC模式运行。在CBC模式下，消息按64bit分组，不
(mod 1010)下相加，得6位认证符！ (二)采用DES的认证算法： 有二种基于DES的认证算法，一种按CFB模式，一种 按CBC模式运行。在CBC模式下，消息按64bit分组，不 足时以0补齐，送入DES系统加密，但不输出密文，只取 加密结果最左边的r位作为认证符。 64比特寄存器 y1,y2,…,yn(64bit数组) As (24bit or 32bit) (64bit) x1,..xn yn DES 选左r位 + 利用CBC模式下DES的认证法

16 r取大小可由通信双方约定。美国联邦电信建议采用
24bit[见FTSC-1026],而美国金融系统采用32bit [ABA,1986] 64bit寄存器 As k 选左边r位 DES 选左边k位 xi yi + 利用工作于CFB模式下DES

17 对于（3），散列函数(Hash Function)
若对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按160比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。 解决的办法：引入可公开的密码散列函数(Hash function)。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列函数h是这样使用的： 消息： x 任意长 消息摘要： Z=h(x) 160bits 签名： y=sigk(Z) bits (签名一个消息摘要)

18 验证签名:(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')。

19 (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在计算上不可行。

20 下面要证明“强无碰撞特性包含有单向性”。为此，先对散列函数h做一规范说明：
首先h:X Z，这里设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的逆函数，那么存在一个概率的Las Vegas算法，它能找到h的一个碰撞的概率至少为1/2。 证明：利用h的逆函数h-1来寻找h的碰撞的Las Vegas概率算法： (1) 随机选择x ∈ X (2)计算Z=h(x)

21 (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]|。 对于前述算法成功的概率是通过平均所有可能x的选 择来计算的：

22 P(成功)=(1/|X|) ∑((|[x]|-1)/|[x]|)
=(1/|X|) ∑ ∑ ((|C|-1)/|C|) c ∈ C x ∈ C =(1/|X|) ∑( |C|- 1) c ∈ C =(1/|X|) (∑|C|-∑1) c ∈ C c ∈ C  (|X|-|Z|)/|X| (|X|-|X|/2)/|X|=1/2 因此，构造了一个成功率至少为1/2的Las Vegas算法。 注：说明强无碰撞与单向性的关系是，单向性含于强 无碰撞之中

23 (二)生日攻击： 任找23人，从中总能选出两人具有相同生日的概率至少为1/2。 假设h:X Z是一个散列函数，X和Z是有限的，且|X|>=2|Z|，记|X|=m和|Z|=n，易见至少有n个碰撞—问题是如何找到它们？ 自然的方法是，选择k个随机的不同元素x1,x2,…,xk ∈ X，计算Zi=h(xi)，1<=i<=k。 然后确定一个碰撞是否已发生(例如：通过分类Zi的值)。 这个过程类似于随机抛k个球进入n个箱子，然后检查一下是否有一些箱子包含了至少两个球(这k个球对应于k个随机值xi，且n个箱子对应于Z中n个元素） 用上述模型来计算一个碰撞的概率下界。这个下界仅依赖于k和n，但不依赖于m。预先做一个假设：

24 任意z ∈ Z,|h-1(Z)|≈m/n(这个假设是合理的，若对任意z ∈ Z的原象个数分布不均匀，则找1个碰撞的概率将增加)。由这些假设可推断xi的象h(xi)=Zi(i=1,2,…,k)也可视为Z中的随机元素。(这k个随机元，也可有相同的)。一个重要的问题是： 若计算这k个随机元素z1,z2,..,zk ∈ Z两两不同(无碰撞时)，对应于初始问题—无碰撞的概率： 考虑有序z1,z2,…,zk中的zi的选择可能，第一个选择z1是随机的，z2z1的概率为1-1/n;z3不同于z1和z2的概率为1-2/n,等等。 因此，无碰撞的概率为(随机抛k个球进入n个箱子,没有箱子被抛进两个以上的球的概率)

25 k-1 (1-1/n)(1-2/n)…(1-(k-1)/n)=∏(1-i/n)≈1-e(-(k(k-1)/(2n)) i=1 注：若设E=1- e(-(k(k-1)/(2n)) ,可解出k的关于n,E的函数，有 e(-(k(k-1)/(2n)) =1-E , (-(k(k-1)/(2n))≈ln(1-E), k2-k≈2nln(1-E)-1 若略去-k项，有k≈ (n(ln(1/(1-E))2)0.5 若取E=0.5,我们估计k≈1.17 n0.5≈ n0.5 说明，在集合X中，n0.5个随机元素散列的结果产生 一个碰撞的概率为50%! 所谓生日攻击就是：如果X为一些人的集合，Y是 一个非闰年的365天集合，h(x)表示x的生日。(x ∈ X)。 在上述估计式中取n=365, 得k≈22.3，即随机的23人中至 少有一个重复生日的概率至少为50%。

26 生日攻击给出消息尺寸的下界。一个40bit的消息摘要将是不安全的。因为k≈1. 17 （240)0
生日攻击给出消息尺寸的下界。一个40bit的消息摘要将是不安全的。因为k≈1.17 （240)0.5, 也就是≈220(大约100万)，即在100万个随机散列值中将找到一个碰撞的概率为1/2。通常建议，消息摘要的尺寸为128bits。