Função de compressão unilateral - One-way compression function

Na criptografia , uma função de compressão unilateral é uma função que transforma duas entradas de comprimento fixo em uma saída de comprimento fixo. A transformação é "unilateral" , o que significa que é difícil, dada uma saída específica, calcular entradas que compactam essa saída. As funções de compactação unilateral não estão relacionadas aos algoritmos convencionais de compactação de dados , que, em vez disso, podem ser invertidos exatamente (compactação sem perdas) ou aproximadamente (compactação com perdas) para os dados originais.

As funções de compressão unilateral são, por exemplo, usadas na construção Merkle – Damgård dentro das funções criptográficas de hash .

As funções de compressão unilateral são freqüentemente construídas a partir de cifras de bloco . Alguns métodos para transformar qualquer cifra de bloco normal em uma função de compressão unilateral são Davies – Meyer , Matyas – Meyer – Oseas , Miyaguchi – Preneel (funções de compressão de bloco único) e MDC-2 / Meyer – Schilling , MDC-4 , Hirose (funções de compressão de comprimento de bloco duplo). Esses métodos são descritos em detalhes mais adiante. ( MDC-2 também é o nome de uma função hash patenteada pela IBM .)

Compressão

Uma função de compressão mistura duas entradas de comprimento fixo e produz uma única saída de comprimento fixo do mesmo tamanho de uma das entradas. Isso também pode ser visto como a função de compressão transforma uma grande entrada de comprimento fixo em uma saída mais curta de comprimento fixo.

Por exemplo, a entrada A pode ter 128 bits, a entrada B 128 bits e eles são compactados em uma única saída de 128 bits. Isso é equivalente a ter uma única entrada de 256 bits compactada em uma única saída de 128 bits.

Algumas funções de compactação não são compactadas pela metade, mas por algum outro fator. Por exemplo, a entrada A pode ter 256 bits e a entrada B 128 bits, que são compactados em uma única saída de 128 bits. Ou seja, um total de 384 bits de entrada são compactados em 128 bits de saída.

A mistura é feita de forma que o efeito de avalanche total seja alcançado. Ou seja, cada bit de saída depende de cada bit de entrada.

Mão única

Uma função unilateral é uma função fácil de calcular, mas difícil de inverter. Uma função de compactação unilateral (também chamada de função hash) deve ter as seguintes propriedades:

• Fácil de calcular: se você tiver alguma entrada (s), é fácil calcular a saída.
• Resistência de pré-imagem: Se um invasor conhece apenas a saída, deve ser inviável calcular uma entrada. Em outras palavras, dada uma saída , deveria ser inviável calcular uma entrada como essa .${\ displaystyle h}$${\ displaystyle m}$${\ displaystyle \ operatorname {hash} (m) = h}$
• Segunda resistência de pré-imagem: Dada uma entrada cuja saída é , deve ser inviável encontrar outra entrada que tenha a mesma saída , ou seja .${\ displaystyle m_ {1}}$${\ displaystyle h}$${\ displaystyle m_ {2}}$${\ displaystyle h}$${\ displaystyle \ operatorname {hash} (m_ {1}) \ neq \ operatorname {hash} (m_ {2})}$
• Resistência à colisão: deve ser difícil encontrar quaisquer duas entradas diferentes que sejam compactadas na mesma saída, ou seja, um invasor não deve ser capaz de encontrar um par de mensagens como essa . Devido ao paradoxo do aniversário (consulte também o ataque do aniversário ), há 50% de chance de uma colisão ser encontrada no momento de aproximadamente onde está o número de bits na saída da função hash. Um ataque à função hash, portanto, não deve ser capaz de encontrar uma colisão com menos de cerca de trabalho.${\ displaystyle m_ {1} \ neq m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2 ^ {n / 2}}$${\ displaystyle n}$${\ displaystyle 2 ^ {n / 2}}$

O ideal seria que a "inviabilidade" na resistência de pré-imagem e na segunda resistência de pré-imagem significasse um trabalho de aproximadamente onde está o número de bits na saída da função hash. No entanto, particularmente para a segunda resistência de pré-imagem, este é um problema difícil. ${\ displaystyle 2 ^ {n}}$${\ displaystyle n}$

A construção Merkle-Damgård

Um uso comum de funções de compressão unilateral é na construção Merkle – Damgård dentro de funções criptográficas de hash. As funções hash mais amplamente usadas, incluindo MD5 , SHA-1 (que está obsoleta) e SHA-2 usam essa construção.

