Directed Acyclic Graphs for Crypto Algorithms

Maybe this on directed acyclic graphs is a bit too geeky for the blog, but I think it’s interesting.

The idea of drawing cipher DAGs certainly isn’t new; DAGs are common in cryptographic research and even more common in cryptographic education. What’s new here is the level of automation, minimizing the amount of cipherspecific effort required to build a DAG from a cipher (starting from a typical reference implementation in C or C++) and to visualize the DAG.

My tools are only prototypes at this point. I’m planning to put a cipherdag package online, but I haven’t done so yet, and 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.

Tags: ,

Posted on October 10, 2007 at 2:59 PM • 29 Comments

Comments

haapi • October 10, 2007 4:50 PM

The tool “make” builds a DAG of dependencies.
To think we just had to type “make codebreaker” and be done with it. 🙂

dragonfrog • October 10, 2007 4:56 PM

@haapi

Dan J. Bernstein wrote this tool. Make will not build code by DJB; recondite and obscure indeed is his code.

Fred P • October 10, 2007 5:03 PM

Pretty. Depending on how his tool functions, I could see uses well outside the field he suggests. For example, very large projects might find this valuable as the basis for a good dependency generator.

RonK • October 10, 2007 5:16 PM

@ Fred P

Pretty… uses well outside the field…

Kind of a pity, then, that djb almost never licenses his code with a standard open-source license, making it nearly impossible to reuse his code legally.

Chris S • October 10, 2007 8:33 PM

Ok – it’s not immediately obvious, but if you start magnifying the PDF, you can see details in the graphs. In fact – you can see all the details in the graph once you get up around 16x normal!

Unfortunately, I can’t find any way to print the page and make these readable. Even at max dpi, the printed rectangle labels are barely findable, let alone legible. The dots can be made out, but they can only be identified by size, not by the symbol they contain.

Lawrence D'Oliveiro • October 10, 2007 11:55 PM

I thought these things were just called “DFDs” (Data Flow Diagrams). The fact that they have no cycles simply indicates that the computation is finite. What’s so geeky about them? DJB points out one obvious thing: short lines good, long lines bad. Are there other, more subtle points to be noticed?

Paul Crowley • October 11, 2007 12:52 AM

@RonK:

Actually, quite a lot of what DJB writes he makes PD – I think all his crypto software is (MACs, signature schemes, etc).

Another vote for the geeky posts – who else is going to blog about such things?

Tim P • October 11, 2007 2:01 AM

This is my vote for more posts like this!

I would love to see something like this for compiled code too, so we can get an impression of any bespoke encryption in those snake oil products.

Anonymous • October 11, 2007 4:35 AM

I’m in favour of posts such as this one, too. If you’ve got interesting material that relates to cryptography (or squids), by all means, post away! 🙂

Max • October 11, 2007 8:05 AM

I agree that more “geeky” posts are interesting.

However, it might not be the goal of this blog. Remember, not everyone has extensive training in mathematics and computer science.

Maybe M. Schneier could provide this information in a separate blog or point those of us with the more academic interest in the right direction ?

Matthew Skala • October 11, 2007 8:31 AM

Hey, I’ve got a neat idea! What if we built little machines that blocked or permitted electricity to flow in order to represent bits? If we created such a device (I’d take the liberty of naming them “gates”) for each vertex in one of these dags, we could link them up with wires corresponding to the edges, and the resulting machine would be a physical analogy for the cipher, expressed in circulating electricity (hence, an “analog circuit”.) Some day it might even be possible to miniaturize them so that dozens or even hundreds of gates would fit on a square inch of some easily-processed crystalline substance (like gallium arsenide). It wouldn’t have any practical applications, of course, but it would be an interesting laboratory curiosity.

Oh, wait.

++Don • October 11, 2007 11:49 AM

I, for one, welcome our geeky blog posting overlords. Oh wait, this isn’t /. 🙂

It’s amazing how just bringing the human visual cortex into play makes such a different in understanding how a cipher works. The long edges in MD5 have already been mentioned, but it’s the fact that you can see them that makes it so much more obvious why they’re problematic (“Wow, look at how those lines go around most of the function.”) And the DAG for TEA beautifully demonstrates just how simple TEA is. It would be interesting to see all five DAGs drawn to the same scale for comparison, instead of scaled to the same height for pagination.

Regarding DJB’s lack of licensing on some of his packages, this does not prevent their use. It prevents them from being redistributed without his permission. If you want to use them in a larger package, then either ask for permission or simply require them as a separately obtained prerequisite.

Porlock Junior • October 12, 2007 2:41 AM

Just curious: Did anyone else momentarily see a headline about directed acrylic graphs?

Musta been the Daily Show segment on kids’ art collections, plus it’s getting late.

alexT • October 12, 2007 12:02 PM

Just curious: Did anyone else momentarily see a headline about directed acrylic graphs?

Indeed :))

LOL • October 14, 2007 11:30 PM

Geeky posts? Give me a break. Schneier wouldn’t know anything about geeky. Bruce Schneier does NOT have a Ph.D. degree.

Daniel J. Bernstein is a respected cryptographer and security expert with a Ph.D. degree from the University of California, Berkeley.

I repeat: Schneier does NOT have a Ph.D. degree.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.