Subject: [Cfrg] EdDSA signer's PRF conservative enough, or as possible?

From: Dan Brown <[email-masked]>
Date: Thu, 23 Jul 2015 19:59:33 +0000

Dear CFRG,

The generalized EdDSA proposal can be viewed as defining the following PRF
function r:

 r(seed,M) = (H(seed || M) mod l)

where || is concatenation and l is the base point order.  The function H
seems to depend on the curve, but is generally a 2b-bit hash where l has b
bits (or slightly fewer).  Further, H is based on SHA-512, perhaps by
truncating and concatenating multiple SHA-512 outputs.

Intuitively, this function r(.,.) is a good PRF, even though technically
H(seed || M) is not a good PRF.  

I say H alone is not a good PRF because it is subject to extension attacks.
Given h = H(seed | M) but not seed, I may be able to compute h' = H( seed |
M | N) for some choices of N. If this H-based construction were a PRF, then
I should not be able to extend it without the seed.  Even if the outputs of
H are kept secret (as ephemeral private keys would be), I could generated a
known (but non-linear) relation between the secrets.

As far as I can tell, the mod l reduction prevents such extension attacks.
So, that's why I say it is intuitive that the r function ought to be a good
PRF.

Q1) Is there some kind of formal argument why the mod l reduction can
elevate a non-PRF into a PRF?

Of course, it is not strictly necessary for the nonces r (ephemeral private
keys) be generated by a PRF, but it is a conservative choice, given that
linear known relations between different r values can expose s, the log of
the verifier's public key, which suffices to be able to forge signatures
(despite not being called the secret key).

In other words, even if EdDSA had instead used a non-PRF for r, such one in
which H was SHA-256 for Curve25519, known non-linear relations between
different r that an adversary could create by using hash extensions, are not
known to expose s.  That would be intuitively fine, but even less
conservative.

Q2) Why not tweak the PRF design to make it more conservative?  

In other words, instead of relying on the non-linearity of extension-based
known relations, and the effect of the mod l reduction on improving the PRF
quality, why not start (before mod l reduction) with a PRF something that is
free of extensions, and also a widely trusted good PRF (with "aegis")?

Other features of EdDSA aim to be conservative to address concerns. For
example, (i) hashing the verifier's public key to address potential
multi-user attacks, and (ii) using 2b bits for the ephemeral, instead of
3b/2 bits. So why be less conservative with the pre-reduction PRF for r?  

Maybe the answer is that the EdDSA PRF function for r is just simpler than
alternatives, and thereby less prone to implementation fault. If so, then,
yes, it can indeed be viewed as a conservative design.

Anyway, the concerns above partly explain why I proposed using HMAC or SHAKE
for this task in ECDSA_CFRG, because at least they are free of known
extension attacks.  Furthermore, they are believed to be good PRFs before
mod l reduction.  (Actually, I'm not 100% sure about SHAKE: it only promises
to be an extendable-output hash.  Maybe sponge designers also promise a good
PRF?)  Perhaps, using HMAC or SHAKE here is just too complicated: and likely
to lead to implementation faults.  If so, then maybe a simpler,
non-extendable, pre-reduction function could be used, like this:

 r(seed,M) = (H(seed||M||seed) mod l).

I think that construction has been called "sandwich" in other contexts. I
recall there being some good reason for not using it in HMAC, though I do
not know if that reason would carry over to ephemeral key generation.
Nevertheless, maybe the simplicity of the sandwich construction plus its
lack of extension attacks combine to be a suitably conservative PRF here
(again, all presuming HMAC or SHAKE are for some reason not simple enough).

Best regards,

Daniel Brown

---

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

Hashing to a large range of integers, and then reducing the result
modulo a substantially smaller integer m, is a completely standard
construction. People often take m to be a power of 2 since truncation is
so efficient, but in public-key contexts another choice of m is often
more natural, and in the ECC signature context the obvious choice of m
is the group order.

