# Ataque de Aniversário - cab4

O ataque do aniversário é um tipo de ataque criptográfico que explora a matemática por trás do paradoxo do aniversário na teoria da probabilidade. Este ataque pode ser usado para abusar de comunicação entre duas ou mais partes. O ataque depende da maior probabilidade de colisões encontrado entre as tentativas de ataque aleatório e um grau fixo de permutações (pigeonholes).

## Entendendo o problema

Como um exemplo, considere o cenário no qual um professor com uma classe de 30 estudantes pergunta pelo aniversário de todo mundo., para determinar se quaisquer dois estudantes tem o mesmo dia de aniversário (correspondendo a uma hash collision como descrito mais adiante [por simplicidade, ignore 29 de fevereiro]). Intuitivamente, essa chance pode parecer pequena. Se o professor escolheu um dia específico (digamos 16 de Setembro), então a chance de pelo menos um aluno ter nascido naquele dia especifico é $1-(364/365)^{30}$, cerca de 7.9%. No entanto, a probabilidade de pelo menos um estudante ter a mesma data de aniversário de qualquer outro estudante é por volta de 70% para n = 30, a partir da fórmula$1-365!/((365-n)!\cdot 365^{n})$.

## Matemáticas

Dada uma função $f$, o objetivo do ataque é encontrar duas diferentes entradas, $x_{1}$ e $x_{2}$ tais que $f(x_{1})=f(x_{2})$. Tal par $x_{1},x_{2}$ é chamado colisão. O método usado para encontrar uma colisão é simplesmente calcular a função $f$ para diferentes valores de entrada que podem ser escolhidos aleatoriamente ou pseudo-aleatoriamente até que o mesmo resultado seja encontrado mais de uma vez. Devido ao problema do aniversário, esse método pode ser bastante eficiente. Especificamente, se uma função $f(x)$ fornece qualquer dos $H$ diferentes saídas com igual probabilidade e $H$ é suficientemente grande, então esperamos obter um par de diferentes argumentos $x_{1}$ e $x_{2}$ com $f(x_{1})=f(x_{2})$ após calcular a função para cerca de $1.25{\sqrt {H}}$ argumentos diferentes em média.
Consideremos o seguinte experimento. A a partir de um conjunto de H valores escolhemos n valores uniformemente aleatórios permitindo, assim, repetições. Seja p(n; H) a probabilidade que durante esse experimento, pelo menos um valor seja escolhido mais de uma vez. Essa probabilidade pode ser escolhida como
    $p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},\,$
Seja n(p; H) o menor número de valores que temos para escolher, tal que a probabilidade de encontrar uma colisão seja, pelo menos, p. Pela inversão desta expressão acima, encontramos a seguinte aproximação
    $n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},$
e atribuindo uma probabilidade de colisão 0.5, chegamos em
    $n(0.5;H)\approx 1.1774{\sqrt {H}}.\,$
Seja Q(H) o número esperado de valores que temos para escolher antes de encontrar a primeira colisão. Esse número pode ser aproximado por
    $Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}.$
Como um exemplo, se um hash de 64-bit é usado, então há aproximadamente 1.8 × 10$^{19}$ diferentes saídas. Se todos estes são igualmente prováveis (o melhor caso), deveria-se considerar 'apenas' 5 bilhões de tentativas (5.1 × 10$^9$) para gerar uma colisão usando força bruta. Esse valor é chamado limite do aniversário e para códigos de n bits poderia ser computados como 2$^{n/2}$. Outros exemplos são os seguintes:
    Bits Possíveis saídas (2 s.f.) (H)  Probabilidade desejada de colisão aleatória (2 s.f.) (p) 10$^{−18}$ 10$^{−15}$ 10$^{−12}$ 10$^{−9}$ 10$^{−6}$ 0.1% 1% 25% 50% 75% 16 65,536 <2 <2 <2 <2 <2 11 36 190 300 430 32 4.3 × 10$^9$ <2 <2 <2 3 93 2900 9300 50,000 77,000 110,000 64 1.8 × 10$^{19}$ 6 190 6100 190,000 6,100,000 1.9 × 10$^8$ 6.1 × 10$^8$ 3.3 × 10$^9$ 5.1 × 10$^9$ 7.2 × 10$^9$ 128 3.4 × 10$^{38}$ 2.6 × 10$^{10}$ 8.2 × 10$^{11}$ 2.6 × 10$^{13}$ 8.2 × 10$^{14}$ 2.6 × 10$^{16}$ 8.3 × 10$^{17}$ 2.6 × 10$^{18}$ 1.4 × 10$^{19}$ 2.2 × 10$^{19}$ 3.1 × 10$^{19}$ 256 1.2 × 10$^{77}$ 4.8 × 10$^{29}$ 1.5 × 10$^{31}$ 4.8 × 10$^{32}$ 1.5 × 10$^{34}$ 4.8 × 10$^{35}$ 1.5 × 10$^{37}$ 4.8 × 10$^{37}$ 2.6 × 10$^{38}$ 4.0 × 10$^{38}$ 5.7 × 10$^{38}$ 384 3.9 × 10$^{115}$ 8.9 × 10$^{48}$ 2.8 × 10$^{50}$ 8.9 × 10$^{51}$ 2.8 × 10$^{53}$ 8.9 × 10$^{54}$ 2.8 × 10$^{56}$ 8.9 × 10$^{56}$ 4.8 × 10$^{57}$ 7.4 × 10$^{57}$ 1.0 × 10$^{58}$ 512 1.3 × 10$^{154}$ 1.6 × 10$^{68}$ 5.2 × 10$^{69}$ 1.6 × 10$^{71}$ 5.2 × 10$^{72}$ 1.6 × 10$^{74}$ 5.2 × 10$^{75}$ 1.6 × 10$^{76}$ 8.8 × 10$^{76}$ 1.4 × 10$^{77}$ 1.9 × 10$^{77}$
    A tabela mostra o número de hashes n(p) necessário para alcançar necessário para alcançar a probabilidade de sucesso dada. Para comparação, de 10$^{−18}$ a 10$^{−15}$ representa a taxa de erro de bits incorrigíveis de um típico disco rígido . Na teoria, hashes MD5 ou UUIDs, sendo 128 bits, deveria ficar dentro deste intervalo até cerca de 820 bilhões de documentos, mesmo se suas possíveis saídas são muitos mais que isso.
