Ataque do aniversário

Predefinição:Mais notas 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ão encontrada 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 colisão hash 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ática

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 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¹⁹ diferentes saídas (18.446.744.073.709.551.616). Se todos estes são igualmente prováveis (o melhor caso), deveria-se considerar 'apenas' 5 bilhões de tentativas (5.1 × 10⁹) para gerar uma colisão usando força bruta. Esse valor é chamado limitante 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 × 109	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	1.8 × 1019	6	190	6100	190,000	6,100,000	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	3.4 × 1038	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	1.2 × 1077	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	3.9 × 10115	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	1.3 × 10154	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

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⁻¹⁸ a 10⁻¹⁵ 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 encontrada ainda mais rapidamente. A noção de 'equilíbrio' de uma função de hash quantifica a resistência de uma função para o ataque do aniversário (explorando chave de distribuição desigual) e permite que a vulnerabilidade dos hashes populares tais como MD e SHA seja estimada (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:

def birthday(probability_exponent, bits):
    from math import log1p, sqrt
    probability = 10. ** probability_exponent
    outputs     =  2. ** bits
    return sqrt(2. * outputs * -log1p(-probability))

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:

$ python -i birthday.py
>>> birthday(-15, 128)
824963474247.1193
>>> birthday(-6, 32)
92.68192319417072

Aproximação simples

Uma boa regra de ouro que pode ser usada para cálculo mental é a relação

$p(n)\approx \frac{n^2}{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 que a chance de uma colisão seja, 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.

Suscetibilidade da assinatura digital

Assinaturas digitais podem ser suscetíveis a um ataque do aniversário. Uma mensagem $m$ é tipicamente assinada computando, primeiro, $f(m)$, onde $f$ é uma função 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^{\prime }$. 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^{\prime }$. 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^{\prime })$.Ela apresenta a versão honesta 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 do 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 Pollard para logaritmos é um exemplo para um algoritmo usando um ataque do aniversário para o cálculo de logaritmos discretos.

Ver também

• Ataque de colisão (do inglês, collision attack)
• Ataque do homem no meio (do inglês, man-in-the-middle attack)
• Ataque da preimagem

Ligações externas

• "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
• "Birthday Attack" X5 Networks Crypto FAQs