## Basic NTLM Protocol

NTLM auth takes three steps:

Client → Server: | Negotiate message
Server → Client: | Challenge message
Client → Server: | Authenticate message

The message header is the same in each step. The packet starts with `"NTLMSSP\0"`, followed by the 4-byte message type (of which only the first byte is significant: 1 for Negotiate, 2 for Challenge, 3 for Authenticate).

The structure definitions below assume x86 conventions: all fields are little-endian. Also, the "`max_len`" fields always contain the same values as their corresponding "`len`" fields. The distinction is presumably historical.

### The Negotiate message

In Samba, this looks like this:

    struct {
            char    protocol[8];     // 'N', 'T', 'L', 'M', 'S', 'S', 'P', '\0'
            guint32 type;            // 0x00000001
            guint32 flags;           // 0x0000b203

            guint16 dom_len;         // NT domain name length
            guint16 dom_max_len;     // NT domain name max length
            guint32 dom_off;         // NT domain name offset

            guint16 host_len;        // local workstation name length
            guint16 host_max_len;    // local workstation name max length
            guint32 host_off;        // local workstation offset

            char    host[];          // local workstation name (ASCII)
            char    domain[];        // NT domain name (ASCII)
    };

The request `xntlm_negotiate()` creates is slightly different from this: we pass `0x00008206` for the flags, `0` for all of the domain and hostname lengths and offsets, and two more "`len`, `max_len`, `offset`" pairs (with lengths `0` and offset `0x30`). I don't know exactly what that all means.

The meanings of the flags, from http://www.opengroup.org/comsource/techref2/NCH1222X.HTM::

    #define NTLMSSP_NEGOTIATE_UNICODE     0x0001  // Text strings are in unicode
    #define NTLMSSP_NEGOTIATE_OEM         0x0002  // Text strings are in OEM
    #define NTLMSSP_REQUEST_TARGET        0x0004  // Server return its auth realm
    #define NTLMSSP_NEGOTIATE_SIGN        0x0010  // Request signature capability
    #define NTLMSSP_NEGOTIATE_SEAL        0x0020  // Request confidentiality
    #define NTLMSSP_NEGOTIATE_LM_KEY      0x0080  // Generate session key
    #define NTLMSSP_NEGOTIATE_NTLM        0x0200  // NTLM authentication
    #define NTLMSSP_NEGOTIATE_LOCAL_CALL  0x4000  // client/server on same machine
    #define NTLMSSP_NEGOTIATE_ALWAYS_SIGN 0x8000  // Sign for all security levels

