Subject: [Curdle] Ed25591ctx

From: Jim Schaad <[email-masked]>
Date: Tue, 16 Aug 2016 14:36:40 -0700

Ilari has done edits on a local draft to respond to my comments and it
appears he is planning on introducing a new mode to the EdDSA drafts for
25519.  Specifically one would have:

EdDSA25519 - the traditional signature algorithm
EdDSA25519ctx - a new mode for 25519 which has a context structure available
to it. 
EdDSA25519pre - a pre-hash mode that uses the same structure as
EdDSSA25519ctx

This means that we would no longer have the huge problem between ctx and pre
hash modes conflicting quite as much as one could require the use of ctx and
pre instead.  One still has the problems between pure and the other modes.

The questions I have are:

Should we issue an OID for the new ctx mode?

Should we require the use of the ctx mode for signing of certificates?

Should we have any advisory language which says that new usages SHOULD use
the ctx mode over the pure mode?

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 17 Aug 2016 06:37:12 +0300

> EdDSA25519pre - a pre-hash mode that uses the same structure as

The names aren't right (the right ones are 'Ed25519ctx' and 'Ed25519ph'),
but otherewise quite so (assuming contexts will be part of the document!)

> pre instead.  One still has the problems between pure and the other modes.

That change also solves the problem of using the same key for Ed25519 and
Ed25519ph. 

However, Ed25519ctx and Ed25519ph can't be computed using standard
Ed25519 software. There is no way to do so while remaining safe to key-
share. Fortunately, the places that are modified are likely not to be
too inaccessable (i.e. written in high-level-language) in practical
implementations, if you can modify one.

> the ctx mode over the pure mode?

It occurs to me that one could avoid use of prehashed EdDSA variants by
adding OID that is defined to sign a hash object[1] instead of the actual
data. If then one could avoid contexts, one could just use standard-issue
Ed25519 code (which is dime dozen).

That could be also be used to avoid the potentially annoying SHAK256
hashing if one wants long-input Ed448.

While contexts could help against things like that TLS 1.2 LURK SKI
attack EKR came up with, there are plenty of RSA or ECDSA keys that are
unprotected against such abuse.

And then there is the issue that contexts are a new input, and many
signature APIs just doesn't have it.

And with regards to new stuff using contexts, I think it is a bad idea,
unless the stuff used only contextualized signatures. And PKIX fails
that criteria.

[1] One rough sketch (excuse me for not using the correct notation):

SEQUENCE {
OID <some-assigned-oid>
OCTET_STRING zeroes_64octets
AlgorithmIdentifier hash_algorithm
OCTET_STRING hash_value
}

DER-encode that (easily templateable if you know the hash,
which would come from the signature algorithm OID) and use that
as message for algorithm.

The OID in the beginning is to distinguish it from other ASN.1
structures.

I threw that zeroes_64octets in there to make it more difficult
to abuse with TLS.

Specifically, valid TLS 1.3 signatures can't look like that because
those start with 0x20, not 0x30 like that one does.

Nor can valid TLS 1.2 signatures, because that one presumably has
a zero in 65th and 66th position, which would code curve type 0
(undefined) for ECDHE and p=0 (division by zero) for DHE.

One minor problem being that it breaks a SHA-512 block (which
is like 2% speed penalty for signing, less for verfication).

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Tue, 16 Aug 2016 21:13:44 -0700

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Tuesday, August 16, 2016 8:37 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Curdle] Ed25591ctx
> 
> > appears he is planning on introducing a new mode to the EdDSA drafts
> > for 25519.  Specifically one would have:
> >
> > EdDSA25519 - the traditional signature algorithm EdDSA25519ctx - a new
> > mode for 25519 which has a context structure available to it.
> The names aren't right (the right ones are 'Ed25519ctx' and 'Ed25519ph'), but
> otherewise quite so (assuming contexts will be part of the document!)
> 
> > This means that we would no longer have the huge problem between ctx
> > and pre hash modes conflicting quite as much as one could require the
> > use of ctx and pre instead.  One still has the problems between pure and the
> other modes.
> 

I had forgotten about the use of the invalid point to make sure that this was clean.

> Ed25519 software. There is no way to do so while remaining safe to key- share.
> Fortunately, the places that are modified are likely not to be too inaccessable
> (i.e. written in high-level-language) in practical implementations, if you can
> modify one.
> 
> > Should we have any advisory language which says that new usages SHOULD
> > use the ctx mode over the pure mode?
> 
> It occurs to me that one could avoid use of prehashed EdDSA variants by adding
> OID that is defined to sign a hash object[1] instead of the actual data. If then
> one could avoid contexts, one could just use standard-issue
> That could be also be used to avoid the potentially annoying SHAK256 hashing if
> one wants long-input Ed448.
> 
> 
> While contexts could help against things like that TLS 1.2 LURK SKI attack EKR
> came up with, there are plenty of RSA or ECDSA keys that are unprotected
> against such abuse.
> 
> And then there is the issue that contexts are a new input, and many signature
> APIs just doesn't have it.

My intent was not clear.  I was indicating that we should use the context version, but specify an empty context as would be done with the Ed448 signature algorithm.  This is not the point in time that I would want to introduce a new parameter to signature and verification APIs.

Jim

> 
> And with regards to new stuff using contexts, I think it is a bad idea, unless the
> stuff used only contextualized signatures. And PKIX fails that criteria.
> 
> 
> 
> DER-encode that (easily templateable if you know the hash, which would come
> from the signature algorithm OID) and use that as message for algorithm.
> 
> The OID in the beginning is to distinguish it from other ASN.1 structures.
> 
> I threw that zeroes_64octets in there to make it more difficult to abuse with
> TLS.
> 
> Specifically, valid TLS 1.3 signatures can't look like that because those start with
> 0x20, not 0x30 like that one does.
> 
> Nor can valid TLS 1.2 signatures, because that one presumably has a zero in 65th
> and 66th position, which would code curve type 0
> One minor problem being that it breaks a SHA-512 block (which is like 2% speed
> penalty for signing, less for verfication).
> 
> 
> 
> 
> -Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 17 Aug 2016 08:06:02 +0300

On Tue, Aug 16, 2016 at 09:13:44PM -0700, Jim Schaad wrote:
> 
> My intent was not clear.  I was indicating that we should use the
> context version, but specify an empty context as would be done with
> the Ed448 signature algorithm.  This is not the point in time that
> I would want to introduce a new parameter to signature and
> verification APIs.

The context is empty by default (except for Ed25519ctx). If that is not
clear from the document, it should be fixed.

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Wed, 17 Aug 2016 08:34:50 -0700

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 19 Aug 2016 08:51:37 +0300

> hashing if one wants long-input Ed448.

Did a PoC implementation:

(The OID I picked is the first "free" OID I found from PKIX registry)

Code:
-----------------------------------------------------------------------
#!/bin/bash

hash=`echo "$1" | cut -b 1-128`
prefix="hex:30819A06072B060105050718300B06096086480165030402030440";
zeroes="0000000000000000000000000000000000000000000000000000000000000000"
prefix2="0440"
echo ${prefix}${zeroes}${zeroes}${prefix2}${hash}
-----------------------------------------------------------------------

