D. J. Bernstein
Hash functions and ciphers
Cipher DAGs

The 2007.09.24 software

I gave a talk on cipher DAGs on 2007.09.24. This page records the software that I used for the talk.

WARNING WARNING WARNING: This software is a crude prototype. It has many obvious deficiencies, both internal and external. I haven't done even a single test of whether the DAGs compute the functions that they're supposed to compute.

Converting C/C++ software into a DAG

The MD5 compression function uses a chain of 17220 bit operations (5640 two-input xors, 4092 three-input xors, 3528 two-input ands, 3960 three-input majorities; I'm counting "not" operations for free) to compress 512 bits to 128 bits. Here's the software that I used to compute the MD5 DAG:

     wget https://cr.yp.to/cipherdag/20070924/dagbit.h
     wget https://cr.yp.to/cipherdag/20070924/dagbit8.h
     wget https://cr.yp.to/cipherdag/20070924/dagbit16.h
     wget https://cr.yp.to/cipherdag/20070924/dagbit32.h
     wget https://cr.yp.to/cipherdag/20070924/dagbit.cpp
     wget https://cr.yp.to/cipherdag/20070924/dagbitn.cpp
     wget https://cr.yp.to/cipherdag/20070924/dagbit8.cpp
     wget https://cr.yp.to/cipherdag/20070924/dagbit16.cpp
     wget https://cr.yp.to/cipherdag/20070924/dagbit32.cpp
     wget https://cr.yp.to/cipherdag/20070924/md5.cpp
     wget https://cr.yp.to/cipherdag/20070924/dagy
     chmod 755 dagy
     g++ -fomit-frame-pointer \
     -o md5 md5.cpp dagbit32.cpp dagbit16.cpp dagbit8.cpp dagbit.cpp
     ./md5 > md5.out
     ./dagy < md5.out > md5.y

The DAG is placed into md5.y.

The dagbit functions are general-purpose tools. The md5.cpp code is an easy modification of preexisting MD5 software.

The dagy script is a reflection of the inadequate time that I spent thinking about DAG data formats. Perhaps I should change dagbit to produce the same output format directly; perhaps I should change the other scripts to handle what dagbit does now; or perhaps, after further thought, I'll end up changing everything to support another format.

Visualizing a DAG

Here's the software that I used to show pictures of the MD5 DAG:

     aptitude install libx11-dev
     wget https://cr.yp.to/cipherdag/20070924/draw.c
     wget https://cr.yp.to/cipherdag/20070924/font.c
     wget https://cr.yp.to/cipherdag/20070924/font.h
     gcc -std=c99 -O2 -fomit-frame-pointer \
     -o draw draw.c font.c -lX11 -lm
     ./draw < md5.y

Processing a DAG

I also showed pictures of two modified DAGs, md5.x and md5.xy, that spread out and rearrange the nodes to show somewhat more clearly how the nodes are connected. I created these DAGs as follows:

     aptitude install original-awk
     wget https://cr.yp.to/cipherdag/20070924/dagcollapse
     wget https://cr.yp.to/cipherdag/20070924/dagpull
     wget https://cr.yp.to/cipherdag/20070924/dagsort
     wget https://cr.yp.to/cipherdag/20070924/dagxinit
     wget https://cr.yp.to/cipherdag/20070924/dagxslide
     chmod 755 dagcollapse
     chmod 755 dagpull
     chmod 755 dagsort
     chmod 755 dagxinit
     chmod 755 dagxslide
     ./dagpull < md5.y > md5.pull
     ./dagxslide < md5.pull > md5.ps
     ./dagsort < md5.ps > md5.x
     ./dagxinit < md5.x > md5.xa
     ./dagcollapse < md5.xa > md5.xc
     ./dagcollapse < md5.xc > md5.xd
     ./dagxinit < md5.xd > md5.xi
     ./dagxslide < md5.xi > md5.xs
     ./dagsort < md5.xs > md5.xy

Beware that dagpull creates a very large DAG (more than 400000 nodes), and dagxslide takes a long time to handle that DAG. But it does finish eventually.

I used original-awk in these scripts because mawk (shipped under Linux as awk) died with an internal memory error. I don't know how original-awk compares to mawk in speed.

There are previous graph-layout tools, notably the dot program from the graphviz package. However, I wasn't able to convince those tools to handle anything as large as the MD5 DAG.