Увеличение вероятности нахождения хеш-столкновения - PullRequest
Новая
       24

Увеличение вероятности нахождения хеш-столкновения

0 голосов
/ 22 мая 2019

Я пытаюсь найти коллизию хешей моей модифицированной хеш-функции.Предполагая, что мой модифицированный хеш выводит только первые 36 бит SHA-1.Как мы знаем, SHA-1 является 160-битным хеш-значением, поэтому для сравнения нам нужно вывести только 9 символов из 40 символов.

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

Во-первых, я бы жестко кодировал строку 2 и извлекал 9 символов из 40 символов, поскольку мне требуются только первые 36 бит SHA-1.Приведенная ниже функция в основном возвращает true, если столкновение найдено, и false, если столкновение не найдено. 

public static boolean findCollision(int x1, int x2) {

    String message1 = "I tried " + x1 + " iteration to find a collision";
    String message2 = "I tried " + x2 + " iteration to find a collision";       


    //hashing my string and extracting 9 characters
    String message_hash1 = sha1(message1);
    String message_hash2 = sha1(message2);

    String modified_hash1 = message_hash1.substring(0, 9);
    String modified_hash2 = message_hash2.substring(0, 9);

    if (modified_hash1.equals(modified_hash2))  
        return true; 
    else 
        return false;
}

Наконец, у меня будет основная функция, которая будет случайным образом целочисленные значения вплоть до MAX_VALUE в бесконечном цикле и будетпрерывать, если и только если найден хеш. 

public static void main(String[] args) {

    Random random = new Random();
    int x1 = 0;
    int x2 = 0;
    int counter = 0;

    while (true) {

        while(true){

            x1 = random.nextInt(Integer.MAX_VALUE);
            x2 = random.nextInt(Integer.MAX_VALUE);

            if (x1 != x2) 
                break;  
        } 

        if (findCollision(x1, x2) == true) {
            break;
        }
        counter++;
    }

    System.out.println("\nNumber of trials: " + counter);
}

Если бы я попытался взять только первые 24 бита SHA-1, я мог бы легко найти столкновение.Тем не менее, я не могу найти коллизию для 36 битов, несмотря на то, что запускаю ее часами.Следовательно, мне интересно, как еще можно найти способ столкновения всего с 36 битами SHA-1.

1 Ответ

1 голос
/ 24 мая 2019

https://stackoverflow.com/users/1081110/dawood-ibn-kareem правильно, что оптимальный метод - запоминать предыдущие хэши и проверять их, если это целесообразно, т.е. помещается в память, и примерно 2 ^ 18 значений, необходимых для столкновения 36 бит, делают вписаться в память, хотя только немного больше (около 50 бит) не будет.

Этот код находит 8 столкновений ниже 2 ^ 20 (первое чуть меньше 2 ^ 18, как и ожидалось) примерно за секунду: 

    static void SO56263762TruncCollision (String[] args) throws Exception {
        int[][] known = new int[1<<24][];
        MessageDigest sha1 = MessageDigest.getInstance("SHA1");
        for( int i = 0; i < (1<<20); i++ ){
            byte[] raw = sha1.digest(("I tried "+i+" iterations to find a collision").getBytes());
            int key = 0; for( int j = 0; j < 3; j++ ) key = key<<8 | (raw[j]&0xFF);
            char[] val = new char[9]; for( int j = 0; j < 9; j++ ) val[j] = Character.forDigit(j%2==0? (raw[j/2]>>4)&0xF: raw[j/2]&0xF, 16);
            int[] test = known[key]; 
            if( test == null ){ (known[key] = new int[1])[0] = i; }
            else{ 
                for( int k = 0; k < test.length; k++ ){
                    byte[] raw2 = sha1.digest(("I tried "+test[k]+" iterations to find a collision").getBytes());
                    char[] val2 = new char[9]; for( int j = 0; j < 9; j++ ) val2[j] = Character.forDigit(j%2==0? (raw2[j/2]>>4)&0xF: raw2[j/2]&0xF, 16);
                    if( Arrays.equals(val, val2)) System.out.println ("found "+i+" and "+test[k]);
                }
                (known[key] = Arrays.copyOf(test, test.length+1))[test.length] = i;
            }
        }
        System.out.println ("Memory="+(Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory()) );
    }
...