Capabilities

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# Access Matrix and its representations
 
# Conceptual access matrix
access_matrix = {
    #               file1    file2    socket   device
    'alice':      {'R,W',   'R',     'R,W',   'R'},
    'bob':        {'R',     'R,W',   '',      ''},
    'server':     {'',      'R',     'R,W,S', 'R,W'},
}
 
# ACL representation: store by object (column)
acls = {
    'file1':  [('alice', 'R,W'), ('bob', 'R')],
    'file2':  [('alice', 'R'), ('bob', 'R,W'), ('server', 'R')],
    'socket': [('alice', 'R,W'), ('server', 'R,W,S')],
    'device': [('alice', 'R'), ('server', 'R,W')],
}
 
# Capability list representation: store by subject (row)
c_lists = {
    'alice':  [('file1', 'R,W'), ('file2', 'R'), ('socket', 'R,W'), ('device', 'R')],
    'bob':    [('file1', 'R'), ('file2', 'R,W')],
    'server': [('file2', 'R'), ('socket', 'R,W,S'), ('device', 'R,W')],
}
 
# Same information, different organization
# ACL: "Who is allowed to access 'socket'?"
#      -> Quick lookup: acls['socket']
#      -> Answer: alice (R,W), server (R,W,S)
 
# Capability: "What can 'bob' access?"
#             -> Quick lookup: c_lists['bob']
#             -> Answer: file1 (R), file2 (R,W)
 
# Cross-query is expensive:
# In ACLs: "What can bob access?" -> Must scan ALL object ACLs
# In Capabilities: "Who can access device?" -> Must scan ALL capability lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// The Confused Deputy Problem: ACL vs Capability
 
// SCENARIO: A compiler that maintains a billing log
// User asks compiler to read 'input.c' and write 'output.o'
// Compiler also writes to '/billing/log' for accounting
 
// === ACL APPROACH ===
// Compiler runs with BOTH user's permissions AND billing permissions
// Because identity is the basis for access control
 
void acl_compile(const char* input, const char* output) {
    // What identity do we check?
    // The compiler is running as 'compiler_user' which has:
    // - Access to billing log (its own need)
    // - Access to user's files (inherited through setuid or similar)
    
    FILE* in = fopen(input, "r");     // Uses... which identity?
    FILE* out = fopen(output, "w");   // Uses... which identity?
    FILE* log = fopen("/billing/log", "a"); // Uses compiler's own access
    
    // PROBLEM: Malicious user passes input="/billing/log"
    // Compiler has write access to billing log!
    // ACL check succeeds because compiler runs with billing authority
    // Result: User corrupts billing log via confused deputy
}
 
// === CAPABILITY APPROACH ===
// Compiler receives ONLY the capabilities user provides for input/output
// Plus its own separate capability for billing
 
