Subject: Re: [Cfrg] Soliciting EC signature scheme proposals

From: Tanja Lange <[email-masked]>
Date: Sun, 5 Jul 2015 20:14:57 +0200

[I tried sending this earlier with the paper as an attachment but
it bounced due to size]

Dear all, 
Please find our suggestion for a generalized EdDSA signature scheme at
	http://eprint.iacr.org/2015/677
 
Looking forward to your comments
 	Bo-Yin, Dan, Peter, Simon, and Tanja

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 5 Jul 2015 21:45:51 -0700

Hello CFRG,

Here is my suggestion for a signature scheme.

For an element x of Z/NZ or [0,N), let FLLEE(x) be the little-endian 
encoding of x with fixed length ceil(log(n)/8) bytes.  Let its partial 
inverse be the function FLLED.

Let G be an abelian group with order h*q, where h is small and q is 
prime.  Let EncodePoint(P) be an encoding from the group to a 
fixed-length byte sequence.  Let DecodePoint(bytes) be the partial 
inverse of Enc.  Let g in G have order q.

Let Setting be a personalization string of size exactly 8 bytes. Let 
Curve be a string of size exactly 4 bytes.

Let HLen be either ceil((log q)/16) bytes or ceil((log q)/8) bytes. 
Different HLens should imply different settings.

Let Hash be a hash function whose output is at least HLen bytes. Let PRF 
be a pseudorandom function from strings to byte strings of length 
ceil((log q)/8 + 8) bytes.

A secret key is a ceil((log q)/8)-byte value Secret.  An expanded secret 
key is (Secret, Exp) where Exp = PRF(Secret, EncodeString("Exponent")).

The public key corresponding to the secret key is Pub := EncodePoint(Exp 
* g).

The CFRG-SUGGESTION signature of a message Message is computed as follows:

Exp = PRF(Secret, "SCRT")
Ephemeral = PRF(Secret, Concat(
     "EPHE", Setting, Curve,
     Message
))
P = Ephemeral * g
Challenge = Truncate(Hash(Concat(
     "CHAL", Setting, Curve, Pub, P,
     Message
)), HLen bytes)

Response = FLLEE(Challenge*Exp + Ephemeral (mod q))

The signature is (Challenge, Response).

To verify a signature with a public key Pub, the verifier first decodes 
Pub to a point PubP.  If the decode fails or if the decoded point is the 
identity, then the signature fails.  The verifier then computes:

P = FLLED(Challenge) * PubP + FLLED(Response) * G.

The signature is valid if Challenge == Truncate(Hash(Concat(
     "CHAL", Setting, Curve, Pub, P,
     Message
)), HLen bytes).

The advantages of this signature scheme are as follows:

1) It includes personalization which can be used to thwart 
cross-protocol attacks.  The personalization is fixed-length to simplify 
implementations.

2) It supports IUF by replacing Message with Hash(Message) (of at least 
log(q)/8 bytes) and changing the setting string.

3) It support signature coupons by replacing the PRF with a random function.

4) It supports a half-length HLen, which makes for shorter signatures 
without losing security.  This is useful when space is at a premium (eg 
in embedded devices).

5) It explicitly supports short secrets, which is useful for embedded 
devices.

6) It supports a full-length HLen, which has the property that it is 
infeasible to find two (pubkey,message) pairs with the same valid 
signature.  This feature could be useful in some sort of authenticated 
file system.

7) If the public key comes from a trusted source, then it is not 
possible for an attacker to fool the verification algorithm by 
exploiting bugs involving a small number of special group elements (eg, 
the identity or torsion points).

8) Everything is fixed-length except the message, unlike ECDSA+ASN1.

9) No inversions mod the field order.

10) It fits all of CFRG's other stated requirements.

Disadvantages of this scheme:

1) It doesn't support batch verification.

2) I didn't tell you the point encoding scheme, because I put off 
writing this until the last minute.  The Ed25519 one is fine, as are 
Half-Caf (y != -1 such that x is positive), Decaf, etc.

Cheers,
-- Mike

