🔐 KerberosX — Threshold Authentication Under Partial Compromise

📖 Description

A distributed Kerberos-like authentication system using 2-of-3 Schnorr multi-signatures that remains secure even when one authority is fully compromised — no single point of failure.

🗂️ Table of Contents

• Overview
• Architecture
• Cryptographic Primitives
• Protocol Phases
• Ticket Structure
• Quick Start
• File Structure
• Attack Scenarios
• Security Analysis
• Key Rotation
• Performance Notes

🧠 Overview

Classical Kerberos relies on a single trusted AS and TGS. If either is compromised, an attacker can forge tickets and impersonate any user.

KerberosX fixes this by distributing trust across three independent authorities using a 2-of-3 Schnorr multi-signature scheme:

• ✅ Any 2 of 3 authorities must sign a ticket for it to be valid
• ✅ A single compromised authority cannot forge tickets alone
• ✅ The system remains fully operational even if one authority goes offline
• ✅ All cryptographic primitives are hand-implemented — no asymmetric crypto libraries

🏗️ Architecture

Clients           AS Cluster              TGS Cluster           Service Servers
  │                 AS1 :9001               TGS1 :9011              fileserver :9021
  │                 AS2 :9002               TGS2 :9012              mailserver :9022
  │                 AS3 :9003               TGS3 :9013                 ...
  │
  ├─── Phase 1 ──► [AS Cluster] ──► TGT with ≥2 Schnorr signatures
  ├─── Phase 2 ──► [TGS Cluster] ──► Service Ticket with ≥2 Schnorr signatures
  └─── Phase 3 ──► [Service Server] ──► Verified access + encrypted session

Each AS and TGS node runs as an independent process on a separate port. No two nodes share a private key.

🔐 Cryptographic Primitives

⚠️ No asymmetric crypto libraries used. All of the above are implemented from scratch in crypto_utils.py.

Schnorr Signature Scheme

Each authority i has an independent keypair:

Private key:  xᵢ ∈ ℤq
Public key:   yᵢ = g^xᵢ mod p

Signing (per authority i over message m):

kᵢ  ← random nonce ∈ ℤq       (MUST be fresh each time)
Rᵢ  = g^kᵢ mod p
eᵢ  = H(m ∥ Rᵢ ∥ IDᵢ)
sᵢ  = kᵢ + eᵢ · xᵢ  mod q
Signature: (Rᵢ, sᵢ)

Verification:

eᵢ  = H(m ∥ Rᵢ ∥ IDᵢ)
Check: g^sᵢ ≡ Rᵢ · yᵢ^eᵢ  (mod p)

A ticket is valid only if ≥ 2 independent signatures verify successfully.

🔄 Protocol Phases

Phase 1 — Distributed AS Exchange (Get TGT)

Client ──SIGN_REQUEST──► AS1, AS2, AS3
                           │  (verify credentials, sign ticket_bytes)
Client ◄──(Rᵢ, sᵢ)────── ASᵢ  (×3 in parallel)

Client collects ≥2 valid signatures → assembles TGT
Client decrypts session key K_{c,tgs} using password hash

1. Client builds ticket_bytes with client_id, timestamp, nonce, lifetime
2. Broadcasts SIGN_REQUEST to all 3 AS nodes in parallel (thread pool)
3. Each AS verifies credentials, checks nonce freshness + timestamp, signs ticket_bytes
4. Client verifies each (Rᵢ, sᵢ) pair independently using yᵢ
5. Client keeps the first 2 valid signatures → TGT formed

Phase 2 — Distributed TGS Exchange (Get Service Ticket)

Client ──TGS_SIGN_REQUEST──► TGS1, TGS2, TGS3  (with TGT + authenticator)
                              │  (verify TGT signatures, sign service ticket)
Client ◄──(Rᵢ, sᵢ)────────── TGSᵢ

Client collects ≥2 valid signatures → assembles Service Ticket

Same multi-signature flow as Phase 1, but:

• Client presents TGT + authenticator (encrypted with K_{c,tgs})
• TGS verifies the TGT's AS signatures before signing the service ticket
• Returns K_{c,s} (client-service session key)

Phase 3 — Service Authentication

Client ──(ServiceTicket + Authenticator)──► Service Server
Service verifies ≥2 TGS signatures, decrypts ticket
                              │
Client ◄──encrypted session──► Service Server

🎫 Ticket Structure

{
  "client_id":    "alice",
  "service_id":   "fileserver",
  "issue_timestamp": 1710000000,
  "lifetime":     300,
  "session_key":  "<hex>",
  "key_version":  1710000000,
  "signatures": [
    { "node_id": 1, "R": "0x...", "s": "0x..." },
    { "node_id": 2, "R": "0x...", "s": "0x..." }
  ]
}

Tickets are:

• 🔒 AES-256-CBC encrypted (with TGS symmetric key for service tickets)
• ✍️ Signed by ≥2 independent authorities
• 🕐 Timestamped and lifetime-bound
• 🔑 Key-version tagged (for rotation support)

🚀 Quick Start

Prerequisites

pip install cryptography

Step 1 — Generate Keys

python3 master_keygen.py

Creates keys/ directory with all keypairs and public parameters.

Default test clients:

Step 2 — Start AS Nodes (3 terminals)

python3 as_node.py 1   # port 9001
python3 as_node.py 2   # port 9002
python3 as_node.py 3   # port 9003

Step 3 — Start TGS Nodes (3 terminals)

python3 tgs_node.py 1   # port 9011
python3 tgs_node.py 2   # port 9012
python3 tgs_node.py 3   # port 9013

Step 4 — Start Service Servers

python3 service_server.py fileserver 9021
python3 service_server.py mailserver 9022

Step 5 — Start Client

python3 client.py alice
python3 client.py bob
python3 client.py newuser   # will prompt for registration

Client Menu:

1. Send Service Request     → Full Phase 1 + 2 + 3 + encrypted chat
2. View Registered Servers  → Lists all active service servers
3. Exit                     → Deregisters client and exits

📁 File Structure

kerberos/
├── master_keygen.py        Offline key generation for all nodes
├── as_node.py              Authentication Server (3 independent instances)
├── tgs_node.py             Ticket Granting Server (3 independent instances)
├── service_server.py       Service Server with Schnorr verification
├── client.py               Interactive Kerberos client
├── crypto_utils.py         All cryptographic primitives (hand-implemented)
├── attacks.py              Attack simulations (4 scenarios)
├── attacker_client.py      Client used in attack demos
├── compromised_authority.py  Simulates a malicious AS/TGS node
├── replay_interceptor.py   Intercepts and replays old tickets
├── leaked_key_attacker.py  Uses a leaked private key to forge signatures
├── data.json               Client and server registry
├── keys/
│   ├── public_params.json       Schnorr params + all public keys
│   ├── as1_key.json             AS1 private keypair
│   ├── as2_key.json             AS2 private keypair
│   ├── as3_key.json             AS3 private keypair
│   ├── tgs1_key.json            TGS1 private keypair
│   ├── tgs2_key.json            TGS2 private keypair
│   ├── tgs3_key.json            TGS3 private keypair
│   └── tgs_symmetric.json       TGS symmetric AES key
├── README.md
└── SECURITY.md

☠️ Attack Scenarios

All attacks are implemented in attacks.py and related files. Each demonstrates a different threat and shows how the system handles it.

Attack 1 — Single Compromised Authority

File: compromised_authority.py

Scenario: One AS or TGS node is hijacked. The attacker controls it completely and forges ticket payloads signed with the node's real private key.

# Replace AS2 with a compromised node
python3 compromised_authority.py AS 2

# Then run the client — it will only get 1 valid signature
python3 client.py alice

What happens:

• ☠️ Compromised node signs a different (forged) payload — ATTACKER_ALICE
• ✅ The 2 honest nodes sign the real payload
• ✅ Client verifies all 3 signatures against the original ticket bytes
• ✅ Forged signature fails verification (signed different bytes)
• ✅ Client collects 2 valid signatures from honest nodes → authentication succeeds