Viewing this reduction as part of the hash construction---a "wide-pipe"
hash, with output size substantially smaller than internal state size---
was introduced by Finney and, in much more detail, by Lucks. This view
hides the public-key context, and Finney's posting sounded like it was
considering only truncation as the reduction map:

   https://www.mail-archive.com/[email-masked]/msg02635.html

However, the Lucks paper---the paper typically cited as introducing wide
pipes---explicitly allowed any reduction map ("C''" in that paper), with
truncation merely as one example:

   http://link.springer.com/chapter/10.1007%2F11593447_26

Either way, it's well understood that this reduction eliminates the only
generic security problem with prefix MACs. Every SHA-3 submission was
required to resist length-extension attacks and to specify PRFs; there
were tons of SHA-3 submissions explicitly conjecturing that their prefix
MACs were secure, without the complications of HMAC; many submissions
achieved this through exactly the "wide-pipe" idea.

Of course, actual _proofs_ of security are available only for limited
classes of attacks, but this is the situation pretty much everywhere in
cryptography: e.g., the PRF conjecture for AES-CBC-MAC is proven only
for attacks that don't break the PRP conjecture for AES. There are
always unproven conjectures, and what really matters is the extent to
which cryptanalysts have tried and failed to come up with attacks.

> elevate a non-PRF into a PRF?

Why do you think HMAC can "elevate a non-PRF into a PRF"?

If you don't think that stopping all known attacks is the right answer
then clearly your answer is the "provable security" of HMAC---the
security of HMAC against a limited class of attacks, namely attacks that
don't break the "pseudorandomness" of the underlying compression
function.

Now here's an exercise for you: Prove, for the same limited class of
attacks, that reduced prefix MAC is secure. As a hint, the following
paper has all the necessary proof techniques, and covers truncated CBC
and prefix sponge MAC as two examples:

   https://eprint.iacr.org/2015/053.pdf

You can and should ask how carefully this has been reviewed---but you
should also ask the same about, e.g., Bellare's Crypto 2006 HMAC paper,
which had a fundamental flaw pointed out in 2012 by Koblitz and Menezes,
explored more thoroughly in a followup paper from Lange and me:

   http://cacr.uwaterloo.ca/~ajmeneze/anotherlook/hmac.shtml
   https://eprint.iacr.org/2012/318

You should also ask how tight the proofs are. This is a real problem for
HMAC. The best solution we know is to take wide pipes, but taking wide
pipes also removes the entire justification for HMAC!

You should also ask whether the class of attacks covered by the security
proof is being accurately summarized. In the case of HMAC it certainly
isn't---the proof is really for NMAC, and for HMAC there's an extra
limitation, basically the assumption that attacks can't distinguish NMAC
from HMAC. Hash-function cryptanalysts will generally agree that this
assumption is reasonable and very hard to break (even when the number of
hash rounds is reduced enough that we can find collisions), but if your
goal is to minimize the number of security assumptions then you should
be objecting to HMAC (and also to pretty much every KDF-related
assumption) and advocating pure reduction instead.

Please let me know whether you'd like to adapt your signature proposal
in light of these considerations. If not then I should dig through your
latest PRF details and implement them in the Python script.

> Q2) Why not tweak the PRF design to make it more conservative?

This question starts with unjustified assumptions. In fact, the existing
design is already extremely conservative, including a very wide pipe and
a reduction layer. An HMAC layer would be redundant, and I don't see how
you can justify the notion that it's _more_ conservative rather than
_less_ conservative. See above.

I'm sympathetic to the notion that AES, with well-documented scrutiny
spanning more than 15 years, is the obvious choice whenever anyone asks
for a PRP---or (for a limited number of queries) a PRF, or a wider PRF.
It's well understood how to build larger PRF constructions assuming that
AES is secure. However:

   * AES is a nightmare for constant-time software on most platforms.
     It's also a nightmare for software auditors.

   * Having to support a hash function _and_ AES is a considerable extra
     cost for small devices implementing signatures. There are various
     proposals of AES-based hashes but these haven't received much
     review---and they aren't based on the well-studied PRP property.