On 6/21/2015 2:52 AM, Alexey Melnikov wrote:
> Dear CFRG participants,
>
> We are now at the point where we have gathered sufficient requirements 
> (not necessarily NIST-compliant, deterministic, IUF interface) where 
> it seems sensible to invite proposals for signature schemes meeting 
> those requirements.
>
> We would like to have proposals that are reasonably detailed so that 
> they can be assessed properly by CFRG readers. We realise that doing 
> fully detailed proposals would take a lot work, so we do not expect 
> full-fledged proposals in the style of a NIST competition (say). That 
> said, we would like to encourage proposers to explain the security 
> properties of their proposals as well as their implementation 
> characteristics, and to make proposals that are generic in the sense 
> of being usable for either of the two curves that we have previously 
> agreed upon.
>
> Please submit your proposals within 2 weeks (i.e. by July 5th); 
> e-mails to the CFRG list are fine. We encourage constructive questions 
> and clarifications about proposals as they are made. At this stage, we 
> anticipate needing a longer discussion period that extends beyond the 
> 2 week submission period. After that, we may poll to decide on CFRG 
> recommended scheme. Depending on how the on-list discussions go in the 
> next 4 weeks, we might also have face-to-face discussion at the CFRG 
> meeting planned for IETF 93 in Prague in July.
>
> Best Regards,
> CFRG Chairs.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 6 Jul 2015 09:42:46 +0300

On Sun, Jul 05, 2015 at 09:45:51PM -0700, Mike Hamburg wrote:
> Let G be an abelian group with order h*q, where h is small and q is prime.
> Let EncodePoint(P) be an encoding from the group to a fixed-length byte
> sequence.  Let DecodePoint(bytes) be the partial inverse of Enc.  Let g in G
> have order q.
> 
> Let Setting be a personalization string of size exactly 8 bytes. Let Curve
> be a string of size exactly 4 bytes.
> 
> Let Hash be a hash function whose output is at least HLen bytes. Let PRF be
> a pseudorandom function from strings to byte strings of length ceil((log
> q)/8 + 8) bytes.
> 
> A secret key is a ceil((log q)/8)-byte value Secret.  An expanded secret key
> is (Secret, Exp) where Exp = PRF(Secret, EncodeString("Exponent")).
> 
> The public key corresponding to the secret key is Pub := EncodePoint(Exp *
> g).
> 
> To verify a signature with a public key Pub, the verifier first decodes Pub
> to a point PubP.  If the decode fails or if the decoded point is the
> 1) It includes personalization which can be used to thwart cross-protocol
> attacks.  The personalization is fixed-length to simplify implementations.

I don't think 8 byte personalization string is enough. And having
implemented scheme with variable-length personalization, the complexity
difference was small (one extra call plus pulling argument around).

> 3) It support signature coupons by replacing the PRF with a random function.

Or the "EPHE" with another string and message with nonce? Has advantage of
requiring "just" a nonce (which is hard already)?
 
> without losing security.  This is useful when space is at a premium (eg in
> embedded devices).
> 
> infeasible to find two (pubkey,message) pairs with the same valid signature.
> This feature could be useful in some sort of authenticated file system.
> 
> 7) If the public key comes from a trusted source, then it is not possible
> for an attacker to fool the verification algorithm by exploiting bugs
> involving a small number of special group elements (eg, the identity or
> torsion points).
> 

See above about 1). And one would never need to decode the variable-
length things anyway.
 
> 2) I didn't tell you the point encoding scheme, because I put off writing
> this until the last minute.  The Ed25519 one is fine, as are Half-Caf (y !=
> -1 such that x is positive), Decaf, etc.

Half-Caf is the "-y if x is negative, otherwise y" one (with maybe bit of
special handling of x=0)?

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 6 Jul 2015 09:45:46 +0300

> 	http://eprint.iacr.org/2015/677

Some quick comments:

- Replacing IVs in SHA-2 computations is pretty unsupported.
- If one allowed asymmetric splits, generating the 1056 bits for E-521
  would only take 3 rounds, not 4.
- Ed448 could use Curve448-compatible basepoint instead.
- Could be possible to use SHA-512 for the verifier-visible hash
  (which would likely cause a nasty mess on hashes to use)?
- Some earlier discussions brought up variable hash truncation.
  Looks like SHAKE* actually truncates, so one has to keep
  output length constant.
- Specifying prehash on key takes preknowledge on key on IUF
  (unless one guesses, possibly multiple guesses).

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 6 Jul 2015 01:35:43 -0700

> On Jul 5, 2015, at 11:42 PM, Ilari Liusvaara <[email-masked]> wrote:
> 

Yeah, I almost made it variable length.  On the one hand, long perso strings
add almost negligible complexity, and might be useful if someone is
dynamically generating them.  On the other hand, I didn’t want to define a
variable-length encoding, and it adds some complexity, and each secret key
is going to be used in, like, three protocols ever, so 64 bits might actually be
enough.  Also, 8 bytes doesn’t break alignment, though for natural alignment
I probably should have made it CHAL, curve, setting instead of CHAL,
setting, curve.

