РЕДАКТИРОВАТЬ , кстати, пункт обходного пути состоит в том, чтобы повторно использовать все существующие HashMap (например, ConcurrentHashMap и т. Д.) Вместо того, чтобы полностью изобретать колесо. Языки с использованием рандомизированных хеш-функций (например, Perl) защищены от этой атаки.
В свете недавнего и разрушительного DDoS, использующего известный недостаток в нескольких реализациях hashmap (как известно, затрагивают веб-серверы Java, но также PHP и другие), Apache Tomcat только что вышел с «исправлением» в виде патча, позволяющего колпачок по максимально разрешенному числу параметров в запросе POST (исправить ваш Tomcat до 6.0.35+ или 7.0.23+ кстати).
(D) DoS, по-видимому, в основном использует тот факт, что строки могут создаваться так, что они сталкиваются при хэшировании и что многие веб-серверы «глупо» ставят параметры ключа / значения в (разбитые) хэш-карты.
Мне было интересно, можно ли написать декоратор вокруг HashMap {String, String}, чтобы каждая строка добавила в String случайное (случайное с точки зрения атакованного) значение, например:
... get( String s ) { return wrappedBrokenMap.get( s + crunch(s ); } ... put( String key, String value ) { wrappedBrokenMap.put( s + crunch(s), value ); } И здесь будет одна реализация хруста (…) (это всего лишь пример, дело в том, что злоумышленник не знает реализации):
private static final int MY_MAGICAL_NUMBER = 0x42BABE; // attacker doesn't know that number private static String crunch( String s ) { return s.length + "" + MY_MAGICAL_NUMBER; }
Если для любого хруста String s возвращается воспроизводимая строка, которую злоумышленник не может угадать, атака DDoS эффективно предотвращена правильно?
Будет ли это работать?
Если для любого хруста String s возвращается воспроизводимая строка, которую злоумышленник не может угадать, атака DDoS эффективно предотвращена правильно?
В основном, это то, что вы делаете, когда вы соедините хэши паролей (хотя и по разным причинам). Он не предотвращает атаки на столкновение полностью (если у вас есть функция хэширования, отображающая вход произвольной длины для вывода фиксированной длины, хеши могут всегда сталкиваться), но использование секретной соли должно сделать такие атаки сложнее.
Операция quick'n'dirty может выглядеть примерно так:
public class SaltedHashMap<V> { private final Map<String, V> map = new HashMap<>(); private final String salt; public SaltedHashMap(String salt) { this.salt = salt; } public V get(String key){ return map.get(key + salt); } public void put(String key, V value) { map.put(key + salt, value); } }
Используя веб-сервер в качестве примера, мы могли бы использовать SecureRandom для рандомизации новой соли для каждого входящего запроса, а это означает, что даже если вам удалось определить вход для генерирования коллизий для одного запроса, было бы крайне маловероятно работать для других Запросы.
Я думаю, что к моменту, когда он дойдет до вашего кода (где вы можете сделать вышеуказанные изменения), хеширование уже было выполнено с помощью базовых библиотек, которые обрабатывают запрос POST. Итак, нет, я не думаю, что это сработает.
Чтобы гарантировать, что изменение является глобальным, я бы создал исправленную строку, подобную методу, подобному этому
// from java.lang.String public int hashCode() { int h = hash; if (h == 0 && count > 0) { h = MY_STARTING_VALUE; int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = MY_PRIME*h + val[off++]; } hash = h; } return h; }
Проблема заключается в том, что некоторые библиотеки полагаются на реализацию hashCode как особый способ. Если вы не используете такую библиотеку, это гарантирует, что каждая часть кода с использованием строк будет исправлена.
Проблема использования «раздавливания» или семян заключается в том, что вам необходимо знать его значение для выполнения поиска в первую очередь. Если вы используете случайное значение, вы должны опросить все возможные ключи, чтобы получить значение, которое не кажется очень эффективным.
Если вас беспокоит худшая производительность, вы можете использовать TreeMap. Типичная и худшая производительность – это O (log n) для выполнения вставки / поиска.
Если вы действительно беспокоитесь об этом, вы можете использовать класс String со своим собственным hashCode () или вы можете переопределить встроенный hashCode для String или значение, используемое HashMap.
Альтернативная хеш-функция String, добавленная в 7u6, была удалена из JDK 8 вместе со свойством jdk.map.althashing.threshold. Вместо этого хэш-буферы, содержащие большое количество сталкивающихся ключей, улучшают производительность, сохраняя свои записи в сбалансированном дереве вместо связанного списка. Это изменение JDK 8 относится только к HashMap, LinkedHashMap и ConcurrentHashMap.
См. https://docs.oracle.com/javase/8/docs/technotes/guides/collections/changes8.html.