| ||||||||||||||||||||||||||||||||||||||||||||||||||||
| Pp. 113–128 of the Proceedings |  |
Naomaru Itoi ![[*]](https://www.engin.umich.edu/pics/latex2html/foot_motif.gif)
Center for Information Technology Integration
University of Michigan
itoi@eecs.umich.edu
because (1) physical security
tends to be overlooked in commodity hardware, (2) software bugs
inevitably introduce
security threats, and (3) new systems introduce new problems. Most of
the security software available today ignores these difficulties, and
simply asserts system
integrity. The reasoning behind this assertion is that physical
attacks are more difficult to execute than software attacks.
However, this assumption can no longer be considered reasonable as the value of information stored in computers increases. For example, the CIC Security Working Group reported the theft of a medical server that contained highly private information, such as social security numbers and medical histories of many donors at a university hospital. Considering the private nature of the stolen information, the damage the incident caused was extremely serious [19].
The time is right to begin addressing the flawed assumption that physical attack is unlikely and that system integrity is intact [32]. One approach is to employ secure hardware with the following considerations in mind. First, such hardware should be physically tamper resistant. Second, to minimize software flaws, it should be simple and throughly tested. Secure hardware is now being mass produced and is becoming more widely available (e.g., [21,8,43]), so it can now be more readily integrated with existing computer infrastructures. In this effort, we secure one of the most critical component in current computer systems: the trusted third party in Kerberos, namely, the Kerberos Key Distribution Center (KDC).
We integrated the IBM 4758 secure coprocessor into the Kerberos KDC, which has resulted in the implemented KDC preserving critical secrets even when compromised. This paper presents the motivation, design, security consideration, implementation, and performance evaluation of the project.
We use the term "card" to refer to the 4758, and "host" to refer to the workstation to which the 4758 is attached.
Many researchers have identified the problem of physical security of distributed computer systems [20,49,37]. Unlike mainframe computers of the past, in isolated computer centers, today's computer environment consists of physically distributed personal computers and workstations, connected by networks. Such an environment is difficult to protect because computers are geographically distributed, making it more difficult to control physical access. Further, PCs and workstations have weaker physical protection than mainframes in that physical access to computational and storage devices is typically possible by simply opening the cover of the computer. For example, a hard disk drive can be easily removed from a personal computer. Once it is removed, an adversary can mount it on his own computer to access it, or can make a copy and analyze it off-line. Some PCs and workstations have locks, but these tend to be of low quality and easily defeated [13].
Arbaugh et al. have pointed out that without a secure bootstrap process, the integrity of operating system kernels cannot be trusted because malicious code (e.g., Trojan horse) can be injected in the bootstrap process [1]. For example, typical PCs can be booted from floppy disks, thus allowing arbitrary operating system kernels to run, even malicious ones or ones with Trojan horses. Some of them allow the administrator to set a BIOS password, preventing booting unless the password is entered. However, an adversary can reset the password by resetting the BIOS [13].
Bugs and design flaws in software, which are unavoidable, can be exploited. For example, buffer overflow in an administrator privileged (root) process can allow an adversary to run arbitrary code with administrator privileges. Vulnerable software ranges from operating systems to applications. Some examples are as follows:
Such vulnerabilities can be quite serious. For instance, they may yield administrative rights to an adversary, crash the computer system, or leak critical information.
The computer security community deals with such flaws by publishing countermeasures as soon as vulnerabilities are found. However, searching for vulnerabilities is an endless chore, as it is impossible to be confident that the software is bug-free. In addition, computer systems are developing quite rapidly, and new systems tend to bring new problems.
For example, the new functionality of Java [18] enabled client side programming on the Internet. At the same time however, a design flaw in Java caused a mismatch between the language and the bytecode, leaving the Java Virtual Machine open to attacks [29], and implementation bugs made Internet browsers vulnerable [9]. In many ways, the new technology itself enabled new kind of attacks [46,28].
It is dangerous to assume the integrity of an operating system's kernel and software, as most software does. This is problematic especially for security critical software, such as trusted third parties.
The T3P is a critical point of attack on a network. The damage caused by a T3P compromise is extremely serious. In particular, it is catastrophic to have the KDC compromised, as the keys of all the members can be obtained by an adversary. With all the member keys in hand, the adversary can decrypt all the secrets encrypted with the keys, and can impersonate any member. To recover from KDC compromise, all keys must be revoked and regenerated, affecting every member. Compared with KDC, CA has better characteristics when compromised because CA stores public keys, but not private keys. However, CA compromise is still quite damaging, as an adversary can impersonate anyone by crafting bogus certificates.
Therefore, to keep systems secure, T3Ps must have the highest security. However, as described in the previous section, fundamental security problems pose a significant challenge to obtaining high levels of security with current computer systems.
We employ the IBM 4758 secure coprocessor because of its superior security and programmability. The 4758 is a PCI card with a tamper-resistant and tamper-responding secure coprocessor.
The 4758 is physically protected with layers of epoxy and metal so that it does not leak information out of the barrier, has electromagnetic shielding, and cannot be accessed without the card detecting it. The card detects opening attempts, penetration attempts, temperature attacks, and radiation attacks.
This has three types of storage: RAM,
battery-backed up RAM (BBRAM), and flash memory. On detecting an
attack, the card responds by resetting all the data in RAM and BBRAM,
thus preventing an adversary from obtaining any information. RAM is
4 MB of volatile memory. BBRAM is 8.5 kilobytes of non-volatile
secure memory. Flash is 1 MB of non-volatile memory.
Validated with the FIPS 140-1 Level 4 standards, this coprocessor is one of the most trustworthy and secure coprocessors [42].
In addition to its security, the 4758 has very good programmability. Applications that run in the card are written in C, and can be debugged with a run-time debugger [12].
It has a very fast cryptographic accelerator (20 MB/s
bulk DES and 20 signatures/s of RSA with 1024 bit modulus),
which allows for efficient implementation of security protocols.
[41,21].
It is natural to use the most secure hardware for the most critical component. To demonstrate the potential of secure hardware integration in T3P protocols, and to counter one of the fundamental security limitations of Kerberos, we integrated the 4758 into Kerberos V5 KDC.
This paper presents the secure coprocessor integration with Kerberos KDC project. The next section provides the motivation behind the project by referring to related work. Section 3 describes the design of the integrated protocols. The security of our design is discussed in Section 4. Section 5 presents the prototype implementation. Performance evaluation of the prototype is presented in Section 6. Discussion and future work are in Section 7.
In this document, it is assumed that readers have some knowledge of the mechanisms of Kerberos. Readers who are not familiar with them are advised to consult available literature [3,44,27,25,26].
This section reviews the work most closely related to our research. Section 2.1 introduces Kerberos. Section 2.2 describes approaches taken by researchers to address goals similar to ours, and the relationship between their approaches and ours. Section 2.3 discusses secure hardware integration with the Kerberos client.
, and computers, is assigned a secret
key, which is shared between the principal and the KDC.
Kerberos is used in universities to protect their computer network environments. CMU, Cornell, MIT, Stanford, the University of Michigan, and many more embrace it. It is also part of the products of many corporations such as Transarc, Cisco, Qualcomm, IBM, and Microsoft, whose Windows 2000 employs it as a fundamental network authentication method. Many network applications are modified to work with Kerberos, including login, ftp, telnet, PAM, ssh, AFS, and DFS. Its security has been thoroughly analyzed [2,27], and it scales quite well. For example, three replicated Kerberos servers at the University of Michigan serve 180,000 users. It is also quite portable. Both the clients and the servers run on almost any UNIX or Windows systems. We believe that Kerberos will continue to be an important security system.
A huge security issue for Kerberos is the common problem of KDCs, that is, it yields all the keys when compromised [2,32]. MIT Kerberos V5-1.0.6 stores a master key, which encrypts the other keys, in cleartext in a file (/usr/local/var/krb5kdc/.k5.DOMAINNAME). Keys of the principals, i.e., the user keys and the service keys, are encrypted with the master key and are stored on hard disks. Therefore, if an adversary has administrative rights for the KDC's computer or physical access to its disks, all the keys can be stolen.
More concretely, the master key is stored in the battery-backed up RAM in the 4758 and never leaves. Because of storage limitations, user keys are stored in the host and encrypted with the master key. The 4758 has BBRAM of 8.5 kilobytes and 1 megabytes of flash memory, allowing it to securely store many DES keys. However, storage in the host is more abundant than storage in the 4758, and a Kerberos realm, for example, at a university, may require a huge number of keys, so we decided to store them in the host.
When user keys are used, for example, to encrypt a ticket, they are downloaded from the host to the 4758, decrypted there with the master key, used, and then deleted from its memory. Session keys are also generated in the 4758, augmented into tickets, and encrypted in the 4758 before being shipped to clients.
To solve this problem, we designed the protocol with the 4758 in Figure 2. Note that all the encryption and decryption is done in the 4758, and no key is in the host in the clear. This protects the keys from an adversary who compromises the host.
The 4758 generates the ticket and the reply only if requests are consistent, namely, the following conditions are met:
Otherwise, it rejects the requests. As a result, the adversary cannot fool the 4758 to generate tickets and replies for her advantage.
In the protocol using the 4758, all the encryption is done in the 4758, and no key is in the host in the clear. Consistency checks similar to the ones in process_as_req take place.
We start with constructing a model of our system. The model consists of the following participants:
We make the following assumptions in our model. Some of these assumptions are discussed in detail in a related paper [22].
As problems of the security of client workstations are out of this paper's scope, client workstations are assumed to be secure, namely, (1) a client workstation does not steal user's information, and (2) it does not alter or modify messages a user sends.
The problem of dictionary attack against user chosen passwords is out of this paper's scope; passwords are assumed to be chosen carefully so that the dictionary attack against them is impossible.
Our principal cipher is DES, which is assumed impossible to compromise in reasonable amount of time. This may not be a good assumption any more in the age of fast DES crackers [14], but Kerberos will eventually replace DES with triple-DES, thus eliminating the brute force attack to DES.
Mallory can read and modify any information in KDC-host, and can make KDC-host do anything she wants.
Mallory can neither read nor modify any information in KDC-4758. When she tries, 4758 deletes all the information in it. Mallory cannot influence the behavior of KDC-4758.
Without 4758
Mallory can steal all keys by compromising KDC-host. This is possible by Assumption 5.
With 4758
Mallory cannot steal any key. The master key is in KDC-4758, and is not readable (Assumption 1, 6). All the other keys are in KDC-host, but are encrypted by the master key, with DES, which is unbreakable (Assumption 4).
Without 4758
Mallory can impersonate any user by stealing or guessing the user key.
With 4758
Mallory cannot impersonate any user. First, she cannot steal a user key. Second, the other way of impersonating a user (Alice) is to obtain a ticket {Alice, Bob, KA,B}KB and the session key KA,B. Mallory can obtain the ticket by sniffing the network (Assumption 7), but this is impossible as well. The session key is generated in KDC-4758 and is always encrypted by KA or KB when it is outside KDC-4758. KA and KB are strong (Assumption 3), so the session key cannot be obtained. These keys cannot be stolen from client workstations (Assumption 2).
Without 4758
Mallory can generate any ticket or reply by using stolen keys.
With 4758
Mallory cannot generate a ticket or reply on her advantage. KDC-4758 generates them only after Alice showes possession of her key through preauthentication, and consistency is checked as described in Section 3.1.
As the performance evaluation in Section 6 shows, the overhead of calling a function in the 4758 is high. Therefore, to obtain high performance, the six calls should be combined into one call. However, as cryptographic code and non-cryptographic code are tightly coupled together in Kerberos, doing so changes the order of execution and breaks modularity, thus significantly complicating the host side code. For this prototype, we decided to make six calls in each AS and TGS, valuing simplicity and manageability over performance. A detailed look at the overhead in Section 6.2 explains our decision.
User keys are stored in the host and encrypted with the master key. The
card decrypts the keys before using them. The host-side
decrypt_key() function sends keys to the card, decrypts them
and then stores them in RAM for future use. The function
is called three times in AS: first
for Alice's key for preauthentication, second for Bob's key for
ticket encryption, and third for Alice's key for reply
encryption.
Preauthentication is the step in which Alice proves her identity to the KDC by proving knowledge of her key. By default, preauthentication takes place in the following three steps:
Because this step requires the use of Alice's user key, this function is moved to the card. The 4758 decrypts the timestamp and verifies it. If the timestamp is invalid, following requests, e.g., ticket encryption and reply encryption, are rejected.
A ticket is a data structure sent from the KDC to Alice to establish a session key. Roughly speaking, it is {Alice, Bob, Kses}Kbob. Part of the ticket is not security critical, and is generated in the host. Afterward, the ticket is sent to the card, filled with the session key generated in the card, encrypted with Kbob, and sent to Alice. The card stores the session key for future use because the reply will include it as described in the next paragraph.
Similar to the ticket, the reply {Bob, nonce, Kses}Kalice includes a public part, which is encoded in the host and is sent to the card. The session key, generated in the ticket encryption function, is inserted into the reply. The card then encrypts the reply with Alice's key.
TGS decrypts the ticket granting ticket, or TGT ({Alice, krbtgt, Kses}Kkrbtgt), to obtain Alice's name and the session key. Because it involves the TGS key (Kkrbtgt), and the session key is in the TGT, this step must be carried out in the card. The card decrypts the TGT and returns it in the clear to the host excluding the session key. The session key must not leave the card, so it is stored in RAM in the card. Later it is used in authenticator decryption and reply encryption.
The authenticator {Alice, time, (subkey)}Kses is decrypted in the card. The timestamp is checked in the card.
To provide a better abstraction, we developed the Secure Hardware Remote Procedure Call (SHRPC), which parses the interface definition file and generates C programs to handle the low-level communication details. With SHRPC, procedure call abstraction is provided to the host. As a consequence, modification in the host side is merely to call SHRPC stub functions, e.g.., decrypt_key(), instead of equivalent but more elaborate functions in the host.
Although interface definition language (IDL) should follow some standards, such as rpcgen, we picked our own simple IDL for rapid implementation. The interface definition file for the Kerberos / 4758 integration looks like this:
# Interface Declaration File
# for the Kerberos V5 / 4758 Project
# 8/6/1999, Naomaru Itoi
PROG: krb5_4758
FUNC: decrypt_key
IN:
int type
# type :
# 0: client key
# 1: server key
string enc_key
OUT:
int tick
...
-
Each measurement was carried out ten times and an average is presented in tables. Variance was very small.
This section describes the performance of AS. kinit is the client program used to initiate the AS request. The total time kinit spends with or without 4758 is shown. To exclude the time spent for password typing, the password is hard coded in the kinit program. kinit with the 4758 takes 34% more time than kinit without it.
| time (sec) | |
| kinit without 4758 | 0.0611 |
| kinit with 4758 | 0.0820 |
sclient is the client we used to initiate the TGS request. sclient with the 4758 takes 33% more time than sclient without it.
| time (sec) | |
| sclient without 4758 | 0.0719 |
| sclient with 4758 | 0.0953 |
4758 integration introduces approximately 33% of overhead in both cases. We look into the details in the following sections.
| Total | Card Time | Overhead | |
| AS w/o 4758 | 0.00054 | - | - |
| AS w/ 4758 | 0.02535 | 0.00866 | 0.01669 |
| TGS w/o 4758 | 0.00032 | - | - |
| TGS w/ 4758 | 0.02748 | 0.00866 | 0.01882 |
Communication overhead is approximately twice as much as the card time in both AS and TGS. This is an obvious bottleneck and there is an obvious optimization. Theoretically, the number of calls can be reduced from six in each AS and TGS to one in AS and two in TGS. All operations can be done at once in AS. In TGS, the TGT (ticket granting ticket) must be decrypted to obtain the name of the client before the KDC looks up its database. In contrast, ticket encryption and reply encryption must happen after the database lookup. Therefore, TGS requires two calls. This optimization would reduce the card time to 0.00278 seconds in AS and 0.00314 seconds in TGS, thus reducing the overhead of using 4758 to 11% in AS and 15% in TGS.
Although communication overhead was the bottleneck, it is also useful to study the details of the time spent in the card. Breakdown of AS and TGS is shown in the following table. For each function, total time and time spent in main components are presented.
AS
| function | contents | time (sec) |
| decrypt_key | 24B DES decryption | 0.000957 |
| TOTAL | 0.001109 | |
| kdc_preauth | 40B DES decryption | 0.000997 |
| CPGetTime | 0.000023 | |
| TOTAL | 0.001445 | |
| encrypt_tk | 168B DES encryption | 0.001191 |
| random number gen | 0.000352 | |
| random number gen | 0.000352 | |
| 168B CRC | 0.000041 | |
| TOTAL | 0.002078 | |
| encode_kdc | 216B DES encryption | 0.001270 |
| random number gen | 0.000352 | |
| 216B CRC | 0.000053 | |
| TOTAL | 0.001809 |
TGS
| function | contents | time (sec) |
| decrypt_key | 24B DES decryption | 0.000957 |
| TOTAL | 0.001115 | |
| decrypt_tk | 168B DES decryption | 0.001172 |
| 168B CRC | 0.000041 | |
| TOTAL | 0.001324 | |
| rd_rec_dec | 120B DES decryption | 0.001113 |
| 120B CRC | 0.000031 | |
| TOTAL | 0.001230 | |
| encrypt_tk | 168B DES encryption | 0.001191 |
| random number gen | 0.000352 | |
| random number gen | 0.000352 | |
| 168B CRC | 0.000041 | |
| TOTAL | 0.002105 | |
| encode_kdc | 184B DES encryption | 0.001211 |
| random number gen | 0.000352 | |
| 184B CRC | 0.000045 | |
| TOTAL | 0.001773 |
DES operation takes the longest time. Considering that the hardware
implemented DES
takes much longer time than the software implemented CRC even though
the hardware itself is quite fast (20 MB/s ), we
believe the most of the DES operation time is spent in making a system
call to DES hardware and setting up a key
schedule. For
an application that operates on such small data (100 - 200 bytes),
which we believe
many authentication and authorization systems do, it is good to
provide (1) software implementation of crypto operations to save system
call overhead and (2) a decoupled API for DES key scheduling separate
from DES operation. (2) is helpful because some keys are used
repeatedly, e.g., a master key.
In Sections 3 and 4, discussions were made assuming a user name and the key of the user are encrypted together. However, this is not the case in our prototype because the key data structure in MIT Kerberos V5-1.* does not include the user name in it.
When preauthentication fails, either because it is not encrypted with an appropriate key, or timestamps do not match, the 4758 should reject the following operations, namely, ticket encryption and reply operations. This has not been implemented yet.
Consistency check described in Section 3.1 has not been implemented.
Authenticator check described in Section 5.3.2 has not been implemented yet. The 4758 simply decrypts and returns the authenticator.
Integration of secure hardware into a security protocol can be significantly simplified if the original implementers of the protocol anticipate the use of secure hardware. Complication of our work comes from cryptographic operations and non-cryptographic operations being tightly coupled in a program, e.g., they coexist in one function. If they are decoupled cleanly in an initial implementation, the work of integration is merely to move the crypto code to the secure hardware. Moreover, we believe the separation is good for portability of the protocol, e.g., to switch from one encryption system to another.
Unfinished implementation, discussed in Section 7.1 should be completed to realize the claimed security.
We have not addressed problems associated with administration: changing passwords, adding / removing principals, changing the the KDC's policy, etc.
The Kerberos Database (KDB) is the database in which Kerberos stores its critical information, e.g., the keys and the principal attributes; it is accessed by administrators through kadmind. Because the data in the KDB are sensitive, the entries are encrypted with the master key. As a consequence, in the 4758 integrated KDC, administration requests must go through the 4758.
An adversary can attack a Kerberos/4758 system by attacking the channel between the administrator and the 4758. For example, one possible attack, which could reduce the advantage of integrating the 4758 into Kerberos, is a Trojan horse in the administrator's terminal. If it can interrupt the operations by the administrator, it can steal sensitive information, e.g., user passwords. In fact, this secure I/O problem is a general concern for any security system, which requires the administrator be trustworthy, and the administrator's terminal be secure.
We plan to address these concerns by carrying out mutual authentication and establishing an encrypted connection between a system administrator and the 4758 with Kerberos authentication, and using the connection to securely transfer requests by the administrator to the 4758.
This will partially achieve our goals because the administrator is authenticated via Kerberos, and communication is encrypted. However, it is not possible to provide a completely trusted terminal with current commercial hardware, even with secure hardware such as the 4758, because even if the processors and storage are trusted, the I/O devices may not be. For example, a keyboard or a display instrumented with a hardware eavesdropper can steal administrators' keystrokes. However, it is much easier to keep a terminal secure during administration than to keep a Kerberos server secure in 24 hours a day, seven days a week fashion. Therefore, we defer solving this problem of secure I/O.
As described in Section 6.2, the six calls to the 4758 in AS and TGS should be combined into one and two calls respectively to optimize the performance. The drawback of this optimization is that it changes the Kerberos code significantly. In the Kerberos/Cartel meeting in July of 1999, we sensed that such a radical change would pose a major challenge to Kerberos developers with regard to maintaining the source code. Therefore, we decided to first implement a prototype to determine what the computer systems community thinks about it before proceeding to the deployment step.
If an adversary has access to messages passed between the host and the 4758, he or she can obtain a plaintext-ciphertext pair. Some messages are encrypted with single DES and the master key. This is problematic because given a plaintext-ciphertext pair, DES key can be cracked by a brute force attack in a week [14]. Kerberos distribution from MIT supports triple DES, eliminating this threat.
Our Kerberos/4758 protocol stores the master key inside the 4758, which encrypts the other keys with this master key and stores the ciphertext on the host. An adversary (Mallory) cannot access these plaintext keys even if she compromises the host because she does not know the master key, which never leaves the 4758.
However, without additional measures, such a protocol suffers from replay attacks if Mallory can learn one of Alice's old passwords. The replay attack is carried out as follows:
To avoid this attack, we use key version numbering and obsolete key caching. First, all the keys in the Kerberos database have a key version number, N. This key version number is different from the key version number used in the original Kerberos V5 protocol. An encrypted key entry contains this version number, i.e., {Alice, Kalice, N}. When Alice changes her password, Alice's current key version number is updated to N+1. The 4758 generates a new key entry {Alice, Kalice', N+1}, sends the entry back to the host, and caches a pair {Alice, N+1} in its internal memory.
The 4758 checks the cache whenever it receives a key from the host. If the version numbers do not match, then the key received is obsolete. To avoid cache overflow, once in a while (e.g., daily) the 4758 regenerates the new N and computes the new entries for all the keys, and sends them back to the host.
The cache should not overflow too quickly. If the cache size is 1MB and each entry is 32 bytes, then the maximum number of entries in the cache is 32K entries -- which we imagine exceeds the maximum number of password changes in a day. (Furthermore, some preliminary tests indicate that the time needed for cryptographic operations to regenerate the cache is not excessive.)
We plan to make the source code freely available.
I thank Sean Smith, Ronald Perez, and Dawn Song at IBM research for their advice and discussion, especially for bringing up the replay attack described in Section 7.3, and suggesting the countermeasures. I thank Peter Honeyman at the University of Michigan, Mark Lindemann and Joan Dyer in IBM research, and the Kerberos developers for their help and discussion. I thank Chris Feak and Evan Cordes at the University of Michigan for assistance on English writing.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split +0 master.tex.
The translation was initiated by Naomaru Itoi on 6/14/2000
|
This paper was originally published in the
Proceedings of the 9th USENIX Security Symposium,
August 14-17, 2000, Denver, Colorado, USA
Last changed: 29 Jan. 2002 ml |
|