> requiring "just" a nonce (which is hard already)?

Good point, thanks.

> See above about 1). And one would never need to decode the variable-

That’s true.  And you could hard-code them into buffers in most applications.

> special handling of x=0)?

Right.  If x=0, then output y=1.  Otherwise -y if x is negative and y if x is
positive.  It divides the cofactor by 2, which doesn’t accomplish much…
it’s one of those “you might as well since it’s so easy” kind of things.

> -Ilari

— Mike

---

From: Björn Edström <[email-masked]>
Date: Sun, 12 Jul 2015 22:50:08 +0200

Re: the EdDSA proposal from Lange et.al: My software engineer perspective:

I'd also express some concern with the SHA-2 IV modification. The
implementer now suddenly has to ship his code with a second
implementation of SHA-2, because I know of no libraries that allow for
changing the IV easily. If I were to implement this proposal for say
OpenSSL or OpenSSH I'd have to do some intrusive internal changes if I
don't want to ship with a completely separate implementation just for
this schema. For example OpenSSL, as well as many other similar
projects, make the assumption that the IV:s are internal and are thus
abstracted away from their library implementation. My 2 cents would
prefer something more standard (instead of changing the IV, maybe use
the strings as an HMAC key, for example - see ideas in my previous
email on this very topic).

(Of course, with algorithms such as Keccak etc the old assumptions
about how a "hash API" should look like have to change anyway, but
that's a separate topic.)

Cheers
Björn

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 12 Jul 2015 14:59:41 -0700

Caution: I have not reviewed the EdDSA proposal yet, so I'm operating
solely on
Bjorn's summary. With that said, it would be very nice to be able to use a
stock
SHA-2 implementation.

-Ekr

---

From: David Jacobson <[email-masked]>
Date: Sun, 12 Jul 2015 16:20:12 -0700

FIPS 180-4 specifies how to compute the hash for a truncation of another 
hash.   Here is a quick summary by example using SHA-512/224.  Make a 
new hash function by XORin the SHA-512 IV with 0xa5a5a5....  Then use 
that hash function to compute the hash of the ASCII string 
"SHA-512/224".  The result is the IV.

The eprint paper http://eprint.iacr.org/2015/677 says

     FIPS 180-4 defines SHA-512/224 s the 224- bit truncation of a 
modified version of SHA-512.
     The modification consists of replacing the SHA-512 IV with an IV 
defined by hashing the
     string "SHA512/224".

That's not quite correct.  It would lead the reader to believe that the 
string "SHA-512/224" was simply hashed with SHA-512.  But it is actually 
hashed with a modified hash.

I've not worked though the examples in the eprint to see whether the 
FIPS 180-4 scheme is actually followed, or whether it follows what the 
text seems so say.

Now on a different subtopic:

Many high-end embedded devices have hardware hash engines with the IV in 
the silicon.  A scheme like this will force a pure software 
implementation of the hashing.  I join Björn and Eric in advocating 
caution about a design that makes existing HW hash engines and software 
libraries unusable.

What the paper is trying to do is an expansion operation to get, in one 
example, 1056 bits out of SHA-512.  Would there be any security 
consequences to just prefixing the message with "SHA-512/1056part0" 
(etc)  zero-padded out to the input block size and hashing with SHA-512 
4 times?  That way any SHA-512 HW engine or software implementation 
would work.  It could be optimized by taking the state after the first 
block has been processed and using that as the IV (4 IVs, of course).

     --David

On 7/12/15 2:59 PM, Eric Rescorla wrote:
> Bjorn's summary. With that said, it would be very nice to be able to 
> use a stock
> SHA-2 implementation.
>
> -Ekr
>
>
> On Sun, Jul 12, 2015 at 1:50 PM, Björn Edström <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Re: the EdDSA proposal from Lange et.al <http://et.al>: My
>     software engineer perspective:
>
>     <[email-masked] <mailto:[email-masked]>>
>     wrote:
>     > [email-masked] <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jul 2015 18:30:48 -0700

On Sun, Jul 12, 2015 at 4:20 PM, David Jacobson
<[email-masked]> wrote:
> hash.   Here is a quick summary by example using SHA-512/224.  Make a new
> hash function by XORin the SHA-512 IV with 0xa5a5a5....  Then use that hash
> function to compute the hash of the ASCII string "SHA-512/224".  The result
> is the IV.
>
>     FIPS 180-4 defines SHA-512/224 s the 224- bit truncation of a modified
> version of SHA-512.
>     The modification consists of replacing the SHA-512 IV with an IV defined
> by hashing the
>     string "SHA512/224".
>
> I've not worked though the examples in the eprint to see whether the FIPS
> 180-4 scheme is actually followed, or whether it follows what the text seems
> so say.
>
> Many high-end embedded devices have hardware hash engines with the IV in the
> silicon.  A scheme like this will force a pure software implementation of
> the hashing.  I join Björn and Eric in advocating caution about a design
> that makes existing HW hash engines and software libraries unusable.
>
> example, 1056 bits out of SHA-512.  Would there be any security consequences
> to just prefixing the message with "SHA-512/1056part0" (etc)  zero-padded
> out to the input block size and hashing with SHA-512 4 times?  That way any
> SHA-512 HW engine or software implementation would work.  It could be
> optimized by taking the state after the first block has been processed and
> using that as the IV (4 IVs, of course).

This is almost the scheme the eprint proposes, except with a change in
how the length of the message is used. It's clear to me that there is
very little to differentiate between different schemes at this point.

> Caution: I have not reviewed the EdDSA proposal yet, so I'm operating solely
> on

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 13 Jul 2015 09:18:38 -0000

>   (unless one guesses, possibly multiple guesses).

All of our prehashing parameter examples for EdDSA use SHA-512 as the
prehash. This means that, no matter what happens in the final signing
process, you start by computing SHA-512(m). The key and curve size
aren't relevant until the finalization (the constant-size PureEdDSA
computation). IUF is fully supported; there's no guesswork.

