Como funcionam as funções hash unidirecionais?(Editado)

https://stackoverflow.com/questions/2112685

22-09-2019
|

Pergunta

Eu li o artigo da Wikipedia sobre hashes md5, mas ainda não consigo entender como um hash não pode ser "reconstituído" de volta ao texto original.

Alguém poderia explicar para alguém que sabe muito pouco sobre criptografia como isso funciona?Que parte da função a torna unidirecional?

Solução

Como todo mundo até agora simplesmente definiu o que era uma função de hash, eu vou morder.

Uma função unidirecional não é apenas uma função de hash-uma função que perde informações-mas uma função f para o qual, dada uma imagem y ("SE" ou 294 em respostas existentes), é difícil encontrar um x de forma x tal que f(x)=y.

É por isso que eles são chamados de ida: você pode calcular uma imagem, mas não consegue encontrar uma pré-imagem para uma determinada imagem.

Nenhuma das funções de hash comuns propostas até agora nas respostas existentes tem essa propriedade. Nenhum deles são funções de hash criptográfico unidirecional. Por exemplo, dado "SE", você pode pegar facilmente a entrada "SXXXE", uma entrada com a propriedade que X-Encode ("Sxxxe") = SE.

Não há funções unidirecionais "simples". Eles precisam misturar suas entradas tão bem que não apenas você não reconhece a entrada na saída, mas Você também não reconhece outra entrada.

O SHA-1 e o MD5 costumavam ser funções de mão única populares, mas ambas estão quase quebradas (o especialista sabe como criar pré-imagens para determinadas imagens ou quase capaz de fazê-lo). Há um concurso em andamento para escolher um novo padrão, que será nomeado SHA-3.

Uma abordagem óbvia para inverter uma função unidirecional seria calcular muitas imagens e mantê-las em uma tabela associada a cada imagem a pré-imagem que a produziu. Para tornar isso impossível na prática, toda a função unidirecional tem uma grande saída, pelo menos 64 bits, mas possivelmente muito maior (até, digamos, 512 bits).

EDIT: Como a maioria das funções de hash criptográfica funciona?

Geralmente eles têm em sua essência uma única função que faz transformações complicadas em um bloco de bits (a Bloqueie a cifra). A função deve ser quase bijetiva (não deve mapear muitas seqüências para a mesma imagem, porque isso causaria fraquezas mais tarde), mas não precisa ser exatamente bijetivo. E essa função é iterada um número fixo de vezes, o suficiente para tornar a entrada (ou qualquer entrada possível) impossível de reconhecer.

Tomar o exemplo de Meada, um dos fortes candidatos ao contexto SHA-3. Sua função principal é iterada 72 vezes. O único número de iterações para as quais os criadores da função sabem como relacionar as saídas com algumas entradas é 25. Eles dizem que ele tem um "fator de segurança" de 2,9.

Outras dicas

Pense em um hash realmente básico - para a sequência de entrada, retorne a soma dos valores ASCII de cada caractere.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

Agora, dado o valor de hash de 294, você pode dizer qual era a string original? Obviamente, não, porque 'ABC' e 'CBA' (e inúmeros outros) dão o mesmo valor de hash.

As funções de hash criptográfico funcionam da mesma maneira, exceto que obviamente o algoritmo é muito mais complexo. Sempre haverá colisões, mas se você conhece string s hashes para h, então deve ser muito difícil ("computacionalmente inviável") para construir Outra string que também tem para h.

Atirando para uma analogia simples aqui, em vez de uma explicação complexa.

Para começar, vamos dividir o assunto em duas partes, operações unidirecionais e hash. O que é uma operação unidirecional e por que você quer uma?

Operações de uma maneira são chamadas assim porque não são reversíveis. A maioria das operações típicas, como adição e multiplicação, pode ser revertida, enquanto a divisão Modulo não pode ser revertida. Por que isso é importante? Como você deseja fornecer um valor de saída que 1) é difícil de duplicar sem as entradas originais e 2) não fornece como descobrir as entradas da saída.

Reversível

Adição:

4 + 3 = 7

Isso pode ser revertido pegando a soma e subtraindo um dos adição

7 - 3 = 4

Multiplicação:

4 * 5 = 20

Isso pode ser revertido pegando o produto e dividindo por um dos fatores

20 / 4 = 5

Não é reversível

Divisão Modulo:

22 % 7 = 1

Isso não pode ser revertido porque não há operação que você possa fazer com o quociente e o dividendo para reconstituir o divisor (ou vice -versa).

Você pode encontrar uma operação para preencher onde '?' é?

1  ?  7 = 22  
1  ?  22 = 7

Com isso dito, as funções de hash unidirecional têm a mesma qualidade matemática que a divisão Modulo.

Por que isso é importante?

Digamos que eu lhe dei uma chave para um armário em um terminal de ônibus que tenha mil armários e pedi para você entregá -lo ao meu banqueiro. Sendo o cara inteligente que você é, para não mencionar suspeito, você imediatamente procuraria a chave para ver qual número de armário está escrito na chave. Sabendo disso, eu fiz algumas coisas desonestas; Primeiro, encontrei dois números que, quando divididos usando a divisão Modulo, me dão um número na faixa entre 1 e 1000, segundo, em segundo lugar, apagarei o número original e escrevi nele o divisor do par de números, segundo eu escolhi um terminal de ônibus que tem um Guarda protegendo os armários de criminosos, deixando as pessoas tentarem um armário por dia com a chave, terceiro, o banqueiro já conhece o dividendo, então, quando ele recebe a chave, ele pode fazer as contas e descobrir o restante e saber qual armário abrir.

Se eu escolher os operandos com sabedoria, posso me aproximar de um relacionamento individual entre o quociente e o dividendo, o que o obriga a experimentar cada armário porque a resposta espalha os resultados das entradas possíveis sobre o alcance dos números desejados, os armários disponível no terminal. Basicamente, isso significa que você não pode adquirir nenhum conhecimento sobre o restante, mesmo que conheça um dos operando.

Então, agora posso 'confiar' para entregar a chave ao seu legítimo proprietário sem me preocupar com o fato de você poder adivinhar facilmente qual armário ele pertence. Claro, você pode pesquisar em força bruta em todos os armários, mas isso levaria quase 3 anos, muito tempo para o meu banqueiro usar a chave e esvaziar o armário.

Veja as outras respostas para obter mais detalhes sobre as diferentes funções de hash.

Aqui está um exemplo muito simples. Suponha que sou um criptografista iniciante e crio uma função de hash que faz o seguinte:

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

Agora aqui está o teste. SimpleHash(specialFile) é 0. Qual foi o meu arquivo original?

Obviamente, não há como saber (embora você provavelmente possa descobrir com muita facilidade que meu hash é baseado no comprimento do arquivo). Não há como "reconstituir" meu arquivo com base no hash porque o hash não contém tudo o que meu arquivo fez.

Um hash é uma codificação (muito) com perdas.

Para dar um exemplo mais simples, imagine uma codificação fictícia de 2 letras de uma palavra de 5 letras chamada X-codificação. O algoritmo para o codificação X é simples: pegue a primeira e a última letras da palavra.

Então,

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

Claramente, você não pode reconstruir o molho a partir de sua codificação SE (assumindo que nossa gama de entradas possíveis é todas as palavras de 5 letras). A palavra poderia facilmente ser espaço.

Como um aparte, o fato de o molho e o espaço produzirem se como uma codificação é chamada de colisão, e você pode ver que a codificação X não faria um hash muito bom. :)

Em termos simples, uma função hash funciona criando uma grande confusão nos dados de entrada.

Ver MD5 por exemplo.Ele processa dados de entrada em blocos de 512 bits.Cada bloco é dividido em 16 palavras de 32 bits.Existem 64 etapas, cada etapa usando uma das 16 palavras de entrada.Portanto, cada palavra é usada quatro vezes no decorrer do algoritmo.É daí que vem a unidirecionalidade:qualquer bit de entrada é inserido em vários locais e, entre duas dessas entradas, a função mistura todos os dados atuais para que cada bit de entrada impacte a maior parte do estado de execução de 128 bits.Isso evita que você inverta a função ou calcule uma colisão observando apenas uma parte dos dados.Você precisa observar todos os 128 bits, e o espaço dos blocos de 128 bits é muito amplo para ser percorrido com eficiência.

Agora, o MD5 não faz um bom trabalho, pois podem ser encontradas colisões para essa função.Do ponto de vista do criptógrafo, MD5 é uma função de criptografia rotacionada.O processamento de um bloco de mensagem M (512 bits) usa um estado de entrada V (um valor de 128 bits) e calcula o novo estado V' como V' = V + E(M, V) onde '+' é uma palavra- adição sábia, e 'E' passa a ser uma função de criptografia simétrica (também conhecida como 'cifra de bloco') que usa M como chave e V como a mensagem a ser criptografada.Olhando mais de perto, E can é uma espécie de “rede Feistel estendida”, semelhante à cifra de bloco DES, com quatro quartos em vez de duas metades.Os detalhes não são importantes aqui;o que quero dizer é que o que torna uma função hash "boa", entre as funções hash que usam essa estrutura (chamada "Merkle-Damgård"), é semelhante ao que torna uma cifra de bloco "segura".Os ataques de colisão bem-sucedidos no MD5 usam criptoanálise diferencial, uma ferramenta que foi projetada para atacar cifras de bloco em primeiro lugar.

De uma boa cifra de bloco a uma boa função hash, há uma etapa que não deve ser descartada.Com a estrutura Merkle-Damgård, a função hash é segura se a cifra de bloco subjacente for resistente a "ataques de chave relacionados", uma propriedade bastante obscura contra a qual as cifras de bloco raramente são reforçadas porque, para criptografia simétrica, os ataques de chave relacionados quase não têm qualquer efeito prático. impacto.Por exemplo, a encriptação AES revelou-se não tão resistente a ataques de chaves relacionados como se poderia desejar, e isto não provocou pânico geral.Essa resistência não fazia parte das propriedades procuradas quando o AES foi concebido.Apenas evita transformar o AES em uma função hash.Existe uma função hash chamada Whirlpool, que se baseia em um derivado de Rijndael, sendo "Rijndael" o nome inicial do que se tornou AES;mas a Whirlpool tem o cuidado de modificar as partes de Rijndael que são fracas a ataques importantes relacionados.

Além disso, existem outras estruturas que podem ser usadas para construir uma função hash.As funções padrão atuais (MD5, SHA-1 e a família "SHA-2", também conhecidas como SHA-224, SHA-256, SHA-384 e SHA-512) são funções Merkle-Damgård, mas muitas das possíveis funções sucessores não.Há uma competição em andamento, organizada pelo NIST (a organização federal dos EUA que lida com esse tipo de coisa), para selecionar uma nova função hash padrão, chamada “SHA-3”.Ver esta página para detalhes.No momento, eles estão reduzidos a 14 candidatos de um total de 51 (sem contar uma dúzia de extras que falharam no teste administrativo de envio de uma submissão completa com código que compila e executa corretamente).

Vamos agora dar uma olhada mais conceitual.Uma função hash segura deve se parecer com um oráculo aleatório:um oráculo é uma caixa preta que, quando recebe uma mensagem M como entrada, gera uma resposta h(M) que é escolhido aleatoriamente, uniformemente, no espaço de saída (ou seja,todos nstrings de -bit se o comprimento da saída da função hash for n).Se receber a mesma mensagem M novamente como entrada, o oráculo gera o mesmo valor do anterior.Além dessa restrição, a saída do oráculo em uma entrada não utilizada anteriormente M é imprevisível.Pode-se imaginar o oráculo como um recipiente para um gnomo que joga dados e registra cuidadosamente as mensagens de entrada e os resultados correspondentes em um grande livro, para que ele honre seu contrato com o oráculo.Não há como prever qual será o próximo resultado, pois o próprio gnomo não sabe disso.