Uma função hash deve ser capaz de processar uma mensagem de comprimento arbitrário em uma saída de comprimento fixo. Isso pode ser conseguido dividindo a entrada em uma série de blocos de tamanhos iguais e operando neles em sequência usando uma função de compressão unilateral. A função de compressão pode ser especialmente projetada para hash ou ser construída a partir de uma cifra de bloco.

O último bloco processado também deve ser preenchido em comprimento , o que é crucial para a segurança dessa construção. Esta construção é chamada de construção Merkle-Damgård . As funções hash mais amplamente utilizadas, incluindo SHA-1 e MD5 , assumem este formato.

Quando preenchimento comprimento (também chamado MD-fortalecimento) é aplicada, os ataques não consegue encontrar colisões mais rápido que o paradoxo do aniversário ( , sendo o tamanho do bloco em bits) se a função usada é de colisão-resistente. Conseqüentemente, a construção de hash Merkle-Damgård reduz o problema de encontrar uma função hash adequada para encontrar uma função de compressão adequada. ${\ displaystyle 2 ^ {n / 2}}$${\ displaystyle n}$${\ displaystyle f}$

Um segundo ataque de pré-imagem (dada uma mensagem que um invasor encontra outra mensagem para satisfazer pode ser feito de acordo com Kelsey e Schneier para uma mensagem -bloqueio de mensagem a tempo . Observe que a complexidade deste ataque atinge um mínimo de para mensagens longas quando e se aproxima quando as mensagens são curtas. ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2 ^ {k}}$${\ displaystyle k \ times 2 ^ {n / 2 + 1} + 2 ^ {n-k + 1}}$${\ displaystyle 2 ^ {3n / 4 + 2}}$${\ displaystyle k = 2 ^ {n / 4}}$${\ displaystyle 2 ^ {n}}$

Construção de cifras de bloco

As funções de compressão unilateral são freqüentemente construídas a partir de cifras de bloco.

As cifras de bloco pegam (como funções de compressão unilateral) duas entradas de tamanho fixo (a chave e o texto simples ) e retornam uma única saída (o texto cifrado ) que é do mesmo tamanho que o texto simples de entrada.

No entanto, as cifras de bloco modernas são apenas parcialmente unilaterais. Ou seja, dado um texto simples e um texto cifrado, é inviável encontrar uma chave que criptografe o texto simples para o texto cifrado. Mas, dado um texto cifrado e uma chave, um texto simples correspondente pode ser encontrado simplesmente usando a função de descriptografia da cifra de bloco. Assim, para transformar uma cifra de bloco em uma função de compressão unilateral, algumas operações extras devem ser adicionadas.

Alguns métodos para transformar qualquer cifra de bloco normal em uma função de compressão unilateral são Davies – Meyer, Matyas – Meyer – Oseas, Miyaguchi – Preneel (funções de compressão de bloco único) e MDC-2, MDC-4, Hirose (duplo - funções de compressão de comprimento de bloco).

As funções de compactação de comprimento de bloco único geram o mesmo número de bits processados ​​pela cifra de bloco subjacente. Conseqüentemente, as funções de compressão de comprimento de bloco duplo produzem duas vezes o número de bits.

Se uma cifra de bloco tem um tamanho de bloco de, digamos, 128 bits, os métodos de comprimento de bloco único criam uma função hash que tem o tamanho de bloco de 128 bits e produz um hash de 128 bits. Os métodos de comprimento de bloco duplo criam hashes com o dobro do tamanho do hash em comparação com o tamanho do bloco da cifra de bloco usada. Portanto, uma cifra de bloco de 128 bits pode ser transformada em uma função hash de 256 bits.

Esses métodos são então usados ​​dentro da construção Merkle – Damgård para construir a função hash real. Esses métodos são descritos em detalhes mais adiante.

Usar uma cifra de bloco para construir a função de compressão unidirecional para uma função hash é geralmente um pouco mais lento do que usar uma função de compressão unidirecional especialmente projetada na função hash. Isso ocorre porque todas as construções seguras conhecidas fazem o agendamento de chave para cada bloco da mensagem. Black, Cochran e Shrimpton mostraram que é impossível construir uma função de compressão unilateral que faça apenas uma chamada para uma cifra de bloco com uma chave fixa. Na prática, velocidades razoáveis ​​são alcançadas, desde que a programação de chave da cifra de bloco selecionada não seja uma operação muito pesada.

