2
$\begingroup$

More precisely, I am looking for hash functions where the internal state can be decomposed as a vector of integers of size 63. That is, machine integers where one of the bits is fixed and unusable.

$\endgroup$
9
  • 2
    $\begingroup$ If you have 63-bit integers, you should be able to implement anything that uses 32-bit integers internally without much problem. Do you have some more exact requirement that prevents using these? $\endgroup$
    – otus
    Apr 13 '16 at 9:55
  • 1
    $\begingroup$ The issue with that is that you need extra work to mask to int32 in internal steps (and emulating many operations, like rotl, become more complex). I have not measured exactly the performance impact of this for my use case, but some rough benchmarks seem to indicate that the cost would be significant in my use case (like one out of three arithmetic or logic instruction becomes related to masking). $\endgroup$ Apr 13 '16 at 10:01
  • $\begingroup$ How does rotation work then? Are 63-bit rotations fast or does rotation use the bit that is supposed to be fixed? $\endgroup$
    – otus
    Apr 13 '16 at 10:08
  • 1
    $\begingroup$ 63-bit rotations are fast and "behave as they should" (as if there was no masked bits). But emulating another layer of masking to get back int32 on top of those 63 bit integers is too much. $\endgroup$ Apr 13 '16 at 10:12
  • $\begingroup$ Another way to look at the question would be "imagine that you are asked to implement a hash function in hardware, and all the arithmetic and logical unit can work on is words of 63 bits". $\endgroup$ Apr 13 '16 at 10:18
1
$\begingroup$

It would be possible to modify some scheme to move use 63-bit words, but that would require cryptanalysis and new choices for constants. I am not aware of any hash families that would be parametric with regard to word size and allow such uneven values.

Instead I would recommend using any existing hash that internally uses 32-bit words and that does not use many shift or rotation instructions. Modular addition, as well as bitwise operations can be computed on 63-bit values while ignoring all but the 32 low bits.

RIPEMD-160 seems like a decent candidate if 80-bit collision resistance suffices, or perhaps RIPEMD-320 if it does not. Only something like one fifth of the arithmetic instructions are rotations. Even if you need 3-4 instructions to implement rotation, the rest of the function should still dominate runtime.

Note that in the case where the limitation is due to tagged integers losing one bit, it may still be possible to do full 32-bit arithmetic, including rotations, on your 63-bit values without extra performance loss. (Depending on the interpreter/compiler.)

$\endgroup$
1
$\begingroup$

Let's consider a platform with 63-bit unsigned integers, and no support for 32-bit or 64-bit unsigned integers.

We can implement SHA-256, or SHA-1, or MD5, with fair efficiency. The idea is to use 63-bit int for 32-bit unsigned variables, and perform masking to 32-bit only where needed.

A simple implementation of SHA-256 could have the critical loop coded as

#define KL(x)     ((x)&0xFFFFFFFF) /* keep lower 32 bits */
#define RL(x,c)   ((x) << (c)) |  ((x) >> (32 - (c)))
#define G0(x)     (RL((x),30) ^ RL((x),19) ^ RL((x),10))
#define G1(x)     (RL((x),26) ^ RL((x),21) ^ RL((x),7))
#define H0(x)     (RL((x),25) ^ RL((x),14) ^ ((x)>>3))
#define H1(x)     (RL((x),15) ^ RL((x),13) ^ ((x)>>10))
#define CH(x,y,z) ((z) ^ ((x) & ((y) ^ (z))))
#define MA(x,y,z) (((x) & (y)) ^ ((z) & ((x) ^ (y))))

// a b c d e f g h w[] r[] are uint63_t quantities limited to 32 bits
for(j=0; j<64; ++j) {
    uint63_t t = h + G1(e) + CH(e, f, g) + r[j] + w[j&15];
    h = g; g = f; f = e;
    e = KL(d + t);
    d = c; c = b; b = a;
    a = KL(t + G0(b) + MA(b, c, d));
    w[j&15] = KL( w[j&15] + H1(w[(j+14)&15]) + w[(j+9)&15] + H0(w[(j+1)&15]) );
}

There are only 4 invocations of the macro KL in the loop, so masking has modest overhead. The closest we get to overflow is in t + G0(b) + MA(b, c, d), but that fits (notice that G0 produces output at most 62 bits, and t is at most 59 bits).

$\endgroup$
0
$\begingroup$

Have you ever considered to use for instance md5 and to modify the digest function in a way such that the round functions do not modify the said bits? its not really hard, you just need to add a few lines on each round function. I am not sure if this helps.

$\endgroup$
3
  • 1
    $\begingroup$ For anyone reading this: If you want strong security, I strongly recommend against creating your own schemes or modifiying existing ones. $\endgroup$
    – SEJPM
    Apr 13 '16 at 10:09
  • $\begingroup$ The user didn't seem to want very strong security as he/she explicitly stated in the topic title that he was after cryptographic (or non-cryptographic) hashing functions. Having said this, yes by doing what I suggested you could actually weaken md5, but I don't think it would be to a state of complete breaking (the round functions are non-linear and are kinda algebraically ugly to treat nicely) - however - I didn't NOT fully studied this so I can't be sure. $\endgroup$ Apr 13 '16 at 10:16
  • $\begingroup$ Yes, I am clearly looking for some scheme that has been peer reviewed and shown to work in the above setting (most certainly, if such a scheme exists, it will be an algorithm family parameterized by the word size on which the operations work). $\endgroup$ Apr 13 '16 at 10:33

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.