[Cfrg] square roots

[Rene Struik <[e-mail]>]

Hi Ilari:

Just curious about your side channel remarks: could you give an example 
where side channel resistance of sqrt{x} is required? Wouldn't this 
computation only arise if one were to uncompress points, or can you give 
another example?

Best regards, Rene

where is On 6/4/2015 2:56 AM, Ilari Liusvaara wrote:
> On Thu, Jun 04, 2015 at 12:04:49AM +0100, Stephen Farrell wrote:
>> I'd hate to miss one of Alexey's polls:-)
>>
>> I'm almost neutral on this one. While we have historically preferred
>> #1 for the reason noted in the subject line, there are really very few
>> cases where that turns out to be a real issue, as opposed to being a
>> theoretical one.
>>
>> So I think we could probably live with #2, and that could suffice for
>> TLS and DNSSEC and other applications, even though #2 would mean
>> that users of the signature scheme (e.g. IETF protocol developers) may
>> need to learn something new, which is a downside.
>>
>> While #3 seems superficially attractive, my guess is it'd cause more
>> confusion and interop issues, and is of course offering a choice to
>> users of the scheme and so I don't like that one:-)
> Having an option of hashing the message first (with an indication that
> message was prehashed or even what hash was used) would be #3.
>
> Conversely, that would be the most reasonable implementation of #3.
>
> The reason for including hash function is to guard against trying to
> confuse implementations over what hash function is used, allowing
> forging signatures using stronger hashes by abusing weaker ones. The
> internal hash function is much less of concern due to natural
> strengthtening from hashing in various things derived from key.
>
>
>> So put me down for (#2 or #1) for this one, with a very very tiny
>> preference for #2 and documenting that one ought not use this for
>> signing large things directly (which one probably ought not do in any
>> case). But #1 would also be an acceptable outcome from my POV since
>> we're in practice already dependent on the collision resistance of
>> all the relevant hash functions and that won't ever really go away
>> as long as there are RSA/SHA256 certificates out there which'll be
>> the case for years and maybe decades to come. So the security
>> benefit of #2 isn't so great, although it's real.
> The problem with #1 isn't so much the CR requirement, but what it will
> do to implementation safety:
>
> Basically, it is difficult to do #1 without either:
> - Prehashing the message with something capabile of signing much larger
>    things. Adding an indication that this prehash has been done would give
>    #3).
> - Making scheme that is dangerous by breaking basic safety.
>
>
> The basic safety requirements I am thinking are:
>
> 1) Determinism.
>
> The scheme is fully deterministic.
>
> Breaking this makes the implementations very hard to test.
>
> 2) No random/unpredictable inputs except key.
>
> No input to functions except key may be assumed random in any way nor
> unpredictable.
>
> Breaking this makes primitive easy to misuse in ways that cause
> catastrophic breakage (reveal signing private key).
>
> 3) No scalar inversions or square roots for signature
>
> Signing must not need computing 1/x mod l or sqrt(x) mod l.
>
> Breaking this doesn't just make scheme slow, but also causes severe
> side-channel hazards.
>
> And sidechannels matter: Modern CPUs and OSes are ridiculously vulernable,
> with attackers capable of exploiting such bugs across virtual machines on
> the same physical hardware.
>
> 4) No nonces in main mode
>
> The main mode may not assume any input is not repeated.
>
> Breaking this again makes scheme easy to misuse with very bad results
> (hopefully anything using special modes will read the caveats).
>
>
> Breaking any of these will cause real-world failures, as has been
> demonstrated many times by ECDSA.
>
>
> -Ilari
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]