Técnica de busca automatizada de funções hash inteiras

Hash Function Prospector

Esta ferramenta é uma ferramenta pequena para a busca automatizada de funções hash inteiras. Ela seleciona aleatoriamente entre 9 operações reversíveis e gera bilhões de funções hash inteiras. As funções geradas são compiladas com JIT e o comportamento de Avalanche é avaliado. A melhor função encontrada atualmente é exibida em sintaxe C.

• Pontuação de Avalanche: o número de bits de saída que, em média, permanecem inalterados quando um único bit de entrada é invertido. Quanto menor a pontuação, melhor. O ideal é que a pontuação seja 0. Ou seja, ao inverter um único bit de entrada, todos os bits de saída são invertidos com probabilidade de 50%.
• O Prospector pode gerar funções hash inteiras de 32 e 64 bits. Consulte o uso (-h) para ver todas as opções. Por causa do compilador JIT, apenas x86-64 é suportado, mas as funções descobertas podem ser usadas em qualquer ambiente.

Funções hash descobertas

Há duas classes úteis de funções hash descobertas pelo Prospector e por outras utilidades auxiliares incluídas aqui. Ambas usam a estrutura xorshift-multiply-xorshift, mas o número de rodadas é diferente.

Função de 2 rodadas

TheIronBorn usou otimização combinatória para encontrar os melhores parâmetros conhecidos para essa estrutura.

• Esta permutação de 2 rodadas de 32 bits possui especialmente baixo viés e até vence, por uma pequena margem, o finalizador de 32 bits do MurmurHash3.
• A estrutura da função hash foi descoberta pelo Prospector, e os parâmetros foram ajustados com hill climbing e algoritmo genético.

Há mais constantes de 2 rodadas com viés baixo, e algumas delas são melhores que lowbias32.

Função de 3 rodadas

Adicionar mais uma rodada de multiply-xorshift a essa estrutura permite atingir o limite teórico de viés com parâmetros cuidadosamente escolhidos. Por exemplo, esta função hash pode se tornar indistinguível de uma PRF perfeita.

• triple32 resolve o problema hash(0) = 0 e também reduz ainda mais o viés.
• Há mais constantes de 3 rodadas com viés mais baixo.

Medição de viés precisa

O modo -E avalia o viés da função hash fornecida (-p ou -l). Por padrão, o Prospector usa uma estimativa para avaliar rapidamente o viés da função, mas ela é não determinística e com muito ruído nos resultados. Use a opção -e para medir o viés de forma exaustiva e precisa.

• Você pode definir a função a ser testada com -p usando um padrão, ou com uma biblioteca compartilhada que contenha uma função hash() e a opção -l.
• Para funções hash de 64 bits, não há teste exaustivo e preciso, pois é demorado demais.

Seleção de operações reversíveis

São usadas as seguintes operações reversíveis:

• x = ~x;
• x ^= constant;
• x *= constant | 1; (somente constantes ímpares)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (rotação à esquerda)
• x = bswap(x) (troca os bytes alto e baixo)

Tecnicamente, x = ~x já é coberto por x ^= constant; no entanto, ~x é singularmente especial e, em particular, muito útil.

Hash de 16 bits

Como as restrições de hash de 16 bits são diferentes, há uma ferramenta separada (hp16) para gerar esse tipo de hash.

• Ao contrário do Prospector de 32/64 bits, esta implementação é totalmente portátil e pode ser executada em quase todos os sistemas.
• Também é possível gerar e avaliar S-boxes de 128 KiB.
• Como o hash de 16 bits pode ser mais necessário em máquinas sem instrução de multiplicação rápida, pode-se omitir certas operações durante a busca (-m, -r).

Alguns resultados interessantes:

• hash xorshift-multiply de 2 rodadas
• hash xorshift-multiply de 3 rodadas
• hash sem multiplicação (apenas xorshift-add)

Um bom hash xorshift de 3 rodadas (busca curta via hp16 -Xn3) se aproxima de uma boa S-box (hp16 -S).

Ao trabalhar com operações de 16 bits, é preciso ter cuidado com as regras de promoção de inteiros em C. O programa C emitido por esta ferramenta cuida para promover operações de 16 bits para unsigned int quando necessário.

Opinião do GN⁺

• A segurança de funções hash é muito importante em criptografia e segurança computacional, então uma ferramenta de busca como essa parece poder ajudar bastante na pesquisa. Em especial, é interessante encontrar funções hash de baixo viés por meio de busca aleatória.

