Praticamente a função hash portátil de 64 bits mais rápida e com qualidade decente.
Esta é uma tradução do artigo original de Leonid Yuriev .
Em vez de um avisoOmitirei a definição de funções de hash, juntamente com a lista detalhada das propriedades e requisitos para sua aplicação criptográfica, e assumirei que o leitor tenha o conhecimento mínimo necessário ou o lerá . Também deve ser observado que daqui em diante irei falar sobre funções de hash não criptográficas (não adequadas para criptografia), a menos que seja explicitamente indicado o contrário.
BanalidadesO hash é usado em muitos algoritmos e quase sempre é necessário o processamento de dados mais rápido (eficiente), juntamente com um certo nível mínimo de qualidade de hash. Aqui, o termo "qualidade" significa, antes de tudo, uma espécie de "aleatoriedade" (estocástica) em relação aos dados iniciais. Um pouco menos frequentemente, requisitos adicionais são impostos, como resistência à geração deliberada de colisões ou irreversibilidade.
Para ser um pouco mais tediosoPara maior clareza, é necessário definir o conceito de "qualidade" da função hash e o restante dos requisitos em um pouco mais detalhadamente:
Qualidade da linha de base e o efeito avalanche : alterar um ou mais bits arbitrários em um conjunto arbitrário de dados de origem faz com que cada bit do resultado mude com uma probabilidade de ½.
- Irreversibilidade ou resistência à primeira pré-imagem: a impossibilidade de obter os dados originais ou bits individuais a partir do resultado do hash.
- Resistência a colisões de primeira ordem e / ou segunda resistência à pré-imagem: a dificuldade de encontrar / ajustar o conjunto de dados original para obter um resultado especificado ou parte dele, inclusive quando o conjunto de dados inicial é conhecido.
- Resistência a colisões de segunda ordem: a dificuldade de encontrar / ajustar dois conjuntos de dados diferentes que dariam o mesmo resultado ou uma correspondência de uma parte significativa.
Omitindo longas citações da matemática subjacente, pode-se resumir:
- Satisfazer todos os requisitos acima e garantir alto desempenho é um problema bastante difícil, resolver o que nos daria uma boa função de hash criptográfico. Mas não vamos fazer isso ainda.
- O fornecimento de qualidade básica requer um número suficientemente grande de operações da ALU. Simplificando, a qualidade sempre compromete a velocidade.
- A obtenção de um resultado de alta qualidade com uma largura de bit maior que a largura de bit das operações da ALU requer mais do que um aumento de várias vezes no número de misturas e, portanto, operações básicas da ALU.
- Em geral, a criação de uma função rápida de hash envolve a obtenção de um compromisso ponderado entre velocidade, qualidade e resultado do resultado .
Portanto, posso dizer que t1ha surgiu como resultado da busca de um compromisso entre qualidade e velocidade, levando em consideração as capacidades dos processadores modernos e os métodos já encontrados (combinações aritmético-lógicas) de misturar e espalhar dependências ( efeito avalanche).
A versão básica do t1ha é uma das funções de hash portáteis mais rápidas para a construção de tabelas de hash e outros aplicativos relacionados. A versão básica do t1ha é focada em arquiteturas little-endian de 64 bits, utiliza um valor de sal de 64 bits (semente) e produz um resultado de 64 bits, que inclui o fortalecimento do tamanho da chave e da semente. Vale a pena notar que t1ha foi projetado intencionalmente para retornar 0 para zero dados de entrada (uma chave de tamanho zero e zero semente).
Respondendo às perguntas mais popularesOperações de 64 bits : Talvez se deva notar que são as operações de 64 bits que fornecem velocidade e qualidade sem prejudicar a portabilidade. De fato, quanto maior a capacidade de dígitos das operações aritméticas, mais efeito avalanche elas produzem e melhor eles misturam os dados. Além disso, o processamento de dados, todas as outras coisas iguais, certamente é mais rápido em 8 bytes do que em 4. Por outro lado, exatamente as operações de 64 bits estão disponíveis nativamente em muitos processadores modernos e podem ser traduzidas de forma mais ou menos adequada em 32 bits. pouco. Todas as outras opções, incluindo operações SIMD , nos obrigam a sacrificar bastante a portabilidade e / ou a velocidade em plataformas não nativas.
Resultado de 64 bits : para construir tabelas de hash, em muitos casos, um resultado menor de largura de bit é suficiente. Até 32 bits podem ser mais que suficientes. No entanto, ao usar operações de 64 bits, o resultado de 64 bits ocorre naturalmente. Ao mesmo tempo, um resultado de hash de 64 bits de alta qualidade o suficiente permite que você execute rapidamente uma comparação para não-igualdade e com boa precisão para comparar para igualdade.
A "mágica" acima de substituir comparações pode parecer pouco clara e desnecessária ou pode aumentar a velocidade do hash em uma ordem de magnitude apenas por meio da localização dos dados, ou seja, menos poluição do cache da CPU. Simplificando, é possível construir uma estrutura de tabela de hash de tal maneira que os valores calculados do hash fiquem lado a lado (agrupados em linhas de cache). A CPU só pegaria os dados reais se os valores de hash correspondessem. E, neste caso, os 64 bits de t1ha permitem obter o melhor resultado possível . Dito isto, 128 bits não fornecerão mais uma vantagem, enquanto tirar menos de 64 bits é sempre possível.
Comparação com HighwayHash : Eu tenho sentimentos contraditórios sobre esse projeto não oficial por funcionários do Google .
- Por um lado, possui um bom código e excelente implementação técnica. Por outro lado, o HighwayHash está posicionado como possivelmente criptograficamente forte (pelo menos igual ao SipHash ). Dentro do HighwayHash, existem algumas manipulações que nos permitem esperar que o resultado não seja ruim. No entanto, não existem provas que nos permitam dizer isso com segurança. A prova de "força" fornecida se resume aos resultados dos testes estatísticos, mas sem capacidade de reproduzi-los (a certa altura, até me permiti um comentário um tanto supérfluo).
- O HighwayHash é realmente rápido apenas em x86_64 com AVX2 ou SSE41. Não é mais fácil usar apenas a aceleração AES-NI ou SHA?
Se tudo correr bem, opções adicionais serão adicionadas ao pacote t1ha (principalmente para o resultado obtido) e otimizadas para o E2K. Com isso, gostaria de encerrar o tópico de comparações com o HighwayHash.
Qualidade
Avaliar a qualidade de uma função de hash em todos os aspectos pode ser bastante difícil. Isso pode ser feito analiticamente ou implementando vários testes estatísticos. Infelizmente, a abordagem analítica não é muito eficaz para avaliar as funções de hash com um compromisso entre qualidade e velocidade. Além disso, uma avaliação analítica comparativa de tais funções tende a ser subjetiva.
Por outro lado, testes estatísticos podem fornecer estimativas quantitativas claras. Para tais fins, existem pacotes de teste comprovados, como o SMHasher . Para t1ha , os resultados são simples - todas as opções de t1ha passam em todos os testes sem comentários. Por outro lado, não se deve presumir que t1ha possua propriedades que excedam as necessárias para o aplicativo de destino (construção de tabelas de hash).
O número de colisões em todos os níveis (variantes) de t1ha corresponde ao paradoxo do aniversário . Para formulá-lo estritamente - a probabilidade de colisão em t1ha corresponde à probabilidade de coincidência de valores discretos aleatórios com o número de bits correspondente.
Uma probabilidade similar de colisões é observada em todas as funções de hash de alta qualidade. No entanto, isso é apenas probabilidade, portanto, o número real de colisões pode variar para cada conjunto de dados específico.
Após a publicação deste artigo, Yves Orton descobriu que o primeiro t1ha1() nem sempre atende ao rigoroso critério de avalanche . Essa desvantagem é insignificante para aplicações direcionadas de t1ha1() e imperceptível do ponto de vista prático. No entanto, essa desvantagem é eliminada no próximo nível / variante t1ha2() , que foi originalmente planejado para fornecer uma qualidade um pouco mais alta. Nos novos processadores, que usam versões atuais dos compiladores, t1ha2() é, em média, um ciclo mais rápido que t1ha1() e, nos demais casos, pode ser um ciclo mais lento. Vale ressaltar que t1ha2() oferece adicionalmente o modo de hash de fluxo e um resultado de 128 bits.
Os leitores certamente apreciariam uma análise completa e aprofundada da qualidade e / ou força do t1ha . No entanto, com base nas áreas de aplicação t1ha de destino, isso parece redundante. Simplificando, a velocidade era mais importante para nós, mesmo para teclas curtas. Portanto, a mistura multi-rodada não foi considerada. A atual versão t1ha economiza ciclos e fornece um resultado de 64 bits - é praticamente inútil medir o comprometimento encontrado de qualquer maneira que não seja estatisticamente, e seus resultados são simplesmente bons.
De fatoEu apenas segui meus colegas do Google em como eles fornecem sua prova estatística
Benchmarks
Quanto à alegação de ser " o mais rápido ". é importante observar que obviamente não é provável que exista uma função de hash que seja ao mesmo tempo útil e a mais rápida em todas as plataformas / arquiteturas. Processadores diferentes têm conjuntos de instruções diferentes disponíveis e executam instruções semelhantes com diferentes eficiências. Obviamente, a função " universalmente mais rápida " provavelmente não pode ser criada. No entanto, parece aceitável usar o termo "o
mais rápido »para uma função que é portátil e ao mesmo tempo a mais rápida, pelo menos na plataforma mais comum (x86_64), embora tenha poucas chances de perder em qualquer processador moderno com um compilador de otimização decente.
O código-fonte do projeto inclui um teste que verifica a correção do resultado e mede a velocidade de cada variante implementada. Ao mesmo tempo, no x86, dependendo dos recursos do processador (e do compilador), variantes adicionais de funções podem ser verificadas e medidas são feitas nos ciclos do processador.
Além disso, o site do projeto contém tabelas com os resultados das medições de desempenho por meio de uma versão modificada do SMHasher da Reini Urban . Pode-se verificar duas vezes todas as figuras e / ou obter resultados em um processador específico usando um compilador específico.
Aqui você pode comparar t1ha com alguns de seus concorrentes mais próximos.
Teclas curtas de hash (média de 1 a 31 bytes).
Veja a coluna da direita "Ciclos / Hash" (quanto menor, melhor) :
| Função | MiB / Segundo | Ciclos / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Fasthash64 | 5578.06 | 43,42 |
| CityHash64 | 11041.72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Metrohash | 11808.92 | 46,33 |
Hashing chaves longas (256 Kb).
Veja a coluna do meio “MiB / Second” (quanto maior, melhor) :
| Função | MiB / Segundo | Ciclos / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Farmhash64 | 12145.36 | 60.12 |
| CityHash64 | 11041.72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Spooky64 | 11820.20 | 60,39 |
Variantes de t1ha
Desenvolvimento de t1ha O primeiro desses objetivos foi obter uma função portátil rápida de qualidade suficientemente alta para a construção de tabelas de hash.
Em seguida, queríamos ter a versão mais rápida da função hash que resultasse em qualidade comparável, mas que fosse adaptada à plataforma de destino o máximo possível. Por exemplo, a versão t1ha básica funciona com ordem de bytes little-endian, devido à qual é necessária uma conversão para arquiteturas big-endian com inevitável perda de desempenho. Então, por que não se livrar de operações desnecessárias em uma plataforma de destino específica? Dessa forma, várias outras opções foram adicionadas:
- Versão simplificada para plataformas de 32 bits, pequena e big endian.
- Variante usando as instruções da AES-NI, mas sem o AVX.
- Duas variantes usando as instruções AES-NI e AVX.
Mais tarde, ficou claro que seriam necessárias mais opções projetadas para várias aplicações, incluindo diferentes resultados de largura de bits, requisitos de qualidade e durabilidade. Essa diversidade exigiu sistematização adequada. Isso foi alcançado alterando o esquema de nomenclatura, no qual o sufixo numérico indica o "nível" da função:
t1ha0() - é a opção mais rápida para o processador atual.t1ha1() - é a versão básica portátil de 64 bits do t1ha.t1ha2() - é uma versão portátil de 64 bits com um pouco mais de preocupação com a qualidade.t1ha3() - é uma versão rápida e portátil de 128 bits para impressões digitais.- etc.
Nesse esquema, supõe-se que t1ha0() seja um despachante que implemente o redirecionamento, dependendo da plataforma e dos recursos do processador atual. Além disso, o uso dos sufixos "_le" e "_be" para uma escolha explícita entre as variantes little-endian e big-endian pode ser introduzido. Assim, sob a placa “t1ha” agora existem várias funções de hash, e essa família crescerá no futuro, incluindo uma versão otimizada para o russo E2K “Elbrus”.
Uma idéia geral do conjunto atual de funções e suas propriedades pode ser entendida observando a saída de teste interna ( make check ). Vale ressaltar que todas as funções são aprovadas em todos os testes do SM Hasher, e o desempenho das variantes do AES-NI varia muito, dependendo do modelo do processador:
Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz
Um pouco sobre a estrutura internaPara aprofundar um pouco mais detalhadamente, o t1ha é construído de acordo com o esquema Merkle-Damgård (versão “wipe-pipe”) com reforço do tamanho dos dados e do valor da semente. Dentro do loop de compactação principal, é utilizado um estado de 256 bits, com o mesmo tamanho do bloco de entrada. Além disso, para cada operando de dados existem dois pontos de injeção com polinização cruzada. Após a conclusão do ciclo de compactação, o estado de 256 bits é compactado para 128 bits.
Ao executar as ações acima, são utilizadas operações de 64 bits, combinadas nos mixers ARX (Add-Rotate-Xor) e MUX / MRX (Mul-Rotate-Xor). É importante que todos esses cálculos sejam construídos de forma a garantir a possibilidade de execução paralela da maioria das operações e compactação apertada de operações opcionais, tanto no pipeline quanto nas unidades de execução x86_64. Devido a isso, é alcançada uma qualidade suficientemente boa, com taxa de hash quase máxima para chaves longas.
Vale ressaltar que o loop de compressão é executado apenas para blocos de tamanho suficiente. Se houver menos dados, o estado intermediário de 128 bits consistirá apenas no tamanho da chave e no valor do sal.
Em seguida, a cauda restante dos dados é misturada em partes de 64 bits alternadamente às metades do estado de 128 bits. Finalmente, o estado é misto e compactado simultaneamente para um resultado de 64 bits. Uma característica importante de t1ha aqui é o uso de um misturador baseado em ampla multiplicação (produto de 128 bits de dois multiplicadores de 64 bits). Isso permite uma mistura de boa qualidade com um bom efeito de avalanche e menos operações. Embora a multiplicação ampla seja uma operação relativamente cara, poucas operações permitem que t1ha processe teclas curtas em um número recorde de ciclos do processador.
Note-se que o misturador baseado em ampla multiplicação e OR exclusivo não é perfeito. Embora t1ha passe em todos os testes SMHasher , o autor entende as consequências da não-injetividade ). No entanto, a qualidade resultante parece ser racionalmente suficiente, e os planos de desenvolvimento para a linha t1ha já refletem a intenção de fornecer opções de qualidade um pouco mais altas.
Você pode encontrar mais informações e código fonte aqui .
Obrigado pela leitura!