Categories
程式開發

安全系列之——主流Hash散列算法介绍和使用


每个人在这个社会上生存,都会有一个属于自己的标记,用于区分不同的个体。通常使用名字就可以了。但是一个名字也并不能完全表示一个人,因为重名的人很多。所以我们可以使用一个身份证号或者指纹来表示独一无二的一个人。

同样在互联网的世界,使用一个符号来表示一个独一无二的事物也很重要。比如我们下载一个文件,文件的下载过程中会经过很多网络服务器、路由器的中转,如何保证这个文件下载过程中没有丢包,被完整的下载下来了呢?我们不可能去检测这个文件的每个字节,也不能简单地利用文件名、文件大小这些极容易伪装的信息去判断。这时候,我们就需要一种指纹一样的标志来检查文件的可靠性,这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

安全系列之——主流Hash散列算法介绍和使用 1

比如从mysql官网下载mysql时,在软件包的右下角,都会有一个MD5算法算出来的hash值。这个hash值有什么用呢?其实这是给我们校验下载的软件包是否完整用的。当我们下载完成后,可以通过相关的手段,比如在linux系统中可以通过md5sum这个命令,计算我们下载的软件包的hash值,然后和官网给出的hash值进行比较,如果两个相等,就表示文件被完整的下载了。

所谓数据的完整性,指的是数据在网络传输中是否被篡改、是否丢包,发送方发出的数据和接收方接收的数据是一样的,就表明数据是完整的。如何评估数据的完整性?通常使用Hash散列函数。散列函数的主要任务是验证数据的完整性。通过散列函数计算得到的结果叫做散列值,这个散列值也常常被称为数据的指纹( Fingerprint)。

一、Hash散列算法介绍

概括来说,哈希(Hash)是将目标文本转换成具有相同长度的、不可逆的杂凑字符串(或叫做消息摘要)。

而加密(Encrypt)是将目标文本转换成具有不同长度的、可逆的密文。Hash算法严格上来说并不属于加密算法,而是与加密算法属于并列关系的一种算法。

有加密就有解密,而hash算法是不可逆,因此不能算加密算法。这里的不可逆既指不能根据转换后的结果逆转回原文,也指对于两个输入,即使其转换结果相同也不能说这两个输入就一定相同。因为,Hash算法的定义域是一个无限集合,但是值域确是一个有限集合,将一个无限集合映射到有限集合上,每个哈希结果都存在无数个可能的目标文本,因此哈希是一个多对一的映射,所以它也不存在逆映射。但是对于加密算法,它的结果往往取决于输入,其定义域和值域都是无限集合,明显是一个一一映射,对于一一映射,理论上都是可逆的。

常见的Hash算法有:MD5、SHA-1、HMAC、HMAC-MD5、HMAC-SHA1等

二、Hash散列算法的特征

一个优秀的散列算法有几个重要的特征:

1.固定长度。散列函数可以接受任意大小的数据,并输出固定长度的散列值。比如MD5这个hash函数为例,不管原始数据有多大,计算得到的hash散列值总是128比特。

>

2.雪崩效应。原始数据哪怕只有一个字节的修改,得到的hash值都会发生巨大的变化。

>

3.单向。只能从原始数据计算得到hash值,不能从hash值计算得到原始数据。所以散列算法不是加密解密算法,加密解密是可逆的,散列算法是不可逆的。

>

4.避免冲突。几乎不可能找到一个数据和当前计算的这个数据计算出一样的hash值,因此散列函数能够确保数据的唯一性。目前标准的MD5算法理论碰撞概率是2的128次方分之一。正是因为这种算法的碰撞概率很小,所以说我们在实际使用的过程之中才是可以无视这个数而直接使用MD5数据确定唯一性。

三、散列算法的使用

3.1文件传输

在文件传输时,散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。

这种场景,对hash碰撞的要求要低于计算的速度,因为文件较大时,计算的速度会更重要。

3.2消息摘要

在密码学中,hash算法的作用主要是用于消息摘要(Message Digest),它主要用于对整个消息的完整性进行校验。举个例子,我们登陆B站的时都需要输入密码,那么B站的数据库会保存明文的密码吗?如果会明文保存,B站的DBA肯定会看到每个人的密码是什么,很不安全;同时如果用户在注册登录时也是明文在网络上传输账号密码,这个信息也会被人恶意截取,都会有很多安全问题。

