Chai: Agentic Discovery of Cryptographic Misuse Vulnerabilities
Source: arXiv:2606.26933 · Published 2026-06-25 · By Corban Villa, Sohee Kim, Austin Chu, Alon Shakevsky, Raluca Ada Popa
TL;DR
Chai addresses the challenging problem of discovering cryptographic misuse vulnerabilities—security flaws arising from subtle implementation or specification ambiguities in widely used cryptographic libraries and their dependent applications. Existing AI-based vulnerability discovery methods excel in classes like memory safety due to strong instrumentation signals, but cryptographic misuse lacks such oracles, making automated detection difficult and prone to false positives. Chai innovates by combining classical differential testing across multiple cryptographic library implementations with adaptive AI-guided input mutation. This combination uses cross-library behavioral discrepancies on identical inputs as verifiable signals of potential security issues, turning ambiguities and inconsistencies into actionable leads.
Unlike prior agents that audit application codebases individually, Chai inverts the paradigm by first detecting root flaws at the library level and then propagating those findings via dependency graphs to downstream applications. This approach amplifies testing coverage and efficiency, enabling Chai to find library vulnerabilities, specification ambiguities, and their security consequences in dependent apps. Empirically evaluated on 47 libraries across X.509, JWT, and SAML protocols, Chai uncovered over 100 vulnerabilities including critical zero-days in libraries like wolfSSL and others embedded in major Linux distributions and browsers. Its AI-driven differential testing doubles unique discrepancy discovery compared to prior fuzzers, highlighting how adapting classical techniques with agentic search and dependency tracing advances cryptographic vulnerability discovery substantially.
Key findings
- Chai surfaced over 100 vulnerability findings in cryptographic libraries and downstream applications.
- It detected multiple previously unknown critical vulnerabilities in wolfSSL, confirmed and patched within hours of reporting, despite recent Mythos audits.
- Chai’s differential testing uncovered ∼2× as many unique library behavioral discrepancies compared to strongest prior fuzzing baselines.
- The system analyzed 47 cryptographic libraries across 8 programming languages covering X.509, JWT, and SAML protocols.
- Chai’s approach classifies discrepancies into vulnerabilities, security bugs, ambiguities, and non-actionable differences with human review.
- Chai’s reverse search traced ambiguities through a dependency graph covering 17 packaging ecosystems to identify affected downstream projects at scale.
- Targeted audits triggered by confirmed ambiguities allow examination of each affected application with specific, close-ended security questions rather than open-ended searches.
- Amplified testing with a single input sent to all implementations simultaneously yields coverage across the union of bugs in all harnessed libraries rather than subsets per project.
Threat model
The adversary can craft and submit cryptographic protocol messages (e.g., JWT tokens, certificates) to verifying endpoints but holds no signing keys or privileged deployment positions. They attempt to subvert security decisions by exploiting implementation quirks or ambiguities observable through differing library behaviors. Chai does not consider attackers with insider privileges, key compromise, or ability to tamper with application code beyond crafted protocol inputs.
Methodology — deep read
Chai operates under the threat model of an attacker who can craft protocol messages (e.g., certificates, JWT tokens, SAML assertions) but possesses no signing keys or privileged deployment access. Vulnerabilities arise when two or more independent cryptographic library implementations disagree on acceptance or rejection of the same input, indicating at least one flawed implementation or ambiguity. The system does not evaluate cryptographic primitives or protocol specs but focuses on concrete implementations.
The dataset comprises 47 open-source cryptographic libraries spanning X.509, JWT, and SAML protocols implemented in 8 languages, along with application dependency metadata from 50,000 critical open-source repos across 17 ecosystems (npm, PyPI, Maven, Cargo, etc.). The dependency graph maps libraries to applications transitively depending on them.
The core algorithm is a two-stage approach: first, differential testing sends inputs to multiple implementations simultaneously. Inputs are generated by an AI mutation agent which iteratively proposes protocol-level semantic mutations based on prior vulnerability disclosures and feedback from differential outputs. A deterministic builder encodes mutations into conformant protocol messages, submitted to all harnessed libraries. Behavioral discrepancies (accept/reject differences) are classified and minimized. This replaces classic differential testing’s reliance on fixed grammars with an agentic search guided by a multi-armed bandit resource allocator leasing mutation groups at cluster and operation granularity.
Second, discrepancy tracing maps library-level ambiguities to dependent applications using the dependency graph and orchestrates targeted audits. An AI agent reviews application use of the ambiguous library behavior, producing proof-of-concept exploit code where the behavior is insecurely relied on. Audits progress through enumeration of candidates, lightweight config checks, sandboxed PoC construction, iterative PoC refinement toward end-to-end exploits, minimal necessary config adjustments, and final validation on clean VMs. Human experts verify findings before reporting.
Training details of the AI agents are not explicitly detailed; the system leverages retrieval augmented generation (RAG) over indexed past CVEs and library source for mutation planning and evolutionary search. Agents propose mutations conditioned on prior results and vulnerability patterns to efficiently explore input space.
Evaluation metrics focus on vulnerability discovery rate, number of unique discrepancies, classification accuracy, and practical impact via CVEs submitted and patches applied. Baselines include grammar-based fuzzers and prior differential testing tools. Ablations examine mutation group leasing and targeted audit efficacy. Reproducibility is supported by open dependency graph mining, reproducible mutation construction, and CI style sandboxed PoC generation, but some library code and application data are from closed or sensitive sources.
A concrete example: starting with a well-formed JWT token as a seed, mutations attempt to embed attacker control fields or keys. The builder assembles signed tokens conforming to JWT specs. The same token is run against 20+ JWT libraries. Divergences in acceptance signal discrepancies, which are minimized by dropping irrelevant mutations. Confirmed ambiguities (like libraries that accept embedded keys) are traced via dependency graph to applications inheriting those libraries. A targeted audit agent checks if the application trusts embedded keys, attempting PoCs that forge tokens accepted by the app. Successful exploits become documented vulnerability reports.
Technical innovations
- Combining classical differential testing with AI-driven adaptive mutation to improve input generation and prioritization for cryptographic protocol fuzzing.
- A two-stage pipeline that first catalogs library-level cryptographic implementation flaws and then propagates those findings through dependency graphs to audit affected applications efficiently.
- Resource allocation using a multi-armed bandit approach to dynamically lease mutation groups defined by semantic attack clusters and concrete operations, balancing exploration and exploitation.
- Discrepancy tracing that treats specification ambiguities not as noise but as potential downstream application vulnerabilities, leading to targeted, close-ended audits rather than broad, open-ended code searches.
Datasets
- Cryptographic Libraries — 47 libraries — Open source ecosystem (various languages)
- Open Source Dependency Graph — 50,000+ critical repositories — package manifests across 17 ecosystems (npm, PyPI, Maven, Cargo, Composer, Go modules, etc.)
- Vulnerability Disclosure Index — Curated CVE database from harnessed libraries’ history (size not specified, internal)
Baselines vs proposed
- Strongest prior fuzzing baseline: unique discrepancies detected = X (approximate) vs. Chai: ~2× X
- Anthropic’s Mythos on wolfSSL: vulnerabilities found = 0 vs Chai: multiple critical vulnerabilities confirmed and patched
- Grammar-based fuzzers: less coverage and fewer high-impact discrepancies surfaced compared to Chai’s AI-driven adaptive mutation
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.26933.
Fig 4: Chai Differential Testing. End-to-end design of Chai. From a high-level goal, 1) Plan decomposes it into subgoals with RAG over library
Limitations
- Chai’s discovery is empirical and probabilistic, dependent on agent-driven input mutation; it does not guarantee exhaustive vulnerability coverage.
- Human review remains necessary to classify discrepancies and verify final reports, highlighting remaining challenges in fully automating cryptographic misuse detection.
- Reproducibility is affected by closed or sensitive codebases and application dependency data not publicly shared.
- The approach focuses on implementation flaws and specification ambiguities but does not address cryptographic primitive weaknesses or specification-level design flaws.
- Adversary model assumes no privileged access or signing keys; threats arising from insider attackers or key compromise are not covered.
- Targeted audit effectiveness depends on quality and completeness of dependency graphs, which may miss some downstream users.
Open questions / follow-ons
- Can the AI mutation agents be further improved or pretrained on more extensive cryptographic protocol knowledge to increase differential coverage?
- How to scale discrepancy tracing to handle closed-source or proprietary applications and large corporate codebases with partial visibility?
- Could extensions incorporate detection of cryptographic primitive-level flaws or specification-level vulnerabilities through formal verification?
- What mechanisms can reduce remaining human review overhead while maintaining ethical vulnerability disclosure standards?
Why it matters for bot defense
Bot-defense and CAPTCHA practitioners often rely on cryptographic protocols for secure authentication tokens or session management. Chai’s approach highlights the subtle risks posed by cryptographic misuse vulnerabilities in widely deployed libraries underpinning these systems. Automated differential testing combined with agentic validation of discrepancies can proactively identify vulnerabilities not only in the crypto libraries themselves but also in the dependent applications that consume cryptographic tokens. This root-to-leaf discovery is relevant for ensuring enhanced trust in authentication mechanisms.
Practitioners can draw insights from Chai’s dependency-driven reverse tracing and targeted audit methodology when considering secure integration of third-party crypto libraries or when evaluating potential supply chain risks. Its AI-guided adaptive mutation strategy may inform fuzzing and vulnerability discovery tools tailored for cryptographic components in bot defense stacks. However, the need for human verification and limitation to observable protocol inputs should caution users to complement automated findings with expert analysis.
Cite
@article{arxiv2606_26933,
title={ Chai: Agentic Discovery of Cryptographic Misuse Vulnerabilities },
author={ Corban Villa and Sohee Kim and Austin Chu and Alon Shakevsky and Raluca Ada Popa },
journal={arXiv preprint arXiv:2606.26933},
year={ 2026 },
url={https://arxiv.org/abs/2606.26933}
}