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

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> 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