Of course, any protocol that doesn't need single-pass IUF, or that
controls its message lengths, can and should simply use PureEdDSA: i.e.,
use the identity function as the prehashing function.

>   (which would likely cause a nasty mess on hashes to use)?

All of our examples use SHA-512. I'm not sure what your question is.

>   would only take 3 rounds, not 4.

Sure, but if an implementation wants to integrate the hash details into
the key derivation then having an even split simplifies the data flow.
The cost difference is negligible either way.

> - Replacing IVs in SHA-2 computations is pretty unsupported.

The great thing about standards is that there are so many of them to
choose from. :-)

Our long-hash examples follow the pattern of the SHA-512/224 and
SHA-512/256 standards from FIPS 180-4. It's of course possible to
replace the FIPS 180-4 approach with prefixed SHA-512, but would this
actually produce any simplifications for a library designer who wants to
add support for a new signature system?

A cleaner possibility (with other advantages) is SHA-3, specifically
SHAKE256. The SHA-3 draft standard is reported to be completely stable,
simply waiting for a final signature from the Secretary of Commerce.

It would be useful to collect data regarding any actual difficulties of
implementing these standards. For example, in every IUF API I've seen
for SHA-512, changing the IV is a trivial matter of overwriting the IV
copied by the Init function, but maybe there are tougher situations.

>   Looks like SHAKE* actually truncates, so one has to keep

EdDSA already has several levels of defense against this type of attack,
so this really isn't an issue for the hash-function selection.

As a reminder, two signatures (R,r+H(R,A,M)s) and (R',r'+H(R',A,M')s)
reveal the difference (r-r')+(H(R,A,M)-H(R',A,M'))s. If r-r' is limited
to an interval, and H(R,A,M)-H(R',A,M') is nonzero, then this limits s
to an interval divided by a public number. A well-known extreme case is
that repetitions r=r' with M!=M' are an instant disaster. As a less
extreme case, if r-r' is in an interval of length 2^128 then "kangaroo"
discrete-log methods find s in 2^64 operations. Even a small bias in
r-r', say being limited to half of the whole discrete-log interval, is
breakable by "lattice attacks" if it happens often enough.

Normally we generate r and r' as secret-prefix hashes of M and M'
respectively. The attack under discussion takes M'=M, which normally
produces r'=r and thus H(R,A,M)-H(R',A,M')=0, revealing nothing; but the
attack hopes that the hash function producing r' is instead chosen as a
truncation of the hash function producing r, so that r-r' has only the
truncated bits and H(R,A,M)-H(R',A,M') is nonzero.

In EdDSA, the number of bits produced by the hash function is always 2b.
The size parameter b is also the length of the secret key. Consequently,
if one hash function used in EdDSA is a truncation of the other, then
the b values are different, so the secret keys don't have the same
lengths---e.g., one Ed41417 secret key and one Ed448 secret key. The
secret keys for different signature systems are of course chosen
independently, producing unrelated hash prefixes and thus completely
breaking the relationship between r and r'.

Even if someone violates standard key-management practice and tries,
e.g., padding an Ed41417 secret key to obtain an Ed448 secret key, the
attack doesn't work. These padded keys are hashed to produce s and the
hash prefix; the different input length for the hash again produces
unrelated outputs, and in particular unrelated hash prefixes, again
completely breaking the relationship between r and r'.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 13 Jul 2015 13:20:51 +0300

> computation). IUF is fully supported; there's no guesswork.

