Explorando Funções Hash no Rust: Fowler–Noll–Vo (FNV), SipHash e além…

Funções hash são fundamentais em inúmeros cenários da computação, oferecendo maneiras de representar dados de tamanho arbitrário em valores de tamanho fixo. Neste artigo, vamos nos aprofundar no funcionamento de duas funções hash bem conhecidas — Fowler–Noll–Vo (FNV) e SipHash — focando principalmente em sua implementação na linguagem de programação Rust.

Função Hash Fowler–Noll–Vo (FNV)

Como funciona em um nível baixo

O FNV funciona multiplicando um hash com um número primo e depois fazendo XOR do resultado com um byte da entrada. Isso é feito para cada byte na entrada, produzindo o hash final.

Existem duas variantes principais: FNV-1 e FNV-1a.

FNV-1

hash = ((hash × FNV_prime) XOR octet)

FNV-1a

hash = ((hash XOR octet) × FNV_prime)

Implementação Rust (Usando o crate fnv)

use fnv::FnvHashMap;

fn main() {
   let mut map = FnvHashMap::default();
   map.insert("key", "value");
   println!("{:?}", map.get("key"));
}

Casos de Uso

• Hashing rápido em situações limitadas pela memória.
• Situações em que a força criptográfica não é obrigatória, mas a velocidade é crucial, como tabelas hash.

SipHash

Como funciona em um nível baixo

SipHash é um algoritmo criptográfico que protege contra ataques de negação de serviço por inundação de hash. Em um nível básico, ele usa uma série de SipRounds nos dados de entrada combinados com duas chaves de 64 bits.

O algoritmo processa blocos de mensagens de 64 bits, e seu loop principal consiste em fazer XOR desses blocos no estado, seguido por um número fixo de SipRounds.

Implementação em Rust

O HashMap padrão do Rust usa SipHash por padrão.

use std::collections::HashMap;

fn main() {
   let mut map = HashMap::new();
   map.insert("key", "value");
   println!("{:?}", map.get("key"));
}

Se você precisar de controle mais direto sobre o algoritmo de hash, o Rust fornece as estruturas SipHasher e SipHasher13 no módulo std:#️⃣:SipHasher.

use std::hash::{Hash, Hasher, SipHasher};

fn main() {
   let mut hasher = SipHasher::new();
   "hello world".hash(&mut hasher);
   let hash = hasher.finish();
   println!("Hash is: {}", hash);
}

Casos de Uso

• Proteção contra ataques DoS que exploram funções hash.
• Hashing de propósito geral com um bom equilíbrio entre velocidade e segurança.

Compromissos de Desempenho

Entender o contexto em que você está implantando uma função hash é crucial, e o Rust oferece excelente flexibilidade.

1. FNV

Velocidade: Uma das grandes vantagens do FNV é a sua velocidade. É muito rápido, especialmente para chaves curtas.

Previsibilidade: Sua simplicidade, no entanto, pode ser uma desvantagem. Se um atacante sabe que você está usando FNV, ele pode gerar colisões intencionalmente, desacelerando operações em estruturas de dados como hashmaps (mapas de hash ou tabela de dispersão).

2. SipHash

Segurança: O design do SipHash se concentra na proteção contra ataques de inundação de hash. Isso é crucial para cenários de propósito geral, onde a entrada pode ser adversária.

Compensação da velocidade: Embora o SipHash seja rápido, ele é tipicamente mais lento que o FNV, especialmente para chaves curtas. No entanto, sua robustez frequentemente compensa esse ligeiro declínio no desempenho.

Escolhendo a Função Hash Certa em Rust

1. Avalie seu modelo de ameaça: Se você está projetando um sistema exposto a entradas não confiáveis (por exemplo, um serviço web público), o SipHash é mais seguro devido à sua resistência a ataques hash DoS.
2. Considere seus dados: Para cenários em que suas chaves são conhecidas por serem curtas e não adversárias (como certas operações em memória), a velocidade do FNV pode ser benéfica.
3. Entenda os padrões do Rust: O HashMap do Rust usa o SipHash por padrão porque ele oferece um bom equilíbrio para casos de uso gerais. No entanto, entender por que e quando optar por uma alternativa é crucial para aplicações críticas de desempenho.

