<commit_before>---
layout: post
date: 2017-03-13 20:00
title:  "Calculating the odds of a SHA-1 Collision"
category: blog
tags: security
d3Load: true
math: true
redirect_from:
  - /archive/2017/03/calculating-odds-of-sha1-collision.html
---

With the announcement that [Google has developed a technique to generate SHA-1 collisions](https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html), albeit with huge computational loads, I thought it would be topical to show the odds of a SHA-1 collision in the wild using the Birthday Problem.

But first, some background:

The Birthday Problem
--------------------
This famously counter-intuitive paradox states that in a room of 23 people there is a 50% chance that two people would share a birthday. If you up the amount of people to 75, then your odds go up to 99.9%

It's probably up there with the [Monty Hall Problem](https://en.wikipedia.org/wiki/Monty_Hall_problem) for most argued about popular probability puzzle, but it actually makes a lot of sense when you break it down.

The confusion usually comes from the fact that we are thinking about 1/365 odds for each of the 23 people instead of the odds of not getting a match in a pair, of which we have 
$$\frac{23\times22}{2}=253 $$ combinations.

Ignoring messy, real-world statistics like how birthdays tend to group together:

<div class="chart"></div>
<script type="text/javascript" src="/assets/js/d3/births.js"></script>


Then, you can calculate the probability of two people not having the same birthday with:

$$ {p} \approx 1 -\left (\dfrac{364}{365}\right)^{x(x-1)/2} $$

Where \\( x = 23 \\) people, we get .500477154 or just over 50% chance of a match.

SHA-1 Background
----------------

Secure Hash Algorithm 1 (SHA-1) was developed by the NSA in 1995 and it is used commonly in security protocols and version control systems, although it is being phased out in favor of more secure hash functions.

In a **very** simplified way it works by padding, appending, expanding, compressing, and splitting the input data into blocks and then adding the result to a hash state that generates the 160-bit final hash known as a Message Digest.

This hash is often represented as a 40 digit hexadecimal number. 

You can read the [full RFC](https://tools.ietf.org/html/rfc3174) if you want to dive deeper into the internals of SHA-1

The Birthday Problem Applied
----------------------------
So how does the Birthday Problem relate to SHA-1 collisions? Instead of finding matches between people's birthdays, now you can find matches in 160 bit hashes.

Diverging from the math we did in first section, we are going to cheat and use an approximation for the finding the amount of files needed for a 50% chance of a match or 'collision' in SHA-1.

A good approximation of a 50% chance of a match is the square root of number of days in the year \\( \sqrt{365} \approx 19 \\). Kind of close to the actual answer of 23, but it doesn't really matter much when dealing with huge numbers like the SHA-1 domain.

Using that approximation for SHA-1 with a 160-bit hash:

$$ \sqrt{ {2}^{160} } = \sqrt{ {2}^{80} } \approx 1,208,925,819,614,629,174,706,176 $$

To put that into perspective, Facebook and Twitter could decide to identify posts using SHA-1 and it would still take them over 3,400 years of data, assuming no growth and always unique messages, before they even had to worry about a 50% chance of a collision.

An upgrade to SHA3-512 or even SHA-256 algorithms and they would need to worry more about the heat death of the universe than a collision.
<commit_msg>Do plain numbers trigger it?<commit_after>---
layout: post
date: 2017-03-13 20:00
title:  "Calculating the odds of a SHA-1 Collision"
category: blog
tags: security
d3Load: true
math: true
redirect_from:
  - /archive/2017/03/calculating-odds-of-sha1-collision.html
---

With the announcement that [Google has developed a technique to generate SHA-1 collisions](https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html), albeit with huge computational loads, I thought it would be topical to show the odds of a SHA-1 collision in the wild using the Birthday Problem.

But first, some background:

The Birthday Problem
--------------------
This famously counter-intuitive paradox states that in a room of 23 people there is a 50% chance that two people would share a birthday. If you up the amount of people to 75, then your odds go up to 99.9%

It's probably up there with the [Monty Hall Problem](https://en.wikipedia.org/wiki/Monty_Hall_problem) for most argued about popular probability puzzle, but it actually makes a lot of sense when you break it down.

The confusion usually comes from the fact that we are thinking about 1/365 odds for each of the 23 people instead of the odds of not getting a match in a pair, of which we have 
$$\frac{23\times22}{2}=253 $$ combinations.

Ignoring messy, real-world statistics like how birthdays tend to group together:

<div class="chart"></div>
<script type="text/javascript" src="/assets/js/d3/births.js"></script>


Then, you can calculate the probability of two people not having the same birthday with:

$$ {p} \approx 1 -\left (\dfrac{364}{365}\right)^{x(x-1)/2} $$

Where \\( x = 23 \\) people, we get .500477154 or just over 50% chance of a match.

SHA-1 Background
----------------

Secure Hash Algorithm 1 (SHA-1) was developed by the NSA in 1995 and it is used commonly in security protocols and version control systems, although it is being phased out in favor of more secure hash functions.

In a **very** simplified way it works by padding, appending, expanding, compressing, and splitting the input data into blocks and then adding the result to a hash state that generates the 160-bit final hash known as a Message Digest.

This hash is often represented as a 40 digit hexadecimal number. 

You can read the [full RFC](https://tools.ietf.org/html/rfc3174) if you want to dive deeper into the internals of SHA-1

The Birthday Problem Applied
----------------------------
So how does the Birthday Problem relate to SHA-1 collisions? Instead of finding matches between people's birthdays, now you can find matches in 160 bit hashes.

Diverging from the math we did in first section, we are going to cheat and use an approximation for the finding the amount of files needed for a 50% chance of a match or 'collision' in SHA-1.

A good approximation of a 50% chance of a match is the square root of number of days in the year \\( \sqrt{365} \approx 19 \\). Kind of close to the actual answer of 23, but it doesn't really matter much when dealing with huge numbers like the SHA-1 domain.

Using that approximation for SHA-1 with a 160-bit hash:

$$ \sqrt{ {2}^{160} } = \sqrt{ {2}^{80} }  $$

To put that into perspective, Facebook and Twitter could decide to identify posts using SHA-1 and it would still take them over 3,400 years of data, assuming no growth and always unique messages, before they even had to worry about a 50% chance of a collision.

An upgrade to SHA3-512 or even SHA-256 algorithms and they would need to worry more about the heat death of the universe than a collision.

{'fraction_non_alphanumeric': 0.08770949720670392, 'fraction_numerical': 0.04120111731843575, 'mean_word_length': 3.7644710578842315, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1083093', 'n_tokens_mistral': 2135, 'n_tokens_neox': 1881, 'n_words': 1072}