Java HashMap 碰撞攻击

Question

我的目标是用几个字符串（大约 10000 或更多）来攻击 Java 的 HashMap，它们会产生相同的散列。我使用了这个link, translated it to Python3 (so that I can produce the strings on my terminal itself) and ran on my machine to produce around 177147 strings. All these strings produce the same hash when String.hashCode() method is called. From this link上的脚本，显然如果对HashMap进行随机读写，时间复杂度是O(N*N)。如果 N 很大（在本例中，N 大于 10000），则需要更多时间。但出人意料的是，不到2s就变成了运行。我希望它花费超过 10 秒。以下是我正在使用的脚本。

# Python3 script to generate strings that produce
# same hash with Java's String.hashCode() method
def combs(n,arr,str,arr_rtn):
    if n==1:
        for j in range(3):
            arr_rtn[str + arr[j]] = 0
    else:
        for j in range(3):
            combs(n-1,arr,str+arr[j],arr_rtn)

arr_src = ['at','bU','c6']
str_tmp = ''
arr_rtn = dict()

t = combs(11,arr_src,str_tmp,arr_rtn)

keys = list(arr_rtn.keys())

print(len(keys))
print(*keys, sep = '\n')

// Java code to insert the generated
// strings into HashMap
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            map.put(s, s.hashCode());
            // Should take more time since all strings 
            // hash to same value
        }
        System.out.println(map.size());
        sc.close();
    }
}

我唯一的目标是用产生相同散列的字符串攻击 HashMap，以便执行时间超过 20 秒（至少）。

Answer 1

实际上，Java 的 HashMap 通过将多个值映射到链表中的同一存储桶来处理冲突。因此，在 Java HashMap 中搜索的最坏情况性能是 O(N)，其中 N 是映射中的元素数。

实际上，在 Java 的更新版本中，HashMap 通过将所有相同的桶元素放在树中来处理冲突。这意味着最坏情况下的搜索性能变为 O(h)，其中 h 是树的高度。

Answer 2

正如Tim所说，从Java8开始，HashMap将用平衡二叉树取代简单的链表hashchain。发生这种情况：

当链的长度超过硬连线阈值时（Java 8 中的 8），并且
当数组超过另一个硬连线阈值（Java 8 中的 64）时。

如果键 class 实现了 Comparable<?>（就像 String 那样），那么 compareTo 方法用于树排序。

这意味着 HashMap<String> 和 N 字符串键被设计为发生冲突的最坏情况将是 O(logN) 而不是 O(N)。

简而言之，针对 HashMap 的碰撞攻击在 Java 8 或更高版本中将无效。（但是您可以运行对 Java 7 或更早版本进行测试攻击。）

如果您需要有关 HashMap 的列表与树的工作原理的更多信息，源代码中有大量注释。找到与您感兴趣的版本匹配的源代码...并阅读它。

请注意，您作为信息来源引用的问题 (java HashMap collision) 是在 2013 年提出并回答的。Java 8 于 2014 年 3 月发布。

Java HashMap 碰撞攻击

Java HashMap Collision attack

python

java

hashmap