Subject: [Cfrg] Re-run of PRF issues: value of HMAC over prefix-Hash?

From: Dan Brown <[email-masked]>
Date: Thu, 6 Aug 2015 18:44:37 +0000

This email merely clarifies my arguments from some previous emails to CFRG:
no new essential details are presented, so you may want to skip (i.e.
tl;dr). 

The previous email in question asked whether the mod l (ell) reduction used
the PRF of EdDSA construction was "conservative enough", and spoke about
linear relations and so on.

My email did mention the threat of extension attacks.  My unclear intention
was extension attacks act like a canary for linearity attacks (described in
detail below).  

DJB's response correctly pointed out solid reasons for the lack of extension
attacks after mod l reduction.   His response also pointed out the fact that
HMAC might not fully resolve the linearity threat either, rhetorically
asking why HMAC might be a good PRF.  Furthermore, DJB argued (in that or
other emails), that various sort of potential hash attacks are not yet
indicated by any reduced-round analyses, and therefore merit no
countermeasure.  These three points are all good points, nearly decisive for
me, but I still have some lingering doubts, which are explained below.

The remote threat is that h = SHA-512 has a weakness of the following form.

An adversary A might find messages m_1,...,m_q for some q, say q=10,000,
such that for any secret s - unknown to the adversary, the vector
v = (h(s,m_1), ..., h(s,m_q))
has a high probability of belong to one of n vector spaces V_1,...,V_n of
rank q-1, where the adversary knows the vector spaces.  In other words, the
adversary might find vectors c_1,...,c_n such that the one of dot products
v.c_i is zero with high probability. We may consider n to be quite large,
e.g. n = 2^40, such that the number of steps is within a feasible range of
steps.  

The speculative intuition of this attack for a Merkle-Damgaard hash such as
SHA-512 is that an attacker (i) may use near-collision blocks in the
messages m_i, to get some kind of convergences away from s, and (ii) also to
employ some small differentials between the m_i, in the hope the relations
between m_i show up as relations between h_i=h(s,m_i).  Even more so, in a
hash like SHA-512, on can find think the message blocks as block cipher
keys, and one is thinking of related-key attacks.  I'm no expert, and don't
claim this will pan out.

Obviously, this would be a severe weakness in SHA-512 -- yes, perhaps more
severe than a collision.  Let's name this type of attack.  I don't know of
an existing name, so how about chosen-message-induced-linearity (CMIL)?
Clearly, one can ask if any PRF has a CMIL attack.  

Clearly a CMIL flaw violates the PRF properties of prefixed SHA-512.  But
prefixed SHA-512 already has extension attacks, which already violate its
PRF properties. This slightly lessens the incentive for cryptanalysts to
find a CMIL attack: it would be like beating a dead horse.

That said, if several expert hash cryptanalysts (i.e. people have attacked
hashes) assured me that many people have seriously tried and failed to find
CMIL attacks on prefixed SHA512, then I would attach more aegis to the
CMIL-resistance of prefixed SHA-512, and would gladly abandon the goal of
CMIL-resilience, and thus drop HMAC from my proposal.  So far, I have
(mis)understood DJB to have suggested exactly that: cryptanalysts have tried
and failed to find CMIL attacks on prefixed SHA-512, spending as much effort
as on collision attacks.  Alternatively, DJB was merely arguing that
collision attacks have progressed further (e.g. reduced-round attacks), than
CMIL attacks, so that collision-resilience is far more warranted than
CMIL-resilience.   Either way, in this regard, I am almost convinced by
DJB's arguments.  Maybe some more hash experts could confirm DJB's
arguments.  Failing that, there's other arguments too, below.

I don't know if: a CMIL attack implies a collision attack, a preimage
attack, a second-preimage attack, but maybe such an implication exists.  Any
one of these implications would decide the issue for me: so I'd definitely
drop HMAC, which does have a small cost, after all.    

Furthermore, I'm not too sure if a CMIL attack on prefixed SHA-512 would
lead to an attack on the use of: SHA-512 for key derivation; SHA-512 for
PRGs (e.g. NIST's HashDRBG or Linux's dev/random if SHA1 were replaced by
SHA-512); HMAC-SHA-512 as a MAC or as a PRF.

This last observation is perhaps most interesting.  The HMAC-as-PRF
construction gives the user one last kick at the can to erase the linearity
found by a CMIL attacker on prefixed Hash, because the compression function
with a secret message block is applied after that last block chosen by the
attack.  In other words, in HMAC, the attacker does not get the last word
(block).   

Of course, maybe there's some _other_ hash flaw out there, that seems no
less likely than the CMIL flaw, that would defeat the HMAC-as-PRF, and I am
just overlooking it.  If so, then let me know, so I can better understand
that HMAC does not improve the situation.

