use SIPhash for OPENSSL_LH_strhash?

classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: use SIPhash for OPENSSL_LH_strhash?

Sands, Daniel
With a small number of buckets, it seems to me that no hash algo will
make you safe from a flooding attack.  You can simply generate your
hashes locally using whichever algo the server uses, and only send those
that fit into your attack scheme.  The data could even be pre-generated.

The only way to guard against a flood that makes sense to me is to limit
the number of items that can be accepted before deciding you're being
trolled.

On Wed, 2017-01-11 at 23:29 +0000, J. J. Farrell wrote:

> Are the issues you raise true of SipHash, given that a prime motivator
> for its design was generating hash tables for short inputs while being
> secure against hash flooding attacks? It achieves this with the
> performance of a portable C implementation the order of four times
> faster than MD5, and not much slower than other modern hash
> algorithms.
>
> I'd have thought the main thing to consider is whether or not there is
> any practical way a hash flooding attack could be used against
> OpenSSL's hash tables, and it sounds like there isn't. In that case,
> the fastest algorithm for the usage patterns would be best.
>
> Regards,
>                           jjf
>
> On 11/01/2017 22:25, Peter Waltenberg wrote:
>
> > And the reason I said you certainly don't need a keyed hash ?
> >
> > Behaviour of the hash function will change with key and in some
> > cases performance would degenerate to that of a linked list. (Ouch).
> > And since the obvious thing to do is use a random key, OpenSSL's
> > performance would get *very* erratic.
> >
> > Simpler functions than cryptographic hashes will almost certainly
> > yield better results here. I note someone further up the thread
> > someone else has pointed that out.
> >
> > Peter
> >
> > From:        "Salz, Rich" <[hidden email]>
> > To:        "[hidden email]" <[hidden email]>
> > Date:        11/01/2017 13:14
> > Subject:        Re: [openssl-dev] use SIPhash for
> > OPENSSL_LH_strhash?
> > Sent by:        "openssl-dev" <[hidden email]>
> >
> > ____________________________________________________________________
> >
> > The needs for OpenSSL's LHASH are exactly what SipHash was designed
> > for: fast on short strings.
> > OpenSSL's hash currently *does not* call MD5 or SHA1; the MD5 code
> > is commented out.
> > Yes, performance tests would greatly inform the decision.
>
> --
> J. J. Farrell
> Not speaking for Oracle
> --
> openssl-dev mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: use SIPhash for OPENSSL_LH_strhash?

J. J. Farrell-2
For something like SipHash, knowing "whichever algo the server uses" effectively implies knowing the 128-bit random key currently being used for the hash table in question.

Regards,
                          jjf

On 12/01/2017 00:39, Sands, Daniel wrote:
With a small number of buckets, it seems to me that no hash algo will
make you safe from a flooding attack.  You can simply generate your
hashes locally using whichever algo the server uses, and only send those
that fit into your attack scheme.  The data could even be pre-generated.

The only way to guard against a flood that makes sense to me is to limit
the number of items that can be accepted before deciding you're being
trolled.

On Wed, 2017-01-11 at 23:29 +0000, J. J. Farrell wrote:
Are the issues you raise true of SipHash, given that a prime motivator
for its design was generating hash tables for short inputs while being
secure against hash flooding attacks? It achieves this with the
performance of a portable C implementation the order of four times
faster than MD5, and not much slower than other modern hash
algorithms.

I'd have thought the main thing to consider is whether or not there is
any practical way a hash flooding attack could be used against
OpenSSL's hash tables, and it sounds like there isn't. In that case,
the fastest algorithm for the usage patterns would be best.

Regards,
                          jjf

On 11/01/2017 22:25, Peter Waltenberg wrote:

And the reason I said you certainly don't need a keyed hash ?

Behaviour of the hash function will change with key and in some
cases performance would degenerate to that of a linked list. (Ouch).
And since the obvious thing to do is use a random key, OpenSSL's
performance would get *very* erratic.

Simpler functions than cryptographic hashes will almost certainly
yield better results here. I note someone further up the thread
someone else has pointed that out. 

Peter

