网络安全 第六章 消息认证和杂凑函数

网络安全 第六章 消息认证和杂凑函数

消息认证与消息认证码

信息安全所面临的基本攻击包括

  • 被动攻击
    • 获取消息的内容
    • 业务流分析
  • 主动攻击
    • 假冒、重放、篡改
    • 业务拒绝

加密机制可以抗击被动攻击,消息认证则抗击主动攻击。

目的:消息的真实性和完整性,同时验证顺序性和时间性。

  • 对称认证
    • 防止第三方的攻击,如文件是否被人修改过
  • 非对称认证
    • 防止对方的攻击,查验收到的文件是否真实

数字签名亦是一种认证技术,实现消息的不可否认性,也可抗击主动攻击。

消息认证机制和数字签名机制都需要产生 认证符

  • 用于认证消息的数值,其产生方法分为
    • 消息认证码(MAC)
    • 哈希函数(Hash function)

消息认证码

定义:消息被一密钥控制的公开函数作用后产生的、用作认证符、固定长度的数值,亦称为 密码校验和

应用场景:双方 A 和 B 共享密钥 K,A 将要发送给 B 的消息 M 经过 \(C_K\) 函数计算 MAC,然后发送 M||MAC 给 B,B 收到后对 M 进行相同计算,将求得的 MAC 与收到的 MAC 作比较。

  • 由于 K 仅双方知道,则若 MAC 一致,则 B 知道 A 发来的消息未被篡改,且发送方不是冒充的。

杂凑函数

定义:哈希函数 H 是一公开函数,用于将任意长的信息 M 映射为较短的、固定长度的一个值 H(M)。

哈希函数应满足的条件:

  1. 函数的输入可以是任意长度
  2. 函数的输出是固定长度
  3. 快速性:已知 x,求 H(x) 十分容易
  4. 单向性:已知 h,求使得 H(x) = h 的 x 在计算上是不可行的
    • 称 H(x) 为单向杂凑函数
    • 抗原象攻击
  5. 已知 x,找出 \(y(y \neq x)\) 使得 H(y) = H(x) 在计算上是不可行的
    • 称 H(x) 为弱单向杂凑函数
  6. 找出任意两个不同的输入 x、y,使得 H(y) = H(x) 在计算上是不可行的
    • 称 H(x) 为强单向杂凑函数
    • 抗碰撞攻击
    • 抗生日攻击

如果杂凑函数对不同的输入可产生相同的输出,则称该函数具有碰撞性。上述 5 和 6 给出了杂凑函数的无碰撞性。

哈希值碰撞

有一对消息 M1 和 M2,使得 \(H(M_1) = H(M_2)\),则可以用 M2 来替换 M1,达到攻击的目的。

第 Ⅰ 类生日攻击

已知一杂凑函数 H 有 n 个可能的输出,H(x) 是一个特定的输出,如果对 H 随机取 k 个输入,则至少有一个输入 y 使得 H(y) = H(x) 的概率为 0.5 时,k 有多大?(第 I 类生日攻击)

\[1-(1- \frac1n)^k \approx 1-(1-\frac kn) = \frac kn = \frac 12\]

说明:寻找一个 y 使得 H(y) = H(x),概率为 \(\frac 1n\),因为 H(x) 有 n 种取值,那么不同的概率即为 \(1-\frac 1n\),独立且连续取 k 个,其概率乘积为 \((1-\frac 1n)^k\),这是取 k 个输入,其结果都与 H(x) 不同的概率,其相反事件,至少有一个输入使得其相同的概率即为 \(1- (1-\frac 1n)^k\)

若 H 输出为 m 比特长,即可能输出个数 \(n=2^m\),则 \(k = 2 ^{m-1}\)

第 Ⅱ 类生日攻击

设杂凑函数 H 有 \(2^m\) 个可能的输出(即输出长 m 比特),如果 H 的 k 个随机输入中至少有两个产生相同输出的概率大于 0.5,则 $k =2^{m/2} $。