É fácil ver que se as saídas da função são distribuídas desigualmente, então a colisão poderia ser encontrado ainda mais rápido. A noção de 'equilíbrio' de uma função de hash quantifica a resistência de uma função para o ataque de aniversário (explorando chave de distribuição desigual) e permite a vulnerabilidade dos hashes populares tais como MD e SHA para ser estimado (Bellare and Kohno, 2004).
A subexpressão $\ln {\frac {1}{1-p}}$ na equação para $n(p;H)$ não é precisamente computada para $p$ pequeno quando diretamente traduzido para linguagens de programação comuns como log(1/(1-p)) devido a perda de significância. Quando log1p é disponível (como é em C99) por exemplo, a expressão equivalente -log1p(-p) deveria então ser usada. Se isso não for feito, a primeira coluna da tabela acima é computada como zero, e vários itens na segunda coluna não tem dígito significativo correto.

### Exemplo de código fonte

Há uma função em Python que pode precisamente gerar a tabela acima:
Se o código é salvo em um arquivo chamado birthday.py, ele pode ser rodado ele pode ser executado de forma interactiva como no exemplo a seguir:

### Aproximação simples

Uma boa regra de ouro que pode ser usada para cálculo mental é a relação
    $p(n)\approx {n^{2} \over 2m}$
que também pode ser escrita como
    $n\approx {\sqrt {2m\times p(n)}}$.
Isso funciona bem para probabilidades menores ou iguais a 0.5.
Esse esquema de aproximação é especialmente fácil para usar quando trabalhar com expoentes. Por exemplo, suponha que você esteja construindo hashes de ($m=2^{32}$) e quer a chance de uma colisão de ser, no máximo, uma em um milhão ($p\approx 2^{-20}$),  quantos documentos poderíamos ter no máximo?
    $n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5$
que é próximo da resposta correta, que é 93.

## Susceptibilidade da assinatura digital

Assinaturas digitais podem ser susceptíveis a um ataque de aniversário. Uma mensagem $m$ é tipicamente assinada computando, primeiro, $f(m)$, onde $f$ é uma função de hash criptográfica, e em seguida usando alguma chave secreta para assinar $f(m)$. Suponha que Mallory quer enganar Bob assinando um contrato fraudulento. Mallory prepara um contrato honesto $m$ e um fraudulento $m'$. Ela então encontra um número de posições onde $m$ pode ser modificado sem alterar o significado, de modo que inserindo vírgulas, linhas vazias, um versus dois espaços após uma sentença, substituindo sinônimos, etc. Pela combinação dessas mudanças, ela pode criar um número enorme de variações sobre $m$ que são todos os contratos justos.
De um modo semelhante, Mallory também cria um enorme número de variações sobre o contrato fraudulento $m'$. Ela, então, aplica a função de hash para todas essas variações até que ela encontra uma versão do contrato justo e uma versão do contrato fraudulento que têm o mesmo valor de hash, $f(m)=f(m')$.Ela apresenta a versão hones a Bob para assinar.  Depois de Bob assinou, Mallory leva a assinatura e a anexa ao contrato fraudulento. Essa assinatura 'comprova' então que Bob assinou o contrato fraudulento.
As probabilidades diferem ligeiramente do problema aniversário original, embora Mallory nada ganhe por encontrar dois contratos honestos ou dois contratos fraudulentos com o mesmo hash. A estratégia da Mallory é gerar pares de contratos, sendo um justo e um fraudulento. As equações do problema do aniversário se aplicam onde $n$ é o número de pares. O número de hashes que Mallory realmente gera é $2n$.
Para evitar este ataque, o comprimento da função de hash utilizado para um esquema de assinatura de saída pode ser escolhido suficientemente grande de modo que o ataque de aniversário se torna computacionalmente inviável,ou seja, cerca de duas vezes quantos bits são necessários para evitar um ataque de ataque de força bruta comum.
O algoritmo rho de P para logaritmos é um exemplo para um algoritmo usando um ataque de aniversário para o cálculo de logaritmos discretos.