BlueHat IL 2020 - Challenges - Alon Livne - The Chitty Chitty Chat Chat Challenge

### Overview At BlueHat IL 2020, Alon Livne presented the walkthrough and solution for "The Chitty Chitty Chat Chat Challenge" (also referred to as the Interplanetary Chat Challenge). Developed around the conference's themes of electronic freedom, surveillance, and privacy, the challenge centered on an end-to-end encrypted, peer-to-peer chat system designed to eliminate the reliance on centralized servers seen in mainstream messaging platforms.

### Key Topics - **Decentralized Chat Architecture**: Built in Go (Golang) using the `libp2p` networking library. It relied on a Kademlia DHT bootstrap node for initial discovery, encrypted peer transports, and GossipSub—a mesh-based pub-sub routing protocol where chat rooms were implemented directly as topics. - **Message Formatting and Encryption**: Messages were serialized via Protocol Buffers (protobufs). Encrypted messages generated a randomized 16-byte initialization vector (IV) and a 16-byte per-message key using an internal random number generator, encrypting the payload with the AES-IGE block cipher. The per-message key was originally intended to be protected with a group/master key derived from a room password. - **Dual_EC_DRBG Backdoor Mechanics**: The application's custom generator (`BHRNG`) used the NIST P-256 elliptic curve. It operated identically to the infamous Dual_EC_DRBG standard, multiplying state by generator point $P$ and outputting state masked by point $Q$. If an attacker knows the scalar relationship $d$ where $P = d \times Q$, observing an output allows computing the internal state and predicting all subsequent outputs. - **Coppersmith's Attack on Partial RSA Keys**: Discovering hidden network topics revealed a redacted, truncated RSA private key and an encrypted base64 payload. Leveraging Coppersmith's small roots attack enabled key recovery from partial prime factors.

### Technical Details 1. **Reconnaissance and Topic Discovery**: While unauthenticated transports protected network traffic in transit, peers could observe all GossipSub traffic. Modifying the client to inspect dropped messages revealed hidden chat rooms: a public plaintext room and an encrypted room named "deep state." 2. **RSA Key Recovery**: The plaintext chat room leaked a base64 ciphertext and an ASN.1/PEM-formatted RSA private key that had missing bytes in the middle and was truncated at the end. While the private exponent $d$ was mostly gone, the modulus $n$, public exponent $e$, and a significant approximation of prime factor $p$ were present. Using SageMath's `small_roots` implementation of Coppersmith's attack, the polynomial $X - \text{partial\_p}$ was solved, efficiently factoring $n$ and restoring the private key. 3. **Extracting the Backdoor Constant**: Decrypting the associated base64 message with the recovered RSA key yielded the backdoor value $d$, which linked elliptic curve points $P$ and $Q$. 4. **Predicting RNG Output and Decrypting Chat**: Because the 16-byte IV was output directly before the 16-byte message key in `BHRNG`, the transmitted IV served as a raw observed output $R$. By multiplying the point derived from the IV by scalar $d$, the solver derived the generator's next internal state and generated the corresponding AES-IGE message key. Bypassing the room password entirely, this allowed decryption of the "deep state" chat room, revealing the challenge flag: `don't trust RNGs`.

### Takeaways The challenge highlights how subtle mathematical relationships in cryptographic primitives—specifically trapdoors in elliptic curve pseudorandom number generators like Dual_EC_DRBG—can completely undermine end-to-end security despite using robust ciphers like AES-IGE.