Se existir um oráculo aleatório, então inverter a função hash custará 2^n:para se ter uma determinada saída, não há estratégia melhor do que usar mensagens de entrada distintas até que uma delas produza o valor esperado.Devido à seleção aleatória uniforme, a probabilidade de sucesso é 1/(2^n) em cada tentativa, e o número médio de solicitações ao gnomo lançador de dados será 2^n.Para colisões (encontrar duas entradas distintas que produzam o mesmo valor de hash), o custo é de cerca de *1,4*2^(n/2)* (grosso modo, com saídas *1,4*2^(n/2)*, podemos reunir sobre 2^n pares de resultados, cada um com uma probabilidade de 1/(2^n) de correspondência, ou seja,tendo duas entradas distintas que têm a mesma saída).Estes são os melhores que podem ser feitos com um oráculo aleatório.

Portanto, procuramos funções hash que sejam tão boas quanto um oráculo aleatório:eles devem misturar os dados de entrada de tal forma que não possamos encontrar uma colisão com mais eficiência do que custaria simplesmente invocar a função 2^(n/2) vezes.A ruína da função hash é a estrutura matemática, ou seja,atalhos que permitem ao invasor visualizar o estado interno da função hash (que é grande, pelo menos n bits) como uma variação de um objeto matemático que vive em um espaço muito mais curto.30 anos de pesquisa pública sobre sistemas de criptografia simétrica produziram toda uma parafernália de noções e ferramentas (difusão, avalanche, diferenciais, linearidade...) que podem ser aplicadas.O ponto principal, entretanto, é que não temos provas de que um oráculo aleatório possa realmente existir.Nós querer uma função hash que não pode ser atacada.O que nós ter são candidatos à função hash, para os quais nenhum ataque está atualmente conhecido, e, um pouco melhor, temos algumas funções para as quais alguns pode-se provar que tipos de ataque não funcionam.

Ainda há algumas pesquisas a serem feitas.

variedade
Com alguns apertos de olhos, as matrizes associativas se parecem muito com hashes. As principais diferenças foram a falta de % de símbolo nos nomes de hash, e que só se poderia atribuir a eles uma chave por vez. Assim, alguém diria $foo{'key'} = 1;, se apenas @keys = keys(foo);. Funções familiares como cada uma, chaves e valores funcionaram como agora (e o exclusão foi adicionado no Perl 2).

O Perl 3 tinha três tipos de dados inteiros: tinha o símbolo % nos nomes de hash, permitiu que um hash inteiro fosse atribuído de uma só vez e acrescentou o DBMopen (agora descontinuado em favor do empate). O Perl 4 usou as chaves de hash separadas por vírgula para emular matrizes multidimensionais (que agora são melhor tratadas com referências de matriz).

O Perl 5 deu o salto gigante de se referir a matrizes associativas como hashes. (Até onde eu sei, é o primeiro idioma a se referir à estrutura de dados, em vez de "tabela de hash" ou algo semelhante.) Ironicamente, também mudou o código relevante de hash.c para hv.c.

Nomenclatura
Os dicionários, como explicado anteriormente, são coleções não ordenadas de valores indexados por teclas exclusivas. Às vezes, eles são chamados de matrizes ou mapas associativos. Eles podem ser implementados de várias maneiras, uma das quais é usando uma estrutura de dados conhecida como uma tabela de hash (e é isso que Perl se refere como um hash).

O uso de Perl do termo "hash" é a fonte de alguma confusão em potencial, porque a saída de uma função de hash às vezes também é chamada de hash (especialmente em contextos criptográficos) e porque as tabelas de hash geralmente não são chamadas de hashes em nenhum outro lugar.

Para estar do lado seguro, consulte a estrutura de dados como uma tabela de hash e use o termo "hash" apenas em contextos óbvios e específicos de Perl.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow