Pesquisa · Mapa mental

Ataque do aniversário

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).

Fonte: Wikipédia (pt)Atualizado em 25/10/2026
01

Entendendo o problema

Imagem: Senado Federal · BY · Openverse

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 {\displaystyle 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 ) ! ⋅ 365 n ) {\displaystyle 1-365!/((365-n)!\cdot 365^{n})} .

02

Matemática

Imagem: Senado Federal · BY · Openverse

Dada uma função f {\displaystyle f} , o objetivo do ataque é encontrar duas diferentes entradas, x 1 {\displaystyle x_{1}} e x 2 {\displaystyle x_{2}} tais que f ( x 1 ) = f ( x 2 ) {\displaystyle f(x_{1})=f(x_{2})} . Tal par x 1 , x 2 {\displaystyle x_{1},x_{2}} é chamado colisão. O método usado para encontrar uma colisão é simplesmente calcular a função f {\displaystyle 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 ) {\displaystyle f(x)} fornece qualquer dos H {\displaystyle H} diferentes saídas com igual probabilidade e H {\displaystyle H} é suficientemente grande, então esperamos obter um par de diferentes argumentos x 1 {\displaystyle x_{1}} e x 2 {\displaystyle x_{2}} com f ( x 1 ) = f ( x 2 ) {\displaystyle f(x_{1})=f(x_{2})} após calcular a função para cerca de 1.25 H {\displaystyle 1.25{\sqrt {H}}} argumentos diferentes em média.

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 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 {\displaystyle m=2^{32}} ) e quer que a chance de uma colisão seja, no máximo, uma em um milhão ( p ≈ 2 − 20 {\displaystyle p\approx 2^{-20}} ), quantos documentos poderíamos ter no máximo? que é próximo da resposta correta, que é 93.

03

Suscetibilidade da assinatura digital

Imagem: Senado Federal · BY · Openverse

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

Vídeos recomendados

Fontes consultadas

Continue pesquisando