Subject: [Cfrg] Outline -> was Re: normative references

From: Paul Lambert <[email-masked]>
Date: Wed, 15 Jan 2014 17:38:55 -0800

Watson,

>> I’ve been trying to be helpful, but your arguments against well intended
>> suggestions is frustrating.   It’s difficult to contribute if you’re
>> arguing for a sloppy RFC because the code is the reference.
>
>I'm arguing for a precise statement of what needs to be calculated,
>and nothing else. 

Likewise … but precision of math is not the same as precision of
protocol interoperability.

Many of the precise words in the latest draft are unnecessary
from an implementation perspective. An implementor does not
need to know anything about abelian groups - just that
there are:
 - algorithm parameters (curve type and domain parameters)
 - x,y coordinate points used as input/output to
   Algorithms using the defined parameters
 - clear algorithm descriptions using just, input, output
   And domain parameters to perform a specific operation
   (point addition and point multiplication)

>That's not sloppy. And in fact I'm supplying
>what has been requested in terms of implementation details, against my
>preference for black-box standards. The next
>version is almost done in fact.

Box is still fuzzy - more suggestions:
 - make an outline to the following form:
  - Elliptic Curve Crypto Background
    (curve types and parameters)
    - Trival intro Fp and points
    Define p, order, generator, curve types
    - background on notation and other necessary functions
  - Montgomery curves
    - short overview for reference
      and pointer to other specs
      (basically - beware new math ahead)
  - Edwards curves
    - point representation
    - point addition
      Just one clear set of equations
    - point multiplication
  - Twisted Edwards curves
  - Montgomery Curves
     - point representation
     - point addition
     - multiplication
  - Cryptographic operations
    - DH
      - DH with Edwards Curve
      - DH with Montgomery Curve
    - Signature Alg(s)
      - Signature Alg with Edwards Curve
      - Montgomery Curve Signatures ...
  - Curve Catalogue
    (include curves def’s, origins, refs, strength, NUM+NUTS whatever)
     - Overview
     - Edwards
     - Twisted Edwards
     - Montgomery
  - References
 Annex
   - int to string / string to int per ANSI
     (could be up front also in intro )
   - other stuff / recomendations / math options

>
>>
>> I was pointing to specific examples that we could emulate in a perhaps
>> more simple manner.  The next step would be get a summary of the
>>relevant
>> details required and emulate one or more of these documents.
>>
>>
>>>>  ⨳|If we aren't specifying any twisted Edwards curves, why would we
>>>>  ⨳|define the formulas?
>>>>  ⨳|I suppose for use with Montgomery form, ala Ransom's suggestion.
>>>> [ ⨳]
>>>> Yes ... and why did you leave out Ed25519?       It's being used and
>>>>should at least be discussed/reviewed/
>>>
>>>It's the same as Curve25519, and not in safecurves. Let's be real
>>>clear: isogenies don't change anything substantial.
>> Substantial???
>> Curve22519 is not interoperable with Ed25519. What could be more
>> substantial.  A point on one curve would have a different x and y value
>> than a curve on the other.
>
>If I transmit to you a Curve25519 point, you can treat it as an
>Ed25519 point (after appropriate transformations) and I
>will never know the difference.
But if you do not identify that it is a Curve25519 point versus a
Ed25519 point you will not know when to do the ‘appropriate transformation’

So .. both are needed - especially if we are restricting Montgomery
Curves to DH operations … which you imply.

>Again, implementations are different
>from the results
>they calculate.
>
>> This is one of my core issues with having mathematicians write
>>protocols …
>> the apparent mathematical precision make the implementations very fuzzy.
>>
>>
>>>If you want to discuss it separately, go ahead: plenty of people have
>>>been discussing alternatives on this list already.
>> Discuss …  no, let me be clear and rephrase.  Please add Ed25519 to the
>> RFC.
>
>By Ed25519 do you mean the twisted Edwards curve, or the Edwards curve?
>Becuase
>the Ed25519 paper uses the Edwards curve, which has a giant parameter,
>and the twisted
>Edwards curve is going to be a unique form in the RFC. Either way
>there is a lot of revising to do, also
>to the explanation of why the curves were chosen.

Explaining why they were chosen should come after explain what we have.
We should document both forms of Ed25519 and give them each unique new
names.
Once named, we can chose to ignore or recommend any named curve.

>
>Do you want to basepoint that corresponds to the choice of basepoint
>9, or should I pick one?
>
>>>
>>>I'm also going to explain the Montgomery ladder and double-and-add on
>>>Edwards and that's it. RFC 6090 doesn't talk about
>>>radix-k either, nor does it explain Shamir's trick, or fun with the
>>>Brier-Joyce ladder, or w-NAF, etc.
>>>>
>>>>
>>>>  ⨳|
>>>>  ⨳|>
>>>>  ⨳|>   2) reuse where possible terminology and variables from
>>>>Weierstrass
>>>>  ⨳|ECC
>>>>  ⨳|>      E.g.  P for prime defining Fp,  n for order, h for cofactor
>>>>  ⨳|>          This would allow all classes of curves to viewed equally
>>>>in
>>>>  ⨳|>          an implementation catalog
>>>>  ⨳|>           E.g.
>>>>  ⨳|>
>>>>  ⨳|>         curveId = 'curve25519'
>>>>  ⨳|>         strength = 127
>>>>  ⨳|>         oid = None
>>>>  ⨳|>         p  = 2**255-19
>>>>  ⨳|>         a  = 486662
>>>>  ⨳|>         xG = 9
>>>>  ⨳|>         yG =
>>>>...
>>
>> ...
>>>
>>>I still don't see why this form is much better than a paragraph
>>>listing these things.
>>>
>>>>  ⨳|Also, different things should be written differently.
>>>> [ ⨳]
>>>>
>>>> On the Edwards curves with cofactors >1 I believe the strength
>>>>estimate
>>>>may be a little less
>>>> than simply taking the bit length of the size / 2
>>>>
>>>> Advice on this small adjustment would be appreciated.
>>>
>>>Size of the group generated by g, not the size of the curve.
>> Oh … of course, thanks.
>>
>>>
>>>>
>>>>
>>>>  ⨳|
>>>>  ⨳|>     Also Š long numbers should be consistently represented hex
>>>>  ⨳|versus
>>>>  ⨳|> decimal
>>>>  ⨳|
>>>>  ⨳|Why hex? Most math papers use decimal, and more importantly GP/PARI
>>>>  ⨳|doesn't accept hex.
>>>>  ⨳|MAGMA, PARI and Sage are going to be used for test vector
>>>>validation.
>>>> [ ⨳]
>>>> By you maybe ...
>>>>
>>>> Hex fits better in an RFC ...  decimal would be fine also.
>>>
>>>Six of one, half-dozen of the other.
>>>
>>>>
>>>>  ⨳|
>>>>  ⨳|>     Note also - Weierstrass Œa¹ is not the same as Edwards Œa¹,
>>>>but
>>>>  ⨳|>     can be written around Š and we should keep Edwards equations
>>>>  ⨳|consistent
>>>>  ⨳|>     where possible with literature.
>>>>  ⨳|
>>>>  ⨳|When we define DH exchange on a group yes. With setting the
>>>>parameters
>>>>  ⨳|like you did we're tempting fate.
>>>> Not really ... just another area for clear specification, eg:
>>>>
>>>> Suggested RFC text:
>>>>
>>>>     The ECC definitions include three classes of curves defined over
>>>>the field
>>>>     of integers modulo a prime p (Fp).  Each class of curve has an
>>>>equation and
>>>>     assoicated parameters unique to the class type.  Three classes of
>>>>curves
>>>>     are described:
>>>>
>>>>       SmallWeierstrassCurveFp       y**2 = x**3 + a*x + b  mod p
>>>>       EdwardsCurveFp         x**2 + y**2 = c*(1 + d*x**2 * y**2)  mod
>>>>p
>>>>       MontgomeryCurveFp             y**2 = x**3 + a*x**2 + x  mod p
>>>>
>>>>     The defintions include for each curve type:
>>>>
>>>>       curveId - An ASCII string used to identify the curve parameters
>>>>       strength - an integer providing the estimated cryptographic
>>>>strength
>>>>                  of the curve as a power of 2
>>>>       oid - a list of integers that correspond to the associated ASN.1
>>>>object
>>>>             identifier. The oid is listed as 'None' if there is no
>>>>assigned oid
>>>>       p - The prime modulus of the group (Fp). Often p is a Mersenne
>>>>prime
>>>>           to facilitate more efficient modular inversion
>>>>       xG - the x-coordinate of a generator point G for the curve
>>>>       yG - the y-coordinate of a generator point G for the curve
>>>>       n  - the order of the generator point G
>>>>       seed - included for reference when available
>>>>       h - the cofactor of the curve
>>>>
>>>>     Each curve type has the following unique parameters
>>>>
>>>>       Small Wierstrass      y**2 = x**3 + a*x + b  mod p
>>>>         a - often set to p-3 for efficiency
>>>>         b - elected for the security properties of the curve shape
>>>>         z - used by 'twisted' Brainpool curves for isogenous transform
>>>>             of untwisted curve to a curve with a = p-3
>>>>
>>>>       Montgomery            y**2 = x**3 + c*x**2 + x  mod p
>>>>         a - selected for the security properties of the curve shape
>>>>
>>>>       Edwards               x**2 + y**2 = c*(1 + d*x**2 * y**2) mod p
>>>>         c - typically set to 1 so the equation is reduced to:
>>>>                             x**2 + y**2 = 1 + d*x**2 * y**2  mod p
>>>>         d - selected for the security properties of the curve shape
>>>>
>>>> Hummm .. could add Twisted Edwards to the above
>>>
>>>But none of the curves in safecurves are presented in twisted Edwards
>>>form,
>>>I'm not going to rehash short Weierstrass here, (RFC 6090 already
>>>exists).
>>
>> Ok … but introducing Weierstrass allows comparisons and clarity of
>> specification.
>> No eed to fully define Weierstrass … it’s just easier to have a complete
>> view
>> of all options.
>
>Unless I include operation counts and real timings from optimized code,
>that
>won't be a complete guide to the choice to make. Look at eBATS for
>performance
>info.

