Here's a simple scenario and I don't see any mitigation.

A site exists, let's say "search.com", and having your searches leaked is bad. A victim opens up a new browser (no HSTS from existing connections) and goes to search.com. An attacker MITMs this HTTP request and injects their own session cookies and then redirects to https://search.com. At this point, let's assume full-domain HSTS kicks in and no more HTTP/MITM are possible.

Now the victim is on https://search.com, lock icon and cert are a-OK. But the user is signed in as attacker. The user might not notice this, and makes searches, which are now available to the attacker, in the attacker's history.

Problem: Fix this, without overly relying on the victim noticing they are signed in as the attacker. After all, they just opened search.com for the first time and aren't expecting to be signed in (though they are wary of HTTPS and do notice the green URL bar).

Perhaps it is slightly contrived and the answer really is "Well, always look on a site to see if you're logged in as someone else". But otherwise it seems rather difficult to fix, outside of HSTS preload. (And this ignores all the other issues noted in the paper.)

Unfortunately no. An attacker can inject a signed cookie just as easily as an unsigned one. A signed cookie can prove integrity, that its data hasn't been tampered with; it can't prove that it is coming from the browser it was issued to.

Exactly. A better, or at least more general, mitigation than enabling HSTS (though that's a good idea anyway), is to not design your web application in such a way that a modified cookie in the client creates a vulnerability. Since cookies are stored in the client, they are always going to be susceptible to malware on the user's machine. So, trusting that the contents of a cookie were authored by the service receiving them is a bad idea in general. Cookies should be stored along with some additional information that verifies their authorship.

A relatively simple way to accomplish this is to have your application include an HMAC in the cookie contents, and verify it whenever the cookie is received. e.g, if you are storing $session_id in a cookie, change your cookie contents to be "$session_id:$hmac_of_session_id", and verify the HMAC every time a cookie is presented.

Now a user, or malware, or a MITM, is not in the position to take over or modify a different user's session simply by altering the cookie, since they will not be able to produce a valid HMAC (the key is never shared with the user).

If even storing the key in your web frontends is too risky, you could use RSA or DSA signatures, only store the public key in the web frontend that verifies cookies, and store the private key in a more hardened cookie-signing service that isn't directly exposed to external networks. This service can be invoked when new sessions are created or upon user login, if applicable.

On top of this, if the client supports ChannelID, you should include the ChannelID in the message that is HMAC'd, so that stolen cookies cannot be reused on other machines.

Presumably this could be done transparently by the web server? Incoming cookies could be validated and then the underlying cookie value passed on to the app. Meanwhile, cookies set by the app get rewritten by the web server to include the signature. This would mean that no server-side code would need to be changed in order to support the cookie signing.

Are there any web servers out there that do this?