use SIPhash for OPENSSL_LH_strhash?

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

use SIPhash for OPENSSL_LH_strhash?

Salz, Rich

Should we move to using SIPHash for the default string hashing function in OpenSSL?  It’s now in the kernel https://lkml.org/lkml/2017/1/9/619

Overview at https://131002.net/siphash/

 

 

-- 

Senior Architect, Akamai Technologies

Member, OpenSSL Dev Team

IM: [hidden email] Twitter: RichSalz

 


--
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/09/2017 10:05 PM, Salz, Rich wrote:

Should we move to using SIPHash for the default string hashing function in OpenSSL?  It’s now in the kernel https://lkml.org/lkml/2017/1/9/619

Overview at https://131002.net/siphash/



Instead of this?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/*-
    unsigned char b[16];
    MD5(c,strlen(c),b);
    return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
*/

    n = 0x100;
    while (*c) {
        v = n | (*c);
        n += 0x100;
        r = (int)((v >> 2) ^ v) & 0x0f;
        ret = (ret << r) | (ret >> (32 - r));
        ret &= 0xFFFFFFFFL;
        ret ^= v * v;
        c++;
    }
    return ((ret >> 16) ^ ret);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Heck, yes!

-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


Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017 18:48:32 CET)

>On 01/09/2017 10:05 PM, Salz, Rich wrote:
>>
>> Should we move to using SIPHash for the default string hashing
>> function in OpenSSL?  It’s now in the kernel
>> https://lkml.org/lkml/2017/1/9/619
>>
><https://urldefense.proofpoint.com/v2/url?u=https-3A__lkml.org_lkml_2017_1_9_619&d=DwMFAg&c=96ZbZZcaMF4w0F4jpN6LZg&r=sssDLkeEEBWNIXmTsdpw8TZ3tAJx-Job4p1unc7rOhM&m=pP5nqGH-O2jy9bgGMmoCbXCc1O46ngqbhe5RSSkFBe8&s=pUULb5vMnjiMFb0kcqwJSHvwKh1G0vQZXwDDYnXNCA8&e=>
>>
>> Overview at https://131002.net/siphash/
>>
><https://urldefense.proofpoint.com/v2/url?u=https-3A__131002.net_siphash_&d=DwMFAg&c=96ZbZZcaMF4w0F4jpN6LZg&r=sssDLkeEEBWNIXmTsdpw8TZ3tAJx-Job4p1unc7rOhM&m=pP5nqGH-O2jy9bgGMmoCbXCc1O46ngqbhe5RSSkFBe8&s=7y76cbQkDMaUqyjBZmNMndmATnk9tUPu8I8JxeD1bKE&e=>
>>
>>
>
>Instead of this?
>
>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>/*-
>    unsigned char b[16];
>    MD5(c,strlen(c),b);
>    return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
>*/
>
>    n = 0x100;
>    while (*c) {
>        v = n | (*c);
>        n += 0x100;
>        r = (int)((v >> 2) ^ v) & 0x0f;
>        ret = (ret << r) | (ret >> (32 - r));
>        ret &= 0xFFFFFFFFL;
>        ret ^= v * v;
>        c++;
>    }
>    return ((ret >> 16) ^ ret);
>
>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>Heck, yes!
>
>-Ben

I fail to see what that would give us. OPENSSL_LH_strhash() is used to get a reasonable index for LHASH entries. Also SIPhash gives at least 64 bits results, do we really expect to see large enough hash tables to warrant that?

Cheers
Richard
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.
--
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/10/2017 12:31 PM, Richard Levitte wrote:

Benjamin Kaduk [hidden email] skrev: (10 januari 2017 18:48:32 CET)
On 01/09/2017 10:05 PM, Salz, Rich wrote:
Should we move to using SIPHash for the default string hashing
function in OpenSSL?  It’s now in the kernel
https://lkml.org/lkml/2017/1/9/619