If to prehash using SHA-512 or use PureEdDSA is controlled by the key,
right?
 
> use the identity function as the prehashing function.

Aside: TLS 1.2 is practicularly odd case. Server signatures can
easily use offline mode (e.g. for Curve25519, the amount of data to
sign would be 100 bytes, all available in one shot, especially with
implementation support for scatter-gather message processing), whereas
Client signatures rather use prehashing (easily reaching multiple
kilobytes accumulated over multiple messages).

> All of our examples use SHA-512. I'm not sure what your question is.

Using raw SHA-512 for H(R,A,M). But that's probably too messy, since
other hashes that have variable-length outputs (e.g. SHAKE256) are
supported too.

> add support for a new signature system?

Not a lot supports SHA-512/256. And even stuff that supports it, doesn't
support loading custom IVs.
 
> simply waiting for a final signature from the Secretary of Commerce.

Unfortunately SHA-3 is regarded as bit "bleh" at current point (due
to slowish speeds combined with hardware focus). So I don't expect
real wide and fast uptake.

Blake2b seems to have gained fair bit of popularity (due to very
high speed together with high security margins), but it is limited to
512-bit output too.
 
> copied by the Init function, but maybe there are tougher situations.

With any sort of "safe" languages, one can't just overwrite the IV,
and even with "unsafe" languages, overwriting IV is pretty hacky
(breaks encapsulation in really nasty way).

> breaking the relationship between r and r'.

Yeah, the hash length is fixed, which prevents attacks from hash
truncation. And using unrelated keys for different curves is the
safe way (it seems surprisingly difficult to deal with curves of
the same size, or worse, isogenous curves otherwise).

-Ilari

---

From: "Dang, Quynh" <[email-masked]>
Date: Mon, 13 Jul 2015 12:30:15 +0000

Hi Ilari,

>From the data on EBASH I showed you before, I think SHAKE256 has better performance than SHA-512 over all.

One can always add encoding for output size at the end of an input message to SHAKE256 to prevent related outputs for different hash output sizes to happen.

Quynh. 

________________________________________
From: Cfrg <[email-masked]> on behalf of Ilari Liusvaara <[email-masked]>
Sent: Monday, July 13, 2015 6:20 AM
To: [email-masked]
Subject: Re: [Cfrg] principles in choosing hash functions for signatures

-Ilari

---

From: David Jacobson <[email-masked]>
Date: Mon, 13 Jul 2015 06:23:15 -0700

On 7/13/15 2:18 AM, D. J. Bernstein wrote:
> [snip]
> [snip]

You are assuming an environment where the developer of the ECC code is 
also the developer of the hash.  But in industrial settings these are 
often developed by different groups.  The modularity police would not be 
at all happy to see the ECC code depending on the detailed layout of the 
context structure for the hash function.  In addition, in different 
products the code is linked with different hash function libraries.  On 
a low-end device, it will be a software implementation.  On higher end 
devices it will call into a hash engine.  (This is very common.)   That 
hash engine will likely have the IV fixed in silicon.  On an ARM V8A 
processor with the crypto extension, there are hardware instructions for 
accelerating SHA-256.  Right now, there are no instructions for SHA-512, 
but there might be in a future release.

Prefixed popular standard hash functions (e.g. SHA-256 and SHA-512) are 
much to be preferred over modifying IVs.  It is super simple: Just a one 
Update call passing in the appropriate literal.  It works with all 
Init-Update-Final implementations.

     --David Jacobson

---

From: Brian Smith <[email-masked]>
Date: Mon, 13 Jul 2015 11:12:07 -0400

>> add support for a new signature system?
<snip>

> Init-Update-Final implementations.

I agree with this. Actually, it greatly simplifies things for some
implementations if only stock SHA-256 and SHA-384, at most, are required.
There would be no other use for SHA-512 with an IV other than the one used
for SHA-384 in many applications.