Mas, em alguns casos, é mais fácil porque uma única implementação de uma cifra de bloco pode ser usada para uma cifra de bloco e uma função hash. Ele também pode economizar espaço de código em sistemas embarcados muito pequenos , como, por exemplo, cartões inteligentes ou nós em carros ou outras máquinas.

Portanto, a taxa de hash ou taxa dá um vislumbre da eficiência de uma função de hash com base em uma determinada função de compactação. A taxa de uma função hash iterada descreve a proporção entre o número de operações de cifra de bloco e a saída. Mais precisamente, a taxa representa a razão entre o número de bits processados ​​de entrada , o comprimento do bit de saída da cifra de bloco e as operações de cifra de bloco necessárias para produzir esses bits de saída. Geralmente, o uso de menos operações de cifra de bloco resulta em um melhor desempenho geral de toda a função hash, mas também leva a um valor de hash menor, o que pode ser indesejável. A taxa é expressa pela fórmula: ${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle s}$${\ displaystyle n}$

${\ displaystyle R_ {h} = {\ frac {\ left | m_ {i} \ right |} {s \ cdot n}}}$

A função hash só pode ser considerada segura se pelo menos as seguintes condições forem atendidas:

• A cifra de bloco não tem propriedades especiais que a distingam das cifras ideais, como chaves fracas ou chaves que levam a criptografias idênticas ou relacionadas (pontos fixos ou colisões de chaves).
• O tamanho do hash resultante é grande o suficiente. De acordo com o ataque de aniversário, um nível de segurança de 2 ⁸⁰ (geralmente considerado inviável para calcular hoje) é desejável, portanto, o tamanho do hash deve ser de pelo menos 160 bits.
• O último bloco é preenchido com o comprimento adequado antes do hashing. (Consulte a construção Merkle-Damgård .) O preenchimento de comprimento é normalmente implementado e tratado internamente em funções hash especializadas, como SHA-1, etc.

As construções apresentadas abaixo: Davies – Meyer, Matyas – Meyer – Oseas, Miyaguchi – Preneel e Hirose mostraram-se seguras sob a análise da caixa preta . O objetivo é mostrar que qualquer ataque que possa ser encontrado é no máximo tão eficiente quanto o ataque de aniversário sob certas suposições. O modelo de caixa preta assume que uma cifra de bloco é usada, escolhida aleatoriamente em um conjunto que contém todas as cifras de bloco apropriadas. Neste modelo, um invasor pode criptografar e descriptografar livremente quaisquer blocos, mas não tem acesso a uma implementação da cifra de bloco. A função de criptografia e descriptografia são representadas por oráculos que recebem um par de um texto simples e uma chave ou um texto cifrado e uma chave. Os oráculos então respondem com um texto simples ou texto cifrado escolhido aleatoriamente, se o par foi perguntado pela primeira vez. Ambos compartilham uma tabela para esses trigêmeos, um par da consulta e a resposta correspondente, e retornam o registro, se uma consulta for recebida pela segunda vez. Para a prova, existe um algoritmo de localização de colisão que faz consultas escolhidas aleatoriamente aos oráculos. O algoritmo retorna 1, se duas respostas resultarem em uma colisão envolvendo a função hash que é construída a partir de uma função de compressão aplicando esta cifra de bloco (0 mais). A probabilidade de o algoritmo retornar 1 depende do número de consultas que determinam o nível de segurança.

Davies – Meyer

A função de compressão de comprimento de bloco único Davies – Meyer alimenta cada bloco da mensagem ( ) como a chave para uma cifra de bloco. Ele alimenta o valor de hash anterior ( ) como o texto simples a ser criptografado. O texto cifrado de saída também é XORed (⊕) com o valor de hash anterior ( ) para produzir o próximo valor de hash ( ). Na primeira rodada, quando não há nenhum valor de hash anterior, ele usa um valor inicial pré-especificado constante ( ). ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {0}}$

Em notação matemática Davies – Meyer pode ser descrito como:

${\ displaystyle H_ {i} = E_ {m_ {i}} {(H_ {i-1})} \ oplus {H_ {i-1}}}$

O esquema tem a taxa (k é o tamanho da chave):

${\ displaystyle R_ {DM} = {\ frac {k} {1 \ cdot n}} = {\ frac {k} {n}}}$

Se a cifra de bloco usa, por exemplo, chaves de 256 bits, então cada bloco de mensagem ( ) é um pedaço de 256 bits da mensagem. Se a mesma cifra de bloco usa um tamanho de bloco de 128 bits, os valores de hash de entrada e saída em cada rodada são 128 bits. ${\ displaystyle m_ {i}}$