void cap_compile(Capability input_cap, Capability output_cap, 
                 Capability billing_cap) {
    // Each operation uses a SPECIFIC capability
    // No confusion possible
    
    FILE* in = cap_open(input_cap, CAP_READ);   // User's capability
    FILE* out = cap_open(output_cap, CAP_WRITE); // User's capability
    FILE* log = cap_open(billing_cap, CAP_APPEND); // Compiler's own
    
    // User cannot pass a capability to billing log UNLESS they have one
    // And if they do, that's their legitimate access, not confusion
    
    // The compiler never uses its billing capability for user operations
    // The user never has the billing capability to misuse
    // Problem SOLVED by design
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

// Object Discovery: ACL vs Capability approaches
 
// === ACL Systems: Naming Separate from Authorization ===
// Objects are named through a global namespace (filesystem, registry, etc.)
// Authorization is checked when the name is resolved
 
int acl_open_file(const char* path, int mode) {
    // 1. Resolve path through global namespace
    struct inode* inode = resolve_path(path);
    
    // 2. Check ACL against current user identity
    if (!acl_check(inode->acl, current_user(), mode))
        return -EACCES;
    
    // 3. Grant access
    return create_file_descriptor(inode, mode);
}
 
// Key issue: Can NAME an object you cannot ACCESS
// This leaks existence information and enables TOCTOU attacks
 
// === Capability Systems: Naming IS Authorization ===
// You only have a reference (capability) to objects you can access
// No global namespace to enumerate
 
void* cap_access(Capability cap) {
    // The capability IS the name IS the authorization
    // You cannot name something you don't have a capability for
    
    // No global namespace to probe
    // No existence leakage
    // No TOCTOU (time-of-check-time-of-use) gap
    
    return cap_dereference(cap);
}
 
// How do you find capabilities? Through designated channels:
// 1. Granted by creator/parent
// 2. Received via IPC from service
// 3. Returned by capability allocation operation
// 4. Found through capability directory services
 
// Example: Capability directory (nameserver)
Capability find_service(Capability directory_cap, const char* name) {
    // Request capability from directory
    // Directory checks if we're authorized (using our directory_cap)
    // Directory returns capability to named service
    
    // Note: We need directory_cap to even ask
    // Directory is itself capability-protected
    return directory_lookup(directory_cap, name);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// Storage overhead comparison
 
// Assumptions:
// - S subjects, O objects
// - Average subject accesses A objects
// - Average object is accessed by B subjects
// - Total access relationships: S*A = O*B (by definition)
 
// === ACL STORAGE ===
// Each object stores list of subject entries
// Storage: O * B * (sizeof(subject_id) + sizeof(rights))
// Typically: (subject_id: 4-8 bytes, rights: 4 bytes) = 8-12 bytes per entry
 
// Example: 1M objects, average 10 subjects per object
// Storage: 1M * 10 * 12 = 120 MB for all ACLs
 
// Plus: need to store object→ACL mapping (object-local, so free)
 
// === CAPABILITY STORAGE ===
// Each subject stores list of capability entries
// Storage: S * A * (sizeof(object_ref) + sizeof(rights) + metadata)
// Typically: (object_ref: 8 bytes, rights: 4 bytes, misc: 4 bytes) = 16 bytes
 
// Example: 10K subjects, average 1000 objects per subject
// Storage: 10K * 1000 * 16 = 160 MB for all C-lists
 
// Plus: need to store subject→C-list mapping (process-local)
 
// Key insight: ACLs scale with object count × access density
//              Capabilities scale with subject count × access density
// Choose based on which is smaller in your domain
 
// Special case: Hardware capabilities (CHERI)
// Doubling pointer size: 64→128 bits = 100% pointer overhead
// But: Replaces separate capability tables entirely
// Net effect: ~10-50% memory increase for typical programs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Unix: ACL + Capability hybrid
 
// Phase 1: ACL-based authorization (open)
int fd = open("/path/to/file", O_RDWR);
// - Resolves path through global namespace (allows naming without access)
// - Checks file's permissions (ACL) against process UID/GID
// - If authorized, creates file descriptor (capability)
 
// Phase 2: Capability-based operation (read/write)
read(fd, buffer, size);
write(fd, buffer, size);
// - No further ACL checks
// - File descriptor IS the capability
// - Can be passed to child processes (inheritance)
// - Can be passed via SCM_RIGHTS (explicit delegation)
 
// Result: ACL controls initial access; capability controls ongoing use
// Best of both:
// - ACL provides easy revocation (chmod/chown)
// - FD provides confused-deputy prevention in programs
// - FD transfer enables delegation
 
// Limitation: Still has ambient authority through namespace
// Process can attempt open() on any path; sees EACCES only after name resolution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Capsicum: ACL + Capability mode
 
#include <sys/capsicum.h>
 
int main() {
    // Phase 1: Use ACLs to open files (ambient authority)
    int input_fd = open("/data/input.txt", O_RDONLY);
    int output_fd = open("/data/output.txt", O_WRONLY | O_CREAT, 0644);
    
    // At this point, process has ambient authority via filesystem ACLs
    // Could open("/etc/passwd", O_RDONLY) if permissions allow
    
    // Phase 2: Enter capability mode
    cap_enter();
    
    // NOW: Ambient authority is REVOKED
    // open("/etc/passwd", O_RDONLY) -> ENOTCAPABLE
    // open("/any/path", ...) -> ENOTCAPABLE
    // socket(AF_INET, ...) -> ENOTCAPABLE
    
    // Can ONLY use file descriptors already held
    // Those FDs ARE capabilities now
    
    // Phase 3: Work in capability mode
    process_data(input_fd, output_fd);
    // Even if compromised, attacker confined to these two files
    
    return 0;
}
 
// Key insight: ACLs for bootstrap, Capabilities for sandboxing
// Get the easy grant/revoke of ACLs for setup
// Get the sandboxing benefits of capabilities for execution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# Modern patterns combining ACL and capability concepts
 
# Pattern 1: Zero Trust API Access
# Traditional (ACL-ish):
#   - Authenticate identity
#   - Check role membership
#   - Allow if policy matches
 
# Capability-influenced:
#   - Request includes token (capability)
#   - Token carries scope, audience, expiration (attenuated rights)
#   - No ambient authority - must present token for each request
 
jwt_token = {
    "sub": "user@example.com",        # Subject (for audit)
    "scope": "read:files write:docs",  # Rights (attenuated capability)
    "aud": "api.example.com",          # Object restriction
    "exp": 1700000000,                 # Time limitation
    "iat": 1699990000                  # Issuance tracking
}
# This IS a capability: unforgeable (signed), designates resource, encodes rights
# But issued based on ACL/RBAC policy
 
# Pattern 2: Container Sandboxing
docker_security = {
    "capabilities": ["NET_BIND_SERVICE"],  # Linux capabilities (coarse-grained)
    "seccomp_profile": "default",          # Syscall filtering
    "read_only_rootfs": True,              # Restrict writes
    "no_new_privileges": True,             # No privilege escalation
}
# Principle of least privilege via capability dropping
# But policies defined via ACL-like configuration
 
# Pattern 3: WebAssembly Import Capabilities
wasm_imports = {
    "fd_read": "cap_read",     # File read capability
    "fd_write": "cap_write",   # File write capability
    "clock_get_time": "allow", # Clock access
    # No network, no filesystem access (not imported)
}
# WASM module can ONLY use imported capabilities
# Pure capability model for sandboxing
# ACL-like policy determines what gets imported