Subject: [Cfrg] Elliptic Curves - signature: use of inversion mod the group order (ends on August 12th)

From: Alexey Melnikov <[email-masked]>
Date: Mon, 03 Aug 2015 18:36:44 +0100

Dear CFRG participants,

As a group, we now need to start moving towards having a single signature
scheme design. To begin this process, chairs note that one of the
proposals ("brown") requires the use of inversion mod the group order
while the other four proposals do not. Concern has been expressed here in
the past about the difficulties of protecting modular inversion against
side channel attacks. Given these concerns and the availability of other
schemes that do not require it, chairs would like to conduct a short poll
on whether we should avoid selecting a scheme that requires modular
inversion. Please express your views on this over the next week and a 
bit by voting
"yes" or "no" with "yes" meaning "yes, we should avoid modular inversion"
and "no" meaning "no, that's not necessary".

[Note that if the majority is for "yes' then this would eliminate the
scheme "brown" from further consideration, but would not preclude its
proposer from tweaking the scheme to avoid inversion; however, we would
then need to examine whether it is substantially different from other
schemes remaining on the table.].

Please don't discuss any other topics in this thread.

Best Regards,
Alexey and Kenny

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 3 Aug 2015 17:49:23 +0000

No.

It's easy enough to protect modular inversion from side channel attacks by blinding; to invert a, select a random value r, and compute r(ar)**-1.

So, I don't believe modinv is an automatic disqualification.  On the other hand, modular inversion isn't a cheap operation; "brown" would need to show enough advantage over the other proposals to be worth the cost.  

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> Sent: Monday, August 03, 2015 1:37 PM
> To: [email-masked]
> Subject: [Cfrg] Elliptic Curves - signature: use of inversion mod the group
> order (ends on August 12th)
> 
> Dear CFRG participants,
> 
> scheme design. To begin this process, chairs note that one of the proposals
> ("brown") requires the use of inversion mod the group order while the other
> four proposals do not. Concern has been expressed here in the past about
> the difficulties of protecting modular inversion against side channel attacks.
> Given these concerns and the availability of other schemes that do not
> require it, chairs would like to conduct a short poll on whether we should
> avoid selecting a scheme that requires modular inversion. Please express
> your views on this over the next week and a bit by voting "yes" or "no" with
> "yes" meaning "yes, we should avoid modular inversion"
> [Note that if the majority is for "yes' then this would eliminate the scheme
> "brown" from further consideration, but would not preclude its proposer
> from tweaking the scheme to avoid inversion; however, we would then need
> to examine whether it is substantially different from other schemes
> remaining on the table.].
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 3 Aug 2015 11:04:13 -0700

Yes, avoid modular inversion.

Modular inversion isn’t a show-stopping security problem.  But it makes the system slower and more complicated, and it requires extra code, with no significant benefit.

This is especially true for ECDSA-like schemes, where the recipient needs to either multiply and divide mod q, or decode and triple-scalarmul.  By contrast, the recipient of a Schnorr-like signature doesn’t need to implement any kind of math mod q.

> On Aug 3, 2015, at 10:36 AM, Alexey Melnikov <[email-masked]> wrote:
> 
> Dear CFRG participants,
> 
> inversion. Please express your views on this over the next week and a bit by voting

---

From: "Mehmet Adalier (Antara Teknik)" <[email-masked]>
Date: Mon, 3 Aug 2015 18:32:25 +0000 (UTC)

No, it is not necessary to avoid modular inversion.
a) as Scott indicates it is relatively easy to protect modular inversion from side channel attacks.
b) performance is not a show stopper.  there are several methods to perform modular inversion quite fast. we have an implementation on x86_64 in C, which is substantially less than 10k cycles (for 256-bit prime operand). 
"brown" should not be disqualified based on its use of modular inversion
      From: Scott Fluhrer (sfluhrer) <[email-masked]>
 To: Alexey Melnikov <[email-masked]>; "[email-masked]" <[email-masked]> 
 Sent: Monday, August 3, 2015 10:49 AM
 Subject: Re: [Cfrg] Elliptic Curves - signature: use of inversion mod the group order (ends on August 12th)
   
No.

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 03 Aug 2015 20:50:02 +0200

Yes.

Modular inversion is strictly speaking not a security problem, but a
significant performance issue.  I believe the question asked is
misleading as you only high-light side-channel as a problem.  It will
not be clear whether people respond based on the side-channel aspect or
on other considerations associated with modular inversoin.

