Olá, Habr! No mundo da análise de algoritmos criptográficos, o conceito de um oráculo é frequentemente usado. Um oráculo é uma entidade computacional hipotética que pode executar instantaneamente operações criptográficas específicas conforme necessário. Por exemplo, pode fornecer números verdadeiramente aleatórios (um oráculo aleatório) ou criptografar/descriptografar dados com uma chave de criptografia conhecida a priori pelo oráculo (um oráculo de criptografia/descriptografia, respectivamente).
Neste artigo, proponho ir mais longe e considerar um oráculo capaz de encontrar a pré-imagem (ou, mais precisamente, um conjunto de possíveis pré-imagens) de um determinado código hash de uma função hash específica. Como as funções hash são frequentemente usadas em construções mais complexas, vamos analisar e discutir como a presença de tal oráculo afeta as propriedades dos mecanismos criptográficos de nível superior. Como exemplo, consideraremos as construções HMAC (Códigos de Autenticação de Mensagens baseados em Hash).
Oráculo de Busca de Pré-Imagens
Chamaremos o oráculo que sabe como encontrar pré-imagens de códigos hash dados de oráculo de busca de pré-imagens e o denotaremos como P. Suponha que um invasor tenha acesso a tal oráculo, como resultado do qual ele pode solicitar ao oráculo (e receber imediatamente) pré-imagens para um determinado código hash h de uma função hash pré-fixada:
P(h, s) = {c1, c2, ..., cz}
onde s é o comprimento em bits de cada uma das pré-imagens que o invasor deseja obter, e o conjunto de z pré-imagens de um determinado comprimento s encontrado pelo oráculo é denotado por.
Observe que, na ausência de um comprimento fixo das pré-imagens desejadas, seu número é infinito (se a função hash não restringir o tamanho da entrada) ou muito grande, se houver uma restrição no tamanho da entrada (nesse caso, geralmente é muito grande – por exemplo, 2^64 – 1 bit para SHA2-256 [1]). Se o tamanho for fixo, o número de pré-imagens encontradas z pode ser estimado da seguinte forma (com uma distribuição quase uniforme dos códigos hash de saída em relação ao conjunto de valores de entrada):
z ≈ 2^(s - n)
onde n é o tamanho do valor de saída da função hash em bits.
Implica-se aqui que s > n. No entanto, os valores s ≤ n também são aceitáveis; nesses casos, z pode ser interpretado como a probabilidade de encontrar uma pré-imagem para um determinado código hash.
HMAC
Os Códigos de Autenticação de Mensagens baseados em Hash HMAC foram propostos em 1996 [2] e são amplamente utilizados em vários protocolos criptográficos. O cálculo do HMAC é feito da seguinte forma:
HMAC(K, m) = hash(K ⊕ opad || hash(K ⊕ ipad || m))
onde:
mé a mensagem de entrada de tamanho arbitrário (sujeito a possíveis restrições da função hash hash subjacente);Ké a chave secreta para calcular o HMAC, eké o resultado de seu preenchimento ou alinhamento para o tamanho do bloco de dados (bbits) da função hash hash;ipadeopadsão constantesb-bit fixas (padronizadas).
As mensagens de entrada m e seus valores HMAC correspondentes são geralmente conhecidos pelo invasor, pois são transmitidos em texto simples.
Suponha que o invasor tenha um oráculo de busca de pré-imagens e um par conhecido de mensagem m (de comprimento len) e seu código HMAC h, calculado usando a chave (preenchida ou alinhada) k. Pode-se ver que, nesse caso, o invasor obterá facilmente um conjunto de possíveis valores intermediários usando o oráculo:
c = K ⊕ opad || hash(K ⊕ ipad || m)
Pergunta: Nesse caso, o invasor poderá obter o valor correto da chave secreta k (o que lhe permitirá falsificar posteriormente o HMAC de qualquer mensagem com essa chave)?
Metodologia para encontrar a chave secreta
Permito-me propor a seguinte metodologia para determinar a chave secreta k usando o oráculo de busca de pré-imagens P:
Passo 1. Usando o oráculo, o invasor obtém um conjunto de possíveis pré-imagens (chamaremos essas pré-imagens de "externas"):
P(h, b + n) = {c1, c2, ..., cz}
onde s = b + n, ou seja, a cardinalidade deste conjunto é z ≈ 2^(b + n - n) = 2^b
Cada possível pré-imagem ci representa a concatenação de duas partes:
ci = ki || mi
onde:
kié o possível valor da chave desejadakcorrespondente à pré-imagemci;mié a mensagem correspondente à pré-imagemci.
Passo 2. A parte direita de cada possível pré-imagem ci, i = 1,...,z, é "passada" pelo oráculo de busca de pré-imagens para obter outro conjunto de possíveis pré-imagens para cada um deles (chamaremos essas pré-imagens de "internas"):
P(hash(ki ⊕ ipad || mi), b + n) = {c_j1, c_j2, ..., c_jz}
onde c_ji é a j-ésima pré-imagem interna obtida da parte direita da i-ésima pré-imagem externa.
Cada uma das pré-imagens internas também consiste em duas partes:
c_ji = k_ji || m_ji
Nesse caso, outro candidato para as chaves desejadas também é obtido da pré-imagem interna:
k_ji
Passo 3. Para determinar qual dos candidatos a chaves secretas é o correto, uma enumeração completa é realizada sobre os seguintes valores:
k_ji ⊕ ipad
Os critérios para encontrar a chave correta são os seguintes:
hash(k_ji ⊕ ipad || m) = h
No caso (extremamente improvável) de esses valores coincidirem para vários candidatos a chaves, um segundo par m e h é necessário para selecionar o correto deles.
Avaliação da intensidade de trabalho
A intensidade média de trabalho para encontrar a chave HMAC correta (sem levar em consideração os requisitos de memória e possíveis falsas correspondências) de acordo com a metodologia descrita acima pode ser estimada da seguinte forma:
z ≈ 2^bchamadas ao oráculo de busca de pré-imagens;2^bcomparações no processo de enumeração.
Para várias funções hash amplamente utilizadas, podemos fornecer números específicos:
| Função Hash | Tamanho do Bloco (igual ao comprimento da chave k), b, bits | Tamanho do Valor de Saída, n, bits | Tamanho das Pré-imagens, s, bits | Chamadas ao Oráculo | Comparações (limite inferior para len = 1) |
|---|---|---|---|---|---|
| MD5 | 512 | 128 | 640 | 2^511 | 2^896 |
| RIPEMD-160 | 512 | 160 | 672 | 2^511 | 2^864 |
| SHA2-256 | 512 | 256 | 768 | 2^511 | 2^768 |
| SHA2-512 | 1024 | 512 | 1536 | 2^1023 | 2^1536 |
| SHA3-256 | 1088 | 256 | 1344 | 2^1087 | 2^1920 |
| SHA3-512 | 576 | 512 | 1088 | 2^575 | 2^640 |
| Stribog-256 | 512 | 256 | 768 | 2^511 | 2^768 |
| Stribog-512 | 512 | 512 | 1024 | 2^511 | 2^512 |
Como pode ser visto na tabela, a intensidade de trabalho do ataque descrito acima para encontrar a chave secreta HMAC usando um oráculo de busca de pré-imagens é extremamente alta e excede em muitas ordens de magnitude o limite hipotético de aplicabilidade prática, o que é mostrado no exemplo de várias funções hash amplamente utilizadas (e deve ser justo para outras funções hash criptográficas com um tamanho de bloco suficientemente grande).
Conclusão
Assim, pode-se concluir que a construção HMAC é extremamente bem-sucedida e, mesmo que o invasor tenha uma ferramenta tão poderosa como um oráculo de busca de pré-imagens, na verdade é resistente em termos de determinar a chave secreta.
Referências
- FIPS 180-4. Secure Hash Standard (SHS). Agosto de 2015.
- M. Bellare, R. Canetti, H. Krawczyk. Keying Hash Functions for Message Authentication. CRYPTO 1996.