SHA-1: Algoritmo de resumo seguro

No blog desta semana, apresentamos o algoritmo de resumo SHA-1 (Secure Hash Algoritm), uma lista de possíveis aplicações e o tipo de ataque ao qual ele está sujeito. O algoritmo foi adotado como padrão dentro do governo norte-americano em 1995 através da FIPS PUB 180-1 (http://www.itl.nist.gov/fipspubs/fip180-1.htm).
Esse algoritmo visa a geração de uma representação numérica, a qual chamamos de hash, de uma dada mensagem de forma segura. É seguro por dois motivos: a. computacionalmente é improvável encontrar uma mensagem a partir de um hash conhecido, b. é improvável encontrar duas mensagens que produzam o mesmo hash.
A utilidade para o hash de uma mensagem está principalmente no teste de integridade da mesma, após uma transmissão ou armazenamento. Os algoritmos de assinatura digital utilizam o hash para otimizar o processo de assinatura. Nesse caso, o hash é assinado e não a mensagem toda, que provavelmente tem um tamanho bem maior. Caso a mensagem seja alterada durante a transmissão ela irá produzir um hash diferente do original e a existência do erro será percebida.

Funcionamento do algoritmo SHA-1
O algoritmo é composto de um conjunto de operações lógicas com a mensagem de entrada resultando num número de 160 bits escrito na base hexadecimal e a mensagem de entrada pode ser de até 2^64 bits.
Etapa 1:
A mensagem de entrada é preenchida com zeros para tornar o seu tamanho mútliplo de 512. Nesse processo, a mensagem é quebrada em blocos de 512 bits. O último bloco, sendo menor que 512, recebe um bit 1 e depois uma quantidade variável de bits 0 até completar 448 bits. Nos últimos 64 bits, será armazenado o tamanho original da mensagem. Na figura abaixo, tem-se a representação de um bloco após o processo de padding.

61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028

Onde:
9 : Mensagem original
9 : é obtido com a inserção do 1 no fim da cadeia de entrada
9 : número de zeros para completar 448 bits
9 : palavras de 32 bits com o tamanho original da mensagem

A mensagem original será então representada no algoritmo SHA-1 por uma quantidade n de blocos de 512 bits chamados de M1, M2,...,Mn.

Etapa 2:
A mensagem é organizada em buffers de 512 bits organizados em 16 palavras Mxi, onde: x é cada bloco de 512 bits e i é cada uma das 16 palavras do bloco.

Etapa 3:
Nessa etapa é calculado o hash propriamente dito, onde cada bloco é processado t=80 vezes.
O algoritmo utiliza o seguinte conjunto de variáveis em memória:
Constante K para cada uma das 80 vezes:
K = 5A827999 ( 0 <= t <= 19)
Kt= 6ED9EBA1 (20 <= t <= 39)
Kt= 8F1BBCDC (40 <= t <= 59)
Kt= CA62C1D6 (60 <= t <= 79).
Buffer de saída, inicializado antes de processar o primeiro bloco com os valores abaixo e sobreposto a cada novo bloco com os valores de hash calculados:
H0= 67452301
H1= EFCDAB89
H2= 98BADCFE
H3= 10325476
H4= C3D2E1F0
Buffer auxiliar inicializado a cada bloco:
A = H0
B = H1
C = H2
D = H3
E = H4
Buffer temporário: TEMP
Buffer para cada iteração: Wt, 0 <= t <= 79

O algoritmo utiliza o seguinte conjunto de expressões lógicas sobre as variáveis auxiliares, conforme a iteração t processada:
ft(B,C,D) = (B AND C) OR ((NOT B) AND D) para 0 <= t <= 19
ft(B,C,D) = B XOR C XOR D para 20 <= t <= 39
ft(B,C,D) = (B AND C) OR (B AND D) OR (C AND D) para 40 <= t <= 59
ft(B,C,D) = B XOR C XOR D para 60 <= t <= 79.

O processamento começa com a preparação dos 80 buffers que serão utilizadas a cada iteração. A preparação segue a seguinte regra:
Wt = Mxt para 0 <= t <= 15
Wt = Rotacionado 1 para esquerda do resultado da expressão: W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)
Inicializa os buffers auxiliares:
A = H0; B = H1; C = H2; D = H3; E = H4
Repete 80 vezes:
TEMP = Rotaciona 5 para esquerda(A) + ft(B,C,D) + E + Wt + Kt;
E = D;
D = C;
C = Rotaciona 30 para esquerda(B);
B = A;
A = TEMP;
O hash intermediário é calculado da seguinte maneira:
H0 = H0 + A;
H1 = H1 + B;
H2 = H2 + C;
H3 = H3 + D;

Após processar os N blocos da mensagem, o hash final é: H0H1H2H3

Aplicações para o algoritmo de hash
Os algoritmos de hash são bastante úteis pela sua característica de gerar um identificador único tendo um dado conjunto de caracteres como entrada. Abaixo tem-se uma lista das possíveis aplicações desse algoritmo:
-Validação de senha de autenticação
-Criação de assinatura digital para documentos
-Verificação de integridade de pacotes em protocolos de comunicação
-Autenticação de mensagens através dos hashes com chave criptográfica

Prováveis ataques ao algoritmo SHA-1

Alguns dos ataques aos quais o algoritmo SHA-1 está sujeito são:
- força bruta
- colisão
No entanto, nenhum desses dois ataques eram considerados factíveis até pouco tempo. Em 2005, um grupo de criptoanalista chineses conseguiram quebrar o SHA-1 utilizando o método da colisão, que utiliza técnicas matemáticas para quebrar o algoritmo.
Isso ainda não oferece alto risco para as aplicações que utilizam SHA-1, mas deve-se deixar de usá-lo e optar por algoritmos mais robustos como o SHA-256 ou SHA-512.