1	Intrusion-Tolerant Password-Enabled PKI Xunhua Wang wangxx@jmu.edu Commonwealth Information Security Center & Department of Computer Science James Madison University
2	Outline Background: password-enabled PKI Virtual soft token Virtual smartcards Intrusion-tolerant password-enabled PKI Related work Building blocks Intrusion-tolerant virtual soft token Intrusion-tolerant virtual smartcards Operational and performance issues Summary
3	Background: password-enabled PKI “Smartcard-based PKI has not happened yet” Passwords are widely used for authentication Ease of use Support user roaming very well Integrate passwords into PKI? Password-enabled PKI A user possesses a password only This password is used to facilitate the management of user’s private key Private key is protected by a password Stored on a centralized server
4	Virtual soft token & Virtual smartcard Virtual soft token (Perlman/Kaufman, 1999; Kwon, 2002) Private key is encrypted by the password User downloads the password-encrypted private key for use Require user authentication before the downloading → password The downloading should be performed over a secure connection Virtual smartcards (Sandhu/Bellare/Ganesan, 2002) The private key is split into two parts A password-derived value d₁ Another value, d₂, is stored on the server Require user authentication before d₂ is used
5	The dark side Passwords are susceptible to the dictionary attack People tend to choose easily memorizable passwords A password of 8 characters, if randomly chosen from the printable characters, has entropy of 52.6 bits An attacker tries the passwords from a dictionary, instead of exhausting all 52.6 bits Password-derived values using public functions are also vulnerable to the dictionary attack Proactive checking? It helps People can still find ways to beat the checking and (Wu, 1999) found that 10% of the passwords are still not safe
6	Virtual soft token & Virtual smartcard
7	Dictionary attack in password-enabled PKI Network-based dictionary attack Eavesdropping-based dictionary attack Password-based authentication: both The downloading of the password-encrypted private key: virtual soft token The using of d₂: virtual smartcards Dictionary-based active protocol attack Password-authenticated key exchange (PAKE) protocol Password is used for authentication only Public key techniques are used to establish a cryptographically strong session key: NO PKI! Server compromise-based dictionary attack
8	Server compromise-based dictionary attack
9	Server compromise-based dictionary attack Server compromise is inevitable: inside/outside attackers, misuse of honest insiders What are stored on the centralized server? Virtual soft token Password verification data (PVD) → dictionary attack Password-encrypted private keys → dictionary attack Virtual smartcards Password verification data (PVD) → dictionary attack d₂ → dictionary attack Approach: intrusion tolerance Server compromise does not necessarily damage the security of passwords and private keys
10	Intrusion-tolerant password-enabled PKI Using multiple servers (say, n) to store the password-protected private key Compromising some (less than t) of these servers does not enable dictionary attacks The system can still function even some servers are shut down Intrusion-tolerant password-enabled PKI Intrusion-tolerant virtual soft token Intrusion-tolerant virtual smartcards Building blocks: threshold PAKE, secret sharing & password-adapted threshold cryptography
11	Related Work
12	Building block 1: threshold PAKE First proposed by (MacKenzie, et al, 2002) Share a PVD among multiple servers Only a threshold number of PVD shares are required for a user authentication The shared PVD is never reconstructed during an authentication computation An authenticated cryptographically strong session key is established after successful authentication New research for efficiency and provable security
13	Building block 2: password-adapted threshold cryptography Password-adapted threshold RSA: two distributed RSA First, d = d₁ + d₂ mod j(N): non-threshold Share d₂ among multiple servers using Shoup’s (t, n) threshold RSA t servers are required for a digital signature d₂ is never reconstructed during a signature
14	Intrusion-tolerant virtual soft token
15	Intrusion-tolerant virtual soft token
16	Intrusion-tolerant virtual smartcards
17	Intrusion-tolerant virtual smartcards
18	Operational Issues Transparent to users Server management Can be automated through a management server Normally the management server stays offline Password change Password change in the intrusion-tolerant PAKE Password update in Virtual soft token: simple Virtual smartcards: d₂ changes, computation intensive
19	Performance Analysis Computation & communication Intrusion-tolerant virtual soft token Threshold PAKE + one digital signature Not an issue for general PCs Faster algorithms are required for restricted environment Intrusion-tolerant virtual smartcards Computation Threshold PAKE is the same as intrusion-tolerant virtual soft token Parallel computation improves the performances: 3 modulo exponentiations for a digital signature
20	Summary Intrusion-tolerant password-enabled PKI Intrusion-tolerant virtual soft token: threshold PAKE + secret sharing Intrusion-tolerant virtual smartcards: threshold PAKE + password-adapted threshold cryptography Operational and performance issues
21	Questions?