通常一个系统都不会明文存储用户的密码,一般,用户在注册的时候,密码在用户侧还未提交时,就会使用密码的明文计算一个hash值,然后传输到后端系统,并将密文记录到数据库中,用户登录时,在用户侧在使用相同的算法对密码计算一个hash值,传到后端后,将这个hash值和数据库中的hash值进行比较,如果相同就登录成功;这样就避免了在网络传输或公司的DBA泄露用户密码,而且密码始终是在用户侧,所以只要用户知道密码的明文是什么。

在这些应用场景里,对于抗碰撞和抗篡改能力要求较高,对速度的要求在其次。一个设计良好的hash算法,其抗碰撞能力是很高的。以MD5为例,其输出长度为128位,碰撞的概率是2的128次方分之一

3.3数据结构

在用到hash进行管理的数据结构中,就对速度比较重视,对抗碰撞不太看中,只要保证hash均匀分布就可以。比如Hashmap,hash值(key)存在的目的是加速键值对的查找,key的作用是为了将元素适当地放在各个桶里,对于抗碰撞的要求没有那么高。换句话说,hash出来的key,只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能,直接与hash值产生的速度有关,所以这时候的hash值的产生速度就尤为重要:

/**
* HashMap对象的hash()
*/
static final int hash(Object key) {
int h;
//计算hashCode,并无符号移动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
* Object对象的hashCode()
*/
public int hashCode() {
int h = hash;
//hash default value : 0
if (h == 0 && value.length > 0) {
//value : char storage
char val[] = value;
for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

很简洁的一个乘加迭代运算,在不少的hash算法中,使用的是异或+加法进行迭代。

四、Hash算法的使用

4.1.MD5算法

Message Digest Algorithm MD5(消息摘要算法5)为计算机安全领域广泛使用的一种散列函数,用以提供消息的完整性保护。是计算机广泛使用的杂凑算法之一,将数据(如汉字)运算为另一固定长度值,是杂凑算法的基础原理,MD5的前身有MD2、MD3和MD4。

MD5算法具有以下特点:

1、压缩性:任意长度的数据,算出的MD5值长度都是固定的。2、容易计算:从原数据计算出MD5值很容易。3、抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的MD5值都有很大区别。4、强抗碰撞:已知原数据和其MD5值,想找到一个具有相同MD5值的数据(即伪造数据)是非常困难的。

MD5应用场景:

1、一致性验证2、数字签名3、安全访问认证

MD5代码测试:

package com.wuxiaolong.EncrypteDecrypt;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
* Description:
*
* @author 诸葛小猿
* @date 2020-08-25
*/
public class MD5Test {

public static void main(String[] args) {

// 字符串的Md5
String content = "诸葛小猿";
String hashStr = md5(content);
System.out.println(content +" => "+ hashStr);

//文件的MD5
String filePath = "G:\FiddlerSetup.exe";
File file = new File(filePath);
String fileHash = md5(file);
System.out.println("file hash =>" + fileHash);
}

/**
* 计算字符串的MD5值
* @param string 明文
* @return 字符串的MD5值
*/
public static String md5(String string) {
if (string.isEmpty()) {
return "";
}
MessageDigest md5 = null;
try {
md5 = MessageDigest.getInstance("MD5");
byte[] bytes = md5.digest(string.getBytes("UTF-8"));
String result = "";
for (byte b : bytes) {
String temp = Integer.toHexString(b & 0xff);
if (temp.length() == 1) {
temp = "0" + temp;
}
result += temp;
}
return result;
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
return "";
}

/**
* 计算文件的MD5值
* @param file 文件File
* @return 文件的MD5值
*/
public static String md5(File file) {
if (file == null || !file.isFile() || !file.exists()) {
return "";
}
FileInputStream in = null;
String result = "";
byte buffer[] = new byte[0124];
int len;
try {
MessageDigest md5 = MessageDigest.getInstance("MD5");
in = new FileInputStream(file);
while ((len = in.read(buffer)) != -1) {
md5.update(buffer, 0, len);
}
byte[] bytes = md5.digest();

for (byte b : bytes) {
String temp = Integer.toHexString(b & 0xff);
if (temp.length() == 1) {
temp = "0" + temp;
}
result += temp;
}
} catch (Exception e) {
e.printStackTrace();
}finally {
if(null!=in){
try {
in.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return result;
}
}

运行结果:

诸葛小猿 => 591a998db81be040be8591d7e2c2ddc2
file hash =>8adb254960a54c08c4453775d10574ba

4.2.SHA1算法

安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64位的消息,SHA1会产生一个160位的消息摘要。当接收到消息的时候,这个消息摘要可以用来验证数据的完整性。在传输的过程中,数据很可能会发生变化,那么这时候就会产生不同的消息摘要。

SHA1算法原理:

首先进行SHA1分组:对于任意长度的明文,SHA1可以产生160位的摘要。对明文的分组处理过程如下:

1)对数据流尾部添加0x80标记。任意长度的明文首先需要添加位数,使明文总长度为448(mod512)位。将0x80字节追加到数据流尾部以后,源数据流的整个长度将会发生变化,考虑到还要添加64位(8个字节)的位长度,必须填充0 以使修改后的源数据流是64字节(512位)的倍数。在明文后添加位的方法是第一个添加位是1,其余都是0。2)然后将真正明文的长度(没有添加位以前的明文长度)以64位表示,附加于前面已添加过位的明文后,此时的明文长度正好是 512位的倍数。当明文长度大于2的64次方时,仅仅使用低64位比特填充,附加到最后一个分组的末尾。3)经过添加处理的明文,其长度正好为512位的整数倍,然后按512位的长度进行分组(block),可以划分成L份明文分组,我们用Y0,Y1,……,YL-1表示这些明文分组。4)Sha1默认数据流以big endian 方式存放。

分组之后,对所得到的若干分组反复重复处理。对每个明文分组的摘要生成过程如下:

1)将512位划分成16个子明文分组,每个子分组32位2)申请5个链接变量a、b、c、d、e,初始为H0、H1、H2、H3、H43)将16个子分组扩展为80份4)80个子分组进行4轮运算,得到新的a、b、c、d、e值5)新的链接变量与原始链接变量进行求和6)链接变量作为下一个明文分组的初始链接变量7)最后一个分组的5个链接变量就是SHA1摘要

