O Paradoxo do Aniversário & Ataque Sweet32!

8 min readAug 9, 2021

O Paradoxo do Aniversário

Na teoria das probabilidades, o paradoxo do aniversário afirma que dado um grupo de 23 pessoas escolhidas aleatoriamente, a chance de que duas pessoas terem a mesma data de aniversário é de mais de 50%. Para 57 ou mais pessoas, a probabilidade é maior do que 99%, entretanto, ela não pode ser exatamente 100% exceto que se tenha pelo menos 367 pessoas. Calcular essa probabilidade (e as relacionadas a ela) é o problema do aniversário. A matemática por trás disso tem sido utilizada para executar o ataque do aniversário.

O ataque do aniversário abusa dessa condição da probabilidade para executar várias colisões até chegar no valor desejado.
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 específico é: 1 — (364/365)³⁰, cerca de 7,9%.

Entretanto, 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)! x 365^n)

“Birthday Paradox Grapher” by inju is licensed under CC BY-NC-SA 2.0

O Tamanho da Chave Importa?

Em criptografia o tamanho da chave importa?
Veja segundo a tabela abaixo a relação do nível de segurança das chaves entre as criptografias que temos disponíveis hoje:

Source: https://www.netburner.com/learn/comparing-rsa-and-ecc-encryption/ Credits: Atmel

Conforme eu expliquei no meu último Post aqui do Medium, a criptografia ECC é a melhor em termos de performance, Key size e segurança. Lembrando que para saber o número de possibilidades por cifra deve-se aplicar a fórmula:
Possibilidades = 2^n
Onde n é o tamanho da cifra.
Vamos usar para fins deste estudo 3 situações.

1- Um Computador de alta potência
MacBook Intel Core i7 com potência de 128 MB/s por core.
Vamos considerar 4 Cores e 2 Threads por Core, ou seja 1024 MB/s.

2- Um dos computadores mais potentes do mundo
Estou considerando aqui o supercomputador Sunway TaihuLight. Ele performa 93 PetaFlops, a efeito de computação o computador anterior performava 100 GigaFlops.
Isso basicamente significa que esse computador é aproximadamente 1 Milhão de vezes mais rápido que o anterior. Usaremos isso como base de cálculo.

3- Todos os computadores do Planeta Terra conectados em um único cluster.
É estimado ter aproximadamente 2 Bilhões de computadores na Terra.
Vamos assumir que a média de velocidade é igual a do primeiro computador, o MacBook. Portanto se pegássemos todos os computadores do mundo num único cluster teríamos uma potência 2 Bilhões de vezes mais rápida. Você deve estar pensando que para quebrar uma chave criptográfica de, por exemplo, 64 Bits você teria que testar todas as 2⁶⁴ Possibilidades… mas isso é um conceito errado. É aí que entra o paradoxo do aniversário, ele se aplica aqui também. De acordo com o paradoxo do aniversário quando você chegasse na metade da validação, a próxima verificação teria 50% de chance de ser a chave!
Portanto, se você fizer somente a metade de 2⁶⁴ você teria 50% (Joga uma moeda aí) de achar a chave correta nas próximas instruções!
Importante frisar que: a metade de 2⁶⁴ NÃO É 2³²
Como estamos na base 2, é uma progressão que cresce pelo dobro do valor anterior, para saber a metade basta calcular o valor de 2^n-1
Pois: 2^n-1 = (2^n)/2
Prova de conceito: 2³² = 4.294.967.296
Metade é 2³¹ = 2.147.483.648

Dito isso vamos para a tabela, onde os valores foram calculados sempre com base nessa premissa: Possibilidades = 2^(Valor da cifra -1)

Os dados em verde são humanamente possíveis de serem quebrados.
Os que estão em vermelho são humanamente impossíveis.
Com o poder computacional atual um computador comum levaria aproximadamente 36 anos para quebrar uma chave de 64 Bits.
O tailuLight quebra em algumas dezenas de milhares da fração de um ano. (Aproximadamente 18 Minutos).
Já o nosso super-cluster teórico quebraria basicamente instantâneamente.
Nem preciso dizer que cifras com menos de 64-bits são facilmente quebradas com o poder computacional convencional de 2021, certo?
As coisas começam a ficar interessantes a partir de 112-Bits.

O computador convencional levaria 10 Quadrilhões de anos para quebrar metade dessa cifra. O tempo de existência do universo é estimado em até 14 Bilhoes de anos. Ou seja, você precisaria de alguns Bilhões de universos rodando seu script em Multi-Thread. Até mesmo para nosso cluster-teórico levariamos aproximadamente 5 Milhões de anos para quebrar metade de uma cifra de 112-Bits.
Já as cifras acima de 128-Bits(e relativas) são consideradas seguras, tão seguras que nem mesmo um teórico computador quântico conseguiria quebrar em um tempo razoável de existência. Mas isso pode ser assunto para outro artigo…
Se você aplica AES-256 com GCM nos seus arquivos, parabéns! Se todos os computadores do planeta estivessem em um cluster seria necessário: 112.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 anos! (112 Penta-decadilhões de anos).
A menos que você seja um buraco-negro super massivo, você não viverá tudo isso.

