5
$\begingroup$

I'm trying to implement a hash function in an esoteric language that has no 32-bit or 64-bit operations. Keccak, for example, is too slow in that language. I'd need a design that minimizes the number of 1-bit operations. Alternatively, I could also use a hash function that relies on integer exponentiation, which is not expensive on this language. Is there any hash function like that?

$\endgroup$
  • $\begingroup$ Very much related, this question that assumes modular exponentiation. $\endgroup$ – Maarten Bodewes Jan 9 at 17:30
  • $\begingroup$ Could you name the language? $\endgroup$ – kelalaka Jan 9 at 17:33
  • $\begingroup$ @kelalaka the language is actually the lambda calculus, running on interaction combinators, which makes certain operations like number exponentiation very fast. I've written about it here. $\endgroup$ – MaiaVictor Jan 9 at 17:41
  • $\begingroup$ Might help Fast Embedded Software Hashing. This can be much faster than exponentiation? $\endgroup$ – kelalaka Jan 9 at 17:55
  • $\begingroup$ @kelalaka what is "this" exactly? I spent a while reading the paper and understand they propose various optimised implementations of different hash functions, but I'm not sure what you're talking about specifically. $\endgroup$ – MaiaVictor Jan 9 at 18:16
5
$\begingroup$

You can use the discrete log-based hash given by $H(x,y) = g^x h^y$, where $g$ and $h$ are two randomly chosen group elements. If your group has known prime order $p$, then this function is collision-resistant if and only if discrete logarithm is hard in your group. In particular, if you find a collision, $g^x h^y = g^{x'} h^{y'}$, then you get $g^{x-x'} = h^{y'-y}$. This means that $x - x' = \log_g h \cdot (y' - y) \mod p$. Since $p$ is prime and $y \neq y'$, we can invert $y'-y$ modulo $p$ to compute the logarithm.

This is assuming that you want a collision-resistant hash function. If you want something stronger, then this might not be suitable for you. E.g., this obviously has the property that $H(x+1,y) = g \cdot H(x,y)$, which could be really bad in some applications.

$\endgroup$
  • $\begingroup$ What if $y' = y$ and $(p-1) | (x - x')$? This collision does not imply a discrete log of $h$. Since the attacker can fix $y$, he can reduce the hash to $H(x)=g^x$. I don't see the point of using $h$... Maybe the reduction works if (x,y) can only be sampled uniformly $\endgroup$ – Hyperflame Jan 11 at 8:58
  • $\begingroup$ x and y are only defined modulo p-1, since the order of the group is p-1. So, if p-1 divides x-x', then x = x'. $\endgroup$ – Noah Stephens-Davidowitz Jan 11 at 9:46
2
$\begingroup$

Wikipedia lists the following hash functions in the article "Security of cryptographic hash functions":

VSH - Very Smooth Hash function - a provably secure collision-resistant hash function assuming the hardness of finding nontrivial modular square roots modulo composite number ${\displaystyle n}$ (this is proven to be as hard as factoring ${\displaystyle n}$).

MuHASH

ECOH - Elliptic Curve Only hash function - based on the concept of Elliptic curves, Subset Sum Problem and summation of polynomials. The security proof of the collision resistance was based on weakened assumptions and eventually a second pre-image attack was found.

FSB - Fast Syndrome-Based hash function - it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.

SWIFFT - SWIFFT is based on the Fast Fourier transform and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal lattices.

Chaum, van Heijst, Pfitzmann hash function - A compression function where finding collisions is as hard as solving the discrete logarithm problem in a finite group ${\displaystyle F_{2p+1}}$.

Knapsack-based hash functions - A family of hash functions based on the Knapsack problem.

The Zémor-Tillich hash function - A family of hash functions that rely on the arithmetic of the group of matrices SL2. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least PSPACE-complete. For this hash, an attack was eventually discovered with a time complexity close to ${\displaystyle 2^{n/2}}$. This beat by far the birthday bound and ideal pre-image complexities which are ${\displaystyle 2^{3n/2}}$ and ${\displaystyle 2^{3n}}$ for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size ${\displaystyle 2n}$ they indeed do not destroy the idea of provable security of invalidate the scheme but rather suggest that the initial parameters were too small.[2]

Hash functions from Sigma Protocols - there exists a general way of constructing a provably secure hash, specifically from any (suitable) sigma protocol. A faster version of VSH (called VSH*) could be obtained in this way.

Items in this list do not necessarily refrain from using bitwise operations completely, but they are built from more algebraic techniques rather than the usual bit mangling techniques

Just the same, they may all still be slower than something such as Keccak or Blake2 in the target language.

$\endgroup$
  • $\begingroup$ Note: The above list was not claimed to be exhaustive; There may exist more designs not listed here. $\endgroup$ – Ella Rose Jan 9 at 17:46
  • $\begingroup$ I looked up a few of those. It seems e.g. FSB commonly uses a normal hash (Whirlpool) to bring down the output size. OK, that doesn't run over all of the data, but it is still something that needs to be considered, especially for smaller messages (and you may not want to run these over large messages :) ). $\endgroup$ – Maarten Bodewes Jan 9 at 18:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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