improving kadmind change-password performance

[Danny Thomas]

One of our systems is used by a large number of new users to set their
password. I've resolved issues with the front-end and performance is
now constrained by kadmind, something I've never been involved with.

kadmind hits 100% CPU when load-testing with <100 simulated clients.
We want to cater for at least 500 concurrent users and see the average
time scale linearly to around 30secs with this number of clients.

Is this the sort of performance we'd expect (currently 2006 Xeon) ?

I tend to think the CPU comes from crypto operations and there'd be a
big benefit from spreading the load across cores.

The Makefile uses pthread but htop shows it using only 1 CPU.

I saw a commit "Use blocking locks in krb5kdc and libkadm5srv"
mentioned on the mailing list. Would that help ?

Finally, kadmind is only accessible from a few of our servers so is
there any opportunity to use faster but weaker crypto methods for a
service not exposed to end-users ?

RedHat EL5, kerberos client and server both on locally built 1.10.3

FWIW we're using the Authen::Krb5::Admin perl module to do this
sub kadmin_cpw ($$)
{
my ($uid, $password) = @_;
# error-checking removed
# my $kadm5 = Authen::Krb5::Admin->init_with_skey('...', '/etc/keytab');
my $kadm5 = Authen::Krb5::Admin->init_with_password('...', '...');
my $krb5_principal = Authen::Krb5::parse_name($uid);
my $success = $kadm5->chpass_principal($krb5_principal, $password);
}


cheers
Danny Thomas

[Greg Hudson]

On 11/11/2012 04:40 PM, Danny Thomas wrote:
> kadmind hits 100% CPU when load-testing with <100 simulated clients.

For password changes, kadmind has to run the string-to-key algorithm on
the new password for each enctype in supported_enctypes (which defaults
to AES-256, AES-128, DES3, and RC4). The string-to-key algorithm for
the AES enctypes is deliberately slow in order to make dictionary
attacks harder. I believe this operation is swamping any other
performance bottlenecks.

> I tend to think the CPU comes from crypto operations and there'd be a
> big benefit from spreading the load across cores.

Our kadmind is single-threaded, and we don't currently have any support
for multiple worker processes or client-side selection between multiple
kadmind servers.

I can't think of any reason why you couldn't run multiple kadmind
processes for the same realm on different ports, but it would be
entirely manual; each kadmind process would need its own config file,
and the front-end would need to choose between multiple client config
files in order to select a particular kadmind port.

> I saw a commit "Use blocking locks in krb5kdc and libkadm5srv"
> mentioned on the mailing list. Would that help ?

I doubt it will help if you're pegging the CPU. It might help with
other problems which might arise under load. It would probably be
required in order to make multiple kadmind processes play well together
under load.

> Finally, kadmind is only accessible from a few of our servers so is
> there any opportunity to use faster but weaker crypto methods for a
> service not exposed to end-users ?

The crypto operations used to protect the password change operation are
probably not the performance bottleneck; instead, it's the operations
used to turn the password into a set of keys. Since those keys will be
used by the KDC as well as kadmind, you probably don't want to use
weaker enctypes.

However, you could reduce the list of enctypes used in
supported_enctypes in order to reduce the number of string-to-key
operations kadmind has to perform. The default value is:

aes256-cts-hmac-sha1-96:normal aes128-cts-hmac-sha1-96:normal
des3-cbc-sha1:normal arcfour-hmac-md5:normal

You can reduce it from there. supported_enctypes should be placed in a
[realms] subsection of kdc.conf (or krb5.conf if you don't use kdc.conf).

It's also possible, in theory, to shift the burden of the string-to-key
operations to the client using the setkey RPC. But there's no
command-line interface to this RPC, and the documentation for
Authen::Krb5::Admin doesn't suggest that it provides a binding for it.

[Booker Bense]

On Sun, Nov 11, 2012 at 8:50 PM, Greg Hudson <ghu...@mit.edu> wrote:

> On 11/11/2012 04:40 PM, Danny Thomas wrote:
> > kadmind hits 100% CPU when load-testing with <100 simulated clients.
>
> For password changes, kadmind has to run the string-to-key algorithm on
> the new password for each enctype in supported_enctypes (which defaults
> to AES-256, AES-128, DES3, and RC4). The string-to-key algorithm for
> the AES enctypes is deliberately slow in order to make dictionary
> attacks harder. I believe this operation is swamping any other
> performance bottlenecks.
>
>

I would want to see the profile data before I made any recommendation.

" premature optimization is the root of all evil "

In my experience even when you know the code base extremely well, you can
often
be quite wrong about where the time is actually spent.

- Booker C. Bense

[Tom Yu]

Booker Bense <bbe...@gmail.com> writes:

> I would want to see the profile data before I made any recommendation.
>
> " premature optimization is the root of all evil "
>
> In my experience even when you know the code base extremely well, you can
> often
> be quite wrong about where the time is actually spent.

A certain part of the test suite that creates a large number of
principals (with known passwords) became measurably slower after a
change to make supported_enctypes include AES. I did not keep the
data around anywhere that I can recall though.

[Nico Williams]

On Tue, Nov 13, 2012 at 3:50 PM, Booker Bense <bbe...@gmail.com> wrote:
> On Sun, Nov 11, 2012 at 8:50 PM, Greg Hudson <ghu...@mit.edu> wrote:
>> For password changes, kadmind has to run the string-to-key algorithm on
>> the new password for each enctype in supported_enctypes (which defaults
>> to AES-256, AES-128, DES3, and RC4). The string-to-key algorithm for
>> the AES enctypes is deliberately slow in order to make dictionary
>> attacks harder. I believe this operation is swamping any other
>> performance bottlenecks.
>>
>>

> I would want to see the profile data before I made any recommendation.
>
> " premature optimization is the root of all evil "
>
> In my experience even when you know the code base extremely well, you can
> often
> be quite wrong about where the time is actually spent.

FWIW, Heimdal has a perf test, and it shows that password
authentication crawls by comparison to keytab authentication. Given
this I completely agree with Greg's diagnosis. A quick test would be
to measure how many randkey operations/second kadmind supports (when
no other activity is going on, of course).

Nico
--

[Roland C. Dowdeswell]

On Tue, Nov 13, 2012 at 05:16:51PM -0500, Tom Yu wrote:

>

> Booker Bense <bbe...@gmail.com> writes:
>
> > I would want to see the profile data before I made any recommendation.
> >
> > " premature optimization is the root of all evil "
> >
> > In my experience even when you know the code base extremely well, you can
> > often
> > be quite wrong about where the time is actually spent.
>

> A certain part of the test suite that creates a large number of
> principals (with known passwords) became measurably slower after a
> change to make supported_enctypes include AES. I did not keep the
> data around anywhere that I can recall though.

It is also relevant to note that this is by design. The string to
key function employed by AES (PKCS#5 PBKDF2[1]) is specified in such
a way to frustrate dictionary attacks on more modern hardware than
the older string2key functions and the key to frustrating dictionary
attacks is to ensure that it is more computationally difficult (and
memory intensive in the case of scrypt[2]) to perform the operation.
PKCS#5 PBKDF2 has an iteration count that may [hopefully] be
increased as computational power increases and therefore over the
course of time this will continue to dominate the setting of passwds
thus limiting the speed of creating principals or changing passwds.

[1] https://tools.ietf.org/html/rfc2898

[2] http://www.tarsnap.com/scrypt.html

--
Roland Dowdeswell http://Imrryr.ORG/~elric/