[512] in Kerberos
Ticket Authentication
daemon@TELECOM.MIT.EDU (Ted Anderson)
Tue Oct 18 13:43:05 1988
From: Ted Anderson <ota+@andrew.cmu.edu>
To: kerberos@ATHENA.MIT.EDU
This is a follow up message to my earlier proposal for changes to the Kerberos
ticket format. That proposal is fairly long so I don't want to include it but
if anyone is interested in a copy, send me a note and I will forward you my
original message.
I've done some more reading on the problems of authentication and have concluded
that the current mechanism for detecting modifications of Kerberos tickets
should be augmented. The basic problem is that although plaintext-ciphertext
block chaining (pcbc_encrypt in the Kerberos distribution) is an improvement
over the DES Standard CBC mode of operation it still has several weaknesses.
These problems result in several simple modifications to the encrypted ticket
failing to propagate errors to the end of the ticket when it is decrypted.
Changes like swapping two ciphertext blocks or inserting blocks whose xor is
zero have this problem. While it isn't clear that these modifications will lead
to usable (for an intruder) changes to the decrypted ticket information, it is
hard to make a convincing case that no one will ever be able to exploit this
weakness.
Most authentication schemes rely on a cryptographic checksum appended to the
message which is then encrypted (if secrecy is desired) using CBC mode. While
using DES for the checksum seems excessively expensive for Kerberos, a simpler
hash function would still be useful. A very cheap solution is to append the
arithmetic sum of all the bytes in the ticket. A better function is suggested
in the X.509 draft standard for directory authentication. It uses
multiplication with a suitably chosen modulus to combine the blocks to be
checksummed. A modulus less than 2^16 and a block size of 8 bits should result
in a inexpensive algorithm for most machines that can do small multiplies nearly
as fast as adds.
The more fundamental issue in authentication is that the message being
authenticated must contain sufficient redundancy to make it unlikely that a
random message would be accepted. Adding a 16 bit checksum is really just
adding 16 bits of redundancy. However, the redundancy is distributed over the
whole message such that a modification to any bit is equally likely to produce
an incorrect checksum. In contrast, inserting two zero blocks into a ticket at
a point within the name has a probability of (255/256)^16 (or about 94%) of
going undetected, at least as far as format goes.
Since I earlier suggested removing the server name from the ticket using the
argument that it was redundant, it seems appropriate to give some attention to
the total redundancy in the ticket. Here is a list of fields and the
approximate (in some cases very approximate) redundancy of each.
flags: 8 bits. Assuming only one value is legal.
session key: 8 bits. The parity requirement on DES keys provides a bit per
byte.
name, instance, realm: 24 bits. The requirement that each end with a null
supplies about 8 bits each, the length limits and the requirement that the
name is at least one character long provides only a small additional amount.
host address: 32 bits. Assuming this is checked, and there is only one
correct host address.
starttime, endtime: 16 bits. I assumed 128K seconds as the maximum lifetime
and a bit for the fact that the interval must be positive.
This totals 88 bits plus the 16 bits of checksum. A very respectable amount.
I'm very interested in comments and suggestions on this suggestion as well as
the other aspects of the ticket proposal.
Ted Anderson
