O que são as constantes mágicas encontradas no algoritmo SHA-256?
SHA-256 é uma das funções hash que faz parte da família SHA-2 (sucessora da família SHA-1) definidas no U.S. National Institute of Standards and Technology - Federal Information Processing Standards Publication (FIPS PUB) 180-4 update 1 publicado em agosto de 2015 (sob revisão após receber sugestões) e previamente definido nos padrões anteriores FIPS PUB 180, FIPS PUB 180-1, FIPS PUB 180-2, 180-2 update 1, FIPS PUB 180-3, FIPS PUB 180-4. Outras funções da mesma família são: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256, sendo o valor numérico o número de bits resultante do resumo ou digest.
Existem diferentes implementações (1, 2, 3) do algoritmo SHA-256, contendo 72 constantes hardcoded para eficiência e padronização. Tais constantes desempenham um papel crucial em determinadas funções internas, sendo 8 delas, denominadas H_j, participantes na etapa de inicialização dos valores de hash e outras 64 constantes, denominadas K_i, participantes na etapa de compressão.
---------------------------------- K ---------------------------------- --- H ---
428A2F98 71374491 B5C0FBCF E9B5DBA5 3956C25B 59F111F1 923F82A4 AB1C5ED5 6A09E667
D807AA98 12835B01 243185BE 550C7DC3 72BE5D74 80DEB1FE 9BDC06A7 C19BF174 BB67AE85
E49B69C1 EFBE4786 0FC19DC6 240CA1CC 2DE92C6F 4A7484AA 5CB0A9DC 76F988DA 3C6EF372
983E5152 A831C66D B00327C8 BF597FC7 C6E00BF3 D5A79147 06CA6351 14292967 A54FF53A
27B70A85 2E1B2138 4D2C6DFC 53380D13 650A7354 766A0ABB 81C2C92E 92722C85 510E527F
A2BFE8A1 A81A664B C24B8B70 C76C51A3 D192E819 D6990624 F40E3585 106AA070 9B05688C
19A4C116 1E376C08 2748774C 34B0BCB5 391C0CB3 4ED8AA4A 5B9CCA4F 682E6FF3 1F83D9AB
748F82EE 78A5636F 84C87814 8CC70208 90BEFFFA A4506CEB BEF9A3F7 C67178F2 5BE0CD19
Código elaborado para cálculo das 72 constantes
echo "" | awk --sandbox '{
j = 0; # Inicializacao do indice para constantes H
# Numeros primos de 2 a 317
primes = " 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,"\
" 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,"\
"103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,"\
"173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,"\
"241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313 ";
n = split(primes, p, ","); # Transcreve para vetor os números primos dados
# Imprime um cabecalho
printf("---------------------------------- K ");
printf("---------------------------------- --- H ---\n");
for(i = 1; i = 64; i++) {
# Calcula e imprime as constantes K( 1) até K(64)
c = p[i]^(1/3); k = int(2^32*(c-int(c))); printf("%08X ", k);
if(!(i%8)) {
j++;
# Calcula e imprime as constantes H(1) até H(8)
b = p[j]^(1/2); h = int(2^32*(b - int(b))); printf(" %08X\n", h);
};
}
}'
Mas, qual é a origem, o significado e o motivo destas constantes?
Ao utilizar as partes fracionárias das raízes cúbicas dos 64 primeiros números primos (NIST.FIPS.180-4, pag. 11) para geração das constantes K e utilizar as partes fracionárias das raízes quadradas dos 8 primeiros números primos (NIST.FIPS.180-4, pag. 15) para geração das constantes H, cria-se, desta forma, um conjunto de constantes que tornam a função hash resistente a ataques, garantindo um comportamento complexo e menos previsível. Para obter as constantes, aquelas partes fracionárias são então multiplicadas por 2^32
, os resultados truncados para inteiros e então impressos na base numérica hexadecimal. Tais valores são então facilmente obtidos de maneira determinística e, para que haja consistência das saídas de hash em diferentes implementações do algoritmo, tais valores devem ser mantidos fixos. Essas constantes mágicas usadas no algoritmo de hash SHA-256 proporcionam uma não-linearidade para a função hash.
Aplicações do SHA-256
SHA-256 é amplamente utilizada como função criptográfica de hash, produzindo uma saída de 256 bits independente do número de bytes fornecidos na sua entrada (um simples caractere ou arquivos inteiros). Outra aplicação relevante é no algoritmo de mineração de um dos ativos digitais mais conhecidos, onde se aplica a função duas vezes, ou seja, sha256(sha256(conteúdo))
e por isso às vezes é denominada sha256d
.
Por que sha256(sha256(conteúdo))?
O Bitcoin encadeia o algoritmo de hash SHA-256 duas vezes no processo de criação de um hash para um determinado bloco, especificamente ao cabeçalho do bloco. O cabeçalho do bloco inclui dados importantes como o hash do bloco anterior, a estampa de hora (timestamp), o nonce (um número usado uma vez) entre outros elementos.
Estrutura de um cabeçalho
O duplo hash resultante é uma representação compacta do estado de todo o bloco e é usado no mecanismo de prova de trabalho (proof of work), onde os mineradores competem para encontrar um hash que seja inferior a um determinado limite alvo denominado difficult.
O duplo hash serve a vários propósitos:
-
Segurança aprimorada: Ao fazer hash dos dados duas vezes, o Bitcoin adiciona uma camada adicional de segurança. Embora o SHA-256 já seja considerado seguro, o hash duplo torna ainda mais difícil para os "invasores" encontrarem colisões (dois dados diferentes que produzem o mesmo hash) ou pré-imagens (encontrar uma entrada que faz hash para uma saída específica).
-
Saída Determinística: O uso de SHA-256 duplo garante que a saída seja determinística, o que significa que a mesma entrada sempre produzirá a mesma saída. Ao aplicar a mesma função hash duas vezes, quaisquer pequenas alterações na entrada levarão a saídas hash significativamente diferentes.
-
Resistência a certos ataques: o hash duplo pode mitigar certos tipos de ataques, especificamente aqueles que visam a primeira camada do processo de hash. Se um invasor puder interferir (influenciar) a entrada do primeiro hash, deverá também precisará lidar com o segundo hash, tornando-o mais complexo e demorado.
-
Consistência do comprimento de saída: Hashing duas vezes garante um comprimento de saída consistente, o que é crucial para funções criptográficas. Mesmo que a primeira função hash tivesse características diferentes, a segunda camada impõe um comprimento e estrutura de saída uniformes.
Funções hash são construídas de maneira que teoricamente não seja possível reverter o processo a partir das saídas, ou seja, recriar uma entrada (um arquivo) a partir de seu hash. Entretanto, hash de mensagens curtas ou mesmo arquivos estruturados, podem ser revertidos a partir de ataques via força bruta como rainbow tables.
Fontes consultadas...
http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf
https://csrc.nist.gov/publications/fips#fips180-4
https://datatracker.ietf.org/doc/html/rfc6234
https://eprint.iacr.org/2011/565.pdf
http://www.hashcash.org/papers/hashcash.pdf
https://bitcoin.org/bitcoin.pdf
https://armantheparman.com/sha256
https://armantheparman.com/dicev1