Capítulo 7 — Probabilidade e estatística
Mapa da aula
Aula 07 publicada. Mapa, exemplo, EX019.
flowchart TD
N0["7.1 O problema do aniversário"]
N1["Laboratório — Probabilidade de colisão"]
N2["7.2 Ler os resultados"]
N3["7.3 Interpretar afirmações probabilísticas"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Exemplo resolvido"]
EX --> Q["Exercício EX019"]
Desenho lógico
flowchart LR
N0["7.1 O problema do aniversário"]
N1["Laboratório — Probabilidade de colisão"]
N2["7.2 Ler os resultados"]
N3["7.3 Interpretar afirmações probabilísticas"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX019"]
[7.1 O problema do aniversário]
|
v
[Laboratório — Probabilidade de colisão]
|
v
[7.2 Ler os resultados]
|
v
[7.3 Interpretar afirmações probabilísticas]
|
v
[Síntese]
|
v
[Exemplo resolvido] --> [Exercício EX019]
Objetivos de aprendizagem
Você vai (1) aplicar o limite do aniversário a colisões; (2) escolher tamanhos de tags e identificadores a partir de metas de colisão; (3) interpretar afirmações probabilísticas nas normas.
7.1 O problema do aniversário
Numa sala com 23 pessoas, a chance de duas fazerem aniversário no mesmo dia passa de metade, embora o ano tenha 365 dias. O motivo é que o número de pares cresce com o quadrado do número de pessoas. Para valores aleatórios de um espaço de tamanho N, as colisões se tornam prováveis depois de cerca da raiz quadrada de N sorteios. Para um valor de n bits, isso dá cerca de 2^(n/2). Katz e Lindell usam esse limite para explicar por que uma função de hash com saída de n bits oferece apenas cerca de n/2 bits de resistência a colisões, e é por isso que se diz que o SHA-256 dá segurança de 128 bits contra colisões.
Laboratório — Probabilidade de colisão
"""Birthday bound: chance two of k random n-bit tags collide (approximation)."""
import math
def p(k, bits):
return -math.expm1(-k * (k - 1) / 2 ** (bits + 1))
def main():
for bits in (32, 64, 128):
k = 2 ** (bits // 2)
print(f"{bits:>3}-bit tags, k=2^{bits // 2}: P(collision) = {p(k, bits):.3f}")
print(f"meters 50,000 with 32-bit ids: P = {p(50_000, 32):.3f}")
if __name__ == "__main__":
main()
Execute com python3 lab_birthday.py. Saída verificada:
32-bit tags, k=2^16: P(collision) = 0.393
64-bit tags, k=2^32: P(collision) = 0.393
128-bit tags, k=2^64: P(collision) = 0.393
meters 50,000 with 32-bit ids: P = 0.253
7.2 Ler os resultados
Para cada tamanho de tag, sortear 2^(n/2) valores aleatórios dá uma probabilidade de colisão de cerca de 0,393, a mesma para 32, 64 e 128 bits. Essa constante mostra exatamente a regra da raiz quadrada. Na prática, dar identificadores aleatórios de 32 bits a 50.000 medidores produz uma chance de cerca de 25 por cento de dois compartilharem um identificador. Aiyana recomenda que a Ridgeway atribua os identificadores sequencialmente a partir de um registro, e não ao acaso, e que todo valor aleatório cuja unicidade importe, como um nonce, use pelo menos 96 bits, como faz o GCM, com contagem e rotação, como exige o SP 800-38D.
7.3 Interpretar afirmações probabilísticas
As normas frequentemente enunciam a segurança como um limite de probabilidade para um atacante que faz certo número de consultas. Aiyana aprende a fazer três perguntas a qualquer afirmação desse tipo: o que o atacante pode fazer, quantas operações são contadas e que evento conta como falha. Uma afirmação de falha 2^-32 depois de 2^32 mensagens é muito diferente de 2^-32 por mensagem. Ela também aprende que as estatísticas de sistemas reais raramente coincidem com a aleatoriedade ideal, de modo que os engenheiros medem, por exemplo verificando nos logs de produção se há nonces duplicados, em vez de confiar apenas no limite teórico.
Exemplo resolvido
Aiyana calcula uma chance de colisão de 25 por cento para 50.000 identificadores aleatórios de 32 bits e recomenda identificadores atribuídos por registro e nonces contados de 96 bits.
Caso sintético. O tamanho da frota é inventado; o SP 800-38D é real.
Erros e limites
O limite do aniversário supõe aleatoriedade uniforme; geradores enviesados colidem mais cedo. Os limites de probabilidade dependem da unidade contada, então leia-os com cuidado.
Exercícios
-
EX019 — Regra da raiz quadrada. Depois de aproximadamente quantos sorteios valores aleatórios de n bits começam a colidir? Rubrica: 3 = cerca de 2^(n/2);; 2 = raiz quadrada mencionada;; 1 = 2^n;; 0 = nenhuma.
-
EX020 — Identificadores dos medidores. Que chance de colisão o laboratório deu para 50.000 medidores com identificadores de 32 bits, e que correção se seguiu? Rubrica: 3 = cerca de 0,253; identificadores atribuídos por registro;; 2 = só o número;; 1 = só a correção;; 0 = nenhuma.
-
EX021 — Ler um limite. Cite as três perguntas que Aiyana faz a uma afirmação probabilística. Rubrica: 3 = capacidades do atacante, operações contadas, evento de falha;; 2 = duas;; 1 = uma;; 0 = nenhuma.
Síntese
O limite do aniversário transforma o risco de colisão em requisitos de tamanho em bits, e a leitura cuidadosa das afirmações probabilísticas evita um falso conforto.
Continue estudando — aula 07 (capítulo 07 de 50)
← Capítulo 06 · Índice das aulas · Capítulo 08 →
Continue para a próxima aula já escrita.