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.