`NTLMSSP_NEGOTIATE_LOCAL_CALL` is a no-op if the client sets it (which Samba does). If it's set in the server's response it means that the client and server are on the same machine. The `0x06` at the end of the flags says we only support 8-bit ("OEM") encoding (which means we don't have to gratuitously convert the username to UTF-16), and we want the server to tell us its auth realm, which is very useful to us because otherwise we generally don't know it.

### The Challenge message

The server's response to the negotiate packet looks like:

    struct {
            char    protocol[8];     // 'N', 'T', 'L', 'M', 'S', 'S', 'P', '\0'
            guint32 type;            // 0x00000002

    	guint16 dom_len;         // NT domain name length
    	guint16 dom_max_len;     // NT domain name max length
            guint32 dom_off;         // NT domain name offset (always 0x0030)

            guint32 flags;

            char    nonce[8];        // nonce
            char    zero[8];

    	guint16 data_len;        // length of data following domain
    	guint16 data_max_len;    // length of data following domain
            guint32 data_off;        // offset of data following domain

    	char    domain[];        // NT domain name

            // The following piece occurs multiple times
    	guint16 type;            // Type of this data item
    	guint16 length;          // Length in bytes of this data item
    	char    data[];          // Data
    	...
    };

The flags basically echo the request flags, but may also contain:

    #define NTLMSSP_TARGET_TYPE_DOMAIN  0x10000 // Server is a DC/AD
    #define NTLMSSP_TARGET_TYPE_SERVER  0x20000 // Server is just a server

Our server returns `0x00818206`. I'm not sure what the `0x008000000` means.

`xntlm_parse_challenge()` extracts the `nonce`, to be used as described below. The `domain` field contains the NT domain name of the server, which is also needed for the response packet.

The additional data item types are:

`0x01` | WINS name of server (eg, `SHREWDNESS`)
`0x02` | NT domain name (eg, `XCS`)
`0x03` | DNS name of server (eg, `shrewdness.xcs.ximian.com`)
`0x04` | Windows 2000 domain name (eg, `xcs.ximian.com`)

However, they may occur in any order. Note that they're returned in Unicode (UTF-16LE) even though we said we don't speak Unicode. The packet is terminated by an item with type and length `0`.

### The Authenticate message

The final message, generated by `xntlm_authenticate()` looks like:

    struct {
            char    protocol[8];     // 'N', 'T', 'L', 'M', 'S', 'S', 'P', '\0'
            guint32 type;            // 0x00000003

            guint16 lm_resp_len;     // LanManager response length (always 0x18)
            guint16 lm_resp_max_len; // LanManager response max length
            guint32 lm_resp_off;     // LanManager response offset

            guint16 nt_resp_len;     // NT response length (always 0x18)
            guint16 nt_resp_max_len; // NT response max length
            guint32 nt_resp_off;     // NT response offset

            guint16 dom_len;         // NT domain name length
            guint16 dom_max_len;     // NT domain name max length
            guint32 dom_off;         // NT domain name offset (always 0x0040)

            guint16 user_len;        // username length
            guint16 user_max_len;    // username max length
            guint32 user_off;        // username offset

            guint16 host_len;        // local workstation name length
            guint16 host_max_len;    // local workstation name max length
            guint32 host_off;        // local workstation name offset

            guint16 session_len;     // session key length
            guint16 session_max_len; // session key max length
            guint32 session_off;     // session key offset

            guint32 flags;           // 0x00008201

            char    domain[];        // NT domain name (UCS-16LE)
            char    user[];          // username (UCS-16LE)
            char    host[];          // local workstation name (UCS-16LE)
            char    lm_resp[];       // LanManager response
            char    nt_resp[];       // NT response
    };

It seems to always be acceptable to leave "`host`" blank.

The LanManager and NT responses are computed from the user's password and the `nonce` from the Challenge message using an arcane series of computations too dull to get into here. UTSL.

## NTLM over HTTP

IIS abuses the HTTP auth mechanism slightly for NTLM. The important bits are:

1. The HTTP connection must be kept open during the auth exchange.

2. If the connection is closed, you have to start over. You can't just present the reponse packet again.

3. Once you've successfully authenticated, the connection remains authenticated until it's closed, without you needing to keep sending the `Authorization` header. (Normally, you authenticate only single requests, not entire connections.)

Certain HTTP proxies will break NTLM authentication, presumably by not allowing persistent connections. In these cases, the user will have to use "Plaintext Password" authentication (which uses the HTTP Basic auth mechanism).

IIS also supports a third auth mechanism, "Negotiate", which is based on RFC 2478. It's basically SASL inside GSSAPI. It presumably allows you to use GSSAPI-based Kerberos 5 authentication. Since this is standards-based, we could theoretically support it. However, GSS is a big mess of ASN1 encoded gunk, so it would probably really suck a lot.

Each of the three auth mechanisms can be turned on and off independently on the server (on a per-user basis even). We know that there are sites that don't allow Basic, and sites that only allow Basic.

It is possible for `/exchange` and `/public` to have different settings. (It's theoretically possible for one to allow only Basic and the other to allow only NTLM, which Connector would not like very much.)

There are a handful of methods for which IIS does not return a 401 when it should:

POLL | 207 Multi-Status with a 409 Conflict inside
BPROPPATCH | 207 Multi-Status with a 401 Unauthorized inside
PUT to `sendmsg` URI | 404 Not Found

## NTLM over LDAP

Meanwhile, Active Directory (and presumably Exchange 5.5 as well) abuses LDAP auth somewhat to support NTLM. RFC 2251 says:

            BindRequest ::= [APPLICATION 0] SEQUENCE {
                    version                 INTEGER (1 .. 127),
                    name                    LDAPDN,
                    authentication          AuthenticationChoice }

            AuthenticationChoice ::= CHOICE {
                    simple                  [0] OCTET STRING,
                                             -- 1 and 2 reserved
                    sasl                    [3] SaslCredentials }

            BindResponse ::= [APPLICATION 1] SEQUENCE {
                 COMPONENTS OF LDAPResult,
                 serverSaslCreds    [7] OCTET STRING OPTIONAL }

            LDAPResult ::= SEQUENCE {
                    resultCode      ENUMERATED {
                                 success                      (0),
                                 ...
                                 other                        (80) },
                    matchedDN       LDAPDN,
                    errorMessage    LDAPString,
                    referral        [3] Referral OPTIONAL }

First, the client sends a `BindRequest` with "`NTLM`" for the name and an `AuthenticationChoice` with a tag value of `10` followed by the NTLM request packet in an `OCTET STRING`. The server responds with a `BindResponse` containing the challenge packet in the `matchedDN` field. The client then sends another `BindRequest` with no name and an `AuthenticationChoice` of `11` followed by the response packet, and the server (hopefully) responds with a successful `BindResponse`.

This is implemented in Connector by `E2kGlobalCatalog`.