The baseline protocol

When designing the squid authentication system, several performance-improving "tricks" have been employed, with beneficial effects to response times, authenticators load, and domain controller load. Unfortunately they have the effect of making the subsystem somewhat complex. In this chapter we'll just have a look at the basic communications among the interested parties, omitting those hacks.

There are at least three parties involved in the authentication procedure, but there could be as many as five. There are at least the client, Squid, and the authentication helper, but also one or more domain controllers might be involved, either in a load balancing/failover architecture, or in a chained architecture (Domain Trusts).

I've prepared some graphic (PNG format (11 Kb) or MS-PowerPoint (22 Kb)) detailing the protocol, along with a somewhat deep explanation of the NTLM authentication protocol as applied to WWW- and Proxy- authentication.

The Squid-helper protocol is text-based and line-oriented. All messages are terminated with a single "\n".
Squid will feed the helper the base64-encoded NTLM authentication packets, possibly prefixed with FLAGS information, and will expect the helper to get back from the helper one of:

[FLAGS flag[ flag ...] ]CH base64-encoded-challenge

This tells Squid that the packet received is a negotiate-request, and that the string supplied must be a base64-encoded challenge packet. Squid will fix all appropriate response codes and send the challenge back to the client

[FLAGS flag[ flag ...] ]OK [domain\]username

This tells squid that the packet received is a valid authenticate request, and that access to the resource (and to all resources subsequently requested on the same TCP connection) should be granted. The TCP connection is marked as "owned" by the user identified by domain\username (the domain part is actually not mandatory)

[FLAGS flag[ flag ...] ]ERR explanatory text

The user couldn't be authenticated for some reason. Squid will reject the user, and MAY use the supplied string for debugging information or to give feedback to the user.

Squid guarantees that all messages pertaining authentication from a client connection will be delivered to the same helper. Also, it won't send requests while waiting for an helper to do what it requires to perform the authentication operation. Squid does not guarantee ordering though. This means that a sequence like:

1. Negotiate from client A
2. Negotiate from client B
3. Authenticate from client A

is legal and to be expected. While this might seem strange, it has big benefits performance-wise.

Deviations from the base protocol

Nothing forbids some server to reuse the same challenge over and over again. In fact, squid kind of expects the authenticator to do exactly this and provides means to further enhance performance using this assumption.

Credentials caching

Given a challenge, the authentication message will be the same, no matter how many times the same challenge is fed.
Squid will exploit this fact by using a user cache, linking paired encoded NTLM authentication packet & encoded NTLM challenge packets to the to the user credentials that the helper returned. This makes it so that as long as the same challenge is reused, authentication requests will not even reach the helpers. The downside is that if some implementor decides to change challenge for each request, that cache will grow up in size quite fast.

Challenge caching (Planned)

Given notification by the helper of challenge changes, squid is able to respond to the negotiate request itself, only send the authenticate request through. And if the authenticate is already cached, then squid can handle the request with no helper-interaction at all.

Ignorance is bliss

The whole authentication system tries to be as stateless as possible (ignorance is bliss). In fact helpers can be completely stateless in theory. This helps performance as well as avoiding starvation problems. A sad side-effect is that it kind of forces us to do challenge reuse, as shown in the following scenario:

1. Client A negotiates and gets challenge X
2. Client B negotiates and gets challenge Y
3. Client A tries to authenticate. Against what challenge? No way to know.

Challenge renewal (PLANNED, might change marginally)

We are reusing a challenge multiple times. However, we can't do that forever, for obvious security reasons; that's the whole point with a challenge-response authentication scheme anyhow.*
This poses a problem: WHEN could we renew a challenge? The problem can be subtly racey:

1. Client A connects, gets challenge X
2. Server renews challenge
3. Client B connects, gets challenge Y
4. Client A connects, attempts authentication against challenge Y. authentication fails (obviously)

In our case, the problem is alleviated by credentials caching: even if a client tries to authenticate against a stale challenge, unless it's the very first time that particular client authenticates, squid will dumbly (but smartly) just accept the authentication it already verified against. The problem remains though: sometimes clients would get rejected for this reason.
To solve this problem, an extension to the squid-helper protocol is needed, because squid and the helpers need to agree and renew challenges only when there are no pending authentications.
In order to do that, Squid and the helpers need to agree on challenge renewal, and that is handled via some more extensions to the squid-helper protocol.

When some helper decides it's time to renew its challenge, it will piggyback to the first answer it sends to squid a request to be taken offline, with the syntax
FLAGS OFFLINE OK domain\user
or
FLAGS OFFLINE ERR reason
or
From that moment on, Squid will stop sending new negotiate requests to that helper. After a while, that helper will have no pending authentications, and Squid will notify the helper that it has no more pending authentications via a
FLAGS REFRESH
message. Note that this will usually prefix the last outstanding authenticate request. At this point the helper may renew the challenge, and it MUST send back Squid a FLAGS REFRESHED or FLAGS NOREFRESH
message flag with the user response. When Squid receives that, it starts feeding requests again to the helper. Note that the helper can send back a indicative response - say REFRESHED before it has actually performed the refresh. As long as the next request from squid is replied to with the new challenge, squid will perform as expected.  
The REFRESH message flag is informational, and might be sent unsolicited. The helper may ignore it, but it MUST answer FLAGS READY anyways.

Resetting

It might happen squid to ask the helpers to reset whatever internal state they might have. It does so by sending a
RESET message, to which the helpers MUST answer with a RESET_OK message. These are not message flags, because they usually indicate something not right in the state information in squid, and it wants a clean slate. Challenge refresh's MAY be done when a reset occurs - squid will drop any cached information before the reset.  

Summary

* The reason for changing the challenge is to reduce replay attack opportunities, not to protect the password per se. If we limit the user to a single IP, the opportunity for unnoticed replay attacks is reduced (whilst  that user is online at least). Equally, given a single sample, there is nothing stopping a malicious user simply trying 1000's of requests anyway as squid currently has no time-delaying mechanism for failed requests from a single username.