Subject: [openpgp] SHA3 algorithm ids.

From: Werner Koch <[email-masked]>
Date: Sat, 08 Aug 2015 11:21:29 +0200

Hi!

Now that an official SHA3 specs has been published I would like to see
algorithm ids assigned.  Although it is some time until we can publish
rfc-4880bis, it would be useful to agree on the algorithm ids now.
This would be helpful for experimental implementations.  Thus what about
this new table with the SHA2 drop in replacements:

      ID           Algorithm                             Text Name
      --           ---------                             ---------
      1          - MD5 [HAC]                             "MD5"
      2          - SHA-1 [FIPS180]                       "SHA1"
      3          - RIPE-MD/160 [HAC]                     "RIPEMD160"
      4          - Reserved
      5          - Reserved
      6          - Reserved
      7          - Reserved
      8          - SHA256 [FIPS180]                      "SHA256"
      9          - SHA384 [FIPS180]                      "SHA384"
      10         - SHA512 [FIPS180]                      "SHA512"
      11         - SHA224 [FIPS180]                      "SHA224"
      12         - SHA3-224 [FIPS202]                    "SHA3-224"
      13         - SHA3-256 [FIPS202]                    "SHA3-256"
      14         - SHA3-384 [FIPS202]                    "SHA3-384"
      15         - SHA3-512 [FIPS202]                    "SHA3-512"
      100 to 110 - Private/Experimental algorithm

Note that I ordered SHA3-224 first; when we did SHA2 we forgot about 224
and thus it ended up out of order.

I am not sure about the text name.  Is a dash okay (cf. armor header)?

The OIDS are:

   The hexadecimal representations for the
   currently defined hash algorithms are as follows:
    
     [...]  

     - SHA3-224:   0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07
     - SHA3-256:   0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x08
     - SHA3-384:   0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x09
     - SHA3-512:   0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0a

   The ASN.1 Object Identifiers (OIDs) are as follows:

     [...]

     - SHA3-224:   2.16.840.1.101.3.4.2.7
     - SHA3-256:   2.16.840.1.101.3.4.2.8
     - SHA3-384:   2.16.840.1.101.3.4.2.9
     - SHA3-512:   2.16.840.1.101.3.4.2.10

   The full hash prefixes for these are as follows:

       [...]

       SHA3-224:   0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07, 0x05,
                   0x00, 0x04, 0x40

       SHA3-256:   0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07, 0x05,
                   0x00, 0x04, 0x40

       SHA3-384:   0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07, 0x05,
                   0x00, 0x04, 0x40

       SHA3-512:   0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
                   0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07, 0x05,
                   0x00, 0x04, 0x40

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Paul Wouters <[email-masked]>
Date: Sat, 8 Aug 2015 14:43:19 +0200

What is the rationale to implement all sha3 variants?

I understand some protocols need lower grade versions for performance reasons but that seems to matter a lot less for openpgp usage. Why not just implement sha3-512?

Sent from my iPhone

> On Aug 8, 2015, at 11:21, Werner Koch <[email-masked]> wrote:
> 
> Hi!
> 
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 8 Aug 2015 09:48:30 -0400

This is an IANA maintained registry so IANA picks the code points while
they are in charge.

But what is sometimes done when there is a working group working on a
protocol with a lot of code points, the registry is moved out of IANA
control and someone in the WG manages it. This is the way PKIX worked.

It is also possible that the way to do this would be for a single document
to propose code points for all the active crypto specs.

---

From: ianG <[email-masked]>
Date: Sat, 08 Aug 2015 23:26:04 +0100

> What is the rationale to implement all sha3 variants?

I agree, I'd like to see a really good rationale.

> I understand some protocols need lower grade versions for performance reasons but that seems to matter a lot less for openpgp usage. Why not just implement sha3-512?

One would be good.  Suits me to go for the longest one.

>>       ID           Algorithm                             Text Name

snip

>>       12         - RESERVED
>>       13         - RESERVED
>>       14         - RESERVED

And while we're at it, can we add DEPRECATED to all the rest except 
SHA(2)512 ?

iang

ps;  And that 100-110 monstrosity - sheesh!  ;-)

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 8 Aug 2015 18:35:25 -0400

On Sat, Aug 8, 2015 at 6:26 PM, ianG <[email-masked]> wrote:

> I understand some protocols need lower grade versions for performance
>> reasons but that seems to matter a lot less for openpgp usage. Why not just
>> implement sha3-512?
>>
>

Discussion in CFRG was definitely pointing to using 512 for the hash
required for the internal bit. So if we choose one it should be 512 and
truncate where necessary in the UI part.

---

From: Werner Koch <[email-masked]>
Date: Sun, 09 Aug 2015 09:50:09 +0200

> What is the rationale to implement all sha3 variants?

Because they are drop-in replacements for the 4 SHA2 algorithms; that is
the whole point of these algorithms.  Assigning algorithm ids does not
mean that they will be used - that is an entire different story.  It is
better to have well defined ids than to resort to experimental
algorithms.  FWIW, I do not plan to support them in write-mode.

Although IANA assigns them, we always agreed prior to any official
assignment on new algorithm ids.

Salam-Shalom,

   Werner

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 10 Aug 2015 02:20:18 +0100

Just on the process crapology...

> control and someone in the WG manages it. This is the way PKIX worked.

That's out of date. We've moved those PKIX registries to IANA and Russ
no longer manages 'em and more importantly here we've put in place a
process for early allocation of IANA code points in RFC 7020. [1]

In terms of code points for use of sha-3 in pgp, my reading of 7120
would be that the list will discuss and the chairs will judge if rough
consensus has been reached at which point the chairs will have the
backing of folks participating in the WG to allocate code points
early.

Cheers,
S.

