Re: [Cfrg] square roots

[David Jacobson <[e-mail]>]

If the field modulus p is congruent to 3 mod 4, one of the square roots 
of x can be computed by x^((p+1)/4) mod p, and the inverse can computed 
with x^(p-2) mod p.  Since the exponent is known, one does not need to 
worry about leaking bits of the exponent.  Underneath that, it is just 
multiplies and adds, and of those leak were are had anyway.

I don't see the problem.

      --David Jacobson


On 6/4/15 6:27 AM, Rene Struik wrote:
> 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
>
>