Subject: Re: [Cfrg] Help with the use of contexts

From: Tibor Jager <[email-masked]>
Date: Fri, 3 Feb 2017 09:16:11 +0100

On 30 January 2017 at 12:40, Paterson, Kenny <[email-masked]>
wrote:

>
> So: does anyone else want to offer an opinion on the question of contexts?
>
>
Contexts are a clean and relatively simple way to prevent cross-protocol
attacks, in particular when implemented in an as simple way as proposed
by Adam and Dan.

The cross-protocol attacks we have seen so far were mostly rather
academic and not too practical. However, with an increasing number of
cryptographic protocols in use the occurrence of practical
cross-protocol attacks becomes much more likely, as the number of
possible combinations grows quadratically. At some point it will become
infeasible to analyze all possible combinations thoroughly enough.

I think at some point in the future we will have to deal with the
prevention of cross-protocol attacks by using contexts, and doing this
as early as possible is a good idea - following the "better safe than
sorry" principle is always a good idea when designing security protocols.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 3 Feb 2017 14:55:33 +0200

> attacks, in particular when implemented in an as simple way as proposed

Unfortunately, in practice those are anything but clean and simple.

Yes, the theoretical notion is pretty simple (where (context,message)
tuple replaces the message in standard notion of signature security).

The biggest practical problem: Backwards compatiblity, the ever-present
nemsis of security.

There are basically two major problems:

- Non-contextualized schemes, which leave the system wide open for
  any possible attacks. Hopefully nothing major.
- The standard signature API can't accomodiate contexts.

When it comes to TLS, AFAIK the most significant target for possible
cross-protocol attacks is PKIX CSR mechanism.

What I think it would take to deploy contextualization to TLS and
closely associated technologies (PKIX mainly):

- New RSA-PSS (possibly original RSA-PSS), ECDSA and EdDSA signature
  schemes (X.509 algorithms) that are contextualized.
- New RSA and ECDSA key types (X.509 key types; EdDSA can reuse keys) 
- New TLS SignatureScheme values to go with these.

One advantage of having different RSA key type would be that the old
standard one has been jinxed by the broken RSA-PKCS#1v1.5 encryption.
However, there is already standard RSA-PSS key type, which does not
have the same problem AFAIK.

-Ilari

---

From: Natanael <[email-masked]>
Date: Fri, 3 Feb 2017 15:41:37 +0100

Den 3 feb. 2017 13:55 skrev "Ilari Liusvaara" <[email-masked]>:

Couldn't we go the other way and suggest that people don't simply use the
raw signature primitive, and instead only use a message format that
includes room for contexts? Because in general, only cryptographers should
deal with the raw primitives.

Can anybody find a flaw with the following?

Sign(<private key>;
    SHAKE256(<output length parameter>;
        <[hexadecimal encoded output length in bits],
        [Base64(Signature algorithm + format identifier],
        [Base64(Context identifier)],
        [hexadecimal encoded message hash]>))

= message signature, context

You feed in the message, key and context, the rest is hardcoded in the
context aware software.

Question: should the public key be included among the above inputs?
Depending on the signature scheme it may not always be formatted as
expected by the verifier (malleability, etc), and must thus be forwarded
along with every message.
This could perhaps be algorithm specific, since those algorithms with a
deterministic public key encoding can hash it without publishing it with
the message, and still validate.

The signature algorithm description could use predefined ciphersuite
identifiers (much like TLS does), defining the exact choices in use.

The above SHAKE256 inputs should also be encoded with prefixes like a null
byte to guarantee there can be no manufactured collision spanning across
them.

This should in theory provide a context-equipped signature that will not
collide accidentally with context-less messages, and will not collide
across unique signature algorithms/formats, and in particular will not
collide across contexts.

It should also resist most imaginable attacks including length extension
attacks and similar, while also naturally being able to generate arbitary
length hashes (SHAKE256) for the signing primitives (which may use unusual
input lengths). It even achieves this without truncation or padding!
Another question, should we prefix the SHAKE256 output? Is there any
attacks that would stop?

This format should also stop context-unaware software (which can be
presumed to be intended to NOT be able to parse these message) from being
able to validate these signatures, preventing these signatures from
enabling cross-protocol attacks elsewhere.
While one could verify the signature of the raw SHAKE256 output, it would
be meaningless to most unaware software.

Software only expecting signatures with contexts also wouldn't accept
context-less signatures, as they would be extremely unlikely to validate
(assuming SHAKE256 is secure).
The exception is if a context-less program would be insecure and behave as
a signature oracle or even be malicious and thus could be manipulated to
generate such a SHAKE256 output to be signed, to be used against context
aware software.

(Sorry if anything is incoherent, my phone keyboard app Swiftkey bugged out
and started deleting text. Had to rewrite a lot.)

---

From: Tibor Jager <[email-masked]>
Date: Sun, 5 Feb 2017 08:48:01 +0100

> The biggest practical problem: Backwards compatiblity, the ever-present

We do not have to change old protocols in order to enable domain separation
via contexts in new protocols:

- Old protocols: keep signing messages as before: sig = Sign(sk, m)
- New protocols: sign messages as sig = Sign(sk, ctx||m)

Here, ctx is a "unique" and sufficiently large context string, which even
in presence of an attacker is unlikely to occur in the message m of any
existing protocol. For example, one could use the ASCII string "TLS 1.3 TLS
1.3 TLS 1.3 ...", repeating "TLS 1.3" a suitable number of times. The
symbol || denotes concatenation of bytes, possibly with a NULL-byte as a
separator.

This is how I understand the solution pointed to by Adam and explained by
Dan, and it seems similar in spirit to (but simpler than) what Natanael
described. In particular, it seems not to break backwards compatibility
with existing protocols, but would allow a smooth transition to the use of
contexts to achieve domain separation, and thus help to prevent
cross-protocol attacks.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 5 Feb 2017 14:35:37 +0200

> - New protocols: sign messages as sig = Sign(sk, ctx||m)

The problem is, that keys need to be separated as well.

If it is just a protocol that stands alone, then one may just declare
its keys to be suitable.

However, if it uses external keys, you are faced with separating these
keys, which means changes to the key format. And if external keys are
critically used in some other way, you need to modify this use as well.

Implication of above for TLS:

- TLS critically relies in practice on X.509 SPKI key format and X.509
  CSRs.
- Reliance on SPKI impiles that new SPKI key type would be needed.
- Reliance on CSR would mean new X.509 signature type would be required.

Yes, the new key type and new signature type are not difficult to
define, but still need to be done for the scheme to give security.

> symbol || denotes concatenation of bytes, possibly with a NULL-byte as a

Fails the basic notion of security of contextualized signatures.

> contexts to achieve domain separation, and thus help to prevent

I don't think they described the catch with this type of construction...

-Ilari