Отделка HashMap добавления случайности, чтобы предотвратить (D) DoS

Question

РЕДАКТИРОВАТЬпо тому, как точка обходной путь здесь, чтобы повторно использовать все существующие HashMap (как ConcurrentHashMap и т.д.) вместо того, чтобы заново изобретать полностью колесо. Языки с использованием рандомизированных хеш-функций (например, Perl) защищены от этой атаки.

В свете недавнего и разрушительного DDoS, использующего известный недостаток в нескольких реализациях hashmap (известный как веб-серверы Java, но также PHP и другие), Apache Tomcat только что вышел с «исправлением» в форме патч, позволяющий установить ограничение на максимально допустимое количество параметров в запросе POST (исправить ваш Tomcat до версии 6.0.35+ или 7.0.23+ кстати).

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; 
} 

Если для любой строки s crunch (s) возвращает воспроизводимую строку, которую злоумышленник не может догадаться, эффективно предотвращена атака DDoS?

Будет ли это работать?

Answer 1

Если для любой строки, сек хруста (ов) возвращает воспроизводимая строку, злоумышленник не сможет догадаться, атака 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 для рандомизации новой соли для каждого входящего запроса, а это означает, что даже если вам удалось определить вход для генерирования коллизий для одного запроса, было бы крайне маловероятно работать для других запросов.

Answer 2

Я думаю, что к моменту, когда он дойдет до вашего кода (где вы могли бы сделать вышеуказанные изменения), хеширование уже было выполнено базовыми библиотеками, которые обрабатывают запрос POST. Итак, нет, я не думаю, что это сработает.

Answer 3

Чтобы гарантировать изменение является глобальным, я хотел бы создать исправленную строку, как с помощью метода, как этого

// 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; 
} 

Проблемы с этим состоит в том, что некоторые библиотеки полагаются на реализации хэш-код является определенным образом. Если вы не используете такую ​​библиотеку, это гарантирует, что каждая часть кода с использованием строк будет исправлена.

---

Проблема с помощью «раздавить» или семя является то, что вам нужно знать его значение для выполнения поиска в первую очередь. Если вы используете случайное значение, вы должны опросить все возможные ключи, чтобы получить значение, которое не кажется очень эффективным.

Если вы беспокоитесь о худшем случае, вы можете использовать TreeMap. Типичная и худшая производительность - это O (log n) для выполнения вставки/поиска.

---

Если вы действительно обеспокоены этим, вы можете использовать класс String, с собственной хэш-код(), или вы можете переопределить встроенный в хэш-код для строки или значения, используемого HashMap.

Answer 4

Альтернативная функция хеша строки, добавленная в 7u6, была удалена из JDK 8 вместе со свойством jdk.map.althashing.threshold. Вместо этого хэш-буферы, содержащие большое количество сталкивающихся ключей, улучшают производительность, сохраняя свои записи в сбалансированном дереве вместо связанного списка. Это изменение JDK 8 относится только к HashMap, LinkedHashMap и ConcurrentHashMap.

Пожалуйста, обратитесь: https://docs.oracle.com/javase/8/docs/technotes/guides/collections/changes8.html