/Simon

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 03 Aug 2015 19:52:04 +0100

Yes, I would prefer to avoid this modular inversion.

Absent a compelling argument for it's security benefits (which
I've not seen) I would favour simplicity and performance.

There is also merit in speedy elimination of alternatives from
consideration, so long as there is no credible *and* significant
security benefit of a given scheme vs, the others. I think this
("getting done") is a fair consideration, given that there is a
need to get this decided before being overtaken by events which
would render the entire signature-selection process moot.

S.

---

From: Dan Brown <[email-masked]>
Date: Mon, 3 Aug 2015 19:09:53 +0000

no... mod order inversion is small price to keep some of the aegis of ECDSA.

if the majority votes yes, then I may either:
 amend my proposal per the CFRG thread ElGamal * Schnorr ...
or require expanded signatures replacing s by t:u.
or just drop it.

let me know off-list if you think either of the first two is worthwhile. If I get no response I'll drop it.

  Original Message
From: Alexey Melnikov
Sent: Monday, August 3, 2015 1:36 PM
To: [email-masked]
Subject: [Cfrg] Elliptic Curves - signature: use of inversion mod the group order (ends on August 12th)

Dear CFRG participants,

Best Regards,
Alexey and Kenny

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 3 Aug 2015 13:28:35 -0700

On Mon, Aug 3, 2015 at 10:36 AM, Alexey Melnikov <[email-masked]>
wrote:

> Please express your views on this over the next week and a bit by voting

I'll vote yes.

I was thinking of voting "no, but..." because I find modular inversion
unnecessary (indeed the whole scheme is markedly not like the others, which
I feel are generally converging on a "rough consensus") and a reason why I
would vote against this scheme in general, but not necessarily an
intractable security problem.

Instead I voted "yes" because I think it creates wiggle-room for screw ups,
and I think it's advantageous to eliminate this wiggle room wherever
possible.

-- 
Tony Arcieri

---

From: Paul Lambert <[email-masked]>
Date: Mon, 3 Aug 2015 21:09:48 +0000

>no... mod order inversion is small price to keep some of the aegis of ECDSA.

It's not clear to me how a goat skin shield emblazoned with ECDSA would be a benefit.
If you mean sponsorship or protection of ECDSA, the group already has strayed from the path of any form of aegis of NIST.

>>. Please express your views on this over the next week and a bit by voting "yes" or "no" with "yes" 
>>meaning "yes, we should avoid modular inversion" and "no" meaning "no, that's not necessary".

Yes - avoid inversion.  

Paul

---

From: Dan Brown <[email-masked]>
Date: Mon, 3 Aug 2015 21:43:33 +0000

from my presentation to CFRG: aegis = age * eyes, where age is the time avoiding attack, and eyes is effort and incentive to attack. a less mnemonic more mundane term is _mature_, or _generally agreed_.  It is one form of protection. Consider it the received wisdom of experts.

we don't trust something brand new, unless it has some kind argument related to something old with aegis, or it is the only solution to a problem, because the age is zero. we don’t trust something obscure that nobody's heard of, because the eyes are nearly zero, unless it is exceptional as above. aegis is the opposite of obscurity.

so aegis is jargon for a standard principle in crypto. If there's a better name, or if it is better for everybody to call it something different, then please let me know.

returning to signatures, I'd argue people have more incentive to attack DSA and ECDSA then Schnorr because it is a more attractive target and a more deployed algorithm. it has higher aegis. Maybe Schnorr has enough aegis, nonetheless .

By the way, I'm not counting NIST's blessing in this aegis of DSA/ECDSA, in case you're wondering. sure NIST ought to count as a few eyes, but we may want to discount it as suspended until further review.

  Original Message
From: Paul Lambert
Sent: Monday, August 3, 2015 5:09 PM
To: Dan Brown; Alexey Melnikov; [email-masked]
Subject: RE: [Cfrg] Elliptic Curves - signature: use of inversion mod the group order (ends on August 12th)

Yes - avoid inversion.

Paul

---

From: Paul Lambert <[email-masked]>
Date: Tue, 4 Aug 2015 00:57:58 +0000

Hi Dan,

Thank you for the thoughtful elaboration to my failed attempt at humor.

>from my presentation to CFRG: aegis = age * eyes, where age is the time
>avoiding attack, and eyes is effort and incentive to attack. a less
>mnemonic more mundane term is _mature_, or _generally agreed_.  It is one
>form of protection. Consider it the received wisdom of experts.
>
>we don't trust something brand new, unless it has some kind argument
>related to something old with aegis, or it is the only solution to a
>problem, because the age is zero. we don¹t trust something obscure that
>nobody's heard of, because the eyes are nearly zero, unless it is
>exceptional as above. aegis is the opposite of obscurity.
>
>so aegis is jargon for a standard principle in crypto. If there's a
>better name, or if it is better for everybody to call it something
>different, then please let me know.
>
>returning to signatures, I'd argue people have more incentive to attack
>DSA and ECDSA then Schnorr because it is a more attractive target and a
>more deployed algorithm. it has higher aegis. Maybe Schnorr has enough
>aegis, nonetheless .

Ok Š it¹s true that the Schnorr signature is only 15 years old. This seems
like plenty of time of time.

Paul

>
>By the way, I'm not counting NIST's blessing in this aegis of DSA/ECDSA,
>in case you're wondering. sure NIST ought to count as a few eyes, but we
>may want to discount it as suspended until further review.
>
>
>
>  Original Message
>From: Paul Lambert
>If you mean sponsorship or protection of ECDSA, the group already has
>strayed from the path of any form of aegis of NIST.
>

---

From: Bryan Ford <[email-masked]>
Date: Tue, 4 Aug 2015 09:58:34 +0200

> On Aug 3, 2015, at 7:36 PM, Alexey Melnikov <[email-masked]> wrote:
> 
> Dear CFRG participants,
> 
> while the other four proposals do not.

