ph-neutral header
welcome talks guest_info party history imprint darklab phenoelit twist4

Exploiting Computational Slack in Protocol Grammars


Language-theoretic security uses the principles of formal language theory, computability theory, and formal semantics to evaluate the security properties of computational protocols. In its ideal form, it is used to build and verify secure systems; however, the same techniques software architects use to prevent entire classes of attacks against a language-theoretically secure protocol also enable attackers to systematically discover attacks against non-LT-secure protocols, particularly those deployed in dynamic environments with multiple implementations of the same specifications.

We will discuss the fundamentals of language-theoretic security, then explain how we applied these principles to the analysis of X.509, leading to our recent multiple-vulnerability break of the Internet certificate authority infrastructure. We will also outline steps for realizing the security potential of LTS-aware protocol stacks compatible with the existing Internet infrastructure.


Meredith L. Patterson is an independent researcher whose areas of expertise range from CS-related topics such as database design, datamining algorithms, complexity theory, computational linguistics, information security, and privacy enhancing technology systems; to synthetic biology, design of transgenic organisms using low-cost, build-it-yourself lab equipment, human metabolic system studies; and speculative fiction as a published author of multiple short stories, mostly science fiction. Meredith has a BA in Linguistics from the University of Houston, and a MA in Linguistics as well as an MS in Computer Science from the University of Iowa. She is a co-founder of the DIYBIO movement, and has done work on transgenic lactic acid bacteria. She co-invented the field of language theoretic security research, which she used to successfully defeat such troublesome attacks as SQL injection with her "Dejector" library. Most recently, she presented the Biopunk Manifesto at a UCLA synthetic biology conference, and presented her work with Dan Kaminsky and Len Sassaman on breaking the Internet's certificate authority system (by creating usable, bogus certificates crafted to exploit ambiguity in X.509 parsing implementations using language theoretic security analysis principles) at the Financial Cryptography conference. Meredith lives in Leuven, Belgium. In her spare time, she knits, repairs cars, and hacks on open source software. This is her second PH-Neutral.

Len Sassaman is a member of the Shmoo Group as well as a researcher at COSIC, the COmputer Security and Industrial Cryptography laboratory at K.U. Leuven. He is currently pursuing his PhD in electrical engineering, advised by Bart Preneel and David Chaum. The focus of Len's research is privacy-preserving technologies, such as anonymity and confidentiality systems, which emphasize usability as a security parameter in privacy solutions subject to the limitations of today's communication systems. Len is the maintainer of the anonymous remailer software Mixmaster, and has written many papers on the topic of anonymous system design. He also co-invented the field of language theoretic security research, which is the topic of his talk. Prior to becoming an academic, Len was an active cypherpunk and held such roles as Chief Architect at Anonymizer, Inc. and a lead software engineer at PGP Security, Inc. Len has spoken at many security conferences, co-founded the CodeCon conference and the HotPETS workshop, and is a returning attendee at Ph-Neutral.