O Princípio de Pigeonhole em funções de Hash

O Princípio de Pigeonhole é um dos principais conceitos por trás da análise combinatória. O princípio diz que:

Se x items são postos em y caixas, e x > y, então pelo menos uma caixa vai ter mais de 1 item.

Podemos entender melhor esse conceito analisando o diagrama abaixo:

Dessa forma, se tivermos mais pombos que caixas, teremos uma caixa para cada pombo (com sobra). Se tivermos o mesmo número de pombos e de caixas, ainda teremos uma caixa para cada pombo. Porém, se tivermos mais pombos que caixas, dois ou mais pombos terão de usar a mesma caixa.

Motivação

Este conceito pode até parecer sem aplicabilidade num primeiro momento, mas na verdade ele é fundamental em diversos assuntos. No caso da área de tecnologia, ele é fundamental para funções de hash.

Funções de Hash

Mais informações sobre a Funções de Hash

wikipedia.org

Hashing

Existem diversos algoritmos de hashing conhecidos, tais como o SHA-1, SHA-3, MD5, SHA-256, SHA-512 e entre tantos outros. Algoritmos estes usados para gerar hashes de arquivos, senhas ou textos, por exemplo.

Usando de exemplo o SHA-256, o número no nome do algoritmo representa a quantidade de bits no hash final, ou seja, 256 bits, resultando em 64 caracteres.

Entendendo mais sobre SHA-256

Mais informações sobre a Funções da família SHA-256

wikipedia.org

Sistema Hexadecimal

Mais informações sobre o Sistema Hexadecimal

wikipedia.org

O hash gerado por esse algoritmo é representado em hexadecimal, portanto o número total de possibilidades que o SHA-256 consegue criar, é o resultado de 16 símbolos em 64 posições diferente. Ou seja:

O SHA-256 é capaz de gerar 1.157920892373162e+77 combinações possíveis.

Este é um número finito, limitado. E como sabemos, podemos ter infinitos arquivos diferentes.

Dessa forma podemos estabelecer uma correlação:

∞ > 1.157920892373162e+77

Então, seguindo o Princípio de Pigeonhole, podemos ver que:

Os Hashes de arquivos ou senhas diferentes, podem acabar sendo iguais, independente de qual algoritmo esteja sendo usado.

Probabilidade

Como hashes são usadas em diversos sistemas diferentes, pode ocorrer essa duplicidade, o que não seria um problema justamente por se tratarem de sistemas diferentes (por exemplo, um sistema usado unicamente em uma empresa privada e um software usado apenas na China). Essa duplicidade seria um problema apenas no caso de hashes duplicadas em um mesmo sistema.

De toda forma, é algo pouco provável de acontecer, mas não impossível