Украшение HashMap добавление случайности, чтобы предотвратить (D) DoS - PullRequest
Новая
       12

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

3 голосов
/ 29 декабря 2011

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

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

(D) DoS, по-видимому, в основном использует тот факт, что строки могут быть обработаны таким образом, что они сталкиваются при хешировании, и что многие веб-серверы "тупо" помещают параметры ключ / значение в (битые) хеш-карты.

Мне было интересно, можно ли написать декоратор вокруг HashMap {String, String}, чтобы к каждой строке добавлялось случайное (случайное с точки зрения атакуемого) значение в строку, например это: 

... get( String s ) {
    return wrappedBrokenMap.get( s + crunch(s );
}

... put( String key, String value ) {


  wrappedBrokenMap.put( s + crunch(s), value );
}

А вот одна из реализаций crunch (...) (это просто пример, смысл в том, что злоумышленник не знает реализацию): 

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 была эффективно предотвращена, верно?

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

Ответы [ 4 ]

3 голосов
/ 29 декабря 2011

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

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

Быстрая и грязная реализация может выглядеть примерно так: 

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

1 голос
/ 07 марта 2016

Альтернативная хеш-функция 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

0 голосов
/ 29 декабря 2011

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

// 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.

0 голосов
/ 29 декабря 2011

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

...