My point above on Weierstrass was for clarity of implementation.  The
parameters have names (like ‘a’).  NIST curves have an ‘a’ that is
different
from the usage in Montgomery curves.  You simply need to show both
equations
and define what an ‘a’ means in each context (text already provided to
you).

That was the point of an early discourse on these being ‘new’ curves.

>
>RFC's are standards, not how to guides for the terminally lazy.

Sigh …   

>>
>> Paul
>>
>>
>>>
>>>Anyway, I think this conversation would be far more productive when I
>>>finish the revisions and put it before
>>>the group again. You can follow on github in between.
>>>
>>>>
>>>>  ⨳|
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|>   3) Use math representation in RFCs that maps directly to a
>>>>  ⨳|computer
>>>>  ⨳|>      language notation - Python would be a good choice for
>>>>  ⨳|>      readability.
>>>>  ⨳|>      E.g. Twisted Edwards point addition definition
>>>>  ⨳|>
>>>>  ⨳|>        x3 = ((x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)) % p
>>>>  ⨳|>        y3 = ((y1*y2-a*x1*x2) * inv(1-d*x1*x2*y1*y2)) % p
>>>>  ⨳|
>>>>  ⨳|The math notation I am using maps directly to that of most CAS
>>>> [ ⨳]
>>>> No - for example:
>>>> " On Montgomery curves, curves of the form y^2=x^3+Ax^2+x, the
>>>>typical"
>>>> is Ax a variable 'Ax' or A*x ... this is sloppy non-parseable notation
>>>
>>>>  ⨳|systems. Anyway, at some point I will be done with the major
>>>>revision,
>>>>  ⨳|and kick it around for comments.
>>>> [ ⨳]
>>>> CAS???
>>>> I prefer running code useable for a protocol implementation.
>>>
>>>So I can just copy the relevant parts of tweetnacl.c and be done with
>>>it?
>>>
>>>>
>>>> Paul
>>>>
>>>>  ⨳|
>>>>  ⨳|>
>>>>  ⨳|>    4) curve names need consolidation and should clearly indicate
>>>>  ⨳|curve
>>>>  ⨳|> type
>>>>  ⨳|
>>>>  ⨳|Blame Tanja. I really do not like the idea of changing existing
>>>>names
>>>>  ⨳|especially when referring people to papers with them. SEC/NIST has
>>>>  ⨳|already caused enough confusing as it is.
>>>> [ ⨳]
>>>> No need to blame, just make the change but  include reference to
>>>>original author and curve name.
>>>> NIST did not add confusion ... just branded the results.
>>>> CFRG branding would be valuable.  More curves will happen and  a
>>>>consistent notation is a good thing.
>>>
>>>What do you propose for the name scheme? E,M with prime in the expc
>>>format is my best proposal, but this might not be unique all the time.
>>>>
>>>> Paul
>>>>
>>>>  ⨳|
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|> Paul
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|>
>>>>  ⨳|> >
>>>>  ⨳|> >David
>>>>  ⨳|> >
>>>>  ⨳|> >>
>>>>  ⨳|> >> Thanks,
>>>>  ⨳|> >>     Yaron
>>>>  ⨳|> >>
>>>>  ⨳|> >> _______________________________________________
>>>>  ⨳|> >> Cfrg mailing list
>>>>  ⨳|> >> [email-masked]
>>>>  ⨳|> >> http://www.irtf.org/mailman/listinfo/cfrg
>>>>  ⨳|> >>
>>>>  ⨳|> >
>>>>  ⨳|> >_______________________________________________
>>>>  ⨳|> >Cfrg mailing list
>>>>  ⨳|> >[email-masked]
>>>>  ⨳|> >http://www.irtf.org/mailman/listinfo/cfrg
>>>>  ⨳|>
>>>>  ⨳|> _______________________________________________
>>>>  ⨳|> Cfrg mailing list
>>>>  ⨳|> [email-masked]
>>>>  ⨳|> http://www.irtf.org/mailman/listinfo/cfrg
>>>
>>>
>>>
>>>--
>>>"Those who would give up Essential Liberty to purchase a little
>>>Temporary Safety deserve neither  Liberty nor Safety."
>>>-- Benjamin Franklin
>>
>
>
>
>-- 
>"Those who would give up Essential Liberty to purchase a little
>Temporary Safety deserve neither  Liberty nor Safety."
>-- Benjamin Franklin

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Jan 2014 18:15:09 -0800

> protocol interoperability.

If we merely needed to define the protocol to be interoperable, then
"big endian x coordinate of points on y^2=x^3+486662x^2+x over
GF(2^255-19) with Diffie-Hellman packed to 32 bytes with leading 0,
basepoint x coordinate 9" would
completely define the protocol.

What you are asking for is guidance on implementations, which I've
added significant amounts of. Let's not confuse
normative with informative.

>    (point addition and point multiplication)

I think we have that in this draft: even a pseudocode outline of the
ladder/double and add method.

Are there specific aspects of the explicit formulas and the text
around them that you think need clarification?

> Box is still fuzzy - more suggestions:

Do you have specific comments about where there is ambiguity?

>  - make an outline to the following form:
i.e. the form of RFC 6090. I'll think about that for a few days and
see if it gets
advantages in comprehension that my current draft could never get.

>       - DH with Montgomery Curve

Signatures are going separately.

>       - Montgomery Curve Signatures ...

If you have a method that will work on a Montgomery curve naturally I
would love to hear it.

Montgomery curves are here for their blazing speed in ECDH without large tables.
Edwards curves are here for their blazing speed in signatures where we
can't toss out
one coordinate. I'ld much rather use Montgomery for ECDH and Edwards
for signatures
than Edwards for everything.

> Curves to DH operations … which you imply.

Well, there are Edwards curves of about the same size. I've put it in because I
take your point: we do need something that has a strongly unified
complete addition law
with that size that can be used for signatures.

The only way I know of to use Montgomery curves for signatures loses
the extreme speed.

As for the transformation, if I tell you that protocol x uses
Curve25519 ECDH, I hopefully
have told you enough to know exactly what will be sent, regardless of what
you chose to do to think about it. Anything in the draft that makes that
not the case is a major issue.

> Once named, we can chose to ignore or recommend any named curve.

The argument for doing this can be extended to the twists of every
curve in the draft already....
I vote for putting in T25519, not the Ed25519 curve, because the small
parameters are much faster.
Yes, you can use an isomorphism to get the speed back, but I don't
like typing giant numbers any more
then you do, and if everyone is going to be using the isomorphism, why
stick with the original curve.

