Subject: Re: [Cfrg] A downside of deterministic DL signatures?

From: Dan Brown <[email-masked]>
Date: Fri, 1 Aug 2014 17:46:47 +0000

I was also asking if pre-computing kG is useful as a secondary side-channel 
countermeasure, which occurred to me upon skimming:

http://eprint.iacr.org/2011/232

As I understand the abstract of that paper, the implemented form Montgomery 
ladder was not constant time. This resulted in an exploitable side channel. 
They describe a simple fix.  But in the event of other possible side channels, 
such as those arising from bugs and underlying system quirks (whatever 
acceleration the system tries to provide), does it make sense to use some 
secondary independent side-channel countermeasures?  For example, does 
computing the ECDSA signature component kG at the start of the TLS handshake 
in parallel with other operations, such as the ECDHE computations and so on, 
have any potential help by blurring any timing information?

Best regards,

Dan

From: Tony Arcieri [mailto:[email-masked]]
Sent: Thursday, July 31, 2014 5:09 PM
To: Daniel Kahn Gillmor
Cc: Michael Hamburg; Dan Brown; IRTF Crypto Forum Research Group
Subject: Re: [Cfrg] A downside of deterministic DL signatures?

On Thu, Jul 31, 2014 at 10:23 AM, Daniel Kahn Gillmor <[email-masked]> 
wrote:

neither of these required nationstate-level effort, and they date back

to 2008.

Okay, let me put it this way instead:

Collisions:

- Can be used to alter the content of individual messages

- This requires that the design of the hash function itself be broken

Bad nonces:

- Leak the private key which can then be used to forge as many messages as you 
wish

- Can be the result of bad RNGs/implementation errata even if the algorithm 
and the rest of its implementation is sound

Which is worse?

-- 
Tony Arcieri

---

From: David Jacobson <[email-masked]>
Date: Fri, 01 Aug 2014 19:55:51 -0700

It is easy to blind k.  Remember you compute something like

k^-1 * (z + r*d)

You also compute k*G.    You do that with the Montgomery ladder, so it 
doesn't leak.

The next problem is to computing k^-1.  We might use the binary inverse 
method, but it has zillions of data-dependent branches and doesn't run 
in anything even close to constant time.  He is how we solve that.

Let b be a fresh for each computation uniform random value in the range 
[1, n-1].

Compute instead

(k * b)^-1 * b * (z + r * d)

Even though the inverse is full of data-dependent branches and isn't at 
all constant time, that doesn't matter, because all values of b are 
equally likely, so it is kind of like encrypting k with a one-time-pad: 
you get information-theoretic security.

I thought about distributing b inside stuff to the right like this:

(k*b)^-1 * (b*z + r * (b*d))

to also avoid a multiplication of d with r, which is both random and 
known to the attacker---generally considered favorable for DPA attacks.  
And if that multiplication could be attacked it would leak d, the 
private key.  But I'm worried because there is a multiplication of b*z, 
and z (basically H(msg)) is known by the attacker.  (I only know enough 
about DPA to get myself into trouble.  So I'll stop before making a 
blunder.)

     --David Jacobson

On 8/1/14 10:46 AM, Dan Brown wrote:
>
> I was also asking if pre-computing kG is useful as a secondary 
> side-channel countermeasure, which occurred to me upon skimming:
>
> As I understand the abstract of that paper, the implemented form 
> Montgomery ladder was not constant time. This resulted in an 
> exploitable side channel.  They describe a simple fix.  But in the 
> event of other possible side channels, such as those arising from bugs 
> and underlying system quirks (whatever acceleration the system tries 
> to provide), does it make sense to use some secondary independent 
> side-channel countermeasures?  For example, does computing the ECDSA 
> signature component kG at the start of the TLS handshake in parallel 
> with other operations, such as the ECDHE computations and so on, have 
> any potential help by blurring any timing information?
>
> Best regards,
>
> Dan
>
> *From:*Tony Arcieri [mailto:[email-masked]]
> *Sent:* Thursday, July 31, 2014 5:09 PM
> *To:* Daniel Kahn Gillmor
> *Cc:* Michael Hamburg; Dan Brown; IRTF Crypto Forum Research Group
> *Subject:* Re: [Cfrg] A downside of deterministic DL signatures?
>
> On Thu, Jul 31, 2014 at 10:23 AM, Daniel Kahn Gillmor 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
> - Leak the private key which can then be used to forge as many 
> messages as you wish
>
> - Can be the result of bad RNGs/implementation errata even if the 
> algorithm and the rest of its implementation is sound
>
> Which is worse?
>
> -- 
> Tony Arcieri
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg