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

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:
>
> 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:bascule@gmail.com]
> *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 
> <dkg@fifthhorseman.net <mailto:dkg@fifthhorseman.net>> 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
>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg