02 — Fundamentos da Criptografia

Conceitos, vocabulário, modelos de adversário, princípios e definições de segurança. Pré-requisito para entender todos os outros arquivos do compendium.

---

1. Vocabulário básico

---

2. Princípios de Kerckhoffs (1883)

Auguste Kerckhoffs, La Cryptographie Militaire (Journal des Sciences Militaires, vol. IX, 1883):

1. O sistema deve ser praticamente, senão matematicamente, indecifrável.
2. Não deve exigir que seja secreto; pode cair em mãos do inimigo sem inconveniente. ⭐ — princípio canônico.
3. Sua chave deve ser comunicável e memorizável sem notas, e mudável à vontade.
4. Deve ser aplicável à correspondência telegráfica.
5. Deve ser portátil, e seu uso não deve requerer mais de uma pessoa.
6. O sistema deve ser fácil de usar, sem demanda mental ou conhecimento de longa lista de regras.

Reformulação moderna de Bruce Schneier: "Security through obscurity is no security". Reformulação de Shannon: "The enemy knows the system".

---

3. Princípios de Shannon (1949)

Claude Shannon, Communication Theory of Secrecy Systems (Bell System Technical Journal 28, 1949):

Secrecy perfeita

Um cifra tem perfect secrecy se para todo P, P' e C: $\(\Pr[E_k(P) = C] = \Pr[E_k(P') = C]\)$

Ciphertext não dá nenhuma informação sobre plaintext. Teorema de Shannon: secrecy perfeita exige \(|K| \geq |M|\) — chave pelo menos tão longa quanto a mensagem. One-Time Pad é a única realização prática, com chave verdadeiramente aleatória, do mesmo tamanho, usada uma vez.

Confusão e difusão

• Confusão: relação entre chave e ciphertext deve ser complexa e não-linear. Cada bit do ciphertext depende de muitos bits da chave.
• Difusão: relação entre plaintext e ciphertext deve ser espalhada. Um bit do plaintext afeta muitos bits do ciphertext (avalanche).

Block ciphers modernos alternam camadas de substituição (S-boxes — confusão) e permutação/mixing (P-boxes ou multiplicação matricial — difusão). Estrutura SPN (Substitution-Permutation Network — AES) ou Feistel (DES).

---

4. Modelos de adversário

Em ordem crescente de poder:

Hierarquia: COA ⊂ KPA ⊂ CPA ⊂ CCA1 ⊂ CCA2.

Definições de segurança IND-* / SUF-* / EUF-*

IND-CPA game (intuição):

1. Adversário escolhe duas mensagens \(m_0\), \(m_1\) de mesmo tamanho.
2. Challenger sorteia \(b \in \{0,1\}\) aleatório, envia \(C = E_k(m_b)\).
3. Adversário tenta adivinhar \(b\).
4. Cifra é IND-CPA segura se \(\Pr[\text{adv adivinha}] - 1/2\) é negligível em \(\lambda\).

---

5. Funções one-way e trapdoor

---

6. Modelos teóricos

Random Oracle Model (ROM)

