Chai: Agentic Discovery of Cryptographic Misuse Vulnerabilities

🕒 Published (v1): 2026-06-25 12:08 UTC · Source: Arxiv · link

Why this paper was selected

Berkeley/Popa group; agentic crypto-misuse detection; closed-loop vulnerability discovery

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Chai is an agentic system that discovers cryptographic misuse vulnerabilities by pairing AI-driven differential testing across all implementations of a protocol simultaneously with a "discrepancy tracing" stage that propagates library-level ambiguities downstream to vulnerable applications. It inverts the standard paradigm of auditing one codebase for many bugs, instead cataloging bugs once at the library level and amplifying findings across a cryptographic dependency graph. Applied to X.509, JWT, and SAML, it found critical vulnerabilities in wolfSSL (used on billions of devices) and over 100 total findings.

Problem

AI vulnerability discovery concentrates on verifiable bug classes (memory safety, crashes) that have programmatic oracles; cryptographic misuse lacks such oracles, making signal extraction hard and false-positive filtering manual. Existing differential testing of crypto libraries is noisy, requires hand-built protocol grammars per target, and stops at the library level — not tracing ambiguities to the downstream applications they actually compromise. Naive agentic auditing re-derives the same analysis for every project built on the same library, scaling poorly across the many independent implementations of a single standard.

Method

Chai operates in two stages joined by a shared artifact, the discrepancy:

Stage 1 — Amplified differential testing. A mutation agent proposes ordered mutation programs (operations drawn from a fixed catalog keyed to protocol trust boundaries) over a seed message. A deterministic builder assembles each candidate into concrete bytes (handling serialization, encoding, signing). Every harnessed implementation of the target protocol (e.g., 20+ JWT libraries across 8 languages) evaluates the identical bytes. Disagreements are collected as discrepancies. An adaptive retrieval agent queries an index of prior CVEs via RAG to steer future mutations. A UCB1 multi-armed bandit allocates search effort across mutation groups (cluster × operation pairs), suppressing duplicate effort and preventing early-yield regions from capturing the budget. Each discrepancy is triaged by an agent into: vulnerability, security bug, ambiguity, or non-actionable difference.

Stage 2 — Discrepancy tracing. Confirmed ambiguities — library behaviors that are defensible under the spec but create missing guarantees — are traced through a dependency graph built from package manifests. This reverse search (Figure 3b) yields a short list of downstream applications that transitively depend on the disagreeing library. Each candidate app receives a targeted audit (Figure 3c): a close-ended agent prompt that checks for one specific property violation and, where applicable, produces a proof-of-concept exploit. The audit is scoped to a single behavior rather than an open-ended bug search, reducing cost and false positives.

Key Contributions

• Agentic differential testing without hand-built grammars: agents replace per-protocol grammars, generalizing across X.509, JWT, and SAML with only library harnesses and seed messages as protocol-specific engineering.
• Mutation group resource allocation: UCB1 bandit over (trust-boundary cluster × mutation operation) pairs ensures breadth-first coverage before exploitation of high-yield areas.
• Discrepancy tracing: novel technique that repurposes library-level ambiguities as leads for downstream application vulnerabilities, inverting the standard one-project-many-bugs paradigm.
• Compounding efficiency: a single test input exercises \(|\text{Libraries}|\) implementations at once; a single ambiguity propagates via dependency graph to \(|\text{Downstream apps}|\) targeted audits.
• Empirical evaluation across 47 libraries in 8 languages with confirmed CVEs and maintainer patches within hours.

Results

• Discovered two severe (critical) vulnerabilities in wolfSSL — a TLS library powering billions of devices — both confirmed and patched by maintainers within hours of submission; wolfSSL had been recently audited by Anthropic's Mythos without surfacing either issue.
• Found security bugs in a library shipped in major Linux distributions and another behind a major web browser.
• Surfaced 100+ vulnerability findings across downstream applications (over-100 under investigation at time of writing).
• Chai's differential search produced ~2× as many unique discrepancies as the strongest differential testing / fuzzing baseline.
• Found a broader range of disagreements, including rare cases where only a few libraries accept an input the rest reject — the strongest signal of a library-level flaw — which baselines did not surface.

Limitations

• Coverage is empirical, not exhaustive: agents generate inputs probabilistically; the discrepancies found are a subset of those present, concentrated toward behaviors the agents are directed at.
• Does not detect flaws in underlying mathematical constructions or in specifications themselves; requires at least two implementations to disagree on the same input.
• Stage 2 downstream findings (100+) were still under investigation at submission time — confirmed exploit rate not yet reported.
• The system requires library harnesses per protocol; supporting a new protocol still demands this upfront instrumentation work.
• Mutation catalog and trust-boundary clusters must be designed per protocol domain, representing residual protocol-specific engineering.
• UCB1 bandit can be captured by early high-yield regions until the initial full sweep completes — the full-sweep guarantee mitigates but does not eliminate this.

Relevance to Agentic AI / LLM Agents

Chai is a direct contribution to the methodology of agentic vulnerability discovery: it demonstrates that agents are most effective not as open-ended code auditors but as adaptive search drivers grounded in verifiable, programmatic signals (differential discrepancies). The "inversion" from project-centric to discrepancy-centric auditing is a transferable architectural pattern for any domain where a shared interface and multiple independent implementations exist. The RAG-over-CVEs retrieval loop and UCB1 lease allocation address two core failure modes of naive multi-agent parallelism — redundancy and budget capture — offering practical blueprints for agentic search campaigns. The comparison with Mythos (Anthropic's state-of-the-art agentic security auditor) finding zero of the two wolfSSL vulnerabilities that Chai caught quantifies where current end-to-end agents fall short and what complementary structure (differential grounding + dependency propagation) recovers.