Key-Based Decentralized Label Model (KDLM)

Local Access Control

Consider the current state of the art: local access control restricts access to data, say via a reference monitor that controls access to data in a database. People wishing access provide their digital credentials. The reference monitor checks the credentials and then provides access to the data. Once the data is released, the reference monitor no longer has any control over the data.


Local access control

Decentralized Label Model

Information flow control is intended to prevent unauthorized leaks of sensitive shared information. The decentralized label model (DLM) developed by Myers and Liskov provides a form of information flow control, based on access control policies. A policy specifies who can access the data. But information may be protected by several policies. Each principal, as it distributes data, may add its own policy to the existing policies for that data. All of these policies continue to be enforced "downstream." In addition a principal may modify the policy it has put on a piece of data, for example relaxing the restrictions of its original policy. However a principal cannot modify policies placed on the data by other principals. Hence selective declassification.

This mechanism is realized by a type system where data has both a normal type and a label (set of policies). For example, a variable x may have both a type int and a label with these policies:

Therefore the only principals that can access the variable x are Bob and Jane, since they are allowed by both policies.

Key-Based Decentralized Label Model

Information flow control can be specified as a type system, and therefore checked very efficiently. However this assumes that the entire program is in a single address space. What happens if the program is distributed over an untrusted network? Typically such systems rely on the run-time to secure the network, basically making the network transparent. While eliding the original problem, this violates the well-known end-to-end argument in system design. The Jeddak philosophy is that network security is too important to be left to the run-time. Applications must be able to develop their own network security, without violating the policies expressed in the type system. Network security should be moved outside the trusted computing base.


Jeddak introduces the key-based decentralized label model (KDLM). KDLM makes an explicit connection between keys (used for cryptographic operations such as encryption and signing) and policies for access control and information flow control. This is done via key names, that are type-level names for cryptographic types. In KDLM such key names are essentially names for policies, and a label is a set of key names rather than a set of policies. For example, a variable x may have both a type int and a label with these key names:

Therefore the only principals that can access the variable x are Bob and Jane, since they are allowed by the policies named by K1 and K2.

Policies are associated with keys, via key names. In asymmetric key schemes, each key name has an associated public-private key pair. For data protected by a policy K, say that allows Alice and Bob to access sensitive data, the data can be protected while in transit over an untrusted network by encrypting it with the public key for K. At the receiving site, the receiver must dynamically check what the policy is for the encrypted data. If the data can be decrypted with the private key for K, then the policy for that data is given by the key name K.


Distributed Declassification

The most important innovation in KDLM is the abstraction of declassification certificates, which are motivated by the interaction between declassification and decryption. Suppose Alice has placed data in a database, encrypted for secrecy, under a policy that does not allow Bob access to the database. Bob later convinces Alice to give him access to the data. The way this is done in a classical information flow system with declassification is to have Alice retrieve the data and declassify it for Bob. With application-applied cryptographic operations, the data would have to be decrypted, declassified, then re-encrypted under a new key with a policy that allows Bob access.

Delegate cert

But this centralized approach is too restrictive in a distributed system. Instead of making Alice be a central conduit for declassifying information for Bob, it should be possible to send Bob "permission" to declassify information for himself protected by a policy controlled by Alice. This is the motivation for declassification certificates. If the data was originally encoded under the public key for key name K1, then Alice performs the following steps:

  1. Generate a new key name (policy) K2, for a policy that allows Bob access to the data.
  2. Using the private key for this key name K2 to generate a declassification certificate that declassifies data under policy K1 to policy K2.
  3. Send the declassification certificate to Bob.
  4. Bob can now decrypt, with the declassification certificate, data that was encrypted under the public key for K1. Decryption also implicitly declassifies the data to the policy K2 that allows Bob access to the clear text.

Delegate cert 2

Why Key-Based DLM?

Suppose we added declassification certificates to DLM. Consider the following scenario: e1 has a label {Joe:{Mary,Sue}}, and e2 has the same label. Joe can then declassify e1 to allow Sam access to it, using a declassify construct:

declassify ({Joe:{Mary,Sue,Sam}}, e1)

Now if we add declassification certificates to DLM, then Joe can issue the certificate:

Joe:{Mary,Sue,Sam} declassifies Joe:{Mary,Sue}

Then e2 can also be declassified! This is clearly not the intent. Declassification certificates in DLM are too liberal. We need a way to control their applicability. In KDLM this is done by naming policies, and only allowing a declassification certificate to be applied to a policy with the correct name. Hence the importance of key names in KDLM for naming policies.