Visual Cryptanalysis

Thomas Ptacek | August 25th, 2007 | Filed Under: Defenses, Development, Uncategorized

Daniel J. Bernstein visualizes ciphers by rendering their DAGs —- an intermediate representation, as would be used by a compiler as a step towards generating object code.

(If you’re not familiar with the concept, a DAG is just a tree where a node can have more than one parent. Single inheritance: tree. Multiple inheritance: DAG. If you are familiar with the concept, I apologize for saying “a DAG is just a tree…”).

How cool is this? For starters: I must have this poster. Here’s a snippet of MD5:

And of SHA-256:

More substantively, from the (short) paper:

The right half of the SHA-1 graph is the SHA-1 message expansion, and the right half of the SHA-256 graph is the more complex SHA-256 message expansion; for comparison, the MD5 graph has many long edges, allowing an attacker to effortlessly pierce deep into the heart of the MD5 computation.

Using visualization tools to find vulnerabilities has been in vogue among the RCE crowd for years now. It’s the whole idea behind Halvar’s excellent BinNavi tool. Now here’s an example of how cryptographers have been using the same idea.

[…] I certainly can’t claim that the tools have saved time in cryptanalysis. But I think that the tools will save time in cryptanalysis, automating several tedious tasks that today are normally done by hand.

Worth watching. Funny quote:

[M]y initial experiments with bit DAGs for MD5 have crashed every standard drawing tool that I’ve tried. My own drawing tools are much more careful in their use of memory.

Ok, maybe it’s only funny if you’ve tried to do large layouts in Graphviz before, or wrote your own crappy graph layout code.