From:        "Salz, Rich" [hidden email]
To:        [hidden email] [hidden email]
Date:        11/01/2017 13:14
Subject:        Re: [openssl-dev] use SIPhash for
OPENSSL_LH_strhash?
Sent by:        "openssl-dev" [hidden email]

____________________________________________________________________

The needs for OpenSSL's LHASH are exactly what SipHash was designed
for: fast on short strings.
OpenSSL's hash currently *does not* call MD5 or SHA1; the MD5 code
is commented out.
Yes, performance tests would greatly inform the decision.
-- 
J. J. Farrell
Not speaking for Oracle
-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

    

-- 
J. J. Farrell
w: +44 161 493 4838

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Peter Waltenberg
In reply to this post by J. J. Farrell-2

It pretty much has to be true of any keyed hash if you think about it. If it didn't distribute the hashes differently each time it wouldn't be working, if it distributes the hashes differently, performance has to be key dependent. And with a hash size the same as the key, at least one of the possible combinations has to be the pathological case.

I can't currently see any possible vector for a flooding attack, well O.K., I certainly can if you use SipHash with random keys :) and even that would be hard to exploit, but otherwise no. If it's significantly faster using it with a pre-tested fixed key is probably fine, but it gives up the security characteristic you were after. My suspicion is also that simply compressing the string with XOR will work at least as well.

Peter



-----"openssl-dev" <[hidden email]> wrote: -----
To: [hidden email]
From: "J. J. Farrell"
Sent by: "openssl-dev"
Date: 01/12/2017 10:05AM
Subject: Re: [openssl-dev] use SIPhash for OPENSSL_LH_strhash?

Are the issues you raise true of SipHash, given that a prime motivator for its design was generating hash tables for short inputs while being secure against hash flooding attacks? It achieves this with the performance of a portable C implementation the order of four times faster than MD5, and not much slower than other modern hash algorithms.

I'd have thought the main thing to consider is whether or not there is any practical way a hash flooding attack could be used against OpenSSL's hash tables, and it sounds like there isn't. In that case, the fastest algorithm for the usage patterns would be best.

Regards,
                          jjf

On 11/01/2017 22:25, Peter Waltenberg wrote:
And the reason I said you certainly don't need a keyed hash ?

Behaviour of the hash function will change with key and in some cases performance would degenerate to that of a linked list. (Ouch). And since the obvious thing to do is use a random key, OpenSSL's performance would get *very* erratic.

Simpler functions than cryptographic hashes will almost certainly yield better results here. I note someone further up the thread someone else has pointed that out.

Peter

From:        "Salz, Rich" [hidden email]
To:        [hidden email] [hidden email]
Date:        11/01/2017 13:14
Subject:        Re: [openssl-dev] use SIPhash for OPENSSL_LH_strhash?
Sent by:        "openssl-dev" [hidden email]


The needs for OpenSSL's LHASH are exactly what SipHash was designed for: fast on short strings.
OpenSSL's hash currently *does not* call MD5 or SHA1; the MD5 code is commented out.
Yes, performance tests would greatly inform the decision.


--
J. J. Farrell
Not speaking for Oracle
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev


--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: use SIPhash for OPENSSL_LH_strhash?

Peter Waltenberg
In reply to this post by J. J. Farrell-2
Yes, but. LHash hashes internal object names not externally presented input.

Certainly if it's used on externally presented data it's a worthwhile change, but AFAIK that isn't the case.

Peter



-----"openssl-dev" <[hidden email]> wrote: -----
To: [hidden email]
From: Jeremy Farrell
Sent by: "openssl-dev"
Date: 01/12/2017 11:17AM
Subject: Re: [openssl-dev] [EXTERNAL] Re: use SIPhash for OPENSSL_LH_strhash?

For something like SipHash, knowing "whichever algo the server uses" effectively implies knowing the 128-bit random key currently being used for the hash table in question.

Regards,
                          jjf

On 12/01/2017 00:39, Sands, Daniel wrote:
With a small number of buckets, it seems to me that no hash algo will
make you safe from a flooding attack.  You can simply generate your
hashes locally using whichever algo the server uses, and only send those
that fit into your attack scheme.  The data could even be pre-generated.

The only way to guard against a flood that makes sense to me is to limit
the number of items that can be accepted before deciding you're being
trolled.

