0
$\begingroup$

I have developed an application that reverses some expressions used in hash algorithms. The application does not reverse the entire algorithm, but does reverse some parts. This application reveals that some expressions in the algorithm can be reversed. Does this pose a risk to hash algorithms using similar expressions?

Below is the application output and test code of an expression formed from frequently used expressions in hash algorithms. It will be seen that each key gives the same hash value when tested. For all expressions of this complexity (bitwise operations only), the application can list all possible keys for each hash value.

Application output:

 Hash : 817621565b0d4457402862cee209f1ab139bbd8caf2dc72ec172d4d90429c409
 
List of keys (3)
 --------------------------------------------------------------------------
  1 Key : 37639fed3f5c6b60c38a1aeb3589f3176e2b965d75b6a1214ec96b34ddebe005
  2 Key : e23aab653bfe6aa1591496d880687ef17624366a6db9a4159e1bd4dfa879aad9
  3 Key : 249d8cca4a00491c20af4cb0ba8d273518162e6ebddbfc2e243355fbfa179089
 --------------------------------------------------------------------------

Test code:

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



//Hash algorithm
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]);
    }

    return 0;
}


int  HexToBin(unsigned char m, unsigned char l, unsigned char * r) {
    unsigned char v;
    if(m>='a' && m<='f') {
        v=(m-'a'+10)<<4;
    }else if(m>='A' && m<='F') {
        v=(m-'A'+10)<<4;
    } else if(m>='0' && m<='9') {
        v=(m-'0')<<4;
    }else{
        return 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');
    }else{
        return 1;
    }
    *r=v;
    return 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])){
            return 1;
        }
    }
    return 0;
}


int BinToHex(unsigned char  b) {
    int v;
    if((b>>4)>=10) {
        v=((b>>4)+'a'-10)<<8;
    } else {
        v=((b>>4)+'0')<<8;
    }

    if((b&15)>=10) {
        v|=((b&15)+'a'-10);
    } else {
        v|=((b&15)+'0');
    }

    return v;

}


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


int Slen(char *s){
    char *t;
    t=s;
    while(*s)
        s++;
    return s-t;
}


int main() {
    int input_len=32;
    int output_len=32;
    unsigned char key[32];
    unsigned char hash[32];
    unsigned char buf[1024];
    int slen;



    while(1) {
            do{
                printf("\n\n\n");
                printf("         -------8-------16------24------32------40------48------56------64 \n");
                printf("                |       |       |       |       |       |       |       |  \n");
                printf(" Key   : ");
                scanf("%s",buf);
                slen=Slen(buf);
                if(slen!=input_len*2){
                    printf(" Key length must be %d digits hexadecimal.",input_len*2);
                }
            }while(slen!=input_len*2);

        //Convert hex string to binary
        if(HexToBinArray(buf,input_len,key)){
            printf(" Foreign character in hexadecimal number. \n");
            continue;
        }

        //Hash algorithm
        Prs(key,input_len,hash,output_len);

        //Convert binary to hex string
        BinToHexArray(hash,input_len,buf);
        printf(" Hash  : %s\n",buf);
    }


    return 0;
}

The test code is written only to test the accuracy of the application output, in the code the hash algorithm is inside the "Prs" function, other functions are necessary for the code to work, but they are not important. Calculates the hash code of 32-byte key values written in an endless loop when the code is compiled and executed. When the above keys are tested, finding the same hash value for each key proves that the expression in the "Prs" function is reversed.

$\endgroup$
1
  • 1
    $\begingroup$ We do not care much about code (especially when a good half of it does conversion from/to hex, and duplicates the functionality of strlen with restriction on length fitting an int). Rather, please, explain the algorithm your code uses, leaving aside conversion details and concentrating on what's cryptographic. $\endgroup$
    – fgrieu
    Sep 28, 2021 at 6:58

1 Answer 1

5
$\begingroup$

This application reveals that some expressions in the algorithm can be reversed"

Actually, it is known that a large majority of the code in SHA-2, SHA-3 can be reversed.

The SHA-2 hash compression function $h(s,m) = s + f_m(s)$, where $f_m(s)$ is invertible for a fixed message block $m$ [1][2] - that is, if you know what $m$ is and what you want the value $f_m(s)$ to be, it's easy to find the starting state $s$ that achieves that value. The hash function accounts for this by including the $+$ operation, which is not invertible (because both sides depend on the previous state $s$, hence the attacker cannot reverse the full hash compression operation).

With SHA-3, the entire state permutation is invertible. That is, if you know the 1600 bit target state, it's easy to compute the previous state that would permute into that. The hash function accounts for this by doubling the size of the 'capacity' (the part of the internal state that the attacker cannot directly control); this means that 'meet-in-the-middle' attacks against preimage are no easier than simple brute-force attacks.

Neither leads to a known vulnerability.


[1]: The hash compression function differs between SHA-256 and SHA-512, however this statement is true for both

[2]: The addition operation $+$ is actually element-wise modular addition of a vector of 32 bit or 64 bit values.

$\endgroup$
1
  • $\begingroup$ In fact, the reversibility of the SHA-1/256/512 compression function can be used as a block cipher. This use is known as "SHACAL". It's not commonly used, though; other block ciphers are better and designed for the purpose. (poncho knows this of course; I'm just including for readers' benefit) $\endgroup$
    – Myria
    Sep 28, 2021 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.