Computer & Network Security I

Size: px

Start display at page:

Download "Computer & Network Security I"

靠来臧
5 years ago
Views:

1 第 4 章数据认证 1

2 为什么需要数据认证? 验证数据的来源确认数据没有被篡改或伪造一个使用预共享秘密的简单认证方案 : Alice 发送消息 M 和密文 C = E k (M) 给 Bob Bob 接收到消息后, 用密钥 K 解密密文 C 得到 M 如果 M = M, 那么 Bob 确认消息 M 来自于 Alice 公钥密码体系能够提供数据认证和抗抵赖功能当需要认证一个很长的消息 M 时, 只需要计算代表此消息的短字符串 h, 并进行加密 2

3 数字指纹不需要使用秘密密钥而生成的一个长数据的短的表示, 称为数字摘要或数字指纹数字指纹可以使用密码散列函数得到, 又称为单向散列函数使用秘密密钥产生的数据的短表示, 称为消息认证码 (MAC) 或标签 MAC 可以通过加密的校验和算法得到带密钥的散列消息认证码 (HMAC) 是密码散列函数和密码校验和算法的组合 3

4 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 4

5 密码散列函数散列函数以一个长的消息为输入, 分成若干部分后, 进行打碎重组, 产生一个新的短字符串不是每一个散列函数都适合用于生成数字指纹, 例如 : M = M 1 M 2 M k 其中 M i 是一个 16-bit 的二进制串定义下面的散列函数 H : H (M) = M 1 M 2 M k 对于上面的散列函数, 很容易举出一些例子, 使得不同的明文消息具有相同的杂凑值 S 1 : He likes you but I hate you 和 S 2 : He hates you but I like you 把上面消息的英文字符用 8-bit ASCII 码进行编码, 并去掉单词之间的空格, 则得到 H (S 1 ) = H (S 2 ) 5

6 设计要求设 H 表示一个散列函数, Γ 是输入长度的上界, γ 是比 Γ 小得多的固定的输出长度单向性 : 计算一个给定消息串的数字指纹是容易的, 但是找到一个数字指纹对应的消息是困难的对于任意的二进制串 x, 其中 x Γ, 计算 H(x) 是容易的, 但是对于一个给定的散列值 h ( h = γ), 很难找到它对应的原像 x 使得 h = H(x) 6

7 设计要求计算唯一性 : 找到两个不同的消息具有相同的数字指纹是困难的无碰撞性给定一个消息 x, 满足 x Γ, 找到另一个不同的消息 y ( y Γ) 与 x 具有相同的散列值, 即 H(x) = H(y), 是困难的强无碰撞性很难找到两个消息 x 和 y 具有相同的散列, 即 H(x) = H(y) 注意 : 不满足强无碰撞性, 并不意味着不满足无碰撞性 7

8 密码散列函数的探索寻求密码散列函数尚未知是否存在单向的计算唯一的密码散列函数几个曾经被认为是安全的密码散列函数, 已被证明不能满足强无碰撞性另一个常用的散列函数 SHA-1 算法, 已经被证明其安全性低于预期本节介绍两个标准的密码散列函数 SHA-512 和 WHIRLPOOL 8

9 基本结构 SHA-1 SHA-2 系列散列函数, 以及 WHIRLPOOL 都具有相同的基本结构这种结构的核心是压缩函数 F 不同的散列函数使用不同的压缩函数反复调用不带密钥的压缩函数的 CBC 模式 M 是明文消息块, IV 是初始化向量, F 是压缩函数, + 是模加运算 9

10 SHA-512 初始化过程 (I) SHA-512 使用 512-bit 初始化向量 IV 设 r 1, r 2, r 3, r 4, r 5, r 6, r 7, and r 8 be 是 8 个 64-bit 寄存器开始时, 这 8 个寄存器被设为 8 个素数的平方根的小数部分 : 2, 3, 5, 7, 11, 13, 17, 19, 10

11 SHA-512 初始化过程 (II) 设 Γ = ,γ = 512 M 是二进制消息, 其中 M = L Γ 设 L 是 128-bit 二进制串, 标记为 b 128 (L) 将消息 M 进行填充, 得到新的二进制字符串 M : M = M 10 l b 128 (L), l 0 其中 M ( 记为 L ) 是 1024 的倍数, 则有 L = L + (1 + l) = L + l L 可以表示为于是, 我们得到 : 因此,, L 是 1024 的倍数. 设 L = 1024N, 则可以记作一系列 1024-bit 的消息块 : M = M 1 M 2 M N 11