Don’t you mean “the other five proposals”?  Are you excluding from consideration for some reason the ‘edshake’ variant I proposed on July 24?  (http://www.ietf.org/mail-archive/web/cfrg/current/msg07112.html <http://www.ietf.org/mail-archive/web/cfrg/current/msg07112.html>)

> Concern has been expressed here in
> and "no" meaning "no, that's not necessary”.

Yes, we should avoid modular inversion.

Beyond the two reasons already discussed on this thread, the modular inversion precludes efficient implementation of multisignature mechanisms.  If the IETF is serious about developing protocols to decentralize trust better and rely on single points of failure, its approved signature scheme(s) should at least be designed so as not to preclude standard mechanisms to do so.

Cheers
Bryan

---

From: "Paterson, Kenny" <[email-masked]>
Date: Tue, 4 Aug 2015 13:33:13 +0000

Dear Bryan,

The deadline for proposals was July 5th. This was announced in the original email from the chairs in mid June. So, yes, we were (and are) excluding your proposal.

Cheers,

Kenny

Sent from my iPhone

On 4 Aug 2015, at 08:58, Bryan Ford <[email-masked]<mailto:[email-masked]>> wrote:

On Aug 3, 2015, at 7:36 PM, Alexey Melnikov <[email-masked]<mailto:[email-masked]>> wrote:

Dear CFRG participants,

Don't you mean "the other five proposals"?  Are you excluding from consideration for some reason the 'edshake' variant I proposed on July 24?  (http://www.ietf.org/mail-archive/web/cfrg/current/msg07112.html)

Cheers
Bryan

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Dan Brown <[email-masked]>
Date: Tue, 4 Aug 2015 15:11:58 +0000

> From: Dan Brown
> let me know off-list if you think either of the first two is worthwhile.
If I get no
> response I'll drop it.
[DB] I already got one off-list suggestion for a special case (with t=1) of
the second option of replacing s by t:u.

Because of this suggestion and the hint from the chairs that a tweak too
close to the other (Schnorr-based) proposals might not be worth considering,
I would request this tweak upon a yes majority.

I sent some emails to CFRG about this method a while back, but will send out
some details in a separate new thread ...

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 05 Aug 2015 18:57:09 +0100

On 2015-08-03 18:36, Alexey Melnikov wrote:

> Please express your views on this over the next week and a bit by 
> voting "yes" or "no" with "yes" meaning "yes, we should avoid 
> modular inversion" and "no" meaning "no, that's not necessary".

Yes.

In my eyes, modinv is an extra pain it is simpler and faster to avoid.
We can avoid it, so we should.

- -- 
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 12 Aug 2015 19:22:45 +0300

> and "no" meaning "no, that's not necessary".

"yes, we should avoid modular inversion"

IMO, the problem with inversion is that, one tends to get one of:
- Slow down the implementations quite a bit (Fermat inversion is
  simple[1], but it is SLOW).
- Increase complexity quite a bit (E.g. Euclidean inversion is
  quite a bit more complicated than Fermat, and it is still
  very noticeable timewise)
- Uses Bignum libs (E.g. problems like side channels[2] and
  truncation shift[3]).

Furthermore, the attacks "prevented" by inversions seem to either
be incredibly difficult or require extremely broken hash.

[1] E.g. Square-and-multiply with static exponent. That's even
constant-time if multiplies and squares are.

[2] If multiplication leaks, then usual blinding won't remove those
leaks.

[3] Some bignum libs export as big-endian with autotrim leading
zeros. Which if not accounted for sometimes causes numbers to get
multiplied.

-Ilari

---

From: David Jacobson <[email-masked]>
Date: Wed, 12 Aug 2015 20:52:07 -0700

On 8/12/15 9:22 AM, Ilari Liusvaara wrote:
> [email-masked]
I actually mostly agree.  But it is easy to make a multiply algorithm 
with an execution path and address path that is oblivious to the 
sensitive data.  If you have a bit of extra space so the max bignum is 
at least twice the modulus, then the garden variety Montgomery 
multiplication will never do a corrective subtract, and the instruction 
flow and address stream will be oblivious to the sensitive data.  If 
arithmetic instructions on the underlying machine are constant time, 
then you have time that is oblivious to the sensitive data.  By "garden 
variety" I mean the kind where you have word-by-bignum multiply and with 
interleaved subtraction of a multiple of the modulus so that all the 
intermediate steps are approximately reduced.  This might be true of 
other ways of doing Montgomery multiplication as well, but I've not 
thought about that.

    --David

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 13 Aug 2015 09:06:01 +0300

On Wed, Aug 12, 2015 at 08:52:07PM -0700, David Jacobson wrote:
> >
> I actually mostly agree.  But it is easy to make a multiply algorithm with
> an execution path and address path that is oblivious to the sensitive data.

Yeah, it isn't difficult do do multiply and modular reduction in constant
time (especially when difference from power-of-two is much below number
itself).

When one only has 1 addition, 1 multiplication, 1 full reduction and 2
partial reductions, it doesn't matter that much what one does, as even
quite "dumb" ways[1] are fast enough to be eclipsed by other stuff.

But when one has on order of hundred reductions (or the ~300 naive
Fermat would take) the algorithm starts mattering quite a bit.

[1] Like having multi-word integer addition, substraction and multiple
and then doing a few rounds of l+k*h or l+b-k*h, where l and h are
split parts of number. That gets it from double width to single width
in 3 rounds with curves in question.

-Ilari

---

From: David Jacobson <[email-masked]>
Date: Thu, 13 Aug 2015 08:23:45 -0700

> in 3 rounds with curves in question.
I was referring to the Montgomery multiplication algorithm as described 
in the box in section 2 of Hachez and Quisquater, "Montgomery 
Exponentiation with no Final Subtractions: Improved Results". 
http://www.uclouvain.be/crypto/services/download/publications.pdf.af0a2fc013f104e7.70646632342e706466.pdf 
.  In short, S will be the result, N the modulus and A and B values to 
be multiplied modulo N.  Lower case letters are words of the 
corresponding upper case bignum.  n'_0 is the inverse of the n_0, i.e. 
n_0 * n'_0 = 1 in "computer arithmetic".  p is the number of words.

S = 0
for i = 0 to p-1
    q_i = (s_0 + a_i * b_0) * n'_0
    S = (S + a_b * B + qi * N) >> one_word.  // The word shifted off 
will always be zero

A and B do not need to be reduced, but as long as A, B, and N all have a 
few leading zero bits, S will never be off from the reduced value by 
more than 1 * n, and you can usually skip reduction until you need to 
output a value or do a comparison, etc.  (Sorry, I don't know the exact 
conditions right now.)  This obviously makes no branches that depend on 
A or B and the address sequence is fixed. And when you do need to 
reduce, you can use clever multiplexing tricks to avoid data-dependent 
branching and to keep the address stream from depending on the data.

This has gotten into a sidetrack to the real topic which is about 
inversion.   I think blinded extended binary GCD is a bit faster than 
Fermat, but when I tried them, neither was optimized.

     --David

---

From: Alexey Melnikov <[email-masked]>
Date: Fri, 14 Aug 2015 11:44:05 +0100

> and "no" meaning "no, that's not necessary".

So there were 3 people who responded "no" and 7 people who responded 
"yes".  So chairs think that there is rough CFRG consensus for the EC 
signature scheme not to use inversion.