Variações desse método substituem XOR por qualquer outra operação de grupo, como adição em inteiros não assinados de 32 bits.

Uma propriedade notável da construção Davies-Meyer é que mesmo que a cifra de bloco subjacente seja totalmente segura, é possível calcular pontos fixos para a construção: para qualquer um, pode-se encontrar um valor tal que : basta definir . Esta é uma propriedade que as funções aleatórias certamente não possuem. Até agora, nenhum ataque prático foi baseado nesta propriedade, mas deve-se estar ciente desse "recurso". Os pontos fixos podem ser usados ​​em um segundo ataque de pré-imagem (dada uma mensagem , o invasor encontra outra mensagem para satisfazer de Kelsey e Schneier para uma mensagem -bloqueio de mensagem no tempo . Se a construção não permitir a criação fácil de pontos fixos (como Matyas – Meyer – Oseas ou Miyaguchi – Preneel) então este ataque pode ser feito a tempo. Observe que em ambos os casos a complexidade é superior, mas inferior quando as mensagens são longas e quando as mensagens ficam mais curtas, a complexidade do ataque se aproxima . ${\ displaystyle m}$${\ displaystyle h}$${\ displaystyle E_ {m} (h) \ oplus h = h}$${\ displaystyle h = E_ {m} ^ {- 1} (0)}$${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2 ^ {k}}$${\ displaystyle 3 \ times 2 ^ {n / 2 + 1} + 2 ^ {n-k + 1}}$${\ displaystyle k \ times 2 ^ {n / 2 + 1} + 2 ^ {n-k + 1}}$${\ displaystyle 2 ^ {n / 2}}$${\ displaystyle 2 ^ {n}}$${\ displaystyle 2 ^ {n}}$

A segurança da construção Davies – Meyer no Modelo de Cifra Ideal foi comprovada pela primeira vez por R. Winternitz.

Matyas – Meyer – Oseas

A função de compressão unilateral de comprimento de bloco único Matyas – Meyer – Oseas pode ser considerada a dual (o oposto) de Davies – Meyer.

Ele alimenta cada bloco da mensagem ( ) como o texto simples a ser criptografado. O texto cifrado de saída também é XORed (⊕) com o mesmo bloco de mensagem ( ) para produzir o próximo valor hash ( ). O valor de hash anterior ( ) é alimentado como a chave para a cifra de bloco. Na primeira rodada, quando não há nenhum valor de hash anterior, ele usa um valor inicial pré-especificado constante ( ). ${\ displaystyle m_ {i}}$${\ displaystyle m_ {i}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {0}}$

Se a cifra de bloco tiver blocos e tamanhos de chave diferentes, o valor hash ( ) terá o tamanho errado para usar como chave. A cifra também pode ter outros requisitos especiais na chave. Em seguida, o valor do hash é primeiro alimentado por meio da função a ser convertido / preenchido para caber como chave para a cifra. ${\ displaystyle H_ {i-1}}$${\ displaystyle g}$

Em notação matemática Matyas – Meyer – Oseas pode ser descrito como:

${\ displaystyle H_ {i} = E_ {g (H_ {i-1})} (m_ {i}) \ oplus m_ {i}}$

O esquema tem a taxa:

${\ displaystyle R_ {MMO} = {\ frac {n} {1 \ cdot n}} = 1}$

Um segundo ataque de pré-imagem (dada uma mensagem que um invasor encontra outra mensagem para satisfazer ) pode ser feito de acordo com Kelsey e Schneier para uma mensagem -message-block a tempo . Observe que a complexidade é superior, mas inferior, quando as mensagens são longas, e quando as mensagens ficam mais curtas, a complexidade do ataque se aproxima . ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2 ^ {k}}$${\ displaystyle k \ times 2 ^ {n / 2 + 1} + 2 ^ {n-k + 1}}$${\ displaystyle 2 ^ {n / 2}}$${\ displaystyle 2 ^ {n}}$${\ displaystyle 2 ^ {n}}$

Miyaguchi – Preneel

A função de compressão unilateral de comprimento de bloco único Miyaguchi – Preneel é uma variante estendida de Matyas – Meyer – Oseas. Foi proposto de forma independente por Shoji Miyaguchi e Bart Preneel .