说明:设事件 Q 为 k 个随机输入,其输出两两不相同。则 \(P(x)=\frac {n!}{(n-k)!\times n^k }\)。k 个输入,其两两不相同的输出取值有 \(n\times (n-1)\times ...\times (n-k+1)=\frac{n!}{(n-k)!}\) 种,一共的输出则有 \(n^k\) 种。则事件 P 为 k 个随机输入,其至少有两个产生相同输出,\(P=1-Q\)。令 \(P >\frac12\),则 \(k\approx \sqrt{n}\)

寻找函数 H 具有相同输出的两个任意输入的攻击方式为第 Ⅱ 类生日攻击。

迭代型杂凑函数的一般结构

通用迭代散列模式
通用迭代散列模式
  • 两个输入
    • n 位长度的压缩值(CV)
    • b 位长度的数据值(M)
  • 一个 n 位输出

MD5

Hash 函数的一种。算法的输入为任意长的消息(K bit),分为 521b 长的分组,输出为 128b 的消息摘要。

MD5 算法的五个步骤:

  1. 填充额外位使其长度等于 448 mod 512;
    • 即使原始长度达到要求,也要填充
    • 填充内容:1 后跟若干个 0
  2. 将消息的原始长度缩减为 mod 64,以一个 64 位数字添加到扩展后消息的尾部;
    • 以 Little-endian 方式,按数据的最低有效字节优先的顺序存储数据
  3. MD5 缓冲区初始化,为四个 32 位寄存器 A、B、C、D
    • A = 0X67452301
    • B = 0XEFCDAB89
    • C = 0X98BADCFE
    • D = 0X10325476
  4. 以分组为单位对消息进行处理,每一分组都经压缩函数 \(H_{MD5}\) 处理
  5. 输出消息的 L 个分组都被处理完后,最后一个 \(H_{MD5}\) 的输出即为消息摘要。

HMD5

压缩函数 HMD5 以四轮的方式处理每一个 512 位块,如下图:

压缩函数 HMD5
压缩函数 HMD5

每一轮 16 个阶段。F、G、H、I 为不同的逻辑函数。每轮输入为当前的消息分组 \(Block_i\) 和缓冲区的当前值 A、B、C、D,输出仍放在缓冲区中产生新的 A、B、C、D。

其中,F、G、H、I 为不同的逻辑函数。每个逻辑函数的输入为 3 个 32b 的字,输出是一个 32b 的字,真值表如下:

MD5 特定轮功能
MD5 特定轮功能

每轮处理还需加上常数表 T 中四分之一的元素,分别为 \(T[1...16],T[17...32],T[33...48],T[49...64]\),计算方式和 T 表如下:

\[T[i]= \lfloor 2^{32} \times abs(sin(i)) \rfloor\]

T 数组中 MD5 常量值
T 数组中 MD5 常量值

之后,A 的结果需要左循环移位,所需要的移位值如下表:

MD5 中位循环移位量
MD5 中位循环移位量

总的来说,压缩函数 \(H_{MD5}\) 有 4 轮处理过程,每轮又有 16 布迭代运算,每一轮运算形式:\(A,B,C,D \leftarrow D,B +CLS_s (A+g(B,C,D)+X[k]+T[i]),B,C\)

  • A、B、C、D 是缓冲区的四个字
  • \(CLS_s\) 是左循环移 s 位,s 如上图
  • g 是基本逻辑函数 F、G、H、I 之一
  • \(X[k] = M[q\times 16+k]\),消息第 q 个分组的第 k 个字
    • 第一轮以字的初始次序使用
    • 第二到四轮分别对字的次序 i 做置换后得到新次序
      • \(\rho_2 (i)=(1+5i) \ mod \ 16\)
      • \(\rho_3 (i)=(5+3i) \ mod \ 16\)
      • \(\rho_4 (i)=7i \ mod \ 16\)
  • T[i] 是表 T 中的第 i 个字

SHA 家族

SHA(Secure Hash Algorithm) 是一个密码散列函数家族,由美国国家安全局设计,是美国政府的标准。