12 SHA-512 压缩函数 (I) 两个输入 : 一个 1024-bit 明文消息块 M i 一个 512-bit 二进制串 H i-1, 其中 1 i N,H i-1 是 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 的当前值 W>>>n: 循环右移 n 位 W<<n: 线性左移 n 位 12

13 SHA-512 压缩函数 (II) 设 K 0,K 1, K 79 表示 SHA-512 常量, 其中每一个常量是一个 64-bit 二进制串, T 1 和 T 2 表示 64-bit 的临时变量,r 是一个 64-bit 寄存器. 设 13

14 SHA-512 压缩函数 (III) 进行 80 轮下面的运算 : 然后, r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 中的 512-bit 字符串就是 F(M i, H i-1 ) 的输出 14

15 SHA-512 算法设 X = X 1 X 2 X k, Y = Y 1 Y 2 Y k 是二进制串, 其中 X i,y i 是 l-bit 字符串. 设 l-bit 的下列运算 : 消息 M 的数字指纹是 H(M) = H N, 其中 15

16 WHIRLPOOL 初始化过程在 Whirlpool 中, Γ = , γ = 512 消息 M 是二进制串, M = L Γ, 将 L 表示为一个 256-bit 二进制串, 记为 b 256 (L). 进行消息填充 : M = M 10 l b 256 (L), l 0 满足 L = M 是 512 的倍数. 则有 L = L + (1 + l) = L + l L 表示为于是, 我们有 : L 是 512 的倍数, 即 L = 512N. 记为 M = M 1 M 2 M N 其中 M i 是一个 512-bit 二进制串 16

17 WHIRLPOOL 压缩函数 WHIRLPOOL 的压缩函数定义为 : W(X, K) 类似于 AES 的加密算法输入 : 512-bit 明文块 X 和 512-bit 密钥 K 输出 : 512-bit 输出消息 M 的数字指纹 H(M) = H N, 是通过使用 CBC 模式得到的 : 17

18 W(X, K) 的构造由密钥 K 共生成 11 个 512-bit 的轮密钥, 记为 K 0, K 1,, K 10. K 0 = K K i (1 i 10) 是由 K i-1 经过 4 个基本运算得到的字节替代 (sub) 列移位 (shc) 行混淆 (mir) 常数相加 (arc) K i = arc(mir(shc(sub(k i-1 ))), RC i ) 其中 RC i 是 512-bit 常数, 由 WHIRLOOL S 盒产生 : 其中 i = 1, 2,, 10 18

19 字节替代 (sub) WHIRLPOOL 的字节替代使用 16ⅹ16 S 盒设 A = (a i,j ) 8ⅹ8 是 8ⅹ8 的字节状态矩阵设 x = x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 是 8-bit 字符串, 其中每一个 x i {0,1} 设 π 1 (x) 是二进制串 x 0 x 1 x 2 x 3 的十进制数值,π 2 (x) 是二进制串 x 4 x 5 x 6 x 7 的十进制值定义替代函数 S 为其中 s u,v 是 WHIRLPOOL s S 盒中第 u 行第 v 列上的元素,0 u, v 7 WHIRLPOOL 的字节替代操作定义为 : sub(a) = (S(a i,j )) 8ⅹ8 列移位 (shc) 类似于 AES 的行移位操作. 第 j 列将向下循环位移 j 个字节. 19

20 行混淆 (mir) 类似于 AES 中的列混淆使用下面的常数矩阵 : 行混淆定义为 : mir(a) = A 常数加 (arc) 和轮密钥加 (ark) 类似于 AES 的轮密钥加 arc(a, RC i ) = A RC i ark(a, K i ) = A K i 20

21 加密结构当轮密钥生成后, 算法 W 将 64 字节字符串 X 表示成状态矩阵的形式 A = (a u,v ) 8 8, 其中 a u,v = x 8u+v, u,v = 0, 1,,7 然后, 将 A 和 K 0 进行轮密钥加运算, 生成新的状态矩阵 A 0 进行 10 轮的运算, 每一轮计算 (1 i 10) 最后,W(X, K) = A 10 21

22 W 的流程图 22

23 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 23