• No entanto, a segurança de uma função hash não é garantida apenas por propriedades estatísticas. Funções hash criptográficas também precisam ser resistentes a ataques de PreImage Resistance, Second PreImage Resistance e Collision Resistance, então essas análises também parecem necessárias.

• Hashes de 16 bits devem ser úteis em ambientes restritos, como sistemas IoT e embarcados. O fato de ser possível criar funções hash usando apenas ADD/XOR/SHIFT, para serem usadas também em CPUs sem instrução de multiplicação, é bastante impressionante.

• A aplicação de técnicas de busca heurística como Hill Climbing e algoritmo genético no projeto de funções hash é uma ideia interessante. O esforço de integrar IA no design de algoritmos criptográficos está ficando cada vez mais forte, e essas técnicas de otimização parecem ter papel crescente no futuro.

• Como há limites intrínsecos de função hash, mesmo com ótima propriedade Avalanche não dá para afirmar com segurança que ela é segura criptograficamente; isso parece ser a limitação do projeto. Ainda assim, ferramentas como essa podem ajudar a analisar falhas e a melhorar funções hash existentes.

[GN⁺]

Comentário no Hacker News

• Motivos pelos quais ele gosta do código do desenvolvedor
  • Gosta de biblioteca de JSON, biblioteca de parsing de opções, decodificador UTF-8 sem ramificações, pilha lock-free e biblioteca trie
  • Gosta também do fato de que essas bibliotecas foram publicadas sob Unlicense
• Comentário do desenvolvedor do MurmurHash
  • Comentou que é interessante a operação multiply-shift-xor ter se mantido bem por tanto tempo
• Compartilha ideias sobre busca automática de função hash
  • Sugere integrar com o SMHasher3 para avaliar automaticamente a saída
    • Dá para priorizar velocidade, usar apenas alguns testes e falhar rapidamente
  • Seria bom expandir para 64 e 128 bits (o espaço de busca é maior)
  • Criou um código em NodeJS na biblioteca Rain para medir o efeito avalanche de multiplicação por primos de 64 bits
• Compartilha a experiência de implementar o problema 1brc em Go
  • Tentou encontrar uma função hash perfeita customizada para colocar cada estação em seu próprio bucket sem colisões, mas desistiu por causa da regra de não poder personalizar a função hash com base nos dados antes do início do programa
  • Fez uma ferramenta de teste para conferir constantes aleatórias e imprimir, conforme o número de buckets e o número de colisões, a melhor constante encontrada até o momento
    • Com taxa de ocupação de cerca de 40%, conseguiu reduzir para 1 bucket com apenas 2 valores em colisão
    • Foi interessante notar que valores semelhantes para a quantidade de posições de deslocamento entravam na melhor constante de desempenho, independente de outras constantes
• Pede uma explicação do porque esse código é legal e quais são os casos de uso
• Questiona exatamente o que o código faz, se ele busca a melhor função hash, e, se não, por que a melhor função muda a cada execução
• Pede informações sobre o mecanismo de descoberta de uma boa função hash para um intervalo específico de valores inteiros
  • Por exemplo, se você conhece valores inteiros entre 10.000 e 200.000 e quer fazer hash com um número ótimo de buckets
• Há o comentário de que restringir operações reversíveis tem uma boa propriedade matemática, porém exclui muita coisa
  • Pensou em hash perfeito ao conhecer previamente o conjunto de entradas
  • Normalmente usa-se array de constantes, mas queria saber se dá para comprimir mais quando a entrada já são inteiros pequenos
  • Fez uma lista com cerca de 100 operações básicas, mas ficou entediado e não prosseguiu com o projeto
• A opinião de que usar a mesma constante em duas multiplicações pode reduzir o tamanho do código e, portanto, aumentar um pouco a velocidade de cálculo
• Ainda que reconheça que essas funções não são adequadas para operações criptográficas, levanta perguntas sobre o impacto do "bias" medido na criptoanálise
  • Fica curioso se alguém familiar com criptografia diferencial pode explicar
  • Fica curioso se uma função hash de baixa preferência pode derrubar a criptoanálise com menos rodadas ou menos computação
  • Pergunta se essa ferramenta ajudaria a encontrar uma função hash criptográfica melhor
• Apresenta projetos semelhantes
  • A velocidade é baixa (por usar interpretador), mas a qualidade da função é melhor
  • Mas não encontrou nada melhor que funções hash existentes