Everyone has heard of encryption, and most understand the basic idea.
You have a message, apply an algorithm, and you get an encrypted version of that message.
To go back to the original message, you use the same key used to encrypt it.
In other words, encryption allows you to move back and forth between the clear message and its encrypted form.
This is a one-to-one relation.
---
Now, Let's Talk About Hashing, Shall We?
Seems to be the same idea, really:
Put something in, hash it, get something out. But it behaves very differently.
Imagine: to your left, a world of infinite possible cleartext messages. In the middle, the hashing function. And to your right, the resulting hashes.
Here's the key difference:
The group to the right is smaller than the one of original messages.
Different messages can end up producing the same hash — this is called a collision.
In other words: there is information loss during hashing:
Your final group of hashed messages is "poorer" in terms of information than your original group.
---
A Simple Example
Let's clarify this with a toy example.
Imagine a small world where every message is made of 4 different digits, each one between 0 and 3.
Here's our original group of possible "cleartext" messages:
(0123) (1023) (2013) (3012)
(0132) (1032) (2031) (3021)
(0213) (1203) (2103) (3102)
(0231) (1230) (2130) (3120)
(0312) (1302) (2301) (3201)
(0321) (1320) (2301) (3210)
And here's our toy hashing rule:
Take the first two positions (the leftmost digits).
Look at the indices that those digits represent.
Swap the values at those two positions.
Example:
(0213)
First two digits are '0' and '2'.
(0213)
Now we swap the values at positions '0' and '2':
(1203)
This final number is our hashed value.
---
What Happens When We Apply This To All Messages?
- Some original values won't be found in the hashed group (information loss).
- Many of the original values will map to the same hashed result (collisions).
- Ergo, we can't always reverse the process and retrieve the original.
---
Let's Showcase This With a Particular Number
Suppose you pick this final (already hashed) value:
(2301)
There is only one way to get to this value, so we can actually reverse our number and get to the original
(2310) -----> (2301)
(check the top image or, even better, try to make the table yourself)
But now take this hashed value:
(3201)
This one can actually be produced by three different original messages:
(0231) ----> (3201)
(3102) ----> (3201)
(3210) ----> (3201)
Which one was the original one? Can we be sure?
---
Key Takeaway
Hashing means:
- Information Loss
- Many-to-one relationship
- Reversibility not guaranteed
Even in this toy example, some hashes have several origin messages, leading to the same output. In fact, the original group has 24 unique values and the end group has only 12 unique values.
And real life examples are much, much more complex than this, making even finding collisions computationally impractical. But the principle remains.
---
And remember:
To teach is to lie (a little).
Hashing (and encryption) can be way more complicated and interesting than this.
For more information, check this link and this link.
Also, this simple algorithm can be found in the fine (and free) "Reverse Engineering for Beginners", by Dennis Yurichev.
Check that out too.
Have Fun!
No comments:
Post a Comment