24 密码校验和校验和通常用于检测网络通信中的传输错误但是, 这些校验和不能用于数据认证或数字指纹, 因为很容易找到不同的消息具有相同的校验和我们可以用对称密码算法生成密码校验和, 用于数据认证密码校验和又称为消息认证码 (MAC) 24

25 异或密码校验和设 E 表示 AES-128 加密算法,K 是 AES-128 秘密密钥这种方法是不安全的, 容易受到中间人攻击. 例如, 假设 Alice 和 Bob 共享一个 AES-128 密钥 K. 如果 Alice 发送 M, E K (H (M))) 给 Bob 来对消息 M 进行认证,Malice 监听了这个密文, 那么 Malice 能够用 E K (H (M)) 假冒 Alice 的身份. 25

26 中间人攻击设 M = Y 1 Y 2 Y l 是任意消息, 其中 Y i 是 128-bit 二进制串. Malice 发送给 Bob: Bob 先计算然后, 解密 '' E K ( H ( M )), 得到 H ( M ) H ( M ) 这样 Bob 认为消息 M 来自于 Alice, 但实际上不是. 26

27 密码校验和的设计要求设 MAC K (M) 为 M 的消息认证码, 其中 K 是秘密密钥, 我们需要 MAC K (M) 满足下列要求 : 1. 正向易解性 : 计算 MAC K (M) 是容易的. 2. 反向难解性 : 从 MAC K (M) 计算出 M 是困难的. 3. 计算唯一性 : 从 (M, MAC K (M) ) 找到 M M 使得 MAC K (M ) = MAC K (M) 是困难的. 4. 均匀分布 : 设 k 是消息认证码的长度,M 是随机选取的数据. 设 M (M M) 是随机选取或由 M 变换而来的, 则 MAC K (M ) = MAC K (M) 的概率是 2 -k. 27

28 密码校验和的构造尚没有已知的算法能满足这四条准则构造密码校验和的一般性方法 : 加密算法和单向散列函数这种方法满足实际应用的需要 28

29 数据认证算法 1985 年, NIST 制定了一种数据认证码标准, 称为 DAC, 是基于 DES 算法的 CBC 模式设 M = M 1 M 2 M k, 其中 M i 是 64-bit 二进制串,K 是 DES 密钥, E 是 DES 密码算法. 令则 DAC = C k. 当 DES 的安全性受到威胁后,DAC 被新的消息认证码方案 HMAC 替代 29

30 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 30

31 密钥散列消息认证码 -HMAC HMAC 是一种算法方案使用散列函数和对称密码算法生成认证码 HMAC 的设计要求 1. 任何散列函数可以直接嵌入使用 2. HMAC 中的密码散列函数应满足单向性计算唯一性等基本性质 3. 秘密密钥的使用是简单易行的 4. HMAC 认证码的安全性强度与所采用的散列函数的安全性强度密切相关 31

32 HMAC 参数 H: 嵌入散列函数 ( 例如 SHA-512 和 WHIRLPOOL) IV: 散列函数的初始化向量 M: 输入的要认证的消息 L: 消息块的个数 l: 散列函数的输出长度 b: 一个消息块的比特数, 其是 8 的倍数, 且满足 b l K: 秘密密钥, 其长度 b K : K = 0 b- K K, 是 K 的前缀填充, 有 K = b ipad: ipad = ( ) b/8 opad: opad = ( ) b/8 K 0 : K 0 = K ipad. K 1 : K 1 = K opad. 32

33 HMAC 算法 HMAC 算法描述如下 : 33

34 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 34

35 第 4 章数据认证 Part II 35

36 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 36

37 生日攻击基础在一个 23 个人的集体中, 至少两个人具有同一天生日的概率大于 1/2. 证明. 23 个人的生日互不相同的概率为 : 因此, > ½. 37

38 强无碰撞性的复杂性上界抗强无碰撞性的复杂性上界设 H 是一个输出长度为 l 的密码散列函数, 则 H 至多有 n = 2 l 个不同的输出值问题 : 2 l 是抗强无碰撞性的复杂性上界吗? 答案是否定的, 我们可以用生日攻击将复杂性降低为 2 l/2, 成功概率在 50% 以上生日悖论 : 一个篮子里装了 n 个不同颜色的球, 均匀地独立随机地从篮子里取 k (k<n) 个球 ( 一次取一个, 记录颜色后放回 ), 如果则一个球被取了两次的概率不小于 1/2. SHA-1 的复杂性上界 : 2 160/2 = 2 80 ; SHA-512: 2 512/2 =

