3

I am doing a bit of research on hash functions. I understand the concept that it is an equation that is easy to do one way (you take the number 00011010 for example and do reasonably simple math with it) but the function you use is very difficult to do the other way. I cannot however find any examples of what a one-way hash function would look like. I watched YouTube videos where they gave prime number multiplication as an analogy, and I searched google for examples but cannot find any examples for what an actual function would look like.

I have basic computer programming knowledge but am not an experienced coder.

  • 1
  • 2
    Your question as it is, is too broad. What do you mean look like? Have you looked at CRCs? Are you trying to understand what makes something cryptographically secure when CRCs or checksums are not? Or what? – whatsisname Jun 6 '18 at 1:31
  • 1
  • 4
    You're confusing two things. One-way or trapdoor functions are bijective, they're just harder to compute in one direction than in the other. Hash functions are not bijective, in fact their entire point is to map a larger space to a smaller one (and a good hash function is one which does this as evenly as possible). – Kilian Foth Jun 6 '18 at 6:13
  • @KilianFoth: I don't think that one-way functions are necessarily bijective. – Michael Borgwardt Jun 6 '18 at 7:02
6

All hash functions are one-way. Hash functions map a larg(er) (potentially infinite) input space into a small(er) (usually finite) output space.

If you are familiar with the Pigeonhole Principle, this should immediately tell you that hash functions must be one-way. If you are not familiar with the Pigeonhole Principle, here is a very simple explanation:

The Pigeonhole Principle states that you cannot put 3 socks in 2 drawers without having at least one drawer with at least 2 socks in it.

So, if you have a function that maps a larger input space into a smaller output space, then you will have at least two inputs that map to the same output, ergo, you cannot reverse a hash function.

A very simple example of a hash function that does not use any advanced math, is this simple parity function:

def hash(n: Nat)
  if n.even?
    0
  else
    1
  end
end

As you can see, it maps a large input space (the natural numbers) into a small output space (the set {0, 1}). And it is one-way: if I tell you that the result is 1, you can't tell me what the input was.

  • 2
    I think you're missing the main point, as did @user180969 in formulating the question (due to limited understanding of the issue): the important cryptographic aspect of "one-way hash function" is that you cannot easily construct any input that will produce a given output. – Michael Borgwardt Jun 6 '18 at 6:58
  • 1
    @MichaelBorgwardt, I disagree that this answer misses the point. It absolutely answers the question, "what does a hash function look like". Your answer is also a good one in that it builds upon this to then explain how hashes can be used in cryptography, but this still remains a good answer. – David Arno Jun 6 '18 at 7:46
  • 1
    @DavidArno: It tries to the title of the question but completely misses the intention visible in the question details. The answer is also blatantly wrong beginning in its very first sentence: It is not true that "all hash functions are one-way" because "one way" is a completely different thing than "not bijective". – Michael Borgwardt Jun 6 '18 at 8:53
  • 2
    @MichaelBorgwardt: You're missing the intention here. By all intentions, OP is using "one way" to refer to "not bijective" functions. Keep in mind that OP explicitly specifies having rudimentary knowledge. If he knew the difference between one-way and not bijective, he'd also be able to form a basic example of either. This answer answers the OP's main question: I cannot however find any examples of what a one-way hash function would look like.. Jorg's answer is oversimplified specifically to make it easy to understand the core intention of what makes this hashing one-way (not bijective). – Flater Jun 6 '18 at 9:00
  • 1
    I have some sympathy for both points of view. @MichaelBorgwardt is absolutely correct that it should be difficult to construct any input for the given output - clearly not the case here. However, this needs to be balanced against providing a simple enough example that anyone who reads this question should be able to understand. – Robbie Dee Jun 6 '18 at 12:34
7

It seems you'tre talking about cryptographic hash functions, where it's essential that you cannot easily construct any input that will have a given output - that is what "one-way function" means. Hash functions in general (e.g. used for hash tables) do not have this requirement.

The easiest example of a cryptographic hash function is the Rabin function, modular squaring. It works like this:

  • Take your input as a number (any digital data can easily be interpreted as a binary number).
  • Square it.
  • Take the modulo (remainder of dividing by) N, where N is the product of two prime numbers and determines the length of your hash.

Let's use N = 4181.

I tell you the hash is 3666. Your job is to find X such that X^2 mod 4181 = 3666. How do you solve that?

You can of course brute force it by seeing whether 4181 + 3666 is a square number, then trying 4181*2+3666, then 4181*3+3666, but that is going to take forever.

You can do some serious math, and find out that you can find a solution quickly if you know the prime factors of N. But you don't, and finding the prime factors for a large number (in a real scenario N would be much larger) also takes forever.

2

Here's a simple example:

A hash of the string "Hello world!" is "Hel". If you're given "Hel", you cannot recreate "Hello world!", and yet it is likely not going to clash with many other strings.

Admittedly, this hash isn't very good because if this were a password, knowing the first three letters makes it a lot easier to brute force the original password.

So what if we multiplied each letter value by 3 mod 26?

H (7) * 3 -> V (21)
e (4) * 3 -> m (12)
l (11) * 3 -> f (5)

Now our hash is "Vmf". Granted, you could reverse this, but without knowing that it was multiplied by 3, this already becomes a bit tricker. For a computer this is trivial, but imagine multiplying against enormous prime numbers. It would make finding a pattern virtually impossible, and you'd have to dedicate long computation hours calculating possible values and trying them out.

Converting it to "Vmf" was a trivial matter, but restoring to "Hel" isn't. This is exactly what we want from a hash.

If the user provides the string "Hello, World!", without having to save the original string, we can simply apply the hash to "Hello, World!" and obtain "Vmf" and then compare that string to the one we have on file..

"Vmf" === "Vmf"  // Bingo!

And in a nutshell this is what hashing is. There are various techniques, but the concept is ultimately the same. Deterministically create an irreversible string of data from an input.

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.