Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Since I'm unfamiliar with cryptography area I haven't been able to find cryptographic hash functions for 32 bit integer keys. It seems all such functions (as I saw here) are designed to digest a stream having hundreds of bytes. What I need is a cryptographic hash function that receives a 32-bit length key, and – preferably with basic math operations (addition, shifting, negating, multiplication) – delivers a preferably 32-bit length hash of the key. Later on I will crop 1, 3, 7, 15, or 31 least-significant bits of the output and use it in my application. Can someone please introduce a suitable algorithm for this purpose?

One more thing to ask: can I rely on simple hash functions on integers introduced here for this purpose? Can I expect them to have quite same characteristics as cryptographic hash functions, such as avalanche effect, for 32 bit integers?

Edit:
The function I'm trying to find or come up with receives an input 32-bit integer number (I referred to it as key in the question description), and delivers a 32-bit length hashed output. What I'm looking for in the output is that by changing even a single bit of the input integer, output varies (preferably drastically in Least Significant Bits). There can be hundreds of millions of keys, so it's better that its output range has a good distribution. Low computation complexity with simple math operations is preferred.
The variation of LSBs in output is much preferred since I'm going to crop LSBs as I described in the question. For example, if I'm going to crop 1 LSB bit, a parity bit would suffice. Or if I want to crop 3 LSB bits, 3 LSB bits of checksum is enough. But if I'm going to crop 7, 15, or 31 LSB bits, checksum would waste 2, 10, and 26 bits respectively.

share|improve this question
    
Welcome to crypto.se! Everything here is cryptographic or off-topic, so I see no use of a cryptographic tag. You do not state the technical objective of your hash, or why it has a key (which in a cryptographic context is secret, and typically much bigger then 32-bit) when what's called a cryptographic hash function does not, and if your hash has another input. –  fgrieu May 17 at 15:54
5  
32-bits is too small to be cryptographically secure, which is why you are not finding what you are looking for –  Richie Frame May 17 at 16:06
    
I added some description. Please let me know if it's still unclear or seems off-topic. –  Farzad May 17 at 16:19
2  
Taking your 32-bit input, applying a cryptographic hash like MD5, and truncating the output to the first 32 bits matches your stated objective. Each bit in the output is a (different) function of all input bits, that behaves much like a random function among the $2^{(2^{32})}$ such functions, except that it has a short description: being that bit of the MD5 output. We can't tell if that matches your real, unstated security objectives, but I doubt that. In particular, MD5, thus this function, is public. And 32 bit is short, thus the input is enumerable, and the output for each input computable. –  fgrieu May 17 at 16:37
    
Thanks. I look into it. –  Farzad May 17 at 17:05

1 Answer 1

up vote 2 down vote accepted

The question asks for a "cryptographic hash function" with 32-bit input and 32-bit output, such "that by changing even a single bit of the input integer, output varies (preferably drastically in Least Significant Bits)". In cryptographic terms, that criteria is reminiscent of good diffusion of input changes.

The non-cryptographic hash functions linked to in the question only vaguely aim at something similar (if we assume that unsigned is 32-bit, unsigned char is 8-bit, and some conversion from 32-bit input to void *key, int len bound to be messy or dependent on endianness). Many of the proposed constructions do not pass the stated criteria. From a quick glance, at least add_hash, xor_hash, rot_hash, djb_hash, sax_hash, fnv_hash, jsw_hash and elf_hash have the problem that some bit of the input never influence the low-order bit of the output.

Out of my head, here is some simple C code matching the stated objective:

#include <stdint.h>
// some arbitrary permutation of 32-bit values
uint32_t perm32(uint32_t x) {
    int n = 12;
    do // repeat for n from 12 downto 1
        x = ((x>>8)^x)*0x6B+n;
    while( --n!=0 );
    return x;
}