Bellare + Rogaway (CCS '93). Tratamos hash como função aleatória ideal: cada query nova retorna valor uniformemente aleatório. Provas em ROM dão garantia heurística — esquema seguro em ROM pode ser seguro com hash real, mas não é garantido (Canetti-Goldreich-Halevi 1998 mostraram contraexemplos artificiais).

Standard Model

Sem oracles idealizados. Provas mais difíceis mas mais convincentes. Esquemas como RSA-OAEP, Cramer-Shoup, Boneh-Boyen têm versões standard model.

Generic Group Model

Adversário só pode usar operações de grupo (multiplicação, exponenciação) sem explorar representação. Usado para provar lower bounds (Shoup 1997, Maurer 2005).

Universal Composability (UC)

Canetti 2001. Framework para provar segurança composicional: se F é UC-seguro, é seguro em qualquer protocolo maior. Ideal para protocolos multi-party.

---

7. Hierarquia de criptografia

Simétrica vs assimétrica

Por finalidade

• Confidencialidade: encryption (AES, ChaCha20, RSA-OAEP, ECIES).
• Integridade: hash, MAC (HMAC, KMAC, Poly1305, CMAC).
• Autenticidade: MAC, assinatura digital.
• Não-repúdio: assinatura digital (não MAC — qualquer um com a chave MAC pode forjar).
• Frescor: nonces, timestamps, sequence numbers.
• Anonimato: ring signatures, group signatures, mix-nets.
• Privacidade computacional: FHE, MPC, ZKP.

---

8. Níveis de segurança

Convencionalmente medidos em bits — significam: melhor ataque conhecido leva \(2^n\) operações.

Regra de equivalência (clássica, NIST SP 800-57):

---

9. Geração de aleatoriedade

Entropy sources

• Hardware: ring oscillators, thermal noise, shot noise, Intel RDRAND, ARM TRNG.
• OS pooling: Linux getrandom(2), /dev/urandom, /dev/random; macOS SecRandomCopyBytes; Windows BCryptGenRandom.
• User input: timing de teclado, mouse — relevante em boot inicial e VMs.

CSPRNGs

• AES-CTR DRBG (NIST SP 800-90A) — saída de AES em CTR mode.
• HMAC-DRBG (NIST SP 800-90A) — popular.
• Hash-DRBG (NIST SP 800-90A).
• Fortuna (Schneier, 2003) — usado em FreeBSD.
• ChaCha20-based — Linux desde 4.8 (2016).
• DualECDRBG ❌ — NIST SP 800-90A original incluía. Backdoor NSA suspeitada e depois confirmada (Snowden); removido 2014.

Regras

• Nunca use Math.random(), rand(), random(), srand(time()).
• Sempre use API criptográfica do OS (getrandom, BCryptGenRandom).
• Seed cuidadosamente após boot — VMs clonadas, embedded, IoT são vulneráveis (Mining Your Ps and Qs, Heninger et al. 2012; ROCA).

---

10. Princípios de design moderno

"Don't roll your own crypto"

Implementar primitivas é fácil; implementar com segurança (sem side-channel, sem bugs sutis) é extremamente difícil. Use bibliotecas auditadas:

• libsodium (alta-nível, design seguro por default).
• NaCl (predecessor de libsodium, DJB).
• BoringSSL (Google fork de OpenSSL).
• OpenSSL 3.x (com FIPS provider quando exigido).
• Tink (Google, high-level).
• Ring (Rust, fork de BoringSSL).
• age (file encryption, Filippo Valsorda).

Constant-time

Todo código que toca segredo deve executar em tempo independente do segredo: sem branches sobre segredo, sem table lookups indexados por segredo, sem multiplicações variáveis em CPUs antigas. Bernstein é o evangelista. AES-NI ajuda (instruções dedicadas).

Misuse-resistance

APIs devem dificultar uso errado:

• NaCl/libsodium — apenas crypto_secretbox (autenticada), sem ECB cru.
• AES-GCM-SIV (Gueron-Lindell) — degrada gracilmente em nonce reuse.
• Tink — keysets versionados, rotação built-in.

Defense in depth

Camadas redundantes. Ex.: TLS + HSTS + HPKP (legacy) / CT (Certificate Transparency); LUKS + dm-verity; signed binaries + boot guard.

Hybrid (clássico + PQC)

Combine algoritmo clássico estabelecido + PQC novo. Ataque precisa quebrar ambos. Padrão em transição (X25519MLKEM768 = X25519 ⊕ ML-KEM-768).

---

11. Métodos de prova

---

12. Quem confia em quê (chain of trust)

Cada elo é um possível ponto de comprometimento. Confidential Computing tenta encurtar a chain isolando workload do host.

---

13. Diferenças culturais: criptografia "americana" vs "europeia"

---

14. Padronizações relevantes

---

15. Bibliografia essencial

• Katz + Lindell, Introduction to Modern Cryptography, CRC Press, 3ª ed. 2020 — texto-padrão de graduação/mestrado.
• Boneh + Shoup, A Graduate Course in Applied Cryptography — gratuito em toc.cryptobook.us.
• Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography (CRC) — clássico técnico, gratuito em cacr.uwaterloo.ca/hac/.
• Schneier, Applied Cryptography, 1996 (datado mas referência cultural).
• Aumasson, Serious Cryptography, No Starch Press 2017 — referência prática moderna.
• Ferguson + Schneier + Kohno, Cryptography Engineering, Wiley 2010.
• Bernstein, Lange, et al., Post-Quantum Cryptography, Springer 2009 (handbook).
• Goldreich, Foundations of Cryptography, 2 volumes Cambridge — teórico, denso.

Online

• IACR ePrint Archive: eprint.iacr.org
• Real World Crypto Symposium proceedings
• CFRG (Crypto Forum Research Group) IETF
• Cryptography Stack Exchange (community Q&A)
• David Wong, Real-World Cryptography (Manning 2021)
• Filippo Valsorda blog filippo.io
• Trail of Bits blog, NCC Group Cryptography Services