Re: [Cfrg] Side inputs to signature systems, take 2

Natanael <> Sat, 23 April 2016 15:16 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 884E912D5B8 for <>; Sat, 23 Apr 2016 08:16:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.799
X-Spam-Status: No, score=-0.799 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id i7mixppAOuV1 for <>; Sat, 23 Apr 2016 08:16:36 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:400c:c09::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2A41B12B02B for <>; Sat, 23 Apr 2016 08:16:36 -0700 (PDT)
Received: by with SMTP id u206so66141439wme.1 for <>; Sat, 23 Apr 2016 08:16:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to; bh=5Obn8lKkn5TxV2DJqb64YAUVPGKNguOightktHPC1HE=; b=YTerWn00I/1hoPLzvkpENd9SuzYch9XjpqXgCtEqLVD9BEFFb4bNN03KlVB266W3bX RpKR6uFXkc+ATMSUdShM3ng/I/csvjCijsrbEmr6kYu/OOVXKJaTiwTiW5hgT47HXPDV q6y26h6XSn28X/CNAQuoj2QWclrgHeSSddSvbgGNAfbdj0Zqz1oTFdlbjpA3P1jwQIeM qKbvjC5n9T88eZREjMFRyBdEUSib90VnPIQnD9+DyUbN5Dd+XDQnuifOysjLbPvyKPkN oi3x1M+YjWzjN6cxnFhacU4g1jrlz77tAkiP0ZOjWlcMCVyJwMzdljd49/WFVLpO7nBb jdEg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to; bh=5Obn8lKkn5TxV2DJqb64YAUVPGKNguOightktHPC1HE=; b=Zpv7sj2BvRCd7CWAAFIIdjQYj2xQyWoQRknZma9QsrNqAmNnszZ/vne22LQPmNOnyt l4WSgImFJdNNOJ51swY8o9MAD02yN9sAc3TbZXQwOH/DiZ+c1s/1aNWF+1qmGREUAsXV Kabd/glZR+ZOboL4I3E/nHdid5n1Qi/AVZogQy1r3jkvPL++X4au8LkKp04Pgwxxuz5X y/0SLXq05uSn6ylflpchHsvkHwOfMdMT7RANYsj8cGymulF3KXtq8twFQHH/7pFPE+1D HUiJXwekBjp8DlX7PHKGkofQ8bd3G+cJWeQZRSqrA17u10Eq/kJ/PUytNH+1z9RFnXAh M0Lw==
X-Gm-Message-State: AOPr4FU9Tv2rwW+Div4KGbC/RqXMZ/GsgcXqLtk7kND1XME/GnPJj5ThbeeqFYiYun3g7gZbvptpoPjBpuvKxg==
MIME-Version: 1.0
X-Received: by with SMTP id d33mr3143481wma.63.1461424594636; Sat, 23 Apr 2016 08:16:34 -0700 (PDT)
Received: by with HTTP; Sat, 23 Apr 2016 08:16:34 -0700 (PDT)
Received: by with HTTP; Sat, 23 Apr 2016 08:16:34 -0700 (PDT)
In-Reply-To: <>
References: <> <>
Date: Sat, 23 Apr 2016 17:16:34 +0200
Message-ID: <>
From: Natanael <>
Content-Type: multipart/alternative; boundary="001a1143608cd4734e0531286dae"
Archived-At: <>
Subject: Re: [Cfrg] Side inputs to signature systems, take 2
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 23 Apr 2016 15:16:38 -0000

Den 23 apr. 2016 15:00 skrev "D. J. Bernstein" <>:
> Here's the standard API for signature systems:
>    * keygen inputs: nothing; outputs: public key, secret key;
>    * sign inputs: message (string), secret key; outputs: signature;
>    * verification inputs: message, signature, public key: outputs: yes/no.
> This API is overwhelmingly popular in the cryptographic literature, the
> security literature, and the software ecosystem. It is shared by the
> vast majority of
>    * specifications of signature systems,
>    * papers analyzing the security of signature systems,
>    * theoretical proofs regarding signature systems,
>    * cryptographic libraries, and
>    * applications of signatures at higher layers of software.
> This sharing is tremendously helpful---compare it to all the horror
> stories of mismatched APIs slowing everybody down, making the auditor's
> job hellishly difficult, and producing real-world security problems. The
> simple fact that the signature API is so popular means that any change
> to the API comes with a heavy presumption of being a _very bad idea_.
> I'm not saying that it's impossible to rebut this presumption. For
> example, I recommend merging the message and signature into a signed
> message---I'm acutely aware of how many system layers need to be adapted
> to make this work, but I don't see any other plausible way to eliminate
> the very common "use the message without noticing it's a forgery" error
> pattern. Stateful signatures are a deeper example. In both of these
> cases I see clear, convincing reasons for a new API, outweighing the
> massive costs and dangers---but changing the API is obviously an uphill
> battle against a default position of amply justified skepticism.

> Encoding the same information into traditional messages does just as
> well in stopping cross-protocol attacks as a "context" side input can
> possibly do. The API divergence is unnecessary and highly undesirable.

I'm just going to add a few more comments in addition to my reply from the
last time.

(And as always, anything of this complexity is unlikely to ever get
implemented, or implemented right for that matter. This is mostly a thought

Summary of how to define the context:

Track the path / branch taken through the code in the generation of the
signed message (identifying the software, the configuration / instance of
it, what it was that invoked the generation of the signature, which checks
the software went through to confirm it should be created, or whatever else
is important). Encode that with the message.

Document what each section of each code branch means, which paths are
valid, what exactly is authorized by any given path's signatures.

A code path that only covers acknowledgement of receipt obviously can't be
use to issue orders of action. Anything that parse the signed messages for
some given system must follow the documentation and must be able to
determine what exact actions a message authorizes. Ideally every type of
valid action should also be explicitly defined in the documentation, so
that this is possible to begin with.

The more I think of it, the more it resembles building a capabilities
oriented system. A bit like an adaption of Bitcoin pay-to-script-hash
transactions / Ethereum, where the system declares what conditions must be
fulfilled for every given action, and where the signed messages
(transactions) must prove the conditions were fulfilled. Take a look at
Bitcoin's Merkelized Abstract Syntax Trees (MAST) for a highly relevant

You shouldn't sign messages with this data structure without first
verifying it does what you want (to not fall for signature oracle attacks).
If everybody follows that advice, you can be sure that the signer intended
to create that particular message.


By my reading, it sounds like you'd rather see something like a specific
signature message input format, where you sign some structured data that
encode the message. (Perhaps we could use the new saltpack format, and
define some json / xml data structure for encoding contexts, etc.)

As for the comment on preventing (carelessly) stripping out the raw message
without further verification: encrypt the message with a key derived from
the metadata (the non-message parts of the data structure) and signature.
Yes, this too is likely to be bypassed by careless programmers, but at
least they should have come across an warnings against doing so when
reading the documentation on how to extract the message. It shouldn't end
up like this: