SHA-1:大坨变小坨的神秘哈希算法

小韩同学上安全与认证课时听懵了,尤其是logical functions那块的操作,什么乱七八糟的玩意儿啊??于是课后自己调研一下写一篇笔记。
本文参考了IETF RFC3174, FIPS PUB 180-4两篇官方文档,以及两个Youtube上的tutorials,credit见文末。

BACKGROUND

SHA is a abbreviation of Secure Hash Algorithm originally designed by NIST & NSA in 1993, which was then revised in 1995 as SHA-1. It’s commonly used in applications related to Cryptography and Data Integrity in early years, and afterwards replaced by later versions (i.e. SHA-2 or SHA-3) due to security concerns.

I/O

Input: it takes binary input of any size.
Output: it produces a message digest of 160-bit hash value (20-byte, or 40-digit in hex).

HOW

The processing consists of:

  1. append padding bits
  2. append length
  3. MD buffter, where MD represents Message Digest
  4. process message in 512-bit blocks
  5. output: 160 bits
PRE-PROCESSING

1.Padding the Message
The purpose of this padding is to ensure that the padded message is a multiple of 512 or 1024 bits, depending on the algorithm. –>只有补位变成合适的长度才可以放进“容器”进行运算。

对于任意长度的明文,SHA1首先对其进行分组,使得每一组的长度为512位,然后对这些明文分组反复重复处理。对于最后一组明文,往往长度小于512位,所以我们要补齐到512位才能做运算。由于明文的最后64位要预留来记录总长度,所以对于剩下的部分(原文和长度位的中间部分),我们在最左边补一个1,其余位补0。上课的时候老师没说最后64位的问题,但看课件上的图在100…0之后还有一小段粉红色,其实就是那64位长度位。

2.Parsing the Message
The message and its padding must be parsed into N 32-bit blocks.

对于每一份512-bit的明文,划分为16个子明文分组M[0…16],每个子明文分组为32位。毕竟要用的是32位的寄存器嘛。

3.Setting the Initial Hash Value H(0)
Before hash computation begins for each of the secure hash algorithms, the initial hash value, H(0), must be set.

因为哈希算法都是头尾相接的,上一轮的结果要参与下一轮的运算,然而在做第一轮运算时我们并没有previous results,因为定义初始变量组。

ALGORITHMS, PROCESSINGS


1.Sub-block, Words
我们一共要进行80轮运算,意味着我们可能需要80组明文,而在一开始我们只分出了16组明文M[0…15],所以我们在这一步要把16组明文扩充成80组。
在运算中我们使用5个变量a, b, c, d, e,都是由5个寄存器A,B,C,D,E,运算所得。
扩充过程如下:80组中的前16组直接用M[0…15]代替,后边第17到80组调用Wt函数计算。

1
2
3
4
5
6
7
扩充过程
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

2.80 Steps

生成好80组明文之后,我们就可以应用到后续的80次操作啦,这乱七八糟的运算过程真是让我不禁感谢伟大计算机…运算过程看得我眼花缭乱,所幸这种没有多大意义的过程压根不需要记住,连自己动手算一下都不用…
我上课的时候就非常懵逼,我不懂80个32位明文怎么放进5个32位寄存器啊???调研的时候才发现,那80个明文是为了80次运算准备的,每次运算A,B,C,D,E这一组寄存器依据算法只调用1个32位的明文。

3.Compute the intermediate, referring the first slide above.

做完80次运算之后,我们还要把结果和初始变量组(或者上一轮的结果)做“+”运算。

4.Final hash value

做完第三步之后,我们刚刚处理完第一个512-bit明文,我们还要继续处理接下来的N个512-bit明文,当最后一个512-bit明文处理完之后,就得到了最后5✖32位的结果。

WHY

1.Every bit of hash code is a function of every bit of the input.
只有所有输入位都参与了运算,且所有输出位都由运算得出的情况下,才能实现任何改动都会导致不同输出。
2.It is unlikely that two messages chosen at random will have the same hash code.
3.It is infeasible to produce two different messages having the same message digest.
后两条就是保证collision resistance, preimage resistance and second preimage resistance。