39 集合相交攻击独立随机地从 {1,2,,n} 中选取两个各包含 k 个整数的集合, 其中 k < n 这两个集合有交集的概率 Q(n,k) 是多少? 这两个集合不相交的概率为因此, 如果, 则 39

40 集合相交攻击的例子集合相交攻击是生日攻击的一种形式例如 : Malice 可以先用一个合法文档 D 得到认证者 AU 的签名 C ) HD ( r KAU 然后,Malice 产生一个新的文档 F, 其与 D 的内容不同, 但是有 H(F)=H(D) Malice 用 (F,C) 表示文件 F 是由 AU 签署的 40

41 如何找到文档 F? Malice 首先准备一个文档集合 S 1, 其包含 2 l/2 个不同的文档, 这些文档均与文档 D 具有相同的意思. 这些文档可以用下面方法得到 : a) 替换一个单词或句子 b) 重新整理调整句子的描述 c) 使用不同的标点符号 d) 重新组织文档的结构 e) 改变语气, 比如把被动语句改为主动语句 Malice 准备另一个文档集合 S 2, 其包含 2 l/2 个不同的文档, 这些文档均与文档 F 具有相同的意思, 并计算 HS (){( HXXS ) } 1 HS (){( HXXS ) } H(D' )= H(F' ) D' S,F' S 1/ 2 因此, Pr 2 1 >

42 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 42

43 数字签名标准 (DSS) 对消息 M 的数字签名 : (, E( H( M))) 公钥密码系统产生数字签名的最有效的机制 RSA ( 直到 2000 年前专利保护 ) 数字签名标准 -DSS M ra K 1991 年颁布 2000 年以后,RSA 和 ECC 被制定为数字签名标准只生成数字签名, 不加密数据 43

44 DSS 的构造 H: SHA-1 (160 bit) L: 512 < L < 1024 参数 : P: 大素数 ; 2 L 1 < p < 2 L q: p 1 的素因子 ; < q < g: g = h (p 1)/q mod p; 1 < h < p 1, g > 1 44

45 DSS 签名 Alice 要对消息 M 进行签名随机选取一个私钥, 0 < x A < q 计算公钥 : y A = g xa mod p 随机选取一个整数 : 0 < k A < q r A = (g ka mod p) mod q k 1 A = k q 2 A mod q s A = k 1 A (H(M)+x A r A ) mod q M 的数字签名为 : (r A, s A ) 45

46 DSS 验证签名 Bob 得到签名值 (M', (r A ', S A ')) 和公钥证书 CA[y A ] 解析公钥证书 CA[y A ], 得到 Alice 的公钥 y A 验证签名 : w = (S A ') 1 mod q = (S A ') q 1 mod q u1 = (H(M') w) mod q u2 = (r A ' w) mod q v = [(g u1 y u2 A ) mod p] mod q 如果 v = r A ', 则签名验证通过 46

47 DSS 的安全强度基于 SHA-1 的安全强度和求解离散对数的困难性攻破 SHA-1 散列函数的强无碰撞性的已经由 2 80 降低到 2 63 攻破无碰撞性更困难离散对数的难解性表明, 从 r A 和 s A 计算出 k A 或 x A 是困难的 47

48 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 48

49 双签名与电子交易 Alice ( 客户 ) Alice 想让 bob 执行一个购物订单 ( I 1 ) Bob ( 商家 ) Alice 必须发送付款信息给银行 Charlie ( I 2 ) Charlie ( 银行 ) Bob 等待来自银行 Charlie 的支付确认信息 49

50 双签名我们不想让 Bob 看到 I 2, 不想让 Charlie 看到 I 1 在 Bob 得到 I 1 之前,Charlie 不能发送 I 2 给 Bob I 1 和 I 2 必须是绑定的, 以防止付款与订单不一致所有的消息必须被认证和加密, 即没有有用的消息被泄露修改或伪造 50

51 双签名一种用于电子交易的交互式认证协议提供安全和隐私性保护在 SET 协议 (Secure Electronic Transactions) 中使用, 此协议是由 Visa 和 MasterCard 在 1996 年设计的, 但是没有在实际中推广需要 Alice, Bob 和 Charlie 协商确定使用的散列函数 H 和公钥加密算法 E Alice, Bob 和 Charlie 必须各自有一对 RSA 密钥对 : (K Au, K Ar ), (K Bu, K Br ), (K Cu, K Cr ) 51

52 SET 协议 : 客户 Alice 计算下面的值 : H ( s 发送 (s B, s C, ds) 给 Bob 等待 Bob 的收据 R B = s h B B ds E D K K u B r A ( I1), sc E u ( I2), B ), h ( H ( h E H ( s h 用 K r A 解密 R B, 得到 ; 用 K u B 验证 Bob K 的签名 C K D rb u A B C K C )) C ), ( D ( RB )) K r B ( R B ) 52

53 SET 协议 : 商家 Bob 验证 Alice 的签名 : 比较与解密发送 (s B, s C, ds) 给 Charlie 等待 Charlie 的收据 R C = 用 K r B 解密 R C 得到的签名发送签名的收据 R B,, 用 K C u 验证 Charlie 给 Alice 53

54 SET 协议 : 银行 Charlie 验证 Alice 的签名 : 比较和解密如果 I 2 包含了有效的付款信息, 则执行正确的付款交易操作, 并发送签名的收据 R C, 给 Bob 54

55 第 4 章内容概要 4.1 密码散列函数 4.2 密码校验和 4.3 HMAC 4.4 密码本偏移操作模式 4.5 生日攻击 4.6 数字签名标准 4.7 双签名与电子交易 4.8 盲签名与电子现金 55

56 盲签名让签名者进行签名, 但不向签名者泄露所签文件的内容需要签名的文档与一个掩盖因子绑定, 以防止签名者看到文档的信息, 但是掩盖因子可以在以后被去掉 56

57 RSA 盲签名随机产生 r < n ( 掩盖因子 ), 满足 gcd(r, n) = 1 令 M r = M r e mod n 签名者对消息 M r 进行签名, 得到 s r = M d r mod n 可以通过以下方法去除掩盖因子 r : s M = s r r 1 mod n = M d mod n 57

58 证明 : 掩盖因子被去除 : s M = (s r r 1 ) mod n = (M d r ed r 1 ) mod n 因为 ed 1 mod ф(n)) r ed r mod n (Fermat s little theorem) 所以 s M = M d mod n 58

59 电子现金真正的现金具有以下特性 : 匿名性转让性可分割性很难伪造电子现金能具备这些特性吗? 59

60 理想的电子现金协议一个理想的电子现金协议应具有以下性质 : 匿名性和不可追踪性安全性 : 不能被修改或伪造便捷性 : 允许离线交易单一性 : 不能被复制或重用转让性 : 可以转让可分割性 : 可以被分割成小的数值. 尚没有满足以上所有性质的电子现金协议 60

61 电子现金 -ecash 1980 年代提出满足电子现金的很多重要性质使用盲签名来保证匿名性和不可追踪性设 B 表示金融机构设 B 的 RSA 参数为 (n, d, e) 61

62 购买电子现金 Alice 进行下面的操作 : 生成一个序列号 m 来代表要购买的电子现金产生一个随机数 r < n ( 掩盖因子 ), 并计算 x = mr e mod n 发送 x 和她的账户号给银行 B 银行 B 从 Alice 的账户支取 $1, 并发送 y = x d mod n 给 Alice ( 获得银行的签名 ) Alice 计算 z y r -1 m d mod n Alice 得到电子现金 (m, z) 62

63 兑换电子现金 Bob 从 Alice 收到了电子现金, 并想进行兑换他发送 (m, z) 和账户号给银行 B. 如果签名是有效的, 而且序列号为 m 的电子现金没有被兑现过, 则银行记录下序列号 m, 并支付 $1 给 Bob 的账户问题 : 既然复制 (m, z) 是容易的, Bob 如何能够防止别人在他之前兑换电子现金呢? 63

Microsoft Word - 第2部分.doc

Microsoft Word - 第2部分.doc SM9 标识密码算法第 2 部分 : 数字签名算法目次 1 术语和定义... 2 2 符号... 2 3 算法参数与辅助函数... 3 3.1 总则... 3 3.2 系统参数组... 3 3.3 系统签名主密钥和用户签名密钥的产生... 4 3.4 辅助函数... 4 3.4.1 概述... 4 3.4.2 密码杂凑函数... 4 3.4.2.1 密码杂凑函数 Hv( )... 4 3.4.2.2