Real-world access control - all or nothing

This blog post is inspired from a poster appeared in this year's CERIAS symposium. Up until I saw this poster, I had not put much thoughts into real-world access control for general use cases such as accessing a bank account, mobile phone service account, electricity service account, etc. Specially on the issues of separation of duty and principle of least privilege. In this post I will be focusing on the second issue of least privilege. In general terms, the principal of least privilege means that a user should be allowed to access (read/write/update/delete) only those resources required for the job at hand. If a user needs to read only a specific resource R1, it is a bad idea to grant read access to all resources, and worse to grant write access also.

Let's take a simple example from MySQL database app.

The database has three users; root, user_ro and user_rw. As we know, root can do anything to the database. user_ro and user_rw have the following grants:

GRANT SELECT ON db1.* TO 'user_ro'@'localhost';
GRANT SELECT, INSERT, DELETE, UPDATE ON db1.* TO 'user_rw'@'localhost';

So, user_ro can only read tables from db1 and user_rw can read/write to tables from db1. In a typical database app, when you want to allow users to read only data from tables (i.e. reading a forum without login for example), you connect to the database using user_ro; when you want to allow users to write also, you connect to the database using user_rw. And when you want to perform administrative tasks you connect as root. Why do we not use one single database account to do all this? The answer is the principle of least privilege. What does it buy you? If your system is compromised, the amount damage caused can be controlled by having different accounts with different privileges. For example, if the application is compromised while user_ro is used to connect to the database, the attacker can only read the database, and nothing else. (The granularity of the application of the principal of least privilege and the practical management privileges is another issue that is worth a separate blog post. So, I will not go into that in this post.) 

Now let's consider the access control in real-world applications.

I am sure most of us have online back accounts. We have one username and one password to connect to the web site and do whatever operation we want on our account. In other words, one username and one password provide all or nothing access. However, after successful log in, we do not perform all available tasks each time we log into our bank account; in fact, we don't use more than 90% of the operations that we are authorized to do. Let's simplify the operations and break them down to two operations (read only, read & write) for the sake of simplicity:


(a) read balances, credit card transactions, etc.
(b) transfer money (for example from checking to saving, checking to credit card, pay bills, transfer to an external account, etc.)

It is the usual practice to perform (a) much more often over (b). That is, users will be performing read-only operations most of the time.

From the security point of view, a better authentication mechanism would be to associate each user with two username/password accounts. For example, user Bob has two accounts bob_r/pw_r and bob_w/pw_w. bob_r/pw_r allows Bob to do (a) and bob_w/pw_w allows Bob to do (b).

If this is more secure, why banks today don't implement such a scheme? The answer is usability [3] and manageability. Managing one password is already a burden. Managing several passwords is going to be a nightmare for both users and banks. Even though password based authentication is known to be vulnerable [2, 4], it does not appear to be replaced by any other alternative approach any time soon [1]. As we colloquially say we are stuck with passwords! So, with this assumption of legacy passwords continuing to be in existence, can we come up with a better password based approach to provide principal of least privilege in real life applications?

The ideal approach should use only one username and one password to provide the same level of usability as earlier. However, it appears that it is not possible to use the same username/password to provide the separation of duty with least privileges and provide better security against attackers.

One preliminary approach would be to order the privileges in the increasing order, in our case (a), then (b), and always login the user with the least privilege (a). In order to perform an operation that requires a higher privilege, the service provider (bank) should ask the user something that he/she knows and but that information should not be readily derivable from users initial login password. Such a solution works if users majority of time are doing only (a), but introduces usability issues if  users frequently want to do (b). Further, if there are more levels of privileges, it further complicates the situation. Do you have a better idea?

I am interested to know if there are any research that has already attempted to solve this issue using password based authentication only. Please share if you know any such work.

 

[1] The Quest to Replace Passwords
[2] Password Security: A Case History
[3] Users are not the enemy, CACM
[4] Foiling the Cracker

[ABE] How to re-encrypt without decrypting in the cloud?

ABE (Attribute Based Encryption) is a great invention by security researchers and allows to efficiently perform group based encryption. While it provides many benefits, revocation of users has been a key issue of utilizing ABE (FYI, another key issue is key escrow problem where one party knows all secret keys - as far as I know this is still an open problem. If you are looking for a ground breaking research topic, it could be this one; but be warned - it's hard, you may not find a solution ;) ). The most common way of revoking attributes in ABE is to periodically refresh secret keys given to users. (Another approach is to use short-lived attributes. For example, use a time based attribute which expires after a certain time in the future.) While this approach works, it does not scale: when there are many users, regenerating keys and sending them to users have a huge overhead. This also requires re-encrypting already encrypted documents to match the new keys. In this blog post, I am looking at an alternative approach that we can utilize. This blog post is inspired from the techniques presented in a recent paper by Sahai et al. [1] and the attribute delegation work done by Goyal et al. [2].

In a real life situation, revocation needs to handle two things:
(1) Make the policy under which data is encrypted is invalid for revoked user(s).
(2) Re-encrypt the affected data to reflect the revocation. (If we do not re-encrypt, a revoked user can use her old credentials to access the encrypted data.)

Let's get started using a simple example.
 
Bob shares an encrypted file in a public cloud with Alice, Ted and Tim. In order to make the encryption process efficient, Bob can a group encryption technique such as ABE (attribute based encryption) or BE (broadcast encryption) or even a simple symmetric key encryption. For this example, we focus only on ABE. I will devote a separate blog post for broadcast encryption.The beauty of the group based encryption technique is that Bob needs to do ONLY ONE encryption for all the people with whom he shares the file.

Some background information: In a modern group based encryption scheme, users are assigned attributes and the users having the same set of attributes belong to the same group. Let's say for this example, Bob has tagged Alice, Ted and Tim with the attributes "cool_friend" and "buddy", and is using ABE cryptosystem.

 Access control policy

Bob has his own KGC (key generation center) to run the ABE cryptosystem. Bob generates the master secret key MK and public key PK. (Keygen(k) --> MK, PK)

 Keygen operations

Encrypt(SK, M, policy("cool_friend", "buddy") steps

Bob does not trust the public cloud, so Bob uses a client side encryption as shown above (Encrypt(SK, M, policy("cool_friend" AND "buddy")) --> C) and keeps the secret key secret from the public cloud.

 Secret Key generation for Alice and Tim (Similarly for Ted - not shown above)

Secret keys for users are generated by Bob based on a linear secret sharing scheme. Shamir's secret sharing scheme is the most popular choice. For simplicity, for this example, I am using simple addition as the linear secret sharing scheme. (Notice that the secret keys given to Alice and Tim and generated using different sets of secret shares. This is to prevent collisions. Interested readers are encouraged to read [3] for more in-depth details on preventing collisions.) For complex monotonic policies, the typical approach is to build an access tree and internally use the Shamir's secret sharing scheme.

Now Alice, Ted and Tim can decrypt the document using their secret keys.

Alice decrypting Bob's message

After some time, Bob decides that he no longer wants Tim to access the encrypted file. Tim's credentials still allow him to decrypt the encrypted file. So, Bob needs to re-encrypt the file so that Tim can no longer decrypt the file.

In a typical ABE setting, how does Bob do this revocation?
a. Generate new secret keys for Ted and Alice for the attribute "cool_friend" and "buddy", and send these to them (this process results in a new master secret key SK' and public key PK' as well.)
b. Download the encrypted document from the cloud and decrypt it (Decrypt(SK, C) --> M) and re-encrypt (Encrypt(PK', M, policy("cool_friend" AND "buddy")) --> C') and upload back to the cloud.

Can we do better? Can we delegate the re-encryption to the cloud itself? (The subject of this post.)
Decrypt -> Re-encrypt is off the table since in order to do that, Bob needs to give SK to the cloud, which is what Bob does not want to do in the first place - Bob wants to hide the content from the cloud. So, is there a way out for this problem?

One possible approach is as follows:
- Execute step 1
- Ask the cloud to do an onion encryption over the current encryption
Problem: size of the onion gets bigger and bigger as we do more revocations.


Can we do better? Yes, we can incrementally change the ciphertext using the technique called ciphertext delegation [1]. I am showing you a simplified version of ciphertext delegation here. Please read [1] for more details.

The idea behind ciphertext delegation is to allow another party to re-encrypt a file under a more restrictive policy than the original policy without decrypting the file. That is, originally encrypted as Encrypt(PK, M, P) = C, then do the delegation: Delegate(PK, C, P') = Encrypt(PK, M, P'), where P' is a more restrictive policy than the original policy P.

How can we encrypt under a more restrictive policy? Recall that the policies we deal with have a linear structure. We can restrict such policies in many ways. Here are some possible approaches:
- increase node threshold (for example from OR to AND)
- add an additional attribute to the access tree
- remove a subtree from the access tree

For illustration purpose, I will be using the second option. I am introducing a new attribute called "time" to restrict the policy.

Restrictive policy

Bob uploads some public information to the cloud so that it can re-encrypt and also some additional public information to allow only Alice and Ted recover the secret components for the attribute "time". It is done in a way that Tim will not be able to recover the secret for the attribute "time". Hence, Tim will not be able to satisfy the new restrictive policy.

New public information given to the cloud to re-encrypt in the cloud

Additional secret given only to Alice and Ted

Bob can use several approaches to give this additional secret only to Alice and Ted. One approach is that Bob may give this secret directly to Alice or Ted. Another approach is to utilize a broadcast encryption technique to encrypt this secret for only Alice and Ted and upload to the cloud as public information.

The following equations shows how the cloud does the re-encryption:

Alice and Ted can generate the following value:

It is easy to see that using their other credentials and the above new value, Alice and Ted can decrypt the re-encrypted file. However, as Tim cannot generate the above value, he will not be able to access the re-encrypted file.

It should be noted that the above scheme fails if Alice or Ted collude with Tim. I leave the readers to figure out a collision resistant way to do the ciphertext delegation (hint: read [1] :) I hope this post gave you some idea about how to do re-encryption for ABE in the cloud itself without decrypting.


References:
[1] http://eprint.iacr.org/2012/437.pdf [CRYPTO 2012]
[2] http://research.microsoft.com/en-us/um/people/vipul/abe.pdf [CCS 2007]
[3] http://eprint.iacr.org/2004/086.pdf [CCS 2006]