Ele alimenta cada bloco da mensagem ( ) como o texto simples a ser criptografado. O texto cifrado de saída é então XORed (⊕) com o mesmo bloco de mensagem ( ) e também XORed com o valor hash anterior ( ) para produzir o próximo valor hash ( ). O valor de hash anterior ( ) é alimentado como a chave para a cifra de bloco. Na primeira rodada, quando não há nenhum valor de hash anterior, ele usa um valor inicial pré-especificado constante ( ). ${\ displaystyle m_ {i}}$${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {0}}$

Se a cifra de bloco tiver blocos e tamanhos de chave diferentes, o valor hash ( ) terá o tamanho errado para usar como chave. A cifra também pode ter outros requisitos especiais na chave. Em seguida, o valor do hash é primeiro alimentado por meio da função a ser convertido / preenchido para caber como chave para a cifra. ${\ displaystyle H_ {i-1}}$${\ displaystyle g}$

Em notação matemática, Miyaguchi – Preneel pode ser descrito como:

${\ displaystyle H_ {i} = E_ {g (H_ {i-1})} (m_ {i}) \ oplus H_ {i-1} \ oplus m_ {i}}$

O esquema tem a taxa:

${\ displaystyle R_ {MP} = {\ frac {n} {1 \ cdot n}} = 1}$

As funções de e podem ser trocadas, de modo que sejam criptografadas na chave , tornando esse método uma extensão de Davies-Meyer. ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i-1}}$${\ displaystyle m_ {i}}$

Um segundo ataque de pré-imagem (dada uma mensagem que um invasor encontra outra mensagem para satisfazer ) pode ser feito de acordo com Kelsey e Schneier para uma mensagem -message-block a tempo . Observe que a complexidade é superior, mas inferior, quando as mensagens são longas, e quando as mensagens ficam mais curtas, a complexidade do ataque se aproxima . ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2 ^ {k}}$${\ displaystyle k \ times 2 ^ {n / 2 + 1} + 2 ^ {n-k + 1}}$${\ displaystyle 2 ^ {n / 2}}$${\ displaystyle 2 ^ {n}}$${\ displaystyle 2 ^ {n}}$

Hirose

A função de compressão unilateral de comprimento de bloco duplo do Hirose consiste em uma cifra de bloco mais uma permutação . Foi proposto por Shoichi Hirose em 2006 e é baseado em um trabalho de Mridul Nandi . ${\ displaystyle p}$

Ele usa uma cifra de bloco cujo comprimento da chave é maior do que o comprimento do bloco e produz um hash de tamanho . Por exemplo, qualquer um dos candidatos AES com uma chave de 192 ou 256 bits (e bloco de 128 bits). ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle 2n}$

Cada rodada aceita uma parte da mensagem com bits de comprimento e a usa para atualizar os valores de estado de dois bits e . ${\ displaystyle m_ {i}}$${\ displaystyle kn}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle H}$

Primeiro, é concatenado com para produzir uma chave . Em seguida, os dois valores de feedback são atualizados de acordo com: ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle K_ {i}}$

• ${\ displaystyle G_ {i} = E_ {K_ {i}} (G_ {i-1}) \ oplus G_ {i-1}}$
• ${\ displaystyle H_ {i} = E_ {K_ {i}} (p (G_ {i-1})) \ oplus p (G_ {i-1})}$

${\ displaystyle p (G_ {i-1})}$é uma permutação arbitrária de ponto fixo livre em um valor de bits, normalmente definida como para uma constante arbitrária diferente de zero (todos os uns podem ser uma escolha conveniente). ${\ displaystyle n}$${\ displaystyle p (x) = x \ oplus c}$${\ displaystyle c}$

Cada criptografia se assemelha à construção Davies – Meyer padrão. A vantagem deste esquema sobre outros esquemas de comprimento de bloco duplo propostos é que ambas as criptografias usam a mesma chave e, portanto, o esforço de programação de chave pode ser compartilhado.

O resultado final é . O esquema tem a taxa relativa à criptografia da mensagem com a cifra. ${\ displaystyle H_ {t} || G_ {t}}$${\ textstyle R_ {Hirose} = {\ frac {kn} {2n}}}$

Hirose também fornece uma prova no Modelo de Cifra Ideal.

Construção de esponja

A construção em esponja pode ser usada para construir funções de compressão unilateral.

Veja também

• Whirlpool - Uma função hash criptográfica construída usando a construção Miyaguchi – Preneel e uma cifra de bloco semelhante a Square e AES .
• CBC-MAC , OMAC e PMAC - Métodos para transformar cifras de bloco em códigos de autenticação de mensagem (MACs).

Referências

Citações

Fontes