Funções Hash Criptográficas

Uma função hash criptográfica comprime uma entrada arbitrária em um resumo curto de comprimento fixo de forma unidirecional e resistente a colisões, servindo como um bloco de construção básico para integridade, autenticação e muitos protocolos de nível superior.

Definition

Uma função hash criptográfica é uma função determinística que mapeia entradas de comprimento arbitrário para uma saída de comprimento fixo (resumo) de tal forma que é inviável encontrar uma pré-imagem, uma segunda pré-imagem ou quaisquer duas entradas distintas que produzam a mesma saída.

Scope

Este tópico aborda as propriedades de segurança das funções hash (resistência à pré-imagem, à segunda pré-imagem e à colisão), suas construções internas (Merkle-Damgaard, sponge), as famílias padronizadas SHA-2 e SHA-3, e aplicações como verificação de integridade, armazenamento de senhas, compromisso e prova de trabalho. Ele aborda ataques criptoanalíticos, incluindo o limite de aniversário e as quebras de MD5 e SHA-1. Exclui códigos de autenticação com chave, que são tratados sob códigos de autenticação de mensagem, embora muitos MACs sejam construídos a partir de funções hash.

Core questions

• O que distingue uma função hash criptográfica de uma soma de verificação comum ou função de tabela hash?
• Por que a resistência à pré-imagem, à segunda pré-imagem e à colisão são distintas, e como elas se relacionam?
• Por que o paradoxo do aniversário limita a resistência à colisão à metade do comprimento do resumo?
• Como as construções Merkle-Damgaard e sponge estendem uma compressão de tamanho fixo para uma entrada arbitrária?
• Como as funções hash são usadas para comprometer dados, verificar a integridade e armazenar senhas?

Key concepts

• resumo da mensagem
• resistência à pré-imagem
• resistência à segunda pré-imagem
• resistência à colisão
• ataque de aniversário
• construção Merkle-Damgaard
• construção sponge (Keccak)
• ataque de extensão de comprimento
• prova de trabalho

Key theories

Resistência à colisão e o limite de aniversário

Devido ao paradoxo do aniversário, um ataque genérico de busca de colisão em um hash de n bits é bem-sucedido em cerca de 2^(n/2) operações; a resistência à colisão, portanto, requer resumos aproximadamente o dobro do nível de segurança desejado (por exemplo, 256 bits para segurança de 128 bits).

Construções iteradas e sponge

O paradigma Merkle-Damgaard constrói um hash completo iterando uma função de compressão de entrada fixa sobre blocos de mensagem; a construção sponge usada pelo SHA-3 (Keccak) absorve a entrada e extrai a saída de um grande estado de permutação, evitando fraquezas de extensão de comprimento.

Mechanisms

Um hash Merkle-Damgaard preenche a mensagem, divide-a em blocos e aplica iterativamente uma função de compressão que mistura cada bloco em um valor de encadeamento em execução, produzindo o valor final como o resumo. A construção sponge do SHA-3, em vez disso, absorve blocos de mensagem por meio de XORing em parte de um grande estado permutado pela função Keccak-f, e então extrai bits de resumo, o que evita a propriedade de extensão de comprimento inerente ao Merkle-Damgaard simples.

Clinical relevance

As funções hash são onipresentes: elas verificam a integridade do download de software, ancoram assinaturas digitais (que assinam um hash, não o documento inteiro), indexam conteúdo em Git e redes de entrega de conteúdo, protegem o armazenamento de senhas por meio de funções lentas de derivação de chave (bcrypt, Argon2) e fornecem a prova de trabalho e as árvores Merkle subjacentes às blockchains. A quebra prática da resistência a colisões de MD5 e SHA-1 forçou a migração para SHA-2 em toda a internet.

Evidence & guidelines

SHA-2 (SHA-256, SHA-512) é especificado em FIPS 180-4 e SHA-3 em FIPS 202; ambos são aprovados pelo NIST. MD5 e SHA-1 são descontinuados para uso de segurança após ataques de colisão demonstrados (sendo a colisão SHAttered SHA-1 de 2017 um marco). Para armazenamento de senhas, os padrões recomendam funções resistentes à memória, como Argon2, em vez de hash simples.

History

A família MD (MD4 e MD5 de Rivest) e o SHA-0/SHA-1 projetados pela NSA dominaram a década de 1990. Os ataques de colisão de Xiaoyun Wang (2004-2005) quebraram o MD5 e enfraqueceram o SHA-1, o que levou à competição aberta SHA-3 do NIST (2007-2012), vencida pelo design sponge Keccak de Bertoni, Daemen, Peeters e Van Assche. O SHA-1 foi praticamente quebrado pela colisão SHAttered em 2017.

Key figures

• Ralph Merkle
• Ivan Damgaard
• Guido Bertoni
• Joan Daemen
• Xiaoyun Wang

Seminal works

• nist2015sha3
• katz2020
• menezes1996

Frequently asked questions

Por que não posso simplesmente fazer o hash de uma senha e armazenar o resumo?

Hashes criptográficos simples são rápidos, o que permite que os atacantes tentem bilhões de palpites por segundo contra um banco de dados roubado. O armazenamento de senhas, em vez disso, usa funções deliberadamente lentas, com sal e resistentes à memória (bcrypt, scrypt, Argon2) para que a força bruta de cada senha seja cara.

O SHA-256 está quebrado agora que o SHA-1 está?

Não. SHA-1 e SHA-256 são algoritmos diferentes; os ataques de colisão no SHA-1 não se transferem para o SHA-2. O SHA-256 permanece inquebrável e é o hash de propósito geral recomendado, juntamente com o SHA-3.