Encadeamento por bloco de cifra

Em criptografia, uma cifra em blocos trabalha com blocos de comprimento fixo, frequentemente de 64 ou 128 bits. Visto que as mensagens podem ter qualquer comprimento, e dado que criptografar o mesmo texto simples sob a mesma chave sempre produz a mesma saída, vários modos de operação foram inventados, os quais permitem que o ciframento em blocos forneça confidencialidade para mensagens de tamanho arbitrário.

Os modos mais antigos descritos na literatura (por exemplo, ECB, CBC, OFB e CFB) provê somente confidencialidade e não assegura integridade da mensagem. Outros modos foram desenvolvidos desde então para assegurar tanto a confidencialidade quanto a integridade da mensagem, tais como os modos IAPM, CCM, EAX, GCM e OCB. O modo configurável de bloco estreito (LRW) e os modos de criptografia de bloco largo (CMC e EME), projetados para criptografar setores de disco com segurança, são descritos no artigo dedicado à teoria de criptografia de disco.

Para os fins deste e do próximo artigo vamos focar no CBC (Cifra de bloco encadeado)

CBC funciona com a seguinte fórmula: ci = Ek(mi ⊕ ci-1)
onde c-1 é um valor de inicialização geralmente denotado como IV. Agora explicamos o impacto das colisões no modo CBC.
O CBC provou ser seguro até 2^(n/2) blocos de mensagens. Por outro lado, há um ataque de aniversário simples contra CBC: após 2n/2 blocos de mensagem criptografados com a mesma chave (na mesma mensagem ou em mensagens diferentes), é esperada uma colisão entre dois blocos de texto cifrado ci = cj. Como Ek é uma permutação, uma colisão na saída significa que as entradas são as mesmas (mi ⊕ ci-1 = mj ⊕ cj-1), o que revela o XOR de dois blocos de texto simples: mi ⊕ mj = ci-1 ⊕ cj-1
Com blocos de dados 2d, o número esperado de colisões é aproximadamente 2d-n-1 (seguindo o paradoxo do aniversário). Em outras palavras: Cifras que usam CBC como o 3DES são vulneráveis a um tipo de ataque matemático que reduz a proteção da cifra pela metade do número de bits da cifra e ainda levamos em conta o ataque do aniversário, reduzindo esse valor novamente pela metade! Ou seja: Uma cifra de 64 bits que aplica CBC na realidade tem um nível de proteção real de uma cifra de 32 Bits, ou seja: 2³¹ (Lembre-se o paradoxo do aniversário). Esse ataque é o Sweet32.

O Ataque Sweet32

O Sweet32 possui esse nome justamente por conta daquela tabela que eu mostrei. Cifras com 32-Bits são humanamente possíveis de serem quebradas em um tempo razoável com computadores normais. Portanto se você consegue reduzir uma cifra de 64-bits para 32-bits já é uma grande vantagem. Para executar este ataque a forma mais simples é através de um MITM.

Além do fato de DES e 3DES serem algoritmos ultrapassados de criptografia, aplicar com CBC permite o ataque sweeet32. O atacante pode injetar um código js no browser da vítima e quebrar a comunicação dela com o servidor principal, ou apenas sniffar a rede e quebrar interceptando os pacotes e aplicando brute-force. Portanto, servidores que usam CBC e DES ou 3DES de 64-bits estão totalmente vulneráveis ao Sweet32. pi = pj ⊕ ci-1 ⊕ cj-1
A forma acima reflete o número de colisões necessárias para se obter a chave.

Exemplo de ataque:

Prova de conceito:

Com a colisão de cifras você encontra a chave e com a chave você quebra a comunicação. Podendo extrair senhas, cookies, sessions-ids, tokens de autenticação e etc. Estão vulneráveis ao sweet32 todas as cifras de 64 bits que aplicam CBC. DES e 3DES são as mais vulneráveis pois elas se limitam à 112-Bits (Metade é 56-bits) e seu encadeamento é quase sempre com CBC. São algoritmos obsoletos, por isso geralmente relacionam o sweet32 com 3DES, mas o sweet32 está relacionado com qualquer cifra 64-bits que aplica CBC. Para se proteger do sweet32 você deve expurgar todas as cifras 64-bit que usam o CBC do seu servidor. Sejam elas DES ou 3DES. Não negocie com essas cifras de 64-Bits que aplicam CBC!
A recomendação é usar AES128 ou 256 com GCM, o mais moderno.