Actively secure MAC 2PC

[themighty1]

The current MAC 2PC protocol is only passively secure. Concretely the following attack is possible:

• for all multiplications, PartyX sends all rows as zeroes
• for one single multiplication in which PartyY's y is H^1 (the GHASH key), PartyX sends such rows which have only 1 bit set in the position corresponding to the current row's positions
• at the end PartyY's GHASH output share will be masks XOR H^1

Luckily, AES-GCM's MAC is not just the GHASH output but it is GHASH output XOR GCTR block. If MAC was just the GHASH output then PartyX (who knows masks) would be able to recover PartyX's H^1 just by looking at the MAC.

The GCTR block (which is secret shared between parties) serves as an OTP when PatryY applies it on top of its potentially leaky GHASH output share.

One argument is that this protocol does not need to be actively secure since the most a malicious party can do is to corrupt the MAC and have it rejected by the TLS server.

Another argument is that to prevent some yet-unknown attacks, it is worth adding active security if it can be achieved cheaply. There are at least 2 options to achieve active security:

Option 1: Notary replays the protocol

We assign the PartyX role to the User and require that User reveals his GHASH key share (for the TLS request) to the Notary at the end of the TLS session. Notary proceeds to check the whole 2PC multiplication transcript to make sure the User was sending correct messages. Only if this check passes will the Notary sign the session.

Option 2: Maliciously secure KOS16 (6x cost of passively secure)

The original formulation of the 2pc multiplication was here (section 4): https://link.springer.com/content/pdf/10.1007/3-540-48405-1_8.pdf and KOS16 builds on top of that for a malicious secure version: https://eprint.iacr.org/2016/505.pdf

[themighty1]

The replaying of the protocol can be done with 2 approaches:

A. The Notary replays the protocol (User is PartyX) B. The User replays the protocol (Notary is PartyX)

Both A and B will protect against a malicious User taking advantage of a yet-unknown vulnerability to sign a bitflipped transcript.

However, there are some tradeoffs in these approaches against the Notary who is actively monitoring the User's internet connection and is trying to hijack the HTTP session.

Potential Notary attack with approach A:

The approach A requires that the User reveals the client_MAC_key (the MAC key used to authenticate the TLS records sent from the TLS client to the TLS server) to the Notary at the end of the TLS session.

To attack, a malicious Notary would intercept the User's request TLS record, not let it through and somehow force the webserver to respond. Then later when Notary learns the client MAC key, he can flip bits in the intercepted request and compute the correct MAC and send the forged request.

This attack is even more pronounced with HTTP2 where servers are allowed to send unsolicited control messages like WINDOW_UPDATE and SETTINGS at any time. The User may be tricked into thinking that the control message is the actual server response.

Mitigation:

• The User needs to make sure that the TLS session is closed before revealing the client_MAC_key to the Notary. With the TLS session closed, the server will not accept a forged request sent by the Notary. This relies on the server sending the TLS Close_Notify message which the majority does Not do.

• Additionally the User should perform an HTTP logout to invalidate the session cookie.

Potential Notary attack with approach B:

To attack the approach B, the Notary would have to find a yet-unknown vulnerability in the MAC 2PC protocol such that the whole MAC key is leaked. Then he could flip bits in the intercepted request and compute the correct MAC and send the forged request.

Mitigation:

• Since the User will replay the protocol, he will detect the attack (after the fact) and can publicize it (if the Notary signs the MAC 2PC transcript).

[themighty1]

Here is one potential solution to add malicious secuirty: DualEx 2PC multiplication.

Suppose, PartyX has a value x and PartyY has a value y. Our goal is to have their product be additively shared between the parties, i.e. PartyX will have a and PartyY will have b such that x*y = a ⊕ b. The main challenge is to have a maliciously secure protocol.