Or, even better, maybe there's even some argument that shows a CMIL attack
on a Merkle--Damgaard hash like SHA-512 implies a weakness in the SHA-512
compression function, and _furthermore_, the compression flaw can be used to
defeat the PRF properties of HMAC!   In other words, maybe a CMIL attack on
the hash implies a CMIL attack on the HMAC.  That does not sound implausible
at all to me, but I would want to see it to believe it.  

By the way, I don't think the argument above leading to a CMIL-attack on
HMAC would violate the existing HMAC security proofs at all, because the
current HMAC proofs generally assume a PRF compression function, at least as
I recall.  In other words, I understand that HMAC proofs work in the
opposite logical direction, a PRF attack on the HMAC implies a PRF attack on
the compression function; the HMAC security proofs offer HMAC PRF security
if the compression function does not offer PRF-security.  Overall, my
intuition of the HMAC security proofs is that they _preserve_ the PRF
properties, while overcoming the extension problems of prefixed
Merkle--Damgaard.  

So, I am trying to use HMAC for something that is not covered by the current
HMAC security proofs, at least according to my understanding of these
proofs. I don't have any sort of formal proof that HMAC can do this, but my
intuitive ad hoc analysis seems to suggest HMAC can fix this potential
problem, and I don't know of any practical alternative.

Again, I would be interested in answers to any of the questions above,
because these would easily reduce the concern about the CMIL flaw, or erase
the value provided by HMAC (or improve it).  Consider me to be looking for
reasons to drop the HMAC usage from my proposal.

In isolation, a CMIL attack might seem a minor technical, or even
theoretical if q and n are large, PRF failure.  Look how long RC4 stuck
around despite some known biases (without any chosen messages): maybe this
lack of reaction to RF4's PRF failures has reduced the incentive to find PRF
flaws in SHA-512.

Alas, for "deterministic" DL-based signatures a CMIL attack on the PRF could
have a very serious impact.  That impact does provide some applied incentive
to find CMIL attacks, but I think that CFRG is the first group to consider
seriously standardize deterministic signaturss, which means it is a
relatively new incentive.

The impact on deterministic signatures is as follows (though I hope I've
just made a big mistake). If one takes a CMIL-vulnerable PRF and _reduces
mod the group order_, as done in EdDSA, the linear relations carry through
into cyclic group modulo the group order.  I'll use some EdDSA notation and
the notation above and write r_i = h_i mod l, and I'll write u = h mod l =
(r_1,...,r_q).  If v.c_i = 0 then u.c_i = 0, which is what I mean by "carry
through".

Given the q signatures, each S_i in a signature, gives one linear equation,
among q+1 unknowns, the long-term signing key a, and q ephemeral keys,
r_1,...,r_q.  

One more equation is all that is needed to solve for all the secret keys.
If the adversary finds i such that u.c_i = 0, that would likely be enough
(unless, c_i is a combination of the equations given by S_i, but this seems
because we are supposing the CMIL attack that works without the involvement
of any signer).

The forger can find the crucial i by checking if sum_j (c_ij R_j) = O.  In
other words, think of U = (R_1,...,R_q) as a public vector corresponding to
secret vector u = (r_1,...,r_q), with the dot product c_i.U being easy to
evaluate, and O only c_i.u = 0.

Anyway, if CMIL-resilience is still worthwhile goal of the signature scheme,
one might try to modify the PRF by replacing the linear mod l reduction step
by something that would thwart the key-extracting forger above.   This is a
similar-in-quality principle to seeking a collision-resilience signature
scheme.  
 