Cheers,
Brian

---

From: "D. J. Bernstein" <[email-masked]>
Date: 13 Jul 2015 22:29:25 -0000

Here's a concise way to set up an OpenSSL SHA512_CTX to contain NIST's
standard IV for SHA-512/224:

   SHA512_Init(&c);
   for (i = 0;i < 8;++i) c.h[i] ^= 0xa5a5a5a5a5a5a5a5;
   SHA512_Update(&c,"SHA-512/224",11);
   SHA512_Final(md,&c);

An alternative approach is to directly call SHA512_Transform, but this
code is simpler since it doesn't have to set the padding bits. A faster,
slightly less concise approach is to directly set each c.h[i] to its
final value.

I'm not at all attached to the FIPS 180-4 hashing standard---the EdDSA
examples follow that approach simply because it's the closest standard
to what's needed; there are many other safe possibilities---but I'm also
puzzled by the comments saying that it's hard to implement.

I'm even more puzzled by the comments suggesting that (for external
users, supposing that the signature system isn't in the library itself)
OpenSSL provides some particular "abstraction" of SHA-512, allowing some
operations but not others. As far as I can tell, OpenSSL didn't actually
document _any_ portion of its SHA-512 C API until February 2015:

   https://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff;h=f7812493a0da6b740274135ce340ff7505027057

Users of the OpenSSL SHA-512 functions have been going beyond the
documented API for many years, and this really doesn't seem to have been
the biggest problem with crypto, or the biggest problem with OpenSSL.

David Jacobson writes:
> On an ARM V8A processor with the crypto extension, there are hardware
> instructions for accelerating SHA-256.

Don't the ARM SHA-256 instructions maintain the current hash value in
NEON registers in a well-understood format? Doesn't this make it easy
for the programmer to change the IV?

> The modularity police would not be at all happy to see the ECC code
> depending on the detailed layout of the context structure for the hash
> function.

EdDSA carefully separates the hashing details from the ECC details. What
we're talking about is something different, namely the relationship
between (e.g.) a SHA-512/224 module and a SHA-512 module, and then it's
much harder to make an information-hiding argument.

It seems reasonably obvious what a SHA-512 module designer will do if
asked to include support for SHA-512/224 etc. with minimum redundancy
(the same way that ARM handles both SHA-256 and SHA-224). Your concern,
if I understand it, is with SHA-512 modules that are set in stone and
that therefore can't include this support---but then what's the problem
with the SHA-512/224 module designer relying on the SHA-512 details?

> Would there be any security consequences to just prefixing the message
> with "SHA-512/1056part0" (etc)  zero-padded out to the input block
> size and hashing with SHA-512 4 times?

Properly prefixed SHA-512 is safe inside EdDSA.

The motivation for NIST's IV tweaks in FIPS 180-4 (and similarly for
"Sakura" in SHA-3) is to set up different contexts for different hash
lengths. The idea is to make it immediately obvious that attackers can't
transport hashes from one context to another. On the other hand, this
certainly isn't a substitute for doing a careful cross-protocol security
analysis---sufficiently agile protocol designs can leap over any number
of cryptographic firewalls into the pit of doom!---and it also isn't a
necessary component of such an analysis. As I said, I'm not at all
attached to the FIPS 180-4 approach.

---Dan

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 14 Jul 2015 00:13:23 -0700

On 07/13/2015 08:12 AM, Brian Smith wrote:
> David Jacobson <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     Prefixed popular standard hash functions (e.g. SHA-256 and SHA-512)
>     are much to be preferred over modifying IVs.  It is super simple:
>     Just a one Update call passing in the appropriate literal.  It works
>     with all Init-Update-Final implementations.
>
>
> implementations if only stock SHA-256 and SHA-384, at most, are
> required. There would be no other use for SHA-512 with an IV other than
> the one used for SHA-384 in many applications.

+1.

On 07/13/2015 02:18 AM, D. J. Bernstein wrote:
> It would be useful to collect data regarding any actual difficulties
> of implementing these standards. For example, in every IUF API I've
> seen for SHA-512, changing the IV is a trivial matter of overwriting
> the IV copied by the Init function, but maybe there are tougher
> situations.

This assumes software implementation with available source code as a 
starting point.

