Atividade Pratica 03 - SHAKE128 Detector de colisões

Pré-requisitos

Como o programa utiliza a função SHAKE128, ele depende das bibliotecas de criptografia do OpenSSL. Antes de compilar, garanta que você tenha o compilador gcc e as ferramentas de desenvolvimento do OpenSSL instaladas:

• No Ubuntu/Debian:

  sudo apt update
  sudo apt install build-essential libssl-dev
  

Funcionamento e Modos de Execução

O programa implementa uma busca de colisões em SHAKE128 truncado utilizando uma abordagem baseada no ataque do aniversário combinada com detecção de ciclos de Brent/Pollard Rho. A ideia principal consiste em transformar sucessivas saídas do hash em novos estados, formando uma sequência iterativa até que um ciclo seja detectado.

A implementação possui diferentes modos de execução para facilitar testes, depuração e experimentos mais longos.

Para compilar

gcc -O3 -march=native -Wall -Wextra -o shake128_collision_true shake128_collision_true.c -lssl -lcrypto

Modo verdadeiro (64 bits)

./shake128_collision_true

Executa o algoritmo utilizando SHAKE128 truncado para 8 bytes (64 bits), conforme especificado no enunciado da atividade.

Nesse modo, a busca por colisões pode exigir bilhões de avaliações da função hash devido à complexidade esperada do ataque do aniversário:

$$ 2^{64/2}=2^{32} $$

Por esse motivo, a execução pode durar horas ou até dias dependendo do hardware utilizado.

• Observação: Na meu laboratório de execução o maior tempo necessário até encontrar colisões foi cerca de quatros horas.

---

Modo demonstrativo (32 bits)

./shake128_collision_true --demo32

Nesse modo, a saída do SHAKE128 é reduzida para apenas 4 bytes (32 bits).

O objetivo desse modo foi permitir validar rapidamente se:

• o algoritmo estava funcionando corretamente;
• a detecção de ciclos estava operacional;
• colisões eram encontradas adequadamente;
• o fluxo geral da implementação estava correto.

Como o espaço de busca é muito menor, colisões costumam ser encontradas rapidamente.

A complexidade esperada nesse caso é aproximadamente:

$$ 2^{32/2} = 2^{16} $$

o que torna os testes muito mais rápidos durante o desenvolvimento.

---

Seed manual

./shake128_collision_true --seed 123456789

Permite definir manualmente a seed inicial utilizada na sequência iterativa.

Esse modo foi implementado para:

• reproduzir execuções específicas;
• depurar o algoritmo;
• repetir experimentos;
• analisar comportamentos determinísticos do ciclo encontrado.

Sem esse parâmetro, o programa gera uma seed pseudoaleatória automaticamente.

---

Limite de avaliações

./shake128_collision_true --max 12000000000

Define um limite máximo de avaliações da função hash antes do encerramento do programa.

Esse modo foi criado principalmente para execuções muito longas, permitindo:

• controlar o tempo de execução;
• evitar consumo indefinido de recursos;
• deixar o programa executando por períodos extensos (por exemplo, durante a noite);
• interromper automaticamente experimentos caso nenhuma colisão fosse encontrada até determinado ponto.

Quando o limite é atingido, o programa encerra a execução informando a quantidade total de avaliações realizadas.

---

Combinação de parâmetros

Os parâmetros podem ser combinados:

./shake128_collision_true --seed 123456789 --max 12000000000

Nesse caso, o programa utiliza simultaneamente:

• uma seed fixa;
• um limite máximo de avaliações.

---