On Wed, 2017-01-11 at 23:29 +0000, J. J. Farrell wrote:
Are the issues you raise true of SipHash, given that a prime motivator
for its design was generating hash tables for short inputs while being
secure against hash flooding attacks? It achieves this with the
performance of a portable C implementation the order of four times
faster than MD5, and not much slower than other modern hash
algorithms.

I'd have thought the main thing to consider is whether or not there is
any practical way a hash flooding attack could be used against
OpenSSL's hash tables, and it sounds like there isn't. In that case,
the fastest algorithm for the usage patterns would be best.

Regards,
                          jjf

On 11/01/2017 22:25, Peter Waltenberg wrote:

And the reason I said you certainly don't need a keyed hash ?

Behaviour of the hash function will change with key and in some
cases performance would degenerate to that of a linked list. (Ouch).
And since the obvious thing to do is use a random key, OpenSSL's
performance would get *very* erratic.

Simpler functions than cryptographic hashes will almost certainly
yield better results here. I note someone further up the thread
someone else has pointed that out.

Peter

From:        "Salz, Rich" [hidden email]
To:        [hidden email] [hidden email]
Date:        11/01/2017 13:14
Subject:        Re: [openssl-dev] use SIPhash for
OPENSSL_LH_strhash?
Sent by:        "openssl-dev" [hidden email]

____________________________________________________________________

The needs for OpenSSL's LHASH are exactly what SipHash was designed
for: fast on short strings.
OpenSSL's hash currently *does not* call MD5 or SHA1; the MD5 code
is commented out.
Yes, performance tests would greatly inform the decision.
--
J. J. Farrell
Not speaking for Oracle
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

--
J. J. Farrell
w: +44 161 493 4838
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev


--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: use SIPhash for OPENSSL_LH_strhash?

Hubert Kario
In reply to this post by Sands, Daniel
On Wednesday, 11 January 2017 18:09:04 CET Sands, Daniel wrote:
> Just a note from my own experience way back when:  I tried hashing using
> various algos and measuring bucket use as the main comparison criteria.
> I found that the crypto hashes left a fair number of unused buckets.

I can explain that only in two ways:
 1. "crypto hashes" were biased
 2. the test used too many buckets compared to number of entries

to put it mildly, option 1 is "unlikely"

so since I don't want to point fingers, I'd say we need more data before we
can discredit use of cryptographically secure hashes for this use case...