SHA-0,最初于 1993 年发布,但发布后很快就被撤回,由 1995 年发布的 SHA-1 取代。2002 年官方标准发布了 SHA-2(SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256)。2012 年美国 NIST 选择了 Keccak 作为 SHA-3 的标准算法。

SHA-1在许多安全协定中广为使用,包括 TLS 和 SSL、PGP、SSH、S/MIME 和IPsec,曾被视为是 MD5 的后继者。但 SHA-1 的安全性如今被密码学家严重质疑;虽然至今尚未出现对 SHA-2 有效的攻击,它的算法跟 SHA-1 基本上仍然相似;因此有些人开始发展其他替代的杂凑算法。

SHA-1

算法的输入为小于 \(2^{64}\)b 长的任意消息,分为 512b 长的分组,输出为 160b 长的消息摘要。它包含四轮运算,每一轮有 20 个阶段。

  1. 对消息的填充:与 MD5 步骤一完全相同;
  2. 附加消息与 MD5 类似,但以 big-endian 方式;
  3. 初始化缓冲区,160b 长的缓冲区,分为 5 个 32b 长的寄存器 A、B、C、D、E;
    • A = 0X67452301
    • B = 0XEFCDAB89
    • C = 0X98BADCFE
    • D = 0X10325476
    • E = 0XC3D2E1F0
  4. 以分组为单位对消息进行处理,每一分组 \(Y_q\) 经一压缩函数处理,压缩函数由 4 轮处理过程构成,每一轮包含 20 步迭代。
    • 每轮输入当前分组 \(Y_q\),缓冲区当前值 A、B、C、D、E
    • 输出代替缓冲区 A、B、C、D、E
    • 还需加法常量 K,80 个常量实际只有 4 个不同取值
  5. 输出消息的 L 个分组都被处理完后,最后一个分组即为 160b 的消息摘要。

SHA-1 的压缩函数

SHA 的各轮与各个阶段
SHA 的各轮与各个阶段

每一轮的处理过程:\(CV_{q+1}=SUM_{32}(CV_q,ABCDE_q)\),其中 SUM 是模 32 位加法, \(CV_i\) 为计算过程中的缓冲区 A、B、C、D、E。最终摘要值为 \(CV_L\)

每一步迭代运算的形式为:

\[A,B,C,D,E \leftarrow (E+F_t(B,C,D)+CLS_5(A)+W_t+K_t),A,CLS_{30}(B),C,D\]

  • A、B、C、D、E 为缓冲区的 5 个字

  • \(f_t(B,C,D)\) 是第 t 步迭代使用的基本逻辑函数,每一轮逻辑函数相同

    • 4 轮所使用的基本逻辑函数 \(F_1,F_2,F_3,F_4\)

    • 其真值表:

      F 函数真值表
      F 函数真值表
  • \(CLS_s\) 为左循环 s 位

  • \(W_t\) 是由当前 512b 长的分组导出的一个 32b 长的字

    • \(W_t=CLS_1(W_{t-16}\oplus W_{t-14}\oplus W_{t-8}\oplus W_{t-3})\)
    • \(W_0,...,W_{15}\),直接取输入分组的 16 个对应字
  • \(K_t\) 是加法常量,每轮相同

    • K[t] = 0X5A827999,t 为 0 ~ 19
    • K[t] = 0X6ED9EBA1,t 为 20 ~ 39
    • K[t] = 0X8F1BBCDC,t 为 40 ~ 59
    • K[t] = 0XCA62C1D6,t 为 60 ~ 79

SHA-2

SHA-224、SHA-256、SHA-384 和 SHA-512 后跟的数字,代表了输出摘要的长度,与 SHA-1 相比,结构相同,逻辑函数相同,模算数相同。

下面以 SHA-512 为例:

SHA-512

SHA-512 算法输入报文的最大长度不超过 \(2^{128}\)b,输入按 1024b 分组进行处理,产生的输出是一个 512b 的报文摘要。

  1. 填充比特,使得填充后长度 = 896 mod 1024,填充 1 个 1 和后续若干个 0,若消息长度已满足要求,也要填充;
  2. 附加长度值。将用 128b 表示的初始报文(填充前)的位长度附加在步骤1 的结果后;
  3. 初始化缓存。使用一个 512b 的缓存 A、B、C、D、E、F、G、H 来存放该散列函数的中间及最终结果;
    • 前 8 个素数取立方根,取小数部分的前 64 比特
    • big-endian 方式
  4. 处理 1024b 报文分组序列。该算法使用了六种基本逻辑函数,由 80 步迭代运算组成。每步都以 256b 缓存值 ABCDEFGH 为输入,然后更新缓存内容。每步使用一个 64b 常数值 \(K_t\) 和一个 64b \(W_t\)
SHA-512 的轮函数
SHA-512 的轮函数
  • \(T_1 = H + Ch(E,F,G)+\sum_1^{512}E+W_t+K_t\)
  • \(T_2=(\sum_0^{512}A)+Maj(A,B,C)\)
  • \(A,B,C,D,E,F,G,H \leftarrow T_1+T_2,A,B,C,D+T_1,E,F,G\)
  • \(Ch(E,F,G)=(E \land F)\oplus(\neg E \land G)\)
  • \(Maj(A,B,C)=(A \land B)\oplus (A \land C) \oplus (B \land C)\)
  • \(\sum_0^{512}A=ROTR_{28}(A)\oplus ROTR_{34}(A) \oplus ROTR_{39}(A)\)
  • \(\sum_1^{512}E=ROTR_{14}(E)\oplus ROTR_{18}(E) \oplus ROTR_{41}(E)\)
  • \(ROTR_i(X)\) 表示将 X 右循环移 i 位
  • \(K_t\):第 t 小的素数开立方,取根的小数部分前 64bit,共 80 个
  • \(W_t\) 是由当前 1024b 长的分组导出的一个 64b 长的字
    • \(W_t=\sigma_1^{512} (W_{t-2})+W_{t-7}+\sigma_0^{512} (W_{t-15})+ W_{t-16}\)
    • \(W_0,...,W_{15}\),直接取输入分组的 16 个对应字
    • \(\sigma_1^{512} (x)=ROTR_1(x)\oplus ROTR_8(x)\oplus SHR_7(x)\)
    • \(\sigma_0^{512} (x)=ROTR_{19}(x)\oplus ROTR_{61}(x)\oplus SHR_6(x)\)
    • \(SHR_i (x)\) 表示 x 左移 i 位,右边填 0

SHA-3

Keccak 算法。同 SHA-2 一样,有 Keccak-224/256/384/512 四个版本。

Keccak 算法采用海绵结构,在预处理(填充并分成大小相同的块)后,海绵结构主要分成两部分:

  • 吸入阶段(absorbing phase):将块 \(x_i\) 传入算法并处理。
  • 挤出阶段(squeezing phase):产生一个固定长度的输出。

Keccak 算法的整体结构如图:

Keccak 的总体结构
Keccak 的总体结构

这两个阶段使用同一个压缩函数 Keccak-f,其过程为:

吸入和挤出的过程
吸入和挤出的过程
  1. 对输入串做填充处理,使其长度能够被 r 整除,后分割为长度为 r 的块,即 \(x_0,...,x_{t-1}\) t 个块;
    • 填充 0X06 || 0X00 || … || 0X00
  2. 初始化一个长度为 r+c bit 的全零向量;
  3. 输入块 \(x_i\),与前 r 个 bit 异或,然后输入到 f 中处理;
  4. 重复上一步,直至处理完 x 中的每个块;
  5. 输出长为 r 的块作为 \(y_0\),输入到 f 中去,输出 \(y_1\),以此类推输出 Hash 序列 \(y =y_0||y_1||...||y_u\),在 Keccak-224/256/384/512 中,只需要在 \(y_0\) 中取出对应长度的前缀即可。
    • r:比特率,是每个输入块的长度
    • c:容量:输出长度的两倍
    • b:向量长度,b = r + c
      • b 的值依赖于指数 \(l\)\(b=25*2^l\)
      • 本文中,\(l=6,b=1600\)
