One-Way Functions

Tópicos

• Preâmbulo
• Funções de Hash
• Message Authentication Codes (MAC)
• Key-Derivation Functions (KDF)

Preâmbulo

A segurança de técnicas criptográficas, em alguns casos, depende do bom funcionamento e garantia de funções que operam apenas num sentido.

Definição de uma função One-Way

A function $f:A\to B$ is one-way when, given some element $x:A$, it is easy to compute $f(x):B$, but giving any $y:B$ in the range of $f$, is very difficult to find some $x:A$ such that $y=f(x)$ (a pseudo-inverse of $y$).

A existência de funções One-Way depende, também, da “não resolução” do problema $P\ne NP$¹.

Funções de Hash

São um exemplo mais concreto de funções One-Way. Estas, transformam um número arbitrário de bits num range de tamanho fixo. $H:{0,1}^{\ast }\to {0,1}^n$ No entanto, colisões podem ocorrer, com uma certa probabilidade, que depende do espaço amostral do contradomínio.

Exemplos de funções de hash

• MD5 - broken
• SHA-1 - broken
• SHA-2 - SHA-1 com segurança acrescida
• SHA-3 - design um pouco diferente do SHA-2
• …

Aplicações de funções de hash

• Message Authentication Codes (MAC)
• Key-Derivation Functions (KDF)
• Geradores pseudo-aleatórios seguros
• Block Ciphers
• …

Message Authentication Codes (MAC)

Pretendem resolver o problema da não-garantia de integridade por parte das funções de hash. O código gerado é baseado num segredo secreto que apenas as partes legítimas (remetente e destinatário) conhecem.

Exemplos de algoritmos

• Poly1305

HMAC

Construção de um MAC a partir de uma função de hash. Neste caso, até são performadas duas passagens pela função, de forma a evitar ataques de length extension².

Nota sobre a utilização conjunta com o SHA-3

By design, o SHA-3 não é vulnerável a ataques de length extension. Ou seja, a utilização de HMAC nesse caso é redundante.

Key-Derivation Functions (KDF)

Permitem a derivação de chaves a partir de material criptográfico secreto. Por exemplo, derivar uma chave a partir de uma password ou passphrase ou até mesmo de um master secret acordado a partir de um protocolo de handshaking.

É ainda interessante pensar em KDFs como uma forma de derivar várias chaves diferentes a partir de um mesmo segredo criptográfico. Cumprindo assim o princípio de que uma chave só deve ser usada para um e um só princípio.

Password-Based

Derivação a partir de passwords.

Problemas

• Baixa entropia
• Vulnerável a ataques de enumeração

Para minimizar os tais problemas, deve ser utilizado um salt. Um número aleatório que randomiza o output da função One-Way.

Exemplos

• PBKDF2

Proteção de passwords

Passwords não devem ser guardadas em plaintext numa base de dados. Devem, para isso, ser utilizados algoritmos de hashing criptográfico. Por exemplo, argon2 ou bcrypt.

Referências

Hashing Algorithms and Security - Computerphile Securing Stream Ciphers (HMAC) - Computerphile

Footnotes

1. Consultar P versus NP problem - Wikipedia. ↩

2. Consultar Length extension attack. ↩