Authentication and authorization systems can be found in almost every software system, and consequently affects every aspect of our lives. Despite the variety in the software that relies on authorization, the authorization subsystem itself is almost universally architected following a common pattern with unfortunate characteristics.

Firstly, there usually exists a set of centralized servers that hosts the set of users and their permissions. This results in a number of security threats, such as permitting the operator of the authorization system to view and change the permission data. Secondly, these systems do not permit federation across administrative domains, as there is no safe choice of system operator: any operator would have visibility and control in all administrative domains, which is unacceptable. Thirdly, these systems do not offer transitive delegation: when a user grants permission to another user, the permissions of the recipient are not predicated upon the permissions of the granter.

Whilst several other systems, such as financial systems and communication systems have recently been reinvented to incorporate decentralization and privacy, there has been little attention paid to improving the authorization systems. This work aims to address that by asking the question "How can we construct an authorization system that supports first-class transitive delegation across administrative domains without trusting a central authority or compromising on privacy?"

We find that Graph Based Authorization, where principals are vertices in a graph and delegation between principals are edges in the graph, is capable of capturing transitive delegation as a first class primitive, whilst also retaining compatibility with existing techniques such as Discretionary Access Control or Role Based Access Control. A proof of permission in the Graph Based Authorization model is represented by a path through the graph. Whilst prior implementations of Graph Based Authorization do not meet the decentralization or privacy-preserving goals, we find that this is not intrinsic, and can be remedied by introducing two new techniques. The first is the construction of a global storage tier that cryptographically proves its integrity, and the second is an encryption technique that preserves the privacy of attestations in global storage.

The horizontally-scalable storage tier is based on a new data structure, the Unequivocable Log Derived Map, which is composed of three Merkle trees. Consistency proofs over these trees allow a server to prove that objects exist or do not exist within storage, as well as proving that the storage is append-only. Our scheme advances prior work in this field by permitting efficient auditing that scales with the number of additions to the storage rather than scaling with the total number of stored objects. The cryptographic proofs of integrity force storage servers to behave honestly.

The design of the storage does not ensure the privacy of the permission data stored within it. We address by introducing Reverse Discoverable Encryption. This technique uses the objects representing grants of permission as a key dissemination channel. By using Wildcard Key Derivation Identity Based Encryption in a non-standard way we allow for permission objects to be encrypted using the authorization policy as a key. Thus, RDE permits the recipient of some permissions to decrypt other compatible permissions granted to the grantee that could be concatenated together to form a valid proof. RDE therefore protects the privacy of permission objects in storage whilst still permitting decryption of those objects by authorized parties.

We construct an implementation of these techniques, WAVE, and evaluate its performance. We find that WAVE has similar performance to the widely used OAuth system and performs better than the equally widely used LDAP system, despite offering significantly better security properties.




Download Full History