From: Paul Rubin on 16 Jun 2010 00:37 Paul Rubin <no.email(a)nospam.invalid> writes: > I have an idea for an improvement, that I"ll try to work out and write > up later. OK, how does this sound: You have n accounts, numbered 1...n. You want to be able to verify logins, to let the user change their own password, and to lock the account if there are too many unsuccessful login attempts. You want validation to depend on a hardware token (successful validation can issue a credential signed by the token), and validation and password change should both resist database replay attacks (i.e. if someone changes their password, then restoring an old copy of the database shouldn't re-enable the old password). The unsuccessful login lockout should also resist database replay. That means that every password change or unsuccessful login should change some internal state in the hardware token, which has limited internal memory. So let's store the hashes in a database, with rows 1...n. Each row will (conceptually) contain a unique key for that row (generated by the token), a password hash with IV, and a login failure count, plus possible timestamps and things like that if desired, with the whole row encrypted and MAC'd by the token. The encryption and MAC keys are derived from the unique key for the row (the "row key"). The row key is derived as explained further down. The database must be able to atomically update O(log n) rows in a single transaction. That can be done with a typical SQL database, or with a functional data structure like an AVL tree serialized to disk, or whatever. The db also has to be able to undo its most recent committed transaction (just keep a record of the values before the update). We can view the encrypted row keys as a binary tree, with uid 1 at the root and uid's 2k-1 and 2k as the children of uid k. uid k's key encrypts the keys of both its children. uid 1's key is encrypted by a master key M inside the hardware token. So decrypting uid k's key requires using the complete chain of keys starting at the token's master key down to uid k, i.e. it can be encapsulated inside the token and requires log2(k) decryptions. Updating the row key for uid k (replacing the key with a new random one) requires updating its sibling (uid (k xor 1)) and the complete chain of parent keys and their siblings, i.e. 2*log2(k) operations. Also, k's two children have to be rewritten to migrate the encryption of their (unchanged) row keys to k's new key. When a person wants to log in to a given uid U and presents a password to check, do the following: 1. The application reads the chain of db entries for the uid and its children, parent, grandparent, etc. up to the root (db[2*U], db[2*U-1], db[U], db[U//2], db[U//4], ..., db[1]) and the siblings of each of these nodes. It sends this chain to the hardware token (in the case of tokens with small memory like cheap smart cards, this can be sent and processed as multiple smaller messages--they don't have to all be in memory at once, just a few chaining keys). 2. The token uses its master key M to decrypt the chain of row keys starting at the root. It generates new row keys for each row in the chain, re-encrypting and MAC'ing all the requisite fields and making an updated version of each row (call this new chain the "update list"). The token examines (and verifies the MAC) of the failure count for uid U, and if it's already too high, the login attempt fails. If it's not too high, the token checks the password, and uses the password to generate the new row for U. If the password is incorrect, the token increments the failure count by 1 in U's slot of the update list. If the password is correct, the failure count is set to zero. Row 1 of the update list's row key is encrypted by a newly generated key M2, created and saved in the token. The token then sends the update list back to the host and asks it to update the db by atomically replacing all those rows. The host db is now in a state indicating whether U's password check has failed or not, but (because U's row is encrypted by the token) the host can't yet tell which of these conditions applies. (The token may also emit an encrypted audit record saying what has happened). 3. The host now tells the token that it has committed the update. After receiving this notice, the token does its own commit by internally replacing M with M2. In the success case, the token sends the host a login credential; and in the failure case, it informs the host of the failure. Either way, the host doesn't learn of the password's success or failure, until after the failure count is committed and synchronized in the db and token. 4. If the application fails to commit (such as by crashing) it can ask the token to roll back its side of the transaction. The rollback is ok since the token has not yet given a credential, so the host hasn't learned anything, and it can try again without penalty. (There is a possible issue that the host may have given the -correct- password and gotten the failure count reset without getting a credential, which might evade some auditing generated when issuing credentials--I don't know if it's worth making some adjustments to deal with this, especially if the token is also generating some other audit trail). 5. If the application commits but the token crashes before it can do its own commit, the application may have to undo its last transaction, which it can do by keeping the old data around temporarily. 6. Password change is basically similar to the above. 7. In a high security (e.g. financial) application, the version of M that the token uses for normal login has no capabilities other than described above. Resetting a lost password can require a separate copy of M (made within the token) with extra capabilities, accessible only through a blob secured by another key, e.g. on a smart card held by a customer service representative, or by a special role on the token, etc. 8. It may be possible to save some space in the rows by not storing the uid in them, since the token always knows which row it is examining or encrypting. The row number can instead be included in the key derivation process. That means if someone tries to substitute one row for another, the MAC will still fail even though there is no uid under the MAC. I could imagine this being useful in something like an OpenID server, where the password check and the relying service are run by separate entities, and a password break could affect many such services. I may try coding it. It is similar to (and somewhat inspired by) something I did for secure erasure a while back: http://groups.google.com/group/sci.crypt/browse_thread/thread/56bee118fd127d01/8ce7eb156bc6085d
From: Kristian Gj�steen on 16 Jun 2010 04:49 Paul Rubin <no.email(a)nospam.invalid> wrote: >Paul Rubin <no.email(a)nospam.invalid> writes: >> I have an idea for an improvement, that I"ll try to work out and write >> up later. > >OK, how does this sound: >[secure external storage used for password storage] Could you store the password hashes only as leaf nodes in your tree? That might reduce the token's cryptographic workload, especially if your per-password record are largish (several times the key size). >I could imagine this being useful in something like an OpenID server, >where the password check and the relying service are run by separate >entities, and a password break could affect many such services. Is the following correct? The idea is to protect the users against compromise of the OpenID server, by essentially removing the password database from the OpenID server and placing it in secure hardware. When the OpenID server is compromised, anyone logging in will have their password compromised, but anyone who doesn't log in will not have their password compromised. Also, the credential is important. The relying party should be able to verify the credential, but not forge it. If this holds, the relying party can use the credential as evidence that the token was involved in the login process. -- Kristian Gj�steen
From: Paul Rubin on 16 Jun 2010 13:17 Kristian Gjøsteen <kristiag+news(a)math.ntnu.no> writes: > Could you store the password hashes only as leaf nodes in your tree? > That might reduce the token's cryptographic workload, especially if your > per-password record are largish (several times the key size). Sure, that is reasonable. The hashes don't have to be in the tree at all. Only the row keys really have to be there. But, I think that except for the smallest tokens, the cryptographic workload is not that large to begin with. 2 * lg n * the record size = perhaps a few hundred primitive crypto operations. > Is the following correct? The idea is to protect the users against > compromise of the OpenID server, by essentially removing the password > database from the OpenID server and placing it in secure hardware. > When the OpenID server is compromised, anyone logging in will have their > password compromised, but anyone who doesn't log in will not have their > password compromised. Yes, good point, I was thinking more about offline attacks using a captured host, than compromising the host but keeping it running. To protect passwords of people logging in, the token could have its own SSL stack and handle the login/password dialog internally, using the host as encrypted external storage. For that matter, though, maybe tokens now available have enough internal persistent storage (multi-GB flash chips are cheap) to just hold the whole database. Then it doesn't need the tree structure or anything like that. I don't know what's happening with hardware tokens these days. Last time I had anything to do with them, the fancier ones were getting to be almost like PC's, which didn't seem like such a good thing. Maybe they're even more like that now. > Also, the credential is important. The relying party should be able > to verify the credential, but not forge it. If this holds, the relying > party can use the credential as evidence that the token was involved in > the login process. Also a good point. If the credential has a public-key signature from the token, thogh, that's probably more cryptographic workload than all the symmetric stuff described earlier.
From: Kristian Gj�steen on 16 Jun 2010 16:12 Paul Rubin <no.email(a)nospam.invalid> wrote: >If the credential has a public-key signature from >the token, thogh, that's probably more cryptographic workload than all >the symmetric stuff described earlier. For sure. I find that when you start playing with a light-weight idea like this, you start adding new features and suddenly you need an HSM rather than a light-weight token. -- Kristian Gj�steen
|
Pages: 1 Prev: File Handling in Ada -95.- Demonstartion. Next: Sexual Contact Privacy |