Capítulo 7 — Probabilidade e estatística
Mapa da aula
Aula 07 publicada. Mapa, exemplo, EX013.
flowchart TD
N0["7.1 Eventos raros"]
N1["7.2 Atividade prática — Laboratório P"]
N2["7.3 Intervalos de confiança"]
N3["7.4 Segurança estatística versus criptográfica"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Exemplo resolvido"]
EX --> Q["Exercício EX013"]
Desenho lógico
flowchart LR
N0["7.1 Eventos raros"]
N1["7.2 Atividade prática — Laboratório P"]
N2["7.3 Intervalos de confiança"]
N3["7.4 Segurança estatística versus criptográfica"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX013"]
[7.1 Eventos raros]
|
v
[7.2 Atividade prática — Laboratório P]
|
v
[7.3 Intervalos de confiança]
|
v
[7.4 Segurança estatística versus criptográfica]
|
v
[Síntese]
|
v
[Exemplo resolvido] --> [Exercício EX013]
Objetivos de aprendizagem
Você vai (1) raciocinar sobre eventos raros, como falhas de decifração; (2) estimar taxas com intervalos de confiança; (3) distinguir níveis de segurança estatísticos de criptográficos; e (4) desenhar uma medição com amostras suficientes. O capítulo parte dos Capítulos 1 e 6 e apoia a medição (Capítulo 29) e a validação (Capítulo 38).
7.1 Eventos raros
Os KEMs de reticulados têm uma probabilidade minúscula de que o desencapsulamento produza a chave errada. Os conjuntos de parâmetros da FIPS 203 a mantêm extremamente pequena — cerca de 2^-139 para o ML-KEM-512 e menor para os conjuntos maiores —, muito abaixo de qualquer taxa que um engenheiro vá observar. O número esperado de falhas em N operações é N·p. O Laboratório P mostra por que uma probabilidade como 2^-20, aceitável para muitos fins de engenharia, seria inaceitável para um KEM usado bilhões de vezes, enquanto 2^-139 é desprezível em qualquer escala.
A regra de decisão é simples: multiplique pelo maior número de operações que o sistema jamais fará e confira que o produto fica muito abaixo de um.
7.2 Atividade prática — Laboratório P
# Lab P (ch 7): how small must a failure probability be? Binomial reasoning for rare events.
import math
for p_exp in (-20, -40, -139):
p = 10.0 ** (p_exp * math.log10(2)) # p = 2^p_exp
for n_ops in (1e9, 1e15):
exp_fail = n_ops * p
print(f"p = 2^{p_exp:5d}, {n_ops:.0e} operations -> expected failures {exp_fail:.3e}")
Saída esperada:
p = 2^ -20, 1e+09 operations -> expected failures 9.537e+02
p = 2^ -20, 1e+15 operations -> expected failures 9.537e+08
p = 2^ -40, 1e+09 operations -> expected failures 9.095e-04
p = 2^ -40, 1e+15 operations -> expected failures 9.095e+02
p = 2^ -139, 1e+09 operations -> expected failures 1.435e-33
p = 2^ -139, 1e+15 operations -> expected failures 1.435e-27
Leia as seis linhas aos pares. Com 2^-20, um bilhão de operações já produz quase mil falhas esperadas, então um esquema assim falharia visivelmente todos os dias na escala da BPA. Com 2^-40, um bilhão de operações parece seguro, mas um quatrilhão, aproximadamente o volume global de um protocolo amplamente implantado ao longo de alguns anos, dá cerca de 900. Com 2^-139, mesmo a contagem maior deixa uma expectativa de 1,4 × 10^-27, e é por isso que a falha de decifração não é, de modo algum, uma preocupação de projeto para o ML-KEM. Estenda o laço com 1e18 operações e confirme que a conclusão não muda.
7.3 Intervalos de confiança
Ao medir as taxas de falha de handshake depois de ativar um grupo híbrido, informe um intervalo, não apenas um ponto. Para proporções pequenas, use o intervalo de Wilson (o laboratório de canário do Capítulo 37 o usa). A regra de três dá um limite rápido: se ocorrerem zero falhas em n tentativas, o limite superior de 95% para a taxa é cerca de 3/n.
A regra decorre de exigir que zero falhas em n tentativas tenham no máximo 5% de chance: (1 − p)^n = 0,05 dá p ≈ 3/n. Ela só vale quando as tentativas são independentes; as falhas causadas por um proxy defeituoso se concentram num local, então um canário espalhado por vários locais dá um limite mais honesto do que a mesma contagem vinda de um só.
7.4 Segurança estatística versus criptográfica
Um teste estatístico que não encontra falhas em um milhão de execuções diz apenas que a taxa provavelmente está abaixo de 3 × 10^-6. Níveis de segurança criptográfica como 2^-128 não podem ser estabelecidos por testes; eles vêm da análise. Os engenheiros testam para encontrar bugs, não para provar segurança.
Para mostrar por testes uma taxa abaixo de 2^-128, seriam necessárias cerca de 10^39 tentativas, muito além de qualquer computador. Ainda assim vale a pena executar os testes, porque um bug de implementação costuma produzir falhas numa taxa de uma em algumas centenas ou milhares, que uma campanha de testes modesta detecta depressa. Uma execução limpa dos testes descarta, portanto, os bugs grosseiros e deixa a alegação de segurança para a análise publicada.
7.5 Exemplo resolvido
O piloto da BPA observa 0 falhas de handshake em 12.000 conexões híbridas num local. A regra de três limita a taxa de falhas abaixo de 2,5 × 10^-4 (95%). Isso basta para implantar em 2 milhões de conexões diárias? No limite, ainda poderiam ocorrer até 500 falhas por dia — então o portão de decisão exige um canário maior antes da implantação completa.
Para baixar o limite a cerca de uma falha por dia com 2 milhões de conexões, é preciso mostrar uma taxa abaixo de 5 × 10^-7, o que, pela regra de três, exige cerca de 6 milhões de conexões limpas. A BPA pode chegar lá ampliando o canário para vários locais durante alguns dias, o que também testa middleboxes diferentes.
7.6 Erros comuns e limites
- Interpretar "nenhuma falha observada" como "a taxa é zero".
- Confundir uma probabilidade de falha de decifração com um nível de segurança.
- Ignorar que as operações se multiplicam: raro por evento não é raro por ano.
O primeiro erro leva as equipes a declarar sucesso após um piloto pequeno, como no exemplo resolvido, em que zero falhas em 12.000 ainda permitiam 500 por dia. O segundo confunde dois números: a probabilidade de falha de 2^-139 do ML-KEM é um número de confiabilidade, enquanto a categoria 3 descreve o trabalho de que um atacante precisa. O terceiro se corrige multiplicando as taxas por evento pelo volume anual antes de julgá-las.
Exercícios
- EX013 — Regra de três. Quantas tentativas sem falha são necessárias para limitar uma taxa abaixo de 10^-5? Rubrica: 3 = 300.000, com o raciocínio.
- EX014 — Escala. Se um componente falha com probabilidade 2^-30 por operação e a BPA executa 10^10 operações por ano, quantas falhas são esperadas? Rubrica: 3 = ≈ 9,3 e interpretação.
Síntese
Eventos raros se tornam comuns em escala; os testes limitam taxas, mas não estabelecem segurança criptográfica; informe intervalos e dimensione as amostras para a decisão a tomar.
Continue estudando — capítulo 07 de 50
← Capítulo 06 · Índice de capítulos do curso · Capítulo 08 →
Siga para a próxima lição escrita.