Heck, yes!
-Ben
I fail to see what that would give us. OPENSSL_LH_strhash() is used to get a reasonable index for LHASH entries. Also SIPhash gives at least 64 bits results, do we really expect to see large enough hash tables to warrant that? 


We don't need to use the full output width of a good hash function.

My main point is, "why would we want to ignore the last 20 years of advancement in hash function research?"  Section 7 of the siphash paper (https://131002.net/siphash/siphash.pdf) explicitly talks about using it for hash tables, including using hash table indices H(m) mod l.

-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?

Blumenthal, Uri - 0553 - MITLL

We don’t need the full output width of a good hash function, but for _this_ purpose (as far as I understand) we don’t need the strength of a good hash function either – and we surely don’t need the unnecessary performance hit of a good hash where we don’t need a good hash.

 

Or am I missing something?

— 

Regards,

Uri

 

 

On 1/10/17, 2:19 PM, "openssl-dev on behalf of Benjamin Kaduk" <[hidden email] on behalf of [hidden email]> wrote:

 

On 01/10/2017 12:31 PM, Richard Levitte wrote:

 
Benjamin Kaduk [hidden email] skrev: (10 januari 2017 18:48:32 CET)
On 01/09/2017 10:05 PM, Salz, Rich wrote:
Should we move to using SIPHash for the default string hashing
function in OpenSSL?  It’s now in the kernel
https://lkml.org/lkml/2017/1/9/619
 

Heck, yes!

-Ben
I fail to see what that would give us. OPENSSL_LH_strhash() is used to get a reasonable index for LHASH entries. Also SIPhash gives at least 64 bits results, do we really expect to see large enough hash tables to warrant that? 
 


We don't need to use the full output width of a good hash function.


My main point is, "why would we want to ignore the last 20 years of advancement in hash function research?"  Section 7 of the siphash paper (https://131002.net/siphash/siphash.pdf) explicitly talks about using it for hash tables, including using hash table indices H(m) mod l.

-Ben


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

smime.p7s (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Richard Levitte - VMS Whacker-2
In reply to this post by Benjamin Kaduk


Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017 20:19:21 CET)

>On 01/10/2017 12:31 PM, Richard Levitte wrote:
>>
>> Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017 18:48:32
>CET)
>>> On 01/09/2017 10:05 PM, Salz, Rich wrote:
>>>> Should we move to using SIPHash for the default string hashing
>>>> function in OpenSSL?  It’s now in the kernel
>>>> https://lkml.org/lkml/2017/1/9/619
>>>>
>>> Heck, yes!
>>> -Ben
>> I fail to see what that would give us. OPENSSL_LH_strhash() is used
>to get a reasonable index for LHASH entries. Also SIPhash gives at
>least 64 bits results, do we really expect to see large enough hash
>tables to warrant that?
>>
>
>We don't need to use the full output width of a good hash function.
>
>My main point is, "why would we want to ignore the last 20 years of
>advancement in hash function research?"  Section 7 of the siphash paper
>(https://131002.net/siphash/siphash.pdf) explicitly talks about using
>it
>for hash tables, including using hash table indices H(m) mod l.

I agree with the advice when one can expect huge tables. The tables we handle are pretty small (I think, please correct me if I'm wrong) and would in all likelihood not benefit very much if at all from SIPhash's relative safety.

Of course, one can ask the question if someone uses LHASH as a general purpose hash table implementation rather than just for the stuff OpenSSL. Frankly, I would probably look at a dedicated hash table library first...

Cheers
Richard
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.
--
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?

Short, Todd
I think I might have an init/update/final version of siphash24 lying around somewhere that would be compatible with OpenSSL’s EVP_PKEY mechanism (similar to Poly1305, in that it needs a key).
--
-Todd Short
// "One if by land, two if by sea, three if by the Internet."

On Jan 10, 2017, at 4:55 PM, Richard Levitte <[hidden email]> wrote:



Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017 20:19:21 CET)
On 01/10/2017 12:31 PM, Richard Levitte wrote:

Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017 18:48:32
CET)
On 01/09/2017 10:05 PM, Salz, Rich wrote:
Should we move to using SIPHash for the default string hashing
function in OpenSSL?  It’s now in the kernel
https://lkml.org/lkml/2017/1/9/619

Heck, yes!
-Ben
I fail to see what that would give us. OPENSSL_LH_strhash() is used
to get a reasonable index for LHASH entries. Also SIPhash gives at
least 64 bits results, do we really expect to see large enough hash
tables to warrant that? 


We don't need to use the full output width of a good hash function.

My main point is, "why would we want to ignore the last 20 years of
advancement in hash function research?"  Section 7 of the siphash paper
(https://131002.net/siphash/siphash.pdf) explicitly talks about using
it
for hash tables, including using hash table indices H(m) mod l.

I agree with the advice when one can expect huge tables. The tables we handle are pretty small (I think, please correct me if I'm wrong) and would in all likelihood not benefit very much if at all from SIPhash's relative safety. 

Of course, one can ask the question if someone uses LHASH as a general purpose hash table implementation rather than just for the stuff OpenSSL. Frankly, I would probably look at a dedicated hash table library first... 

Cheers 
Richard 
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.
-- 
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: use SIPhash for OPENSSL_LH_strhash?

Peter Waltenberg
Reality check

Others have pointed this out but I don't think it's making it through. LHash doesn't need a cryptographic hash and it doesn't have security implications. It certainly doesn't need a keyed hash.

LHash does need to be something that's good at distinguishing short text strings, that's not necessarilly the same thing as a good cryptographic hash, and possibly it's exactly the opposite thing due to the limitted incoming symbol space (ascii text).
About the only thing LHash needs is high performance in it's use area. I'd suspect that switching MD5 to SHA-1 in the existing algorithm would get you that simply because SHA-1 is asm optimized on most platforms now and MD5 typically isn't.
I'd suggest that anyone wishing to change this should at least have to demonstrate improved performance in the OpenSSL use case before it's accepted.

Peter



From:        "Short, Todd" <[hidden email]>
To:        "[hidden email]" <[hidden email]>
Date:        11/01/2017 08:42
Subject:        Re: [openssl-dev] use SIPhash for OPENSSL_LH_strhash?
Sent by:        "openssl-dev" <[hidden email]>




I think I might have an init/update/final version of siphash24 lying around somewhere that would be compatible with OpenSSL’s EVP_PKEY mechanism (similar to Poly1305, in that it needs a key).
--
-Todd Short
// tshort@...
// "One if by land, two if by sea, three if by the Internet."

On Jan 10, 2017, at 4:55 PM, Richard Levitte <levitte@...> wrote:



Benjamin Kaduk <
bkaduk@...> skrev: (10 januari 2017 20:19:21 CET)
On 01/10/2017 12:31 PM, Richard Levitte wrote:

Benjamin Kaduk <
bkaduk@...> skrev: (10 januari 2017 18:48:32
CET)
On 01/09/2017 10:05 PM, Salz, Rich wrote:
Should we move to using SIPHash for the default string hashing
function in OpenSSL?  It’s now in the kernel

https://lkml.org/lkml/2017/1/9/619

Heck, yes!
-Ben

I fail to see what that would give us. OPENSSL_LH_strhash() is used
to get a reasonable index for LHASH entries. Also SIPhash gives at
least 64 bits results, do we really expect to see large enough hash
tables to warrant that?



We don't need to use the full output width of a good hash function.

My main point is, "why would we want to ignore the last 20 years of
advancement in hash function research?"  Section 7 of the siphash paper
(
https://131002.net/siphash/siphash.pdf) explicitly talks about using
it
for hash tables, including using hash table indices H(m) mod l.


I agree with the advice when one can expect huge tables. The tables we handle are pretty small (I think, please correct me if I'm wrong) and would in all likelihood not benefit very much if at all from SIPhash's relative safety.


Of course, one can ask the question if someone uses LHASH as a general purpose hash table implementation rather than just for the stuff OpenSSL. Frankly, I would probably look at a dedicated hash table library first...


Cheers
Richard
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.
--
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




--
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
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.
--
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?

Tomas Mraz-2
On Wed, 2017-01-11 at 03:13 +0000, Salz, Rich wrote:
> 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.

+1

Is there really no use of LHASH tables in OpenSSL where an attacker
attempting a DoS attack can control the contents of the tables? If you
are reasonably sure that there is no such occurrence or that the number
of entries attacker can insert into such table is severally limited by
other means then perhaps it really makes no sense to replace the
existing algorithm. But we need to know this first.

--
Tomas Mraz
No matter how far down the wrong road you've gone, turn back.
                                              Turkish proverb
(You'll never know whether the road is wrong though.)

--
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?

Michel
In reply to this post by Salz, Rich
Reply | Threaded
Open this post in threaded view
|

Re: use SIPhash for OPENSSL_LH_strhash?

Richard Levitte - VMS Whacker-2
In message <001901d26bed$d3746ed0$7a5d4c70$@[hidden email]> on Wed, 11 Jan 2017 10:33:53 +0100, "Michel" <[hidden email]> said:

michel.sales> And what about using FNV or CityHash ?
michel.sales>
michel.sales> https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

I'm a little worried about the zero hash value issue mentioned here:

https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#Non-cryptographic_hash

michel.sales> https://en.wikipedia.org/wiki/CityHash

Google has replaced that with FarmHash according to that page...

--
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?

Richard Levitte - VMS Whacker-2
In reply to this post by Salz, Rich
In message <[hidden email]> on Wed, 11 Jan 2017 03:13:39 +0000, "Salz, Rich" <[hidden email]> said:

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

Done, using the reference siphash implementation.

https://github.com/levitte/openssl/tree/test-string-hashes

A run on my laptop gave these results:

    : ; ./util/shlib_wrap.sh apps/openssl speed siphash lhash
    Doing lhash for 3s on 16 size blocks: 27635188 lhash's in 3.00s
    Doing lhash for 3s on 64 size blocks: 6934726 lhash's in 3.00s
    Doing lhash for 3s on 256 size blocks: 1698489 lhash's in 3.00s
    Doing lhash for 3s on 1024 size blocks: 431185 lhash's in 3.00s
    Doing lhash for 3s on 8192 size blocks: 53868 lhash's in 3.00s
    Doing lhash for 3s on 16384 size blocks: 27041 lhash's in 3.00s
    Doing siphash for 3s on 16 size blocks: 22488748 siphash's in 3.00s
    Doing siphash for 3s on 64 size blocks: 10485674 siphash's in 3.00s
    Doing siphash for 3s on 256 size blocks: 3320898 siphash's in 3.00s
    Doing siphash for 3s on 1024 size blocks: 894647 siphash's in 3.00s
    Doing siphash for 3s on 8192 size blocks: 114170 siphash's in 3.00s
    Doing siphash for 3s on 16384 size blocks: 57151 siphash's in 3.00s
    OpenSSL 1.1.1-dev  xx XXX xxxx
    built on: reproducible build, date unspecified
    options:bn(64,64) rc4(16x,int) des(int) aes(partial) idea(int) blowfish(ptr)
    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
    The 'numbers' are in 1000s of bytes per second processed.
    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.

I have no idea how they compare with regard to distribution (which,
considering I ask for the same size output from both, should be the
main factor that affects the sensitivity to hash flooding)...

Our use of OPENSSL_LH_strhash() is with configuration sections and
names, ASN.1 object names and the function names in the openssl app.
All our other uses of lhash use their own hashing functions, and are
usually very short still (definitely less than 16 bytes).

My conclusion is that performance-wise, siphash doesn't give us any
advantage over OpenSSL_LH_strhash for our uses.

Cheers,
Richard

(*) Strictly speaking, it's a modified version that takes a length and
tolerates all 8-bit bytes, including 0x00.

--
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?

Richard Levitte - VMS Whacker-2
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>
--
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 reply to this post by Short, Todd
Can we look forward to a github PR?

In message <[hidden email]> on Tue, 10 Jan 2017 22:42:17 +0000, "Short, Todd" <[hidden email]> said:

tshort> I think I might have an init/update/final version of siphash24 lying
tshort> around somewhere that would be compatible with OpenSSL’s EVP_PKEY
tshort> mechanism (similar to Poly1305, in that it needs a key).
tshort> --
tshort> -Todd Short
tshort> // [hidden email]
tshort> // "One if by land, two if by sea, three if by the Internet."
tshort>
tshort>     On Jan 10, 2017, at 4:55 PM, Richard Levitte <[hidden email]>
tshort>     wrote:
tshort>
tshort>
tshort>
tshort>
tshort>     Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017
tshort>     20:19:21 CET)
tshort>
tshort>     On 01/10/2017 12:31 PM, Richard Levitte wrote:
tshort>
tshort>
tshort>             Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017
tshort>             18:48:32
tshort>
tshort>
tshort>         CET)
tshort>
tshort>                     On 01/09/2017 10:05 PM, Salz, Rich wrote:
tshort>
tshort>                 Should we move to using SIPHash for the default string
tshort>                     hashing
tshort>                     function in OpenSSL? It’s now in the kernel
tshort>                     https://lkml.org/lkml/2017/1/9/619
tshort>
tshort>
tshort>
tshort>                 Heck, yes!
tshort>                 -Ben
tshort>
tshort>
tshort>             I fail to see what that would give us. OPENSSL_LH_strhash
tshort>             () is used
tshort>
tshort>
tshort>         to get a reasonable index for LHASH entries. Also SIPhash
tshort>         gives at
tshort>         least 64 bits results, do we really expect to see large enough
tshort>         hash
tshort>         tables to warrant that?
tshort>
tshort>
tshort>
tshort>
tshort>         We don't need to use the full output width of a good hash
tshort>         function.
tshort>
tshort>         My main point is, "why would we want to ignore the last 20
tshort>         years of
tshort>         advancement in hash function research?" Section 7 of the
tshort>         siphash paper
tshort>         (https://131002.net/siphash/siphash.pdf) explicitly talks
tshort>         about using
tshort>         it
tshort>         for hash tables, including using hash table indices H(m) mod
tshort>         l.
tshort>
tshort>
tshort>     I agree with the advice when one can expect huge tables. The
tshort>     tables we handle are pretty small (I think, please correct me if
tshort>     I'm wrong) and would in all likelihood not benefit very much if at
tshort>     all from SIPhash's relative safety.
tshort>
tshort>     Of course, one can ask the question if someone uses LHASH as a
tshort>     general purpose hash table implementation rather than just for the
tshort>     stuff OpenSSL. Frankly, I would probably look at a dedicated hash
tshort>     table library first...
tshort>
tshort>     Cheers
tshort>     Richard
tshort>     --
tshort>     Sent from my Android device with K-9 Mail. Please excuse my
tshort>     brevity.
tshort>     --
tshort>     openssl-dev mailing list
tshort>     To unsubscribe:
tshort>     https://mta.openssl.org/mailman/listinfo/openssl-dev
tshort>
--
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 Tomas Mraz-2
> Is there really no use of LHASH tables in OpenSSL where an attacker
> attempting a DoS attack can control the contents of the tables?

The only use of LHASH is in SSL_SESSION and X509_NAME, which use their own hashing functions, and are only used after the session and/or certs have been cryptographically verified.

--
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?

Short, Todd
In reply to this post by Richard Levitte - VMS Whacker-2
I’d be doing it in a manner similar to Poly1305, since that’s a fresh memory… it shouldn’t take long.
--
-Todd Short
// "One if by land, two if by sea, three if by the Internet."

On Jan 11, 2017, at 9:44 AM, Richard Levitte <[hidden email]> wrote:

Can we look forward to a github PR?

In message <[hidden email]> on Tue, 10 Jan 2017 22:42:17 +0000, "Short, Todd" <[hidden email]> said:

tshort> I think I might have an init/update/final version of siphash24 lying
tshort> around somewhere that would be compatible with OpenSSL’s EVP_PKEY
tshort> mechanism (similar to Poly1305, in that it needs a key).
tshort> --
tshort> -Todd Short
tshort> // [hidden email]
tshort> // "One if by land, two if by sea, three if by the Internet."
tshort>
tshort>     On Jan 10, 2017, at 4:55 PM, Richard Levitte <[hidden email]>
tshort>     wrote:
tshort>
tshort>
tshort>
tshort>
tshort>     Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017
tshort>     20:19:21 CET)
tshort>
tshort>     On 01/10/2017 12:31 PM, Richard Levitte wrote:
tshort>
tshort>
tshort>             Benjamin Kaduk <[hidden email]> skrev: (10 januari 2017
tshort>             18:48:32
tshort>
tshort>
tshort>         CET)
tshort>
tshort>                     On 01/09/2017 10:05 PM, Salz, Rich wrote:
tshort>
tshort>                 Should we move to using SIPHash for the default string
tshort>                     hashing
tshort>                     function in OpenSSL? It’s now in the kernel
tshort>                     https://lkml.org/lkml/2017/1/9/619
tshort>
tshort>
tshort>
tshort>                 Heck, yes!
tshort>                 -Ben
tshort>
tshort>
tshort>             I fail to see what that would give us. OPENSSL_LH_strhash
tshort>             () is used
tshort>
tshort>
tshort>         to get a reasonable index for LHASH entries. Also SIPhash
tshort>         gives at
tshort>         least 64 bits results, do we really expect to see large enough
tshort>         hash
tshort>         tables to warrant that?
tshort>
tshort>
tshort>
tshort>
tshort>         We don't need to use the full output width of a good hash
tshort>         function.
tshort>
tshort>         My main point is, "why would we want to ignore the last 20
tshort>         years of
tshort>         advancement in hash function research?" Section 7 of the
tshort>         siphash paper
tshort>         (https://131002.net/siphash/siphash.pdf) explicitly talks
tshort>         about using
tshort>         it
tshort>         for hash tables, including using hash table indices H(m) mod
tshort>         l.
tshort>
tshort>
tshort>     I agree with the advice when one can expect huge tables. The
tshort>     tables we handle are pretty small (I think, please correct me if
tshort>     I'm wrong) and would in all likelihood not benefit very much if at
tshort>     all from SIPhash's relative safety.
tshort>
tshort>     Of course, one can ask the question if someone uses LHASH as a
tshort>     general purpose hash table implementation rather than just for the
tshort>     stuff OpenSSL. Frankly, I would probably look at a dedicated hash
tshort>     table library first...
tshort>
tshort>     Cheers
tshort>     Richard
tshort>     --
tshort>     Sent from my Android device with K-9 Mail. Please excuse my
tshort>     brevity.
tshort>     --
tshort>     openssl-dev mailing list
tshort>     To unsubscribe:
tshort>     https://mta.openssl.org/mailman/listinfo/openssl-dev
tshort>
--
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?

Sands, Daniel
In reply to this post by Richard Levitte - VMS Whacker-2
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.  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>

--
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 Salz, Rich
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.
--
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: use SIPhash for OPENSSL_LH_strhash?

J. J. Farrell-2
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
12