Invisible but Detected: Physical Adversarial Shadow Attack and Defense on LiDAR Object Detection

Towards Internet-Based State Learning of TLS State Machines

Speakers: Marcel Maehren (Ruhr University Bochum); Nurullah Erinola (Ruhr University Bochum); Robert Merget (Technology Innovation Institute); Jörg Schwenk (Ruhr University Bochum); Juraj Somorovsky (Paderborn University)

Conference: USENIX Security

YouTube: N/A - This is a peer-reviewed conference paper, not a recorded talk.

Overview

This paper presents a groundbreaking approach to understanding the real-world behavior of Transport Layer Security (TLS) implementations by applying state machine learning (SML) techniques at an unprecedented scale over the Internet. Traditionally, SML has been confined to controlled, local environments where network conditions are stable, and implementation details are often known or modifiable. The authors, a team of researchers from Ruhr University Bochum, Technology Innovation Institute, and Paderborn University, challenge this paradigm by addressing the inherent complexities of the Internet, such as non-determinism, network jitter, and unknown server configurations.

The core contribution lies in demonstrating the feasibility of learning TLS state machines from live, Internet-facing servers. This endeavor involved developing novel methodologies for handling large input alphabets, dealing with the non-deterministic nature of internet traffic, and automating the analysis of the resulting complex state machine models. By extending the scope of SML to include features like ID-based session resumption, renegotiation, and specific attack vectors for CBC padding oracles and Bleichenbacher vulnerabilities, the research offers a more comprehensive view of TLS behavior in the wild.

The significance of this work is underscored by its ability to uncover real-world security vulnerabilities that might otherwise remain hidden. Through a large-scale study spanning 7337 domains, the researchers successfully extracted 1304 state machine models, revealing critical deviations from TLS specifications. Notably, they identified a transcript integrity vulnerability in Citrix NetScaler and the first CBC padding oracle vulnerabilities detected through state machine learning, providing invaluable insights for both protocol designers and security practitioners.

Background

Transport Layer Security (TLS) is the cornerstone of secure communication over the Internet, underpinning protocols like HTTP, FTP, and IMAP by providing authenticity, integrity, and confidentiality. The establishment of a secure connection hinges on the TLS handshake, a meticulously defined sequence of messages between a client and a server. A robust TLS implementation must strictly adhere to this protocol flow, rejecting out-of-order or malformed messages to prevent serious vulnerabilities such as authentication bypasses or the acceptance of unencrypted application data.

State machine learning (SML), also known as state machine fuzzing, is a powerful technique for analyzing protocol implementations and identifying such vulnerabilities. SML involves a "learner" algorithm (e.g., L* or TTT) that interacts with a "system under learning" (SUL) to construct a hypothesis of its underlying state machine. A "mapper" translates abstract symbols from the learner into concrete protocol messages for the SUL and vice-versa. Through repeated queries and observation of responses, the learner refines its hypothesis, which is then validated using equivalence tests by a "fuzzer" that generates random words and compares predicted behavior with actual SUL responses.

Prior applications of SML to cryptographic protocols like TLS, DTLS, SSH, and QUIC have predominantly occurred in controlled local environments. In such settings, researchers can meticulously tune timeouts, analyze bugs via source code or binary review, and often modify the SUL to enforce determinism. While beneficial for focused analysis, these controlled conditions fail to capture the vast diversity and inherent complexities of the real-world TLS ecosystem. Vulnerabilities like the ROBOT attack (Bleichenbacher oracles) and certain CBC padding oracles were found in deployed implementations that did not exist in well-studied open-source libraries, highlighting the limitations of local testing.

Scanning TLS implementations over the Internet introduces a new set of challenges that previous SML approaches largely avoided. These include:

• Fully Blackbox Environment: The configuration and internal state of Internet servers are unknown, precluding manual adjustments or source code analysis.
• Non-Determinism: Factors like non-heterogeneous load balancing (different server versions/configs behind a single endpoint), varying system load, network jitter, and mapper discrepancies can lead to inconsistent SUL responses. Previous SML work often had to patch SULs to enforce determinism.
• Automatic Analysis: The sheer scale of Internet scans makes manual analysis of extracted state machines infeasible, necessitating automated bug detection and verification.
• Limited Scope vs. Learning Time: Expanding the input alphabet to cover more TLS features (and thus potentially more vulnerabilities) drastically increases the number of queries required, leading to polynomial growth in learning time and a higher risk of service interruption.

These challenges led the authors to pose two key research questions:

