06 — Hash, MAC, KDF

Funções hash (oneway, collisionresistant), 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}\) (≥ AES128). Por isso SHA256 oferece "128 bits de segurança" para colisões.

Propriedades adicionais úteis

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

2. Hash funções históricas

MD2 (Rivest 1989) ❌

128 bits, 8bit operations. Lento. Collisions found 1995 (RogierChauvaud). *ão use.*

MD4 (Rivest 1990) ❌

128 bits, faster. *uebrado*em 1995 (Dobbertin); collision em 1996, *rá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.

*istórico de quebras*

• 1993: Den Boer + Bosselaers — pseudo-collision.
• 1996: Dobbertin — collision in compression function.
• 2004: *ang Xiaoyun*+ Yu — primeira colisão prática (rump session CRYPTO '04).
• 2005: LenstraWangWeger — falsifica X.509 certificates.
• 2008: *arc Stevens*et al. — *hosen-prefix collision* forja *ogue CA certificate*assinada por RapidSSL.
• 2012: *lame*malware (descoberto) usa MD5 chosenprefix collision para forjar certificado Microsoft Windows Update. Estimase desenvolvido por governo.

*tatus* collision em segundos em CPU comum. *ã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.

*uebras*

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

*tatus* *eprecated 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 1802 / 1804. MerkleDamgård com DaviesMeyer compression. Versões:

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

*tatus* SHA256 e SHA512 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. *eccak*ganhou competição NIST SHA-3 (2007–2012, 64 candidatos). Designers: *uido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche*(STMicroelectronics).

*ãoMerkleDamgård*— usa *ponge 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 θρπχι.

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

*mune a length extension*por design (sponge absorb sempre XORcompadding antes da última permutação).

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

BLAKE2 / BLAKE3

*LAKE*foi finalista SHA3 (perdeu para Keccak). *LAKE2*(Aumasson, Neves, WilcoxO'Hearn, Winnerlein 2012) — refinement.

• *LAKE2b* 64-bit ops, output até 64 bytes.
• *LAKE2s* 32-bit ops, output até 32 bytes.
• Built-in keyed mode (substitui HMAC); personalization; tree mode.
• ~3× mais rápido que SHA256 em software, ~1.5× mais rápido que SHA512.
• RFC 7693.

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

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

RIPEMD160 / RIPEMD256 / RIPEMD-320

European response em meio aos 1990s. RIPEMD160 ainda usado em *itcoin addresses*(HASH160 = RIPEMD160(SHA256(pubkey))). RIPEMD128 broken; RIPEMD160 sem ataque prático mas só 80 bits collision security — abaixo de SHA256.

Whirlpool (Rijmen + Barreto 2000)

512bit hash baseado em AESlike MiyaguchiPreneel. ISO/IEC 101183. Pouco uso prático; superado por SHA-2/3.

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, MerkleDamgård. Obrigatório em sistemas chineses. Similar a SHA256 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 *ntegridade + 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. *IPS 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 (HMACSHA256, HMACSHA3256, HMACBLAKE2b).
• Resistente a length extension (estrutura dupla).
• *rovavelmente seguro*sob assumption de hash PRF (Bellare 2006).
• HMACSHA1 ainda OK porque collision em hash ≠ HMAC forge.

KMAC (NIST SP 800-185, 2016)

MAC nativo de Keccak/SHA3. Mais eficiente que HMACSHA3 (sem dupla compressão).

Poly1305

Bernstein 2005. Polynomial MAC em GF(\(2^{130} - 5\)). *netime MAC*— exige nonce único. Sempre usado combinado: *haCha20Poly1305* *ESGCMPoly1305*variants. Velocíssimo (3 cyclesbyte ARM, ~1 cyclebyte com VEC).

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

CBCMAC variante com subkeys. *ESCMAC*padrão.

GMAC

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

SipHash (Aumasson + Bernstein 2012)

*ão para mensagens longas* otimizada para *hort inputs*(até alguns KB). Resiste a *ash 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 encryptthenMAC. ❌ Nãoconstanttime 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

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

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

• *alt* público, idealmente random (mas zero OK).
• *km* input keying material (DH shared secret, master key).
• *nfo* context binding (string identificador do uso).
• *km* output, qualquer comprimento.

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

Outras KDFs

• *IST SP 800-108*— KDF in counter mode, feedback, double pipeline.
• *9.63 KDF*— usado em ECIES legacy.
• *oncat 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 *aro 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.
• *IPS-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).
• *ão FIPS*
• Adoção massiva: Linux PAM legacy, Ruby/Rails default, PHP password_hash.

scrypt (Percival 2009; RFC 7914)

*emoryhard* força atacante a usar memória, não só CPU. AntiASIC 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 proofofwork.

Argon2 (Biryukov + Dinu + Khovratovich 2015)

*encedor PHC*(Password Hashing Competition 2013–2015). *FC 9106*

Variantes:

• *rgon2d* datadependent memory access (resistente a TMTO; vulnerável sidechannel).
• *rgon2i* dataindependent (resistente sidechannel; menos resistente a TMTO).
• *rgon2id* *ecomendado*— híbrido: 1ª passada dataindependent, depois datadependent.

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

*WASP 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.

*nclusion 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).

HMACbased OneTime Password (HOTP, RFC 4226)

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

Counterbased OTP. Movido para eventbased (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 (PasswordAuthenticated Key Exchange) protocols use specific KDF construction to avoid offline dictionary attack serverside.

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

• *edersen commitments* \(\text{Com}(m, r) = g^m h^r\) — perfectly hiding, computationally binding (under DLP). Usado em ZK.
• *DF (Verifiable Delay Function)* hash que toma \(T\) segundos sequenciais (irreduzível em paralelo). Wesolowski 2019, Pietrzak 2019. Usado em Ethereum lottery seeding, Filecoin proofofreplication.
• *RF (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 CBCMAC, GMAC: `04simetrica.md`.
• Hashbased signatures (SLHDSA, XMSS, LMS): 08-pos-quantica.md.
• Sidechannel em HMAC (timing): `11ataques.md`.
• Ataques colisão (MD5 chosenprefix, SHA1 SHAttered): 13-incidentes.md.