CoCalc Shared Files3 - Hashes to ashes / Hashes to ashes.sagews
Author: Gabriel Chênevert
Description: Crypto @ ISEN Lille -- Lab 3: Hashes to ashes

# Lab 3: Hashes to ashes

## A) Pearson hashing

You are given a permutation of the integers $0$ to $2^{16} -1$ as a list:
perm = load("perm")

If you want to know the image of, say, 10000, under this permutation, just look at the corresponding entry:
perm[10000]

28390
And the other way around:
perm.index(28390)

10000
%html
<p>Use this permutation to construct a Pearson hash function turning arbitrarily long byte strings into 2-character hashes (use some padding scheme when the original string has odd length).</p>
<p>Make sure that you get the following values:</p>
<p>$m = \tt{hello!}$, $h = \tt{1b3f}$</p>
<p>$m = \tt{HELLO?}$, $h = \tt{fea5}$</p>
<p>$m = \verb{A longer one{$, $h = \tt{e1ba}$</p>



Use this permutation to construct a Pearson hash function turning arbitrarily long byte strings into 2-character hashes (use some padding scheme when the original string has odd length).

Make sure that you get the following values:

$m = \tt{hello!}$, $h = \tt{1b3f}$

$m = \tt{HELLO?}$, $h = \tt{fea5}$

$m = \verb{A longer one{$,$h = \tt{e1ba}$




## B) Birthday attack

From now on, you play the attacker and try to break the above (insecure) hash function, to which you have unlimited access (i.e., you can compute as many hashes as you want with it).

How many hashes of randomly generated strings do you expect it would take before a collision is found for this hash function?



Check how lucky you are today by performing a birthday attack on the Pearson hash function.


%html
<h2>C) Extension attack</h2>

<p>The situation is much worse than that, since the Pearson hash function is not designed to be cryptographically secure. Convince yourself that, given two strings, such as
$a = \tt{target}$ and $b = \verb{beginning of the end{$,
it is always possible to append two characters at the end of $b$ to get a new string $b'$ such that $H(b') = H(a)$. Be fair game by using only information known to the attacker (<i>i.e.</i>, it is forbidden to look at $\tt{perm}$ but you can perform as many hash evaluations as you like).</p>


## C) Extension attack

The situation is much worse than that, since the Pearson hash function is not designed to be cryptographically secure. Convince yourself that, given two strings, such as $a = \tt{target}$ and $b = \verb{beginning of the end{$, it is always possible to append two characters at the end of$b$to get a new string$b'$such that$H(b') = H(a)$. Be fair game by using only information known to the attacker (i.e., it is forbidden to look at $\tt{perm}$ but you can perform as many hash evaluations as you like).



%html
<h2>D) Dictionary attack</h2>

<p>Now a "real-world" example. Some hackers have leaked a large database of SHA1 password hashes from a well-known online retailer, where we learn that Alice's password hashes to
eb0176f4d146dd4118ec6ef04552ee92febc3550.</p>

<p>You think Alice might be the kind of person to use her birthdate as password, and you know she was born after 2000. Can you recover her password? (the website administrators carelessly didn't use any salt when hashing the passwords).</p>


## D) Dictionary attack

Now a "real-world" example. Some hackers have leaked a large database of SHA1 password hashes from a well-known online retailer, where we learn that Alice's password hashes to eb0176f4d146dd4118ec6ef04552ee92febc3550.

You think Alice might be the kind of person to use her birthdate as password, and you know she was born after 2000. Can you recover her password? (the website administrators carelessly didn't use any salt when hashing the passwords).