Рейтинг:0

Есть ли риск того, что некоторые выражения в хэш-функции могут быть обращены?

флаг au

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

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

Вывод приложения:

 Хэш: 817621565b0d4457402862cee209f1ab139bbd8caf2dc72ec172d4d90429c409
 
Список ключей (3)
 --------------------------------------------- ------------------------
  1 ключ: 37639fed3f5c6b60c38a1aeb3589f3176e2b965d75b6a1214ec96b34ddebe005
  2 Ключ: e23aab653bfe6aa1591496d880687ef17624366a6db9a4159e1bd4dfa879aad9
  3 Ключ: 249d8cca4a00491c20af4cb0ba8d273518162e6ebddbfc2e243355fbfa179089
 --------------------------------------------- ------------------------

Тестовый код:

#include <stdio.h>
#include <stdlib.h>


#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define ROTBYTE(x, y) (((x) << (y)) | ((x) >> ((8) - (y))))



//Алгоритм хеширования
int Prs(unsigned char * input,int input_len,unsigned char *output,int output_len) {
    инт я;

    unsigned char pn[32] = {113 232 143 101, 58, 79 137, 10 145, 88 110, 97 203, 35 241 171,
                            221 156, 88, 39 122, 91 105 145 253 103 165, 26 197, 96, 74 131};

    for(i=0; i<output_len; i++) {
        вывод[i]=pn[i%32]^ROTBYTE(вход[i%input_len],2)^ROTBYTE(вход[(i+1)%input_len],3);
        вывод [i] ^ = MAJ (ввод [(i)% input_len], ввод [(i + 1)% input_len], ввод [(i + 2)% input_len]);
    }

    вернуть 0;
}


int HexToBin (символ без знака m, символ без знака l, символ без знака * r) {
    беззнаковый символ v;
    если (m>='a' && m<='f') {
        v=(m-'a'+10)<<4;
    }else if(m>='A' && m<='F') {
        v=(m-'A'+10)<<4;
    } иначе если(m>='0' && m<='9') {
        v=(m-'0')<<4;
    }еще{
        вернуть 1;
    }

    если(l>='a' && l<='f') {
        v|=(l-'a'+10);
    } иначе если(l>='A' && l<='F') {
        v|=(l-'A'+10);
    } иначе если(l>='0' && l<='9') {
        v|=(l-'0');
    }еще{
        вернуть 1;
    }
    *г=в;
    вернуть 0;
}


int HexToBinArray (беззнаковый символ * src, int len, беззнаковый символ * выход) {
    инт я;
    for(i=0; i<len; i++) {
        if(HexToBin(src[i*2],src[i*2+1],&out[i])){
            вернуть 1;
        }
    }
    вернуть 0;
}


int BinToHex (беззнаковый символ b) {
    на телевидении;
    если((b>>4)>=10) {
        v=((b>>4)+'a'-10)<<8;
    } еще {
        v=((b>>4)+'0')<<8;
    }

    если((b&15)>=10) {
        v|=((b&15)+'a'-10);
    } еще {
        v|=((b&15)+'0');
    }

    вернуть v;

}


void BinToHexArray(unsigned char * in,int len,unsigned char *out) {
    инт я;
    на телевидении;
    for(i=0; i<len; i++) {
        v=BinToHex(in[i]);
        выход[i*2]=v>>8;
        выход[i*2+1]=v&0xff;
    }
    выход[я*2]=0;
    возвращаться;
}


интервал Slen(char *s){
    диаграмма;
    т=с;
    пока(*с)
        с++;
    возврат с-т;
}


интервал основной () {
    интервал input_len=32;
    интервал_вывода_len=32;
    беззнаковый символьный ключ[32];
    беззнаковый символьный хэш[32];
    символ без знака buf[1024];
    инт слен;



    в то время как (1) {
            делать{
                printf("\n\n\n");
                printf(" -------8-------16------24------32------40------48--- ---56------64\n");
                printf(" | | | | | | | | \n");
                printf("Ключ:");
                scanf("%s",buf);
                slen = Slen (баф);
                если(slen!=input_len*2){
                    printf(" Длина ключа должна состоять из %d шестнадцатеричных цифр.",input_len*2);
                }
            } while(slen!=input_len*2);

        // Преобразование шестнадцатеричной строки в двоичную
        если (HexToBinArray (buf, input_len, ключ)) {
            printf(" Иностранный символ в шестнадцатеричном числе. \n");
            Продолжить;
        }

        //Алгоритм хеширования
        Prs (ключ, input_len, хэш, output_len);

        // Преобразование двоичного кода в шестнадцатеричную строку
        BinToHexArray (хеш, input_len, buf);
        printf(" Хэш: %s\n",buf);
    }


    вернуть 0;
}

Тестовый код написан только для проверки правильности вывода приложения, в коде алгоритм хеширования находится внутри функции "Prs", остальные функции необходимы для работы кода, но они не важны. Вычисляет хэш-код 32-байтовых значений ключей, записанных в бесконечном цикле, когда код компилируется и выполняется. Когда вышеуказанные ключи проверяются, нахождение одного и того же хеш-значения для каждого ключа доказывает, что выражение в функции «Prs» перевернуто.

fgrieu avatar
флаг ng
Мы не очень заботимся о коде (особенно когда добрая половина его выполняет преобразование из/в шестнадцатеричный код и дублирует функциональность strlen с ограничением длины, подходящей для int). Скорее, пожалуйста, объясните алгоритм, который использует ваш код, оставив в стороне детали преобразования и сосредоточившись на том, что является криптографическим.
Рейтинг:5
флаг my

Это приложение показывает, что некоторые выражения в алгоритме могут быть обращены"

На самом деле известно, что подавляющее большинство кода в SHA-2, SHA-3 можно реверсировать.

Функция сжатия хэша SHA-2 $h(s,m) = s + f_m(s)$, куда $f_m(s)$ обратим для фиксированного блока сообщений $м$ [1][2] - то есть если знать что $м$ и что вы хотите значение $f_m(s)$ быть, легко найти начальное состояние $s$ который достигает этого значения. Хеш-функция учитывает это, включая $+$ операция, которая необратима (поскольку обе стороны зависят от предыдущего состояния $s$, следовательно, злоумышленник не может отменить операцию полного сжатия хэша).

С SHA-3 вся перестановка состояний обратима. То есть, если вы знаете 1600-битное целевое состояние, легко вычислить предыдущее состояние, которое перейдет в это состояние. Хеш-функция учитывает это, удваивая размер «емкости» (часть внутреннего состояния, которую атакующий не может контролировать напрямую); это означает, что атаки типа «встреча посередине» против прообраза не проще, чем простые атаки грубой силы.

Ни один из них не приводит к известной уязвимости.


[1]: Функция сжатия хэша различается между SHA-256 и SHA-512, однако это утверждение верно для обоих.

[2]: операция сложения $+$ на самом деле является поэлементным модульным сложением вектора 32-битных или 64-битных значений.

Myria avatar
флаг in
На самом деле обратимость функции сжатия SHA-1/256/512 может использоваться как блочный шифр. Это использование известно как «ШАКАЛ». Однако он не используется обычно; другие блочные шифры лучше и предназначены для этой цели. (пончо, конечно, это знает; я просто включаю для читателей)

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.