lucy-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nick Wellnhofer (JIRA)" <j...@apache.org>
Subject [lucy-issues] [jira] [Commented] (CLOWNFISH-48) Protect Hash against algorithmic complexity attacks
Date Thu, 02 Jul 2015 19:11:05 GMT

    [ https://issues.apache.org/jira/browse/CLOWNFISH-48?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14612395#comment-14612395
] 

Nick Wellnhofer commented on CLOWNFISH-48:
------------------------------------------

Another approach is to use [SipHash|https://131002.net/siphash/], a relatively fast, cryptographically
strong hash function. It is used by Ruby, Rust, Python (since 3.4), and in many other projects.
SipHash is reasonably fast on 64-bit systems. On x86, performance can be improved with SSE.

> Protect Hash against algorithmic complexity attacks
> ---------------------------------------------------
>
>                 Key: CLOWNFISH-48
>                 URL: https://issues.apache.org/jira/browse/CLOWNFISH-48
>             Project: Apache Lucy-Clownfish
>          Issue Type: Improvement
>            Reporter: Nick Wellnhofer
>
> We should randomize our hash function to protect against algorithmic complexity attacks.
We should also consider randomizing the order of hash entries returned by Hash_Keys, Hash_Values,
and HashIterator to protect against key discovery attacks.
> This is a hard topic, so I'd suggest to copy Perl's implementation. Perl was one of the
first languages to address this issue in 2003 and to improve protection against new attack
vectors in 2013.
> Perl's standard hash function is Jenkins' one-at-a-time hash. The computation starts
with a per-interpreter random seed and also appends four random bytes to every string being
hashed. The latter is important to protect against attacks discovered in 2013.
> The randomization of the order of hash entries works by XORing the index into the hash
table with a random value which is updated on every hash insert.
> A good write-up can be found here:
> http://blog.booking.com/hardening-perls-hash-function.html
> We'll also need a cross-platform way to get good quality random seeds.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message