Request-Response Binding Issues in httpbis-message-signatures-15

I think there are some issues which lead to practical attacks in the 
Request-Response Binding section of httpbis-message-signatures-15 
<https://www.ietf.org/archive/id/draft-ietf-httpbis-message-signatures-15.html>. 
I took a look through recent github issues and mailing list discussions 
and I didn’t see anyone raise similar issues before, but apologies if 
this is a duplicate. My understanding is based purely on a read of the 
spec, I haven’t messed around with the implementations.

*Problems*

httpbis-message-signatures-15 specifies a scheme for binding requests 
and responses together (Sect 2.4 
<https://www.ietf.org/archive/id/draft-ietf-httpbis-message-signatures-15.html#name-request-response-signature->) 
where the response includes components from the request which are tagged 
with |req|. The example provided in the draft uses the signature 
component from the request:

  Request:

        {"Hello, World"}

        Signature-Input: sig1=("@method" "@authority" "@path" \

        "content-digest" "content-length" "content-type")\

        ;created=1618884475;keyid="test-key-rsa-pss"

        Signature: sig1=:LAH8BjcfcOcL...

        ​

        Response:

        {"Your call is important to us"}

        Signature-Input: reqres=("@status" "content-length" "content-type" \

        "signature";req;key="sig1" "@authority";req "@method";req)\

        ;created=1618884479;keyid="test-key-ecc-p256"

        Signature: reqres=:mh17P4TbYYB...

Creating a signature over a signature from another party is a 
cryptographic mistake. This is because the security definition of most 
common signature schemes does not cover the case where the signer is 
malicious and so leaves the resulting behavior undefined.

Practically, this allows for a couple of different attacks. Firstly, it 
means that when using RSA-PKCS / RSA-PSS signatures. an attacker who 
witnesses the above request-response pair and can register a new public 
key, can choose a public key such that sig1 is valid for a different 
message [1]. For example, they could choose {“Goodbye, World”} or any 
other string and then produce the faked transcript:

  Request:

        {"Goodbye, World"}

        Signature-Input: [...] keyid="attackerKey"

        Signature: sig1=:LAH8BjcfcOcL... (unchanged)

        ​

        Response (unchanged):

        {"Your call is important to us"}

        Signature-Input: [...]

        Signature: reqres=:mh17P4TbYYB...

The responder (or any third party) would verify this transcript 
successfully. The responder’s signature validates because it is 
unaltered as are its inputs. The request signature validates because the 
attacker has chosen their public key such that it is valid for the 
alternative message content which contains their keyid and their own 
choice of message. This allows the attacker to take a legitimate 
response from the server to a different user and apply it to a request 
of their choice.

A similarly powerful attack is also possible without access to a 
request-response pair from another party. The attacker registers a 
malicious public key in advance, such as the all-zero Ed25519 key. When 
using this public key, it is trivial to generate signatures which 
validate for any message. The attacker engages in the request-response 
protocol and stores the transcript. Later, the attacker change their 
request to be whatever message they like and the resulting transcript 
will still validate. Depending on the application, this could allow them 
to equivocate, change their vote, alter a timestamp, etc.

This type of attack is very similar to a previous one we found and 
formally modeled in 2019 on WS-Security, which also used a signature of 
a signature to bind request-response pairs. See the discussion and 
protocol diagram in 5.2 of Seems Legit 
<https://dennis-jackson.uk/assets/pdfs/signatures.pdf>.

In the Security Considerations section of the draft (Sect 7.3.1 
<https://www.ietf.org/archive/id/draft-ietf-httpbis-message-signatures-15.html#name-cryptography-and-signature->), 
the existence of signature collisions is acknowledged but the impact is 
largely dismissed and it is suggested the user only use vetted public 
keys and signature algorithms in the draft’s registry. However, at least 
half of the algorithms in the HTTP Signature Algorithms Registry are 
known to suffer from these kinds of problems [2] and I am unaware of any 
IETF standard which specifies how to vet public keys to avoid these 
kinds of attacks. The draft also suggests that the inclusion of the 
signature parameters in the signature base may foil these types of 
attack but I’m quite doubtful as many of the attacks allow for a 
arbitrary choice of message content, meaning that the signature 
parameters can be freely replaced by the attacker.

*Suggested Fixes*

The minimal fix would be to rework the example in 2.4 to avoid a 
signature over a signature and the guidance in 7.3.1 adjusted. This 
could be a simple as just highlighting that signing signature components 
doesn’t bind the message contents and that if the response signature is 
to include the request signature, it should also include the request 
signature’s components directly.

However, I think the draft would be much improved if it gave users a 
sensible default mechanism for how to use request-response signing in a 
robust / secure way via a SHOULD recommendation. Users could choose to 
apply request-response binding differently but should only do so on the 
understanding that they need to do their own security analysis and can’t 
rely on any included within the draft.

A sensible default would be that all signed components of the request 
should be included in the response signature, as well as the request’s 
signature and signature components. This avoids any surprising 
mismatches between what the requester and responder were authenticating. 
This could be done either by explicitly including every signed request 
field in the responder’s signature components (increases message size, 
simplifies implementation) or implicitly by defining special rules for 
interpreting a “signature;req” component in a signature components(saves 
space, adds small amount of implementation complexity). Specifically, 
the implementation would replace "signature;req" by looking up the 
signature component for the associated signature and process each 
element of that, as well as the signature and associated public key.

I would lean towards the latter because its less sharp edges for the 
user and I’m struggling to think of any situation in which you would 
want to include a signature, but not the contents of a signature.

*Further Reading*

  * In 2005, Pornin and Stern introduced some of the key concepts around
    these kind of signature behaviors and show in Sect 2.1 how to
    construct malicious RSA public keys with the necessary properties.
    [PDF <https://www.bolet.org/~pornin/2005-acns-pornin+stern.pdf>] [1]

  * In 2019, we looked at how how these types of attack impact protocols
    in Seems Legit [PDF
    <https://dennis-jackson.uk/assets/pdfs/signatures.pdf>] [2]. Table 1
    provides a summary of the different signature schemes and their
    properties. Section 3 explores how the different properties impact
    various simple request-response protocols. Section 5 describes some
    practical real world attacks on deployed protocols.

  *

    In 2020, we looked at the case of Ed25519 specifically [PDF
    <https://dennis-jackson.uk/assets/pdfs/ed25519.pdf>] and gave a
    proof that with sufficient additional checks which are not part of
    RFC 8032, these behaviors can be removed from Ed25519.

Best,
Dennis