SHA3 is very slow - Externals

8 years ago by Yasuo Ohgaki — view source

unread

Hi all,

I noticed that our SHA-3 is inefficient.

=== Ruby SHA3-256 ===
[yohgaki@dev ~]$ cat t2.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i do
Digest::SHA3.hexdigest("abcdedf", 256)
$i -= 1
end

[yohgaki@dev ~]$ time ruby t2.rb

real 0m0.438s
user 0m0.216s
sys 0m0.222s
[yohgaki@dev ~]$ time ruby t2.rb

real 0m0.429s
user 0m0.228s
sys 0m0.202s
[yohgaki@dev ~]$

=== Ruby SHA2-256 ===
[yohgaki@dev ~]$ cat t.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i do
Digest::SHA2.hexdigest("abcdedf", 256)
$i -= 1
end

[yohgaki@dev ~]$ time ruby t.rb

real 0m0.431s
user 0m0.228s
sys 0m0.205s
[yohgaki@dev ~]$ time ruby t.rb

real 0m0.409s
user 0m0.208s
sys 0m0.203s

=== PHP master SHA3-256 ===
[yohgaki@dev PHP-master]$ time ./php-bin -r '$s = microtime(true); for ($i
= 0; $i < 1000000; $i++) { hash("sha3-256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(2.7503371238708)

real 0m2.764s
user 0m2.755s
sys 0m0.005s
[yohgaki@dev PHP-master]$ time ./php-bin -r '$s = microtime(true); for ($i
= 0; $i < 1000000; $i++) { hash("sha3-256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(2.8106999397278)

real 0m2.831s
user 0m2.823s
sys 0m0.003s

=== PHP master SHA2-256 ===
[yohgaki@dev PHP-master]$ time ./php-bin -r '$s = microtime(true); for ($i
= 0; $i < 1000000; $i++) { hash("sha256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(0.48856687545776)

real 0m0.502s
user 0m0.499s
sys 0m0.002s
[yohgaki@dev PHP-master]$ time ./php-bin -r '$s = microtime(true); for ($i
= 0; $i < 1000000; $i++) { hash("sha256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(0.48898410797119)

real 0m0.505s
user 0m0.499s
sys 0m0.005s

As you can see, PHP's SHA3 is about 6 times slower.
According to DJB's benchmark, it seems SHA-3 could be as fast as SHA-2.
https://bench.cr.yp.to/results-sha3.html

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

8 years ago by Sara Golemon — view source

unread

I noticed that our SHA-3 is inefficient.

Entirely possible. Feel free to improve it. :D

8 years ago by Yasuo Ohgaki — view source

unread

Hi Sara,

I noticed that our SHA-3 is inefficient.

Entirely possible. Feel free to improve it. :D

I would like to, but it wouldn't happen in short time.
I also would like to have SHAKE algorithm.
Perhaps, hash_shake($also, $msg, $len [, $binary=false])?
Anyone, please improve it :D

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

8 years ago by Christian Schneider — view source

unread

Am 01.04.2017 um 05:12 schrieb Yasuo Ohgaki yohgaki@ohgaki.net:

I noticed that our SHA-3 is inefficient.

=== Ruby SHA3-256 ===
[yohgaki@dev ~]$ cat t2.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i do
Digest::SHA3.hexdigest("abcdedf", 256)
$i -= 1
end

Two things I noticed:

As far as I understand Ruby (and as far as I tested it) this does not execute the function at all. You probably mean something like
while $i > 0 do
For some reason the Ruby implementation yields different results, I didn't track down why.
- hash("sha3-256", "abc"); => 3a985da74fe225b2045c172d6bd390bd855f086e3e9d525b46bfe24511431532
which matches the test vector at http://www.di-mgt.com.au/sha_testvectors.html
- Digest::SHA3.hexdigest("abc", 256) => 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45

For whatever reason this is, it means that you can't really compare those two functions.

Regards,

Chris

8 years ago by lauri.kentta@gmail.com — view source

unread

Am 01.04.2017 um 05:12 schrieb Yasuo Ohgaki yohgaki@ohgaki.net:

I noticed that our SHA-3 is inefficient.

=== Ruby SHA3-256 ===
[yohgaki@dev ~]$ cat t2.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i do
Digest::SHA3.hexdigest("abcdedf", 256)
$i -= 1
end

Two things I noticed:

As far as I understand Ruby (and as far as I tested it) this does
not execute the function at all.

Why am I not surprised...

For some reason the Ruby implementation yields different results, I
didn't track down why.

Here's another library, which actually works.
https://rubygems.org/gems/sha3

Tests with that one:

time ruby -e 'require "sha3"; 123456.times {
SHA3::Digest::SHA256.hexdigest("abc") }'
user 0m1.597s
sys 0m0.023s

time php -r 'for ($i = 0; $i < 123456; ++$i) hash("sha3-256", "abc");'
user 0m2.497s
sys 0m0.020s

There's a small difference, but I wonder if anybody (except Yasuo)
actually cares?

--
Lauri Kenttä

8 years ago by Yasuo Ohgaki — view source

unread

Hi Christian,

On Mon, Apr 3, 2017 at 8:44 PM, Christian Schneider cschneid@cschneid.com
wrote:

Two things I noticed:

As far as I understand Ruby (and as far as I tested it) this does not
execute the function at all. You probably mean something like
while $i > 0 do

Oops, forgot to add "== 0"

[yohgaki@dev ~]$ cat t.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i == 0 do
Digest::SHA2.hexdigest("abcdedf", 256)
$i -= 1
end

[yohgaki@dev ~]$ time ruby t.rb

real 0m1.790s
user 0m1.596s
sys 0m0.194s
[yohgaki@dev ~]$ cat t2.rb
#!/usr/bin/env ruby

require 'digest/sha2'

$i = 1000000
until $i == 0 do
Digest::SHA3.hexdigest("abcdedf", 256)
$i -= 1
end

[yohgaki@dev ~]$ time ruby t2.rb

real 0m2.594s
user 0m2.429s
sys 0m0.165s

PHP's sha3 seems slower than it could be.
I knew DJB benchmark before the tests, so I was sloppy.

For some reason the Ruby implementation yields different results, I
didn't track down why.
- hash("sha3-256", "abc"); => 3a985da74fe225b2045c172d6bd390
bd855f086e3e9d525b46bfe24511431532
which matches the test vector at http://www.di-mgt.com.au/sha_t
estvectors.html
- Digest::SHA3.hexdigest("abc", 256) =>
4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45

For whatever reason this is, it means that you can't really compare those
two functions.

Nice finding.
https://github.com/phusion/digest-sha3-ruby
seems a little old. It may not implement final version.
Whichever is wrong, we may be better look into this.

Anyway, it seems someone is better to try to improve SHA3 performance.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

8 years ago by Christian Schneider — view source

unread

Am 05.04.2017 um 04:31 schrieb Yasuo Ohgaki yohgaki@ohgaki.net:

PHP's sha3 seems slower than it could be.

I created a pull request at https://github.com/php/php-src/pull/2453 for a version using the KeccakCodePackage version from https://github.com/gvanas/KeccakCodePackage which yields ~30 times faster results for a simple test.

I don't know whether the PHP maintainers prefer to keep the (very short) inline reference implementation which is slow or whether the optimised version from KeccakCodePackage with around a dozen files would be acceptable.

I put the (part which is used from the) KeccakCodePackage code (without modifications!) in a separate directory under ext/hash/sha3 and I also implemented switching between a 64bit and a 32bit version. Don't know if this is necessary and following all the guidelines.

Oh, I also only superficially scanned
https://github.com/gvanas/KeccakCodePackage#under-which-license-is-the-kcp-distributed
but it looked like it should be ok. Not an expert on this though ;-)

Regards,

Chris

8 years ago by Sara Golemon — view source

unread

On a similarly superficial scan, I have no issues with this.

The only tiny thing which gives me pause is
https://github.com/php/php-src/pull/2453/files#diff-0bb62bbdac4073ae183a857299826533R24
as I don't recall 100% if that redefinition will leak out to other
parts of the runtime (my instinct says it will, so that might need to
live in a different spot).

As long as the unit tests continue to pass (I assume they do) and the
licensing on the bundled library is favorable (it seems to be), it's
just one fast implementation in exchange for a slow one.

-Sara

On Wed, Apr 5, 2017 at 10:45 AM, Christian Schneider
cschneid@cschneid.com wrote:

Am 05.04.2017 um 04:31 schrieb Yasuo Ohgaki yohgaki@ohgaki.net:

PHP's sha3 seems slower than it could be.

I created a pull request at https://github.com/php/php-src/pull/2453 for a version using the KeccakCodePackage version from https://github.com/gvanas/KeccakCodePackage which yields ~30 times faster results for a simple test.

I don't know whether the PHP maintainers prefer to keep the (very short) inline reference implementation which is slow or whether the optimised version from KeccakCodePackage with around a dozen files would be acceptable.

I put the (part which is used from the) KeccakCodePackage code (without modifications!) in a separate directory under ext/hash/sha3 and I also implemented switching between a 64bit and a 32bit version. Don't know if this is necessary and following all the guidelines.

Oh, I also only superficially scanned
https://github.com/gvanas/KeccakCodePackage#under-which-license-is-the-kcp-distributed
but it looked like it should be ok. Not an expert on this though ;-)

Regards,

Chris

8 years ago by Yasuo Ohgaki — view source

unread

Hi Christian,

On Thu, Apr 6, 2017 at 12:45 AM, Christian Schneider cschneid@cschneid.com
wrote:

I created a pull request at https://github.com/php/php-src/pull/2453 for
a version using the KeccakCodePackage version from
https://github.com/gvanas/KeccakCodePackage which yields ~30 times faster
results for a simple test.

Nice work!!
SHA3 is now faster than SHA2.

==== Small String ====
[yohgaki@dev php-src]$ time ./php-bin -r '$s = microtime(true); for ($i =
0; $i < 1000000; $i++) { hash("sha256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(0.46163821220398)

real 0m0.557s
user 0m0.471s
sys 0m0.086s
[yohgaki@dev php-src]$ time ./php-bin -r '$s = microtime(true); for ($i =
0; $i < 1000000; $i++) { hash("sha3-256", "abcdefg"); }
var_dump(microtime(true) - $s); '
float(0.57230806350708)

real 0m0.585s
user 0m0.579s
sys 0m0.006s

==== Large String ====
[yohgaki@dev php-src]$ time ./php-bin -r '$s = microtime(true);$v =
str_repeat("a", 9999999); for ($i = 0; $i < 100; $i++) { hash("sha256",
$v); } var_dump(microtime(true) - $s); '
float(4.6689560413361)

real 0m4.691s
user 0m4.675s
sys 0m0.009s
[yohgaki@dev php-src]$ time ./php-bin -r '$s = microtime(true);$v =
str_repeat("a", 9999999); for ($i = 0; $i < 100; $i++) { hash("sha3-256",
$v); } var_dump(microtime(true) - $s); '
float(2.9090809822083)

real 0m2.928s
user 0m2.919s
sys 0m0.005s

I don't know whether the PHP maintainers prefer to keep the (very short)
inline reference implementation which is slow or whether the optimised
version from KeccakCodePackage with around a dozen files would be
acceptable.

I put the (part which is used from the) KeccakCodePackage code (without
modifications!) in a separate directory under ext/hash/sha3 and I also
implemented switching between a 64bit and a 32bit version. Don't know if
this is necessary and following all the guidelines.

Oh, I also only superficially scanned
https://github.com/gvanas/KeccakCodePackage#under-which-
license-is-the-kcp-distributed
but it looked like it should be ok. Not an expert on this though ;-)

It's fine for me.

I'll wait few weeks for more comments.
If not, I'll merge your PR to master.
I don't think we really need to merge it to released version.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net