Re: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519

[Daniel Kahn Gillmor <[e-mail]>]

On Wed 2016-04-20 16:51:20 -0400, D. J. Bernstein wrote:
> I sent CFRG a message "Side inputs to signature systems" back in
> September that raises several different objections to the "context"
> concept. I believe that all of the objections remain valid. I didn't
> notice until now that the concept was still under consideration; sorry!

The context label is explicitly in place in Ed448 in the current draft,
but not in Ed25519.

Your concerns are reasonable, but i don't think they're insurmountable
or that they warrant the removal of Ed448:

>       * Are cryptographic libraries supposed to change their signature
>         APIs to allow an extra side input?

A library that implements a signature scheme that has a context string
needs to provide an API for it, yes.  For signature schemes where the
context string is optional (which is all of them, afaict), the context
label should be optional.  Libraries that implement such a scheme can
continue to offer the traditional API (without a context label) of
course.

We've already seen some primitives adopt this approach, including the
"info" parameter for HKDF-Expand
(https://tools.ietf.org/html/rfc5869#section-2.3).  This isn't a
traditional asymmetric signature scheme, but it's an addition to the API
compared to earlier KDFs (e.g. PBKDF2 didn't have such a context label).

>       * What exactly are the format and semantics of this input? For
>         example, how exactly would this side input be used to stop the TLS
>         bug mentioned above?

We're actually doing exactly this in TLS 1.3, but doing it in an ad-hoc
way: basically using the prefix approach in some places (e.g. server
CertificateVerify and client CertificateVerify in TLS 1.3 are prefixed
with distinct context strings:
https://tools.ietf.org/html/draft-ietf-tls-tls13-12#section-6.3.4), and
switching our KDF to HKDF in others (key expansion, etc
https://tools.ietf.org/html/draft-ietf-tls-tls13-12#section-7.1).

>       * What happens when someone wants to use more of these inputs?

I'm not sure what you mean here.  You mean more context labels?  the
goal here is one distinct context label per domain.  the only purpose of
the context label is domain separation.  why would you want more than
one?

>       * How should libraries handle all of the signature standards that
>         don't support this input?

Not all signature schemes take the same set of parameters (e.g. public
keys and secret keys have different structures in different messages).

A library that wants to offer a generic signature scheme where the user
doesn't know anything about the mechanism in use could accept a context
label (byte array and length) and a message (bytearray and length).  if
the signature scheme supports an explicit context, it would use it. If
not, it could use the concatenation approach described above.

>       * More to the point, how is this supposed to be better than having
>         the application sign a more informative message, using the
>         traditional concept of a signature system?

"more informative" assumes that you know exactly how any bytestring is
going to be interpreted in every other context.

If we define a standard way that a signature or key derivation domain
can distinguish itself from any other domain, then we can avoid
cross-protocol attacks for every scheme that adopts this standard.

Without it, each protocol will define how it thinks it should structure
a message that is "informative enough" to be distinct from every other
signed message in every other protocol -- but how will this be
determined without cross-protocol coordination?  This mechanism offers a
means for cross-protocol coordination by selection of distinct context
strings.  (for signature schemes like Ed448 that aren't using the
prefix-approach, the only requirement is context string uniqueness,
since they are prefix-resistant)

Does this make it seem more palatable?  This isn't a strictly
cryptographic property, it's a mechanism to facilitate larger
cross-protocol coordination.

Regards,

               --dkg