Fine-grained control of security capabilities

Dan Boneh, Xuhua Ding, Gene TsudikACM Trans. Internet Techn 2004 · DOI

TL;DR

This paper introduces the SEM (SEcurity Mediator) architecture, a novel approach to fine-grained control and immediate revocation of security capabilities like digital signing and decryption. By splitting RSA private keys between users and a semi-trusted mediator, it allows for revocation without affecting existing infrastructure or requiring complex changes to legacy systems.

What Problem Does This Paper Address?

In many organizations (government, military, corporate), users have digital signature and decryption capabilities for secure communication and data access. When a user's privileges need to be revoked (e.g., due to termination or suspected compromise), current methods like Certificate Revocation Lists (CRLs) or Online Certificate Status Protocol (OCSP) are often too slow or don't offer the necessary fine-grained control. This means a user might still be able to decrypt old messages or perform other actions even after their access should be terminated. The paper aims to solve this by enabling immediate revocation of specific capabilities, not just the entire certificate.

Methods

The core of the proposed solution is the SEM (SEcurity Mediator) architecture, built upon a variant of RSA called Mediated RSA (mRSA).

  • Mediated RSA (mRSA): Instead of a user holding their entire RSA private key, it's split into two "half-keys." One half is kept by the user, and the other by a SEM. For operations like signing or decryption, both the user and the SEM must cooperate. This split is transparent to external parties who only see the standard public key.
  • SEM Architecture: A SEM is an online, semi-trusted server that serves multiple users. When a user needs to sign or decrypt, they send a request (along with their message or encrypted data) to their SEM. The SEM checks if the user is revoked. If not, it provides a "token" (a partial signature or decryption component) that, when combined with the user's own half-key computation, completes the operation.
  • Revocation Mechanism: Revocation is achieved by simply instructing the SEM to stop providing tokens to a specific user. This instantly revokes their signing and/or decryption capabilities.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Fine-grained Revocation: The key insight is that revoking capabilities (signing, decrypting) is more practical and immediate than revoking entire certificates, especially for specific organizational needs.
  • Semi-Trusted Mediator: The SEM doesn't need to be fully trusted. It can't forge signatures or decrypt messages on its own. Its compromise primarily allows an attacker to "unrevoke" already revoked users, which is a manageable risk compared to full key compromise.
  • Backwards Compatibility: A major design goal is that mRSA operations are indistinguishable from standard RSA to external verifiers and encryptors. This means existing infrastructure doesn't need significant changes.
  • Binding Signature Semantics: The system naturally supports "binding signature semantics," meaning a signature is valid if the signer's certificate was valid at the time of signing, regardless of subsequent revocation. This is crucial for contracts and long-term agreements.

Key Results

The paper presents experimental results demonstrating the feasibility and performance of the SEM architecture.

  • Performance: Signature and decryption times for clients are not significantly higher than standard RSA, especially when the SEM is fast. The overhead is mainly communication latency and the SEM's processing time.
  • Scalability: A single SEM can serve many users, and the architecture can be extended to support multiple SEMs per client for fault tolerance.
  • Practicality: The implementation includes plug-ins for email clients (Eudora, Outlook) and an email proxy, showing real-world applicability.

Limitations and Future Work

  • SEM Trust: While semi-trusted, a compromised SEM can still allow revoked users to regain capabilities. The paper suggests that for certain applications, a fully trusted SEM might be necessary, or alternative protocols like SSL could secure SEM-client communication.
  • CA-based Key Generation: The default mRSA key generation relies on a Certificate Authority (CA) to split keys. While efficient, this could be seen as a liability. Future work could explore distributed key generation protocols.
  • Identity-Based mRSA: An extension is proposed for identity-based mRSA, but it requires a fully trusted SEM, which deviates from the original semi-trusted model.
  • Appropriateness: The authors note that the SEM architecture is best suited for small- to medium-sized organizations and is likely inappropriate for the global internet or large educational campuses due to management overhead.

Summary updated

BibTeX
@article{boneh2004fine,
  author = {Dan Boneh and Xuhua Ding and Gene Tsudik},
  title = {{Fine-grained control of security capabilities}},
  journal = {ACM Trans. Internet Techn.},
  year = {2004},
  doi = {10.1145/967030.967033},
}
Figure