Secure end-to-end when part of conversation must be over HTTP

Question

We have a situation where a user's identity can be verified as follows: the network provider knows the identity of the user and injects secure headers into the HTTP request, which our servers can use to authenticate the user.

We're writing client-server applications and want to use this mechanism to automatically authenticate the user. We can't use HTTPS end-to-end for the authentication request because obviously the network couldn't inject headers in that case.

EDIT: roughly equivalent setup:

(client <-VPN-> HTTP proxy) <-internet-> our server

Assume the VPN (bold section) is secure and the user is authenticated within in the VPN.

The client generates a HTTP request. A proxy within the network knows the client's identity and generates a token which is automatically added to the headers in the proxied HTTP request. All of this happens in a secure domain and cannot therefore be compromised. (Unfortunately we can't change anything in the VPN setup, such as have the proxy make a HTTPS request instead.)

Our server can query back to the network (securely) to determine the identity of the client who initiated the request.

Assumptions:

1. This HTTP requirement is a given and can't be changed.
2. An attacker can't fool the identity verification process by presenting fake headers.
3. An attacker might be able to otherwise intercept/compromise the HTTP request/response.
4. Server is stateless (so no storing one-time keys server-side).
5. Storing a private key in the client application is not an option as it could be compromised
6. The HTTP request/response will be used auto-authenticate the user, but all other interactions before (if necessary) and afterward will be over HTTPS.

Here's what we've tried so far:

1. Client fetches a public key PK from server over HTTPS
2. Client generates a symmetric key SK
3. Client encrypts SK using PK, and sends this to server over HTTP
4. Server verifies user's identity and generates authentication token AT
5. Server encrypts AT using SK -> E(AT,SK)
6. Server signs E(AT,SK) using its private key and sends to client
7. Client uses PK to verify signature
8. Client uses SK to decrypt E(AT,SK) giving AT
9. Client uses AT to authenticate all subsequent HTTPS traffic.

(And we should probably use separate key pairs for encryption and signing, but let's ignore that for now).

As far as I can see, this is secure against eavesdroppers (as they won't have SK) but if a malicious attacker can modify the HTTP request, there is nothing stopping them from generating their own symmetric key instead of SK, encrypting it with PK, replacing the request payload with that and the server will have no idea that it's not talking to the real client. The server will then happily encrypt a valid AT and send it back to the attacker who can then proceed with impunity.

Is there a way to shore up this hole? Is it even possible to do this with a stateless server?

EDIT: if the server can detect tampering and abort the authentication process, that would be sufficient. "This is not possible because X" is also a valid answer, if it can be demonstrated.

Answer 1

Why can't it be changed? You can use an HTTPS proxy where the user connects via SSL to the gateway adding the headers and then relays the communication on to your servers, also over SSL. You can't have one SSL connection the entire way though, but that doesn't mean you can't have SSL connections for each step of the journey.

Otherwise, you are effectively asking an impossible question because you want to have a secure connection between you and the client, but want someone else to be able to be a man in the middle and modify what you are sending. Those are mutually exclusive goals unless you make it so that the intended man in the middle can be in the middle of the communication.