SHA1有如下特性:

不可以从消息摘要中复原信息;两个不同的消息不会产生同样的消息摘要。

MD5代码测试:

计算SHA1值的Java代码与计算MD5值的代码基本相同,区别只在于

MessageDigest.getInstance("MD5"); //将"MD5"替换为"SHA1"。

可以将的上面计算MD5值的两个函数md5(String string)和hash(File file)进行简单的修改,将算法也作为参数传入,hash(String string, String algorithm)和hash(File file, String algorithm),就可以动态支持MD5和SHA1两种算法了。

4.3.MurmurHash算法

MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。 由Austin Appleby在2008年发明, 并出现了多个变种,都已经发布到了公有领域。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。其在Redis,Memcached,Cassandra,HBase,Lucene都使用了这种hash算法。所有很有必要说一下。

Redis在实现字典时用到了两种不同的哈希算法,MurmurHash便是其中一种(另一种是djb)。MurmurHash在Redis中应用十分广泛,包括数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。发明算法的作者被邀到google工作,该算法最新版本是MurmurHash3,基于MurmurHash2改进了一些小瑕疵,使得速度更快,实现了32位(低延时)、128位HashKey,尤其对大块的数据,具有较高的平衡性与低碰撞率。

与MD5这些讲究安全性的摘要算法比,MurmurHash并不关注安全性,比如在Redis内部只是为主键做个Hash而已,就不需要安全性了。因此MurmurHash是一种non-cryptographic的hash算法,比安全散列算法快几十倍。

在Java中,有很多地方都使用了MurmurHash,比如Guava包、Jedis包,Cassandra包中都有这种hash算法。

MurmurHash算法总结:高运算性能,低碰撞率。

package com.wuxiaolong.EncrypteDecrypt;

import com.google.common.base.Charsets;
import com.google.common.base.Stopwatch;
import com.google.common.collect.Sets;
import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import org.apache.commons.codec.digest.DigestUtils;

import java.nio.charset.StandardCharsets;
import java.util.Set;

