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

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
>