Expandindo o Panorama do Hashing em Rust

Além do FNV e SipHash, o ecossistema Rust oferece uma variedade de algoritmos de hashing para se adequar a diferentes contextos. Sendo uma linguagem expressiva que enfatiza desempenho e segurança, Rust permite que os desenvolvedores aproveitem seu robusto sistema de tipos, modelo de propriedade e vasto ecossistema de bibliotecas para implementar e utilizar hashing efetivamente.

Novos Participantes no Ecossistema de Hashing do Rust

1. ahash: Este é um algoritmo de hashing de alta velocidade (mas não criptográfico) projetado especificamente para o HashMap do Rust. É consideravelmente mais rápido que o SipHash em muitos cenários e é uma boa escolha quando o desempenho é primordial e a força criptográfica não é necessária.
2. blake3: Uma evolução do BLAKE2, o BLAKE3 é uma função hash criptográfica que é mais rápida que MD5, SHA-1, SHA-2, SHA-3 e BLAKE2. A implementação em Rust tira total proveito das instruções SIMD, tornando-a adequada para desempenho e segurança criptográfica.

Integrando Geradores de Hashes Personalizados em Rust

O Rust permite que os desenvolvedores definam geradores de hashes (hashers) personalizados e os integrem perfeitamente com as estruturas de dados da biblioteca padrão.

Por exemplo, para usar o ahash com o HashMap do Rust:

use std::collections::HashMap;
use ahash::AHasher;
use std::hash::BuildHasherDefault;

type AHashMap<K, V> = HashMap<K, V, BuildHasherDefault<AHasher>>;fn main() {
   let mut map: AHashMap<&str, &str> = AHashMap::default();
   map.insert("key", "value");
   println!("{:?}", map.get("key"));
}

Benchmarks e Comparações:

Ao selecionar um algoritmo de hashing, é essencial realizar benchmarks relevantes para o seu caso de uso. Embora o ecossistema Rust frequentemente forneça benchmarks comparando diferentes funções hash, o desempenho no mundo real pode variar com base em padrões de dados, arquitetura do sistema e características da carga de trabalho.

Ferramentas como criterion-rs podem ajudá-lo a conduzir benchmarks precisos em Rust, garantindo que você tome uma decisão informada.

Melhores Práticas:

1. Atualize regularmente as dependências: Algoritmos de hashing podem ter vulnerabilidades. Atualizar regularmente seus pacotes Rust garante que você se beneficie das últimas correções de segurança.
2. Equilibre desempenho e segurança: Embora um gerador de hash como o FNV seja extremamente rápido, ele pode não ser adequado para contextos adversários. Sempre considere as implicações de segurança de sua escolha.
3. Aproveite o sistema de tipos do Rust: O Rust permite que você crie aliases de tipo e novos tipos. Use-os para tornar seu código mais expressivo e garantir que o gerador de hash correto seja usado no contexto adequado.

Conclusão:

Hashing é um domínio complexo com vantagens que abrangem desempenho, segurança e necessidades específicas do domínio. Com seu foco em abstrações de custo zero e segurança de memória, o Rust oferece aos desenvolvedores uma vasta caixa de ferramentas para geração de hashes. Ao entender as nuances das funções hash disponíveis, manter-se atualizado com o ecossistema em evolução e aproveitar as características únicas do Rust, os desenvolvedores podem criar sistemas tanto performáticos quanto seguros.

Fique ligado e boa programação!

Visite meu Blog para mais artigos, notícias e coisas sobre engenharia de software!

Siga-me no Medium, LinkedIn e Twitter.

Tudo de bom!

CTO | Engenheiro de Software Sênior | Líder Técnico | Arquiteto de Soluções AWS | Rust | Golang | Java | ML IA & Estatísticas | Web3 & Blockchain

Artigo original publicado por Luis Soares. Traduzido por Paulinho Giovannini.