/**
* Description:
* 需要jar:
*
* com.google.guava
* guava
* 23.0
*
*
* @author 诸葛小猿
* @date 2020-08-25
*/
public class MurmurHashTest {

public static void main(String[] args) {

int testCount = 100000;
String msg = "诸葛小猿";

long totalTime = 0L;

long start = System.currentTimeMillis();

// Hashing.murmur3_32(seed)
HashFunction murmur3 = Hashing.murmur3_32();

Set set = Sets.newHashSet();
for (int i = 0; i < testCount; i++) { // 计算每一次hash的耗时 Stopwatch w = Stopwatch.createStarted(); HashCode murmur3HashCode = murmur3.hashString(msg + i, Charsets.UTF_8); String murmur3HashCodeStr = murmur3HashCode.toString(); System.out.println(String.format("murmur3's hashCode:%s,length:%s,it consumes:%s", murmur3HashCodeStr, murmur3HashCodeStr.length(), w)); set.add(murmur3HashCodeStr); } long end = System.currentTimeMillis(); totalTime = end - start; System.out.println("set的元素个数" + set.size()); System.out.println("总耗时" + totalTime); } }

部分运行结果:

murmur3's hashCode:a2e96039,length:8,it consumes:2.500 μs
murmur3's hashCode:12c86afb,length:8,it consumes:2.400 μs
murmur3's hashCode:ad6ff257,length:8,it consumes:1.200 μs
murmur3's hashCode:b71c537d,length:8,it consumes:1.200 μs
murmur3's hashCode:92508a73,length:8,it consumes:1.100 μs
set的元素个数99998
总耗时984

这里运行了100000次,但是Set中去重后只有99998个元素,可以使用Hashing.murmur3_32(seed)的seed降低元素的重复。

MurmurHash的应用除了上面说的redis,在很多时候都可以应用到,比如短连接服务生成短连接、BloomFilter都可以使用。

五、Hash算法的安全性

MD5、SHA1等hash算法作为一种不可逆算法,一定程度上保证了密码的安全性,但是MD5等hash算法真的是完全安全的吗,其实不然。

从概率来说,2的128次方遍历后至少出现两个相同的MD5值,但是2的128次方有多大?3402823669209384634633746074317.7亿,就算全世界最快的超级计算机也要跑几十亿年才能跑完。可是,王小云院士破解了MD5。这里所说的破解,并不是给王小云院士一个MD5散列值,然后她就能通过计算还原出原文来。从密文推算出明文理论上是不可能的,所以王小云的研究成果不能通过 MD5 的散列值逆向推算出明文。王小云的研究成果是给定消息 M1,能够计算获取 M2,使得 M2 产生的散列值与 M1 产生的散列值相同。这样,MD5 的抗碰撞性就不满足了,使得 MD5 不再是安全的散列算法。从而导致MD5 用于数字签名将存在严重问题,因为可以篡改原始消息,而生成相同的 Hash 值。因此,业界专家普林斯顿计算机教授Edward Felten等强烈呼吁信息体系的设计者赶快更换签名算法,而且他们侧重这是一个需要当即处理的问题。

同时美国国家技能与规范局(NIST)于2004年8月24日宣布专门谈论,谈论的首要内容为:“在近来的世界暗码学会议(Crypto 2004)上,研究人员宣布他们发现了破解数种HASH算法的办法,其间包含MD4,MD5,HAVAL-128,RIPEMD还有 SHA-0。剖析标明,于1994年代替SHA-0成为联邦信息处理规范的SHA-1的削弱条件的变种算法能够被破解;但完好的SHA-1并没有被破解,也没有找到SHA-1的碰撞。研究结果阐明SHA-1的安全性暂时没有问题,但随着技能的发展,技能与规范局计划在2010年之前逐步筛选SHA-1,换用别的更长更安全的算法(如SHA-224、SHA-256、SHA-384和SHA-512)来代替。”

所以从这里也可以看出,单步的hash算法还是存在很大的漏洞,容易被碰撞。那么该如何进一步的加强hash算法的安全性呢,可以使用如下的办法:

5.1.hash+盐(salt)

salt可以简单的理解成:随机产生的一定长度的,可以和密码相结合,从而使hash算法产生不同结果的字符串。也就相当于你的新密码 = 旧密码 + 随机的盐值,然后对新密码进行hash。

优点:这种方法会极大防止受到彩虹表的攻击,因为即便攻击者构造出彩虹表,因为你使用了 hash(密码+ salt),攻击者彩虹表里的哈希值hash(密码)和你数据库中的哈希值是不同的。

5.2.增加计算的时间(哈希+salt+Iteration)

通过迭代计算的方式增加计算密码的成本。迭代的周期控制在用户可以接受范围内,这样攻击者的计算和时间成本就会大大增加。

一般到此时,hash结果就比较安全了。但是如果还需要更加地安全,可以继续对这种方法计算出来的hash值使用加密算法加密。

参考文章:

https://blog.csdn.net/qq_33408113/article/details/82635009

https://www.oschina.net/translate/state-of-hash-functions

https://blog.csdn.net/qq_24280381/article/details/72024860

https://blog.csdn.net/weiliangliang111/article/details/51457874

关注公众号,输入“java-summary”即可获得源码。

完成,收工!

安全系列之——主流Hash散列算法介绍和使用 2

【传播知识,共享价值】,感谢小伙伴们的关注和支持,我是【诸葛小猿】,一个彷徨中奋斗的互联网民工。

安全系列之——主流Hash散列算法介绍和使用 3