1. Is it possible to learn the state automaton of a TLS implementation deployed in an uncontrolled environment over the Internet at scale?
2. Is it possible to conduct state learning over the Internet using an extended input alphabet and automatically evaluate the resulting TLS state machines to detect unknown bugs? This paper answers both questions affirmatively through its novel methodology and extensive evaluation.

Key Findings

The research successfully demonstrated the viability of Internet-based SML at scale, yielding significant insights and uncovering critical vulnerabilities in deployed TLS implementations.

From an initial set of 7337 domains sourced from open bug bounty programs, the authors successfully extracted 1304 state machine models. This represents a 22% success rate for converged learning, even under challenging real-world conditions. These models provided unique insights into the diverse behaviors of TLS state machines deployed across the Internet.

Among the most impactful findings were:

• Handshake Transcript Integrity Vulnerability in Citrix NetScaler: The automated analysis reported 11 domains using Citrix NetScaler that exhibited a critical flaw. These servers accepted two ClientHello messages during the handshake but only included the second ClientHello in the session transcript validated by the Finished message. This allows a Man-in-the-Middle (MITM) attacker to inject arbitrary extensions into the handshake via a crafted initial ClientHello, without leaving a trace in the final transcript. Such a violation of transcript integrity fundamentally undermines TLS security guarantees and could facilitate renegotiation attacks.
• First CBC Padding Oracle Vulnerabilities Detected via SML: The study identified two domains vulnerable to CBC padding oracle attacks. These servers exhibited a differential response based on the validity of padding in manipulated records: messages with valid padding but an invalid MAC triggered a bad_record_mac TLS alert, while messages with invalid padding resulted in an immediate TCP RST (reset) without any TLS alert. This behavioral difference can be leveraged by an attacker to break confidentiality. This marks the first time such vulnerabilities have been detected through automated SML.

Beyond these critical vulnerabilities, the study also revealed a range of other deviations and non-compliant behaviors:

• Ignored Unsolicited Client Certificates: Two domains accepted a Client Certificate message even when none was requested, and allowed the handshake to complete without the expected CertificateVerify message (Figure 4c).
• Additional Domains Accepting Multiple Handshake Messages: Three other domains accepted multiple TLS 1.2 ClientHello messages, though unlike NetScaler, they included all messages in the session transcript, which would eventually lead to handshake failure.
• Aborted Renegotiation Handshakes: 38 domains accepted a renegotiation ClientHello but immediately terminated the connection with a TCP FIN after sending their initial handshake messages, rather than sending a no_renegotiation_warning alert as specified by the RFC.
• Ignored Application Data During Handshake: 43 domains tolerated application data sent during the handshake without replying. Manual tests suggested this data was silently ignored rather than passed to the application layer.
• Ignored Post-Handshake ChangeCipherSpec (CCS) Messages: 396 TLS 1.2 servers and 89 TLS 1.3 servers ignored a CCS message sent after a completed handshake, which is a compliance issue, as TLS 1.3 explicitly demands a fatal alert in this scenario.
• Unrejected Initial Messages: 17 domains seemingly accepted various messages (e.g., ChangeCipherSpec, ServerHello) at the start of the TCP session, though subsequent messages led to connection closure.
• Ignored Close Notify: 59 domains ignored a close_notify alert, allowing continued communication as if the session had not ended.
• Missing Key Update Support: One TLS 1.3 server immediately terminated the TCP connection upon receiving a KeyUpdate message.

The analysis further enabled the clustering of extracted state machines based on their similarity, revealing that most targets form larger groups with similar response patterns. However, the most critical security flaws were found in the "outlier" domains, underscoring the value of exploring the full diversity of the Internet's TLS ecosystem.

Technical Deep Dive

The success of Internet-based SML hinges on a sophisticated methodology designed to overcome the inherent challenges of black-box, non-deterministic, and large-scale environments. The authors' framework, depicted in Figure 2, comprises several innovative components, from initial feature extraction to automated security analysis.

Extended Scope and Alphabet Design:

To maximize the potential for vulnerability detection, the research significantly extended the SML alphabet beyond previous work. The scope included:

• TLS Versions: TLS 1.2 and TLS 1.3.
• Cipher Suites: Multiple cipher suite classes to capture behavior variations.
• Key Features: ID-based session resumption, renegotiation, client authentication, alert messages, and heartbeat messages.
• Attack Vectors: Specific test vectors for Bleichenbacher and CBC padding oracle attacks, designed based on prior research findings. These vectors were crafted as application data, handshake, ChangeCipherSpec, and heartbeat messages, resulting in 16 padding oracle inputs.
• Output Alphabet: Crucially, the SML output alphabet considered not only TLS messages but also the number of records and the socket state of the underlying TCP connection, allowing detection of vulnerabilities like padding oracles that manifest at the TCP layer (e.g., TCP RST).

