Bitcoin - Função criptográfica de hash

O que funções criptográficas de hash são e quais propriedades são desejadas delas.

Funções criptográficas de hash são
basicamente alicerces fundamentais

que são usados dentro de vários
algoritmos de criptografia e protocolos.

Nós temos um grande número
de aplicações importantes

no contexto de segurança da
informação como um todo.

Alguns dos algoritmos mais
conhecidos nessa categoria,

conhecidos como funções
criptográficas de hash,

incluem MD5, e ele também tem
predecessores como MD4 e outros;

bem como os algoritmos SHA-256,

e, na verdade, SHA-256 é precedido
por outros algoritmos como SHA-1

e assim por diante,

e também há alguns algoritmos que
talvez você tenha ouvido falar,

talvez eles sejam menos conhecidos, mas
temos RIPEMD e BLAKE e Skein e outros.

Bem, funções criptográficas
de hash são basicamente

usadas como partes críticas
de várias aplicações

e, a primeira aplicação que motivou,

a primeira aplicação histórica
desses tipos de funções de hash

foi no contexto conhecido
como assinatura digital.

E assinatura digital é usada em tantas
aplicações criptográficas diferentes hoje,

ela é o pilar de muitos
protocolos de e-commerce,

é usada para fazer coisas como
geração de Bitcoin por exemplo.

Funções criptográficas de hash são usadas
em protocolos de autenticação de mensagens

na geração de números pseudo-aleatórios
e na segurança de senhas

até mesmo em criptografia em certo grau

e, na verdade, além de seu
uso em assinaturas digitais,

essas funções de hash são também usadas
em outros lugares do protocolo Bitcoin.

Então, antes de tudo deixe-me falar sobre
o que uma função criptográfica de hash é.

E, é claro, como o próprio nome implica,
a primeira coisa, ela é uma função de hash

e por função de hash eu quero dizer
que ela vai receber uma entrada,

ela é uma função matemática,
uma transformação se preferir,

que recebe uma entrada particular,
e chamamos essa entrada de uma "mensagem"

e a mensagem pode ser
de um tamanho arbitrário

e a função de hash basicamente aplica
uma transformação matemática,

talvez um conjunto de transformações
matemáticas, nessa entrada

para produzir uma única saída.

Nós normalmente chamamos essa saída de
resumo, entretanto às vezes você verá essa

saída sendo referida como uma etiqueta,
ou uma hash, ou uma impressão digital;

mas resumo é um dos
nomes mais comuns.

E, na verdade, MD5 - que foi uma das
primeiras funções de hash - significa

"Message Digest 5" (Resumo da Mensagem 5)

e MD4 é "Message Digest 4" (Resumo da
Mensagem 4) e assim por diante.

A mensagem, como eu mencionei breviamente,
pode ser de um tamanho arbitrário

pode ser tão longa quanto quiser,
ou pode ser tão curta quanto quiser,

mas a saída, o tamanho do resumo
vai ser de um tamanho fixo.

Por exemplo, no contexto de uma função
de hash como, vamos dizer, SHA-256,

o resumo vai ter exatamente
256 bits de tamanho.

Então vai ter uma saída de tamanho fixo
mas uma entrada de tamanho arbitrário

E a outra coisa que quero ressaltar sobre
essas funções criptográficas de hash é

que a função é uma função determinística,
e por isso eu quero dizer que

a saída sempre será a mesma
para uma entrada específica.

Então se você tem uma entrada específica,
vai ver a mesma exata saída.

Você não vai ter uma situação em que dado
uma entrada terá duas possíveis saídas.

Vai ser consistente.

Bem, funções de hash tradicionais vem
sendo usadas em Ciência da Computação

há bastante tempo e elas são usadas
em várias aplicações computacionais.

Você talvez tenha ouvido sobre uma função
hash usada para fazer uma tabela hash.

Mas o tipo de funções hash que são usadas
em tabelas hash, e eu quero destacar isso,

não são necessariamente o mesmo
que funções criptográficas de hash.

O qualificador 'criptográficas'
aqui é muito importante.

E geralmente significa que essa função
hash tem que ter um certo conjunto de

objetivos críticos de design e talvez
algumas propriedades particulares em mente

que a faça adequada para o uso em
aplicações que usem criptografia

onde talvez segurança ou privacidade,
ou confidencialidade ou autenticação

é uma preocupação séria.

Então, primeiro e antes de tudo em
descrevendo as propriedades de alguém

é que, e talvez isso nem precise ser dito,

uma das propriedades que você quer
em uma função criptográfica de hash

é que ela deveria ser computacionalmente -
computacionalmente eficiente.

E com isso quero dizer que
ela não deveria levar muito tempo

para computar a saída de
uma determinada entrada

Se você recebe uma mensagem e quer aplicar
um conjunto de transformações nesta

mensagem para obter um resumo, esse
conjunto de transformações não deveria

tomar muito tempo para ser implementado
em um computador, deveria ser bem rápido.

E isso quase nem precisava ser dito mas
acho importante reforçar e destacar

porque eu já vi pessoas fazerem
implementações grosseiramente ineficientes

de funções de hash algumas vezes e estas
não seriam consideradas adequadas

no contexto de uma típica função
criptográfica de hash que é usada para

aplicações criptográficas.

E a segunda propriedade que geralmente
se precisa, especialmente no contexto de

assinatura digital, é: você quer que seja
o caso de ser difícil que duas entradas

sejam mapeadas realmente para a mesma
entrada. Duas entradas distintas

cujos resumos correspondentes
sejam idênticos.

E essa propriedade geralmente é chamada de
colisão, resistência à colisões.

Isso significa que é difícil achar
um par de entradas que colidam.

Em outras palavras, se temos duas entradas
vamos dizer uma mensagem M1 e uma M2.

Suas saídas da aplicação da função de hash
não deveriam ser a mesma.

Você nunca teria o caso em que a saída
de M1 e M2 da aplicação da função de hash

são iguais. Nunca deveria ser igual.
Deve sempre ser diferente.

Eu deveria voltar um passo e
destacar que, é claro, na prática,

dado que a mensagem pode ser de um tamanho
arbitrário e a saída é de um tamanho fixo,

não é mateticamente possível garantir
que a saída sempre será diferente

para duas mensagens distintas.

Mas o que você geralmente quer não é que
as saídas sejam necessariamente diferentes

mas que seja difícil para achar mensagens
distintas que produzem a mesma saída.

Nós sabemos que elas existem em virtude do
fato que mensagens podem ser mapeadas

em apenas um número finito e pequeno

(ou relativamente um número pequeno se
comparado ao número de mensagens)

um número pequeno de
possíveis valores resumo.

Mas fora essa consideração, deveria ser
difícil, deveria levar muito tempo,

e por muito tempo eu quero dizer
astronomicamente muito tempo para achar

duas mensagens distintas que resultariam
na mesma saída aplicando a função de hash.

Bem, a terceira coisa que eu quero
ressaltar é que em vários casos

você pode também querer, no contexto das
funções de hash, que a função seja capaz

de esconder informações
sobre as entradas.

Em outras palavras, dado a saída, deveria
ser difícil coletar qualquer informação

útil ou interessante sobre a entrada.
Qualquer coisa, qualquer detalhe relevante

e não quero dizer apenas a entrada inteira
mas até mesmo uma coisa tão simples quanto

"a entrada era um número par
ou um número ímpar?"

E isso deveria ser o tipo de coisa que é
difícil inferir quando você vê a saída.

Até mesmo algo tão simples quanto a
paridade ou imparidade da entrada.

Agora, a quarta propriedade
que quero ressaltar

é que você geralmente quer
que a saída seja bem distribuída.

Em outras palavras, a saída
deve parecer aleatória.

Deve parecer como se fosse um conjunto de
jogadas de moeda feitas de nenhuma forma

previsível em que a saída foi criada.

E isso significa que é quase como se você
jogasse várias moedas para fazer a saída.

Deve parecer aleatório.

Você pode pensar em funções criptográficas
de hash como talvez o equivalente

matemático ou análogo
de um moedor de carne.

Ele pode receber entradas e aplicar essas
transformações matemáticas nelas

de modo que a saída pareça, para todos os
propósitos, completamente aleatória

e sem relação com
a entrada original.

Eu quero fazer algumas pequenas
observações sobre essas propriedades.

E antes de tudo, elas são
inter-relacionadas - por exemplo,

se você tem uma situação onde a saída não
aparenta mesmo ter relação com a entrada,

e a saída também parece aleatória,

então isso vai te dar na verdade, em certo
grau, uma grande resistência a colisões

porque apenas o fato de que você não pode
prever a saída e o fato de que ela esconde

toda essa informação implica que vai ser
difícil achar duas entradas distintas

que são mapeadas para a mesma saída.

E então, às vezes você consegue uma
propriedade em troca das outras.

A segunda coisa que eu quero ressaltar
é que geralmente essas propriedades

na prática, ou até mesmo em matemática
subjacente, são coisas que você espera por

mas que você não pode sempre garantir
que elas serão sempre válidas.

E talvez seja completamente possível que
você poderia desenvolver uma função hash

que você pensa ser completamente
resistente à colisões

mas alguém pode aparecer e, daqui a um ano
inventar uma maneira mais inteligente

para achar colisões.

Talvez ele tenha descoberto um jeito que
não involva fazer uma busca de força bruta

E acontece que criptógrafos, para o bem ou
para o mal, atualmente não têm nenhuma

técnica matemática, eles não
desenvolveram técnicas capazes de

contornar algumas dessas limitações.

Assim, nós frequentemente tomamos como
base de quanto esses esquemas são seguros

pelo tempo que eles
vêm sendo utilizados.

Agora eu também quero destacar uma última
coisa, essa forma como tratei o assunto

não é de forma alguma
matematicamente rigoroso.

Existem métodos muito mais precisos
de descrever essas propriedades.

Mas eu espero que esse vídeo
talvez te dê uma noção geral

do que é necessário a uma função
criptográfica de hash

sem ficar chato entrando em
detalhes formais matemáticos.

[Legendado por Alberto Oliveira]