A more attractive approach is to switch to SHA-3. Unlike SHA-2, SHA-3
was selected through a public competition that from the outset required
collision resistance _and_ a PRF. For various reasons I'm pretty sure
that most cryptanalysts who have looked at these functions would rate
SHA-3 as lower risk than SHA-2, despite the age of SHA-2. However, it's
not clear to me that IETF is ready to start using SHA-3.

Here's what the original Ed25519 paper said about these issues:

   Standard PRF hypotheses imply that this pseudorandom session key r is
   indistinguishable from a truly random string generated independently
   for each M, so there is no loss of security. Well-known
   length-extension properties prevent secret-prefix SHA-512 from being
   a PRF, but also do not threaten the security of Ed25519-SHA-512,
   since r is not visible to the attacker. All remaining SHA-3
   candidates are explicitly designed to be PRFs, and we will not
   hesitate to recommend Ed25519-SHA-3 after SHA-3 is standardized. It
   would of course also be safe to generate r with a cipher such as AES,
   combined with standard PRF-stretching mechanisms to support a long
   input; but we prefer to reuse H to save area in hardware
   implementations.

---Dan

---

From: Dan Brown <[email-masked]>
Date: Tue, 28 Jul 2015 19:53:46 +0000

Hi Dan,

Thanks for your reply to my message, in which I had written in perhaps too
much haste, partially forgetting a some basics.

Thanks for generously giving my initial under-specified proposal a free ride
in your python script: you lent my proposal the EdDSA PRF design.

Thanks for your patient reminder about wide-pipes in general serving as PRF,
and with the final truncation provided being the well-established, primary
protection against extension attacks in many wide-pipe hashes.  (Is it the
only protection, or is there also some kind of padding protections?)

Thanks also for your reminder that PRF was a goal of the SHA3 competition. 

I am still undecided about the _best_ PRF. 

So, there's three prominent unbroken variable-input-length PRFs:
(generalized) EdDSA's prefixed-truncated-(extended)-SHA-512; and
NIST/Keccaks' SHAKE, and HMAC. 

In ECDSA_CFRG proposal, my thought was to combine the wide-pipe strategies
with the HMAC strategy to build a PRF.  That's redundant, as already you
pointed out.  Sometimes redundancy helps to be conservative, sometimes it is
superfluous.    

Just to be clear: do you think a 256-bit truncated HMAC-SHA-512 is _less_
conservative a PRF than a key-prefixed 256-bit truncated SHA-512 hash?  

It seems that I have not followed all the HMAC controversy as closely as you
have.  I will review your 2012 paper.  In the meantime, is all this fuss
just about proof correctness, or is there also hypothetical attack against
which HMAC is not resilient?  That might be a reason is to deem it less
conservative, even if combined with a wide-pipe.

I hadn't noticed the 2015 eprint on proving that prefixing wide-pipe hashes
prevents extension.  At least I am not the only one seeking more
verification of this feature.

You asked whether you should amend your python script: I can send you the
relevant changes, but first I would like to think about the PRF issue a
little more.  Thanks for the offer.

Further comments in-line below.

Best regards,

Dan

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of D. J. Bernstein
> Sent: Saturday, July 25, 2015 9:42 AM
> To: [email-masked]
> Subject: Re: [Cfrg] EdDSA signer's PRF conservative enough, or as
possible?
> 
> Hashing to a large range of integers, and then reducing the result modulo
a
> substantially smaller integer m, is a completely standard construction.
People
> often take m to be a power of 2 since truncation is so efficient, but in
public-
> key contexts another choice of m is often more natural, and in the ECC
> signature context the obvious choice of m is the group order.
> 
was
> introduced by Finney and, in much more detail, by Lucks. This view hides
the
> public-key context, and Finney's posting sounded like it was considering
only
> truncation as the reduction map:
> 
>    https://www.mail-
> archive.com/[email-masked]/msg02635.html
> 
pipes-
> --explicitly allowed any reduction map ("C''" in that paper), with
truncation
> merely as one example:
generic
> security problem with prefix MACs. Every SHA-3 submission was required to
> resist length-extension attacks and to specify PRFs; there were tons of
SHA-3
> submissions explicitly conjecturing that their prefix MACs were secure,
without
> the complications of HMAC; many submissions achieved this through exactly
> the "wide-pipe" idea.
> 
classes of
> attacks, but this is the situation pretty much everywhere in
> cryptography: e.g., the PRF conjecture for AES-CBC-MAC is proven only for
> attacks that don't break the PRP conjecture for AES. There are always
> unproven conjectures, and what really matters is the extent to which
> cryptanalysts have tried and failed to come up with attacks.
> 
> Dan Brown writes:
[DB] Intuitively, the HMAC construction elevates a fixed-input-length PRF
into a variable-input-length PRF. So, HMAC stopped the extension attacks,
has been around for quite a while, and seems also to be quite a high-profile
target (not something obscure) without any major attacks.  In other words,
it has lots of aegis security as a PRF. (Sure, newer designs are shinier,
perhaps even preferable over HMAC.)