Unfortunately, this doesn't cover hardware-software implementations of 
SHA. These interfaces will likely have limited choices and we can't 
expect that they always offer extensibility through tweaking of the IVs. 
SHA-512/256 is rare anyway, but even if e.g. SHA-512 + SHA-384 are 
available, they are either offered as unrelated hash algorithms or as 
limited choices (e.g. I can't define my own flavor of SHA-512), in the 
examples I know.

Other notes:

 >     SHA512_Update(&c,"SHA-512/224",11);

I am curious whether this code is always correct on 32 bit build 
targets. IMO OpenSSL doesn't hide c.h because it expects cooperating 
developers. The 'c' was intended to be used as an opaque type through 
"accessor methods" like Init/Update/Final.

Finally, there would be a need for another set of test vectors for yet 
another SHA variant.

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 14 Jul 2015 07:44:54 +0000

> OpenSSL doesn't hide c.h because it expects cooperating developers. The 'c'
> was intended to be used as an opaque type through "accessor methods" like
> Init/Update/Final.

And the next release will make it opaque so you can't play this "trick" without special support.

	/r$

---

From: "D. J. Bernstein" <[email-masked]>
Date: 14 Jul 2015 15:33:37 -0000

> If to prehash using SHA-512 or use PureEdDSA is controlled by the key,

I don't understand the question. How do you imagine an EdDSA key
controlling the choice of prehash function?

A protocol that specifies HashEdDSA (for IUF) would normally specify the
prehash function as part of this. All of our HashEdDSA examples specify
SHA-512; this means that all messages are fed through SHA-512, without
regard to the key or the key length or the choice of curve.

It's of course possible to build a protocol that hashes some long
messages with SHA-256 and hashes other long messages with SHA-512, where
the choice between SHA-256 and SHA-512 is dynamically dictated by a bit
in a signature-key-plus-hash-choice blob, and then obviously a signer or
verifier would want to inspect the blob before hashing. But this sounds
like agility run amok. More to the point, this isn't specific to EdDSA;
exactly the same complication can be applied to any signature system.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 14 Jul 2015 19:37:32 +0300

> controlling the choice of prehash function?

Well, apparently some misunderstanding based on lack of "firewalling"
plus some comments.
 
> regard to the key or the key length or the choice of curve.

Let's take that TLS 1.2 (and likely 1.3) it has a field for hash
algorithm used in signature, offering choices including identity and
SHA-512 (with note that identity is intended for signature algorithms
that can take arbitrary length inputs to sign, but no presently
defined signature algorithm is capable of that, but e.g. Ed25519 certainly
would).

The structure is like:

- Signature algorithm (1 => RSA, 2 => DSA, 3 => ECDSA, ...)
- Hash algorithm (0 => Identity, 4 => SHA256, 5 => SHA384, 6 => SHA512, ...)
- Actual signature blob (octet string).

Where the opposite side advertises (signature, hash) pairs it supports,
and the signer picks one.

No two hash algorithms presently available have the same output length,
but in future algorithm colliding with one of the SHA-2 algorithms could
be added (and of course, identity can collide lengthwise with all).

This mostly affects client certificates in TLS 1.2. I'm having difficulty
imagining anything that would have problems using identity for TLS 1.2
server signature or either of the present TLS 1.3 signatures.

Also, note that server that is practicularly lazy might want to pick
SHA-256 or SHA-384 (or any other prf-hash) depending on cipher, as
servers need to keep running hash with intermediate results using
that algorithm anyway (and TLS security theorems rely on that being
CR).

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Tue, 14 Jul 2015 20:08:31 +0300

> - Actual signature blob (octet string).

That’s only if TLS decides to define it that way. They might decide that EdDSA is only used with a pre-hash and then they don’t need an identity hash.

Or they could decide that EdDSA is only used with an identity hash and then (4,4), (4,5), or (1,0) is illegal. 

Or they could decide that each curve is assigned a fixed pre-hash so we use zero in the hash algorithm octet as a special value that means that the hash is dictated by RFC.

Or IPsecME might decide that all these signatures are acceptable, and each hash-EdDSA-anotherhahs combination gets its own OID as does PureEdDSA-hash and that is used in the signature payload of RFC 7427.

It’s up to the protocol WG to decide which combinations to use and how much freedom of choice to give implementers and users. 

Yoav

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 14 Jul 2015 19:22:03 +0000

On 7/14/15, 3:44 , "Cfrg on behalf of Salz, Rich" <[email-masked]

>And the next release will make it opaque so you can't play this "trick"

+10!  :-)

---

From: Damien Miller <[email-masked]>
Date: Wed, 15 Jul 2015 09:18:36 +1000 (AEST)

