06 — Hash, MAC, KDF

Funções hash (one-way, collision-resistant), Message Authentication Codes (MACs), Key Derivation Functions (KDFs). Componentes fundamentais que aparecem em todo protocolo.

1. Funções hash criptográficas — propriedades

\(H: \{0,1\}^* \to \{0,1\}^n\) deve satisfazer:

Para \(n = 256\): collision custa \(2^{128}\) (≥ AES-128). Por isso SHA-256 oferece "128 bits de segurança" para colisões.

Propriedades adicionais úteis

• Pseudorandomness: output indistinguível de aleatório.
• Avalanche: 1 bit muda no input → ~50% bits mudam no output.
• Length extension resistance (não-MD construções têm).
• Indifferentiability from RO (sponge construction).

2. Hash funções históricas

MD2 (Rivest 1989) ❌

128 bits, 8-bit operations. Lento. Collisions found 1995 (Rogier-Chauvaud). Não use.

MD4 (Rivest 1990) ❌

128 bits, faster. Quebrado em 1995 (Dobbertin); collision em 1996, prática em minutos em 2007 (Wang). Ainda usado em NTLM password hashing (Windows) — vulnerável.

MD5 (Rivest 1991) ❌

128 bits, Merkle-Damgård. RFC 1321. Workhorse dos 1990s.

Histórico de quebras:

• 1993: Den Boer + Bosselaers — pseudo-collision.
• 1996: Dobbertin — collision in compression function.
• 2004: Wang Xiaoyun + Yu — primeira colisão prática (rump session CRYPTO '04).
• 2005: Lenstra-Wang-Weger — falsifica X.509 certificates.
• 2008: Marc Stevens et al. — chosen-prefix collision; forja rogue CA certificate assinada por RapidSSL.
• 2012: Flame malware (descoberto) usa MD5 chosen-prefix collision para forjar certificado Microsoft Windows Update. Estima-se desenvolvido por governo.

Status: collision em segundos em CPU comum. Não use para nada criptográfico. Ainda OK para checksums não-adversarial (file integrity em mirror).

SHA-0 (NIST 1993) ❌

160 bits. FIPS 180. Retirado em 1995 sem explicação pública (suspeita NSA fix).

SHA-1 (NIST 1995) ❌

160 bits. FIPS 180-1. Workhorse 1995–2010.

Quebras:

• 2005: Wang+Yin+Yu — 2^{69 operações (abaixo de 2}80 ideal).
• 2017: SHAttered (Stevens, Bursztein, Karpman, Albertini, Markov — Google + CWI) — primeira colisão prática com chosen prefix. Custou ~110 GPU-anos / US$110k em cloud. Demo: dois PDFs distintos com mesmo hash.
• 2020: Shambles (Leurent + Peyrin) — chosen-prefix collision prática em ~US$45k. Permite forjar GPG/X.509 com identidade arbitrária.

Status: deprecated em qualquer contexto criptográfico. Removido de TLS 1.3, Chrome/Firefox certs desde 2017, OpenSSH desde 2020. Aceitável só em HMAC-SHA1 (HMAC sobrevive a collisions mas migrar).

SHA-2 family (NIST 2001) ✅

FIPS 180-2 / 180-4. Merkle-Damgård com Davies-Meyer compression. Versões:

Length extension attack: dado \(H(m)\) e \(|m|\), atacante pode computar \(H(m \\\| pad \\\| m')\) sem saber \(m\). Por isso HMAC usa estrutura específica.

Status: SHA-256 e SHA-512 sem quebra prática em 23 anos. Padrão moderno. Hardware: Intel SHA Extensions (desde Goldmont 2016), ARM Crypto Extensions.

SHA-3 / Keccak (NIST 2015) ✅

FIPS 202. Keccak ganhou competição NIST SHA-3 (2007–2012, 64 candidatos). Designers: Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche (STMicroelectronics).

Não-Merkle-Damgård — usa sponge construction:

1. Absorb: XOR plaintext em "rate" do state; permute (Keccak-f[1600]).
2. Squeeze: extrai bits do rate; permute para mais.

Permutação Keccak-f[1600] = state 1600 bits, 24 rounds de θρπχι.

XOF (Extendable Output Function): arbitrary-length output. Usado em padding (Kyber, Dilithium), key stretching.

Imune a length extension por design (sponge absorb sempre XOR-com-padding antes da última permutação).

Performance: software ~2× mais lento que SHA-256 (sem hardware accel). Hardware barato em ASICs.

BLAKE2 / BLAKE3

BLAKE foi finalista SHA-3 (perdeu para Keccak). BLAKE2 (Aumasson, Neves, Wilcox-O'Hearn, Winnerlein 2012) — refinement.

• BLAKE2b: 64-bit ops, output até 64 bytes.
• BLAKE2s: 32-bit ops, output até 32 bytes.
• Built-in keyed mode (substitui HMAC); personalization; tree mode.
• ~3× mais rápido que SHA-256 em software, ~1.5× mais rápido que SHA-512.
• RFC 7693.

BLAKE3 (O'Connor, Aumasson, Neves, Wilcox-O'Hearn 2020):

• Tree-based, arbitrary parallelism.
• ~10× mais rápido que SHA-256 em CPU moderna.
• ~SHA-3 internals (ChaCha-like) com tree mode.
• Output XOF até 2^64 bytes.
• Usado em IPFS recente, OpenZFS performance forks, age (parcialmente).

RIPEMD-160 / RIPEMD-256 / RIPEMD-320

European response em meio aos 1990s. RIPEMD-160 ainda usado em Bitcoin addresses (HASH160 = RIPEMD160(SHA256(pubkey))). RIPEMD-128 broken; RIPEMD-160 sem ataque prático mas só 80 bits collision security — abaixo de SHA-256.

Whirlpool (Rijmen + Barreto 2000)

512-bit hash baseado em AES-like Miyaguchi-Preneel. ISOIEC 10118-3. Pouco uso prático; superado por SHA-23.

Streebog (GOST R 34.11-2012, Rússia)

256/512 bit. Padrão obrigatório em sistemas estatais russos.

SM3 (China GM/T 0004-2012)

256 bits, Merkle-Damgård. Obrigatório em sistemas chineses. Similar a SHA-256 em estrutura.

3. Recomendações de hash (2026)

Anti-patterns

❌ MD5, SHA-1 em contexto criptográfico. ❌ Truncar SHA-256 abaixo de 128 bits sem análise. ❌ Usar hash sem salt como password storage (ver §KDFs). ❌ Usar hash criptográfico em hashmap interno (DoS via collision flooding). ❌ Assumir que hash de string conhecida é "secret" (rainbow tables).

4. MACs — Message Authentication Codes

MAC garante integridade + autenticidade (mas não não-repúdio, porque receiver pode forjar).

Interface: \(\text{MAC}_k(m) = T\); verificação compara tag.

HMAC (RFC 2104, 1996)

Bellare + Canetti + Krawczyk. Padrão universal. FIPS 198-1.

$\(\text{HMAC}(k, m) = H((k \oplus opad) \\\| H((k \oplus ipad) \\\| m))\)$

onde \(opad = 0x5C5C\dots\), \(ipad = 0x3636\dots\).

• Funciona com qualquer hash (HMAC-SHA256, HMAC-SHA3-256, HMAC-BLAKE2b).
• Resistente a length extension (estrutura dupla).
• Provavelmente seguro sob assumption de hash PRF (Bellare 2006).
• HMAC-SHA-1 ainda OK porque collision em hash ≠ HMAC forge.

KMAC (NIST SP 800-185, 2016)

MAC nativo de Keccak/SHA-3. Mais eficiente que HMAC-SHA3 (sem dupla compressão).

Poly1305

Bernstein 2005. Polynomial MAC em GF(\(2^{130} - 5\)). One-time MAC — exige nonce único. Sempre usado combinado: ChaCha20-Poly1305, AES-GCM-Poly1305 variants. Velocíssimo (3 cyclesbyte ARM, ~1 cyclebyte com VEC).

CMAC (NIST SP 800-38B, RFC 4493)

CBC-MAC variante com subkeys. AES-CMAC padrão.

GMAC

Tag-only mode do GCM (sem encryption). Usado quando só autenticidade é necessária.

SipHash (Aumasson + Bernstein 2012)

Não para mensagens longas; otimizada para short inputs (até alguns KB). Resiste a hash flooding (DoS contra hashmap). Default keyed hash em hashmap interno de Rust, Python (3.4+), Ruby, Go, Perl, Haskell.

Anti-patterns

❌ MAC truncado abaixo de 64 bits. ❌ MAC sem nonce/IV em encrypt-then-MAC. ❌ Não-constant-time comparison (timing leak na verificação) — use subtle.ConstantTimeCompare / crypto.timingSafeEqual. ❌ Usar mesma chave para encrypt e MAC (derive via HKDF).

5. KDFs — Key Derivation Functions

KDF para chaves criptográficas: HKDF

HKDF (Krawczyk + Eronen, RFC 5869, 2010). Two-phase:

prk = HMAC(salt, ikm)            // Extract
okm = HMAC(prk, info \\\| 0x01)
       \\\| HMAC(prk, okm[0..] \\\| info \\\| 0x02) ...   // Expand

• salt: público, idealmente random (mas zero OK).
• ikm: input keying material (DH shared secret, master key).
• info: context binding (string identificador do uso).
• okm: output, qualquer comprimento.

Usado em TLS 1.3 key schedule, Signal Protocol, Noise, MLS. Padrão moderno.

Outras KDFs

• NIST SP 800-108 — KDF in counter mode, feedback, double pipeline.
• X9.63 KDF — usado em ECIES legacy.
• Concat KDF — simples; usado em JOSE.

Password-based KDFs (PBKDF)

Senhas têm baixa entropia (humano-memorável). Atacante faz dictionary attack. KDF de senha torna isso caro intencionalmente (memory, CPU).

PBKDF2 (RSA Labs 2000; RFC 8018)

PBKDF2(P, S, c, dkLen) = HMAC(P, S \\\| 1) \\\| HMAC(P, S \\\| 2) ...

• \(c\) = iterations (recomendado 600k para SHA-256 em 2026; OWASP).
• Fácil GPU acceleration → fraco contra atacante moderno.
• Ainda OK para legacy compatibility.
• FIPS-aprovado.

bcrypt (Provos + Mazières 1999)

Baseado em Blowfish key schedule modificado (caro de inicializar). Memory: ~4 KB (fixo).

• Cost parameter \(\text{cost}\): \(2^{\text{cost}}\) iterações.
• Limite de senha: 72 bytes (truncation).
• Não FIPS.
• Adoção massiva: Linux PAM legacy, Ruby/Rails default, PHP password_hash.

scrypt (Percival 2009; RFC 7914)

Memory-hard: força atacante a usar memória, não só CPU. Anti-ASIC inicialmente.

• Parâmetros: \(N\) (CPU/memory cost), \(r\) (block size), \(p\) (parallelism).
• 2026 OWASP: \(N = 2^{17}\), \(r = 8\), \(p = 1\) → ~64 MB memory.
• Tirado de Litecoin proof-of-work.

Argon2 (Biryukov + Dinu + Khovratovich 2015)

Vencedor PHC (Password Hashing Competition 2013–2015). RFC 9106.

Variantes:

• Argon2d: data-dependent memory access (resistente a TMTO; vulnerável side-channel).
• Argon2i: data-independent (resistente side-channel; menos resistente a TMTO).
• Argon2id: recomendado — híbrido: 1ª passada data-independent, depois data-dependent.

Parâmetros: memory \(m\), iterations \(t\), parallelism \(p\).

OWASP 2026 recommendation: Argon2id, \(m = 19\) MiB, \(t = 2\), \(p = 1\) (mínimo) — ajustar pra hardware atual com limite "1 segundo por verify" como balizador.

Comparação

6. Construções relacionadas

Merkle trees

Hash tree. Folhas = \(H(\text{leaf}_i)\); nós = \(H(\text{left} \\\| \text{right})\). Root é compromisso a todos os dados.

Inclusion proof: \(O(\log n)\) tamanho. Permite provar que \(x\) está no set sem revelar set inteiro.

Aplicações:

• Git commit hashes (tree de blobs).
• Bitcoin block merkle root.
• Certificate Transparency (Google).
• Verkle trees em Ethereum proposed.
• BitTorrent (BEP 30).

HMAC-based One-Time Password (HOTP, RFC 4226)

$\(\text{HOTP}(k, c) = \text{truncate}(\text{HMAC-SHA1}(k, c), 6\text{ digits})\)$

Counter-based OTP. Movido para event-based (Yubikey HOTP) e time-based (TOTP).

TOTP (RFC 6238)

\(\text{TOTP} = \text{HOTP}(k, \lfloor T/30 \rfloor)\). Google Authenticator, Authy, FreeOTP, 1Password, etc.

KDF for SRP, OPAQUE

PAKE (Password-Authenticated Key Exchange) protocols use specific KDF construction to avoid offline dictionary attack server-side.

7. Hash baseados em problemas duros (RPM-friendly)

• Pedersen commitments: \(\text{Com}(m, r) = g^m h^r\) — perfectly hiding, computationally binding (under DLP). Usado em ZK.
• VDF (Verifiable Delay Function): hash que toma \(T\) segundos sequenciais (irreduzível em paralelo). Wesolowski 2019, Pietrzak 2019. Usado em Ethereum lottery seeding, Filecoin proof-of-replication.
• VRF (Verifiable Random Function): hash com proof; verificável publicamente determinístico. RFC 9381. Usado em DNSSEC (NSEC5), blockchains.

8. Tabela resumo — qual usar onde

9. Referência cruzada

• Block ciphers usados em CBC-MAC, GMAC: 04-simetrica.md.
• Hash-based signatures (SLH-DSA, XMSS, LMS): 08-pos-quantica.md.
• Side-channel em HMAC (timing): 11-ataques.md.
• Ataques colisão (MD5 chosen-prefix, SHA-1 SHAttered): 13-incidentes.md.