The alphabet was systematically partitioned into four groups, progressively increasing in detail:

1. Happy Flow: Symbols for basic TLS handshake completion and encrypted data.
2. Extended: Adds optional paths (e.g., Certificate Verify), "reflection symbols" (messages client should not send to server, motivated by CVE-2018-10933), and a TCP connection reset symbol.
3. Vulnerabilities: Incorporates 28 attack symbols (12 Bleichenbacher, 16 Padding Oracle vectors).
4. All: Includes more unexpected inputs like DTLS HelloVerifyRequest and EndOfEarlyData.

Before learning, a classic TLS scanner (specifically TLS-Scanner [1]) performed feature extraction to generate a host-specific alphabet, removing symbols related to unsupported features (e.g., Bleichenbacher symbols if no RSA cipher suites are supported). Learning was then iteratively restarted with additional ClientHello symbols for different key exchange algorithms and symmetric cipher types, while retaining a persistent cache.

Learning Algorithm and Mapper:

The core learning algorithm used was TTT [24], implemented via the LearnLib library. The "mapper" component, responsible for translating abstract symbols to concrete TLS messages and vice-versa, was built upon TLS-Attacker [40]. TLS-Attacker's capability to dynamically create cryptographically valid yet manipulable TLS messages was critical for crafting specific attack vectors (e.g., malformed padding, ClientHello without key exchange for HelloRetryRequest) and managing session transcripts for renegotiation.

Optimizations for Internet Learning:

Given the slow nature of Internet interactions and the need to avoid DoS, several optimizations were crucial:

• Sink States: Artificial states were introduced to provide the learner with TCP and TLS context. For instance, if the SUL closes the TCP connection, subsequent queries (unless a connection reset) immediately return an "illegal learner transition" (φ) response from the mapper, trapping the learner in a sink state. Similar sink states were defined for TLS contexts (e.g., sending session resumption ClientHello before a session cache exists, or padding oracle inputs before encryption is active). This significantly reduces unnecessary SUL queries.
• Cache Optimization: A persistent cache stores responses to previously executed queries. With sink states, the cache can immediately answer queries known to lead to a sink state, further reducing SUL interactions. The cache proved highly effective, responding to 97.58% to 99.99% of all words (average 99.79%) requested during alphabet learning.
• Timeout Shortcuts: Leveraging the determinism of the SUL, this optimization (inspired by Rasoamanana et al. [32]) allows the mapper to stop receiving as soon as all expected messages for a flight are received, rather than waiting for the full timeout. This was applied for 82.39% of symbols sent to OpenSSL in evaluation. These optimizations collectively reduced execution time for the first alphabet from 369 minutes (unoptimized) to 5 minutes 35 seconds.

Handling Non-Determinism:

Internet environments amplify non-determinism. The authors employed several strategies:

• Majority Votes: Upon a cache conflict (a previously seen sequence yielding a different response), the query is repeated seven times. The most common response overwrites the cache, and the TTT algorithm is restarted with the updated cache.
• Dynamic Timeouts: If multiple cache conflicts occur, the timeout is dynamically increased, acknowledging that an insufficient timeout might have caused previous invalid cache entries.
• Cache Fallbacks: To mitigate issues from incomplete responses due to inaccurate timeouts, 25% of empty receives are re-executed with a full timeout to validate cache entries.
• Omission from Dataset: SULs exhibiting persistent non-determinism that prevent convergence within set time limits (24 hours for the first alphabet, 72 hours for the second) are excluded from the final dataset.

Counterexample Generation:

To refine the TTT algorithm's hypothesis, counterexamples were generated via three strategies:

1. Happy Flows: Predefined protocol-compliant message sequences (TLS 1.2/1.3) quickly identify common states.
2. Random Words: For each state in a hypothesis, 42,000 random words were generated to explore paths, acting as the "fuzzing" component.
3. Automated Security Analysis Findings: Detected non-compliances and vulnerabilities were used as counterexamples to verify their presence in the actual SUL.

Automated Security Analysis:

A novel approach was developed to automatically analyze the extracted Mealy machines for bugs and vulnerabilities (Figure 3).

• Valid Message Flows:
• Error States: Identified as states with no outgoing edges (except for connection reset).
• Happy Subgraph (HSG): Whitelisted states and edges corresponding to benign TLS connections, based on RFC-defined "symbol chains" and context conditions. This process also checks for context mismatches when reaching the same state via different paths.
• Valid Self-Edges: Checks if messages intended to progress the session actually cause a state change.
• Identifying Invalid Message Flows:
• Unexpected Edges Leaving HSG: Transitions from benign paths to non-error states that are not whitelisted.
• Illegal Paths to HSG: Edges leading from states outside the HSG back into it, indicating non-RFC-compliant paths to handshake completion (e.g., skipping security checks).
• Ignored Messages: Non-optional messages leading to the same node in the graph.
• Unexpected States: States outside the happy flow that are not error states, potentially allowing attackers to influence connection state.
• Suspicious Alert Messages: Alerts like DECRYPTION_FAILURE or INTERNAL_ERROR in unexpected contexts.
• Bleichenbacher and Padding Oracle Vulnerabilities: Identified by tracking differential behavior of attack-related inputs, distinguishing between "same-state" (response-based) and "state-diverging" (subsequent behavior-based) vulnerabilities.

Demo / Proof of Concept

While the paper describes a large-scale study rather than a live demonstration, the "Demo / Proof of Concept" section for this article focuses on the concrete vulnerabilities and behavioral anomalies discovered, demonstrating the practical feasibility and impact of the proposed SML methodology. The findings serve as a compelling proof of concept for Internet-based state learning.

Citrix NetScaler Transcript Integrity Vulnerability (Figure 4a):

The most significant finding was a critical transcript integrity vulnerability affecting 11 domains running Citrix NetScaler. The SML process revealed that these servers would accept two ClientHello messages during a single handshake. Crucially, the first ClientHello, despite influencing parameter negotiation, was not included in the session transcript that is cryptographically authenticated by the Finished message. This creates a powerful attack vector: a Man-in-the-Middle (MITM) attacker could inject malicious or unexpected extensions into the first ClientHello, which the server would process. The legitimate client, upon receiving the Finished message, would only validate a transcript containing its own (second) ClientHello, remaining completely unaware of the attacker's manipulation. This effectively allows an attacker to tamper with the session parameters without detection by the client, potentially enabling sophisticated renegotiation attacks [33, 35]. The visual representation in Figure 4 (a) illustrates this non-compliant flow, where an unexpected ClientHello leads to a state that eventually merges back into a successful handshake path, bypassing critical integrity checks.

CBC Padding Oracle Vulnerabilities (Figure 4b):

The study successfully identified two domains exhibiting CBC padding oracle vulnerabilities, a first for SML. The proof of concept here lies in the differential responses observed for specially crafted padding oracle attack vectors. When the mapper sent records with valid padding but an invalid Message Authentication Code (MAC) – denoted as ValPad in Figure 4 (b) – the server responded with a bad_record_mac TLS alert. However, when records with invalid padding (InvPad) were sent, the server immediately issued a TCP RST (reset) without any TLS-layer alert. This distinct behavioral difference between an invalid MAC and invalid padding provides a clear oracle that an attacker can exploit to decrypt ciphertext block by block, breaking confidentiality. The ability of SML to detect such subtle, state-diverging responses, even those manifesting at the TCP layer, underscores its power in uncovering complex cryptographic vulnerabilities.

Miscellaneous Findings (Figure 4c):

The automated analysis also highlighted other interesting, though perhaps less critical, deviations. For instance, Figure 4 (c) illustrates a case where a server accepted an unsolicited Client Certificate message. While not immediately exploitable without further context, such behaviors indicate a lax adherence to protocol specifications and could potentially open doors for future attacks or unexpected interactions. The ability to automatically flag such "unwanted" transitions and paths, as detailed in the automated security analysis, is a key aspect of the proof of concept, demonstrating the methodology's comprehensive nature.

Defensive Implications

The findings from this large-scale SML study offer critical insights for defenders and TLS implementers, highlighting areas where real-world deployments deviate from specifications and introduce vulnerabilities.

1. Strict RFC Compliance, Especially for Out-of-Order Messages: The discovery of transcript integrity vulnerabilities and ignored messages emphasizes the need for strict adherence to TLS RFCs, particularly regarding message ordering and expected state transitions. Implementations should explicitly reject unexpected or out-of-order messages with fatal alerts, rather than silently ignoring them or allowing them to lead to non-compliant handshake paths. Lax handling of unexpected inputs can create subtle bypasses.

1. Ensure Transcript Integrity: The Citrix NetScaler vulnerability underscores the paramount importance of ensuring that all messages influencing handshake parameters are included in the session transcript that is cryptographically signed and verified by the Finished messages. Any deviation here can allow Man-in-the-Middle (MITM) attackers to inject malicious extensions without detection, fundamentally undermining the security guarantees of TLS. Implementers should review their transcript construction logic meticulously.