>>Do you want to basepoint that corresponds to the choice of basepoint
<snip>
> That was the point of an early discourse on these being ‘new’ curves.

I'm having trouble visualizing why putting in the short Weierstrass form here
helps an implementor understand what the document says about Montgomery and
Edwards curves.

<rest omitted>
Sincerely,
Watson Ladd

---

From: Paul Lambert <[email-masked]>
Date: Wed, 15 Jan 2014 22:42:32 -0800

>If you have a method that will work on a Montgomery curve naturally I

That’s the point of having the section … you need a section to say it
is not a good idea… or transform or whatever.

>than Edwards for everything.

Again the point of the outline was to provide a framework to possibly make
such recommendations.

These all seem like severe issues with these new curves.  The Weierstrass
curves
work well for signatures and key establishment.

A truly ‘unified' public key system would support both signatures and key
establishment
with the same key.

>not the case is a major issue.

… And if you are using Ed25519a or Ed25519b you also need to identify the
curve.

>helps an implementor understand what the document says about Montgomery

You simply need to put the new curves in the context of the old.
No need to describe everything about them since they are well known.
They should be mentioned to show that the math is not the same.
The outline provided a section to briefly mention the old to introduce the
new.

Paul

---

From: Yoav Nir <[email-masked]>
Date: Thu, 16 Jan 2014 07:07:50 +0000

> completely define the protocol.

And just to be on the safe side, it's best to also add a numerical example: an x and y in numerical form and then encoded as on the network.

We usually craft RFCs so as to be understandable to implementers in general, which could be fresh comp-sci or software engineering graduates who have never taken a cryptography course, and who have never programmed in a low enough level to consider endianness. No, you don't have to explain asymmetric crypto - they can look it up, but you should not assume any deeper knowledge than there is in the relevant wikipedia article.

That should be the assumption for a crypto document. Consider yourself lucky. Some documents need to be understood by the "teach yourself Javascript in 21 days" crowd.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 07:33:12 -0800

> A truly ‘unified' public key system would support both signatures and key

ECDH with Edwards is still extremely fast, and if you have devices with code
size limitations, is a fine way to fit signatures and ECDH into a limited space.
However, there is a mandatory check of the square root when decompressing
points that must take place, and whose omission harms security without affecting
interoperability. I'll add text explaining this more clearly.

As for same key, I'm not an expert on the security implications of key reuse.
So far the draft is silent on this issue, and I don't feel capable of
saying anything
about it.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Thu, 16 Jan 2014 19:42:40 +0000

Paul Lambert 
On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:

> 
> A truly ‘unified' public key system would support both signatures and
> key establishment with the same key.
>

Received wisdom is that using the same key for both key establishment and
signatures is a bad idea.  I believe the concern is that one protocol 
might be used an Oracle to subvert the other.

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 12:10:35 -0800

Hi Kevin,

⨳|> A truly ‘unified' public key system would support both signatures
 ⨳|and
 ⨳|> key establishment with the same key.
 ⨳|>
 ⨳|
 ⨳|Received wisdom is that using the same key for both key establishment
 ⨳|and signatures is a bad idea.  I believe the concern is that one
 ⨳|protocol might be used an Oracle to subvert the other.
[ ⨳]
Yes - greatly appreciate the transfer of wisdom.  General guidelines are well documented to this effect.

This makes complete sense in the general case where a curve may support generic  key establishment or signature algorithms.

However, for specifically selected signature and key establishment methods I would assume that and examination could be made of this potential subversion.  The general guideline seems to be blocking the examination and evaluation of the sensitivity of such combined modes.

As a protocol designer, being able to use the same key for signatures and key establishment makes for a simpler design and trust model.  The session key security (e.g. from ECDH) would be implicitly bound to the any signed information from the same key.  

I is possible to just consider a combined public key that is the concatenation of two types ... but then you need another mechanism to validate the binding.  Right now if you have two public keys Pe and Ps (public to sign and public to encrypt) This would be P = Pe|Ps ( concatenated).  Binding could through and be Id = h(P)=h(Pe|Ps) or 
Ps signing Pe, etc.

Still ... it doubles the effective required key size and adds additional steps in an authenticated key exchange.

Thanks,

Paul

---

From: David McGrew <[email-masked]>
Date: Thu, 16 Jan 2014 15:30:51 -0500

Hi Kevin, Paul, and Watson,

> might be used an Oracle to subvert the other.

Agreed on that point, but there is a background issue here that I want 
to ask about.

Watson said in a previous email:
 > Edwards curves are here for their blazing speed in signatures where 
we can't toss out
 > for signatures than Edwards for everything.

So, what would this mean for an implementation that uses both ECDH and 
an EC signature?   That the math routines for both Edwards and 
Montgomery need to be included?    Or is translation between the formats 
very efficient?  If a single curve type and a single set of 
math/algorithms could be used for both, then an implementation could be 
simpler and more compact, and could perform better in software.

In any case, it makes sense to consider a complete system, rather than 
to optimize ECDH in isolation, and optimize a signature method in 
isolation.

David

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 16 Jan 2014 12:44:08 -0800

On Jan 16, 2014, at 12:30 PM, David McGrew <[email-masked]> wrote:

> > Edwards curves are here for their blazing speed in signatures where we can't toss out
> So, what would this mean for an implementation that uses both ECDH and an EC signature?   That the math routines for both Edwards and Montgomery need to be included?    Or is translation between the formats very efficient?  If a single curve type and a single set of math/algorithms could be used for both, then an implementation could be simpler and more compact, and could perform better in software.

It is preferable to include both formats.  It is possible to use Edwards for ECDH or Montgomery for signatures, but it is not ideal speedwise.  Anyway, whereas Montgomery implementations can be extremely simple, Edwards implementations are usually significantly more complex (because they need complexity to extract maximum performance, unlike the Montgomery ladder).  For curves larger than 256 bits, authors probably won’t inline their multiplication formulas into their laddering, so I don’t think the extra formulas will hurt much.

Conversion hurts Montgomery curves more than it hurts Edwards curves, so it might make sense to use only Montgomery form for the wire format.  The conversion adds non-negligible complexity, though, especially because fast conversion routines may vary between curves.

On the other hand, if the wire format is Montgomery, then a *really* space-constrained device could use Montgomery for signatures as well as ECDH without too much pain.

> David

Cheers,
— Mike

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 12:57:49 -0800

On Thu, Jan 16, 2014 at 12:30 PM, David McGrew <[email-masked]> wrote:
> Agreed on that point, but there is a background issue here that I want to
> ask about.
>
> So, what would this mean for an implementation that uses both ECDH and an EC
> signature?   That the math routines for both Edwards and Montgomery need to
> be included?    Or is translation between the formats very efficient?  If a
> single curve type and a single set of math/algorithms could be used for
> both, then an implementation could be simpler and more compact, and could
> perform better in software.

Edwards curves can be used for ECDH and outperform short Weierstrass
over the same
field, so one could use ECDH on an Edwards curve along with
signatures. The one issue
is there is a critical check Edwards curves require that Montgomery
curves do not when
receiving points.

Mike Hamburg pointed out there are clever tricks to do signatures on
Montgomery curves, but they are still
slower than variable time radix k algorithms on Edwards curves
signature verification.

You can use an isogeny to take advantage of the radix-k algorithms in
Edwards curves for
points on a Montgomery curve: this is why T25519 is in the latest
version (along with tons of typos,
and some point checks need to be performed on it, and I've not
documented the algorithm yet)
Right now this is faster for ECDH, but with better differential-addition
chains Montgomery will be back on top. And there is that special check
which makes me worry about poor quality implementations:
send an invalid Edwards encoding, and things can go badly wrong.

>
> In any case, it makes sense to consider a complete system, rather than to
> optimize ECDH in isolation, and optimize a signature method in isolation.

On big servers and clients cold code size is really not an issue:
provided your inner loop and the data it accesses fit in L1, all is
good, so
Montgomery and Edwards make sense to get an extra little bit of
performance. On tiny systems with enough RAM for high performance
Edwards implementations, one could use the Edwards curves. If get
smaller you will lose performance to Edwards curves vs. Montgomery,
but as Mike Hamburg points out in an email below there are special
tricks that can be played.

