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

关注
发布于: 2020 年 08 月 25 日
每个人在这个社会上生存，都会有一个属于自己的标记，用于区分不同的个体。通常使用名字就可以了。但是一个名字也并不能完全表示一个人，因为重名的人很多。所以我们可以使用一个身份证号或者指纹来表示独一无二的一个人。
﻿
同样在互联网的世界，使用一个符号来表示一个独一无二的事物也很重要。比如我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件下载过程中没有丢包，被完整的下载下来了呢？我们不可能去检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息去判断。这时候，我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。
﻿
﻿
比如从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、H4
3）将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:
 *         <dependency>
 *             <groupId>com.google.guava</groupId>
 *             <artifactId>guava</artifactId>
 *             <version>23.0</version>
 *         </dependency>
 *
 * @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<String> 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”即可获得源码。
﻿
完成，收工！
﻿
【传播知识，共享价值】，感谢小伙伴们的关注和支持，我是【诸葛小猿】，一个彷徨中奋斗的互联网民工。
﻿
﻿