> and the signer picks one.

That yields a N*M explosion of possibilities, with only few of them useful
and increased opportunities for downgrade shennannigans.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 15 Jul 2015 13:31:47 +0300

> and increased opportunities for downgrade shennannigans.

Maybe, but that's how TLS 1.2 (and as of current editor's draft,
1.3) signatures apparently work as of currently.

And there is apparently an assumption that the hash algorithm identified
is calculated by the TLS code and the hash is passed to be signed, so
if signature algorithm is to take anything but hash to sign, then hash
algorithm indicated will be identity (called "none" in TLS RFC itself).

-Ilari

---

From: "D. J. Bernstein" <[email-masked]>
Date: 16 Jul 2015 20:36:12 -0000

David Jacobson writes:
> prefixing the message with "SHA-512/1056part0" (etc)  zero-padded out
> to the input block size and hashing with SHA-512 4 times?  That way
> any SHA-512 HW engine or software implementation would work.  It could
> be optimized by taking the state after the first block has been
> processed and using that as the IV (4 IVs, of course).

Just to explore this idea further: Since this is a more serious
deviation from the FIPS 180-4 approach, I'd suggest a slightly different
naming scheme, say "+" for prefixing instead of "/" for IV replacement.
This means that, e.g., the 114-byte "SHA-512+912" output for a message m
would be the concatenation of

   57 bytes of SHA-512("SHA-512+912part0/2"+zeropadding+m)
   57 bytes of SHA-512("SHA-512+912part1/2"+zeropadding+m)

with the padding expanding the prefix to one SHA-512 input block (128
bytes). As you said, the state after the first block can be precomputed,
similarly to HMAC.

Obviously this would work with SHA-512 (rather than just the SHA-512
compression function) as a black box, without the FIPS 180-4 IV tweaks.
>From a security perspective, the disadvantage of prefixing is that the
auditor has to watch out for the possibility of the prefixed hash of m
being transported to a protocol that uses SHA-512 directly and views the
same hash as coming from a modified message prefix+m; but this doesn't
matter for EdDSA.

Were there other concerns regarding the choices of hash functions?

A few of the comments on the mailing list sounded to me like objections
to any use of SHA-512 as requiring serious new implementation work for
devices that support only SHA-256 and SHA-384 (and that didn't use the
obvious modularization of SHA-384). I don't see adding SHA-512 code as a
significant fraction of the ECC implementation effort, and it's also not
a significant performance issue for normal signature applications,
_except_ that prehashing a very long message might be a significant
cost. The choice here is pretty much independent of the signature
proposal, but it does have to be settled one way or another if
signatures are going to be interoperable.

One of the nice features of SHA-3 is that all the different output sizes
can be easily supported with a single implementation. With SHA-2 there's
a real separation between the SHA-256 compression function, mapping 768
bits to 256 bits, and the SHA-512 compression function, mapping 1536
bits to 512 bits; everyone uses separate code, separate tables, etc.
With SHA-3, all output sizes are built straightforwardly from one
unified 1600-bit permutation module, which is also an obvious target for
tests and for optimizations.

---Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 17 Jul 2015 11:21:14 +0300

> bytes). As you said, the state after the first block can be precomputed,

Should work.
 
> Were there other concerns regarding the choices of hash functions?

Not really (using unextended H(R,A,M) is probably too nasty to specify).

Then there are prehash choices in various protocols, e.g. TLS 1.2:
- For server signature, there is no problem with PureEdDSA.
- However, for client signature, there is a problem: Even if the data
  to sign is only a few kB, the private key might very well be on a
  smartcard (with extremely limited resources).

Or PKIX:
- Certs and OCSP responses should be small enough (relative to devices
  used to sign those) that PureEdDSA works fine.
- CRLs can be pretty large. And might very well use the same signing
  keys as the two above.

> signatures are going to be interoperable.

I haven't heard of any software where SHA-384 is supported but SHA-512
isn't either in already or could be easily be added.

It is completely different ballgame with IV replacements (where even
support for SHA-512/256 is no guarantee that arbitrary IV replacements
are supported).

-Ilari

---

From: Björn Edström <[email-masked]>
Date: Mon, 20 Jul 2015 11:29:53 +0200

Since there aren't that many comments here I just want to chime in
that I believe this proposal (SHA512+t) is much nicer from an
implementation perspective than the original FIPS 180-4 based one. The
desired trait for me is to be able to use a hash implementation as a
black box, which I can in this case.

Best regards
Björn