\documentstyle[simplemargins]{article}

\title{Dual-workfactor Encrypted Key Exchange: \\
        Efficiently Preventing Password Chaining \\ 
        and Dictionary Attacks}
\author{Barry Jaspan\footnotemark[1]}
\date{}

\newcommand{\mod}{\ \mbox{mod}\ }
\renewcommand{\v}[1]{\verb+#1+}

\setallmargins{1in}
\pagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Allow line breaking after \_.
\let\underscore=\_
\def\_{\underscore\penalty75\relax}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\nocite{NeedhamSc78}
\nocite{SteinerNeSc88}
\nocite{BelMer91}

\maketitle

{\def\thefootnote{\fnsymbol{footnote}}
\footnotetext[1]{Affiliation: Independent consultant, 4 Merrill Ave,
Belmont, MA 02178, {\it bjaspan@mit.edu}.  This work was also funded
in part by BBN Planet Corporation and the Internet Software
Consortium.}
}

\thispagestyle{empty}

\begin{abstract}
Password-based key-server protocols are susceptible to {\it password
chaining} attacks, in which an enemy uses knowledge of a user's
current password to learn all future passwords.  As a result, the
exposure of a single password effectively compromises all future
communications by that user.  The same protocols also tend to be
vulnerable to dictionary attacks against user passwords.

Bellovin and Merrit\cite{BelMer92} presented a hybrid of symmetric-
and public-key cryptography called Encrypted Key Exchange (EKE) that
cleanly solves the dictionary attack problem.  This paper presents an
extension of their ideas called {\it dual-workfactor encrypted key
exchange} that preserves EKE's strength against dictionary attacks but
also efficiently prevents passive password-chaining attacks.
\end{abstract}

%\section*{TODO}
%
% read kerblimit for points and references
%
% Points from EKE:
%  2.5 makes some security points i missed
%  ref from section 6 and 7
%
% Check eurocrypt '95 for papaer on DH implementation.
%
% ``No longer using a long-term key to protect verifiable data.''
%

\section{Introduction}

Virtually all password-based key server protocols are vulnerable to
{\it password chaining} attacks.  In these systems, a user shares only
a single secret, its password, with the trusted key server.  In
addition to protecting the normal authentication and key-distribution
messages, the current password is also used to protect the protocol
exchanges used to select a new password.  An enemy that already knows
the user's current password can ``daisy-chain'' the passwords together
by decrypting the password-changing session and reading out the new
password.

Many password-based protocols are also vulnerable to a dictionary
attack against user passwords.  In the Kerberos authentication
system\cite{NeumanTs94}, for example, the initial protocol exchange is
encrypted in a key derived from the user's password.  A malicious user
can obtain these encrypted messages and use them to attempt to guess
the user's password.  Since the format of the messages is well known,
a correct guess is easily verifiable.  Once the guessing attack
succeeds, the attacker can use the password to impersonate the user
until the password is changed.  In practice, password guessing attacks
have a high degree of success\cite{FeldmeirerKa90,Spaff92}.

The combination of these two weaknesses is particularly worrisome.
The password guessing vulnerability makes it likely that at least one
of a user's passwords will eventually be disclosed; password chaining
means that once one password is disclosed, all future passwords are
compromised.  Since it is easy for an attacker to record all of a
user's traffic while simultaneously attacking old messages, both past
and future communications are at risk.

Bellovin and Merrit\cite{BelMer92} presented a fundamentally novel
hybrid of symmetric- and public-key cryptography called Encrypted Key
Exchange (EKE) that cleanly solves the dictionary attack problem.
This paper presents an extension of their ideas called {\it
dual-workfactor encrypted key exchange} that preserves EKE's strength
against dictionary attacks but also prevents passive password-chaining
attacks, without incurring unnecessarily high overhead.  The basic
idea is to use an extremely strong EKE exchange for password-changing
messages, thus preventing chaining, while using a much weaker EKE
exchange with normal authentication for efficiency.  Dual-workfactor
encrypted key exchange is motivated in the context of a new EKE-based
pre-authentication type for Kerberos 5 called PA-ENC-DH that can be
implemented without changing the current Kerberos 5 protocol or
requiring additional network messages.

Section \ref{sec:prev} discusses previous work on password chaining
and dictionary attacks.  Section \ref{sec:prot} provides background on
the Kerberos and Diffie-Hellman exponential key exchange protocols,
and motivates dual-workfactor encrypted key exchange.  Section
\ref{sec:impl} discusses implementation issues for this protocol
specific to Kerberos 5, including public-key parameter selection.
Table \ref{tab:notation} summarizes the notation used throughout this
paper.

\begin{table*}
\begin{tabular}{@{}ll}
{\bf Notation} & {\bf Meaning} \\
\hline
$C$             & client \\
$S$             & server \\
$KDC$           & Key Distribution Center, a.k.a. the Kerberos server \\
$K_x$           & symmetric secret key for user $x$ \\
$K_{xy}$        & symmetric session key for users $x$ and $y$ \\
$\{X\}^{K_x}$      & message $X$ encrypted in symmetric key $K_x$ \\
$p_x$           & private Diffie-Hellman key for user $x$ \\
$P_x$           & public Diffie-Hellman key for user $x$, $P_x=q^{p_x}$ \\
$\{X\}^R$        & message $X$ encrypted in symmetric key $R$ derived from
                  Diffie-Hellman key $q^{p_cp_s}$ \\
$T_{cs}$        & Kerberos ticket for client $c$ to use service $s$ \\
$\mbox{PA}=D$   & Kerberos pre-authentication with data $D$
\end{tabular}
\caption{Notation used throughout this paper.}
\label{tab:notation}
\end{table*}

\section{Previous work}
\label{sec:prev}

There does not appear to be any previous work on strengthening
password-based protocols against an attacker that already knows the
password.

The issue of dictionary attacks has been widely discussed.  Kerberos
version 5\cite{KRB5-RFC} partially addresses the problem with {\it
pre-au\-then\-ti\-ca\-tion}, requiring the initial request to the KDC
to prove the user's identity so an attacker cannot fraudulently
request tickets for another user; see section \ref{sec:krb}.  A
protocol can be designed in which off-line guessing attacks are
impractical and so every password guess must involve a central
authority which can then detect the attack\cite{Lomas89}. A password
changing mechanism can be designed to enforce password quality,
insisting on passwords with a minimum length, character mix, or other
properties.  It is also possible to design a password selection
process that simplifies the selection of quality passwords that are
both easy to remember and hard to guess\cite{Bishop92}.

\section{Protocol description}
\label{sec:prot}

This section provides background on the Kerberos and Diffie-Hellman
protocols, explains how Encrypted Key Exchange is applied to Kerberos,
and motivates dual-workfactor encrypted key exchange.  The new
PA-ENC-DH Kerberos pre-authentication type is presented.

\subsection{Kerberos AS\_REQ protocol}
\label{sec:krb}

The most basic exchange of the Kerberos protocol is an Application
Service Request, or AS\_REQ.  Client software uses an AS\_REQ to
request a Kerberos ticket for a user.  The response is sent encrypted
in a key derived from the user's password.  Typically, an AS\_REQ is
used exactly once per login session to obtain a ticket-granting
ticket.  A simplified version is as follows:
%
\begin{eqnarray*}
C \rightarrow KDC & : & C, S \\
KDC \rightarrow C & : & C, T_{cs}, \{S, K_{cs}\}^{K_c}
\end{eqnarray*}
%
In the AS\_REQ, the client $C$ sends its own name and the name of a
service $S$ to the KDC.  The KDC responds with an AS\_REP (Application
Service Reply) containing the client's name, a ticket $T_{cs}$ for the
client to use with the service, and a block of data {\it encrypted in
the user's password-derived key} $K_c$ containing the service name and
a copy of the session key $K_{cs}$ for the client and service to use.
A dictionary attack is possible against the block encrypted in $K_c$
in the AS\_REP because the attacker can validate password guesses---if
an attacker guesses $K_c'$, performs the decryption, and a meaningful
server name $S$ appears in the result, the guess is correct.

Kerberos 5 introduced pre-authentication into the AS\_REQ exchange as
a partial defense against dictionary attacks.  With
pre-authentication, the user's initial request is required to contain
a block of data that proves the identity of the requesting user.  The
Kerberos server refuses to respond to the request unless the
pre-authentication data is correct, thus preventing an attacker from
making a fraudulent request at any convenient time.  The most common
pre-authentication method uses an encrypted timestamp and is called
PA-ENC-TIMESTAMP:
%
\begin{eqnarray*}
C \rightarrow KDC & : &  C, S, 
        \mbox{PA} = \{\mbox{time}\}^{K_c} \\
KDC \rightarrow C & : &  C, T_{cs}, \{S, K_{cs}\}^{K_c}
\end{eqnarray*}
%
When the KDC receives the AS\_REQ, it decrypts the timestamp using the
client's secret key, and only honors the request if the timestamp is
within a pre-defined window of the KDC's current time.  An attacker
cannot forge the pre-authentication data without knowing $K_c$.
However, the attacker can still read either the request or the reply
off the network and perform a dictionary attack against it.  Other
forms of pre-authentication exist\cite{KRB5-SAM} in which the request
does not allow for dictionary attacks, but so far all of them leave
the reply vulnerable.  Thus, while existing pre-authentication schemes
make a dictionary attack somewhat harder to perform, they are not a
fully satisfactory solution.

\subsection{Kerberos password-changing protocol}

Kerberos users change their passwords by interacting with the Password
Changing Service, typically implemented as part of the Kerberos
administration system. The password-changing program performs an
AS\_REQ to obtain a ticket $T_{c,pw}$ for the administration principal
$S_{pw}$ which it then uses to perform encrypted communications with
the Password Changing Server:
%
\begin{eqnarray*}
C \rightarrow KDC & : &  C, S_{pw} \\
KDC \rightarrow C & : &  C, T_{c,pw}, \{S_{pw}, K_{c,pw}\}^{K_c} \\
C \rightarrow S_{pw} & : & T_{c,pw}, \{\mbox{new pw}\}^{K_{c,pw}}
\end{eqnarray*}
%
An attacker that already knows the user's password can decrypt
$\{S_{pw}, K_{c,pw}\}^{K_c}$ to obtain $K_{c,pw}$ and then decrypt
$\{\mbox{new pw}\}^{K_{c,pw}}$ to obtain the new password.  This is
called {\it password chaining} and it can be performed indefinitely to
learn all of a user's future passwords.

\subsection{Exponential key exchange}

Diffie-Hellman exponential key exchange\cite{DiffieHe76b} is a
well-known method for two parties to exchange a secret key across an
open network.  A good explanation appears in \cite{Schneier93}.
Briefly, the Diffie-Hellman protocol requires a prime modulus $m$ and
a primitive root of that modulus $q$; both values are public
knowledge.  Suppose that two parties $C$ and $S$ want to exchange a
key.  $C$ picks a random number $p_c$, computes from it $P_c \equiv
q^{p_c} \mod{} m$, and sends that value to $S$:
%
\begin{eqnarray*}
C \rightarrow S: P_c
\end{eqnarray*}
%
Similarly, $S$ picks a random number $p_s$, computes $P_s \equiv
q^{p_s} \mod{} m$, and sends the value to $C$:
%
\begin{eqnarray*}
S \rightarrow C: P_s
\end{eqnarray*}
%
At this point, both $C$ and $S$ can compute $R \equiv {P_c}^{p_s} \equiv
{P_s}^{p_c} \equiv q^{p_cp_s}$.  An attacker knows both $P_c$ and $P_s$ but
cannot compute $R$ without knowing one of $p_c$ or $p_s$, neither of
which is available.  $C$ and $S$ can use $R$ to encrypt further
communications.

This protocol provides key exchange, but it does not provide
authentication\cite{DiffieVaWi92} because it is subject to a
man-in-the-middle attack.  An attacker can intercept all
communications between $C$ and $S$ and substitute its own values for
$P_c$ and $P_s$, and neither $C$ nor $S$ will notice.  Furthermore,
the choice of $m$ is critically important from a practical point of
view\cite{LaMacchiaOd91a,PohligHe78} if the protocol is to be
resistant to cryptanalytic attacks.

\subsection{Merging Diffie-Hellman and Kerberos}

Encrypted Key Exchange (EKE) can be used to merge Diffie-Hellman
exponential key exchange and Kerberos.  The protocol presented here is
a proposed pre-authentication type for Kerberos called PA-ENC-DH:
%
\begin{eqnarray*}
C \rightarrow KDC & : &  C, S, 
        \mbox{PA} = (\{P_c\}^{K_c}, m) \\
KDC \rightarrow C & : &  C, T_{cs}, \{S, K_{cs}\}^{R}, 
        \mbox{PA} = \{P_s\}^{K_c}
\end{eqnarray*}
%
The client chooses a random $p_c$, computes $P_c$, and sends $P_c$
{\it encrypted with its secret key $K_c$} along with the modulus $m$
as pre-authentication data.  The KDC receives the request, decrypts
$P_c$ with its local copy of $K_c$, generates a fresh $p_s$ and $P_s$
of its own, and computes $R \equiv {P_c}^{p_s}$.  Finally, and this is
the critical part, the KDC encrypts the block containing the server
name and session key in $R$ instead of the user's key $K_c$.  The KDC
then sends the AS\_REP to the client along with its own public
exponential $P_s$ encrypted in $K_c$.  The client can decrypt
$\{P_s\}^{K_c}$ to obtain $P_s$, use $P_s$ and its own $p_c$ to
compute $R$, and use $R$ to decrypt the KDC response and extract the
session key $K_{cs}$.

\subsection{Analysis of PA-ENC-DH}

Using $R$ to protect the AS\_REP has two significant consequences.
The new AS\_REP is not vulnerable to a dictionary attack because $R$
is derived entirely from random values unconnected to the user's key
$K_c$.  The new AS\_REP is also not vulnerable to a passive password
chaining attack, because knowledge of $K_c$ only yields $P_c$ and
$P_s$ which are not sufficient to compute $R$.

A dictionary attack against $\{P_c\}^{K_c}$ is not possible because
there is no way for an attacker to verify a correct guess.  $P_c$ has
no number-theoretical properties other than being less than $m$ (this
affects the choice of $m$; see section \ref{sec:m-and-q}) and is
generated from a random number $p_c$; thus, when an attacker guesses
$K_c'$ and gets $P_c'$, there is no way to tell if the guess is
right.\footnote{Note that this is only true if $P_c$ is not encoded
with redundant information (e.g. with ASN.1\cite{ASN1}) before
encryption.}  The same argument applies to $P_s$.  Even an attacker
that computes the potential $P_c'$ for all $K_c$ in the dictionary has
still accomplished nothing because $P_c$ alone will not decrypt the
AS\_REP.  $R$ cannot be computed without $p_c$ or $p_s$, neither of
which is available without computing the discrete log.  Since both of
the random exponentials are encrypted for transmission, it is
extraordinarily difficult to compute the discrete log even for small
values of the modulus $m$.  If $P_s$ were not encrypted, for example,
an attacker could calculate its discrete log $p_s$ and then validate
guesses at $K_c$ by comparing each potentially correct ${P_c'}^{p_s}$
with $R$.  $P_s$ is not available, so the enemy has to perform a
dictionary attack against $\{P_s\}^{K_c}$ and then compute the
discrete log of {\it every} result.

A man-in-the-middle attack is thwarted, as well.  An attacker that
intercepts $\{P_c\}^{K_c}$ cannot predict how a replacement will be
decrypted by the KDC.  If $\{P_c'\}^{K_{fake}}$ is inserted, the KDC
will decrypt to get $P_{unknown}$ and compute $R' \equiv
{P_{unknown}^{p_s}}$; the response will then be encrypted in $R'$ but
will include the legitimate $P_s$.  Since the attacker cannot replace
$P_s$ without knowing $K_c$, the client will compute $R \equiv
{P_s}^{p_c} \not\equiv R'$, and will notice the attack when it is
unable to decrypt the response.

An attacker cannot successfully forge a response from the KDC because
he cannot generate a correct pair $(\{P_s\}^{K_c}, R)$ matching the
client's $p_c$.  Furthermore, since the exchanged key $R$ in the reply
is derived from the value $P_c$ just provided to the KDC, the client
is assured that the KDC's response is fresh and not replayed.  This
guaranteed freshness has the additional benefit that the client can
set its clock by the ticket's timestamp, using the KDC itself as a
secure time service and eliminating Kerberos' dependence on time
synchronization\cite{DAVIS-PERSONAL}. This is a simple variation on
the basic idea presented in \cite{KRB5-TIMESYNC}.

Finally, even if the attacker already knows $K_c$, he still cannot
determine $R$ without performing a discrete logarithm computation.
Without $R$, the attacker cannot obtain the session key $K_{cs}$ so as
to eavesdrop on the conversation.  It is this property that prevents
passive password chaining attacks---if the modulus $m$ used to compute
$R$ is long enough, knowledge of the current password cannot be used
to discover future passwords.

\subsection{Dual-workfactor encrypted key exchange}

The previous analysis of PA-ENC-DH presents a conflict in choosing the
modulus length.  For efficiency, the modulus should be as short as
possible because the KDC's throughput will generally be limited by the
time required to perform exponentiations modulo $m$.  The nature of
PA-ENC-DH allows the modulus to be considerably shorter than that
which would normally be required for long-term Diffie-Hellman
security.  However, a short modulus limits the effectiveness of one of
PA-ENC-DH's primary benefits, that knowledge of the password alone
cannot be used to learn the session key $K_{cs}$ without also
computing a discrete logarithm modulo $m$.  If a short modulus is used
and the user's password is ever compromised, any individual recorded
session protected by that password can be disclosed merely by
computing a single discrete logarithm under the small $m$.  This is a
substantial improvement over the current Kerberos protocol, but does
not fully take advantage of PA-ENC-DH's potential.

The solution is to enhance EKE by using {\it dual-workfactor}
encrypted key exchange, employing a harder public-key problem for the
more critical password-changing messages than for the day-to-day
authentication messages.  In particular, the password-changing
Kerberos exchange should be protected with a modulus that provides
sufficiently long-term protection for the password-changing message
all by itself, perhaps a value 1,024 or 2,048 bits in length.  An
attacker with the user's password will be able to read previously
recorded ordinary sessions protected with the shorter modulus of
perhaps a few hundred bits with only moderate difficulty, but when the
attacker comes to the password-changing session the discrete logarithm
will not be computationally feasible.  The exposure of a disclosed
password will thus be limited to the sessions actually protected by
that password.  Meanwhile, the majority of AS\_REQs used to acquire
normal ticket-granting tickets can still use a smaller modulus for
efficiency.

\section{Implementation issues}
\label{sec:impl}

This section discusses some implementation requirements for the
PA-ENC-DH extension to the Kerberos 5 protocol, including a discussion
of Diffie-Hellman parameter selection.  Familiarity with the discrete
logarithm problem and Kerberos is assumed.

\subsection{Properties of $m$ and $q$}
\label{sec:m-and-q}

Any modulus selected must conform to all the normal requirements for a
good prime for the discrete logarithm problem.  The current
literature\cite{Photuris95,OorschotWi96} recommends using {\it safe
primes} for which both $m$ and $(m-1)/2$ are prime.  These primes are
time-consuming to find but, as described below, can be computed
off-line.

PA-ENC-DH imposes the additional requirement on $m$ that it not
provide an attacker any information that can be used to validate a
guess at a user's password; this is not normally a consideration with
Diffie-Hellman.  Such information can be leaked because, with an
$N$-bit $m$, the random exponentials $P_c$ and $P_s$ by definition
satisfy
%
$$
P_x < m < 2^N
$$
%
but the decryption of $\{P_c\}^{K_c}$ with an incorrect guess of $K_c$
can have any value less than $2^N$ with equal probability.  A guess
$K_c'$ that yields a value
%
$$
m \leq P_c' < 2^N
$$
%
can be immediately discarded as incorrect, reducing the number of
entries in the dictionary for which an attacker must compute a
separate discrete logarithm.  Viewed another way, a guess of $K_c'$
that yields a valid $P_c'$ for a large number of messages has an
improved probability of being correct; in effect, this is a simple
dictionary attack applied over multiple messages instead of a single
message.

This probabilistic attack can be prevented by choosing $m$ to be close
enough to its maximum value $2^N$.
%
\footnote{Bellovin and Merritt suggest an alternative, and perhaps
simpler, solution.  Instead of transmitting $\{P_c\}^{K_c}$, transmit
$\{P_c+rm\}^{K_c}$ where $rm$ is added to $P_c$ using non-modular
addition such that the value encrypted can have any value $0 < P_c+rm
< 2^N$ with equal probability; the legal values of $r$ are discussed
in \cite{BelMer92}.  The legitimate user can be sure the decrypted
value is right and thus can factor out $rm$ after decryption; the
attacker doesn't know whether the decrypted value is greater than $m$
because of the addition or because the guessed password is wrong and
so gains no information.}
%
How close is enough?  The probability that a guess $K_c'$ will yield a
$P_c'$ smaller than $m$, and thus be possibly correct, is ${m \over
2^N}$.  Thus each message will allow an attacker to reduce the size of
the working dictionary for that user by a factor of ${m \over 2^N}$;
the fraction $1 - {m \over 2^N}$ of passwords in the dictionary will
be disqualified.  The effect is cumulative, so if an attacker steals
$M$ messages, the working dictionary will be reduced by a factor of
$({m \over 2^N})^M$\cite{DAVIS-PERSONAL}.

If the attacker's dictionary has $D$ entries and it takes $T$ time to
compute a single discrete logarithm in the field, $m$ must be chosen
so that $D*T*{m \over 2^N}^M$ is still large enough to make the attack
impractical.  It is reasonable to assume that an attacker could
collect on the order of 1,000 messages encrypted in $K_c$---two per
day during login, assuming the password is changed only annually.  If
$m$ differs from $2^N$ by no more than one part in 10,000, the
attacker's work load will be reduced by a factor of $(0.9999)^{1000}
\approx 0.90$, or by about 10\%, which seems reasonable.
Consequently, $m$ should be chosen so that its first 14 bits are all
1.\footnote{The number of most-significant bits of $2^N-1$ and
$p(2^N-1)$ that are equal is $\lceil N-1 - \log_2 (2^N-1 -
p(2^N-1))\rceil \approx \lceil N-1 - \log_2 ((2^N-1)(1-p))\rceil
\approx -\lceil \log_2 (1-p) \rceil$.  For $p = 0.9999, -\lceil \log_2
0.0001 \rceil = 14$ bits.}

If the modulus $m$ is a safe prime, the generator $q$ can be 2; the
provides an additional speed advantage\cite{OorschotWi96}.

\subsection{Generation of exponents}
\label{sec:exponents}

The most recent work on how long Diffie-Hellman exponents need to be
in order to provide sufficient security\cite{OorschotWi96} confirms
the widely held opinion that the exponents should be twice as long as
the symmetric key that will be derived from the exponentially
exchanged key.  For Kerberos, the longest keys currently in use are
168 bits, for Triple-DES.  Thus, the exponents need be at least 336
bits long.  Note that if the exponentials are not a multiple of the
symmetric cryptosystem's block size in length, the extra high-order
bits of the last encrypted block of $\{P_x\}^{K_c}$ must be filled
with random data\cite{BelMer92}; alternatively, the exponentials'
length can simply be rounded up.

The exponents $p_c$ and $p_s$ selected by the client and KDC must be
``random'' in order for PA-ENC-DH to be secure.  The question of how
much randomness is needed and how it can be generated on a computer
without a hardware random number source is still unresolved.
\cite{RFC1750} and \cite{P1363-RND} address this issue and provide
various implementation suggestions.  The implementation must be
careful not to use the client's password $K_c$ to generate random
exponents in a way that will expose it to an indirect dictionary
attack.  For example, a guessable seed for a PRNG whose output is
encrypted with $K_c$ will provide at least some verifiable bits of
plaintext to an attacker.

\subsection{Modulus length recommendations}

To perform a dictionary attack against PA-ENC-DH, an enemy must
compute a discrete logarithm for every password guess.  The cost of a
dictionary attack is therefore the product of the time to compute the
logarithm and the size of the attacker's dictionary.  The best
algorithms for computing discrete logarithms are executed in two
phases, a pre-computation phase and a per-exponent phase.  The
pre-computation phase involves building a large, modulus-specific
database and is the time consuming portion of the attack.  The
per-exponent phase is relatively fast.  In fact, \cite{LaMacchiaOd91a}
estimates that discrete logarithms for a 192 bit modulus can be
computed in only several minutes after pre-computation is complete.
If ``several minutes'' for a 192 bit modulus actually means five
minutes, it would take just less than a year to try 100,000 passwords,
after pre-computation.  Depending on site password policies and the
importance of past sessions remaining secret, that may not be long
enough.  As described in section \ref{sec:exponents}, the modulus must
be at least 336 bits anyway.  This might be sufficient, but it seems
prudent to use a 512 bit modulus for now.  \cite{Photuris95} states
that pre-computation on a 512 bit modulus currently takes about a
year.  Assuming per-exponent computation time grows at least linearly
with length, an attacker would then have to spend at least several
more years guessing passwords.  This is probably strong enough
protection for a user that might choose a guessable password.

%Clearly, the choice of a modulus length for normal AS\_REQs depends
%heavily on the per-exponent computation time after pre-computation is
%complete.  The problem is that there does not appear to be any
%literature reporting experimental results for the order of growth of
%the per-exponent computation as a function of modulus length for
%moduli longer than 192 bits.  This lack is not surprising, as without
%EKE the time required for per-exponent calculations is too low to be
%cryptographically relevant.  Nevertheless, the information is critical
%for EKE.

The situation is more clear for the password-changing modulus.  The
modulus must be chosen with the assumption that an attacker already
knows the user's password and, therefore, the public exponentials.
Only one discrete logarithm computation will be required.  Therefore,
the modulus must be long enough to prevent the pre-computation phase
entirely.  \cite{Photuris95} suggests that 1,024 bits is enough to
protect a single modulus for a decade, and a 2,048 bit modulus is
currently believed to prevent discrete logarithm computation forever.
Since passwords are typically changed at most monthly and often much
less frequently than that, a reasonably high delay can be tolerated,
so there is no good reason not to use 2,048 values.

\subsection{Configuration of moduli}

The specific modulus to use for each transaction is not a fixed
constant for the protocol but rather is specified by the client as
part of the protocol message itself.  This is necessary to allow
dual-workfactor encrypted key exchange.  It also frees the protocol
from being tied to a specific modulus which may be found to be too
short or too weak for other reasons.  

Moduli can be site-specific and changed as often as necessary to keep
up with computational speed increases and theoretic developments.  The
various moduli a client is allowed to use should be specified in a
configuration file (e.g. \v{/etc/krb5.conf}) that is available on all
client hosts.\footnote{Clients must verify that the moduli meet the
requirements of section \ref{sec:m-and-q} to prevent trojan horse
values.}  Two classes of moduli must be specified, one for normal
authentication and one for use with the password-changing protocol.
The client can simply choose one of the listed values, and then
include it in the PA-ENC-DH message; alternatively, the protocol could
be designed to specify an index into a list of moduli for transmission
efficiency.  The KDC should have a copy of the same list of moduli and
accept a message based on any of them, but refuse a message based on
any other value on the grounds that it may not be secure.

\section{Consequences and limitations of PA-ENC-DH}

PA-ENC-DH only prevents {\it passive} password chaining attacks
against recorded sessions.  An attacker that knows the user's password
and fully controls the network (rather than merely being able to
listen on the network) can perform an {\it active} man-in-the-middle
attack by replacing the encrypted exponentials in the client's and
server's message with its own value.  The attacker can then allow the
client and server to complete the password change without interruption
while at the same time learning the user's new password.
Interestingly, it seems {\it almost} possible for a client to detect a
man-in-the-middle attack by timing the password-changing protocol,
since an attacker is forced to compute several exponentiations
himself; however, a clever attacker can avoid such
detection\cite{DAVIS-PERSONAL}.

PA-ENC-DH does not actually provide pre-au\-then\-ti\-ca\-tion of the
client's request to the Kerberos server.  Furthermore, it makes using
other forms of pre-authentication questionable since some of them
(e.g. PA-ENC-TIMESTAMP) will re-expose the client's password to a
dictionary attack.  This implies that it is once again not possible to
have any control whatsoever on who requests tickets for a given user.
As PA-ENC-DH solves the problem that pre-authentication was designed
to solve better than pre-authentication does, this is not really a
drawback.

The lack of pre-authentication does expose PA-ENC-DH to an
undetectable on-line password guessing attack\cite{DinHor95}. Since
the KDC cannot authenticate the entity performing an AS\_REQ or detect
the freshness of a request, an attacker is free to make password
guesses by performing the AS\_REQ protocol with PA-ENC-DH
pre-authentication at any time.  This is not a serious threat,
however.  The KDC can be modified to allow only a certain number of
requests per day and refuse (or simply log to a high-priority channel)
any requests over the limit.  An upper limit of perhaps 20 requests
per day will be more than enough for users but still low enough to
prevent such on-line guessing attacks.

The KDC is sometimes used to maintain state about user logins
(e.g. invalid login attempts, last login time) that provide useful
administrative information.  Pre-authentication allowed this
information to be considered ``trustworthy'' because a request with
bad pre-authentication data would be rejected without updating user
state.  Without pre-authentication, the KDC cannot tell a valid
request from an invalid one.  However, most of this information can be
tracked just as usefully without pre-authentication---there is no loss
in security, for example, of considering the last login time of a user
to be the time of the last AS\_REQ, authenticated or not.

\section{Conclusion}

With only a single modulus, EKE can either prevent password chaining
but make the protocol slow, or prevent dictionary attacks without
protecting against password chaining.  Dual-workfactor encrypted key
exchange allows EKE to be used efficiently to prevent both of these
attacks.

PA-ENC-DH simultaneously solves three long-standing limitations of
Kerberos: vulnerability to dictionary attacks, dependence on insecure
time synchronization, and vulnerability to password chaining.  There
are other solutions for at least the first two of these problems,
notably password quality and secure time protocols, but none of them
solve all three problems simultaneously and with such simplicity.
Although other public-key modifications of the Kerberos protocol have
been proposed that accomplish some or all of these goals, only
PA-ENC-DH does so without introducing extra protocol exchanges or
requiring substantial protocol modification.  PA-ENC-DH also preserves
the primarily symmetric-key nature of Kerberos, giving it both higher
performance and better long-term security prospects than purely
public-key based systems.

The PA-ENC-DH protocol can be varied and generalized in many ways.  It
applies to essentially any password-based key server protocol, not
just Kerberos.  Any number of different workfactors can be employed to
provide an appropriate level protection for multiple categories of
transactions.  Diffie-Hellman exponential key exchange can be replaced
with many other public-key cryptographic algorithms, notably including
elliptic curve cryptography, which may provide substantial practical
benefits such as greater resistance to cryptanalysis.

Naturally, PA-ENC-DH should not be used as an excuse to lessen the
emphasis on choosing quality passwords nor on protecting those
passwords carefully.  A password-based protocol will still be more
secure with PA-ENC-DH and a good password than with PA-ENC-DH and a
bad password.

\section{Acknowledgements, patents}

Don Davis and Brian LaMacchia reviewed early drafts of this paper and
provided substantial helpful discussion and analysis of PA-ENC-DH.
Don also introduced me to Bellovin and Merrit's previous work in this
area after reviewing an initial sketch of this paper.

Diffie-Hellman exponential key exchange is covered by a
U.S. patent\cite{HelMer80} which expires in March, 1997.  Bellovin and
Merrit's Encrypted Key Exchange is covered by a
U.S. patent\cite{EKE-PATENT} which expires in August, 2010.

\bibliography{paper,rivest-crypto}
\bibliographystyle{plain}

\end{document}
