10

Eu vi que está sendo programado para próxima versão do PHP 8.1 a implementação do MurmurHash.

Eu nunca tinha ouvido falar sobre. Gostaria de saber do que se trata.

2
  • 8
    É um hash não criptográfico (não serve para segurança, pode servir para integridade), mas que de sacanagem nesse link seu foi comparado com criptográficos (justo seria ter o CRC32 na lista, que eu desconfio que ele perca, ou no máximo empate). Assim como o CRC32, ele é incremental (stream), ou seja, você pode ir calculando ele sem precisar por inteiro na memória, usa o valor anterior e "incrementa". Edit: confirmado num link mais extenso, ele perde pro CRC32: php.watch/articles/php-hash-benchmark - o que tem de interessante em algumas das variações é que tem mais bits que o CRC32
    – Largato
    Commented 31/12/2020 às 22:15
  • 2
    Briga de cachorro grande. Commented 5/01/2021 às 2:21

2 Respostas 2

10
+50

MurmurHash (família de algoritmo de hash Murmur) é um hash não criptográfico com foco em altas performance, otimização e resistência a colisões.

Introdução

Para entender a motivação por trás do MurmurHash (um hash não criptográfico), é preciso entender, primeiramente, alguns dos principais fatores necessários para que um algoritmo hash seja considerado critptográfico:

  • Resistência a colisões;
  • Resistente ao ataque pre-image;
  • Bom efeito avalanche (isso significa, em resumo, que mudar uma ínfima parte da entrada representa enorme alteração na saída).
  • Determinístico (uma mesma entrada deve sempre produzir mesma saída).
  • Ser unidirecional (de modo a tornar impossível obter a mensagem original a partir do hash).

Uma vez que algum desses requisitos não tenha sido propriamente cumprido, o algoritmo deixa de ser considerado função hash criptográfica, passando a ser chamado de função hash não criptográfica.

Não pense que uma função hash não criptográfica perde a sua utilidade por não servir para fins criptográficos. Embora alguns algoritmos como MD5 ou SHA1 tenham sido rebaixados de hashes criptográficos para a classificação de não criptográficos (em detrimento de suas respectivas obsolescências), alguns hashes são desenvolvidos como não criptográficos desde o início para desempenhar algumas tarefas com desempenho superior. É o caso do MurmurHash.

Trade offs: Trade offs everywhere

MurmurHash

O nome veio das duas operações básicas utilizadas em sua implementação, multiplicação (MU) e rotação (R). Do inglês, multiply e rotate.

Em resumo, algoritmos da família Murmur abrem mão de parte da "segurança criptográfica" para aumentar a eficiência e performance. Desse modo, MurmurHash:

  • É simples em termos da quantidade de instruções Assembly geradas;
  • Bom efeito avalanche;
  • Boa resistência a colisões (para chaves de até 4 bits colisões são garantidamente impossíveis);
  • Otimizado para arquitetura Intel/AMD, de modo que representa um bom tradeoff entre qualidade de hash e consumo de CPU.

Observe então que o MurmurHash abre mão de certa parte da segurança (especificamente na resistência contra reversibilidade) para ganhos em performance e otimização.

Embora não seja, por isso, ideal para fins criptográficos, pode ser uma boa opção para implementações de certos tipos de hash tables, uma vez que é rápido e relativamente resistente a colisões.

Além disso, MurmurHash é um streaming hash, o que significa que os valores podem ser atualizados em sequência sem a necessidade de recomputar utilizando a string inteira. Ou seja, pode ser utilizado de modo incremental, algo extremamente útil em strems de dados.

Um outro exemplo de uso interessante aqui.

Referência

Recursos e fontes que utilizei para elaborar esta resposta.

-5

É um algorítmo não criptográfico criado por Austin Appleby.

Foi criado para ter alta performance no uso de buscas e identificações de conteúdo mas não para criptografia de segurança

Tem libs para várias linguagens como python e NodeJS

Dá uma olhada no repositório https://github.com/ksss/digest-murmurhash

3
  • 5
    Isso qualquer um pode dizer. O mesmo já foi colocado bem claro nos comentários para evitar que alguém responda com trivialidade. O outro comentário foi bem explicito "Briga de cachorro grande" a respostas competindo por votos e recompensas deve ter conteúdo técnico. O autor quer saber formalmente, como o algoritmo funciona. Commented 5/01/2021 às 18:37
  • Ok, sem problema, mas sua pergunta foi "Eu nunca tinha ouvido falar sobre. Gostaria de saber do que se trata." Acredito que eu respondi o que se trata. Se quer saber mais sobre como é o algorimo, só olhar o código no link que botei ali! Valeu. Abraço.
    – Sérgio B.
    Commented 5/01/2021 às 20:38
  • 2
    Dá uma olhada no perfil do autor da pergunta. Ele escreve algoritmos criptográficos com as mão amarradas. Commented 5/01/2021 às 20:48

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .