6
\$\begingroup\$

I don't know much about the design of cryptographic hash functions but despite that I made an attempt for the sake of learning. This is what I got:

#include <stdio.h>

void hash(int* bits, int bitsLen, int* out, int outLen){
  const int tt[9] = {1,2,0,0,0,1,1,2,2};
  int st[128], i, k, j, y, a, b, o = 0;
  for (i=0; i<128; ++i)
    st[i] = i%3;
  for (k=0; k < bitsLen + outLen; ++k){
    for (j=0; j<32; ++j){
      if (k < bitsLen)
        st[0] = bits[k];
      for (i=j%2; i<128; i+=2){
        y = (i+1)%128;
        a = st[i];
        b = st[y];
        st[i] = tt[a*3+b];
        st[y] = tt[b*3+a];
      };
    };
    if (k >= bitsLen)
      out[o++] = (st[0] + st[1]*3 + st[2]*9 + st[3]*27) % 2;
  };
}

void printHex(int* bits, int bitsLen){
  int i;
  for (i=0; i<bitsLen/4; ++i)
    printf("%x", bits[i*4+0]*8+bits[i*4+1]*4+bits[i*4+2]*2+bits[i*4+3]);
}

void toBits(int n, int* bits, int bitsLen){
  int i;
  for (i=0; i<bitsLen; ++i)
    bits[bitsLen-i-1] = (n >> i) & 1;
}

int main(){
  const int bitsLen = 16;
  int bits[bitsLen];

  const int outLen = 256;
  int out[outLen];

  int i;
  for (i=0; i<256; ++i){
    toBits(i, bits, bitsLen);
    hash(bits, bitsLen, out, outLen);
    printHex(bits, bitsLen);
    printf(": ");
    printHex(out, outLen);
    printf("\n");
  };
}

This passes my (certainly lacking) criteria. I'd like to know what are the weaknesses of this function and how it could be exploited if actually used to replace, say, SHA3 in a cryptographic application that requires collision-resistance, non-reversibility and so on.

\$\endgroup\$
  • 1
    \$\begingroup\$ (The modulus operations in hash() look uncalled-for; the ; following block statements ({}) are. Declaring variables at the top of a function instead of the only block they are used in (e.g, a&b) is old style.) \$\endgroup\$ – greybeard Jan 30 '17 at 5:47
  • 1
    \$\begingroup\$ modulus, […] is necessary on the last index ah, for y, yes. Try leaving it out for x. (I first noticed the extraneous semicolons after the for loops, where they can get more dangerous.) \$\endgroup\$ – greybeard Jan 30 '17 at 5:52
  • 4
    \$\begingroup\$ Mandatory reading: Why is writing your own encryption discouraged? \$\endgroup\$ – Alejandro Feb 4 '17 at 23:01
  • 3
    \$\begingroup\$ @Alejandro if everybody followed that advice the field would instantly stop evolving. There is a huge difference between deploying your own toy crypto to production, and doing as an exercise it for the sake of learning. \$\endgroup\$ – MaiaVictor Feb 4 '17 at 23:19
  • 1
    \$\begingroup\$ Although you ask what are the crpytographic weaknesses of this function?, you don't provide any explanation of the mathematics underpinning your hash - even a comment along the lines of this uses a Rijndal block cipher to repeatedly encrypt the IV using successive input chunks as keys would provide something which we could look up. If your variables don't correspond exactly with the algorithm description, then they need to be commented. \$\endgroup\$ – Toby Speight Mar 8 '17 at 14:44
2
\$\begingroup\$

First you need to read Schneier's Memo to the Amateur Cipher Designer. All amateur cryptography is faulty, not just yours. I too designed a cryptographic hash, based round RC4, put it out on the web and Scott Fluhrer was kind enough to show me the obvious faults in it. He is an expert, so he knew what to look for. I was not and I did not know what I had to protect against. Our conversation is probably still out there on the sci.crypt Usenet group from 2007.

To design a good hash function you need to know the types of attacks that are used against hashes. For example, does your hash specifically guard against length-extension attacks?

How fast is your hash compared to other current cryptographic hashes such as SHA3?

For a first suggestion, learn how cryptographic hashes pad their input and why. Either incorporate the same technique into your hash or else find a different way to serve the same purpose. You are not the first person to write a hash. Learn so you can stand on the shoulders of giants.

\$\endgroup\$
  • \$\begingroup\$ Why you're assuming my hash doesn't work without any evidence of it? \$\endgroup\$ – MaiaVictor Aug 3 '17 at 3:15
  • \$\begingroup\$ Have you specifically protected your hash against length-extension attacks? Have you tested it to see if it is vulnerable to those attacks? How many other forms of cryptographic attacks on hash functions have you researched and protected against? \$\endgroup\$ – rossum Aug 3 '17 at 8:07
  • \$\begingroup\$ Talking about length-extension attacks doesn't even make sense on my construction. They're a byproduct of how certain kinds of hash work, which do not apply here. If you have any other form of attack in mind please let me know. \$\endgroup\$ – MaiaVictor Aug 3 '17 at 8:09
  • \$\begingroup\$ Have you specifically protected your hash against length-extension attacks? Have you tested it to see if it is vulnerable to those attacks? \$\endgroup\$ – rossum Aug 3 '17 at 8:14
  • \$\begingroup\$ I believe that, to perform a "length-extension" the attacker would need to to find the 32th previous iteration of the automata based on a single bit, which is equivalent to the problem of reversing the automata, so either the attacker can reverse it and recover the original value, or he can't do anything. There's no length extension attack in between. \$\endgroup\$ – MaiaVictor Aug 3 '17 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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