Ataque do aniversário

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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 é , 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]

Matemática[editar | editar código-fonte]

Dada uma função , o objetivo do ataque é encontrar duas diferentes entradas, e tais que . Tal par é chamado colisão. O método usado para encontrar uma colisão é simplesmente calcular a função 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 fornece qualquer dos diferentes saídas com igual probabilidade e é suficientemente grande, então esperamos obter um par de diferentes argumentos e com após calcular a função para cerca de 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(nH) a probabilidade que durante esse experimento, pelo menos um valor seja escolhido mais de uma vez. Essa probabilidade pode ser escolhida como

Seja n(pH) 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

e atribuindo uma probabilidade de colisão 0,5, chegamos em

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

Como um exemplo, se um hash de 64-bit é usado, então há aproximadamente 1.8 × 1019 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 × 109) para gerar uma colisão usando força bruta. Esse valor é chamado limitante do aniversário[2] e para códigos de n bits poderia ser computados como 2n/2.[3] 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−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 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 na equação para não é precisamente computada para 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.[4] 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[editar | editar 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[editar | editar código-fonte]

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

que também pode ser escrita como

.

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 () e quer que a chance de uma colisão seja, no máximo, uma em um milhão (), quantos documentos poderíamos ter no máximo?

que é próximo da resposta correta, que é 93.

Suscetibilidade da assinatura digital[editar | editar código-fonte]

Assinaturas digitais podem ser suscetíveis a um ataque do aniversário. Uma mensagem é tipicamente assinada computando, primeiro, , onde é uma função hash criptográfica, e em seguida usando alguma chave secreta para assinar . Suponha que Mallory quer enganar Bob assinando um contrato fraudulento. Mallory prepara um contrato honesto e um fraudulento . Ela então encontra um número de posições onde 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 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 . 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, .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 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 é o número de pares. O número de hashes que Mallory realmente gera é .

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[editar | editar código-fonte]

Notas[editar | editar código-fonte]

Referências[editar | editar código-fonte]

Links externos[editar | editar código-fonte]