PS: A nice side-effect of using 7120 - IANA regularly send the IESG a
summary of the early allocations that will soon expire. That's a
great way to kick a WG into finishing a bit of work they ought have
gotten done ages before:-)

[1] https://tools.ietf.org/html/rfc7120

---

From: Derek Atkins <[email-masked]>
Date: Mon, 10 Aug 2015 11:22:31 -0400

> One would be good.  Suits me to go for the longest one.

Possibly two...  But the SHA3 competition has shown that SHA2 is pretty
darn good...

> And while we're at it, can we add DEPRECATED to all the rest except

I see no reason to deprecate SHA2-256.  But I'm fine with all the rest.

> iang

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 10 Aug 2015 16:50:32 -0400

I agree with Derek (I think).

There is a very clear need for 512 bits and there is a case for 256 bits.
It does not seem very likely that the other sizes will get use.

The competition did result in restoring most people's confidence in SHA-2.
It is widely deployed and used today. So I don't see a case for deprecating
any of the SHA-2 bit sizes.

Right now Comodo and various other CAs are using SHA-2-384 in our ECC certs
but that is based on using the NIST curves. It would not surprise me if
people using SHA-2 made the same choice. It is quite clear that the CFRG
ECC signature scheme will use 512 bit and that is the algorithm most likely
to be used with SHA-3.

Given that email recipients tend to end up having to implement all the code
points in a cipher suite because they can't really control what is sent, I
think it is a good plan to be a little parsimonious in selecting key sizes
and avoid choosing key strengths that aren't likely to see use.

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 12:10:45 +0200

> points in a cipher suite because they can't really control what is sent, I

That is not the case with OpenPGP.  If you encrypt and sign the key
gives you a list of hash algorithms supported by the recipient.  Only
those may be used.   In a signature only case there is no point in an using
extravagant hash algorithm because most recipients won't be able to
verify such a signature.

We have a lot of experience in how to deploy new algorithms and we are
very conservative here.  My request for adding SHA3 algo ids does not
mean in any way that I endorse its use or would even suggest that
4880bis should contain a SHOULD or MAY for implementing such an
algorithm.  When we come to the point on deciding on algorithms I would
suggest something like this: 

 - Implementations MUST implement SHA-1.  Implementations MAY implement
 - other algorithms.  MD5 is deprecated.
 + Implementations MUST implement SHA-1 and SHA2-FIXME.  Implementations
 + MUST NOT implement MD5.  Implementations SHOULD NOT implement
 + SHA3-xxxx.  Implementations MAY implement other algorithms.

The algo ids are a different case and I would be fine with the RFC-7120
method.  Iff the unexpected case happens that a severe weakness in SHA2
is found, the pre-allocated SHA3 ids will allow us to quickly switch to
SHA3.  Isn't that the whole point of SHA3 being plugin-in replacements
for SHA2?

I suggest to use a different thread for discussing algorithm selection
because that is a different topic than assigning algorithm ids.

Shalom-Salam,

   Werner

---

From: ianG <[email-masked]>
Date: Tue, 11 Aug 2015 13:29:22 +0100

On 11/08/2015 11:10 am, Werner Koch wrote:
...
> because that is a different topic than assigning algorithm ids.

Hmmm... I understand that.  What I'm not convinced of is that at the 
current time we can sensibly allocate the numbers.

As far as I can see, to sensibly allocate the numbers, we'd want:

   * to choose which SHA3 we're going for.  This not only means 
addressing the additionals (like the 4 lengths) but also resolving the 
uncertainty (perhaps in my mind only) about SHAKES.

   * to build a more comprehensive alg-failure recovery strategy.  By 
this I mean, more than handwaving at SHA3 as a potential drop in; 
making it the actual drop in with a process by which we trigger that 
move and a series of events listed that we anticipate happening;  text 
in the draft that lays that out;  etc.

Otherwise, we're fortune gazing.

(It may sound like I'm engaging in waffly rhetoric again - but there is 
a known discipline for this.  It's called *disaster recovery* and it's a 
required component of many compliance programmes, taught and certified 
in various places.  There are many people who know how to do this stuff, 
it's just that it is a relatively new and/or infrequent delivery in the 
open source crypto world.)

iang

---

From: Paul Wouters <[email-masked]>
Date: Tue, 11 Aug 2015 08:30:42 -0400 (EDT)

> + SHA3-xxxx.  Implementations MAY implement other algorithms.

openpgp is unique in that there is a _very_ long validity time required
for some algorithms, so one could verify a 20 year old message, even if
that security 20 years later is questionable (eg breakable)