For a small system I would stick with Edwards: the loss of robustness
might be worth the smaller code size. However, other people might
disagree,
and as new performance tricks come out this could change.
Unfortunately eBATS doesn't include a MSP430, so I really don't know
what life is like
down there.

>From just a pragmatic perspective, people want to use both: the TLS
people want Curve25519 yesterday on top of whatever signature schemes
are lying around already (RSA PKCS 1.5 (blegh!), ECDSA, etc.), while
people who want to verify lots of signatures very quickly want Edwards
curves.
I don't feel confident enough in my knowledge of what will work best
to remove the option of having both from protocol designers.

Sincerely,
Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 13:16:49 -0800

> However, for specifically selected signature and key establishment methods I would assume that and examination could be made of this potential subversion.  The general guideline seems to be blockin…

Signcryption has been an area of research. I think what you want is to
use the same private and public key for multiple purposes.
> As a protocol designer, being able to use the same key for signatures and key establishment makes for a simpler design and trust model.  The session key security (e.g. from ECDH) would be implicitl…

If I understand correctly you want to use something like HMQV with
keys that can be used in a signature scheme, thus saying "The person I
share key X with is the person who signed messages M_1,\ldots M_n".
This can be done by having a master key sign a key exchange key and a
message signing key. However, people can sign whatever messages they
feel like, so I don't know how helpful the semantics are.

> Still ... it doubles the effective required key size and adds additional steps in an authenticated key exchange.

The key exchange and PKIX we have now works with this restriction just
fine. The naive solution I mentioned above doesn't require
any extra rounds, just some more data. Yes, it is sort of a pain in
highly restricted environments, but I'm having trouble thinking
of a highly restricted environment with lots of public key ops taking
place that need those semantics.
It's never going to amount to a high percentage of the load anyway.
> Paul

Sincerely,
Watson

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 13:55:08 -0800

⨳|The key exchange and PKIX we have now works with this restriction just
 ⨳|fine. [ ⨳] 

PKIX does not work well ... and it will not be used for my applications.
When was the last time you used a PKI based key to encrypt something?

I'm building consumer equipment that needs a simple enrollment and trust model.  We will have public keys embedded in a wide range of devices (large and small).  The enrollment process may include the presentation of a public key in machine readable form (e.g. QR code). Smaller is better.  PKI and any naming hierarchy is an unnecessary burden.  Human validation of visual information is a fall-back for the device introduction process.

Initial setup is Static and/or ephemeral DH based, signatures later required. 

[ ⨳] >The naive solution I mentioned above doesn't require any extra
 ⨳|rounds, just some more data. Yes, it is sort of a pain in highly
 ⨳|restricted environments, but I'm having trouble thinking of a highly
 ⨳|restricted environment with lots of public key ops taking place that
 ⨳|need those semantics.
[ ⨳] 
It's not the size restriction or speed that is an issue. I'm looking at making the 'trust chain' simpler.  It is not a critical mechanism ... but it would make the overall presentation of chains of related keys easier.  

Signature authenticated DH is an extra couple of steps but is viable. Key 'trust statements' just require an extra level of abstraction.

Will be proceeding with a multi key model ... unless I can find a well vetted single key algorithm suite.  That's why I'm asking here....   

Paul

 ⨳|It's never going to amount to a high percentage of the load anyway.
 ⨳|>
 ⨳|> Thanks,
 ⨳|>
 ⨳|> Paul
 ⨳|
 ⨳|Sincerely,
 ⨳|Watson
 ⨳|>
 ⨳|>
 ⨳|
 ⨳|
 ⨳|
 ⨳|--
 ⨳|"Those who would give up Essential Liberty to purchase a little
 ⨳|Temporary Safety deserve neither  Liberty nor Safety."
 ⨳|-- Benjamin Franklin

---

From: Rene Struik <[email-masked]>
Date: Thu, 16 Jan 2014 17:31:23 -0500

Hi Paul et al:

A counter example in practice to the "received wisdom" not to reuse 
public keys both for key agreement and non-repudiation is during 
certification requests, when the key to be certified is to be used for 
uses including key agreement and where the request is signed.

[see also NIST SP 800-56a-2013, Section 5.6.3.2, item #5:
A static key pair may be used in more than one key-establishment scheme. 
However, one static public/private key pair shall not be used for 
different purposes (for example, a digital signature key pair is not to 
be used for key establishment or vice versa) with the following possible 
exception: when requesting the (initial) certificate for a public static 
key-establishment key, the key-establishment private key associated with 
the public key may be used to sign the certificate request. See SP 
800-57, Part 1 on Key Usage for further information.
]

While key separation seems prudent, it is not entirely clear (to me) 
whether the conditions under which this is required are precisely known 
(even in the above-mentioned case of signed certificate requests).

Best regards, Rene

On 1/16/2014 3:30 PM, David McGrew wrote:
> [snip]

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 14:37:27 -0800

Hi Rene,

 ⨳|-----Original Message-----
 ⨳|From: Rene Struik [mailto:[email-masked]]
 ⨳|Sent: Thursday, January 16, 2014 2:31 PM
 ⨳|To: David McGrew; Igoe, Kevin M.; Paul Lambert; Watson Ladd
 ⨳|Cc: Yaron Sheffer; [email-masked]
 ⨳|Subject: Keys for multiple cryptographic uses (was: Re: [Cfrg] Outline
 ⨳|-> was Re: normative references)
 ⨳|
 ⨳|Hi Paul et al:
 ⨳|
 ⨳|A counter example in practice to the "received wisdom" not to reuse
 ⨳|public keys both for key agreement and non-repudiation is during
 ⨳|certification requests, when the key to be certified is to be used for
 ⨳|uses including key agreement and where the request is signed.
 ⨳|
 ⨳|[see also NIST SP 800-56a-2013, Section 5.6.3.2, item #5:
 ⨳|A static key pair may be used in more than one key-establishment
 ⨳|scheme.
 ⨳|However, one static public/private key pair shall not be used for
 ⨳|different purposes (for example, a digital signature key pair is not
 ⨳|to be used for key establishment or vice versa) with the following
 ⨳|possible
 ⨳|exception: when requesting the (initial) certificate for a public
 ⨳|static key-establishment key, the key-establishment private key
 ⨳|associated with the public key may be used to sign the certificate
 ⨳|request. See SP 800-57, Part 1 on Key Usage for further information.
 ⨳|]
 ⨳|
 ⨳|While key separation seems prudent, it is not entirely clear (to me)
 ⨳|whether the conditions under which this is required are precisely
 ⨳|known (even in the above-mentioned case of signed certificate
 ⨳|requests).[ ⨳] 

Yes - exactly!   Caution is good ... but once this guidance was set down we have not bothered to investigate deeply which algorithm combinations are secure for mixed use. 

Additional wisdom on where specific Oracle exist would be very informative.

Thanks,

Paul

 ⨳|
 ⨳|Best regards, Rene
 ⨳|
 ⨳|
 ⨳|On 1/16/2014 3:30 PM, David McGrew wrote:
 ⨳|> Hi Kevin, Paul, and Watson,
 ⨳|>
 ⨳|> On 01/16/2014 02:42 PM, Igoe, Kevin M. wrote:
 ⨳|>> Paul Lambert
 ⨳|>> On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:
 ⨳|>>
 ⨳|>>> A truly ‘unified' public key system would support both signatures
 ⨳|>>> and key establishment with the same key.
 ⨳|>>>
 ⨳|>> Received wisdom is that using the same key for both key
 ⨳|establishment
 ⨳|>> and signatures is a bad idea.  I believe the concern is that one
 ⨳|>> protocol might be used an Oracle to subvert the other.
 ⨳|>
 ⨳|> Agreed on that point, but there is a background issue here that I
 ⨳|want
 ⨳|> to ask about.
 ⨳|>
 ⨳|> [snip]
 ⨳|
 ⨳|
 ⨳|--
 ⨳|email: [email-masked] | Skype: rstruik
 ⨳|cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 16 Jan 2014 22:57:09 +0000

Hi

There is significant *scientific* literature on the question of security
of multiple uses of keys - both for the setting where the same key is used
in more than one algorithm of the same type (under the name of
cryptographic agility) and where the same key is used in algorithms of
different types (e.g. same key in a signature scheme and in a public key
encryption scheme).

Cautionary examples include:

T. Jager, K.G. Paterson and J. Somorovsky, One Bad Apple: Backwards
Compatibility Attacks on State-of-the-Art Cryptography. In Network and
Distributed System Security Symposium (NDSS 2013).
http://www.isg.rhul.ac.uk/~kp/BackwardsCompatibilityAttacks.pdf

J.P. Degabriele, A. Lehmann, K.G. Paterson, N.P. Smart and M. Strefler, On
the Joint Security of Encryption and Signature in EMV. In O. Dunkelmann
(ed.), CT-RSA 2012, Lecture Notes in Computer Science Vol. 7178, pp.
116-135, Springer, 2012. Full version at: http://eprint.iacr.org/2011/615

Positive (and some negative) results can be found in:

K.G. Paterson, J.C.N. Schuldt, M. Stam and S. Thomson, On the Joint
Security of Encryption and Signature, Revisited. In D.H. Lee and X. Wang
(eds.), ASIACRYPT 2011, Lecture Notes in Computer Science Vol. 7073, pp.
161-178, Springer, 2011. Full version at http://eprint.iacr.org/2011/486

Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic agility and
its relation to circular encryption.
In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403{422.
Springer, Heidelberg (2010)

Coron, J.S., Joye, M., Naccache, D., Paillier, P.: Universal padding
schemes for RSA. In: Yung, M. (ed.)
CRYPTO 2002. LNCS, vol. 2442, pp. 226{241. Springer, Heidelberg (2002)

Haber, S., Pinkas, B.: Securely combining public-key cryptosystems. In:
ACM Conference on Computer and
Communications Security. pp. 215{224 (2001)

This list is by no means complete, but serves to illustrate that the
picture is complicated and we are far from having a full understanding of
this domain. Several additional references can be found in the
first-mentioned paper above.

Finally, let me draw your attention to this very recent paper which
highlights the issues arising from multiple key usage in the context of
TLS:

Karthikeyan Bhargavan, Cedric Fournet, Markulf Kohlweiss, Alfredo Pironti,
Pierre-Yves Strub, and Santiago Zanella-Beguelin. Proving the TLS
Handshake Secure (as it is).
https://www.mitls.org/downloads/Proving_the_TLS_Handshake.pdf

Happy reading.

Cheers

Kenny

On 16/01/2014 17:37, "Paul Lambert" <[email-masked]> wrote:

>Yes - exactly!   Caution is good ... but once this guidance was set down
>we have not bothered to investigate deeply which algorithm combinations
>are secure for mixed use.
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Rene Struik <[email-masked]>
Date: Thu, 16 Jan 2014 19:42:34 -0500

Hi Kenny:

Another useful reference is the Indocrypt2009 paper "Reusing Static Keys 
in Key Agreement Protocols" by Sanjit Chatterjee, Alfred Menezes, and 
Berkant Ustaoglu. This being said, it seems you concur that the picture 
is complicated and that the precise conditions under which key 
separation is required are not exactly known (my original note to Paul 
Lambert's practical question [and discussed as motivation in your 
2011-486 ePrint]).

Best regards, Rene

---

From: Greg Rose <[email-masked]>
Date: Thu, 16 Jan 2014 17:18:44 -0800

The same key is used in GSM phones no matter which A5 algorithm is used. The algorithm can change with base stations. Two of the algorithms are breakable in real time (i.e. quickly enough not to break the connection).

Greg.

>> ⨳|cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

Greg.

Phone: +1 619 890 8236 
secure voice / text: Seecrypt +28131139047 (referral code 54smjs if you want to try it).
PGP: 09D3E64D 350A 797D 5E21 8D47 E353 7566 ACFB D945 (id says [email-masked], but don’t use that email)

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 18:53:54 -0800

Kenny,

Many thanks for the references!

These show a clear path forward to joint key usage with ECC and ECIES!

Do you have any opinions or results (+ or -) on ECDH?

]On Jan 16, 2014, at 14:57 , Paterson, Kenny <[email-masked]>
]wrote:
]
]> Hi
]>
]> There is significant *scientific* literature on the question of
]> security of multiple uses of keys - both for the setting where the
]> same key is used in more than one algorithm of the same type (under
]> the name of cryptographic agility) and where the same key is used in
]> algorithms of different types (e.g. same key in a signature scheme and
]> in a public key encryption scheme).
]>
]> Cautionary examples include:
]>
]> T. Jager, K.G. Paterson and J. Somorovsky, One Bad Apple: Backwards
]> Compatibility Attacks on State-of-the-Art Cryptography. In Network and
]> Distributed System Security Symposium (NDSS 2013).
]> http://www.isg.rhul.ac.uk/~kp/BackwardsCompatibilityAttacks.pdf

This shows RSA is dangerous for a particular joint use ...
  In the public key setting, we focus on
  RSA encryption and signatures, showing a BC attack on
  RSA-OAEP when it is used in conjunction with an imple-
  mentation of PKCS#1v1.5 encryption that is vulnerable to
  Bleichenbacher’s attack [13]. We also remark that a sig-
  nature forgery attack is possible under the same circum-
  stances; here we require the same RSA key to be allowed
  for use in both encryption and signature algorithms
]>
]>
]> J.P. Degabriele, A. Lehmann, K.G. Paterson, N.P. Smart and M.
]> Strefler, On the Joint Security of Encryption and Signature in EMV. In
]> O. Dunkelmann (ed.), CT-RSA 2012, Lecture Notes in Computer Science
]Vol. 7178, pp.
]> 116-135, Springer, 2012. Full version at:
]> http://eprint.iacr.org/2011/615

RSA Signature Forgery possible in EMV schemes
ECIES and EC-Schnorr shown secure: 
    More specifically, we prove that the ECIES encryption scheme 
    and the EC-Schnorr signature scheme are jointly secure 
    in the Random Oracle Model, and that ECIES and the 
    EC-DSA signature scheme are jointly secure in the 
    Generic Group Model (GGM). Such results are the best 
    that we can currently hope for, given the state of 
    the art in analyzing ECC signature schemes.

]>
]>
]> Positive (and some negative) results can be found in:
]>
]> K.G. Paterson, J.C.N. Schuldt, M. Stam and S. Thomson, On the Joint
]> Security of Encryption and Signature, Revisited. In D.H. Lee and X.
]> Wang (eds.), ASIACRYPT 2011, Lecture Notes in Computer Science Vol.
]7073, pp.
]> 161-178, Springer, 2011. Full version at
]> http://eprint.iacr.org/2011/486

Interesting ...
   Extending the ideas of a combined public key 
   scheme, we show how to construct a signcryption 
   scheme which enables a user to use a single keypair 
   for both sender and receiver roles, and which furthermore 
   allows ecient instantiations with short public keys in the standard model

Paul

]>
]>
]>
]> Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic agility
]> and its relation to circular encryption.
]> In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403{422.
]> Springer, Heidelberg (2010)
]>
]> Coron, J.S., Joye, M., Naccache, D., Paillier, P.: Universal padding
]> schemes for RSA. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp.
]> 226{241. Springer, Heidelberg (2002)
]>
]> Haber, S., Pinkas, B.: Securely combining public-key cryptosystems.
]In:
]> ACM Conference on Computer and
]> Communications Security. pp. 215{224 (2001)
]>
]>
]>
]>
]>
]> This list is by no means complete, but serves to illustrate that the
]> picture is complicated and we are far from having a full understanding
]> of this domain. Several additional references can be found in the
]> first-mentioned paper above.
]>
]> Finally, let me draw your attention to this very recent paper which
]> highlights the issues arising from multiple key usage in the context
]> of
]> TLS:
]>
]> Karthikeyan Bhargavan, Cedric Fournet, Markulf Kohlweiss, Alfredo
]> Pironti, Pierre-Yves Strub, and Santiago Zanella-Beguelin. Proving the
]> TLS Handshake Secure (as it is).
]> https://www.mitls.org/downloads/Proving_the_TLS_Handshake.pdf
]>
]>
]> Happy reading.
]>
]> Cheers
]>
]> Kenny
]>
]> On 16/01/2014 17:37, "Paul Lambert" <[email-masked]> wrote:
]>
]>> Hi Rene,
]>>
]>> ⨳|-----Original Message-----
]>> ⨳|From: Rene Struik [mailto:[email-masked]]
]>> ⨳|Sent: Thursday, January 16, 2014 2:31 PM
]>> ⨳|To: David McGrew; Igoe, Kevin M.; Paul Lambert; Watson Ladd
]>> ⨳|Cc: Yaron Sheffer; [email-masked]
]>> ⨳|Subject: Keys for multiple cryptographic uses (was: Re: [Cfrg]
]>> Outline ⨳|-> was Re: normative references) ⨳| ⨳|Hi Paul et al:
]>> ⨳|
]>> ⨳|A counter example in practice to the "received wisdom" not to reuse
]>> ⨳|public keys both for key agreement and non-repudiation is during
]>> ⨳|certification requests, when the key to be certified is to be used
]>> for ⨳|uses including key agreement and where the request is signed.
]>> ⨳|
]>> ⨳|[see also NIST SP 800-56a-2013, Section 5.6.3.2, item #5:
]>> ⨳|A static key pair may be used in more than one key-establishment
]>> ⨳|scheme.
]>> ⨳|However, one static public/private key pair shall not be used for
]>> ⨳|different purposes (for example, a digital signature key pair is
]>> not ⨳|to be used for key establishment or vice versa) with the
]>> following ⨳|possible
]>> ⨳|exception: when requesting the (initial) certificate for a public
]>> ⨳|static key-establishment key, the key-establishment private key
]>> ⨳|associated with the public key may be used to sign the certificate
]>> ⨳|request. See SP 800-57, Part 1 on Key Usage for further
]information.
]>> ⨳|]
]>> ⨳|
]>> ⨳|While key separation seems prudent, it is not entirely clear (to
]>> me) ⨳|whether the conditions under which this is required are
]>> precisely ⨳|known (even in the above-mentioned case of signed
]>> certificate ⨳|requests).[ ⨳]
]>>
]>> Yes - exactly!   Caution is good ... but once this guidance was set
]down
]>> we have not bothered to investigate deeply which algorithm
]>> combinations are secure for mixed use.
]>>
]>> Additional wisdom on where specific Oracle exist would be very
]>> informative.
]>>
]>> Thanks,
]>>
]>> Paul
]>>
]>>
]>> ⨳|
]>> ⨳|Best regards, Rene
]>> ⨳|
]>> ⨳|
]>> ⨳|On 1/16/2014 3:30 PM, David McGrew wrote:
]>> ⨳|> Hi Kevin, Paul, and Watson,
]>> ⨳|>
]>> ⨳|> On 01/16/2014 02:42 PM, Igoe, Kevin M. wrote:
]>> ⨳|>> Paul Lambert
]>> ⨳|>> On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:
]>> ⨳|>>
]>> ⨳|>>> A truly ‘unified' public key system would support both
]>> signatures ⨳|>>> and key establishment with the same key.
]>> ⨳|>>>
]>> ⨳|>> Received wisdom is that using the same key for both key
]>> ⨳|establishment ⨳|>> and signatures is a bad idea.  I believe the
]>> concern is that one ⨳|>> protocol might be used an Oracle to subvert
]>> the other.
]>> ⨳|>
]>> ⨳|> Agreed on that point, but there is a background issue here that I
]>> ⨳|want ⨳|> to ask about.
]>> ⨳|>
]>> ⨳|> [snip]
]>> ⨳|
]>> ⨳|
]>> ⨳|--
]>> ⨳|email: [email-masked] | Skype: rstruik
]>> ⨳|cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
]>>
]>> _______________________________________________
]>> Cfrg mailing list
]>> [email-masked]
]>> http://www.irtf.org/mailman/listinfo/cfrg
]>
]> _______________________________________________
]> Cfrg mailing list
]> [email-masked]
]> http://www.irtf.org/mailman/listinfo/cfrg
]
]
]Greg.
]
]Phone: +1 619 890 8236
]secure voice / text: Seecrypt +28131139047 (referral code 54smjs if you
]want to try it).
]PGP: 09D3E64D 350A 797D 5E21 8D47 E353 7566 ACFB D945 (id says
][email-masked], but don’t use that email)

---

From: Watson Ladd <[email-masked]>
Date: Thu, 16 Jan 2014 18:56:41 -0800

> Do you have any opinions or results (+ or -) on ECDH?

