Boa noite amigos!
Vimos no versículo anterior a parte 3. No versículo de hoje veremos a quarta parte da tradução de “The Sybil Attack”.
3.1 Validação de identidade direta
O único meio direto pelo qual duas entidades podem convencer uma terceira entidade de que elas são distintas é performando alguma tarefa que uma única entidade não poderia. Se assumirmos que os recursos de quaisquer duas entidades diferem por, no máximo, um fator constante, uma entidade pode exigir prova dos recursos de uma entidade remota antes de aceitar sua identidade. Todavia, isso nos deixa com a seguinte limitação:
Lema 1: Se ρ é a razão dos recursos de uma entidade faltosa ? para os recursos de uma entidade minimamente capaz, então ? pode apresentar ? = |_ρ_| identidades distintas para entidade local l.
O Lema 1 indica um limite inferior no dano alcançável por uma entidade faltosa. Para mostrar como isso pode ser aplicado como um limite superior, apresentamos três mecanismos que podem (pelo menos teoricamente) explorar limitações em três diferentes recursos: comunicação, armazenamento e computação.
Se os recursos de comunicação são restritos, a entidade local l pode transmitir uma requisição por identidades e então apenas respostas que ocorram dentro de um dado intervalo de tempo.
Se os recursos de armazenamento são restritos, a entidade l pode desafiar cada identidade a armazenar uma grande quantidade de dados únicos e não compactáveis. Mantendo pequenos trechos desses dados, a entidade l pode verificar, com probabilidade arbitrariamente alta, que todas as entidades armazenam simultaneamente os dados que lhe foram enviados.
Se recursos computacionais são restritos, a entidade l pode desafiar cada identidade a resolver um quebra-cabeças computacional único. Por exemplo, a entidade local pode gerar um grande valor aleatório y e desafiar a identidade a encontrar, dentro de um tempo limitado, um par de valores x, z tal que a concatenação x | y | z, quando executada em uma função hash segura, resulta um valor cujo menor n bits significativos são todos zero:
dado y, encontre x, z tal que LSBn(hash(x | y | z)) = 0
2* medido na contagem de avaliações da função hash. Para uma função has aleatória oracle [2], a única maneira de encontrar uma solução é iterar pelos valores candidatos de x e/ou z, computar o hash para cada x | y | z triplo; e testar o resultado. A implementação real requer uma função hash que é resistente tanto a pré-imagem quanto a ataques de força não-bruta, como ataques de encadeamento [24].
[2] M. Bellare and P. Rogaway, “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols”, 1st Conference on Computer and Communications Security, ACM, 1993, pp. 62-73.[24]A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
Fim da quarta parte. No versículo seguinte a quinta. Deus os abençoe!