> Of
> course, CRCs were far worse.  What gave the most normal distribution was
> to simply take the bytes 4 at a time as 32-bit integers and simply add
> them.
>
> Not to say that this is really the holy grail, just pointing out that
> compute speed shouldn't be the only criteria you use for comparison.
>
> On Wed, 2017-01-11 at 15:43 +0100, Richard Levitte wrote:
> > A note: I have absolutely nothing against the addition of SIPhash in
> > our collection of hash algos.  My scepticism was only in regards to
> > using it as a string hasher for our hash tables indexes.
> >
> > Cheers,
> > Richard
> >
> > In message <[hidden email]> on
> > Wed, 11 Jan 2017 15:34:58 +0100 (CET), Richard Levitte
> > <[hidden email]> said:
> >
> > levitte> In message
> > <[hidden email]> on
> > Wed, 11 Jan 2017 03:13:39 +0000, "Salz, Rich" <[hidden email]> said:
> > levitte>
> > levitte> rsalz> The needs for OpenSSL's LHASH are exactly what SipHash was
> > designed for: fast on short strings. levitte> rsalz> OpenSSL's hash
> > currently *does not* call MD5 or SHA1; the MD5 code is commented out.
> > levitte> rsalz> Yes, performance tests would greatly inform the decision.
> > levitte>
> > levitte> Done, using the reference siphash implementation.
> > levitte>
> > levitte> https://github.com/levitte/openssl/tree/test-string-hashes
> > levitte>
> > levitte> A run on my laptop gave these results:
> > levitte>
> > levitte>     : ; ./util/shlib_wrap.sh apps/openssl speed siphash lhash
> > levitte>     Doing lhash for 3s on 16 size blocks: 27635188 lhash's in
> > 3.00s levitte>     Doing lhash for 3s on 64 size blocks: 6934726 lhash's
> > in 3.00s levitte>     Doing lhash for 3s on 256 size blocks: 1698489
> > lhash's in 3.00s levitte>     Doing lhash for 3s on 1024 size blocks:
> > 431185 lhash's in 3.00s levitte>     Doing lhash for 3s on 8192 size
> > blocks: 53868 lhash's in 3.00s levitte>     Doing lhash for 3s on 16384
> > size blocks: 27041 lhash's in 3.00s levitte>     Doing siphash for 3s on
> > 16 size blocks: 22488748 siphash's in 3.00s levitte>     Doing siphash
> > for 3s on 64 size blocks: 10485674 siphash's in 3.00s levitte>     Doing
> > siphash for 3s on 256 size blocks: 3320898 siphash's in 3.00s levitte>  
> >  Doing siphash for 3s on 1024 size blocks: 894647 siphash's in 3.00s
> > levitte>     Doing siphash for 3s on 8192 size blocks: 114170 siphash's
> > in 3.00s levitte>     Doing siphash for 3s on 16384 size blocks: 57151
> > siphash's in 3.00s levitte>     OpenSSL 1.1.1-dev  xx XXX xxxx
> > levitte>     built on: reproducible build, date unspecified
> > levitte>     options:bn(64,64) rc4(16x,int) des(int) aes(partial)
> > idea(int) blowfish(ptr) levitte>     compiler: gcc -DDSO_DLFCN
> > -DHAVE_DLFCN_H -DOPENSSL_THREADS -DOPENSSL_NO_STATIC_ENGINE -DOPENSSL_PIC
> > -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5
> > -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DRC4_ASM
> > -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DGHASH_ASM
> > -DECP_NISTZ256_ASM -DPADLOCK_ASM -DPOLY1305_ASM
> > -DOPENSSLDIR="\"/usr/local/ssl\""
> > -DENGINESDIR="\"/usr/local/lib/engines-1.1\""  -DDEBUG_UNUSED -Wswitch
> > -DPEDANTIC -pedantic -Wno-long-long -Wall -Wsign-compare
> > -Wmissing-prototypes -Wshadow -Wformat -Wtype-limits -Werror
> > -Wa,--noexecstack levitte>     The 'numbers' are in 1000s of bytes per
> > second processed. levitte>     type             16 bytes     64 bytes  
> > 256 bytes   1024 bytes   8192 bytes  16384 bytes levitte>     lhash      
> >     147387.67k   147940.82k   144937.73k   147177.81k   147095.55k  
> > 147679.91k levitte>     siphash         119939.99k   223694.38k  
> > 283383.30k   305372.84k   311760.21k   312120.66k levitte>
> > levitte> So it seems that for short strings, OPENSSL_LH_strhash (*) wins
> > some, levitte> while siphash wins big for larger strings.
> > levitte>
> > levitte> I have no idea how they compare with regard to distribution
> > (which, levitte> considering I ask for the same size output from both,
> > should be the levitte> main factor that affects the sensitivity to hash
> > flooding)... levitte>
> > levitte> Our use of OPENSSL_LH_strhash() is with configuration sections
> > and
> > levitte> names, ASN.1 object names and the function names in the openssl
> > app. levitte> All our other uses of lhash use their own hashing
> > functions, and are levitte> usually very short still (definitely less
> > than 16 bytes). levitte>
> > levitte> My conclusion is that performance-wise, siphash doesn't give us
> > any levitte> advantage over OpenSSL_LH_strhash for our uses.
> > levitte>
> > levitte> Cheers,
> > levitte> Richard
> > levitte>
> > levitte> (*) Strictly speaking, it's a modified version that takes a
> > length and levitte> tolerates all 8-bit bytes, including 0x00.
> > levitte>
> > levitte> --
> > levitte> Richard Levitte         [hidden email]
> > levitte> OpenSSL Project         http://www.openssl.org/~levitte/
> > levitte> --
> > levitte> openssl-dev mailing list
> > levitte> To unsubscribe:
> > https://mta.openssl.org/mailman/listinfo/openssl-dev levitte>

--
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Benjamin Kaduk
In reply to this post by Richard Levitte - VMS Whacker-2
On 01/11/2017 08:43 AM, Richard Levitte wrote:
A note: I have absolutely nothing against the addition of SIPhash in
our collection of hash algos.  My scepticism was only in regards to
using it as a string hasher for our hash tables indexes.


