Există riscul ca unele dintre expresiile din funcția hash să poată fi inversate?

Am dezvoltat o aplicație care inversează unele expresii folosite în algoritmii hash. Aplicația nu inversează întregul algoritm, dar inversează unele părți. Această aplicație dezvăluie că unele expresii din algoritm pot fi inversate. Reprezintă acest lucru un risc pentru algoritmii hash care folosesc expresii similare?

Mai jos este rezultatul aplicației și codul de testare al unei expresii formate din expresii utilizate frecvent în algoritmii hash. Se va vedea că fiecare cheie dă aceeași valoare hash atunci când este testată.Pentru toate expresiile de această complexitate (numai operațiuni pe biți), aplicația poate lista toate cheile posibile pentru fiecare valoare hash.

Ieșire aplicație:

 Hash : 817621565b0d4457402862cee209f1ab139bbd8caf2dc72ec172d4d90429c409
 
Lista cheilor (3)
 --------------------------------------------- ------------------------
  1 cheie: 37639fed3f5c6b60c38a1aeb3589f3176e2b965d75b6a1214ec96b34ddebe005
  2 Cheie: e23aab653bfe6aa1591496d880687ef17624366a6db9a4159e1bd4dfa879aad9
  3 Cheie: 249d8cca4a00491c20af4cb0ba8d273518162e6ebddbfc2e243355fbfa179089
 --------------------------------------------- ------------------------

Cod de testare:

#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))))



//Algoritm hash
int Prs(unsigned char * input,int input_len,unsigned char *output,int output_len) {
    int i;

    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++) {
        output[i]=pn[i%32]^ROTBYTE(input[i%input_len],2)^ROTBYTE(input[(i+1)%input_len],3);
        output[i]^=MAJ(input[(i)%input_len],input[(i+1)%input_len],input[(i+2)%input_len]);
    }

    întoarce 0;
}


int HexToBin(unsigned char m, unsigned char l, unsigned char * r) {
    nesemnat char v;
    if(m>='a' && m<='f') {
        v=(m-'a'+10)<<4;
    }altfel dacă(m>='A' && m<='F') {
        v=(m-'A'+10)<<4;
    } else if(m>='0' && m<='9') {
        v=(m-'0')<<4;
    }altfel{
        întoarcere 1;
    }

    if(l>='a' && l<='f') {
        v|=(l-'a'+10);
    } else if(l>='A' && l<='F') {
        v|=(l-'A'+10);
    } else if(l>='0' && l<='9') {
        v|=(l-'0');
    }altfel{
        întoarcere 1;
    }
    *r=v;
    întoarce 0;
}


int HexToBinArray(unsigned char * src, int len, unsigned char *out) {
    int i;
    for(i=0; i<len; i++) {
        if(HexToBin(src[i*2],src[i*2+1],&out[i])){
            întoarcere 1;
        }
    }
    întoarce 0;
}


int BinToHex(unsigned char b) {
    în televizor;
    dacă((b>>4)>=10) {
        v=((b>>4)+'a'-10)<<8;
    } altfel {
        v=((b>>4)+'0')<<8;
    }

    dacă((b&15)>=10) {
        v|=((b&15)+'a'-10);
    } altfel {
        v|=((b&15)+'0');
    }

    întoarcere v;

}


void BinToHexArray(unsigned char * in, int len, unsigned char *out) {
    int i;
    în televizor;
    for(i=0; i<len; i++) {
        v=BinToHex(în[i]);
        out[i*2]=v>>8;
        out[i*2+1]=v&0xff;
    }
    out[i*2]=0;
    întoarcere;
}


int Slen(car *s){
    char *t;
    t=s;
    în timp ce(*s)
        s++;
    întoarcere s-t;
}


int main() {
    int input_len=32;
    int output_len=32;
    cheie char nesemnată[32];
    hash char nesemnat[32];
    nesemnat char buf[1024];
    int slen;



    în timp ce(1) {
            do{
                printf("\n\n\n");
                printf(" -------8-------16------24------32-------40------48--- ---56------64 \n");
                printf(" | | | | | | | | \n");
                printf("Cheie: ");
                scanf("%s",buf);
                slen=Slen(buf);
                if(slen!=input_len*2){
                    printf(" Lungimea cheii trebuie să fie %d cifre hexazecimale.",input_len*2);
                }
            }while(slen!=input_len*2);

        // Convertiți șirul hexadecimal în binar
        if(HexToBinArray(buf,input_len,key)){
            printf(" Caracter străin în număr hexazecimal. \n");
            continua;
        }

        //Algoritm hash
        Prs(key, input_len, hash, output_len);

        //Conversie binar în șir hexadecimal
        BinToHexArray(hash,input_len,buf);
        printf(" Hash: %s\n",buf);
    }


    întoarce 0;
}

Codul de testare este scris doar pentru a testa acuratețea ieșirii aplicației, în cod algoritmul hash este în interiorul funcției „Prs”, alte funcții sunt necesare pentru ca codul să funcționeze, dar nu sunt importante. Calculează codul hash al valorilor cheilor de 32 de octeți scrise într-o buclă nesfârșită atunci când codul este compilat și executat. Când cheile de mai sus sunt testate, găsirea aceleiași valori hash pentru fiecare cheie demonstrează că expresia din funcția „Prs” este inversată.

Această aplicație dezvăluie că unele expresii din algoritm pot fi inversate"

De fapt, se știe că marea majoritate a codului din SHA-2, SHA-3 poate fi inversată.

Funcția de compresie hash SHA-2 $h(s,m) = s + f_m(s)$, Unde $f_m(s)$ este inversabilă pentru un bloc de mesaje fixe $m$ [1][2] - adică dacă știi ce $m$ este și ce valoare doriți $f_m(s)$ a fi, este ușor să găsești starea de pornire $s$ care atinge acea valoare. Funcția hash ține cont de acest lucru prin includerea $+$ operație, care nu este inversabilă (deoarece ambele părți depind de starea anterioară $s$, prin urmare atacatorul nu poate inversa operația completă de compresie hash).

Cu SHA-3, întreaga permutare a stării este inversabilă. Adică, dacă cunoașteți starea țintă de 1600 de biți, este ușor să calculați starea anterioară care ar trece în aceasta. Funcția hash ține seama de acest lucru prin dublarea dimensiunii „capacității” (partea stării interne pe care atacatorul nu o poate controla direct); aceasta înseamnă că atacurile „meet-in-the-middle” împotriva imaginii prealabile nu sunt mai ușoare decât simple atacuri cu forță brută.

Nici unul nu duce la o vulnerabilitate cunoscută.

[1]: Funcția de compresie hash diferă între SHA-256 și SHA-512, totuși această afirmație este adevărată pentru ambele

[2]: Operația de adăugare $+$ este de fapt adăugarea modulară în funcție de elemente a unui vector de valori de 32 de biți sau 64 de biți.