一开学专业课就是密码学,意料之中,但是在课程进行中发现和本科时候学的密码学还是有所区别的,而且自己也已经很多不记得了,趁有空,把一些密码学的东西总结下,也算是对之前内容的复习和对现在正上着的课程的预习了。因为密码学是一门大学科,也没打算将所有的东西都弄懂,能够把一些常用的东西理清楚其实就很不错了,而这一篇主要是对密码杂凑函数的一些总结和概述。

简介

先引用维基上对于杂凑函数的介绍:“密码散列函数(英语:Cryptographic hash function),又译为加密散列函数、密码散列函数、加密散列函数,是散列函数的一种。它被认为是一种单向函数,也就是说极其难以由散列函数输出的结果,回推输入的数据是什么。这样的单向函数被称为“现代密码学的驮马”。这种散列函数的输入数据,通常被称为消息(message),而它的输出结果,经常被称为消息摘要(message digest)或摘要(digest)。”

简单来说,杂凑函数就是一种单向函数,由输入计算得出结果容易,但是理论上由输出结果计算输入是困难的,另外,杂凑函数也叫hash函数、散列函数等。另外,杂凑函数需符合以下性质:

  • 抗原像攻击(单向性),对任意给定的hash h,找到满足H(y)=h的y在计算上不可行
  • 抗第二原像攻击(抗弱碰撞性),对任何给定的分块x,找到满足y≠x且H(x)=H(y)的y在计算上是不可行的
  • 抗碰撞(抗强碰撞性),找到任何满足H(x)=H(y)的偶对(x,y)在计算上是不可行的

其中,满足上述条件的为弱Hash函数,如果函数的输出满足伪随机性测试标准,则成为强Hash函数。
此外,对于杂凑函数的计算,应该满足以下条件:

  • 哈希函数应该在CPU/软件和AS IC/硬件上都有效地实现。
  • 哈希函数的计算速度应该和磁盘IO相当
  • 短消息或长消息优化设计

杂凑函数输入输出

函数输入:

  • 输入长度以bit计算
  • 允许0长度输入
  • 通常一个给定的哈希函数会规定最大输入长度

函数输出:

  • 固定长度输出
  • 一般输出长度为128/160/256/512位(不同函数)
  • 同一类哈希函数的算法相似,输出长度和参数不同(比如salt)

杂凑函数结构

对于杂凑函数,目前最常见的为两种,分别为Merkle Damgard结构和海绵结构,其核心思想都在于尽可能将数据原文中的信息扩散到hash值中。

Merkle Damgard结构

算法流程:

  1. 把消息划分为n个消息块
  2. 对最后一个消息块做长度填充
  3. 每个消息块和一个输入向量做一个运算,把这个计算结果当成下个消息块的输入向量
  4. IV为初始向量,已知且固定不变

Merkle Damgard结构是使用地较多的一种杂凑函数结构,其中常见的MD5、SHA1等都是使用这一结构,但是这一结构也有其弊端,攻击者可以利用哈希长度扩展攻击进行破解,当然,在破解该种杂凑函数时需要满足以下条件:

  • 知道密文secret的长度
  • 知道一个密文secret的hash值

海绵(sponge)结构

海绵结构能够进行数据转换,将任意长的输入转换成任意长的输出。在使用海绵结构前,需要进行预处理,预处理会将数据进行分块,分成大小相同的块,在预处理后,海绵结构主要分为以下两部分:

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

假设输入为x,核心处理函数为f,则其流程分为以下几步:

  1. 对输入串x做padding,使其长度能被r整除,将padding后分割成长度为r的块,即x=x_0||x_1||x_2||…||x_t-1。
  2. 初始化一个长度为r+c bit的全零向量。
  3. 输入块x_i,将x_i和向量的前r个bit亦或,然后输入到f函数中处理。
  4. 重复上一步,直至处理完x中的每个块。
  5. 输出长为r的块作为y_0,并将向量输入到f函数中处理,输出y_1,以此类推。得到的Hash序列即为y=y_0||y_1||y_2||…||y_u。对于对应不同输出长度的杂凑函数,只需要在y_0中取出对应长度的前缀即可。

对于海绵结构,一些较新的杂凑函数,如SHA-3算法等,使用的就是这一结构。

MD5杂凑函数