It uses techniques borrowed from cryptography, namely:

  • multiple rounds with equivalent structure, each performing a transformation of the state x; these transformations are reversible (avoiding a reduction in the number of possible results as the number of rounds grows), non-linear and with diffusion in both directions (insuring overall diffusion), and different at each round; the combination gives high confidence that near-perfect diffusion is reached after some moderate number of rounds, and remains so with more rounds;
  • x(x>>8)^x is a reversible transformation with right diffusion (8 allows a speed-up on common low-end CPUs, is high enough that the leftmost bit has traveled to the right in a reasonable 4 rounds, while being low enough that the eXclusive-OR acts on many bits);
  • xx*0x6B is a reversible transformation with left diffusion, amounting to repeated addition modulo $2^{32}$ (the multiplicative constant must be coprime with the modulus; 0x6B is high enough that the rightmost bit has traveled to the left in a reasonable 5 rounds, while allowing fast implementation on any CPU with an 8-bit multiplier, and has binary representation 01101011 with some irregularity);
  • xx+n for given n is a reversible transformation, introduced so that rounds are different, and x=0 is not a fixed point;
  • alternating bitwise eXclusive-OR and addition modulo $2^{32}$ results in non-linearity.

I guesstimate from its structure that the function already has fair diffusion at 6 rounds; and with 12 rounds is good enough for almost all uses where using an arbitrary reversible function (rather than an arbitrary function) is fit, and no intelligent adversary is involved.


Applying a cryptographic hash like MD5, SHA-1 or SHA-256, and truncating the output to the first 32 bits, matches the stated objective (in an extremely overkill manner). Each bit in the output is essentially a (different) function of all input bits, that behaves much like a random function among the $2^{(2^{32})}$ such functions, except that it has a short description: being that bit of the output of the hash. Notice that the resulting transformation is not reversible (much likely, some 32-bit outputs are reached for several different 32-bit inputs).

As test vectors for a possible implementation, here is an input-output table showing the effect of changing an input bit starting from input A7000AB9h, for the MD5 and SHA-1 hashes; all values are in hexadecimal.

 input        MD5     MD5 (BE)   SHA-1 
A7000AB9    C4D1EA9D  4DDC786B  BF7C439D
A7000AB8    6F8D506F  9415C265  8C104649
A7000ABB    B140436D  60A906F5  607EA4C3
A7000ABD    55D15F80  C500E8C7  A4E02774
A7000AB1    34B3EFD1  D6EA08ED  7A0181D9
A7000AA9    2FBAC43D  CCF97629  E727356B
A7000A99    2D4BCF14  546B1E97  5707C499
(..)
A6000AB9    84DF82C6  E9319225  5DE2A3A7
A5000AB9    0D314C76  0D70D1D8  39DB8C96
A3000AB9    38A46809  62B798C4  BD586E3C
AF000AB9    E4F2D5DE  57A4E8E1  AF434967
B7000AB9    2E0671E2  25EFAE88  8D0C6003

Note: for MD5, I have also shown what happens if Big-Endian convention is used in converting 32-bit integers to octet strings and back rather than the little-endian convention used by MD5, because that's what you'll tend to get when asking the hash of A7000AB9 to an online tool (scroll down for the results).


While the above solves the problem as stated, it might not be what is actually needed in the (unstated) practical situation. In particular, the functions defined here are public, thus anyone can quickly compute them. And because the input is short, it is possible to try all input values to find those (if any) that give a particular output value, even if the transformation is not directly reversible.

Cryptography has other constructs that might be better suited. In particular we have Message Authentication Codes, that accept a secret key, and a message (which would be the 32-bit input, even though it is named key in the question), and outputs an authenticator (that can be truncated as we did for hashes). That would behave much like the above, but some adversary without the key is left totally in the blues about output that is not known from earlier observations. A common suitable MAC would be HMAC-SHA256.

share|improve this answer
    
Thanks a lot for this comprehensive answer. In your code, may I know what characteristics of the output would be affected if n:the number of iterations become lower and lower? –  Farzad May 18 at 12:53
    
I did some tests with your code. n seems to be like a trade-off factor that provides variety in Most Significant Bits. The more n: the more computation time: the more variety on MSBs. Is that correct? –  Farzad May 18 at 18:22
1  
@Farzad: yes n (the number of rounds in cryptographic terms) is a trade-off; increasing it makes the function slower, but improves diffusion. Given the other choices of parameters, the function still has grossly insufficient diffusion for 4 rounds (the rightmost input bit has little chance to influence the leftmost output bit). For some goals (like randomizing an experiment), 6 rounds could be enough. I conjecture 12 rounds is fine if there is no intelligent adversary. –  fgrieu May 18 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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