Practical format transforming encryption with context-free grammars and finite automata

Network censorship and Deep Packet Inspection (DPI) allow adversaries to identify and block encrypted traffic based on its protocol signatures, threatening free communication even when content is protected. Format Transforming Encryption (FTE) addresses this by producing ciphertexts that conform to a target format, disguising traffic as a permitted protocol. Existing tools such as LibFTE are limited to regular languages, while grammar-based approaches lack practical, publicly available implementations. This thesis presents an open, modular FTE library in Python that bridges this gap by separating syntactic and lexical structure: context-free grammars handle high-level syntax, while finite state automata handle token-level constraints. The two components are ranked independently and combined via a bit interleaving pairing, enabling efficient ranking and unranking over context-free languages. Encryption uses AES in CTR mode with a nonce embedded into the ciphertext and cycle-walking ensures ciphertexts always conform to the target format. The library is evaluated against LibFTE and grammar-based formatted encryption, demonstrating reduced complexity and improved flexibility. Applicability to real-world formats is validated on C99, JSON and DNS, showing that structurally valid, protocol compliant ciphertexts can be generated efficiently. The results confirm the practical feasibility of the approach and outline directions for future optimization.

La censura di rete e il Deep Packet Inspection (DPI) consentono a un avversario di identificare e bloccare il traffico cifrato in base alle sue signature di protocollo, minacciando la libertà di comunicazione anche quando il contenuto è protetto. La Format Transforming Encryption (FTE) affronta questo problema producendo testi cifrati conformi a un formato di destinazione, in modo da mascherare il traffico come un protocollo consentito. Gli strumenti esistenti come LibFTE sono limitati ai linguaggi regolari, mentre gli approcci basati su grammatiche sono privi di implementazioni pratiche e pubblicamente disponibili. Questa tesi presenta una libreria FTE modulare e open source scritta in Python, che colma questa lacuna separando la struttura sintattica da quella lessicale: le grammatiche libere dal contesto gestiscono la sintassi ad alto livello, mentre gli automi a stati finiti gestiscono i vincoli lessicali. Le due componenti vengono classificate indipendentemente e combinate tramite un pairing a bit interleaving, garantendo procedure di ranking e unranking efficienti su linguaggi liberi dal contesto. La cifratura avviene tramite AES in modalità CTR con nonce incorporato nel testo cifrato e il cycle-walking assicura che il risultato rispetti sempre il formato di destinazione. La libreria viene valutata rispetto a LibFTE e alla formatted encryption basata su grammatiche, mostrando minore complessità e maggiore flessibilità. L'applicabilità pratica è validata su C99, JSON e DNS, dimostrando la capacità di generare testi cifrati strutturalmente validi e compatibili con protocolli reali. I risultati confermano la fattibilità dell'approccio e delineano direzioni per future ottimizzazioni.