For curves of 256 bits or smaller, my ECDSA_CFRG uses HMAC-SHA-384 (though
it could use HMAC-SHA-512 if that's what people prefer), followed by mod l
reduction.   So, compared to prefixed-hash PRF, the use of HMAC here inserts
an extra application of the compression function, with a secret block.
Again, the hope is that by applying a secret-message-block, the linearity
produced by the CMIL-attacker will be erased.  This seems like a small cost.

As I said above, I am aware of the fact that a CMIL attack on prefix-SHA512
would likely also imply a weakness in the SHA512 compression function, in
which case the argument for HMAC as a countermeasure to the threat is rather
weak.  

Maybe there's other good sources of PRF-ness that could be applied instead.
I can think of something based on an ECC operation, but that might be far
slower, and would raise the question of bad interaction with the other uses
of ECC operation in the signature scheme.

For larger curves, my presentation proposal recommends SHAKE256 (with an
excess of output bits) for the PRF.  In that setting, I am indeed relying
_solely_ on the SHA-3 competition to have stamped any possibility of a CMIL
attack, i.e. that prefixed-SHAKE256 is CMIL-resistant.  By contrast, for
smaller curves, which are more likely to deployed and therefore limited to
SHA-512, I proposed seeking a CMIL-resilience instead of relying on
CMIL-resistance.  

Of course, this is a somewhat inconsistent treatment of SHA-512 and
SHAKE256. I justify this using the extension attacks as kind of a proxy
canary to decide whether to add the HMAC layer, and to a lesser extent the
origin and history of the two hashes.

Best regards,

Daniel Brown
Certicom Research, BlackBerry Standards

---

From: "D. J. Bernstein" <[email-masked]>
Date: 10 Aug 2015 12:52:51 -0000

This subdiscussion is about the relative merits of two methods of using
(e.g.) SHA-512 to generate a nonce k modulo (e.g.) the Curve25519 group
order l:

   (1) k = SHA-512(seed,M) mod l.
   (2) k = HMAC-SHA-512(seed,M) mod l.

Neither of these allows length extension. Both of them offer "provable
security" marketing under plausible assumptions. The primary assumption
in both cases is that the SHA-512 compression function is very strong as
a PRF. #2 also needs an extra assumption, essentially the assumption
that the attacker can't distinguish HMAC from NMAC.

Of course, one shouldn't confuse marketing with true mathematical
guarantees of security. As Kelsey wrote in an internal NIST memo

   https://github.com/matthewdgreen/nistfoia/blob/master/EFFVersion/Two%20new%20DRBGs%20Based%20on%20Approved%20Hash%20Function%2C%20Kelsey%2C%20Jan.%202004.pdf

in 2004: "The public crypto community is (in my opinion) a little *too*
trusting of HMAC." Maybe the primary assumption is correct and #1 is
secure but the second assumption is wrong and #2 is breakable. Maybe
both assumptions are wrong and both #1 and #2 are breakable. Maybe
there's a gap between the assumptions and the conclusions: for example,
maybe both assumptions are wrong but one or both of #1 and #2 is
nevertheless secure. There are many possibilities.

Dan Brown's latest message is objecting to #1 because there's no proof
that an attack against #1 implies an attack against #2. For example,
it's conceivable that the attacker could find messages that produce a
collision (or other linear relation or bias or other nonce attack) in
SHA-512(seed,M) mod l without breaking HMAC-SHA-512(seed,M) mod l.

One can, however, object to #2 in exactly the same way: there's no proof
that an attack against #2 implies an attack against #1. For example,
it's conceivable that the attacker could find messages that produce a
collision (or other linear relation or bias or other nonce attack) in
HMAC-SHA-512(seed,M) mod l without breaking SHA-512(seed,M) mod l.

Is "AES could be weaker than Salsa20---there's no proof guaranteeing
that it's as strong" a valid objection to AES? Is "RSA could be weaker
than ECC---there's no proof guaranteeing that it's as strong" a valid
objection to RSA? Is "ECC could be weaker than RSA---there's no proof
guaranteeing that it's as strong" a valid objection to ECC? It should be
obvious that such statements don't say anything useful about security:
they're simply recognizing the reality that proofs aren't an adequate
basis for making cryptographic decisions.

Dan Brown writes:
> The HMAC-as-PRF construction gives the user one last kick at the can
> to erase the linearity found by a CMIL attacker on prefixed Hash

"One last kick at the can"? Sorry, but the user's code doesn't get the
chance to adaptively react to attacks. The code is written first, and
then the attacker looks at it and chooses messages accordingly.

Maybe the extra step in HMAC helps security. Or maybe it hurts security:
for example, maybe the second application of the key neatly cancels the
first application of the key. You keep speculating that hash functions
might allow "deletion" of a prefix, occasionally turning H(R,M) into
F(M), but one can just as easily speculate that hash functions might
allow "deletion" of the HMAC key.

> DJB argued (in that or other emails), that various sort
> of potential hash attacks are not yet indicated by any reduced-round
> analyses, and therefore merit no countermeasure.

No, that's not even close to what I said. Please go back and read my
messages more carefully.

---Dan

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 10 Aug 2015 16:43:34 +0000

+1 to DJB.

Also, should we reconsider our assumptions with SHA-3 becoming FIPS 202
(final)? As SHA-3 (a) is not vulnerable to extension attacks, and (b) is a
PRF by design requirement -  k=SHA-3-512(seed, M) mod l should be
sufficient form any point of view.

???

P.S. AFAIK, security proofs for (2) (below) are based on assumption that
the underlying compression function is a PRF. So a successful attack
against the underlying compression function should invalidate the proofs.
-- 
Regards,
Uri Blumenthal

On 8/10/15, 8:52 , "Cfrg on behalf of D. J. Bernstein"
<[email-masked] on behalf of [email-masked]> wrote:

>https://github.com/matthewdgreen/nistfoia/blob/master/EFFVersion/Two%20new
>%20DRBGs%20Based%20on%20Approved%20Hash%20Function%2C%20Kelsey%2C%20Jan.%2
>02004.pdf
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://mail.ietf.org/mailman/listinfo/cfrg