Schneier on Security
A blog covering security and security technology.
« Cheap Cell Phone Jammer |
| Shoe Scanners at the Orlando Airport »
October 10, 2007
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.
Posted on October 10, 2007 at 2:59 PM
• 29 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
I, for one, would welcome more geeky posts like this one.
A third vote in favour of them.
I would personally like to see more posts of this nature
Does anyone but geeks read this blog? Why the hesitation?
The tool "make" builds a DAG of dependencies.
To think we just had to type "make codebreaker" and be done with it. :-)
Dan J. Bernstein wrote this tool. Make will not build code by DJB; recondite and obscure indeed is his code.
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.
@ 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.
More geeky posts are good!
freaks must be miserable now :-)))))
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.
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?
I want more geeky posts too!
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?
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.
More geeky posts to the people.
Back to the old school Crypto-Gram days.
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! :)
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 ?
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.
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.
+1 vote for more posts like this
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.
> Just curious: Did anyone else momentarily see a headline about directed acrylic graphs?
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.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.