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

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