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

Hi Dennis,

My mail system seems to have been over-aggressive in its spam filtering, and so I didn’t actually see your previous response at all, or this reply, until someone else pointed it out to me just now. I had merged the changes as they stood because my co-author had told me that she had some additional changes she wanted to make on top of the text, and (as far as I could tell), I hadn’t heard back from you about it yet. My apologies for the misunderstanding.

The changed text changed the guidance on what implementors should do and what they should expect out of the exchange. In the request-response binding example, the server is no longer claiming that the entire request is covered, but instead that only specific portions are covered, including the signature-input. This addition does, at the very least, allow the server to include nonces, key identifiers, and timestamps under the signature base. It is not equivalent to signing the whole request, but the example is no longer promised to do that.

The example does include the “@method”;req and “@authority”;req, but you are correct that it doesn’t include the request "@path”, "content-digest”;req, "content-type”;req, and "content-length”;req as well. The reason for this was to show that the server’s concerns about what part of the request is covered by the response signature is separate from what the client covers with its own signature, but I don’t think that comes across in the narrative.

I think there are a couple options that we can do to the example to highlight these concerns in a useful way to developers:

1) Remove the request signature from the example entirely. It’s not needed in order for the server to cover appropriate portions of the request, and it’s no longer promised to have the transitive property that your paper shows it does not have. And besides, the server’s concerns about what’s covered don’t need to align with the client’s.

2) We add a signature less example from (1) but keep the current example by :adding: a client signature to the request and response. This would tie into the discussion in the new security considerations section about why covering :only: the signature is a bad idea.

Would that work?

 — Justin


On Mar 27, 2023, at 2:34 PM, Dennis Jackson <ietf@dennis-jackson.uk> wrote:


Hi Justin,

You appear to have merged the PR as-is. As I detailed in my earlier message, the change doesn't address the attack.

Have I misunderstood the handling of the header in your proposal or are you still considering the path forwards?

Best,
Dennis

On 07/03/2023 00:29, Dennis Jackson wrote:

Hi Justin,

Sorry for taking a couple of days to get to this, but I don't think the proposed changes do anything to fix the attack.

In your changed example, you've included the `signature-input` field from the request in the response, but this field doesn't include the referenced field values from the request. The resulting signature base of the responder lists the expansions as:

```
signature-input";req;key="sig1": ("@method" "@authority" "@path" \
  "content-digest" "content-type" "content-length")\
```

As this doesn't capture the field values, the attacker can still mutate the value of all of these fields from the request. The responder's signature base needs to include either:

  *   All of the request's field values directly; or
  *   Some equivalent binding, e.g. a hash of all the field values in the request.

If taking the first option, the signature base for the responder would need to cover the actual value of each field, e.g.something like:

```
"content-digest";req:sha-512=:WZDPaVn/7XgHaAy8pmojAkGWoRx2UFChF41A2svX+T\
  aPm+AbwAgBWnrIiYllu7BNNyealdVLvRwEmTHWXvJwew==:

Let me know if I've misunderstood or if the example text for the signature base wasn't updated correctly. As you can see this will be quite verbose when repeated for every signed field in the request, which is also why I favor  defining a derived @signature field to do this on behalf of the application.

I have further feedback on capturing these changes as explicit MUST requirements and some minor nits on your description of the attack, the proxy example and the conflict between 7.3.1 and 7.3.7, but they can wait until we've clarified this issue.

Best,
Dennis

On 03/03/2023 12:20, Justin Richer wrote:
Hello everyone,

I’ve created a pull request to address the issues Dennis raised in this thread:

https://github.com/httpwg/http-extensions/pull/2452


I believe that this addresses the concerns by providing appropriate guidance, advice, and warnings. I would be interested in pursing a specialized “@signature” derived component as an extension, if there is interest in doing so.

 — Justin

On Feb 8, 2023, at 3:32 PM, Justin Richer <jricher@mit.edu><mailto:jricher@mit.edu> wrote:

Hi Dennis, thanks for bringing this issue to the group’s attention and for your thorough writeup of the details involved.

I want to start by summarizing that I agree with the attack vector being a problem, but I disagree with Dennis’s proposed means of addressing it within this spec.

First, it’s important to know that this attack relies on their being a weakness in the underlying cryptographic primitive: namely, that a signature collision can be forced between two different, unrelated signatures bases. It doesn’t matter if the originator signs all required components of the message or not because the attacker can force the output of their signature to be a binary match against the signer’s.

Where I disagree with Dennis is the proposed mitigation. I do not think it is reasonable to special-case the “signature” field in the way that is proposed. While doing so would mitigate the specific problem here, I believe there are several major problems with this:

 - Special casing a single field like this is bound to get missed by implementations and libraries, and I fully believe handling of this would be iffy at best. Saying that developers will always rely on a full-blown library do handle signature generation is, I believe, not realistic. While I think it’s preferable for there to be a well-vetted and supported library dedicated to a core function, the truth is that people out there are going be implementing this inline in a lot of places because the signature base generation is ultimately about deterministic string production and off-the-shelf libraries can be used for the crypto primitives.
 - Special casing the “signature" field begs the question of whether other fields could be forged in a similar fashion (content-digest, for instance?), causing related but slightly different attacks.
 - Adding the original signature base in verbatim to the old signature base is going to create a component value with newline characters. These characters are explicitly disallowed in order to prevent other forms of constructions attacks, where the attacker can force in one value that looks like it’s terminating a previous value to overwrite something else.
 - The attack relies on weaknesses in underlying crypto, and this spec intentionally does not limit the kinds of digital signature or MAC that can be used by an application. It’s entirely reasonable that an application that requires the kind of non-repudiation link that drove the addition of the request-response binding function would also specify a signing algorithm, key properties, and any additional parameters that prevent that kind of forgery as well.
 - We can call out the problem case with sufficient detail to let application developers decide what to do with their application of HTTP Signatures. This spec was always intended to be somewhere in the middle of an application stack, with applications defining the properties they need in the end result. Adding this kind of complexity feels like a pretty major foot-gun that would be better addressed in a wholistic manner up the stack.


Furthermore, I think there’s an alternative approach which could fit the work of an extension: have a new derived component with the behavior listed in the proposal below. For argument sake let’s call this “@signature” and we can even have it take a parameter to select which signature of the target message is being called upon. The component value of this derived component would be the signature base of the target signature, re-generated and then encoded, perhaps as an sf-string item to escape newlines and quotes and other potentially problematic items, or even enforce use of the “bs” flag that would give us the encoding properties we’re after. That way there’s no special casing of the field, it’s a production rule of the derived component definition that’s either supported or not by the implementation — and any derived components that aren’t recognized cause an error and cessation of processing of the signature base. Annabelle and I discussed doing exactly this a while ago but rejected it because of the additional complexity it adds on top of just signing a header like any other header.

My proposal for addressing this issue is to take the following actions, none of which fundamentally change the existing draft’s processing:

 - Update the examples and advice that talk about signing another signature value and instead have the examples sign more specific components instead of the signature (for the request-response binding) or additional rationale for the transitivity of the trust (in the reverse proxy example).
 - Add a security consideration section that details this specific sig-over-sig attack, using Dennis’s well-reasoned example below.
 - Expand the signature collision section with discussion of the kind of key-collision that makes this attack viable, and which has been studied in the referenced papers.
 - Target the expanded “@signature” derived component, expanded above, as an extension to this draft with its own deeper discussion.
-  Bring this issue to the OpenID Foundation’s FAPI working group, which is where the original non-repudiation linking use case and requirement came from that lead to the addition of this function. I believe that community can offer some important insight into how this could be addressed.


Dennis has offered off-list to help work on whatever the final text ends up being.


 — Justin

On Feb 8, 2023, at 11:09 AM, Dennis Jackson <ietf@dennis-jackson.uk><mailto:ietf@dennis-jackson.uk> wrote:


Bringing some off-list discussions with the authors (and others) back to the list:

What's the tl;dr?

The Message Signatures draft has serious cryptographic issues which break the claimed properties around request-response binding and allow for practical attacks. Depending on the exact specifics of the application, attackers can forge responses without having access to the responder's signing key. These issues are very similar to previously known signature attacks on request-response protocols like WS-Security, the initial ACME certificate issuance protocol (as reported by Andrew Ayer) and SCION's DRKey protocol [1].

Has this been fixed in -16?

No.

How do the attacks work?

An attacker can forge transcripts and violate the request-response binding, without having to break the signature scheme's cryptographic properties, compromise a signing key or change another party's public key. The attacker exploits properties which are common in widely used signature schemes:

  1.  The same signature can validate under two different public keys.
  2.  The same signature can be valid for two (or more) different messages.

The Message Signatures drafts assumes that this is not the case, assuming that a signature can be verified only for a unique public key and a unique message.

What is the suggested fix?

The draft needs to be updated to ensure that whenever a signature is made over a signature, it is also made over the message (signature base) associated with the signed signature. This can be done either by having Message Signature libraries automatically include the signature base when including a signature or by insisting that users ensure all such fields from the request are manually listed in the new signature base.

I strongly believe that IETF drafts should be secure by default and so this should be handled by the library. Leaving it to application developers is a recipe for mistakes and omissions.

This means adjusting the text to add a new MUST requirement to include signature bases when processing signatures within signature components, fixing the examples and correcting the security considerations.

Can you sketch what a concrete attack looks like?

Here's a version of the example protocol in 2.4, where Alice a client is using a financial service from server Charlie. All the parties are using RSA Signatures (doesn't matter which variant).

Alice -> Charlie:
{"I want to pay Bob, what account details should I use?"}
Signature { Content-Digest } := Sig1

Charlie -> Alice:
{"Use Acc #: 123456, Ref #: 789}
Signature { Content-Digest, Sig1 } := Sig2

After getting the response, Alice checks that Charlie's content-digest + Sig2 is valid and makes the payment to Bob's account details.

Let's see how Mallory (the attacker) can steal Alice's money. Mallory is also a user of the system and has compromised Charlie's TLS key but NOT Charlie's Message Signature signing key. Firstly, Mallory intercepts Alice's TLS connection to Charlie and receives the message:

Alice -> 'Charlie':
{"I want to pay Bob, what account details should I use?"}
Signature { Content-Digest } := Sig1

Based on Alice's signature sig1, Mallory then crafts a new public key PK_M with a special property:

RSA-PKCS#1v1.5-Verify(PK_M, Sig1, "I want to pay Mallory, what account details should I use?") == True

In English: PK_M is chosen such that Alice's signature Sig1 verifies under a different message for Mallory's key. This is NOT a forgery or a breakage of the signature scheme. This is in fact easy to do for the RSA-PKCS#1v1.5 signatures as used in things like TLS, see the academic papers I linked in the initial post.

Mallory registers PK_M as her public key with Charlie and then starts a new request/response:

Mallory -> Charlie:
{"I want to pay Mallory, what account details should I use?"}
Signature { Content-Digest} := Sig1

Charlie -> Mallory:
{"Use Acc #: 666666, Ref #: 333}
Signature {Content-Digest, Sig1} := Sig2

Mallory now delivers Charlie's response and signature Sig2 back to Alice, presenting it as a response to Alice's initial Request. Alice now sees:

'Charlie' -> Alice:
{"Use Acc #: 666666, Ref #: 333}
Signature {Content-Digest, Sig1} := Sig2

Alice check's the content digest and signature against Charlie's public key, both are correct. Alice transfers the money to account number #666666, thinking those are Bob's details and Mallory retires as a wealthy criminal.

This violates the request-response binding claimed by the draft.


--

Best,
Dennis

[1] https://dennis-jackson.uk/assets/pdfs/signatures.pdf


On 02/02/2023 09:12, Dennis Jackson wrote:

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