1. Parties run the Gilboa protocol from ("Two party RSA key generation" section 4.1 in https://link.springer.com/content/pdf/10.1007/3-540-48405-1_8.pdf), where PartyX is the OT sender. At the end of the protocol they will have additive shares c and d.

2. Parties run the Gilboa protocol again but this time PartyY is the OT sender. At the end, the parties will have shares e and f.

Note that since c ⊕ d = x y and e ⊕ f = x y, then c ⊕ d = e ⊕ f and also c ⊕ e = d ⊕ f

3. Parties run an equality check protocol which can be instantiated with:

A) maliciously secure garbled circuit where PartyX inputs his c ⊕ e and PartyY inputs her d ⊕ f and the circuit returns true if they match

B) take advantage of one-sidedness of the TLSNotary protocol and have the User first commit to her checked value, then the Notary reveals his checked value and then the User reveals her commitment.

[sinui0]

To attack, a malicious Notary would intercept the User's request TLS record, not let it through and somehow force the webserver to respond. Then later when Notary learns the client MAC key, he can flip bits in the intercepted request and compute the correct MAC and send the forged request.

This attack is even more pronounced with HTTP2 where servers are allowed to send unsolicited control messages like WINDOW_UPDATE and SETTINGS at any time. The User may be tricked into thinking that the control message is the actual server response.

This withholding attack seems to apply in any scenario where the User reveals the MAC key without having assurances that the TLS session is terminated.

In general we require the Server to return an expected response to the User. Each record has a corresponding sequence number which the Server checks. So the if the User sends a record with sequence number N, and receives an expected response, they know that any prior records <N must have been processed by the Server.

Order protection/non-replayability: An attacker should not be able to cause the receiver to accept a record which it has already accepted or cause the receiver to accept record N+1 without having first processed record N.

The message the User sends to check this would ideally occur at the TLS layer, not the application layer. You mentioned that most Servers don't send close_notify. Do you have a source for that?

The TLS 1.2 RFC says "The other party MUST respond with a close_notify alert of its own and close down the connection immediately, discarding any pending writes". https://www.rfc-editor.org/rfc/rfc5246#section-7.2.1

TLS 1.3 RFC says "Each party MUST send a "close_notify" alert before closing its write side of the connection" https://www.rfc-editor.org/rfc/rfc8446#section-6.1 though the RFC is vague about the read-side, which is what we're concerned about.

Perhaps for TLS 1.3 we could use another TLS record, such as renegotiating the cipher suite? Whichever approach we use, we must implement this check as a precondition to revealing the MAC key.

edit I just scanned a few domains, and you're correct, many do not send close_notify.

[sinui0]

Here is the solution I propose to this connection termination problem:

We're already planning to scan a server prior to notarization in order to detect which protocol version + ciphersuites it supports so that we can do a bunch of setup beforehand. In addition to determining that information, we will also determine whether the server properly responds to close_notify. If a server does not respond to close_notify, we play dirty instead. To terminate the connection we will instead send an encrypted message with a unexpected record header, eg. with a HandshakeMessage type. This should cause the server to respond with a fatal Alert message and close the connection. Receiving this fatal alert (which is encrypted by the server) will assure the User that all prior messages were processed and the connection was closed.

Knowing this, we can safely reveal the MAC keyshares to the Notary afterwards.

Because this message occurs at the TLS layer, not the application layer, it should not cause any unexpected side effects in the app. Although, this will unfortunately be very detectable to the server and, if they're paying attention, will reveal that the User used our protocol.

[themighty1]

This is a good approach. Let's use close_notify where possible and use some workarounds when it is not available.

[themighty1]

Seems like relying on server to send a close_notify or a bad_record_mac alert will not work anymore. A few months ago when we tested it, we had > 50% servers replying with close_notify. Now, almost none of them does.

This can be tested with this repo https://github.com/themighty1/rustls The actual test is in examples/src/bin/simpleclient.rs To compile and run:

cd examples
cargo build --release
../target/release/simpleclient