Given what ECIES consists of this should imply ECDH+E-Schnorr works,
but I would not be surprised
if this turns out a bit differently. I'll have to reread the Schnorr
proof to think if the reduction can still work
with an ECDH oracle.
Sincerely,
Watson Ladd

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 19:18:04 -0800

]-----Original Message-----
]From: Paul Lambert
]Sent: Thursday, January 16, 2014 6:54 PM
]To: Paterson, Kenny
]Cc: Rene Struik; David McGrew; Igoe, Kevin M.; Watson Ladd; Yaron
]Sheffer; [email-masked]; 'Greg Rose'
]Subject: RE: [Cfrg] Keys for multiple cryptographic uses (was: Re:
]Outline -> was Re: normative references)
]
]
]Kenny,
]
]Many thanks for the references!
]
]These show a clear path forward to joint key usage with ECC and ECIES!
]
]Do you have any opinions or results (+ or -) on ECDH?
Specifically static ECDH ...

]
]
]]On Jan 16, 2014, at 14:57 , Paterson, Kenny <[email-masked]>
]]wrote:
]]
]]> Hi
]]>
]]> There is significant *scientific* literature on the question of ]>
]security of multiple uses of keys - both for the setting where the ]>
]same key is used in more than one algorithm of the same type (under ]>
]the name of cryptographic agility) and where the same key is used in ]>
]algorithms of different types (e.g. same key in a signature scheme and
]]> in a public key encryption scheme).
]]>
]]> Cautionary examples include:
]]>
]]> T. Jager, K.G. Paterson and J. Somorovsky, One Bad Apple: Backwards
]]> Compatibility Attacks on State-of-the-Art Cryptography. In Network
]and ]> Distributed System Security Symposium (NDSS 2013).
]]> http://www.isg.rhul.ac.uk/~kp/BackwardsCompatibilityAttacks.pdf
]
]This shows RSA is dangerous for a particular joint use ...
]  In the public key setting, we focus on
]  RSA encryption and signatures, showing a BC attack on
]  RSA-OAEP when it is used in conjunction with an imple-
]  mentation of PKCS#1v1.5 encryption that is vulnerable to
]  Bleichenbacher’s attack [13]. We also remark that a sig-
]  nature forgery attack is possible under the same circum-
]  stances; here we require the same RSA key to be allowed
]  for use in both encryption and signature algorithms ]> ]> ]> J.P.
]Degabriele, A. Lehmann, K.G. Paterson, N.P. Smart and M.
]]> Strefler, On the Joint Security of Encryption and Signature in EMV.
]In ]> O. Dunkelmann (ed.), CT-RSA 2012, Lecture Notes in Computer
]Science ]Vol. 7178, pp.
]]> 116-135, Springer, 2012. Full version at:
]]> http://eprint.iacr.org/2011/615
]
]RSA Signature Forgery possible in EMV schemes ECIES and EC-Schnorr shown
]secure:
]    More specifically, we prove that the ECIES encryption scheme
]    and the EC-Schnorr signature scheme are jointly secure
]    in the Random Oracle Model, and that ECIES and the
]    EC-DSA signature scheme are jointly secure in the
]    Generic Group Model (GGM). Such results are the best
]    that we can currently hope for, given the state of
]    the art in analyzing ECC signature schemes.
]
]]>
]]>
]]> Positive (and some negative) results can be found in:
]]>
]]> K.G. Paterson, J.C.N. Schuldt, M. Stam and S. Thomson, On the Joint
]]> Security of Encryption and Signature, Revisited. In D.H. Lee and X.
]]> Wang (eds.), ASIACRYPT 2011, Lecture Notes in Computer Science Vol.
]]7073, pp.
]]> 161-178, Springer, 2011. Full version at ]>
]http://eprint.iacr.org/2011/486
]
]Interesting ...
]   Extending the ideas of a combined public key
]   scheme, we show how to construct a signcryption
]   scheme which enables a user to use a single keypair
]   for both sender and receiver roles, and which furthermore
]   allows ecient instantiations with short public keys in the standard
]model
]
]
]Paul
]
]]>
]]>
]]>
]]> Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic agility
]]> and its relation to circular encryption.
]]> In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403{422.
]]> Springer, Heidelberg (2010)
]]>
]]> Coron, J.S., Joye, M., Naccache, D., Paillier, P.: Universal padding
]]> schemes for RSA. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp.
]]> 226{241. Springer, Heidelberg (2002)
]]>
]]> Haber, S., Pinkas, B.: Securely combining public-key cryptosystems.
]]In:
]]> ACM Conference on Computer and
]]> Communications Security. pp. 215{224 (2001) ]> ]> ]> ]> ]> ]> This
]list is by no means complete, but serves to illustrate that the ]>
]picture is complicated and we are far from having a full understanding
]]> of this domain. Several additional references can be found in the ]>
]first-mentioned paper above.
]]>
]]> Finally, let me draw your attention to this very recent paper which
]]> highlights the issues arising from multiple key usage in the context
]]> of ]> TLS:
]]>
]]> Karthikeyan Bhargavan, Cedric Fournet, Markulf Kohlweiss, Alfredo ]>
]Pironti, Pierre-Yves Strub, and Santiago Zanella-Beguelin. Proving the
]]> TLS Handshake Secure (as it is).
]]> https://www.mitls.org/downloads/Proving_the_TLS_Handshake.pdf
]]>
]]>
]]> Happy reading.
]]>
]]> Cheers
]]>
]]> Kenny
]]>
]]> On 16/01/2014 17:37, "Paul Lambert" <[email-masked]> wrote:
]]>
]]>> Hi Rene,
]]>>
]]>> ⨳|-----Original Message-----
]]>> ⨳|From: Rene Struik [mailto:[email-masked]] ]>> ⨳|Sent:
]Thursday, January 16, 2014 2:31 PM ]>> ⨳|To: David McGrew; Igoe, Kevin
]M.; Paul Lambert; Watson Ladd ]>> ⨳|Cc: Yaron Sheffer; [email-masked] ]>>
]⨳|Subject: Keys for multiple cryptographic uses (was: Re: [Cfrg] ]>>
]Outline ⨳|-> was Re: normative references) ⨳| ⨳|Hi Paul et al:
]]>> ⨳|
]]>> ⨳|A counter example in practice to the "received wisdom" not to
]reuse ]>> ⨳|public keys both for key agreement and non-repudiation is
]during ]>> ⨳|certification requests, when the key to be certified is to
]be used ]>> for ⨳|uses including key agreement and where the request is
]signed.
]]>> ⨳|
]]>> ⨳|[see also NIST SP 800-56a-2013, Section 5.6.3.2, item #5:
]]>> ⨳|A static key pair may be used in more than one key-establishment
]]>> ⨳|scheme.
]]>> ⨳|However, one static public/private key pair shall not be used for
]]>> ⨳|different purposes (for example, a digital signature key pair is
]]>> not ⨳|to be used for key establishment or vice versa) with the ]>>
]following ⨳|possible ]>> ⨳|exception: when requesting the (initial)
]certificate for a public ]>> ⨳|static key-establishment key, the key-
]establishment private key ]>> ⨳|associated with the public key may be
]used to sign the certificate ]>> ⨳|request. See SP 800-57, Part 1 on Key
]Usage for further ]information.
]]>> ⨳|]
]]>> ⨳|
]]>> ⨳|While key separation seems prudent, it is not entirely clear (to
]]>> me) ⨳|whether the conditions under which this is required are ]>>
]precisely ⨳|known (even in the above-mentioned case of signed ]>>
]certificate ⨳|requests).[ ⨳] ]>>
]]>> Yes - exactly!   Caution is good ... but once this guidance was set
]]down
]]>> we have not bothered to investigate deeply which algorithm ]>>
]combinations are secure for mixed use.
]]>>
]]>> Additional wisdom on where specific Oracle exist would be very ]>>
]informative.
]]>>
]]>> Thanks,
]]>>
]]>> Paul
]]>>
]]>>
]]>> ⨳|
]]>> ⨳|Best regards, Rene
]]>> ⨳|
]]>> ⨳|
]]>> ⨳|On 1/16/2014 3:30 PM, David McGrew wrote:
]]>> ⨳|> Hi Kevin, Paul, and Watson,
]]>> ⨳|>
]]>> ⨳|> On 01/16/2014 02:42 PM, Igoe, Kevin M. wrote:
]]>> ⨳|>> Paul Lambert
]]>> ⨳|>> On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:
]]>> ⨳|>>
]]>> ⨳|>>> A truly ‘unified' public key system would support both ]>>
]signatures ⨳|>>> and key establishment with the same key.
]]>> ⨳|>>>
]]>> ⨳|>> Received wisdom is that using the same key for both key ]>>
]⨳|establishment ⨳|>> and signatures is a bad idea.  I believe the ]>>
]concern is that one ⨳|>> protocol might be used an Oracle to subvert ]>>
]the other.
]]>> ⨳|>
]]>> ⨳|> Agreed on that point, but there is a background issue here that
]I ]>> ⨳|want ⨳|> to ask about.
]]>> ⨳|>
]]>> ⨳|> [snip]
]]>> ⨳|
]]>> ⨳|
]]>> ⨳|--
]]>> ⨳|email: [email-masked] | Skype: rstruik ]>> ⨳|cell: +1 (647)
]867-5658 | US: +1 (415) 690-7363 ]>> ]>>
]_______________________________________________
]]>> Cfrg mailing list
]]>> [email-masked]
]]>> http://www.irtf.org/mailman/listinfo/cfrg
]]>
]]> _______________________________________________
]]> Cfrg mailing list
]]> [email-masked]
]]> http://www.irtf.org/mailman/listinfo/cfrg
]]
]]
]]Greg.
]]
]]Phone: +1 619 890 8236
]]secure voice / text: Seecrypt +28131139047 (referral code 54smjs if you
]]want to try it).
]]PGP: 09D3E64D 350A 797D 5E21 8D47 E353 7566 ACFB D945 (id says
]][email-masked], but don’t use that email)

---

From: Paul Lambert <[email-masked]>
Date: Thu, 16 Jan 2014 19:20:47 -0800

]-----Original Message-----
]From: Watson Ladd [mailto:[email-masked]]
...
]> Do you have any opinions or results (+ or -) on ECDH?
]
]Given what ECIES consists of this should imply ECDH+E-Schnorr works, but
]I would not be surprised if this turns out a bit differently. I'll have
]to reread the Schnorr proof to think if the reduction can still work
]with an ECDH oracle.

Yes ... interested especially with static.
Ephemeral exchanges look like they map well to any ECIES analysis.
Static would leave another dimension of issues ..

