[2832] in Kerberos
Kerberos non-repudiation idea
daemon@ATHENA.MIT.EDU (Jim Miller)
Wed Sep 29 22:57:15 1993
From: jim@bilbo.suite.com (Jim Miller)
Date: Wed, 29 Sep 93 21:26:45 -0500
To: kerberos@MIT.EDU
Reply-To: Jim_Miller@suite.com
About a week ago I posted 3 posts to comp.protocols.kerberos describing an idea
I have for incorporating a non-repudiation mechanism into Kerberos. None of
the posts made it back to me via the Kerberos mailing list. Therefore, I am
assuming that the bridge between the news group and the mailing list is either
broken or only one-way. This being my assumption, I'm going to post the
non-repudiation idea directly to the mailing list. I apologize if you end up
seeing this twice.
------------------------------------------------
[all three posts merged into one, with edits]
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.
They describe their mechanism in a paper titled "Network Security via
Private-Key Certificates". You can get this paper via ftp at:
athena-dist.mit.edu:/pub/kerberos/doc/net_sec_cert.PS
In their system, every principal publishes a *private-key certificate*. A
principal's certificate contains the principal's identity and a private key
that is valid for the life of the certificate. The certificate is encrypted
using the Authentication server's master key. These certificates can be
published in world readable Directories, just like public-key certificates.
Let's say Bob wants to send a message to Alice. Instead of getting a ticket
for Alice, as in Kerberos, Bob encrypts the message using the key that is in
his private-key certificate.
Alice receives the message from Bob. To read and authenticate this message,
Alice must retrieve Bob's private-key certificate from the Directory and then
send the message, Bob's certificate, and her own certificate to the
Authentication server. The Authentication server will decrypt Bob's
certificate, retrieve Bob's private key and decrypt the message, and re-encrypt
the message with Alice's private key, which it obtained from Alice's
certificate. The Authentication server then sends the message back to Alice.
Alice will now be able to read the message. The reply from the Authentication
server also contains information that assures Alice that Bob really did send
the message.
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. However, with some modifications, I *believe*
this system can be used as a practical private-key non-repudiation mechanism.
.
.
Application's should be able to demand that some, but not necessarily all,
messages be non-repudiatable (Is that a word? Well, it is now.).
I propose continuing to use the standard Kerberos 5 protocol for most message
authentication. However, since the Kerberos protocol does not supply a
non-repudiation mechanism something else must be added to the standard protocol
to achieve non-repudiation.
My proposed additions involve a mechanism for obtaining a private-key
certificate from the Authentication server (could be built into kinit), a
mechanism for using the certificate at the message sending side, and a
mechanism for using the certificate and the message receiving side.
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
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.)
The recipient of the message will continue to use standard Kerberos mechanisms
to authenticate messages. However, since this is a non-repudiatable message,
the recipient must also verify that the message signature is valid.
Since the message signature is encrypted using a key unknown to the recipient,
she must send it to the Authentication server for validation.
To validate the message signature, the recipient sends a new message hash, the
message signature, and the sender's certificate to the Authentication server.
The Authentication server decrypts the certificate and obtains the certificate
nonce and the certificate key. The Authentication server uses the certificate
key to decrypt the message signature. The Authentication server then XOR's the
result with the certificate nonce and obtains the original message hash.
If the new message hash equals the original message hash, then the
Authentication server can assert that the message signature is valid and that
principal identified in the certificate is the originator of the message.
The validation of the message signature can take place in parallel with the
recipient's own conventional authentication of the message. If the message is
a requests for a database transaction, then the recipient can perform all of
the transaction except the commit. The commit can be held until the recipient
receives the validation reply from the Authentication server.
Upon receiving the reply from the Authentication server, the recipient archives
the message, the message signature, and the sender's private-key certificate.
If, at a later date, the recipient wishes to re-authenticate the origin of the
archived message, she can send a new message hash, message signature, and
sender's certificate to the Authentication server as described above.
Discussion:
How do you get a certificate? You could generate a new certificate as often as
you wish (could be built into kinit, for example).
It would work something like this:
Bob logs onto a system. Through the process of logging in, Bob acquires a new
ticket-granting-ticket, session key, new private-key certificate, and a
corresponding certificate nonce and certificate key pair. Both the
ticket-granting-ticket and the certificate are encrypted using the
Authentication server's private key. These items are cached the same way
credentials are currently being cached.
Bob uses applications that send messages to other processes. The messages are
authenticated using the conventional Kerberos authentication mechanisms.
Occasionally, Bob does something that requires him to send a non-repudiatable
message. In addition to the normal Kerberos ticket and/or authenticator, Bob
also sends a message signature and his private-key certificate. The recipient
of the message authenticates the message and validates the message signature in
the manner described above.
.
.
As with tickets, certificates could be sent with the first non-repudiatable
message to a given destination. Or it could be sent with every
non-repudiatable message, thus relieving the destination process from having to
manage sender's certificates.
.
.
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.
.
.
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-repudiatable 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.
--------
Now for the 64 dollar questions...
Is what I have just described really secure? Does it seem useful?
I not a cryptographer, so I'm only making educated guesses when I say that this
or that is secure or is required.
Any and all comments appreciated.
Jim_Miller@suite.com
