SHA-3

Keccak (pronúncia: [kɛtʃak] , como “ketchak”) é uma função hash criptográfica projetada por Guido Bertoni, Joan Daemen , Michaël Peeters e Gilles Van Assche da função RadioGatún .

SHA-3 vem da competição de função hash NIST que elegeu o algoritmo Keccak em2 de outubro de 2012. Não se destina a substituir o SHA-2 , que ainda não foi comprometido por um ataque significativo, mas a fornecer uma solução alternativa para as possibilidades de ataques contra os padrões MD5 , SHA- 0 e SHA-1 .

Keccak é uma função esponja na qual os blocos de mensagem são submetidos a XOR com bits iniciais e, em seguida, trocados de forma reversível.

O algoritmo Keccak originalmente enviado às vezes é usado, ele difere do algoritmo especificado pelo NIST porque o NIST especificou como completar a mensagem quando o comprimento da mensagem não é igual ao tamanho exigido como entrada pela função esponja. Os resultados são diferentes.

Permutação de bloco de Keccak

Keccak é uma função de esponja cuja transformação descreveremos, denominada f na terminologia da construção da esponja. Essa transformação é uma permutação válida pela escolha de uma palavra de tamanho que é uma potência de dois w = 2 ℓ . No caso de Keccak as palavras são de 64 bits, ou seja, ℓ = 6 .

O estado interno desta função será visto como uma matriz de dimensão 5 × 5 × w . será a parte da entrada. Os índices são calculados módulo 5 para as duas primeiras dimensões e módulo w para a terceira.

A função f de Keccak é uma permutação que consiste em 12 + 2ℓ iterações ( ou seja, 24) de cinco sub-rotinas bastante simples:

A rotina θ Calcule a paridade das colunas 5 × w (5 bits) do relatório e, em seguida, calcule a exclusiva ou entre duas colunas vizinhas. A rotina ρ Mude circularmente as 25 palavras de um número triangular (0, 1, 3, 6, 10, 15, ...). não é deslocado e: para cada 0 ≤ t <24 :
 A rotina π Permutação das 25 palavras com um padrão fixo: A rotina χ Combine as linhas pouco a pouco de acordo com a fórmula : Esta operação é a única chamada não linear. A rotina ι Calcule o exclusivo ou de uma constante com uma palavra de estado, que depende do número da iteração ( n ): para cada 0 ≤ m ≤ ℓ :é Xore com o bit numerado m + 7n de uma sequência LFSR de grau 8. Esta última etapa visa quebrar as últimas simetrias deixadas pelas anteriores.

Mensagens de hash de tamanho variável

O SHA-3 utiliza a construção esponja , na qual o input é, metaforicamente em uma primeira frase absorvida pelo estado, a uma certa velocidade, e em uma segunda espremida , na mesma velocidade.

Para absorver r bits dos dados, os dados são XOR ed nos primeiros bits do estado, então a permutação de bloco é aplicada se uma saída adicional for desejada.

A capacidade da função hash, os c = 25 w - r bits de estados que nunca são afetados diretamente pela entrada ou pela saída, é um parâmetro importante. Pode ser ajustado de acordo com a segurança esperada da construção, mas o padrão SHA-3 o define razoavelmente em c = 2 n , com n do tamanho da pegada desejada.

Assim , r , a quantidade de bits da mensagem processada em cada permutação, depende do tamanho da impressão desejada. As diferentes opções de taxa de r são 1152, 1088, 832 ou 576 (144, 136, 104 ou 72 bytes ) para tamanhos de impressão digital de 224, 256, 384 e 512 bits, respectivamente, para w definido como 64.

Para alinhar a mensagem em um tamanho múltiplo do tamanho de um bloco de r bits, ela é preenchida (preenchendo ou preenchendo em inglês) com o padrão binário 10 ... 01  : um primeiro bit em 1, possivelmente seguido pelo número apropriado de bits em 0 (máximo r -1 bits), mas sempre seguido por outro bit em 1. Este último bit é uma pré-condição necessária para a prova de segurança da construção da esponja (o último bloco de mensagem deve ser não -zero).

O algoritmo procede da seguinte forma: o estado é inicializado em 0, a entrada é preenchida, dividida em blocos de r bits. A entrada é absorvida pelo estado, ou seja, para cada bloco ela é XOR izada com o estado então a permutação é aplicada ao resultado.

Depois de realizadas todas as permutações, a impressão digital do resultado é composta pelos primeiros n bits do relatório. r é sempre maior que n , então nunca há necessidade de aplicar várias permutações durante a fase de spin. Em outras aplicações, como o Optimal Asymmetric Encryption Padding (OAEP), a saída de tamanho variável é útil. Nesse caso, n é mais um parâmetro de segurança do que apenas um tamanho de saída.

Variantes da função de permutação para gerar hashes menores também estão disponíveis para tamanhos de hash até a metade do tamanho de seu estado interno, se a taxa r for baixa o suficiente. Eles não eram necessários para a entrada na competição SHA. Por exemplo, é possível calcular uma pegada de 256 bits usando 25 palavras de 32 bits se r = 800−2 × 256 = 288 , ou 32 bytes por iteração.

SHA-3, instanciando a construção da esponja, pode ser escrito em pseudo-código:

Função SHA-3 ( fluxo ): parâmetros de construção: f  : uma transformação de b bits → b bits, descrita na seção anterior r  : o número de bits por bloco de saída pad  : uma função para preencher o fluxo de entrada em blocos inteiros de r bits n s  : o número de blocos de saída variáveis ​​internas: estado  : uma matriz de b bits, inicializada em 0, dividida em estado [1 .. r ] e estado [ r +1 .. b ] blocos  : uma matriz de blocos de r bits cada z  : uma string a retornar, de comprimento n s × r , inicializada vazia algoritmo: (* fase de absorção *) blocos ← almofada de corte ( fluxo ) em blocos de tamanho r bits para cada p em blocos  : estado ← f ( estado [1 .. r ] ⊕ p ) (* fase de rotação *) repetir n s vezes  : z ← concatenados ( z , estado [1 .. r ]) estado ← f ( estado ) retornar z

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  Keccak  " ( ver a lista de autores ) .
  1. (in) Guido Bertoni, Joan Daemen, Michaël Peeters e Gilles Van Assche, "  The Keccak sponge function family: Specifications summary  " em http://keccak.noekeon.org/ (acessado em 11 de maio de 2011 )
  2. Patrick Guignot, "  Keccak vence a licitação e torna-se SHA-3  " , no Linuxfr
  3. (in) Guido Bertoni, Joan Daemen, Michaël Peeters e Gilles Van Assche, "  Sponge Functions  " , ECRYPT Hash Workshop 2007
  4. (in) Guido Bertoni, Joan Daemen, Michaël Peeters e Gilles Van Assche, "  On the Indiferentiability Construction of the Sponge  " , EuroCrypt 2008
  5. Valor da string 'abc' para várias variantes do algoritmo

Apêndices

Artigos relacionados

links externos