Session:
-----------------------------------------------------------------------
# Generate a new key
$ python3 eddsa2-prototool.py keygen Ed25519 base64url base64url
privkey: f2cLOhNwOiWxIdYilrx8j_jfW_eiYU7TTRM4WAAjlTo
pubkey: b0xsyPvk9X6EBuA7Us765Yt_V_6Jfd6CIIUXahTIJ04
# Sign SHA-512("abc")
$ python3 eddsa2-prototool.py sign Ed25519 base64url:f2cLOhNwOiWxIdYilrx8j_jfW_eiYU7TTRM4WAAjlTo $(./sha512ph $(echo -n "abc" | sha512sum)) base64url
signature: 4YXV2bze-vbAjfn0bZFynRhjI9BMf34NX-gh8r4aLEFxEEvTsRjEhCcMQezR3YkzlaCYuG9kIyGQqLp-sL2UBQ
# Verify the signature just generated.
$ python3 eddsa2-prototool.py verify Ed25519 base64url:b0xsyPvk9X6EBuA7Us765Yt_V_6Jfd6CIIUXahTIJ04 $(./sha512ph $(echo -n "abc" | sha512sum)) base64url:4YXV2bze-vbAjfn0bZFynRhjI9BMf34NX-gh8r4aLEFxEEvTsRjEhCcMQezR3YkzlaCYuG9kIyGQqLp-sL2UBQ
# Exit status 0 => success.
$ echo $?
0
# What that program does?
$ ./sha512ph $(echo -n "abc" | sha512sum)
hex:30819A06072B060105050718300B06096086480165030402030440000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000440ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f
# The hash itself (this is one of SHA-2 test vectors).
$ echo -n "abc" | sha512sum
ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f  -
$
-----------------------------------------------------------------------

The signature algorithm is standard-issue Ed25519. The same trick would
also work for Ed448.

I ensured that 64th, 65th and 66th bytes are all zero, which avoids
collision with either TLS 1.2 or 1.3 (it is either invalid padding,
invalid curve type or divide by zero). And the OID I put in there
avoids collisions with other ASN.1 stuff.

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Sun, 21 Aug 2016 11:34:20 -0700

A follow up to this message.

The CFRG draft has been published and based on the text it really only
leaves the question of do we want to assign an OID for EdDSA25519cxt at this
time.

jim

> From: Curdle [mailto:[email-masked]] On Behalf Of Jim Schaad
> Sent: Tuesday, August 16, 2016 2:37 PM
> To: [email-masked]
> Subject: [Curdle] Ed25591ctx
> 
appears
> he is planning on introducing a new mode to the EdDSA drafts for 25519.
> Specifically one would have:
> 
mode
> for 25519 which has a context structure available to it.
> This means that we would no longer have the huge problem between ctx and
> pre hash modes conflicting quite as much as one could require the use of
ctx and
> _______________________________________________
> Curdle mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/curdle

---

From: Jim Schaad <[email-masked]>
Date: Sun, 21 Aug 2016 12:27:31 -0700

> penalty for signing, less for verfication).

This worries me from the following perspective:

Ok - this would work if we had just TLS and ASN.1, but I start worrying about this when you also decide to do the same thing for CBOR, XML, JSON and who knows what other formats.  YAML anybody?  It is easy to potentially avoid the collisions with two, but harder as new people without the same experience as we have decide to do the same type of thing.

I would rather tell people to design a content structure that does the prehash thing and sign that content than have fancy structure as part of the signature processing.  This is the basic approach I have suggested for signing of large detached files for CBOR and JOSE.  It is also similar to how CMS is designed where the content is hashed and that result is part of what is signed.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 22 Aug 2016 14:02:37 +0300

On Sun, Aug 21, 2016 at 12:27:31PM -0700, Jim Schaad wrote:
> Ok - this would work if we had just TLS and ASN.1, but I start
> worrying about this when you also decide to do the same thing for
> CBOR, XML, JSON and who knows what other formats.  YAML anybody? 
> It is easy to potentially avoid the collisions with two, but harder
> as new people without the same experience as we have decide to do
> the same type of thing.

If you use the same key for those and interactions haven't been
considered in the design, you are far into what I originally
intended contexts to be used for.

OTOH, I think that by far the most common other format ASN.1 keys
need to share with is TLS (note: CSRs cause this sharing to happen a
lot).

Out of what ASN.1 could collide with in that list,  CBOR looks to be
the worst. I checked how the construct would fare with CBOR: SHA-384
variant could encode into valid concatenation of CBOR structures (it
won't encode into single one, because the first byte is already a
value).

-Ilari