> If you don't think that stopping all known attacks is the right answer
then
> clearly your answer is the "provable security" of HMAC---the security of
HMAC
> against a limited class of attacks, namely attacks that don't break the
> "pseudorandomness" of the underlying compression function.

[DB] Yes, "provable security" is nice too, especially for deciding between
new schemes.

> Now here's an exercise for you: Prove, for the same limited class of
attacks,
> that reduced prefix MAC is secure. As a hint, the following paper has all
the
> necessary proof techniques, and covers truncated CBC and prefix sponge MAC
> as two examples:
> 
should
> also ask the same about, e.g., Bellare's Crypto 2006 HMAC paper, which had
a
> fundamental flaw pointed out in 2012 by Koblitz and Menezes, explored more
> thoroughly in a followup paper from Lange and me:
> 
HMAC.
> The best solution we know is to take wide pipes, but taking wide pipes
also
> removes the entire justification for HMAC!
> 
proof
> is being accurately summarized. In the case of HMAC it certainly
isn't---the
> proof is really for NMAC, and for HMAC there's an extra limitation,
basically
> the assumption that attacks can't distinguish NMAC from HMAC. Hash-
> function cryptanalysts will generally agree that this assumption is
reasonable
> and very hard to break (even when the number of hash rounds is reduced
> enough that we can find collisions), but if your goal is to minimize the
number
> of security assumptions then you should be objecting to HMAC (and also to
> pretty much every KDF-related
> Please let me know whether you'd like to adapt your signature proposal in
light
> of these considerations. If not then I should dig through your latest PRF
details
> and implement them in the Python script.
> 
design is
> already extremely conservative, including a very wide pipe and a reduction
> layer. An HMAC layer would be redundant, and I don't see how you can
justify
> the notion that it's _more_ conservative rather than _less_ conservative.
See
> above.
[DB] To clarify the question: wouldn't it be _yet even_ more conservative to
use HMAC-SHA-512 as the PRF, and then truncate to 256 bits. 

Yes, this is a redundant layer, but wouldn't a failure require both layers
to fail?  

Just to be clear, I don't intend to ask if wide-pipe hash in EdDSA should be
replaced by a narrow-pipe HMAC: that is perhaps less conservative.

> spanning more than 15 years, is the obvious choice whenever anyone asks
for
> a PRP---or (for a limited number of queries) a PRF, or a wider PRF.
AES is
> secure. However:
> A more attractive approach is to switch to SHA-3. Unlike SHA-2, SHA-3 was
> selected through a public competition that from the outset required
collision
> resistance _and_ a PRF. For various reasons I'm pretty sure that most
> cryptanalysts who have looked at these functions would rate
not
> clear to me that IETF is ready to start using SHA-3.
> 

 [DB] Again, in the ECDSA_CFRG proposal I suggested for the PRF:
- HMAC-SHA-384 (or HMAC-SHA-512 if it is more widely supported), intended
for immediate deployment
- SHAKE256 intended for those who want to have lots of extra security
protections, e.g. scrutiny of the SHA3 competition.

This split case is a tad complicated, but it aims to encourage migration
those who want extra-security to use as many extra-security as possible.