Substitution-permutation network visualizer

Question

I'm doing differential analysis of a toy block cipher in which I've to extract the differential characteristic of the first n-1 rounds.

However, I can't do that very well as I can't see the network itself. Basically, I wonder if there is a software which generates a SPN network automatically given round permutations&S boxes and presents it visually. This would make the analysis much simpler.

Answer 1

You might be interested in TikZ for Cryptographers:

PGF/TikZ is a tandem of languages for producing vector graphics from a geometric/algebraic description. PGF is a lower-level language, while TikZ is a set of higher-level macros that use PGF. The top-level PGF and TikZ commands are invoked as TeX macros. Together with the LaTeX language, it is the most efficient way to write research papers.

Here is an example of a substitution permutation network diagram that was drawn with it:

And here is the source that created it:

\documentclass{standalone}

\usepackage{tikz}
\usetikzlibrary{calc}

\usetikzlibrary{crypto.symbols}
\usetikzlibrary {positioning}
\usetikzlibrary{shapes}
\begin{document}    
    \begin{tikzpicture}
        %% Subkey XORs
        \foreach \z in {0,...,15} {
            \node[XOR, scale=0.8] (xor\z) at ($\z*(0.75em, 0)$) {};
            \node[XOR, scale=0.8] (xorr\z) at ($\z*(0.75em, 0)+(0,-9em)$) {};
        }

        %% Nodes positions
        \foreach \z in {0,...,15} {
            \node (i\z) [above = 0.75em of xor\z] {};
            \node (o\z) [below = 2.5em of xor\z] {};
            \node (ii\z) [above = 0.25em of xorr\z] {};
            \node (oo\z) [below = 3em of xorr\z] {};
            \node (t\z) [below = 4em of oo\z] {};
            \draw[thick] (i\z) -- (xor\z);
        }

        %% Permutation layer
        \foreach \z [evaluate=\z as \zz using {int(mod(11*\z,15))}] in {0,...,14} {
            \draw[thick] (xor\z)  -- (o\z.center)  -- (ii\zz.center) -- (xorr\zz) -- (oo\zz);
            \draw[thick] (oo\z.north)  -- (t\zz.south) -- +(0,-0.5em);
        }
        \draw[thick] (xor15) -- (o15.center) -- (ii15.center) -- (xorr15) -- (oo15);
        \draw[thick] (oo15.north) -- (t15.south) -- +(0,-0.5em);    

        %% SBoxes
        \foreach \z in {0,...,3} {
            \node[draw,thick,minimum width=2.75em,minimum height=2em,fill=white] (p4) at ($\z*(3em,0) + (1.1em,-2em)$) {$S$};
            \node[draw,thick,minimum width=2.75em,minimum height=2em,fill=white] (p4) at ($\z*(3em,0) + (1.1em,-11em)$) {$S$};
        }

        \node[left = 0em of xor0] {$k_{1}$};
        \node[left = 0em of xorr0] {$k_{2}$};

    \end{tikzpicture}
\end{document}

Answer 2

I know of no software that lets you visualize an arbitrary SPN network; however, many of us on the semiconductor side of things have their verification tools output visualizations based on the bit states. We used these to compare the SPICE output to the software simulated. My Simon Cipher and AES verification tools print out bit grids. My AES tools are async, but the simontool program gives synchronous outputs and will give you an example of how to generate these types of bit grids if you dig into the code. As a tractable example using the SIMON32/64 test vector:

simontool -e -b 32 -k 64 -s 1918111009080100 -t 65656877 -l log.e.32.64.txt -x simon-e-32-64

That dynamically creates a LaTeX file that contains a bit grid based on the input vector.

Answer 3

I'm not 100% familiar with all the crypto software out there, but have spent a fair while looking at SPNs. If you google images[SPN] all you get are diagrams that look as if they've been hand drawn. Some are in the info graphic style. I've never found a reference in the literature either to an analysis tool. All crypto papers seem to hand draw their flows.

I'm not quite sure how this would work exactly. I've written SPNs with my own code. So you'll have repeated rounds of a substitution layer, and a permutation layer. You might even throw in a (sub)key merge layer. All these layers would have to be entered into the tool, probably in the form of code as the operations will be unique to your algorithm. You can't just simply enter a substitution matrix or a polynomial equation into a form. You might have bit shifts, rolls or even more exotic manipulations like the weirdness of the π mapping in Keccak. Incidentally, avalanche studies are also done with custom rolled code.

The programmatic solution to this is to instrument your code. So I wrote routines that nicely formatted the state whenever called. Locate them at strategic points throughout your algorithm and between layers. You might start with a simple input block like "1000000..." and see how those bits propagate.

(Of course programming subjects are off topic here so please ignore this answer.)