[lucy-issues] [jira] [Commented] (CLOWNFISH-48) Protect Hash against algorithmic complexity attacks

["Nick Wellnhofer (JIRA)" <ji...@apache.org>]

    [ 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)