Understood.  Can you further clarify whether you would like to maintain the existing 20-year-old hand-rolled hash function for that purpose or are open to using a more modern hash (not necessarily SIPhash; there are also things like the Jenkins hash to consider)?

-Ben

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Richard Levitte - VMS Whacker-2
In message <[hidden email]> on Thu, 12 Jan 2017 14:07:54 -0600, Benjamin Kaduk <[hidden email]> said:

bkaduk> On 01/11/2017 08:43 AM, Richard Levitte wrote:
bkaduk>
bkaduk>     A note: I have absolutely nothing against the addition of SIPhash in
bkaduk>     our collection of hash algos.  My scepticism was only in regards to
bkaduk>     using it as a string hasher for our hash tables indexes.
bkaduk>
bkaduk> Understood. Can you further clarify whether you would like to maintain
bkaduk> the existing 20-year-old hand-rolled hash function for that purpose or
bkaduk> are open to using a more modern hash (not necessarily SIPhash; there
bkaduk> are also things like the Jenkins hash to consider)?

If it makes sense, yes.  I found SMhasher (*) and started playing with
it for this very purpose.  Just for kicks, I added OPENSSL_LH_strhash_ex
to it and am currently doing a huge run of all hashes it knows.

I did a test with Google's FarmHash, and that one shows promise, speed
wise (it performs twice as fast as OPENSSL_LH_strhash_ex).

Cheers,
Richard

(*) https://github.com/rurban/smhasher

--
Richard Levitte         [hidden email]
OpenSSL Project         http://www.openssl.org/~levitte/
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Benjamin Kaduk
On 01/12/2017 02:19 PM, Richard Levitte wrote:
In message [hidden email] on Thu, 12 Jan 2017 14:07:54 -0600, Benjamin Kaduk [hidden email] said:

bkaduk> On 01/11/2017 08:43 AM, Richard Levitte wrote:
bkaduk> 
bkaduk>     A note: I have absolutely nothing against the addition of SIPhash in
bkaduk>     our collection of hash algos.  My scepticism was only in regards to
bkaduk>     using it as a string hasher for our hash tables indexes.
bkaduk> 
bkaduk> Understood. Can you further clarify whether you would like to maintain
bkaduk> the existing 20-year-old hand-rolled hash function for that purpose or
bkaduk> are open to using a more modern hash (not necessarily SIPhash; there
bkaduk> are also things like the Jenkins hash to consider)?

If it makes sense, yes.  I found SMhasher (*) and started playing with
it for this very purpose.  Just for kicks, I added OPENSSL_LH_strhash_ex
to it and am currently doing a huge run of all hashes it knows.

I did a test with Google's FarmHash, and that one shows promise, speed
wise (it performs twice as fast as OPENSSL_LH_strhash_ex).


Cool!  I look forward to seeing the results :)

-Ben

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Salz, Rich
In reply to this post by Benjamin Kaduk
> Understood.  Can you further clarify whether you would like to maintain the existing 20-year-old hand-rolled hash function for that purpose or are open to using a more modern hash (not necessarily SIPhash; there are also things like the Jenkins hash to consider)?

Because it works, because nobody has looked at our touched that code, because there are no security concerns and it's unclear if the speed gain(s) make a difference.
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Andy Polyakov-2
In reply to this post by Richard Levitte - VMS Whacker-2
> A run on my laptop gave these results:
>
>     : ; ./util/shlib_wrap.sh apps/openssl speed siphash lhash
>     type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
>     lhash           147387.67k   147940.82k   144937.73k   147177.81k   147095.55k   147679.91k
>     siphash         119939.99k   223694.38k   283383.30k   305372.84k   311760.21k   312120.66k
>
> So it seems that for short strings, OPENSSL_LH_strhash (*) wins some,
> while siphash wins big for larger strings.

This is just *one* data point. Most notably what about 32-bit systems?
Another factor is code size, or rather time it takes to bring it into
cache, as well as what does it invalidate. Conventional benchmarks don't
tell you that, but it's only sensible to consider code size in
comparison to "typical" input size.

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
12