I would like to see (and maybe the documents already do that but the
above bullet points don't indicicate this) a difference in support for
verifying signatures (eg we should implement MD5 and MUST implement
SHA1) and creating new signatures (MUST NOT use MD5 or SHA1)

> SHA3.  Isn't that the whole point of SHA3 being plugin-in replacements

Yes, but I don't see why we need to have 6 versions of SHA3 on standbye.
openpgp validity / security is measured in years, and as such,
performance don't really come to play when considering algorithms.

Paul

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 11 Aug 2015 13:21:07 +0000

>There is a very clear need for 512 bits and there is a case for 256 bits.

What's the clear need for -512?  By which I mean a demonstrated practical need
for a hash size of 64 bytes, not a hypothesised need given an imaginary
attack.  I can see a need for SHA-256 (to replace SHA-1), but for something
like SHA3-512 all I can see are downsides (compared to SHA2-256).

Peter.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 11 Aug 2015 10:06:14 -0400

> extravagant hash algorithm because most recipients won't be able to

And what then happens if you use the same key on two different devices
running two different applications?

Advertising crypto capabilities is good. But it isn't a panacea. If people
are going to use end to end encrypted email as default, they have to be
able to read their mail on multiple devices.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 11 Aug 2015 10:16:43 -0400

> like SHA3-512 all I can see are downsides (compared to SHA2-256).

The CFRG replacement for ECDSA will almost certainly use the 512 bit wide
pipe hash internally.

Dan Bernstein put together a Perl script that shows every algorithm and
every option. If you are going to sign a 1Gb file then you are going to
need multiple trips through the digest function. Now there is of course a
good argument to be made for a faster 256 bit hash for the bulk digest on
that 1Gb file. But you also need one or more digests of fixed bits of data
internally.

So the practical upshot is that if we were to define an absolutely minimal
cryptolib it would almost certainly include the 512 bit digest. The 256 bit
is optional.

Constrained devices still exist. But the constraint on processing speed is
easing up much more quickly than the constraint on code space and working
memory.

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 17:41:12 +0200

> need multiple trips through the digest function. Now there is of course a

This is not an option for OpenPGP!  OpenPGP has been carefully designed
to allow its use in a pipe ("online" in current parlance).  Any signing
function which requires multiple passes over the signed data is useless.
(I heard of encrypted(+signed) backups in the TiB range.)

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 17:47:54 +0200

> like SHA3-512 all I can see are downsides (compared to SHA2-256).

One advantage of SHA-512 (SHA2) is that it faster than SHA-256 on modern
machines.  Thus SHA-512 truncated to 256 might be an option.  This would
eventually allow to write a small application which uses SHA-512 as its
only hash algorithm.

Salam-Shalom,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 18:03:28 +0200

> that security 20 years later is questionable (eg breakable)

I think that it is not yet the time to discuss deprecation of algorithms
or new standard preferences; this can and should be delayed until we
have done the bulk of 4880bis work.

> Yes, but I don't see why we need to have 6 versions of SHA3 on standbye.

Only 4 can be used as direct replacements.  SHAKE would only make sense
if we adjust the used signature algorithms.

> performance don't really come to play when considering algorithms.

Having the ids allocated allows to switch to them without much
discussion.  If you really want, we could also say these numbers are re
severed for SHA3 so that it is clear that they should not be used.  But
that is bascially what RFC-7120 does after a year.

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 18:08:10 +0200

> uncertainty (perhaps in my mind only) about SHAKES.

I don't think so.  Let's assume that 4880bis specifies SHA-256 as the
replacement for SHA throughout the protocol.  Then it would be pretty
clear that SHA3-256 can be used if surprisingly a Chinese researcher
finds weaknesses in SHA2.

> making it the actual drop in with a process by which we trigger that

We already have this.  The preference systems greatly helped with the
migration from SHA-1 to SHA-256 et al.

Salam-Shalom,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 11 Aug 2015 12:14:11 -0400

> like SHA3-512 all I can see are downsides (compared to SHA2-256).

Is your concern CPU time or bandwidth (network/storage) or something
else?

If it's CPU time: on some architectures SHA-512 implementations are
faster than SHA-256 implementations (except for digests of very short
messages):

0 dkg@alice:~$ openssl speed sha512 sha256
Doing sha256 for 3s on 16 size blocks: 9475191 sha256's in 3.00s
Doing sha256 for 3s on 64 size blocks: 5366754 sha256's in 3.00s
Doing sha256 for 3s on 256 size blocks: 2344003 sha256's in 3.00s
Doing sha256 for 3s on 1024 size blocks: 715128 sha256's in 3.00s
Doing sha256 for 3s on 8192 size blocks: 96700 sha256's in 3.00s
Doing sha512 for 3s on 16 size blocks: 7094449 sha512's in 3.00s
Doing sha512 for 3s on 64 size blocks: 7048926 sha512's in 3.00s
Doing sha512 for 3s on 256 size blocks: 2764993 sha512's in 3.00s
Doing sha512 for 3s on 1024 size blocks: 972785 sha512's in 3.00s
Doing sha512 for 3s on 8192 size blocks: 136283 sha512's in 3.00s
OpenSSL 1.0.2d 9 Jul 2015
built on: reproducible build, date unspecified
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx) 
compiler: gcc -I. -I.. -I../include  -fPIC -DOPENSSL_PIC -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -g -O2 -fstack-protector-strong -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-z,relro -Wa,--noexecstack -Wall -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM -DECP_NISTZ256_ASM
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
sha256           50534.35k   114490.75k   200021.59k   244097.02k   264055.47k
sha512           37837.06k   150377.09k   235946.07k   332043.95k   372143.45k
0 dkg@alice:~$ 

extra speed is hardly a downside. :)

   --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 11 Aug 2015 12:22:57 -0400

On Tue 2015-08-11 10:16:43 -0400, Phillip Hallam-Baker wrote:
> every option.

for those who haven't followed that process, djb's python script is
here:

   http://ed25519.cr.yp.to/cfrg/signatures.py

> If you are going to sign a 1Gb file then you are going to need
> multiple trips through the digest function. Now there is of course a
> good argument to be made for a faster 256 bit hash for the bulk digest
> on that 1Gb file.

(except when the 512-bit hash is faster for the bulk digest, see my
earlier post in this thread)

> easing up much more quickly than the constraint on code space and working

The other constraints to consider are network bandwidth and permanent
storage.  But compared to the move from strong RSA to (any reasonable
form of) ECC (e.g. the variable part of keys/signatures/PKESKs going
from 2048 bits or more to 521 bits or less), the difference between a
256-bit hash and a 512-bit hash seems nearly lost in the noise.

   --dkg

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 11 Aug 2015 16:39:21 +0000

Daniel Kahn Gillmor <[email-masked]> writes:

>Is your concern CPU time or bandwidth (network/storage) or something else?

Yes.

>If it's CPU time: on some architectures SHA-512 implementations are faster
>than SHA-256 implementations (except for digests of very short messages):

A huge number of devices, and in particular ones with less CPU power, are
still 32-bit, and will remain so for a long time, probably more or less
indefinitely.

In addition from the original post it was unclear whether -512 referred to
SHA2 or SHA3 (which is why I qualified my reply as SHA2-256 and SHA3-512),
SHA3 will be ever worse than SHA2-512 in speed terms.

In terms of network/storage, there's the unnecessary use of 64-byte hashes
that I've already mentioned.  For TLS and SSH you really don't need more than
maybe 64 bits (not bytes), and certainly 64 bytes is nothing more than a
pointless waste of space when you're sending lots of small data quantities
back and forth.

Peter.

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 19:29:39 +0200

> still 32-bit, and will remain so for a long time, probably more or less

Does anyone know a summary of SHA-256 performance on standard CPUs
with dedicated SHA hardware?  The Padlock engine has this but I don't
know whether other CPUs also provide hardware support.  I assume that on
x86 the AVX instructions are as good as dedicated support:

FWIW, Libgcrypt on an i5-2410M (64 bit) gives this:

                |  nanosecs/byte   mebibytes/sec   cycles/byte
 SHA1           |      1.92 ns/B     496.5 MiB/s      4.42 c/B
 SHA256         |      4.42 ns/B     215.6 MiB/s     10.17 c/B
 SHA512         |      2.97 ns/B     321.1 MiB/s      6.83 c/B

with AVX disabled:

 SHA1           |      2.27 ns/B     419.7 MiB/s      5.23 c/B
 SHA256         |      5.26 ns/B     181.1 MiB/s     12.11 c/B
 SHA512         |      3.61 ns/B     264.0 MiB/s      8.31 c/B

with AVX and SSSE3 disabled:

 SHA1           |      3.27 ns/B     292.0 MiB/s      7.51 c/B
 SHA256         |      7.50 ns/B     127.1 MiB/s     17.26 c/B
 SHA512         |      4.68 ns/B     203.6 MiB/s     10.78 c/B

We have no optimized SHA3 yet; for reference here are the numbers from
the unoptimized version:

 SHA3-256       |      5.70 ns/B     167.3 MiB/s     13.11 c/B
 SHA3-512       |     10.66 ns/B     89.46 MiB/s     24.52 c/B

Salam-Shalom,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 11 Aug 2015 13:45:37 -0400

> FWIW, Libgcrypt on an i5-2410M (64 bit) gives this:

I'm assuming this is done over large inputs KiB or MiB of data into each
hash -- is that right?  can you indicate what commands you ran to
generate these figures?

>                 |  nanosecs/byte   mebibytes/sec   cycles/byte

Thank you for the precise and clear units!  that's (sadly) pretty rare
to see in performance test reports, but it's very helpful.

    --dkg

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 11 Aug 2015 17:48:59 +0000

Werner Koch <[email-masked]> writes:

>Does anyone know a summary of SHA-256 performance on standard CPUs with
>dedicated SHA hardware?

This is focusing on entirely the wrong end of the performance scale,
benchmarking anything on an i7 (or whatever) is pretty much irrelevant because
no matter how you implement it (with hardware assist, software-only, handcoded
asm, C, Visual Basic, whatever), it's still going to be way faster than you
ever need.  The only difference will be whether it's 100x faster than required
or 200x faster.  

Where it matters is IoT implementations, 180MHz STM32's and the like.  For
example on a Cortex A7 (which is way more powerful than most IoT devices use,
but I happen to have figures at hand for it), SHA2-512 is more than an order
of magnitude slower than SHA2-256.  SHA-3 is too new to have figures
available, but I'd guess it's going to be a lot worse than that.  That's what
you need to benchmark for, systems where speed is actually an issue.

Peter.

---

From: "Dang, Quynh" <[email-masked]>
Date: Tue, 11 Aug 2015 17:53:42 +0000

See the Keccak's website: http://keccak.noekeon.org/, under the "Implementation" section.

It stated that "Keccak has overall good software performance. It is faster than SHA-2 on modern PCs and shines when used in a mode exploiting parallelism. On AMD™ Bulldozer™, 128-bit and 256-bit security hashing tops at 4.8 and 5.9 cycles/byte, respectively. On Intel™ Sandy Bridge™, the same functions reach 5.4 and 6.9 cycles/byte."

Quynh. 
________________________________________
From: openpgp <[email-masked]> on behalf of Werner Koch <[email-masked]>
Sent: Tuesday, August 11, 2015 1:29 PM
To: Peter Gutmann
Cc: Phillip Hallam-Baker; Derek Atkins; ianG; Daniel Kahn Gillmor; IETF OpenPGP
Subject: [openpgp] SHA-x performance (was:  SHA3 algorithm ids)

with AVX disabled:

Salam-Shalom,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 22:01:13 +0200

> hash -- is that right?  can you indicate what commands you ran to

The values are taken from mesurements of 64 buffer sizes from 16 to 4112
bytes.  Result should be somewhat similar to SUPERCOP. 

I ran this from current Libgcrypt master:

  tests/bench-slope --cpu-mhz 2300 \
      --disable-hwf intel-avx --disable-hwf intel-ssse3 \
      hash sha1 sha256 sha512 sha3-256 sha3-512

Salam-Shalom,

   Werner

---

From: ianG <[email-masked]>
Date: Tue, 11 Aug 2015 21:08:52 +0100

> finds weaknesses in SHA2.

This assumes that any future breach of SHA2 is of the class that we can 
then drop in a replacement from SHA3 -- without any change.  Eg, a 
prediction that the Chinese researcher attack actually comes true a 
second time.

I find this unlikely.  We're fighting a mythical enemy here, indeed the 
Chinese research attacker hasn't as yet actually count coup [0] on SHA1 
let alone SHA2 :)

I suggest we get back to other things, we're wheel-spinning.  If you 
really want to allocate those numbers, go ahead - I think it is 
pointless but it does no harm to the document, and it's better to move on.

> migration from SHA-1 to SHA-256 et al.

OK, I'd have to review that in the doc.  (But I don't have time, so I'll 
defer.)

iang

[0] old Hollywood term for scalping the enemy in westerns.

---

From: Werner Koch <[email-masked]>
Date: Tue, 11 Aug 2015 22:32:03 +0200

> ever need.  The only difference will be whether it's 100x faster than required

Depends on what you want to do: To feed a big pipe you will need a
reasonable fast CPU anyway because there are other things to do beside
crypto.  Thus it matters for those applications whether you can you
still use a cheaper CPU.

> example on a Cortex A7 (which is way more powerful than most IoT devices use,

Right that is a different class but fortunately we can run our protocols
easily there.  I concur that a MUST algorithm in OpenPGP should work
well on small devices.  This is also the reason why one algorithm
_might_ not fit all devices.

bench.cr.yp.to has a lot data points but AFAICS it start with an A8 and
it any case there is too much data for a useful discussion.  Do you have
a suggestion on what CPUs from low to high end to do benchmarks so to
check which SHA variant is suitable?  Although, I assume that SHA-256
will likely be the best over all CPUs, having some concrete data points
may help to convince other folks.

Shalom-Salam,

   Werner

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 11 Aug 2015 17:20:03 -0400

> (I heard of encrypted(+signed) backups in the TiB range.)

That isn't what I was referring to, the signature mechanisms are using the
digests internally. So the 1Gb file will go through once. But the proof of
correctness for the signature algorithm itself requires internal digest
functions.

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 12 Aug 2015 02:08:33 +0000

Werner Koch <[email-masked]> writes:

>Do you have a suggestion on what CPUs from low to high end to do benchmarks
>so to check which SHA variant is suitable?

It'd be a longish list :-).  I'm also not sure how easy it'll be to get at
them, this is all embedded-systems stuff so you can't just SSH into a box and
run the tests.  In any case the most common is ARM Cortex M (and a few R), so
any Cortex M3 (the example I gave was an STM32 at 180MHz which admittedly is
the top end of the range, 100 or 80 Mhz would be another benchmark level, but
then they're all ARMv7-M so you can extrapolate from one clock speed to
another), then for PowerPC something like an MPC560x at 80 MHz (very common in
industrial and automotive), a PIC32MX (MIPS32) at 60 MHz, and then for exotica
maybe a NIOS II or MicroBlaze at 100 Mhz.  You don't really need to do dozens
of variants since things mostly scale directly with clock speed, and in any
case those are reasonably representative clocks, at least for the faster devices
where power-saving isn't an issue.

Peter.

---

From: Werner Koch <[email-masked]>
Date: Wed, 12 Aug 2015 08:21:46 +0200

> correctness for the signature algorithm itself requires internal digest

I know.  The speed of the hash algorithm is not an issue here, though.

The only issue would be whether the extra code size required for a
different hash algorithm than for what is used as part of the signature
algorithm (SHA-256 for bulk, SHA-512 for EdDSA) is a matter of concern.

Salam-Shalom,

   Werner

---

From: ianG <[email-masked]>
Date: Wed, 12 Aug 2015 14:23:55 +0100

> where power-saving isn't an issue.

To what extent are we accepting the embedded market as "our market" ?

Is this something that already exists in the sense that a lot of them 
are already doing OpenPGP signing for some purpose?  Is the process 
things like signed updates, or are people using OpenPGP to encrypt 
and/or sign requests to the devices?

Or, are we making a stab at the future:  "IoT will need security 
systems, and OpenPGP will be used to supply that, so we'd better make 
sure it fits on the rough template of devices."

To give a ludicrous counter-example, we could also optimise the future 
hash for smartcards.  That's another big market, why not?  I'd say this 
doesn't work mostly because the smartcard or tokens market is mostly 
closed, and systems are typically constructed to be tightly bound to the 
end-user application;  generic systems such as OpenPGP would find it hard.

Where do we draw the line?  Are embedded / IoT inside?

iang

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 12 Aug 2015 10:13:02 -0400

On Wed, Aug 12, 2015 at 9:23 AM, ianG <[email-masked]> wrote:

> Is this something that already exists in the sense that a lot of them are
> already doing OpenPGP signing for some purpose?  Is the process things like
> signed updates, or are people using OpenPGP to encrypt and/or sign requests
> to the devices?
>
> Or, are we making a stab at the future:  "IoT will need security systems,
> and OpenPGP will be used to supply that, so we'd better make sure it fits
> on the rough template of devices."
>

If we are picking algorithm suites then we should look at the cases where
the choice might matter rather than when it does not.

IOT looks set to create a demand for an absolutely minimal cryptographic
suite. One signature algorithm, one exchange algorithm, both on the same
curve, one authenticated encryption mode, one digest/pseudorandom function.

That suite is going to be the one that finds its way into hardware
accelerators and those are in turn the sort of things that are going to be
found as standard cell and on smartcards and such.

So looking at a five year horizon, that is the set that is interesting.

---

From: Derek Atkins <[email-masked]>
Date: Wed, 12 Aug 2015 10:40:52 -0400

> easing up much more quickly than the constraint on code space and working

You'd actually be surprised at how untrue this is.  There are tons of
devices out there still using 8- and 16-bit processors (or no processors
at all!)  What's happening is that these low-end systems are getting
installed into smaller and smaller devices.  So yes, if you look at a
particular device (e.g. cell phone) it's getting more powerful every
year.  However soon our light bulbs will be "smart".

So let's not assume that these low-end processors are going away, please?

-derek

---

From: ianG <[email-masked]>
Date: Wed, 12 Aug 2015 16:11:44 +0100

On 12/08/2015 15:13 pm, Phillip Hallam-Baker wrote:
>
>
> On Wed, Aug 12, 2015 at 9:23 AM, ianG <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>         Werner Koch <[email-masked] <mailto:[email-masked]>> writes:
>
>     Is this something that already exists in the sense that a lot of
>     them are already doing OpenPGP signing for some purpose?  Is the
>     process things like signed updates, or are people using OpenPGP to
>     encrypt and/or sign requests to the devices?
>
>     systems, and OpenPGP will be used to supply that, so we'd better
>     make sure it fits on the rough template of devices."
>
>     To give a ludicrous counter-example, we could also optimise the
>     future hash for smartcards.  That's another big market, why not?
>     I'd say this doesn't work mostly because the smartcard or tokens
>     market is mostly closed, and systems are typically constructed to be
>     tightly bound to the end-user application;  generic systems such as
>     OpenPGP would find it hard.
>
> If we are picking algorithm suites then we should look at the cases
> where the choice might matter rather than when it does not.
>
> accelerators and those are in turn the sort of things that are going to
> be found as standard cell and on smartcards and such.
>

Yes I entirely agree, that interesting discussion exists.  Is that what 
we are doing here, though?

Are we rewriting OpenPGP so we can turn on the lightbulb?

Personally, I see a huge leap here.  OpenPGP isn't suitable/designed at 
all for that application(s) / market(s).

iang

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 12 Aug 2015 11:42:51 -0400

> So let's not assume that these low-end processors are going away, please?

Well the constraint on processing is easing up due to the move from RSA to
ECC. And for the amount of data going though one of these processors, the
choice of AES or DES doesn't make much of a difference. These things don't
have to communicate very fast.

The thing that gets really uncomfortable is dealing with the amount of
memory available. Quite a few of the embedded chips have even less RAM than
the Commodore PET I started with when 32KB was the large machine.

Yes, these chips are not going away any time soon. The number of chips
being made with 6502 based cores has increased every year since the 80s.
But the problem with the chips isn't just that they are slow.

---

From: Bill Frantz <[email-masked]>
Date: Wed, 12 Aug 2015 10:12:12 -0700

On 8/12/15 at 8:11 AM, [email-masked] (ianG) wrote:

>Personally, I see a huge leap here.  OpenPGP isn't 
>suitable/designed at all for that application(s) / market(s).

I see some security needs in this market that, like most 
security needs, are being generally ignored.

(1) Authentication of messages

(2) Replay protection for messages

(3) Authentication of software updates

Can PGP perform these functions? Is it the best technical solution?

If the answer to both of these is yes, then we should consider 
these small systems.

Cheers - Bill

------------------------------------------------------------------------
Bill Frantz        |"Insofar as the propositions of mathematics 
refer to
408-356-8506       | reality, they are not certain; and insofar 
they are
www.pwpconsult.com | certain, they do not refer to reality.” 
-- Einstein

---

From: Hilarie Orman <[email-masked]>
Date: Wed, 12 Aug 2015 11:38:56 -0600 (MDT)

For the very low end devices, things that run on a AA battery for
10 years unattended, there simply is not enough power to do
any kind of crypto.  It's a research problem for device physicists.

Hilarie

----- Original Message -----
From: Bill Frantz <[email-masked]>
To: ianG <[email-masked]>
Cc: [email-masked]
Sent: Wed, 12 Aug 2015 11:12:12 -0600 (MDT)
Subject: Re: [openpgp] SHA-x performance

Cheers - Bill

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 12 Aug 2015 16:05:36 -0400

> eventually allow to write a small application which uses SHA-512 as its

Yes, oddly enough, this is a case where the pressure seems to be behind 512
being the default strength.

We definitely need 512 bits and adding 256 in addition seems like its the
thing to do. While the CFRG crypto is going for the 512 bit hash
internally, there is still a lot of ECDSA based stuff using the NIST curves
and that expects the 256 bit digest.

I can't see any particular reason for any of the other key strengths.

Talking of constrained devices BTW, I'm just trying out the new Windows 10
on a Raspberry Pi 2. Of course its going to have all the NIST curve
generation ECC and we are likely 3 years off the point where the CFRG stuff
is ubiquitous.

---

From: NIIBE Yutaka <[email-masked]>
Date: Thu, 13 Aug 2015 08:15:36 +0900

On 08/12/2015 05:32 AM, Werner Koch wrote:
> Do you have a suggestion on what CPUs from low to high end to do
> benchmarks so to check which SHA variant is suitable?

FWIW, here is some fact.

My RSA-2048 private key is on FST-01, which uses STM32F103 @ 72MHz.
This device is used to sign GnuPG source code release.  And it's daily
use to my access to Git repositories by OpenSSH.  With no crypto
accelerator, it takes about 1.4 second to sign.

Yesterday, I created a new key of ed25519/cv25519 and installed on
another FST-01.  It's faster.

If a user can wait for EdDSA computation as long as computation of
RSA-2048, STM32F030 @ 48MHz would be a candidate (no, I haven't tested
yet, just a possibility).

Please note that the firmware (Gnuk) doesn't implement OpenPGP, but
only OpenPGPcard specification.  It only computes with private key.
Since EdDSA requires SHA2-512, we have SHA2-512.

It scales to low end, when/if a user can wait.
--

---

From: Derek Atkins <[email-masked]>
Date: Thu, 13 Aug 2015 09:32:44 -0400

Phillip Hallam-Baker <[email-masked]> writes:

> Well the constraint on processing is easing up due to the move from RSA to ECC.

Sure, it reduces computation time from tens of seconds down to ones of
seconds.  ;)

