3
$\begingroup$

I'm trying to understand what is required to construct one-way hash functions. I know about many algorithms used in practice, such as SHA256, Blake2, MD5, which are of high quality, but they're complex and studying them doesn't really answer my question. I also know about "simpler" algorithms such as multiplication modulus - but those are often not one-way, so they also don't help with the question.

Are there one-way, cryptographically safe hashing algorithms that are very, very simple to describe? When I say simple, I mean really, really simple. As in, a cellular automata, or something that could be implemented in 4 or 5 lines of code.

$\endgroup$
  • 7
    $\begingroup$ I'm trying to understand what is required to construct one-way hash functions: actually, nobody really knows that. In fact, nobody knows if there exists any efficient one-way hash functions. All we have is some functions that no one knows how to invert (or find collisions in). $\endgroup$ – poncho Dec 30 '16 at 19:53
  • $\begingroup$ I'm not very good at reading so I like to look at pictures instead. Try Google Images with "hash function". You'll see that they're actually quite simple. They're just various inventive (and sometimes just tediously derivative) arrangements of bit substitution, bit permutation and some XORs. I learnt a lot from studying the very simple Pearson Hash. Also try Keccak which has some fancy and innovative marketing gimmicks, but is very well explained in the specification paper. $\endgroup$ – Paul Uszak Dec 30 '16 at 21:36
  • 2
    $\begingroup$ Cryptography is sometimes hard. This is not something that you can over-simplify. MD5 cannot be broken and high quality at the same time. $\endgroup$ – Maarten Bodewes Dec 31 '16 at 1:12
4
$\begingroup$

Designing a conceptually simple one-way function is a very hard challenge in itself - and conceptual simplicity is not such a well defined concept, so the answers you will receive might be a bit opinion-based (and in particular, so will be my answer).

One of my favourite candidate OWF regarding conceptual simplicity is Goldreich's local one-way function. It is more a vast class of possible functions than a specific one, but here is the core idea:

  • You fix some simple predicate $P$ that acts on a small number of inputs $d$.
  • You fix $m$ random subsets $(S_1, \cdots, S_m)$ of $[1,n]$, such that each subset is of size exactly $d$. $n$ represents the input size of the function, and $m$ is the output size.

Now, the function simply does this: on input $x \in \{0,1\}^n$, output $y = y_1y_2\cdots y_m \in \{0,1\}^m$ where $y_i$ is computed by evaluating $P$ on the $d$ bits of $x$ indexed by the subset $S_i$.

As you can see, the high level idea of the function is extremely simple. The hard part is choosing a good predicate $P$, and studying the conditions that must be satisfied by the sets $S_i$ to be able to withstand existing attacks. And indeed, both problems have been intensively studied in the theoretical community in the past ten years. But this does not affect the extreme simplicity of an implementation: to implement it, fix once for all a list of subset $(S_1, \cdots, S_m)$ (if you want a compression function, take $m = n/2$), picked at random in some setup phase, and store it in some file. For $P$ and $d$, take something widely regarded as good in the theoretical community - e.g., you can take $d = 5$ and $$P : (x_1,x_2,x_3,x_4,x_5) \mapsto x_1+x_2+x_3+x_4\cdot x_5 \bmod 2$$ (see e.g. this article). The code for evaluating the function is extremely simple: to generate the $i$th bit of the output, it retrieves $S_i$ from the stored file (a random subset of $[1,n]$ of size $5$), and applies the above $P$ on the bits of $x$ whose index are in $S_i$. Moreover, all the output bits can be generated in parallel.

Now, if your sole purpose is understanding how OWF are built - well, looking at a very specific example will hardly help, as OWF functions can be constructed from a huge variety of designs. But if you only wanted to see a conceptually simple one, with some detailed explanations on why this family of functions can be conjectured to be one-way (see Goldreich's paper, which I find fairly easy and pleasant to read), this might satisfy your need.

$\endgroup$
  • $\begingroup$ This is a very satisfying answer, I was looking exactly for examples like this one. Similarly simple constructions would be welcome so I could compare them. $\endgroup$ – MaiaVictor Jan 4 '17 at 14:28

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.