MD5是使用最为广泛的杂凑函数之一,其由Ron Rivest设计,在此之前有MD2 MD4,而MD5则是在RFC1321中被提出,使用Merkle Damgard结构,后续成为使用最广泛的哈希算法,其哈希长度为128bits,主要攻击方法为爆破和密码分析。

将输入信息text的位数按照特定的方法填充至512的整数倍,然后每512位为一个分组M[i]进行处理。每个分组又将分为16个32位的子分组,经过一系列循环后将产4个32位的散列值a, b, c, d,作为下一个分组的输入。最终,将a, b, c, d组合起来即可得到text的MD5值。

其算法流程如下:

  1. 信息填充
    对明文信息进行填充0,使其长度mod512=448,因此信息的位长度被扩展为(Nx512+448)。然后再在这个结果后面附加一个以64为二进制表示的填充前信息长度,即此时长度变为 (N+1)*512。
  2. 结构初始化
    定义一个结果,包含每次需要处理的明文块(512bits)和计算出来的散列值128bits。在散列的整个过程,各个明文块计算的散列值都由其进行传播。
  3. 分组
    将填充好的明文信息进行分组,每组512位,共 N+1组
  4. 处理分组
    设置链接变量初值,共四个,每个32位,四组共128位,即密文长度为128位:
    a = 0x01234567,b = 0x89abcdef, c = 0xfedcba98,d =0x76543210
    再设A = a,B = b,C = c,D = d
    进入hash循环运算,循环次数为明文信息的分组数N+1
    每次循环运算分为4轮,每轮使用不同的函数计算,设其实的512位分组为M,则将其划分为16*32,即16个小分组,在4轮循环中,需要进行对应这16个小分组的16次运算,4轮结束后,将循环后的a,b,c,d值加到A,B,C,D上即得新一轮的链接变量,当所有512位分组都循环结束后,此时的A,B,C,D值即为哈希值。其涉及4个计算公式如下:
      F(X,Y,Z) =(X&Y)|((~X)&Z)
      G(X,Y,Z) =(X&Z)|(Y&(~Z))
      H(X,Y,Z) =X^Y^Z
      I(X,Y,Z)=Y^(X|(~Z))
      (&是与,|是或,~是非,^是异或)

函数说明:
如果X、Y和Z的对应位是独立和均匀的,那么结果的每一位也应是独立和均匀的。
假设M[j]表示消息的第j个子分组(从0到15),常数ti是4294967296*abs(sin(i))的整数部分,i取值从1到64。

  F(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + F(b, c, d) + Mj + ti) <<< s)
  GG(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + G(b, c, d) + Mj + ti) <<< s)
  HH(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + H(b, c, d) + Mj + ti) <<< s)
  II(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + I(b, c, d) + Mj + ti) <<< s)

在每次循环中,其循环分为4轮,可用下列公式表示:

a = A; b = B; c = C; d = D;
//对M[j]的第一轮循环
FF(a,b,c,d,M[0],7,0xd76aa478);
FF(d,a,b,c,M[1],12,0xe8c7b756);
FF(c,d,a,b,M[2],17,0x242070db);
FF(b,c,d,a,M[3],22,0xc1bdceee);
FF(a,b,c,d,M[4],7,0xf57c0faf);
FF(d,a,b,c,M[5],12,0x4787c62a);
FF(c,d,a,b,M[6],17,0xa8304613);
FF(b,c,d,a,M[7],22,0xfd469501) ;
FF(a,b,c,d,M[8],7,0x698098d8) ;
FF(d,a,b,c,M[9],12,0x8b44f7af) ;
FF(c,d,a,b,M[10],17,0xffff5bb1) ;
FF(b,c,d,a,M[11],22,0x895cd7be) ;
FF(a,b,c,d,M[12],7,0x6b901122) ;
FF(d,a,b,c,M[13],12,0xfd987193) ;
FF(c,d,a,b,M[14],17,0xa679438e) ;
FF(b,c,d,a,M[15],22,0x49b40821);

//对M[j]的第二轮循环
GG(a,b,c,d,M[1],5,0xf61e2562);
GG(d,a,b,c,M[6],9,0xc040b340);
GG(c,d,a,b,M[11],14,0x265e5a51);
GG(b,c,d,a,M[0],20,0xe9b6c7aa) ;
GG(a,b,c,d,M[5],5,0xd62f105d) ;
GG(d,a,b,c,M[10],9,0x02441453) ;
GG(c,d,a,b,M[15],14,0xd8a1e681);
GG(b,c,d,a,M[4],20,0xe7d3fbc8) ;
GG(a,b,c,d,M[9],5,0x21e1cde6) ;
GG(d,a,b,c,M[14],9,0xc33707d6) ;
GG(c,d,a,b,M[3],14,0xf4d50d87) ;
GG(b,c,d,a,M[8],20,0x455a14ed);
GG(a,b,c,d,M[13],5,0xa9e3e905);
GG(d,a,b,c,M[2],9,0xfcefa3f8) ;
GG(c,d,a,b,M[7],14,0x676f02d9) ;
GG(b,c,d,a,M[12],20,0x8d2a4c8a);

//对M[j]的第三轮循环
HH(a,b,c,d,M[5],4,0xfffa3942);
HH(d,a,b,c,M[8],11,0x8771f681);
HH(c,d,a,b,M[11],16,0x6d9d6122);
HH(b,c,d,a,M[14],23,0xfde5380c) ;
HH(a,b,c,d,M[1],4,0xa4beea44) ;
HH(d,a,b,c,M[4],11,0x4bdecfa9) ;
HH(c,d,a,b,M[7],16,0xf6bb4b60) ;
HH(b,c,d,a,M[10],23,0xbebfbc70);
HH(a,b,c,d,M[13],4,0x289b7ec6);
HH(d,a,b,c,M[0],11,0xeaa127fa);
HH(c,d,a,b,M[3],16,0xd4ef3085);
HH(b,c,d,a,M[6],23,0x04881d05);
HH(a,b,c,d,M[9],4,0xd9d4d039);
HH(d,a,b,c,M[12],11,0xe6db99e5);
HH(c,d,a,b,M[15],16,0x1fa27cf8) ;
HH(b,c,d,a,M[2],23,0xc4ac5665);

//对M[j]的第四轮循环
II(a,b,c,d,M[0],6,0xf4292244) ;
II(d,a,b,c,M[7],10,0x432aff97) ;
II(c,d,a,b,M[14],15,0xab9423a7);
II(b,c,d,a,M[5],21,0xfc93a039) ;
II(a,b,c,d,M[12],6,0x655b59c3) ;
II(d,a,b,c,M[3],10,0x8f0ccc92) ;
II(c,d,a,b,M[10],15,0xffeff47d);
II(b,c,d,a,M[1],21,0x85845dd1) ;
II(a,b,c,d,M[8],6,0x6fa87e4f) ;
II(d,a,b,c,M[15],10,0xfe2ce6e0);
II(c,d,a,b,M[6],15,0xa3014314) ;
II(b,c,d,a,M[13],21,0x4e0811a1);
II(a,b,c,d,M[4],6,0xf7537e82) ;
II(d,a,b,c,M[11],10,0xbd3af235);
II(c,d,a,b,M[2],15,0x2ad7d2bb);
II(b,c,d,a,M[9],21,0xeb86d391);

A += a;
B += b;
C += c;
D += d;

处理完所有的512位的分组后,得到一组新的A,B,C,D的值,将这些值按ABCD的顺序级联,然后输出。这里还要注意,输出的MD5是按内存中数值的排列顺序,所以我们要分别对A,B,C,D的值做一个小端规则的转换。举个例子:A有32位,分成4个字节A1A2A3A4。输出A的时候,要这样输出:A4A3 A2A1。这样就能输出正确的MD5了。

SHA-1杂凑函数

SHA-1(Secure Hash Algorithm 1,安全散列算法1)是一种密码杂凑函数,由美国国家安全局设计,并由(NIST)发布为FIPS。SHA-1的数据杂凑值为160位(20字节),杂凑值通常的呈现形式为40个十六进制数。该杂凑函数使用的是和MD5一样的Merkle Damgard结构。

SHA1对任意长度明文的预处理和MD5的过程是一样的,即预处理完后的明文长度是512位的整数倍,但是有一点不同,那就是SHA1的原始报文长度不能超过2的64次方,然后SHA1生成160位的报文摘要。SHA1算法简单而且紧凑,容易在计算机上实现。SHA-1和MD5相比,其差别大致可概括如下:

差异处 MD5 SHA1
摘要长度 128位 160位
运算步骤数 64 80
基本逻辑函数数目 4 4
  • 安全性:SHA1所产生的摘要比MD5长32位。若两种散列函数在结构上没有任何问题的话,SHA1比MD5更安全。
  • 速度:两种方法都是主要考虑以32位处理器为基础的系统结构。但SHA1的运算步骤比MD5多了16步,而且SHA1记录单元的长度比MD5多了32位。因此若是以硬件来实现SHA1,其速度大约比MD5慢了25%。
  • 简易性:两种方法都是相当的简单,在实现上不需要很复杂的程序或是大量存储空间。然而总体上来讲,SHA1对每一步骤的操作描述比MD5简单。

其算法流程如下:

SHA-1算法中,填充时第一位填1,其他填0,再将长度附到后面,此时明文长度为512的倍数,按照512划分分组,分别表示为Yi,然后对于每个分组进行处理。其预处理和MD5类似,区别主要在于后续的分组处理,在此也只对预处理后的步骤进行介绍:

每个512位分组划分为16个小分组Mi,将16个小分组扩充为80份小分组,记为Wi,扩充方法为:

  Wt = Mt , 当0≤t≤15
  Wt = (Wt-3⊕Wt-8⊕Wt-14⊕Wt-16)<<<1, 当16≤t≤79

SHA1有4轮运算,每一轮包括20个步骤(一共80步),最后产生160位摘要,这160位摘要存放在5个32位的链接变量中,分别标记为A、B、C、D、E。这5个链接变量的初始值以16进制位表示如下。

  A=0x67452301
  B=0xEFCDAB89
  C=0x98BADCFE
  D=0x10325476
  E=0xC3D2E1F0

SHA1有4轮运算,每一轮包括20个步骤,一共80步,当第1轮运算中的第1步骤开始处理时,A、B、C、D、E五个链接变量中的值先赋值到另外5个记录单元A′,B′,C′,D′,E′中。这5个值将保留,用于在第4轮的最后一个步骤完成之后与链接变量A,B,C,D,E进行求和操作。
在SHA-1每轮步骤中,使用的函数步骤是一样的:

  A,B,C,D,E←[(A<<<5)+ ft(B,C,D)+E+Wt+Kt],A,(B<<<30),C,D

其中 ft(B,C,D)为逻辑函数,Wt为子明文分组W[t],Kt为固定常数。这个操作程序的意义为:

  • 将[(A<<<5)+ ft(B,C,D)+E+Wt+Kt]的结果赋值给链接变量A;
  • 将链接变量A初始值赋值给链接变量B;
  • 将链接变量B初始值循环左移30位赋值给链接变量C;
  • 将链接变量C初始值赋值给链接变量D;
  • 将链接变量D初始值赋值给链接变量E。

举一个例子来说明SHA1哈希算法中的每一步是怎样进行的,比起MD5算法,SHA1相对简单,假设W[1]=0x12345678,此时链接变量的值分别为A=0x67452301、B=0xEFCDAB89、C=0x98BADCFE、D=0x10325476、E=0xC3D2E1F0,那么第1轮第1步的运算过程如下:

  1. 将链接变量A循环左移5位,得到的结果为:0xE8A4602C。
  2. 将B,C,D经过相应的逻辑函数:
    (B&C)|(~B&D)=(0xEFCDAB89&0x98BADCFE)|(~0xEFCDAB89&0x10325476)=0x98BADCFE
  3. 将第(1)步,第(2)步的结果与E,W[1],和K[1]相加得:
    0xE8A4602C+0x98BADCFE+0xC3D2E1F0+0x12345678+0x5A827999=0xB1E8EF2B
  4. 将B循环左移30位得:(B<<<30)=0x7BF36AE2。
  5. 将第3步结果赋值给A,A(这里是指A的原始值)赋值给B,步骤4的结果赋值给C,C的原始值赋值给D,D的原始值赋值给E。
  6. 最后得到第1轮第1步的结果:

  A = 0xB1E8EF2B
  B = 0x67452301
  C = 0x7BF36AE2
  D = 0x98BADCFE
  E = 0x10325476

按照这种方法,将80个步骤进行完毕。第四轮最后一个步骤的A,B,C,D,E输出,将分别与记录单元A′,B′,C′,D′,E′中的数值求和运算。其结果将作为输入成为下一个512位明文分组的链接变量A,B,C,D,E,当最后一个明文分组计算完成以后,A,B,C,D,E中的数据就是最后散列函数值。