> And for the amount of data going though one of these processors, the choice of
> AES or DES doesn't make much of a difference. These things don't have to
> communicate very fast.
>
> The thing that gets really uncomfortable is dealing with the amount of memory
> available. Quite a few of the embedded chips have even less RAM than the
> Commodore PET I started with when 32KB was the large machine. 

Oh, yeah.  Some of the environments I work in have like 2-4KB of RAM!

> Yes, these chips are not going away any time soon. The number of chips being
> made with 6502 based cores has increased every year since the 80s. But the
> problem with the chips isn't just that they are slow.

I'm not seeing 6502, but I am seeing a lot of 8051.

-derek

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 14 Aug 2015 09:30:24 +0000

>To what extent are we accepting the embedded market as "our market" ?

It's not a case of "now we want to target 8051's" but more a case of "the same
hardware that can currently employ PGP shouldn't be prevented from employing
it in the future because of a change to an overly heavyweight algorithm".
Switching from SHA-1 to SHA-256 isn't a big deal, but going to SHA-512 with
its order-of-magnitude slowdown over -256 is.

An example of a typical target device was the one mentioned in another post by
Yutaka Niibe, an STM32F103, which is a Cortex M3 that I mentioned earlier.  A
more recent, and also very popular one, is the M0 (released five years after
the M3, but with much more minimal capabilities, I'd set the minimum target at
an M3 in that if you want to be doing crypto you shouldn't be using an M0).

>already doing OpenPGP signing for some purpose? 

Use of PGP in embedded is basically nonexistent, so it's more a case of "this
could be useful in the future".  The stuff will have to be secured in some
manner, and being able to present PGP as a candidate would be good.

(To put this into perspective, there's an apparently neverending stream of
checkbox-engineered security standards and best-practices for things like
smart meters where the developers are being asked to implement X.509 cert
handling, SCEP for cert enrolment, TLS for reporting, and SSH for remote
management, on an M0 realtime system (so no task can hold up the CPU for more
than, say, 10ms) with 4kB RAM and 32kB flash total.  Now admittedly PGP won't
fit into that either, but it's slightly less insane than the wishlists being
promulgated by industry groups.  I have no idea what developers are doing in
response to this disconnect from reality in the requirements, but I'm guessing
it'll provide fodder for Black Hat and Defcon talks for years to come).

Peter.

---

From: Bill Frantz <[email-masked]>
Date: Fri, 14 Aug 2015 11:19:42 -0700

>I'm not seeing 6502, but I am seeing a lot of 8051.

I think in the IoT space, we will need to have signed software 
updates. I don't think there is much of an issue taking several 
seconds to verify an update signature, but these 8 bit 
processors seem like the right level of hardware for these IoT devices.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        |The nice thing about standards| Periwinkle
(408)356-8506      |is there are so many to choose| 16345 
Englewood Ave
www.pwpconsult.com |from.   - Andrew Tanenbaum    | Los Gatos, 
CA 95032

---

From: ianG <[email-masked]>
Date: Fri, 14 Aug 2015 20:07:50 +0100

> Oh, yeah.  Some of the environments I work in have like 2-4KB of RAM!

https://www.youtube.com/watch?v=Xe1a1wHxTyo

"And you try and tell the young people today..."

:)

---

From: Derek Atkins <[email-masked]>
Date: Sun, 16 Aug 2015 11:47:57 -0400

Bill Frantz <[email-masked]> writes:

> seconds to verify an update signature, but these 8 bit processors seem
> like the right level of hardware for these IoT devices.

Yes, signed software is definitely one use case.  However, often on
these systems it's more than just authenticating a software update;
sometimes it might actually want to check the signature on every bootup
(to prevent an attack on the flash/firmware)!

I'll note that there are alternate algorithms that run much faster than
ECC (e.g. Algebraic Eraser can run in the tens of miliseconds instead of
the ones of seconds of ECC)!  However my real point is that we should
not ignore these platforms, and more specifically we should remember
that they might not have the power to run the same algorithms that work
fine on our x86-64 servers.

-derek

---

From: Bill Frantz <[email-masked]>
Date: Tue, 18 Aug 2015 07:32:56 -0700

>(to prevent an attack on the flash/firmware)!

I hope we don't have to worry about attacks via physical access, 
so the only attacks available will be through the upgrade mechanism.

We also need to worry about authentication and replay prevention 
for the instructions delivered to these devices through the 
internet. One can imagine an architecture with a controller with 
the power of a Raspberry Pi giving orders to dumber devices 
using authenticated symmetric crypto as a solution. That system 
would prevent my favorite "neat hack" attack, turning your 
neighbor's living room into your own light organ.

>fine on our x86-64 servers.

I think we are in violent agreement here.

Cheers - Bill

---------------------------------------------------------------------------
Bill Frantz        | If you want total security, go to prison. 
There you're
408-356-8506       | fed, clothed, given medical care and so on. 
The only
www.pwpconsult.com | thing lacking is freedom. - Dwight D. Eisenhower

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 18 Aug 2015 10:53:14 -0400

On Tue, Aug 18, 2015 at 10:32 AM, Bill Frantz <[email-masked]> wrote:

> I hope we don't have to worry about attacks via physical access, so the
> only attacks available will be through the upgrade mechanism.
>
> We also need to worry about authentication and replay prevention for the
> instructions delivered to these devices through the internet. One can
> imagine an architecture with a controller with the power of a Raspberry Pi
> giving orders to dumber devices using authenticated symmetric crypto as a
> solution. That system would prevent my favorite "neat hack" attack, turning
> your neighbor's living room into your own light organ.

Exactly the approach I want to see.

Yes, it is absolutely true that 8 bit CPUs matter and I have been telling
people that there are more of them produced every year than the last for
over ten years now.

BUT

Anyone building a system who is trying to tell me that there is no room
anywhere in that system for a $1 Raspberry Pi sized CPU and memory needs
slapping with a cluestick.

What I would really like right now is some low cost controller for two
stepper motors that can sit off an IC2 serial port with all the commands
being authenticated by a MAC. I don't need a lot of CPU power to be able to
take commands off a slowish serial bus, authenticate them and set registers
controlling a couple of steppers.

Llama, my static hero sized dalek prop would like to be able to waggle his
plunger and exterminator gun. The idea is that when someone enters the
office without badging in, they get a surprise.

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 19 Aug 2015 01:27:59 -0700

> this new table with the SHA2 drop in replacements:

Dear OpenPGP list members.

NIST has finally produced the SHA-3 spec, FIPS 202 
http://dx.doi.org/10.6028/NIST.FIPS.202. It is difficult to believe that 
the last discussion on SHA3 ID that I recall was in 2012 in 
https://lists.gnupg.org/pipermail/gnupg-devel/2012-December/027173.html .

I have updated and posted the ID with details that were discussed so far 
in the thread, here:

>
> A new version of I-D, draft-jivsov-openpgp-sha3-00.txt
> has been successfully submitted by Andrey Jivsov and posted to the
> IETF repository.
>
> Name:		draft-jivsov-openpgp-sha3
> Revision:	00
> Title:		The use of Secure Hash Algorithm 3 in OpenPGP
> Document date:	2015-08-19
> Group:		Individual Submission
> Pages:		7
> URL:            https://www.ietf.org/internet-drafts/draft-jivsov-openpgp-sha3-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-jivsov-openpgp-sha3/
> Htmlized:       https://tools.ietf.org/html/draft-jivsov-openpgp-sha3-00
>
>
> Abstract:
>    This document presents the necessary information to implement the
>    SHA-3 hash algorithm with the OpenPGP format.

Your comments are very welcome.

The idea of the spec is to keep technical details written down, such as 
IDs, ASN.1 DER prefixes, and the exact set/subset of SHA3 algorithms. I 
also think that a few words on interoperability concerns will be helpful.

Second,  and this took the most time, I wrote a single-file C code SHA3 
implementation that should assist with the implementation of SHA3 in 
OpenPGP applications, testing, troubleshooting, and interoperability. 
One feature of this sample is that it follows Init/Update/Finalize (IUF) 
API, which is how OpenPGP uses the message digest. The project is called 
SHA3IUF.

The code is here:

    https://github.com/brainhub/SHA3IUF

To run the sample code:

    $ wget https://raw.githubusercontent.com/brainhub/SHA3IUF/master/sha3.c
    $ gcc -Wall sha3.c -o _ && ./_
    SHA3-256, SHA3-384, SHA3-512 tests passed OK

I hope that a spec and the SHA3IUF sample code will help avoid mistakes, 
such as the one in the above quoted message. All DER prefixes except for 
the SHA3-512 are incorrect. Please use the DER prefixes from the spec.

SHA3 is not the same as Keccak, and the two produce different hash 
values. SHA3IUF helps with other issues, such as how to define the IUF 
state, and how difficult is it to add each SHA3-X algorithm.

Presently the spec excludes SHA3-224, as seems to be a consensus on this 
list.

Please note that presently DSA or ECDSA truncate hashes. A digital 
signature with a DSA key with FIPS 186-3 L=2048 N=224 and a SHA3-256 
hash algorithm has security properties similar to the case when SHA3-224 
hash was used instead. In other words, an application already has a tool 
to use a 224-bit hash via an appropriate DSA/ECDSA key.

RSA signatures have plenty of "free" space for the hash, therefore, it's 
not clear why SHA3-224 would be needed.

Thank you.

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 19 Aug 2015 09:45:31 +0000

> and thus it ended up out of order.

And that's pretty much what the -224 hashes are, forgettable (and -384 only
slightly less so).  There's an obvious need for -256, and then you need -512
for people who need hashes that go to 11, but what's the point of -224 and
-384 in OpenPGP?  Are users really going to say "well, everyone else is using
-256 and I like to be different, but -512 is too big, and -384 just doesn't go
with the tie I'm wearing, so I'm really glad there's -224 as well"?  It's just
more bloat in the spec (and implementations) that'll never be used by anyone.
It was forgotten in 4880, it should be forgotten in x880 as well (along with
the equally useless -384).