b /bits r /bits c /bits 输出长度 /bits 安全级别 /bits
1600 1152 448 224 112
1600 1088 512 256 128
1600 832 768 384 192
1600 576 1024 512 256

压缩函数 Keccak-f

输入 b 比特,输出 b 比特,内部结构如下:

Keccak-f 内部结构
Keccak-f 内部结构
  • \(n_r\) 轮,其取值与计算 b 用到的 \(l\) 有关,\(n_r=12+2*l\)
  • 每一轮中,执行五步,θ、ρ、π、χ、ι
    • $: a[x][y][z] a[x][y][z]+{y'=0}^4 a[x][y'][z]+{y'=0}^4 a[x+1][y'][z-1] $
    • \(\rho: a[x][y][z]\leftarrow a[x][y][z-(t+1)(t+2)/2]\)
      • t 满足 \[0 \leq t < 24 \]

        \[\begin{pmatrix} 0 & 1 \\ 2 & 3\end{pmatrix}^t \begin{pmatrix} 1 \\ 0\end{pmatrix}= \begin{pmatrix} x \\ y\end{pmatrix} \]

      • in \(GF[5]^{2 \times 2}\),或 x = y = 0 时,t = -1
    • \(\pi:a[x][y]\leftarrow a[x'][y']\)

      • t 满足

        \[\begin{pmatrix} 0 & 1 \\ 2 & 3\end{pmatrix} \times\begin{pmatrix} x' \\ y'\end{pmatrix}= \begin{pmatrix} x \\ y\end{pmatrix} \]
    • \(\chi:a[x]\leftarrow a[x]+(a[x+1]+1)a[x+2]\)
    • \(\iota:a\leftarrow a+RC[i_r]\)
    • 上述中加法和乘法均为 GF[2] 中运算
  • 把 1600 bit 排列成 \(5*5*w\) 的矩阵 a,其中 \(w = 2 *l\)
1
2
3
4
5
6
7
圈常数 RC[nr] = {
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008};

HMAC

利用哈希算法,以一个密钥和一个消息为输入,生成一个消息摘要。

\[HMAC(K,m) = H((K \oplus opad) ∥ H((K \oplus ipad) ∥ m))\]

  • opad:重复 0X36 B 次
  • ipad:重复 0X5C B 次
  • K:认证密钥
  • m:信息
  • H:采用的哈希算法
  • B:散列函数的明文长度分组

操作步骤如下:

(1)在密钥 K 后面填充 0,使其成为长度为 B byte 的字符串;如:K 是 20byte的字符串,B = 64,则要填充 44 个字节的 0x00。

(2)用第一步得到的 B byte 的字符串与 ipad 按位异或;

(3)将数据流 m 附加到第(2)步产生的 B byte 字符串后面;

(4)对第(3)产生的数据流用散列函数 H 计算消息摘要;

(5)用第一步得到的 B byte 的字符串与 opad 按位异或;

(6)将第(4)生成的消息摘要附加到第(5)步的 B byte 字符串之后;

(7)对第(6)产生的数据流用散列函数 H 计算消息摘要,作为输出。

典型应用:挑战/响应 身份认证

  1. 客户端向服务器发出一个验证请求
  2. 服务器接到此请求后生成一个随机数并通过网络传输给客户端(此为挑战)
  3. 客户端将收到的随机数提供给 ePass,由 ePass 使用该随机数与存储在 ePass 中的密钥进行HMAC-MD5 运算并得到一个结果作为认证证据传给服务器(此为响应)。
  4. 与此同时,服务器也使用该随机数与存储在服务器数据库中的该客户密钥进行 HMAC-MD5 运算,如果服务器的运算结果与客户端传回的响应结果相同,则认为客户端是一个合法用户 。

参考文献

华中科技大学密码学课件第六章

SHA-256

Keccak

Keccak算法介绍与分析

SHA-3 and The Hash Function Keccak

HMAC

HMAC

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×