Result: Attack contained ✔

Attack 2 — Replay Attack

File: replay_interceptor.py

Scenario: Attacker captures a valid signed request and re-sends it later.

What happens:

• ☠️ Old nonce is already in seen_nonces set on each AS node
• ☠️ Old timestamp exceeds the 30-second freshness window
• ✅ AS nodes detect both conditions and reject the replayed request

[NONCE CHECK]     FAIL — nonce 'abc123' already seen!
[TIMESTAMP CHECK] FAIL — packet is 87s old (max 30s)
☠  REPLAY ATTACK DETECTED

Result: Attack blocked ✔

Attack 3 — Leaked Private Key

File: leaked_key_attacker.py

Scenario: One authority's private key xᵢ is leaked to the attacker.

What happens:

• ☠️ Attacker uses the leaked key to produce one valid signature on a forged ticket
• ✅ The other two honest nodes sign the legitimate ticket bytes
• ✅ Client needs ≥2 valid signatures on the same bytes
• ✅ The forged signature (on different bytes) fails — threshold not met

Result: Attack contained (single key leak is insufficient) ✔

Attack 4 — Modified Ticket Payload

Scenario: Attacker intercepts a valid ticket and modifies the payload (e.g., changes client_id).

What happens:

• ☠️ Modifying any byte of the ticket bytes changes H(m ∥ R ∥ ID)
• ✅ All existing signatures fail verification against the tampered bytes
• ✅ Service server rejects the ticket — 0 valid signatures

Result: Attack blocked ✔

Attack 5 — Authority Offline

Scenario: One AS or TGS node crashes or is unreachable.

What happens:

• ✅ Client sends requests to all 3 nodes in parallel threads
• ✅ Timeout/exception on the offline node is caught gracefully
• ✅ Client collects signatures from the 2 remaining online nodes
• ✅ Authentication proceeds normally

Result: System remains operational ✔

Attack 6 — Single Signature Ticket

Scenario: Attacker attempts to present a ticket with only 1 valid signature.

What happens:

• ✅ Service server counts valid signatures
• ✅ Threshold check: valid_count < 2 → ticket rejected

Result: Rejected at service layer ✔

🛡️ Security Analysis

Why One Compromised Authority Cannot Forge Tickets

Each authority has an independent Schnorr keypair — no shared private key exists anywhere. A compromised authority can produce only one valid signature, on whatever payload it chooses. But the client verifies each signature against the original ticket bytes it constructed. A signature on different bytes fails. With only 1 valid signature (below the threshold of 2), the forged ticket is useless.

Why Two Compromised Authorities Break Security

If two authorities collude, they can both sign the same forged payload. Their two signatures verify successfully, satisfying the ≥2 threshold. The system's security assumption is at most f=1 malicious node. With f=2, the Byzantine fault tolerance model breaks.

Nonce Reuse is Fatal for Schnorr

If a nonce k is reused across two signatures:

s₁ = k + e₁·x   →   x = (s₁ - s₂) / (e₁ - e₂)  mod q
s₂ = k + e₂·x

The private key x is fully recoverable from two signatures with the same nonce. This is mitigated by generating a fresh random k via schnorr_commit() for every signature, and tracking nonces in seen_nonces.

Key Leakage Impact

🔁 Key Rotation

• AS1 and TGS1 trigger rotation every 600 seconds
• New keypairs are generated, written to keys/, and public_params.json is updated
• Other nodes auto-reload key files on change
• Tickets carry a key_version field; servers accept current and one prior version
• Rotation is non-disruptive — in-flight tickets remain valid for their lifetime

⚡ Performance Notes

Parallelism via thread pools keeps latency close to a single-node system. The security gain (full Byzantine fault tolerance at f=1) far outweighs the overhead.

👥 Default Users

📜 License

For academic use — CS5.470 System and Network Security, IIIT Hyderabad, Spring 2026.

🧾 References

• Schnorr Signature Scheme
• Kerberos Protocol
• Threshold Cryptography
• Byzantine Fault Tolerance