[2833] in Kerberos
Kerberos non-repudiation idea
daemon@ATHENA.MIT.EDU (Donald T. Davis)
Sun Oct 3 00:41:49 1993
From: "Donald T. Davis" <don@GZA.COM>
Date: Sun, 3 Oct 93 00:22:16 EDT
To: miller@suite.com
Cc: kerberos@MIT.EDU
jim_miller@suite.com wrote:
Don Davis and Ralph Swick from MIT described a private-key authentication
mechanism that, with some modifications, I think can provide a practical
private-key non-repudiation mechanism that can be built into Kerberos 5.
much as i would like to see private-key signatures gain acceptance,
i think there is no chance of krbv5 incorporating a signature mechanism,
just because v5 is a done deal. further, i don't think this notary
function should be part of the kerberos server's responsibility.
Although interesting, this mechanism is not very efficient.
Alice needs to send every message she receives to the Authentication
server for translation, verification, and re-encryption.
your solution for this inefficiency is, i believe, natural and correct:
only the message-checksum should be encrypted. we thought that this
detail was self-evident, and so left it out of our paper.
other efficiency improvements are possible, also.
of course, if bob wants to send his message privately to alice, and
without setting up a network connection with her, he'll still have to
accept the inefficiency of bulk-encryption.
My proposed additions involve a mechanism for obtaining a private-key
certificate from the Authentication server (could be built into kinit)...
actually, kinit already can be the mechanism for certificates' issuance,
because certificates are just long-lived tgts, anyway.
The format of the private-key certificate could be something like:
certificate = {nonce,
time issued,
lifetime,
certificate key,
principal name} Authentication server's private key
On the message sending side, Kerberos code would XOR the MD4 (or MD5) hash
of the principal's message with the nonce present in his private-key
certificate, and then encrypt the result with the key contained in the
certificate. The result will be called the message signature:
msg signature = {msg hash XOR certificate nonce}certificate key
here, your "nonce" seems to offer little if any extra security; it's really
just a key for an extra layer of vernam encryption under the des layer
this extra layer would only be useful if each "nonce" and certificate were
used only once, but if you're worried about cryptanalysis, triple-key des
would be more effective insurance.
in the literature (Gong, Saltzer, et al, in SOSP '89), this one-time-pad trick
has been called a "confounder;" it was briefly considered for krb v5 tickets,
when v5 was being designed.
The message signature and the principal's certificate can be placed in the
authenticator sent with the message. (No need to publish certificates in
Directories.)
for email-type applications, this works, but for others, directories will still
be valuable.
The recipient of the message will continue to use standard Kerberos
mechanisms to authenticate messages. However, since this is a
non-repudiable message, the recipient must also verify that the
message signature is valid.
...
As with tickets, certificates could be sent with the first non-repudiable
message to a given destination. Or it could be sent with every
non-repudiable message, thus relieving the destination process from
having to manage sender's certificates.
agreed.
Problem: If an attacker obtains the sender's credentials, then the
recipient is in big trouble. The certificate she archived with the sender's
message has been potentially compromised. The sender can now claim that
the attacker sent the message.
To help with this problem, we can alter the message signature validation step
described earlier. Instead of simply verifying the message signature and
returning a yea or nay, the Authentication server will also return an
encrypted *something* that indicates that a given message signature was
successfully validated at a time when the certificate was believed to be
secure. Let's call this *something* a "validated message signature":
validated message signature =
{random,
timestamp,
original message signature,
sender's certificate,
checksum
}Authentication server's private key
All that the recipient would need to archive would be the original message
and the validated message signature.
It is now possible for a recipient to re-authenticate the origin of an
archived message, even after the sender's certificate has become compromised.
it's not as simple as this, because the recipient needs to know that this
archival signature is itself authentic, because its contents are hidden from
the recipient. this is straightforward to fix, though.
One problem with the private-key non-repudiation mechanism I've been
describing is that everybody's archives of validated message signatures
become (potentially) compromised if the Authentication server's private
key becomes compromised.
Here are some possible solutions to this problem.
1) Extend the certificate creation protocol to enable an application to
acquire a second private-key certificate from an Authentication server
higher up in the Authentication server hierarchy. The application can
then use this second certificate to periodically send itself a
non-repudiable message that contains a hash of the current contents
of its message archive. The validated message signature the application
receives back from the remote Authentication server can be used to prove
the integrity of the application's message archive (at a given time),
even if the local Authentication server becomes compromised.
2) Periodically hash your message archive and send the hash to Bellcore's
timestamping service.
In either case, it might be sufficient to periodically hash only the
incremental changes to your message archive, rather than the entire message
archive.
this sounds right to me, though it also sounds burdensome.
Now for the 64 dollar questions...
Is what I have just described really secure? Does it seem useful?
your efficiency improvements are ones i knew about already, so i certainly
believe they're secure. i don't believe the "nonce" and special certificate
format are necessary. your signature archive mechanism is similar enough to
one that i devised (since writing the paper) that i believe it's right, too.
of your ideas, my favorite is the signed hash of the message archive;
i had believed that a compromised translator key would inevitably invalidate
old signatures.
-don davis
openvision/geer zolot associates
1 main st. cambridge, ma 02142
(617) 374-3713 x228