Peter.

---

From: ianG <[email-masked]>
Date: Wed, 19 Aug 2015 14:47:56 +0100

> not clear why SHA3-224 would be needed.

For reasons like the above and the rest of the conversation (and Peter's 
comment), I think we should be examining SHAKE more closely.  The world 
of hashes has changed fundamentally because of Sponge.  The old 
assumptions embedded in the above are literally that - old, tired, 
historical.  If we want to make OpenPGP for the future, we want to have 
a stab at aiming for that future.

iang

---

From: "Robert J. Hansen" <[email-masked]>
Date: Wed, 19 Aug 2015 10:19:35 -0400

> And that's pretty much what the -224 hashes are, forgettable (and 
> -384 only slightly less so).  There's an obvious need for -256, and 
> then you need -512 for people who need hashes that go to 11, but 
> what's the point of -224 and -384 in OpenPGP?

IIRC, early drafts of DSA2 required a 224-bit hash for DSA-2048 and
didn't allow for the possibility of a truncated 256-bit hash.  Later
revisions corrected this oversight.  That's where it got into the spec:
because at the time it got into the spec, SHA-224 was required for
conformance.

---

From: Werner Koch <[email-masked]>
Date: Thu, 20 Aug 2015 15:08:13 +0200

> the equally useless -384).

Okay, you convinced me.  I retract my request to pre-allocate algo id
for SHA-3.  Let's add them if it turns out that they are required.

Shalom-Salam,

   Werner