Paul

]Sincerely,
]Watson Ladd
]>
]>
]> ]On Jan 16, 2014, at 14:57 , Paterson, Kenny
]> <[email-masked]>
]> ]wrote:
]> ]
]> ]> Hi
]> ]>
]> ]> There is significant *scientific* literature on the question of ]>
]> security of multiple uses of keys - both for the setting where the ]>
]> same key is used in more than one algorithm of the same type (under ]>
]> the name of cryptographic agility) and where the same key is used in
]> ]> algorithms of different types (e.g. same key in a signature scheme
]> and ]> in a public key encryption scheme).
]> ]>
]> ]> Cautionary examples include:
]> ]>
]> ]> T. Jager, K.G. Paterson and J. Somorovsky, One Bad Apple: Backwards
]> ]> Compatibility Attacks on State-of-the-Art Cryptography. In Network
]> and ]> Distributed System Security Symposium (NDSS 2013).
]> ]> http://www.isg.rhul.ac.uk/~kp/BackwardsCompatibilityAttacks.pdf
]>
]> This shows RSA is dangerous for a particular joint use ...
]>   In the public key setting, we focus on
]>   RSA encryption and signatures, showing a BC attack on
]>   RSA-OAEP when it is used in conjunction with an imple-
]>   mentation of PKCS#1v1.5 encryption that is vulnerable to
]>   Bleichenbacher’s attack [13]. We also remark that a sig-
]>   nature forgery attack is possible under the same circum-
]>   stances; here we require the same RSA key to be allowed
]>   for use in both encryption and signature algorithms ]> ]> ]> J.P.
]> Degabriele, A. Lehmann, K.G. Paterson, N.P. Smart and M.
]> ]> Strefler, On the Joint Security of Encryption and Signature in EMV.
]> In ]> O. Dunkelmann (ed.), CT-RSA 2012, Lecture Notes in Computer
]> Science ]Vol. 7178, pp.
]> ]> 116-135, Springer, 2012. Full version at:
]> ]> http://eprint.iacr.org/2011/615
]>
]> RSA Signature Forgery possible in EMV schemes ECIES and EC-Schnorr
]> shown secure:
]>     More specifically, we prove that the ECIES encryption scheme
]>     and the EC-Schnorr signature scheme are jointly secure
]>     in the Random Oracle Model, and that ECIES and the
]>     EC-DSA signature scheme are jointly secure in the
]>     Generic Group Model (GGM). Such results are the best
]>     that we can currently hope for, given the state of
]>     the art in analyzing ECC signature schemes.
]>
]> ]>
]> ]>
]> ]> Positive (and some negative) results can be found in:
]> ]>
]> ]> K.G. Paterson, J.C.N. Schuldt, M. Stam and S. Thomson, On the Joint
]> ]> Security of Encryption and Signature, Revisited. In D.H. Lee and X.
]> ]> Wang (eds.), ASIACRYPT 2011, Lecture Notes in Computer Science Vol.
]> ]7073, pp.
]> ]> 161-178, Springer, 2011. Full version at ]>
]> http://eprint.iacr.org/2011/486
]>
]> Interesting ...
]>    Extending the ideas of a combined public key
]>    scheme, we show how to construct a signcryption
]>    scheme which enables a user to use a single keypair
]>    for both sender and receiver roles, and which furthermore
]>    allows ecient instantiations with short public keys in the standard
]> model
]>
]>
]> Paul
]>
]> ]>
]> ]>
]> ]>
]> ]> Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic
]> agility ]> and its relation to circular encryption.
]> ]> In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403{422.
]> ]> Springer, Heidelberg (2010)
]> ]>
]> ]> Coron, J.S., Joye, M., Naccache, D., Paillier, P.: Universal
]> padding ]> schemes for RSA. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.
]2442, pp.
]> ]> 226{241. Springer, Heidelberg (2002) ]> ]> Haber, S., Pinkas, B.:
]> Securely combining public-key cryptosystems.
]> ]In:
]> ]> ACM Conference on Computer and
]> ]> Communications Security. pp. 215{224 (2001) ]> ]> ]> ]> ]> ]> This
]> list is by no means complete, but serves to illustrate that the ]>
]> picture is complicated and we are far from having a full understanding
]> ]> of this domain. Several additional references can be found in the
]> ]> first-mentioned paper above.
]> ]>
]> ]> Finally, let me draw your attention to this very recent paper which
]> ]> highlights the issues arising from multiple key usage in the
]> context ]> of ]> TLS:
]> ]>
]> ]> Karthikeyan Bhargavan, Cedric Fournet, Markulf Kohlweiss, Alfredo
]> ]> Pironti, Pierre-Yves Strub, and Santiago Zanella-Beguelin. Proving
]> the ]> TLS Handshake Secure (as it is).
]> ]> https://www.mitls.org/downloads/Proving_the_TLS_Handshake.pdf
]> ]>
]> ]>
]> ]> Happy reading.
]> ]>
]> ]> Cheers
]> ]>
]> ]> Kenny
]> ]>
]> ]> On 16/01/2014 17:37, "Paul Lambert" <[email-masked]> wrote:
]> ]>
]> ]>> Hi Rene,
]> ]>>
]> ]>> ⨳|-----Original Message-----
]> ]>> ⨳|From: Rene Struik [mailto:[email-masked]] ]>> ⨳|Sent:
]> Thursday, January 16, 2014 2:31 PM ]>> ⨳|To: David McGrew; Igoe, Kevin
]> M.; Paul Lambert; Watson Ladd ]>> ⨳|Cc: Yaron Sheffer; [email-masked]
]> ]>> ⨳|Subject: Keys for multiple cryptographic uses (was: Re: [Cfrg]
]> ]>> Outline ⨳|-> was Re: normative references) ⨳| ⨳|Hi Paul et al:
]> ]>> ⨳|
]> ]>> ⨳|A counter example in practice to the "received wisdom" not to
]> reuse ]>> ⨳|public keys both for key agreement and non-repudiation is
]> during ]>> ⨳|certification requests, when the key to be certified is
]> to be used ]>> for ⨳|uses including key agreement and where the
]request is signed.
]> ]>> ⨳|
]> ]>> ⨳|[see also NIST SP 800-56a-2013, Section 5.6.3.2, item #5:
]> ]>> ⨳|A static key pair may be used in more than one key-establishment
]> ]>> ⨳|scheme.
]> ]>> ⨳|However, one static public/private key pair shall not be used
]> for ]>> ⨳|different purposes (for example, a digital signature key
]> pair is ]>> not ⨳|to be used for key establishment or vice versa) with
]> the ]>> following ⨳|possible ]>> ⨳|exception: when requesting the
]> (initial) certificate for a public ]>> ⨳|static key-establishment key,
]> the key-establishment private key ]>> ⨳|associated with the public key
]> may be used to sign the certificate ]>> ⨳|request. See SP 800-57, Part
]> 1 on Key Usage for further ]information.
]> ]>> ⨳|]
]> ]>> ⨳|
]> ]>> ⨳|While key separation seems prudent, it is not entirely clear (to
]> ]>> me) ⨳|whether the conditions under which this is required are ]>>
]> precisely ⨳|known (even in the above-mentioned case of signed ]>>
]> certificate ⨳|requests).[ ⨳] ]>>
]> ]>> Yes - exactly!   Caution is good ... but once this guidance was
]set
]> ]down
]> ]>> we have not bothered to investigate deeply which algorithm ]>>
]> combinations are secure for mixed use.
]> ]>>
]> ]>> Additional wisdom on where specific Oracle exist would be very ]>>
]> informative.
]> ]>>
]> ]>> Thanks,
]> ]>>
]> ]>> Paul
]> ]>>
]> ]>>
]> ]>> ⨳|
]> ]>> ⨳|Best regards, Rene
]> ]>> ⨳|
]> ]>> ⨳|
]> ]>> ⨳|On 1/16/2014 3:30 PM, David McGrew wrote:
]> ]>> ⨳|> Hi Kevin, Paul, and Watson,
]> ]>> ⨳|>
]> ]>> ⨳|> On 01/16/2014 02:42 PM, Igoe, Kevin M. wrote:
]> ]>> ⨳|>> Paul Lambert
]> ]>> ⨳|>> On Thursday, January 16, 2014 1:43 AM Paul Lambert wrote:
]> ]>> ⨳|>>
]> ]>> ⨳|>>> A truly ‘unified' public key system would support both ]>>
]> signatures ⨳|>>> and key establishment with the same key.
]> ]>> ⨳|>>>
]> ]>> ⨳|>> Received wisdom is that using the same key for both key ]>>
]> ⨳|establishment ⨳|>> and signatures is a bad idea.  I believe the ]>>
]> concern is that one ⨳|>> protocol might be used an Oracle to subvert
]> ]>> the other.
]> ]>> ⨳|>
]> ]>> ⨳|> Agreed on that point, but there is a background issue here
]> that I ]>> ⨳|want ⨳|> to ask about.
]> ]>> ⨳|>
]> ]>> ⨳|> [snip]
]> ]>> ⨳|
]> ]>> ⨳|
]> ]>> ⨳|--
]> ]>> ⨳|email: [email-masked] | Skype: rstruik ]>> ⨳|cell: +1
]> (647) 867-5658 | US: +1 (415) 690-7363 ]>> ]>>
]> _______________________________________________
]> ]>> Cfrg mailing list
]> ]>> [email-masked]
]> ]>> http://www.irtf.org/mailman/listinfo/cfrg
]> ]>
]> ]> _______________________________________________
]> ]> Cfrg mailing list
]> ]> [email-masked]
]> ]> http://www.irtf.org/mailman/listinfo/cfrg
]> ]
]> ]
]> ]Greg.
]> ]
]> ]Phone: +1 619 890 8236
]> ]secure voice / text: Seecrypt +28131139047 (referral code 54smjs if
]> you ]want to try it).
]> ]PGP: 09D3E64D 350A 797D 5E21 8D47 E353 7566 ACFB D945 (id says
]> ][email-masked], but don’t use that email)
]>
]
]
]
]--
]"Those who would give up Essential Liberty to purchase a little
]Temporary Safety deserve neither  Liberty nor Safety."
]-- Benjamin Franklin