\chapter{The Problem}

The fundamental aim of my research project is to document the addition
of Kerberos KDC%
\footnote{In Kerberos, the KDC (Key Distribution Center) forms the core of the
Kerberos authentication system. Users `log in' with a request to the
KDC, and the KDC stores (or has access to) all the passwords.%
} support to the early implementation of Active Directory Domain Controller
compatibility in Samba version 4.0. 

This is an area of great collaboration, especially between members
of the Samba Team\citep{samba-team}, and forms the culmination of
over 3 years personal effort as a member of that team. In researching
this thesis, I have been working on Samba4 since May 2004, and developed
the authentication and GENSEC security subsystems (described in Section
\ref{sec:GENSEC}) as well as bringing some of my previous work into
the Samba4 framework.

This thesis contributes a solid documentary basis for the work going
forward, as well as specific forward development in the Kerberos area. 


\section{Building blocks:}

This research is based on a solid foundation, utilizing ideas and
implementations found within the following Open Source software packages.

\begin{lyxlist}{00.00.0000}
\item [Samba3]A production, NT4 replacement DC (Domain Controller)
\item [Samba4]The new development branch of Samba\citep{vlsamba4} 
\item [Heimdal~Kerberos]A Kerberos 5 implementation with a pluggable back-end
system. 
\end{lyxlist}
This thesis also builds on my previous research project, into a Windows
compatible Virtual Private Networking solution\citep{comp3700}.


\section{Samba4 Progress}

The Samba4 project started as an effort to rewrite Samba in a way
that would allow such functionality - and it included a completely
rewritten DCE-RPC (Remote Procedure Call) library. The development
effort in creating this system has created the infrastructure\citep{vlsamba4}
upon which an Active Directory compatible DC is entirely possible.

In developing Samba4, \citet{tridge} demonstrated the ability to
join a Microsoft Windows XP Professional client to a Samba4 domain;
however this process had not been independently reproduced. In Section
\ref{sec:Domain-Join} I proceed to reproduce this in my test environment. 


\section{Targeting Active Directory}

In developing the new Samba4 infrastructure, the Samba Team decided
to implement calls in the same way as Microsoft Windows 2003 Server.
This decision is in line with a policy the Samba Team has consistently
followed: to emulate the latest versions of Microsoft's products wherever
possible. Because other software vendors test against the latest Microsoft
releases, and because the latest Microsoft release is the only `standard'
we can reference, we must emulate that very closely.

This policy has been hampered in recent years by the significant changes
made by Microsoft in developing Active Directory.  The Samba and IBM
Blue Directory research teams%
\footnote{The work of this research team is described in Section \ref{sub:blue dir}.%
} determined that emulating parts of Windows 2000 would cause the client
to assume Samba implemented other parts of the system. Since Active
Directory is a fundamental part of the Windows 2000 (and later Windows
2003) architecture, this created an `all or nothing' problem.

The Samba Team, lead by \citet{tridge}, decided to remedy this problem
in Samba4 by simply implementing the missing components.


\section{Kerberos}

The introduction of Kerberos with Windows 2000's Active Directory
was the biggest change in Windows authentication since the introduction
of Microsoft Windows NT. Seen as a fundamental shift away from pure
password-based authentication schemes, the migration to Kerberos allowed
Microsoft to adopt an  industry-standard, extensible authentication
system, with far more flexibility in implementation.

Though Kerberos, an industry-standard authentication system, was developed
for Unix-like systems, Samba3 made very limited use of Kerberos. Since
Samba3 mirrored the un-kerberized NT4 almost all respects, users in
a Samba3 domain were unable to enjoy all of the advantages Kerberos
offers. Recent work has allowed Unix-like clients to use Kerberos
in such domains\citep{sambaheimdal}, but Windows clients are still
stuck with Microsoft's proprietary NTLM\citep{davenportntlm}%
\footnote{NTLM is an authentication scheme, described in Chapter \ref{cha:NTLM}}.

NT4 is now a legacy technology\citep{nt4eol}, despite the number
of sites still running NT4 on both the client and the server. Therefore,
the challenge is to emulate a much more recent version of Microsoft's
offerings.

Because Kerberos is such key change in Active Directory, and because
of the lack of documentation for NTLM, this thesis looks at the authentication
problem in considerable detail.


\section{More than had been done before }

Support for the CIFS%
\footnote{CIFS is a network file-system, formerly known as SMB, that I
  describe in section \ref{sec:CIFS}}
 protocol is clearly a characteristic element
of Samba, but in Samba4 this is extended: Samba4 moves beyond CIFS to expose DCE RPC%
\footnote{DCE-RPC is a Remote Procedure Call system, i.e. a system that invokes
functions over a network, to perform distributed computing. This is
 described in section \ref{sec:DCE-RPC}}
 over non-CIFS transports, such as directly on TCP/IP. 

In previous versions of Windows, DCE RPCs were principally made over
named pipes pipes, a concept existing in the file-system and shared
between hosts by the CIFS file-sharing protocol. The change with Windows
2000 is that RPC became available directly on TCP/IP sockets.

In the same way that Samba must support the newer DCE-RPC over TCP,
this thesis shows how Kerberos is added to the protocols that Samba4
supports, and to create patches to other projects to allow them to
cooperate with Samba4 in implementing this.


\part{Background}


\chapter{Introducing Active Directory}


\section{What is a directory server?}

Directory servers are becoming a core component of most corporate
networks: the central store for information about every computer and
user as well as the basis for the network login system.

Directory servers are available from a number of vendors, and in their
most basic form consist of key-value lookups on structured information.
This information is often organised into a hierarchy.

The predominant directory access technology in use today is LDAP\citep{whatisldap,rfc2251},
a descendant of the X.500 directory standard from the International
Telecommunication Union (ITU), and a component of the full OSI networking
stack.\citep{X.500-LDAP,Understand-X.500}.


\section{What is Active Directory?}

Active Directory is many things to many people:


\subsection{Standards-based directory server}

To those in institutions who care about such things, Active Directory
is a standards-based (and in some ways standards-compliant) directory
system, with access made possible by protocols such as LDAP and Kerberos.
Both of these protocols provide views onto the directory, and the
internal database appears to be a X.500 data model of some kind (but
is not exposed to the outside world directly, only via LDAP).

By leveraging this standards base, Microsoft has been able to claim
interoperability with other vendors. Unfortunately this is a one-way
process, with Active Directory at the core, and other systems using
Internet Standards to reference that data. 


\subsection{Proprietary directory server}

While Microsoft has claimed compatibility with LDAP and Kerberos (being
Internet standard technologies) to potential customers, a truthful
analysis of how Microsoft's own clients use the AD system will show
that this is for the benefit of others much more than Microsoft's
own clients. The technology Microsoft uses for client-server communication
is remote  procedure calls (RPC). The use of RPCs in Windows networking
has grown significantly since NT4.

These calls are not documented, even though the basic transport for
them is DCE/RPC, for which documents and a reference implementation
are available from The Open Group\citep{opengroupdce}. This documentation,
however, does not address the format of individual calls that the
client will make.

Much of the challenge of Samba4 is the continued task of `network
protocol analysis', the art of determining the operation of a proprietary
network protocol by examining network operations\citep{tridge-net-analysis}. 


\subsection{Simple directory server}

To small organisations, Active Directory is a system with which a
Windows network can be administered from a single, simple, GUI interface.
An Active Directory network may use LDAP and Kerberos, but these users
simply do not need to know or care about this.


\chapter{Active Directory Protocols}

Looking at Active Directory from the ground up, it is clear that a
large number of network protocols are involved. Many of these are
Internet standards, or widely understood, but others are proprietary. 


\section{CIFS}

\label{sec:CIFS}CIFS\citep{mind,hertel,sniacifs}, perhaps the most
important protocol in the Microsoft networking landscape, dominates
the connections made between almost all clients and servers on a Windows
network. Expanded, CIFS stands for the Common Internet File System,
but the name only really tells us that it is a network file-system.
Being a network file-system, files are shared over it, but unlike
other network file-systems CIFS also presents printing and 
an Inter-Process Communication (IPC) interface. Accordingly CIFS carries
much of the network activity in an Active Directory implementation.


\subsection{CIFS, SMB and NetBIOS}

There is much confusion and contradictory terminology in the area
of CIFS networking. Originally SMB (Server Message Block), CIFS
sits on top of the complete NetBIOS stack of services. Both of these
are quite sufficient to fill a book,%
\footnote{Chris's Hertel's Implementing CIFS\citet{hertel} is a very good reference
on the topic%
} but it is important to note that SMB and NetBIOS has historically
run over IPX, DECNet and NetBEUI as well as TCP/IP.


\subsection{CIFS as an IPC mechanism}

CIFS exports the concept of `named pipes' - a system for Inter-Process
Communication (IPC) over the network, making CIFS a transport layer
to RAP%
\footnote{The Remote Administration Protocol (RAP) was implemented in LAN Manager,
OS/2 and subsequently Windows NT but is now largely replaced by DCE-RPC.%
} and DCE-RPC in particular. This is unusual in networking, because
both local and remote IPC are conducted in a very similar way, abstracting
away many of the usual concerns. Because this CIFS transport layer
is authenticated, and because CIFS (then SMB) ran over these multiple
network layers, applications need not deal with either of these network
transport issues.

Only with the release of Windows 2000 did Microsoft directly use TCP/IP
as an IPC transport layer, in domain logon services.


\section{LDAP}

The Lightweight Directory Access Protocol (LDAP)\citep{rfc2251,rfc2252,rfc2253,rfc2254,rfc2255,rfc2256}
has become the Internet standard for access to structured information,
in particular information in the format of an X.500-like tree. Active
Directory exports much of its information in the form of an LDAP tree,
and a wide variety of tools are available to query and in some cases
modify that information.


\section{Connectionless LDAP}

CLDAP (Connectionless LDAP) originally was an Internet standards-track
proposal to allow LDAPv2 queries over UDP, a process that may be useful
for service discovery. Microsoft implements CLDAP, but they do not
follow the proposed standard, instead creating a version of CLDAP
based on LDAPv3. As will be discussed in Section \ref{sub:CLDAP},
Microsoft's CLDAP has become nothing more than an Internet Protocol
transport for a proprietary blob of data. However, the implementation
of Microsoft compatible CLDAP is important, because it forms a critical
role in DC and domain location.


\subsection{Sites}

Sites are a concept closely tied to CLDAP and DNS - workstations will
try to use servers found at their own site, rather than one further
away (over potentially expensive WAN links). The CLDAP reply includes
information on sites, and clients can use this, as well as packet
timing information, to determine which DC to use.


\section{DCE-RPC}

\label{sec:DCE-RPC}DCE-RPC is a long-established standard for the
operation of Remote Procedure Calls (RPC), and is published free of
charge by the Open Group\citep{opengroupdce}. However, the complexity
in DCE-RPC is not in the transport or basic operation (not that the
difficultly in writing a DCE-RPC marshaling and control library should
be underestimated), but in the proprietary security mechanisms and
interface definitions.


\subsection{Interface Definitions}

Each function exposed over DCE-RPC has an associated interface
definition, written in the Interface Definition Language (IDL), and if
you were to make a particular interface public, all you would need to
do is publish the IDL file.  This is the same IDL file that you would
compile yourself to create the initial framework and library on which
you build your own client or server.

One of the big changes in Samba4 is PIDL, our own IDL compiler, detailed
in Section \ref{sec:PIDL---Midl}.


\subsection{DCE-RPC Security}

NTLMSSP (described in Section \ref{sec:NTLMSSP}) and Schannel (a
similar security scheme between member workstations and domain controllers)
are the two predominant security mechanisms applied to DCE RPC in
a Microsoft environment, and both are considered proprietary by Microsoft.
Fortunately there is a growing body of documentation on both, built
up by independent researchers and the Samba Team. With the introduction
of Active Directory, Kerberos also becomes available for DCE RPC.
In all these cases the mechanism authenticates clients (by means of
an authenticated `bind') and can secure the traffic as it passes over
the network. 


\subsection{Transports}

DCE-RPC describes not only the format for the function calls, but
also a number of network transports. The predominant network transport
used in Windows networking is \texttt{ncacn\_np} - the acronym is
unimportant, but it means `Named Pipes' and this file-system concept
is carried over CIFS to remote servers. Other transports include:

\begin{lyxlist}{00.00.0000}
\item [\texttt{ncacn\_ip\_tcp}]DCE-RPC over TCP/IP
\item [\texttt{ncadg\_ip\_udp}]DCE-RPC over UDP/IP
\item [\texttt{ncacn\_http}]DCE-RPC over HTTP
\end{lyxlist}

\section{DNS}

Active Directory provides and uses an extensive amount of information
in DNS, particularly based around the new SRV record type. Under the
\texttt{\_msdcs} sub-domain, Microsoft stores information about each
of the domain controllers on the network, both by DC name and more
importantly by the network service they provide. 

Microsoft has devised their own secure update scheme for DNS, based
around Kerberos. This allows machines to update their own entry in
the DNS server.


\section{SNTP}

The Simple Network Time Protocol (SNTP) is an Internet Standard time
protocol, and is used extensively in ADS domains to keep accurate
time. Each domain controller runs a time server, and in an ideal network
is synchronised with an upstream time server. In an interesting extension
to SNTP, Microsoft signs the time responses with the schannel security
scheme. This allows a secure bootstrapping to the correct time, needed
for correct Kerberos operation.


\chapter{Authentication}


\section{Authentication problems}

Authentication is about proving identity - proving that a particular
person is who they claim to be, proving that a particular endpoint
on a network is legitimately allowed to operate as a particular account.
There are many issues surrounding the connection between a user and
their network identity: enough certainly for a research paper in and
of itself\citep{rogerclarkauth}. For the purpose of this discussion,
a user will be considered to be the entity holding the password to
an account. Likewise, a server is the entity that answers on a particular
network address, and may hold its own server account details.


\subsection{Who you are}

The most common operation in the authentication area is proving a
user's identity. In a common example, a logged on user would say,
`only I should be able to get at my mailbox'. This is an easy problem
to solve in the abstract: you simply prove who you are, and proceed
with other operations. Performing this operation in a manner that
is secure to attack is difficult, however.


\subsection{Who they are}

One of the less-considered, but equally important matters in the authentication
space is the authentication of peers. It is readily accepted that
the user must prove their identity to a server, but with a few exceptions
(mostly involving `secure' websites), users do not expect a server
to prove its identity to them.

Proof of server identity is a very important issue, as soon as any
of the information given by that server needs to be trusted. Often
called `mutual authentication', a solution to this problem ensures
that the server is `trusted' not to provide malicious data, such as
an invalid address book, and that it will behave properly with information,
such as credit card numbers, given to it.


\subsection{Data integrity}

Once the identity of a server or client has been established, there
must be some way to ensure that only that server or client can continue
to communicate with the other. Otherwise, it may be possible for an
impostor to take over a connection and impersonate one party to the
other. This connection hijacking could allow unauthorized access to
privileged documents, or server administration functionality.

The practice of data integrity, also known as `signing', typically
involves a cryptographic calculation where both sides can prove that:
could only be performed by the other, and could only have been performed
over the data received. If the signature (the output of that calculation)
is invalid, the message must be considered compromised.


\subsection{Data encryption}

Whenever data flows over a communications network, it becomes open
to attacks simply by observation. Should a user's password be sent
in clear-text, an attacker could use it to later log in as that user.
Likewise, if a confidential document were retrieved, an attacker in
a position to watch the network traffic could also read that document. 

The practice of data secrecy, also known as `sealing', `privacy' and
`confidentiality', involves the encryption of specific data portions,
or the entire communications channel, such that only the other party
can decrypt it.


\section{Authorization problems}

The problem of authentication and the problem of authorization are
often lumped together, and this is certainly the case in Active Directory.
However, we first need to consider them apart.

Once a user is authenticated (they are who they claim to be, or more
simply they know the password to the account), a decision needs to
be made as to what resources they may access: what files may they
read/write, what hosts may they login to? This process is authorization,
and even extends to such ideas as impersonation: a user may be authorized
to impersonate another user.

The tempting thing to do when designing real-world systems it to embody
a great deal of authorization information in the authentication process;
information such as group membership may be returned as a product
of the login process, and even evaluated to determine if an authentication
attempt should succeed. This is frowned upon because it links the
two processes very tightly: preventing a single authentication identity
from having multiple authorization identities. That said, the two
are linked (as they are in AD) for reasons of network efficiency. 


\section{Authentication Schemes}

There are a large number of theoretical and practical ways to establish
identity. Almost all rely on some degree of cryptography to secure
the login process.


\subsection{Plain-text Authentication}

Certainly the easiest form of authentication to explain and implement,
plain-text authentication turns up all over the modern networking
world, from the typical use of HTTP Basic authentication\citep{httpauth}
and HTTP form-based authentication to `LDAP authentication', found
inside many corporate networks. Typically, these are not protected
by a transport layer security (a security mechanism that protects
the entire stream, not just the passwords), and are otherwise clear
on the network. If the remote server is not somehow authenticated,
it could maliciously indicate successful authentication or steal the
passwords.


%
\begin{figure}
\includegraphics[%
  width=0.80\columnwidth,
  keepaspectratio]{dia/SMB11}


\caption{\label{fig:Challenge/Response}Challenge/Response}

\begin{quote}
The server generates a random challenge, which it sends to the client.
Both systems encrypt the challenge using the secret encryption key.
The client sends its result (rc) to the server. If the client's result
matches the server's result (rs), then the two nodes have matching
keys. (Image and text (c) Chris Hertel\citep{hertel}, \url{http://www.ubiqx.org/cifs/figures/smb-11.html})\end{quote}

\end{figure}


\subsection{Challenge-response Authentication}

Challenge-response authentication is typically a shared-secret scheme,
where both parties to the authentication exchange have a copy of the
password, or a fixed derivative thereof. As shown in Figure \ref{fig:Challenge/Response},
the server generates a random `challenge' to the client, and asks
the client to perform a fixed operation with inputs consisting of
the `challenge', the user's password, and possibly some random data
of the client's choosing. 

The result of this operation should not in any way disclose the user's
password, and should be repeatable on the server. Figure \ref{fig: challenge-response-block}
shows how, when the server repeats the operation using its copy of
the password, it compares the output with the value supplied by the
client. If the values match, the client must know the user's password.

%
\begin{figure}
\includegraphics[%
  clip,
  width=0.50\paperwidth,
  keepaspectratio]{challenge-response-blocks}


\caption{\label{fig: challenge-response-block}The server must compare it's
calculated result with the one supplied by the client}
\end{figure}


NTLM (described in chapter \ref{cha:NTLM})and Kerberos (described
in chapter \ref{cha:Kerberos}) are both challenge-response authentication
schemes, and are both used extensively in Active Directory. However,
Kerberos has important other properties that make distributed operation
far more secure than NTLM, an area discussed in section \ref{sec:Distributed-NTLM}.


\subsection{Trusted Third Party Authentication}

Many distributed authentication systems allow logins to occur on numerous
hosts, but only a few hosts (possibly one) actually confirm or deny
an authentication request. These are trusted third party systems;
all hosts trust those with the passwords (the third party in the authentication
exchange) to correctly return authentications success or failure.

For an authentication system to be secure, it must be possible to
trust this third party, preferably by some cryptographic proof. Often
this is by yet another shared-secret authentication scheme. 


\subsection{Single Sign On}

Often abbreviated as simply SSO, the concept of Single Sign On is
a matter of usability; users wish to establish their identity once,
and not have to think about it after that. This allows for more complex
authentication procedures as the user only has to tolerate them once
per session. SSO has become the expectation in modern network environments.


\chapter{NTLM}

\label{cha:NTLM}


\section{NTLM Challenge Response}

NTLM is a challenge-response authentication scheme, designed to prevent
a direct compromise of the user's password as it passes from client
to server. In theory, the value that the client gives the server can
only be generated with knowledge of the password, but does not reveal
the password itself. 

More importantly, this authentication scheme has a direct heritage
back to the early days of the CIFS (then SMB) networking suite, with
much of the weakness in it as an authentication scheme linked to backward
compatibility. It is the ubiquitous authentication scheme in Windows
networking, and even with Windows 2000 is the transparent fall-back
option if and when Kerberos fails to operate in a particular environment.


\subsection{Shared Secrets and Hashing}

NTLM is a shared secret authentication scheme. The shared secrets
are hashed (passed though a one-way-function), so as not to be the
original plain-text password, but still password equivalent for the
purpose of challenge-response authentication. As is implied by the
name, the shared secrets are stored on disk on the Server, and derived
from the password typed in by the user.

There are two password hashes in NTLM, known as the NT hash (introduced
with Windows NT) and the LM or LANMAN hash (compatible with LAN Manager) are
16 byte quantities\citep{userauthNT}


\subsubsection*{Calculating the LM Hash}

\label{sub:Calculating-the-LM}The LM hash is constructed from the
uppercase, ASCII version of the user's password. 

The password is truncated/NULL padded to 14 ASCII characters%
\footnote{Implementations should not store/disable any LM password created from
more than 14 ASCII characters, as use of this password would compromise
the additional length.%
}, and split into two 7 byte halves. Each half is used as a key to
encrypt the constant string {}``KGS!\%@\$\%''. To the extent that
DES is a strong encryption function\citet{appliedcrypto}, neither
knowledge of this `plaintext', nor the encrypted output allows one
to find the key. Therefore this is a one-way hash function. 

The function is (in pseudocode, C-style 0 based arrays):

\begin{lyxcode}
part1~=~DES(upper(password{[}0-6{]}),~\char`\"{}KGS!\%@\$\%\char`\"{})

part2~=~DES(upper(password{[}7-13{]}),~\char`\"{}KGS!\%@\$\%\char`\"{})

LMhash~=~concat(part1,~part2)


\end{lyxcode}
The fact that the password is constructed in two halves (as well as
properties of the LM challenge response function below) creates a
cryptographic weakness in the security of LM challenge-response authentication.
This is discussed in Section 2.8.3.5 of Implementing CIFS\citep{hertel},
but in short, the password's length (less than, equal to or greater
than 8 characters) is exposed in the final output.


\subsubsection*{Calculating the NT Hash}

The NT hash is much stronger, and quite simply created:

\begin{lyxcode}
NThash~=~MD4(unicode(password))
\end{lyxcode}
Because the NT hash is not composed in parts, and uses the secure
hash algorithm MD4\citep{RFC1320}, it is 128 bits in strength. It
is also Unicode, allowing for a wider variety of passwords, particularly
in languages other then English. Most importantly however, it is mixed
case, lacking the forced uppercase step of the LM hash.


\subsection{LM Challenge Response}

Sharing the secrets is only one half of a shared-secret based authentication
scheme - the more important half is securely proving that you know
that secret. This is where the LM challenge-response scheme comes
in, with another round of DES applied to either the NT or LM hash.
This process is discussed in detail, including an example implementation,
in Section 2.8.3.4 of \citet{hertel}, but is summarised here.

The server generates an 8 bytes cryptographic challenge (the LM
challenge), consisting of random data.

The LM response takes successive 7 byte parts of the NT or LM hash,
and uses them to encrypt that LM challenge:

\begin{lyxcode}
resp1~=~DES(hash{[}0-6{]},~chall);

resp2~=~DES(hash{[}7-13{]},~chall);

resp3~=~DES(concat(hash{[}14-15{]},~zeros{[}5{]}),~chall);

resp~=~concat(resp1,~resp2,~resp3);
\end{lyxcode}
The 24 byte response (8 bytes from each DES operation) is then sent
over the network, proving to the server that the client knows the
NT or LM hash, and presumably therefore the password. This is known
as the LM response when based on the LM hash, and the NTLM response
when based on the NT hash.

The LM challenge-response function sufferers from a number of flaws,
but the most easily understood is that it is 56 bit DES at best. Other
weaknesses (the 7 byte split in the underlying LM response) make it
possible to reverse the calculations in a period of hours on modern
hardware.\citep{l0phtcrack}


\subsection{NTLMv2}

Due to the problems with the security of the NTLM challenge-response
scheme, a new scheme was devised by Microsoft, and became known as
NLTMv2\citep{ntlmv2enable}. Unfortunately a number of other improvements
are also labeled NTLMv2%
\footnote{The improvements labeled as NTLMv2 include the NTLM2 session response
(described in Section \ref{sub:NTLM2-Session-Response}) and NTLMv2
Session Security, which changes the NTLMSSP signing and sealing algorithm,
(described in section \ref{sub:NTLMSSP-Signing-and}).%
}, but we will start by describing the new NTLMv2 challenge-response:

NTLMv2 uses the same NT hash, but instead of the LM challenge-response
formula, a new system based on HMAC-MD5\citet{rfc2104} has been built.
Because the 56-bit (cypher strength) DES step has been replaced by
a 128-bit HMAC-MD5 function, logins can be considered to be protected
by 128 bit security.


\subsection{Session Keys}

As a byproduct of NTLM authentication, a password-derived `session
key' is produced for use in verifying or encrypting data carried between
the client and server. The algorithm used varies depending on the
method of authentication and unfortunately can be very weak - often
a fixed derivative of the user's password! This key is known as the
`user session key', and is used in a number of places within CIFS
directly, as well as by the NTLMSSP suite.


\subsubsection*{LM session key construction}

The LM session key is constructed from the first 8 bytes of the LM
hash, padded to 16 bytes with zeros. Given what we understand about
the LM hash, it is equivalent to the password for passwords of 7 characters
or less!

\begin{lyxcode}
LM\_key~=~concat(head(LM\_hash,~8),~zeros{[}8{]});
\end{lyxcode}

\subsubsection*{NT session key construction}

The NT session key is also fixed derivative of the password:

\begin{lyxcode}
NT\_key~=~md4(NT\_hash);
\end{lyxcode}
Which is also

\begin{lyxcode}
NT\_key~=~md4(md4(unicode(password)));
\end{lyxcode}

\section{NTLMSSP}

\label{sec:NTLMSSP}NTLMSSP is a collection of protocols, which together
fulfil the Microsoft Security Support Provider Interface (SSPI\citep{sspi}).
As such, the NTLM challenge-response steps have been wrapped into
a framework such that a calling application need only know how to
pass these messages, not to understand them. At each end of the connection,
these messages are passed down to the security libraries for processing.


\subsection{NTLMSSP Packets}

Within those messages is a particular packet format, which is known
as NTLMSSP, partly because the ASCII string \texttt{\char`\"{}NTLMSSP\char`\"{}}
prepends every protocol exchange. Three different packets pass back
and forth between client and server:

\begin{lyxlist}{00.00.0000}
\item [Negotiate]The initial packet, sent from the client to the server,
suggesting options (including choice of Unicode or ASCII for future
communication) and requesting an authentication
\item [Challenge]The return packet, containing the LM challenge, and
the server's options (influenced by the client). It may also include
data on the target system's name and domain.
\item [Authenticate]The final packet, containing the user-name, domain
and challenge-response (also known as the encrypted passwords), in
whatever format may have been negotiated.
\end{lyxlist}
The format of these packets, and the meaning of most of the options
carried in them is now reasonably well understood, and partially documented
in an official sense by \citet{opengroupntlm}. Unofficial documentation
includes the comprehensive reference by \citet{davenportntlm} and
the older reference by \citet{javantlm}.


\subsection{NTLMSSP Options}

Within the NTLMSSP context, a different set of session keys, cyphers
and authentication inputs are used - depending on the negotiated options.
The fact that these are negotiated is problematic, but the implementation
may define minimum required options. What follows is a discussion
of some of the options, but a more complete treatment is given by
\citet{davenportntlm}.


\subsubsection*{LM Session Key}

The LM session key is created as specified by \citet{opengroupntlm}:
it is based on the NTLM `LM Key', and includes part of the LM response
(and therefore the server-generated random challenge) in a DES based
hash, making it unique for each session. It is negotiated by the specification
of the \texttt{NTLMSSP\_NEGOTIATE\_LM\_KEY} in the negotiated options.

This key is then 'weakened' to various strengths, to fix export requirements.
The irony is that the 128 bit negotiated key is far from this in real
strength, due to there being at most 56 bits of key input!


\subsubsection*{NT Session Key (v1)}

When the LM\_KEY option is not negotiated, and no other options are
specified, the session key is the NT Key from the NTLM authentication
exchange. This key is 128 bits in strength, but fixed until the user's
password changes. Unfortunately, despite being 128 bits in strength,
the session key's value can be obtained by breaking the 56-bit DES
in the LM response algorithm, so it never provides 128 bits of cryptographic
protection.


\subsubsection*{NTLM2 Session Response}

\label{sub:NTLM2-Session-Response}Another modification to the NTLMSSP
login scheme, this option prevents a server-initiated dictionary attack,
by providing input from the client and server in calculating the challenge
input to the challenge-response function. This option also changes
the session key negotiation to include mutually agreed random data
into the key. This ensures that the session key again changes between
sessions.


\subsubsection*{Key Exchange}

In another modification to the session key negotiation, the specification
of the `key exchange' flag allows the
client to specify a new session key, to be encrypted with what otherwise
would be the session key. Presumably, the client would choose a random
sequence of bytes, unrelated to the password, but as will be noted
in Section \ref{sec:LSAKEY}, the ability for the client the propose a known
session key is an unexpected weakness in the NTLMSSP scheme, particularly
given the steps taken when the NTLM2 Session Response is
selected.  


\subsection{NTLMSSP Signing and Sealing}

\label{sub:NTLMSSP-Signing-and}NTLMSSP provides generic functions
to sign and seal quantities of data, and this is used in DCE-RPC.
Using the session key negotiated between the client and server, a
cipher state is established though which the data is encrypted, or
the signature is generated/verified.

The core of the sign/seal algorithms is alleged to be RC4\citep{RC4FAQ,RC4Page,appliedcrypto}:
an algorithm used repeatedly (and unfortunately often poorly) in many
parts of Microsoft's network server implementation. When negotiating
the newer `NTLM2 Session Security', multiple RC4 sboxs are generated,
one per direction, each using unique subkeys, and checksums are calculated
with the strong HMAC-MD5\citep{rfc2104} checksum. However, when this
is not negotiated the checksum is a only a CRC32 function\citep{crcguide};
weaknesses in this function have been used in the past to break the
security of SSH connections\citep{sshcrc}. 


\section{Distributed NTLM}

\label{sec:Distributed-NTLM}NTLM as so far described has no inbuilt
mechanism for distribution over a network. In short, NTLM assumes
that the server being contacted is also the server holding the passwords.
In order to implement a distributed network architecture, compromises,
which are invisible to the client, must be made at the server. Typically
these are to somehow contact the Domain Controller (DC) to confirm
or deny an incoming user's identity, a process shown in \ref{fig:Trusted-Third-Party}.

%
\begin{figure*}
\includegraphics[%
  width=0.80\columnwidth,
  keepaspectratio]{dia/SMB15}


\caption{\label{fig:Trusted-Third-Party}Trusted Third Party Authentication
(NTLM).}

\begin{quote}
The Domain Controller (DC) wears a special hat. It keeps track of
the common authentication database that is shared by the SMB servers
in the Domain. The SMB servers query the DC when a client requests
access to SMB services. (Image and text (c) Chris Hertel\citep{hertel},
\url{http://www.ubiqx.org/cifs/figures/smb-15.html})\end{quote}

\end{figure*}



\subsection{Pass-though Authentication}

The first, and easiest compromise the server can make is simply to
defer the decision to another server. In pass-though authentication,
optimised by Samba's \texttt{security=server}\citep{samba-3.0-howto-sec-server}
configuration option, the challenge is generated by a remote server,
and the response forwarded to it likewise. The server in the middle,
to which the client wants access, simply assumes that the remote server
will correctly signal authentication success or failure. Such a server
does not gain any additional knowledge, such as session keys, nor
does it have cryptographic proof that the remote server is not in
some way being spoofed.

This mode of operation is particularly fragile, because once a challenge
is retrieved from the remote server, the connection \emph{must} remain
open - a transparent re-connection cannot be made later.


\subsection{NETLOGON}

\label{sub:NETLOGON}The NETLOGON authentication process was introduced
by Microsoft Windows NT to handle this problem in a more secure manner.
Fundamentally, the challenge-response step to the remote server (the
DC) is removed, and instead the DC is presented with both the challenge
and the response. The server in the middle (the member server) gains
in return a set of details about the user: their name, groups and
the cryptographic session keys described above. 

However, this process presents a security exposure - why couldn't
an attacker ask the DC the same question, perhaps with a challenge
and response found by sniffing the network? And why couldn't an attacker
modify the response from the DC to include the `Administrators' group?
This is prevented (on later clients and servers%
\footnote{Windows NT4 with Service Pack 4 and above, Windows 2000 and above
and Samba 3.0 and above.%
}) by the cryptographic signing and sealing of the connection, using
a shared secret between the member server and the DC.%
\footnote{This is a system known as schannel or Secure Channel.%
}

\emph{It is for the purpose of setting up this secret that a machine
'joins' the domain in the first place.}

While modern clients will negotiate, and even require,%
\footnote{Windows XP will not communicate with a Domain Controller that does
not support the schannel scheme for signing and sealing it's connection
to the DC.%
} a level of security in their communication with the DC, another issue
remains very real: the circle of friends that the DC trusts to perform
this operation is very large, extending to each and every workstation
that is a member of the domain, not just the file and print servers.
Any single one of these may perform this logon operation, and obtain
information such as the user's long term session key, or even the
first 8 bytes of their LANMAN password!


\chapter{Kerberos}

\label{cha:Kerberos}


\section{Kerberos Basics}

Kerberos\citep{appliedcrypto} is described as a `trusted third party'
authentication system, based around shared secrets and symmetric cryptography.
The hub of the Kerberos authentication system is the Key Distribution
Center (KDC), which contains a copy of each user's passwords (in very
much the same way a DC or standalone server does for NTLM). Kerberos
is an Internet Standard\citep{rfc1510}, with MIT providing the reference
implementations, used in their Project Athena. In an interesting diversion
from the standards documents, four-part dialogue, describing the system
is available\citep{krb5-dialog}.

Aside from a far superior cryptographic base, the key difference between
NTLM and Kerberos authentication is that the user is given their ticket,
with cryptographic proof of their own identity. The server can verify
that proof with local cryptography, avoiding the need for the server
to contact the KDC in real time. Kerberos also includes mutual authentication,
signing and sealing of data, and is extensible with new encryption
types, something that Microsoft did allow in an upgrade from Windows
NT:


\section{An upgrade compatible encryption type}

\label{sec:type-23-crypto}One of the biggest deterrents to the deployment
of Kerberos at any site is the frightening concept that to do it,
all of the user's passwords must be securely collected, in clear-text,
for hashing into appropriate Kerberos keys. Microsoft knew that it
could not expect this kind of effort in upgrading Windows servers
from NT4 to Active Directory, so they solved it a different way. 

Instead of obtaining the plain-text password, Microsoft used the NT
hash%
\footnote{Previously calculated and stored for use with the NTLM password scheme%
} as the shared Kerberos key, and defined a set of cryptographic operations
around this base. Published as an Internet-Draft \citet{brezac-krb5-draft},
this encryption type has been added to other Kerberos implementations
for the purpose of interoperability.


\section{The PAC}

Kerberos follows a model that describes a strict separation between
authentication and authorization. This is very nice in theory, but
presents some practical difficulties in mapping a Kerberos identity
to a user, and their access rights. In particular, it is the problem
of performing this mapping in a network-efficient manner that caused
the PAC (Privilege Attribute Certificate) and associated infrastructure
to be devised.

The PAC is a cryptographically signed blob of data including information
on a user's groups, their home directory location, and similar details.
This is nothing particularly special, but Microsoft created a storm
by releasing the specification for this data format under a `click-though'
licence, including a Non-Disclosure Agreement (NDA)\citep{westerlundheimdal}.

Subsequently, portions of this data format were released under a much
more liberal licence\citep{mspac}.


\chapter{Security Negotiation}

In what is in many ways an oxymoron, security protocols must be negotiated
between any two peers, to ensure that each site is talking a dialect
(or indeed and entire language) that the other understands. Invariably,
these negotiation protocols are described as simple,%
\footnote{A point made very good fun of by \citet{jra-security-soup}.%
} and provide each side with choice over the desired mechanisms. The
idea of security negotiation is also associated with security fall-back;
if one authentication scheme is unavailable (even without a negotiation
step), the peers may simply attempt an older scheme. This too has
security implications, if an attacker can influence the decision to
fall-back.

Once a mechanism is chosen, it may also perform its own negotiation
steps, as NTLMSSP does with the negotiated flags. 


\section{SASL}

\label{sec:SASL}As far as security negotiation mechanisms go, SASL
is surprisingly sane. SASL succeeds because it is very easy to implement
in almost any protocol: it places no requirement on the use of ASN.1,
and is often trivially placed into text-based Internet protocols such
as IMAP and SMTP. Security mechanisms are advertised and selected
by simple exchange of text strings. By convention (and specified in
standards for each protocol it is actually placed in), the subsequent
exchange of security packets are again simple text strings, by simple
use of base64 encoding.

Away from protocol implementation details, the names of security mechanisms
are associated with particular levels of security. Clients and servers
may place requirements on each other by which mechanisms they support,
but this does not have any network-visible artifacts.


\section{GSSAPI}

Designed as a simple API for access to Kerberos and other security
mechanisms, GSSAPI is both a C programming API, and a network protocol.
Both are reasonably complex, a point exampled well by the way GSSAPI
uses an Object IDentifier (OID) to prefix its network messages. OIDs
are globally unique streams of numbers, delegated out of a hierarchical
name-space, and formatted (as is the case for all of GSSAPI) in ASN.1.
(SASL uses simple text strings for the same purpose, with much clearer
effect).

GSSAPI, like SASL, exchanges datagrams until both sites are happy
with the security result.


\subsection{SPNEGO}

\label{sub:SPENGO}Born out of the need to mutually negotiate a security
mechanism, where both parties may not already know what the other
supports, the Simple and Protected NEGOtiation protocol (SPNEGO) is
a selection mechanism for GSSAPI. It appears in a GSSAPI wrapping,
because on the network it is a GSSAPI mechanism. The server or client
(depending on who `speaks' first) suggests a list of mechanisms, and
the peer responds. If both parties agree on a mechanism, then that
mechanism's exchange can commence. By anticipating that choice, the
exchange for one of these mechanisms can be started in the negotiation
phase, providing less round trips.

SPNEGO is interesting because it is used by Microsoft to select between
Kerberos and NTLMSSP, and is the basis for their `Negotiate' SSPI
security mechanism. Microsoft also broke their implementation of SPNEGO,
by removing the integrity protection. (This allows an attacker to
modify the list of protocols being exchanged, to force a selection
of a less secure protocol).


\chapter{The Join process}


\section{Purpose}

The purpose of the `domain join' is to securely setup a password (shared
secret) between the workstation (or member server) and the domain
controllers, so it may use the NETLOGON mechanism described in \ref{sub:NETLOGON},
and the Kerberos system described in \ref{cha:Kerberos}. This is
done by a privileged user, who has the right to specify that a new
machine account be added to the domain. At the conclusion of this
process, both the workstation and the domain controllers know the
password, and can use this value to prove to each other that they
are indeed authentic. 


\section{Process and Tools}

In this example, a WinXP Professional, Service Pack 2, virtual workstation
is joined to Active Directory, hosted on Windows 2003 Advanced Server.
The workstation is a virtual machine running under VMWare \citep{vmware},
and is known in this process as \texttt{WINXP1}. The domain it is
joining is \texttt{WIN2K3.THINKER.LOCAL} with \texttt{WIN2003.WIN2K3.THINKER.LOCAL}
being the Windows 2003 Domain Controller (DC). The \texttt{Administrator}
user is used to join the machine to the domain, which also has a short
name of \texttt{WIN2K3THINK}. This was monitored%
\footnote{Because both the WinXP and Windows 2003 machines are running under
VMware (which itself is run on Linux), the whole process can be monitored
by listening on the virtual Ethernet hub that VMware provides. %
} and analysed with the assistance of Ethereal \citep{ethereal}, which
produced the packet capture diagrams.


\section{Initial Join}

The join process is initiated by selecting `Change' from the `Identity'
tab of the `System' control panel, on the WinXP client. This presents
a very simple interface, shown in Figure \ref{fig:The-Join-Dialog}.

%
\begin{figure}
\includegraphics[%
  clip,
  width=1.0\columnwidth]{screens/join-win2k3}


\caption{\label{fig:The-Join-Dialog}The Join Dialog}
\end{figure}



\subsection{DC Location}

The first part of the domain join process is to locate a Domain Controller
(DC) to join. This involves both DNS and CLDAP, if available.


\subsubsection*{DNS}

Microsoft has defined a number of expected DNS names, under the \texttt{\_msdcs}
sub-domain, containing SRV records, for service location. The first
assumption for a domain join is that the domain exists as a DNS name,
with \texttt{\_ldap.\_tcp.\_msdcs.} prepended.

%
\begin{figure}
\includegraphics[%
  bb=20bp 520bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-dns-lookup}


\caption{Initial DNS Lookup}
\end{figure}



\subsubsection*{CLDAP}

\label{sub:CLDAP}Connectionless LDAP is used as an `Internet Standard'
transport for Microsoft's proprietary domain controller location protocols.
While CLDAP would be an ideal mechanism for this purpose, it has been
mangled into not much more then a wrapper for a proprietary network
structure in the form of the \texttt{netlogon} attribute. Information
about the machine attempting to locate the domain is included as an
LDAP filter, and is sent to hosts appearing in the DNS reply. Part
of the purpose of this process is to easily eliminate bad DNS data
from the following processes: only those servers that send a reply
to the UDP based CLDAP need be considered for further connection attempts.

%
\begin{figure}
\includegraphics[%
  bb=20bp 510bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-cldap-lookup}


\caption{Initial CLDAP Lookup}
\end{figure}


%
\begin{figure}
\includegraphics[%
  bb=20bp 270bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-cldap-reply}


\caption{Initial CLDAP Reply}
\end{figure}


The Netlogon CLDAP reply includes a large amount of detail about the
server, its basic operating details and in particular the site at
which it is located. Windows clients in an Active Directory domain
can use the site information to restrict operations to domain controllers
located at the same physical site as the client, avoiding stress on
often comparatively slow WAN links.


\subsubsection*{NetBIOS Lookups and NetBIOS GetDC}

If a DNS name is not found, an NT4 style NetBIOS lookup can be performed,
looking for the \texttt{WIN2K3THINK\#1c} NetBIOS name, and using the
result in the same way as the DNS result is used above. Likewise,
a GetDC request (this time encapsulated in the NetBIOS mail-slot protocol),
will return the same proprietary blob of information regarding the
domain.


\subsection{Asking for a password}

Now that the Domain and Domain Controllers have been located%
\footnote{In particular, this step ensures that the domain exists, and the user
has not made a typographical error%
}, the user is prompted for a password, shown in Figure \ref{fig:admin-password-prompt}.
This is the last thing a user sees before the process is completed,
only a few seconds later. From here on, we can only observe progress
by watching the network traffic.

%
\begin{figure}
\includegraphics[%
  clip,
  width=1.0\columnwidth]{screens/join-win2k3-password}


\caption{\label{fig:admin-password-prompt}Prompting for a password}
\end{figure}



\subsection{CIFS Connection}


\subsubsection*{Two connections!}

%
\begin{figure}
\includegraphics[%
  bb=20bp 450bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-cifs-connection}


\caption{\label{fig:Initial-CIFS-connection}Initial CIFS connection}
\end{figure}
The address found in DNS is used to make a connection to the two registered
CIFS ports on the server, and is shown in Figure \ref{fig:Initial-CIFS-connection}.
If both ports successfully connect, then the connection to port 139
is dropped, with the connection continuing on port 445. This strange
behaviour is justified by the removal of NetBIOS (which is connected
with port 139) from the CIFS protocol stack - in a mode that Chris
Hertel\citep{hertel} likes to refer to as `naked transport'. Clearly,
the interest here is not in network efficiency%
\footnote{A point that will become very, very clear at the end of the 1300 packets
in this join / domain logon sequence!%
}.


\subsubsection*{Negotiated Security}

%
\begin{figure}
\includegraphics[%
  bb=20bp 300bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-cifs-negprot-reply}


\caption{\label{fig:Negotiate-Protocol-Reply}Negotiate Protocol Reply}
\end{figure}


The expanded packet in Figure \ref{fig:Negotiate-Protocol-Reply}
shows the initial SPNEGO \citet{msspnego} token, as part of the Negotiate
Protocol reply, indicating what security mechanisms this server is
able to accept. The presence of Kerberos (in two forms, due to an
unfortunate bug in early Windows 2000 versions), allows the login
to progress using Kerberos authentication. Likewise, a client unable
to perform Kerberos knows from this reply that NTLMSSP, the more traditional
login scheme on Windows networks, is also acceptable.


\subsection{Kerberos Login}

%
\begin{figure}
\includegraphics[%
  bb=0bp 270bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-krb5-as-req-rep}


\caption{\label{fig:Initial-Kerberos-exchange}Initial Kerberos exchange (AS-REQ).}
\end{figure}


Kerberos is a separate networking authentication protocol entirely,
and Figure \ref{fig:Initial-Kerberos-exchange} shows the client requesting
a Ticket Granting Ticket (TGT), allowing it to request other tickets.
It does so by sending the current time, encrypted with the user's
password (this is the pre-auth data). Of interesting note in this
TGT is the HostAddresss (network addresses where this TGT may be validly
used) is given as a NetBIOS Name, not the usual IP address! The TGT
allows the client to request tickets for services, which in this case
is passed to the CIFS server form of a Session Setup request (shown
in Figure \ref{fig:Session-Setup,-using}), wrapped in SPNEGO and
GSSAPI. Note the server name as it appears in the ticket: \texttt{cifs/win2003.win2k.thinker.local}.

%
\begin{figure}
\includegraphics[%
  bb=20bp 170bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-session-setup}


\caption{\label{fig:Session-Setup,-using}Session Setup, using the Kerberos
ticket, wrapped in GSSAPI and SPNEGO.}
\end{figure}



\subsection{DCE-RPC over CIFS}

\label{sub:DCE-RPC-over-CIFS}

%
\begin{figure}
\includegraphics[%
  bb=20bp 450bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-lsarpc-packets}


\caption{\label{fig:The-initial-RPC}The initial RPC requests}
\end{figure}


The CIFS connection in this case is only made for the purpose of establishing
a transport for DCE-RPC, and Figure \ref{fig:The-initial-RPC} shows
the client's first request - looking again for basic information about
the domain. Of particular note is the \texttt{LsarQueryInformationPolicy2}
reply - the presence of this reply (as opposed to a fault indicating
an unknown operation) indicates to the client that this is indeed
an `Active Directory' domain. The information supplied is actually
very much like that found in the CLDAP reply - an exploded view of
this packet is in Figure \ref{fig:LsarQueryInformationPolicy2-Reply}.

%
\begin{figure}
\includegraphics[%
  bb=20bp 390bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-lsarpc-query-info-policy2}


\caption{\label{fig:LsarQueryInformationPolicy2-Reply}LsarQueryInformationPolicy2
Reply}
\end{figure}


From this point, a stream of requests are made, starting with the
\texttt{SAMR} pipe, to create the new machine account. Shown in summary
in Figure \ref{fig:SAMRAccount-creation}, the end result is a new
machine account, with a password set. The \texttt{SamrGetUserDomainPasswordInformation}
call is to enquire of the minimum password length, so that the subsequent
\texttt{SamrSetInformationUser2} request can set a sufficiently long
password. 

%
\begin{figure}
\includegraphics[%
  bb=20bp 140bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-samr-summary}


\caption{\label{fig:SAMRAccount-creation}Account creation over SAMR }
\end{figure}



\section{Modifying the servicePrincipalNames}

\label{sec:Modifying-the-servicePrincipalNames}Up until this point,
the join process is very much like that of a Samba or NT4 server,
and could be implemented without many changes to an existing code-base.
However, the client soon changes the problem drastically, by making
a call to the LDAP server, which it presumes to be operating on the
same Domain Controller. Combined with yet more DCE-RPC calls, this
time to the DRSUAPI (Directory Replication Service) endpoint, the
client uses `standard' LDAP%
\footnote{Standard in the sense of being TCP based (not UDP, as CLDAP is) and
being largely conforment with the LDAPv3 specifications\citep{rfc2251}.%
} to modify the Kerberos service principal names associated with the
machine account.

This series of calls is interesting for a number of reasons, but particularly
because of the implementation challenges it presents:


\subsection{LDAP Bind}

\label{sub:LDAP-Bind}The LDAP protocol consists of a connect, and
optionally a bind (authenticate request) as a particular user. In
the case of Active Directory, the client uses an authenticated bind,
with the credentials of the user joining the domain. In this case,
shown in Figure \ref{fig:The-SASL/SPENGO/Kerberos-LDAP}, the bind
is performed using Kerberos, which is wrapped rather oddly in both
SASL (described in \ref{sec:SASL}) and SPNEGO (\ref{sub:SPENGO}).

%
\begin{figure}
\includegraphics[%
  bb=20bp 260bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/intial-krb5-spnego-ldap-bind}


\caption{\label{fig:The-SASL/SPENGO/Kerberos-LDAP}The SASL/SPNEGO/Kerberos
LDAP bind request.}
\end{figure}



\subsection{DCE-RPC over TCP}

\label{sub:DRSUAPI}After confirming that the LDAP server is contactable,
and a login has been performed, figure \ref{fig:DCE-RPC-over-TCP}
shows the client making a DCERPC End Point Mapper (EPM) call to locate
the DRSUAPI pipe, and performing a similar SPENGO/KRB5 bind (login).
This sets up an encrypted connection on that pipe, which prevents
the data payload from being revealed. However, the function numbers
are still visible, and we can determine a little without need to decrypt
the entire connection.

%
\begin{figure}
\includegraphics[%
  bb=20bp 260bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/intial-drsuapi}


\caption{\label{fig:DCE-RPC-over-TCP}DCE-RPC over TCP}
\end{figure}


We can see from the exposed function numbers that a call to DsCrackNames
is made, which we can assume from the context makes a conversion between
a machine account name%
\footnote{This is known, because it was just created, and a password was just
set on it.%
} and its LDAP DN%
\footnote{A DN, or Distinguished Name, is the unique location of an entry in
the directory tree. The DN in this case is \texttt{CN=WINXP1,CN=Computers,DC=win2k3,DC=thinker,DC=local}.%
}. We know it must return the DN, because the LDAP search in packet
391 (in Figure \ref{fig:LDAP-Search-and}) uses the exact name of
the machine%
\footnote{This whole procedure could be considered pointless, as a similar search
for the machine name could be performed directly in LDAP. However,
it is clear from the MSDN documentation\citep{dscracknames-msdn}
that \texttt{DsCrackNames} provides a simple API for this purpose.%
}.

%
\begin{figure}
\includegraphics[%
  bb=20bp 600bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/initial-ldap-search-modify}


\caption{\label{fig:LDAP-Search-and}LDAP Search and Modification}
\end{figure}



\subsection{LDAP search and modification}

The next step is to search LDAP for that exact DN, looking for an
existing DNS host name, and any existing servicePrincipalName. Figure
\ref{fig:Adding-new-servicePrincipalName} shows the subsequent modify
request, where new servicePrincipalName attributes are added, per
the standard scheme for a member server.

%
\begin{figure}
\includegraphics[%
  bb=20bp 470bp 612bp 750bp,
  clip,
  width=1.0\columnwidth]{capture-ps/ldap-service-prinicapl-modify}


\caption{\label{fig:Adding-new-servicePrincipalName}Adding new servicePrincipalName
attributes}
\end{figure}



\section{Information Discovery}

At this point, the machine is joined to the domain, and few further
modifications of the server appear to occur. Instead, the machine
now takes the opportunity to discover certain information about the
domain that it joined. This process is incredibly verbose, but consists
primarily of RPC queries, DNS lookups and LDAP searches. 

It is not worthwhile to analyse each call in detail at this point,
as our existing knowledge provides sufficient work for analysis and
implementation as it is. That said, an examination of the packets
shows new calls, but no new technologies. 


\section{Success!}

The join process concludes, and the user is informed of the join's
success, as in figure \ref{cap:Sucessfully-joined-to}. %
\begin{figure}
\includegraphics[%
  clip,
  width=1.0\columnwidth,
  keepaspectratio]{screens/join-win2k3-joined}


\caption{\label{cap:Sucessfully-joined-to}Successfully joined to the domain}
\end{figure}



\chapter{The Challenge of Active Directory}

The challenge of Active Directory is not the individual components
- each can be broken down into simple problems, most of which are
not particularly novel in computer science. Instead, the challenge
in achieving Active Directory compatibility is that of integration.
Each and every one of the above protocols and authentications schemes
all work together on a common basis. As is clear from the join process
- the LDAP server is expected to contain the results of the SAMR call,
as soon as that call is made. Likewise, the Kerberos server is expected
to honour both the passwords and the servicePrincipalNames set by
SAMR and LDAP. While there are numerous views on the Data model, Microsoft's
own documentation, and the behaviour on the network, make it clear
that the back-end is eventually a single Jet%
\footnote{Jet is the same database technology used behind Microsoft Access,
Microsoft Visual Basic and Microsoft Visual C++%
} Database\citep{ms-ad-auth-over}.

As such, the goal of Active Directory compatibility must be achieved
by integration, and as such the Samba4 implementation must strongly
reflect that.


\part{Implementation}


\chapter{Open Source Building Blocks}


\section{Samba}

Samba provides Windows networking services, on a Unix-like platform.
These services range from simple file and printer sharing, to full
management of a NT-style domain. All of these services are provided
in the Samba package, which is itself distributed under the Free Software
Foundation's\citep{FSF} General Public Licence (GPL).\citep{GPL}


\subsection{History of Samba}

Started by Andrew Tridgell, during his PhD studies \citep{10years},
Samba quietly evolved over the past 12 years from a barely functional
prototype, used to communicate between a DOS Pathworks client and
a Sun server, into a solid file and print server for Windows clients,
maintained by a team of over 30 international developers, 12 of which
are active at any one time.


\subsubsection*{Samba 2.0}

After years of 1.x and in particular 1.9.x releases, Samba 2.0 brought
new levels of protocol completeness to the Samba project, and initial
support for becoming a domain member.


\subsubsection*{Samba 2.2}

Samba 2.2 brought the first implementation of a Domain Controller
to Samba's stable series, and provided a solid domain member platform
with the introduction of the \texttt{winbindd} daemon in Samba 2.2.3.


\subsubsection*{Samba 3.0}

With the introduction of Samba 3.0, Samba finally used the Unicode
character representation when talking to network clients, solving
many issues in non-English environments. Samba 3.0 also featured a
vastly improved domain controller, and support for being a client
of Active Directory. 


\subsection{Samba as a DC}

Samba 2.2\citep{abartlet-samba-pdc} and in particular Samba 3.0 grew
to include the ability to be an NT4 compatible domain controller,
a functionality that even allows Samba to `take over' an existing
Windows network\citep{samba-guide-migration}. This has allowed many
sites to remove Windows servers entirely from their networks.

Because Samba 3.0 implements the full requirements of an NT4 DC, it
can be used to host some of the legacy parts of the protocol, not
yet found in Samba4 - in particular, NetBIOS name registration and
NETLOGON requests. Patches have been proposed (and some already accepted)
to allow this piece of Samba3 infrastructure to handle these roles,
in the Samba4 framework.


\subsection{Samba as a Active Directory domain member}

Samba 3.0 release \citep{samba-3.0} has the ability to be a member
of an Active Directory domain, and as such has an implementation of
a particular form of AD client. This client uses Kerberos for authentication,
and used DCE-RPC and LDAP to query user and group information from
the DCs.


\subsection{Samba 3.0 Active Directory DC research }

\label{sub:blue dir}As part of a internship project known as Blue
Directory, students and supervisors at IBM's Linux Technology Center
spent a lot of time researching the problem space around Active Directory,
but as described by \citet{jmcdAD}, they kept hitting up against
limitations in the available technology. Their research work has been
rapidly superseded by the Samba4 effort, but their input showed what
would be possible with the proper infrastructure. 


\section{Heimdal Kerberos}

Heimdal \citep{heimdal,westerlundheimdal} is an Open Source implementation
of the Kerberos protocol. Created outside the USA due to export controls
on strong encryption \citep{exportcontrols,mitkrb5export}, it has
been developed independently of the well-known MIT distribution\citep{mitkrb5}.
The Heimdal source code is well tested, and quite easy to modify.
The presence of the HDB back-end interface (not found in the MIT distribution)
is what made Heimdal the clear choice for this integration effort.

Another aspect that makes Heimdal a key building block in this effort
has been the active participation of key Heimdal developers in our
branch of the Heimdal source \citep{lhasamba-technical}.


\subsection{HDB Back-end}

Within Heimdal, there is an abstraction layer that separates the password
database from the rest of the Kerberos implementation. In the unmodified
code, this allows the administrator to select between an LDAP back-end,
and a simple key-value database. It is this interface that this project
will extend, with a new `ldb' back-end to be provided.


\subsection{Heimdal/Samba Integration}

Another feature of current Heimdal snapshots is support for integration
with Samba 3.0. By using Samba 3.0's password entries in the LDAP
database, Heimdal snapshots can use the \texttt{sambaNTPassword} attribute
as an \texttt{arcfour-hmac-md5} Kerberos key. This integration work
not only opened up valuable communication channels between Samba and
Heimdal developers, it provided hands-on experience in hdb module
development.


\section{\texttt{clapd}}

\texttt{clapd} is a simple Connectionless LDAP daemon, written as
part of the IBM research effort\citep{jmcdAD} and designed to answer
the basic requests that a Windows client makes over connectionless
LDAP. At present, it is functional to the extent required for my domain
join test, but has failed for others. It will need to be rewritten
and properly integrated into the Samba4 system.


\section{BIND}

An Active Directory domain is strongly based on a DNS domain, particularly
due to the tight integration between Kerberos and DNS, and the fact
that this allows a move to a hierarchical name space. No modifications
have been required to the BIND software, and only the installation
of configuration files is required.

In the future, changes to BIND will be required to support Microsoft's
dynamic DNS update scheme.


\chapter{Samba4 Status}

Samba version 4 is an ongoing research project of the Samba Team,
and had made significant headway into this problem space before I
even proposed my thesis topic. It has grown up in a very modular style,
and with a much cleaner code-base than Samba 3.0. The core development
on Samba4 has been by Andrew Tridgell, Stefan Metzmacher and myself,
with contributions from many others from time to time.

While there is far more to Samba4 than these subsystems, the AD emulation
work hits on these in particular:


\section{LDB}

LDB is described as a `LDAP like Database'. Designed to avoid giving
Samba4 a dependency on OpenLDAP, ldb implements an `LDAP like' API
and data format. LDB includes an abstraction layer that allows it
to be backed onto LDAP, or onto a local flat-file database, in the
format of a TDB. Therefore, a Samba4 installation can remain self-contained,
without demanding the notoriously complex task of setting up an external
LDAP server. 

LDB is available as a shared library, and is licenced under the LGPL.
This allows other applications to link against our database back end.


\section{GENSEC}

\label{sec:GENSEC}Intended to replicate SSPI \citep{sspi} on Windows
in ubiquitous use, GENSEC allows all aspects of Samba4 to use the
same implementation of our core authentication protocols. The interface
is completely generic, and on starting this thesis it contained support
only for NTLMSSP, the development of which had been brought forward
from Samba 3.0. The addition of Kerberos support to this interface
is one of the core objectives in this thesis.


\section{PIDL - Midl replacement for Samba}

\label{sec:PIDL---Midl}One of the biggest achievements in Samba4's
design and development is the PIDL\citep{pidl} IDL compiler. Known
as PIDL because it is a Perl compiler of the Interface Definition
Language, this comparatively small collection of Perl modules and
handling scripts converts the standard IDL file format into C code
for use inside Samba (On the Microsoft platform a program known as
\texttt{midl\citep{midl}} does the same thing). Attempted, but not
completed, in the past, this contrasts greatly with the approach in
Samba3 - that of manual parsing of packets, with little regard to
the inbuilt rules of the Network Data Representation (NDR) format.


\section{Echo Pipe}

In development of a generic DCE-RPC infrastructure, it is often helpful
to have some way to `define' the problem. Many aspects of DCE-RPC
are only exercised in particular circumstances. By defining our own
DCE-RPC pipe, it becomes possible to create overly large request and
replies, for example. Similarly, by working with a protocol that is
simple, and with a public definition, we can expose bugs in the layers
that handle simple parsing of the packets.

The particular success of the echo pipe in Samba development is the
Windows client and server. By running the echo server on a Microsoft
platform, questions such as 'how much data can I pass in a DCE-RPC
packet' can be answered, without first contriving to find a piece
of Microsoft software that creates large RPC replies. Likewise, the
Windows echo client allows great opportunities for testing authentication
technologies. 


\section{Domain Join}

\label{sec:Domain-Join}At the commencement of this thesis, \citet{tridge}
had recently claimed success in joining a WinXP machine to the Samba4
domain controller. Naturally, this is a process that must be repeated
by others, and I took this on as one of the first tasks in the thesis.
While a packet-by-packet analysis of the join is not warranted, it
is worth noting two particular characteristics:


\subsection{An Upgraded NT4 Join}

\label{sub:An-Upgraded-NT4}In replicating the domain join (with a
WinXP client), I found that the domain join process would only complete
when using the domain's `short' or NetBIOS name. Use of the long (DNS,
and Kerberos realm) name would result in calls the (unimplemented)
LDAP server, and failure. In the short-name case, the domain join
proceeds using just SAMR calls, much the same way as that shown in
Section \ref{sub:DCE-RPC-over-CIFS}.


\subsection{A more AD-like Logon}

Once the domain join has completed, the logon phase is more `AD like'.
That is, DNS lookups are performed on the long name, and the CLDAP
reply is expected, likewise the End Point Mapper (EPM), (not found
in NT4) is contacted and newer \texttt{netlogon} calls are made, negotiating
security mechanisms such as 128-bit session keys.%
\footnote{The challenge of implementing these new extensions to \texttt{netlogon}
is detailed in Section \ref{sec:Netlogon-128}.%
}


\chapter{Adding Kerberos}

The addition of Kerberos to the Samba4 implementation forms the experimental
basis for this thesis. While the domain join has been demonstrated
using the older NTLM technologies (no mean feat in itself), the addition
of Kerberos remains critical to any real claim to implement AD. 


\section{Heimdal Integration}

As has already been described, the Heimdal implementation of Kerberos
includes a database abstraction layer, known as hdb. The challenge
in this experiment is to modify Heimdal in such as way that it can
use the Samba4 ldb as a password database. To allow easy development,
a copy of the Heimdal development snapshots were imported into the
Samba `lorikeet' subversion repository. This allowed easy modification
and version control, separate from the original Heimdal authors. Care
was taken to liaise with Heimdal's developers to reassure them of
our intentions, and that we did not intend this to be a long-term
fork of the Heimdal code-base.


\subsection{A new hdb-ldb for Heimdal}

The obvious first step in the process was to take the hdb-ldap, long
established Heimdal component, and modify it to call ldb (the Samba4
`ldap like' database API) rather than LDAP. This work was initially
performed by Stefan Metzmacher, and extended by myself, and essentially
consists of a semantic mapping exercise - mapping ldb attributes into
the form defined as the Heimdal hdb interface. Because Microsoft extended
Kerberos with the \texttt{servicePrincipalName} concept (a principal
may be resolved by many names), this needed to be carefully addressed
in LDB.

This process was iterative, and at each stage of development tests
were performed - starting with a Unix \texttt{kinit} and later by
using a WinXP client, as part of testing on the entire domain join
operation. This showed up defects, and at each stage a more complete
semantic mapping was devised. 


\subsection{Heimdal Structural Changes}

A few aspects of the hdb-ldb development created problems, due to
the structure and assumptions in the original Heimdal code. In particular,
hdb-ldb is unique in Heimdal in that it may contain plain-text passwords,
not the hashed encryption keys. Storing the plain-text password is
required when the `store password with reversible encryption' flag
is set, and doing so by default has allowed easier initial development.
In this case, we `hash' the passwords on the fly, but we can also
store the pre-hashed password if the plain-text is not available.
These requirements required me to perform a minor code restructure,
which has now been included by Heimdal's developers into current snapshots.


\subsection{No PAC at this stage}

While the PAC is now well understood, and sample KDC implementations
that successfully sign the PAC have been contructed\citet{jmcdAD},
PAC support was not implemented: instead the Samba server was modified
to accept Kerberos packets without the PAC. (The client does not process
the PAC in the initial use case, so this complexity was deferred).


\section{Adding Kerberos to Samba4}

By this stage, Samba4 had gained the new GENSEC security subsystem,
and it was from this base that Kerberos client and server support
was added. In particular, Stefan Metzmacher added support for parsing
(but not yet verifying the signatures on) the PAC, and we both worked
on the basic infrastructure required to produce and accept a Kerberos
ticket. Despite being a re-implementation of functionality already
working in Samba 3.0, the new GENSEC system needed work to cope with
how Kerberos functions, and the Kerberos code was again hooked into
mechanisms such as SMB signing. 

This would allow an attempted domain join (the target of this experiment)
to use Kerberos.


\section{Testing the Experiment - the Kerberos Domain Join }

Now that Kerberos has been added to Samba4, and the Heimdal Kerberos
distribution has been modified to read information from ldb, the changes
can be assessed. 


\subsection{'Long name' domain join}

In my testing the of a Kerberos domain join, it quickly becomes clear
that the domain would not use Kerberos for the join if the `short'
(NetBIOS) domain name was specified. While it is no more painful to
enter the long name, the point made in Section \ref{sub:An-Upgraded-NT4}
still holds - such a domain join will contact LDAP and DRSUAPI, and
fail. Fortunately LDAP server support is progressing rapidly, as is
the implementation of DRSUAPI (and the associated Kerberos security
layers), but these were not ready at the technical completion of work
for the thesis.


\subsection{Kerberos in CIFS}

Adding correct Kerberos (and SPNEGO) support into CIFS was the primary
challenge in the Samba4 code-base, and in this area the project was
very much a success. In this case, the keytab was manually exported
from Heimdal, and the WinXP client successfully obtained a ticket,
and used that ticket to log into the Samba4 server. We also know that
the session key logic is correct, because both SMB signing and the
password set occur correctly.


\subsection{Failing at LDAP}

The failure in the domain join process occurs as the client attempts
to contact the LDAP server, where it wishes to perform the process
described in Section \ref{sec:Modifying-the-servicePrincipalNames}.
As mentioned above, this blocking point should be removed in near-future
development, but this marks the conclusion of the development for
this thesis.


\subsection{Trying the short name}

After completing the `failed' testing with long-name domain joins,
comparison tests were run - to confirm the status of the `before'
case, which was expected to easily be triggered by simply using the
`short' or NetBIOS domain name. Indeed, this domain join proceeds
with NTLMSSP, but what is more interesting is what happens after the
client reboots, having sucessfully joined the domain. It turns out
that the client clues in on Kerberos in the meantime, and proceeds
to make a sucessful Kerberos connection to the Samba4 server, using
the machine account! Unfortunately, other issues with current Samba4
prevent the login from proceeding, but these appear unrelated to the
Kerberos work (it occurs with Kerberos completely disabled), and is
rather an unrelated regression.


\section{Assessing the Changes}

The changes for this particular experiment were not large - they could
perhaps better be described as tedious, with details in the infrastructure
being brought to the surface. However, the change in the domain join
procedure was easily noticed - the client (WinXP) would indeed use
Kerberos, and this would succeed to the stage (described in Section
\ref{sub:LDAP-Bind}) of contacting the LDAP server. Naturally, this
failed due to the lack of an integrated LDAP server in the Samba4
suite.

This presented an anticlimax - progress has indeed been made, but
if it is used, the domain join demonstrated previously fails. This
does not however condemn this experiment as a failure - it simply
reminds us that more work needs to be done. \emph{The KDC is indeed
operable, and Samba4 can use it for simple CIFS logins. }

Since this work was performed an integrated LDAP server has appeared,
and will soon support Kerberos logins itself, and we can again test
this procedure `one step further'. It is known from Section \ref{sub:DRSUAPI}
of the trace, that we will also need Kerberos encrypted DRSUAPI support.
Likewise, the compromised `short name' join looks very promising,
sucessfully putting off the Kerberos until the logon stage.


% Make these last two things the appendix
\appendix
\part{Appendix}

\chapter{Crypto Challenges}

In implementing many of the Active Directory protocols, there have
been a number of cryptographic puzzles which we have had to solve.
These have involved determining the encryption routine, or in one
case the previously unknown encryption keys used between Microsoft's
own client and server.

Cryptographic challenges differ greatly from the normal style of network
protocol analysis because, until the correct answer is obtained, there
is no indication how `close' a particular solution may be. This puts
off many people from the challenge, but also makes the problem that
much more rewarding when the answer finally arrives. The following
cryptographic challenges were solved by Tridgell and other members
of the Samba Team (including myself) over the course of 2004.


\section{Password Change Mechanisms}

It turns out that in the CIFS and associated protocol suites, there
are at least 15 different ways to change or set a user's password.
Most of these have their own particular cryptographic system, to avoid
disclosure of the old or new passwords during the password change.


\subsection{Encrypt new passwords with old}

This classic technique for password changes has been in documented
use since the early 90's, where the AppleTalk network protocol encrypted
the user's new password with the old password, when the user wished
to change their password. Importantly, to ensure that the password
change was not tampered with, the old password was also sent, encrypted
with the new password. This is documented in `Inside AppleTalk'\citep{appletalk}.
This cross-encryption technique has been duplicated many times in
CIFS, with only changes to what form the passwords take (already `hashed'
passwords or the plain-text), and what cryptographic algorithms are
used to secure them. As an example, on only the SAMR pipe, we have
4 different password change functions:

\begin{lyxlist}{00.00.0000}
\item [samr\_ChangePasswordUser]Encryption of old and new hashed passwords
with DES. Does not give plain-text to the server.
\item [samr\_OemChangePasswordUser2]Encryption of new password with old
LM hash, using arcfour\citet{RC4Page}. Old LM and hashs encrypted
with new hashed password.
\item [samr\_ChangePasswordUser2]Encryption of new password with old LM
and NT hashs, using arcfour\citet{RC4Page}. Old LM and NT hashes
encrypted with new hashed password.
\item [samr\_ChangePasswordUser3]Identical encryption, but return detailed
information of reason for password change rejection.
\end{lyxlist}
Where plain-text passwords are encrypted in CIFS, they are randomly
padded in a large (512 byte) buffer. This technique is described in
\citet{randomcrypto}, and referred to as a `confounder'. This avoids
certain chosen plain-text attacks on the system, because the full
input into the encryption algorithm is no longer constant. In particular,
given the use of arcfour in the cypher step, this avoids encryption
of known constant padding bytes, which can be problematic in RC4.


\subsection{Encrypt new passwords with administrator passwords}

While encrypting new passwords with their former values is good for
user password changes, remote password setting is also permitted,
and this is generally secured with some derivative of the administrator's
password. This presented a number of security issues in modern networks,
as the scheme chosen in early versions of NT would allow an attack
on the administrator's own password!%
\footnote{With the fixed User Session Key in NTLM, any two password set operations
would have the same encryption key, until the administrator changed
their own password.%
} Hence, versions of Windows 2000 introduced a confounder, into the
session key (integrated in this case with MD5), to ensure that any
two password set operations have distinct encryption keys.


\subsection{Solving the password change puzzles}

Like all cryptographic puzzles, the password change puzzle can be
restricted by the known inputs and outputs. It is known what the password
is before and after a password change, and we know what the server
can store in its user database (that is, the NT and LM passwords).
Given the small amount of information exchanged in the password change
packets, we know . Like we see in the authentication chapters, we
know the server can only use the NT and LM passwords in the password
change. Therefore, the task is reduced to considering what encryption
and digest (hash) functions have been used, and in what order. 

The process is tedious, but because Microsoft has a few `favorite'
encryption functions (clearly easily accessed from a central library),
combinations of DES, arcfour and MD5 are a very suitable first guess.
Once one password change or set function is known, may of the others
prove to be simple variations, fixing particular issues (such as adding
in the new NT password, or adding a confounder). We look at a couple
of puzzles in detail:


\section{Netlogon 128}

\label{sec:Netlogon-128}As attempts to solve the Active Directory
DC problem continued, Tridgell led attempts to solve most of the outstanding
cryptographic puzzles that stood in the way. This included a new 128
bit security mode for the \texttt{netlogon} pipe, and the associated
schannel bulk encryption mechanism. This problem, like most of the
previous problems, was already partly solved - Samba 3.0 had support
for schannel, and Samba 2.2 has supported the basic security mechanisms
on \texttt{netlogon}. What was unknown is how the new 128 bit security
system worked, with an unmodified packet format. 


\subsection{A `simple' challenge }

The 128-bit Netlogon problem was solved with the assistance of a standalone
cryptographic challenge. Simply consisting of a few C files and a
makefile, the challenge provides a malleable unit test, completely
distinct from the complexities in the rest of samba. The programmer
attempting the puzzle needs only to tweak a small file, recompile
and run, to test a given possible solution. 

It was with a challenge set by Tridgell that I solved part of the
Netlogon-128 puzzle (much to his pleasant surprise). By expressing
the problem so simply, the hints found in the standards drafts were
easily applied, and I turned an answer around a matter of minutes.


\subsection{Related standards}

In solving this puzzle, my attention was drawn to the fact that netlogon
is disturbingly similar in cryptographic operation to the new Kerberos
encryption functions described in Section \ref{sec:type-23-crypto}.
Reading the standards drafts, it became clear that Tridgell's attempt
was almost, but not quite the same as one of the cryptographic functions
in the draft. This combined with the discovery that other parts of
the key setup are simply `longer' versions of the traditional 56-bit
exchange allowed a full implementation of 128 bit Netlogon security.


\section{LSAKEY}

\label{sec:LSAKEY}When communicating over the network, it is possible
for the entire communication channel to be secured, by negotiation
of bulk encryption. However when the whole channel is not secured,
the SAMR and LSA pipe still transmit sensitive data, such as when
an administrator sets a user's password, or retrieving `LSA secrets'.
To secure this data a session key is negotiated between the peers
- and in \texttt{ncacn\_np} (the most common authentication modal)
this is simply inherited from the session key determined for use at
the CIFS layer. 

However, when the CIFS layer does not exist (such as in \texttt{ncacn\_ip\_tcp}
- the direct transport of DCE-RPC over TCP/IP), a different session
key must be used. Likewise, it was found during testing that if the
DCE-RPC layer performed any authentication, that the inherited session
key was no longer valid.

This presented a challenge - to perform correct testing of all DCE-RPC
transports, we needed to know how to perform these encrypted operations.


\subsection{An opening:}

In attempting to solve this puzzle, it came to our attention that
the LSA set and query secret functions could provide a cryptographic
insight into the problem. This function allows storage of an arbitrary
piece of data in the server. By setting the secret encrypted with
one (known) session key, and retrieving it over \texttt{ncacn\_ip\_tcp}
(and therefore the unknown key), properties of the encryption function
can be derived by extracting the cipher-text for a known plain-text.


\subsection{Controlling the session key}

In researching this problem, I noticed that in NTLMSSP, the \texttt{KEY\_EXCHANGE}
option allows the network client to chose the session key. At this
stage, it was unknown what encryption function was in use, but by
choosing a known weak encryption key, such as all-ones (all zeros
was not supported), we could analyise the properties of the cyphertext. 


\subsection{Proof that it's a fixed key}

One of the first breakthroughs in solving the puzzle was the realisation
that, despite changes in session keys, user-names or passwords, the
encrypted secret would not change. This was most puzzling, because
secrets are typically encrypted with a value shared between the user
and server (which implies that it should change with the user's password,
even if somehow disconnected from the key exchange mentioned above).

This strongly suggests that the key is some constant value, possibly
a `dummy' value that was always intended to be replaced with a real
encryption key (such as happens in \texttt{ncacn\_np} without additional
authentication).


\subsection{Key-search}

An analysis of the (unchanging) cyphertext indicated that the encryption
function used indicated that is was probably unchanged from the DES
variant used in the \texttt{ncacn\_np} case. This indicated the need
for a key search, for the secret key shared between Microsoft implementations.

In considering the possible secret keys, I suggested that the key
was probably not a random value, but more likely an ASCII string used
for initialisation.%
\footnote{Other Microsoft security functions use ASCII strings as dummy values,
such as SMB signing, where the signature is set to \texttt{\char`\"{}BSRSPYL
\char`\"{}} as an initial value.%
} On this basis, Tridgell constructed a systematic DES key-breaking
attack, using a parallel DES decryption engine, starting with upper
and lower case ASCII values, sorted by the frequency in which they
occur in natural words. 

Eventually (and this only took a matter of 24 hours of CPU time) the
fixed key was found: \texttt{\char`\"{}SystemLibraryDTC\char`\"{}}.


\subsection{Consequences of a fixed key}

The use of fixed keys in cryptography is very much frowned upon -
it only takes one effort such as the one mounted by the Samba Team
to break the security of all the communications `secured' with that
key. However, in this case the security issues are mitigated by the
requirements for authentication and at a minimum cryptographic signing
of the data stream. As such, the client can be careful not to ask
for such secrets across a clear-text channel, and an attacker cannot
spoof the requests of the client, because that would break the cryptographic
signature. The client should instead use the bulk encryption security
of the entire session to secure the transport of these sensitive data
items.


\chapter{Glossary}

\begin{lyxlist}{00.00.0000}
\item [AD]Active Directory
\item [ADS]Active Directory Services
\item [CIFS]Common Internet File System, originally the file and print
  sharing protocol known as SMB, and the core of Microsoft's
  networking stack.
\item [DECNet]A now deprecated networking standard from Digital
  Equipment Corporation (DEC).
\item [DES]Data Encryption Standard, a US Government encryption standard.
\item [DNS]Domain Name System, the Internet standard for hierarchical name to
  address translation.
\item [HTTP]Hyper-Text Transfer Protocol, the Internet standard
  transport for the 'World Wide Web'.
\item [IDL]Interface Definition Language, the structured format for
  description of DCE-RPC interfaces, including the network format.
\item [IP]Internet Protocol.  The base networking standard on which
  TCP/IP sits, and which the Internet runs.
\item [IPX]Novell's network standard, now superseded by TCP/IP.
\item [Kerberos]A centralised authentication system, the current
  version of which is also known simply as KRB5, based on strong
  cryptography, shared-secrets, and a trusted third party (the KDC).
\item [LDAP]An Internet standard directory services interface. While LDAP
is a protocol specification, the protocol implies the X.500 information
model.
\item [NetBEUI]An simple encapsulation of NetBIOS directly onto
  Ethernet, now superseded by TCP/IP.
\item [NT~Domains]Windows NT domains share the information about users,
groups and passwords between machines in the domain. The protocols
are limited in what information can be stored, and is not extensible.
Windows 2000 and Samba both provide {}``NT Domain'' views onto their
more complex directory back-ends.
\item [LM~hash]The user's case insensitive, ASCII password, processed
with DES, as described in Section \ref{sub:Calculating-the-LM} (comparatively
weak).
\item [NT~hash]The user's case sensitive, Unicode password, processed
with MD4. Used for NTLM and Kerberos authentication.
\item [NTLM]A challenge-response authentication protocol, based on shared
secrets (passwords).
\item [NTLM2]The description applied to an NTLMSSP negotiated option, that
improves the NTLM security system.
\item [NLTMSSP]NTLMSSP is a generic wrapping of the NTLM authentication
protocol, encompassing negotiated options and an encryption engine.
\item [NTLMv2]A modified version of NTLM, with a true 128 bit challenge/response
step.
\item [Session~Key]The encryption key used for a particular session. This
key should change between sessions.
\item [Shared~Secret]A value, usually a password, shared between two systems
but otherwise private.
\item [TCP]Transmission Control Protocol, which combined with IP is
  the Internet standard TCP/IP suite, and provides reliable
  connections over IP connections.
\item [UDP]User Datagram Protocol, part of the IP suite of Internet
  Protocols for unreliable datagram (message) transmission.
\end{lyxlist}