常见杂凑函数对比

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

  • MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。
  • MD5(RFC 1321)是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以 512 位分组,其输出是 128 位。MD5 比 MD4 复杂,并且计算速度要慢一点,更安全一些。MD5 已被证明不具备"强抗碰撞性"。
  • SHA (Secure Hash Algorithm)是一个 Hash 函数族,由 NIST(National Institute of Standards and Technology)于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世,它的输出为长度 160 位的 hash 值,因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理,并且模仿了该算法。SHA-1 已被证明不具"强抗碰撞性"。
    为了提高安全性,NIST 还设计出了 SHA-224、SHA-256、SHA-384,和 SHA-512 算法(统称为 SHA-2),跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

可以看出,上面这几种流行的算法,它们最重要的一点区别就是"强抗碰撞性"。另外,在维基中对于一些主流的杂凑函数有进行对比,其总结如下:

算法和变体 输出杂凑值长度(bits) 数据块长度(bits) 最大输入消息长度(bits) 循环次数
MD5 128 512 无限 64
SHA-0 160 512 2^64-1 80
SHA-1 160 512 2^64-1 80
SHA-256 256 512 2^64-1 64
SHA-512 512 1024 2^128-1 80
SHA3-224 224 1152 无限 24
SHA3-256 256 1088 无限 24
SHA3-512 512 576 无限 24

杂凑函数安全性

如果不存在设计缺陷,根据杂凑函数的三大性质,函数的安全性取决于输出哈希值的位长度。假设给定一个长度为m的杂凑函数,攻击者至少需要爆破2^(m/2)次,这是利用生日攻击进行推导得出,具体推导过程这里不详细阐述,提供一个参考

由生日攻击可得,假设哈希空间大小为N,则只要计算 (π/2*N)^1/2 ,就有50%的可能性产生碰撞,假设N为365,按照公式计算出为23.9,其概率如下图:

由生日攻击可得,哈希碰撞所需耗费的计算次数,和取值空间的平方根是一个数量级。假设d为哈希空间大小,n为当前碰撞次数,则当前碰撞成功的概率计算公式为:

由公式可得,假设哈希值为m位,则攻击者准备2^m/2次方信息X生成hash,2^m/2次方信息Y生成hash,则找到hash(X)=hash(Y)的概率为50%。

杂凑函数应用

在密码系统中的应用

  1. 密钥导出
  2. 消息认证码
  3. 数字签名中的消息摘要
  4. 将公钥密码机制转为CCA安全机制
  5. 构造伪随机数生成器

其它应用

  1. 文件校验:使用杂凑函数计算文件哈希值作为文件完整性的校验值,检查文件是否被更改。
  2. 内容标识符:使用杂凑函数作为数据指纹,判断数据是否可信
  3. 分布式哈希表
    哈希表,将 key 和 value 以 (hash(key) ,value)的形式存储,即为哈希表,哈希表将所有数据存储在同一台设备上,而分布式哈希表则将说句分为若干个部分分别存储在不同的机器上,从而降低数据被全部损坏的风险。
    分布式哈希表是一种分布式的存储方法,不需要中心节点服务器,直接由每个客户端负责一个小范围的路由,并负责存储一小部分数据,从而实现整个DHT网络的寻址和存储。其次,DHT网络还在和关键字最接近的节点上复制备份冗余信息,从而避免单一节点失效的问题。
    DHT寻址和存储过程:
    通过DHT数据结构它把KEY和 VALUE用某种方式对应起来。使用hash()函数把一个KEY值映射到一个index上:hash(KEY) = index。这样就可以把一个KEY值同某个index对应起来。然后把与这个KEY值对应的VALUE存储到index所标记的存储空间中。这样,每次想要查找KEY所对应的VALUE值时,只需要做一次hash()运算就可以找到了。以上就是寻址过程。
    这里的hash函数为一个一致性哈希函数,假设存储空间地址可以以 0-2^32-1 表示,则该一致性函数即将key值hash成一个index值,index值即为空间地址,以此就可以按照index value进行存储和寻址。

  1. 密码存储保护:在文档加密和磁盘加密中,加密算法要求使用相同长度的密钥,要求将不同长度的密码转为相同长度,因此可以使用hash函数,先将passwd哈希为密钥,再以这一密钥进行文档的加密。
  2. 服务器端密码保护:在服务器端存储密码时,使用哈希的方式存储
  3. 数字签名