Subject: [Cfrg] Deterministic signatures, revisit?

From: Dan Brown <[email-masked]>
Date: Mon, 9 Oct 2017 16:56:56 +0000

Hi CFRG,

ia.cr/2017/975 and ia.cr/2017/985 suggest tweaks to deterministic signing, eg EdDSA, due to side channels, etc. Do these tweaks merit consideration in CFRG?‎ (I'm not sure how important side channels are to CFRG or how strong the tweaks are.)

Best regards,

Dan

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 9 Oct 2017 10:30:19 -0700

This certainly keeps coming up. Beyond those papers see the previous "Side
channel attack and Edwards curves" thread on this list:

https://mailarchive.ietf.org/arch/msg/cfrg/V1JXfnf05uE88huYaQVKi7iZ6mY

I think it's definitely a problem that needs to be addressed. I've seen
various proposals to do so as well, i.e. synthesizing "r" as a combination
of a random nonce and the message, so that fault attacks would, at the very
least, require an RNG failure as opposed to always being possible, due to
repeated "r" values for the same message. This should retain the extant
defense against RNG failures in general as we saw with ECDSA "k" values,
since it would still include hashing the message as part of the calculation.

--
Tony Arcieri

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 9 Oct 2017 20:49:39 +0300

> since it would still include hashing the message as part of the calculation.

The latter (2017/985) paper in original message seemingly proposed a
countermeasure of that type. The description of countermeasure was not
completely clear, but I _think_ they proposed adding 768 random bits
between prefix and message in calculation of r.

This change would not break compatiblity (the verifier never sees how
r was generated), and if the random bits are bad, the scheme would not
break catastrophically (can not predict r even if all this entropy was
known).

However, it would expose the scheme to additional kleptographic
attacks. An ability to influence the random numbers used would be
enough to compromise the private key.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Tue, 10 Oct 2017 10:23:31 +0000

‎http://ia.cr/2017/890 gives a theoretical reason to prefer deterministic signatures: some proofs work better. So, my question goes to side channels (and subversion too, but less so) which is better at resisting them, deterministic or one of these tweaks in the 2 eprints below?

From: Dan Brown
Sent: Monday, October 9, 2017 12:57 PM
To: Cfrg
Subject: [Cfrg] Deterministic signatures, revisit?

Hi CFRG,

Best regards,

Dan

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 10 Oct 2017 13:46:11 +0300

On Tue, Oct 10, 2017 at 10:23:31AM +0000, Dan Brown wrote:
> ‎http://ia.cr/2017/890 gives a theoretical reason to prefer
> deterministic signatures: some proofs work better. So, my
> question goes to side channels (and subversion too, but less so)
> which is better at resisting them, deterministic or one of these
> tweaks in the 2 eprints below?

I think it depends...

There are environments that do not have to care about fault attacks
as long as the algorithm does not leak the key with random faults
(*cough* RSA-CRT *cough*), e.g. stuff running on general purpose
operating systems. However, such environments might very well care
about other side channels like cache attacks. The value of defenses
proposed by the paper for this are somewhat doubtful, altough those
defenses would prevent trying to repeatedly scan r with the same
message to sign (but proper constant-time algorithm would take care of
that as well).

Then there are environments that do care about fault attacks, like
smartcards. These environments usually care about side channels such as
timing and power analysis too. However, the sensitive parts are
elsewhere, needing additional randomization beyond what was proposed in
these papers.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Tue, 10 Oct 2017 13:51:58 +0000

< Hi, my responses (=questions) below (&sorry about the non-standard indicators) >

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Tuesday, October 10, 2017 6:46 AM

On Tue, Oct 10, 2017 at 10:23:31AM +0000, Dan Brown wrote:
> deterministic signatures: some proofs work better. So, my question 
> goes to side channels (and subversion too, but less so) which is 
> better at resisting them, deterministic or one of these tweaks in the 
> 2 eprints below?

I think it depends...

< ... skip ... >

Then there are environments that do care about fault attacks, like smartcards. These environments usually care about side channels such as timing and power analysis too. However, the sensitive parts are elsewhere, needing additional randomization beyond what was proposed in these papers.

< Am I right to interpret your "sensitive ... needing ... beyond ... these papers" as meaning you can attack the proposals in the IACR eprints 2017/{975,985}? Or, is it just a case of we already got other, larger problems than this anyway? >