1. Beware of Differential Responses: The CBC padding oracle findings demonstrate that subtle differences in server responses (e.g., a TLS alert versus a TCP RST) can be exploited as cryptographic oracles. Defenders should conduct thorough testing of error handling mechanisms, especially for malformed encrypted records, to ensure responses are indistinguishable to an attacker. This applies to padding, MAC errors, and other cryptographic integrity checks.

1. Harden Against Renegotiation Abuse: While renegotiation is an optional feature, its implementation needs careful consideration. Servers that accept renegotiation but then immediately terminate the connection (as found in 38 domains) are non-compliant and can create denial-of-service vectors. If renegotiation is not supported, a no_renegotiation_warning alert should be sent.

1. Address Non-Determinism in Deployment: Load balancers, firewalls, and other network intermediaries can introduce non-determinism, which complicates security analysis and can potentially mask vulnerabilities or allow attackers to craft inputs that trigger specific backend behaviors. While SML can mitigate this for analysis, deployed systems should aim for deterministic behavior from an external perspective where possible, or at least ensure that non-deterministic paths do not lead to security degradation.

1. Regularly Update and Review TLS Libraries/Configurations: The clustering of state machines suggests that many domains share similar underlying implementations. This means that vulnerabilities found in one instance are likely to affect many others. Keeping TLS libraries (like OpenSSL) up-to-date and regularly reviewing server configurations are fundamental defensive practices.

1. Consider SML as a Powerful Testing Tool: This research validates SML as a highly effective technique for identifying complex, real-world protocol state machine vulnerabilities, even in black-box, proprietary systems. Organizations developing or deploying critical TLS infrastructure should consider integrating SML into their security testing pipelines, complementing traditional fuzzing and static analysis. It can reveal issues that simple test vectors might miss.

1. Client-Side Vigilance: While the focus is on server-side vulnerabilities, clients also play a role. For instance, the transcript integrity vulnerability could be exploited against clients that do not strictly validate the full handshake transcript or are vulnerable to specific renegotiation attack variants.

Key Takeaways

• Internet-scale State Machine Learning is Feasible and Effective: This work successfully demonstrated that state machine learning can be applied to live, Internet-facing TLS servers at scale, extracting 1304 models from 7337 domains.
• Real-world TLS Implementations Deviate Significantly: Many deployed TLS servers exhibit behaviors that deviate from RFC specifications, often ignoring unexpected messages or allowing non-compliant paths, highlighting the gap between theoretical protocol design and practical implementation.
• Critical Vulnerabilities Uncovered in Outliers: The study identified a critical handshake transcript integrity vulnerability in Citrix NetScaler and the first CBC padding oracle vulnerabilities detected through SML, proving the method's ability to find high-impact flaws in deployed systems.
• Automated Analysis and Optimizations are Crucial: Novel techniques like partitioned alphabets, sink states, cache optimizations (achieving ~99.79% hit rate), timeout shortcuts, and automated security analysis are essential for making large-scale, black-box SML practical.
• Non-Determinism is a Major Challenge but Can Be Mitigated: Internet conditions introduce significant non-determinism, addressed through majority voting, dynamic timeouts, and cache fallbacks, though some targets remain too non-deterministic for full convergence.
• SML Provides Unique Ecosystem Insights: The clustering of state machines offers a novel way to understand the diversity and commonalities within the TLS ecosystem, indicating that while many systems conform, critical flaws often reside in less common or outlier implementations.

About the Speaker(s)

The research presented in "Towards Internet-Based State Learning of TLS State Machines" was conducted by a collaborative team of academics specializing in network security, cryptography, and protocol analysis.

Marcel Maehren and Nurullah Erinola are affiliated with Ruhr University Bochum, a prominent institution in IT security research. Their work, under the guidance of Jörg Schwenk, a distinguished professor at Ruhr University Bochum, focuses on practical aspects of network protocol security, including TLS vulnerabilities and state machine analysis.

Robert Merget is associated with the Technology Innovation Institute, a leading scientific research center. His contributions reflect expertise in advanced cryptographic attacks and their detection, particularly in the context of TLS.

Juraj Somorovsky is from Paderborn University, another institution known for its strong cybersecurity research. He is a recognized expert in cryptographic protocol analysis and has a history of uncovering significant vulnerabilities in widely used protocols like TLS through various testing methodologies, including state machine learning.

Collectively, the authors demonstrate extensive expertise in applying rigorous academic research to real-world security challenges, leveraging advanced techniques like state machine learning to uncover subtle yet critical flaws in complex systems. Their work bridges the gap between theoretical protocol analysis and practical deployment security.