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

["Dang, Quynh (Fed)" <[e-mail]>]

#3 is a clever idea.

Regards,
Quynh. 

________________________________________
From: Cfrg <[e-mail]> on behalf of Bryan Ford <[e-mail]>
Sent: Saturday, May 21, 2016 5:43 AM
To: Daniel Kahn Gillmor
Cc: Robert Edmonds; [e-mail]; [e-mail]; Ondřej Surý; Benjamin Kaduk
Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519

I see after a long absence that I missed a new flare-up of the Great Context Debate (tm). :)

When I originally proposed the hashing scheme that included contexts for Ed448, I brought up this Ed25519 backward-compatibility issue, and suggested a few alternatives, at least one of which as I recall was similar to DKG’s suggestion.

At any rate, I agree with DKG and others that it would be nice for the RFC to specify a way to deal with an *optional* context parameter for Ed25519 - for consistency with Ed448 if nothing else - while preserving Ed25519 backward compatibility when the context parameter is missing/empty.  No one is forced to use it, but having it in the RFC - and in the APIs of implementations that choose to support it - both makes the RFC more self-consistent and offer a small robustness benefit to new protocols that decide to use contexts.

While the same domain-separation benefit can always be achieved by just prefixing the message, having an explicit context parameter in an API forces the software developer who’s calling that API to see it, and think “do I need to pass something there? what? should I ask a colleague?”  Whereas it’s much easier (essentially trivial) to “forget” to decide to prefix a signed message with something, especially if you’re not a crypto-geek and never heard that you were supposed to.  TLS won’t use contexts, and that’s fine, bit TLS isn’t the relevant “customer” here.  The “customer” is all the possible users of Ed25519 that are *not* nearly so widely-analyzed as TLS.

Yes, key-separation practices are good too, but do not substitute for the domain-separation that contexts can provide, because relying on key-separation exposes message-confusion risks at much higher levels of the “protocol stack” where key management occurs.  If an IETF protocol or proprietary application protocol is designed to use of a context, then any properly-functioning software implementing that protocol will enforce that domain-separation independently of how well or badly users or administrators might manage their keys.  Contexts provide a way for the protocol and software developer to enforce domain separation, whereas key-separation in many environments is something users and administrators have to do.  As others have stated, it’s about redundancy: no one is saying key-separation is bad, but encouraging the use of both reduces the chance of something going critically wrong at *both* levels (protocol design/implementation and key management).

In terms of how exactly to specify a backward-compatible context mechanism for Ed25519, I would certainly support DKG’s specific proposal where context may be empty) as offering a reasonable balance between simplicity and domain-separation goals.  But just to explore a couple slightly different variants with slightly different tradeoffs:

1. DKG’s proposal (baseline): mainly just change H(x) in Table 1 to H(context || x), where context may be empty for backward-compatibility.

2. Change the H(x) line in Table 1 to:

   |    H(x)   | SHA-512(x) [RFC4634] if ctx is empty               |
   |    H(x    | SHA-512(len(ctx) || ctx || x) if ctx is nonempty   |

Advantage: stronger domain separation, ensuring any use that specifies a context is domain-separated from any use that does not.
Downside: slightly more complex specification and code (one ‘if’ statement), though this bit of complexity is hidden from callers of the Ed25519 API.

3. Change the H(x) line in Table 1 to:

   |    H(x)   | SHA-512(len(context)^len(context) || context || x) [RFC4634]    |
…that is, the prefix is L consecutive bytes having value L, where L is the length of the context string, followed by the context and x.  So:

- empty context: H(x) is SHA-512(x)
- context = “foo”: H(x) is SHA-512(“\3\3\3foo” || x)
- context = “blah”: H(x) is SHA-512(“\4\4\4\4blah” || x)

Advantage: eliminates the need for a special-case (the ‘if’ statement) for backward compatibility, while providing the same stronger domain-separation of alternative #2 above.
Downside: doubles the effective size of the context-prefix to process.  But I can’t imagine this mattering in any practical scenario, especially since contexts are expected to be short strings.

Cheers
Bryan