cryptography.nw

\documentclass{article}
\usepackage{noweb,amsmath}
\pagestyle{noweb}
\begin{document}


\title{Trying out literate programming}

This is an experiment with literate programming, based around an
attempt to understand and implement some cryptanalysis.

\section{Cryptography basics}

\subsection{S-boxes}

An S-box is a simple function that substitutes one value for another
in a fixed, key-independent way.

Our S-box function should satsify the following test:

<<testSBox>>=
sbox = [2, 0, 3, 1]
self.assertEqual(0, substituteSBox(sbox, 1))
@ 

We require that every S-box has a size that is a power of two. We use
this little utility function to verify whether a number is a power of
two:

<<isPowerOfTwo>>=
def isPowerOfTwo(n):
    if n % 2 != 0:
        return False

    if n == 2:
        return True

    return isPowerOfTwo(n / 2)
@ 

Note that this only works if a positive integer is passed to it, which
is kind of lame. Even zero trips it up.

Substituting into an S-box is trivial:

<<substituteSBox>>=
def substituteSBox(sbox, index):
    if not isPowerOfTwo(len(sbox)):
        raise ValueError

    return sbox[index]
@ 

This is the main code module itself, which isn't very interesting at
all as it's just a way of sewing all the function definitions
together.

<<cryptography.py>>=
#!/usr/bin/python

<<substituteSBox>>
<<isPowerOfTwo>>
@ 

\section{Cryptanalysis}

\subsection{Linear cryptanalysis}
Linear cryptanalysis is a statistical method of attack that attempts
to exploit systematic weaknesses in the algorithm that, combined with
known plaintexts, can reveal some key information without the need for
brute force.

It proceeds by attempting to define linear equations of bits, of the
form:

\[
A \oplus B \oplus \dots \oplus Z = 0
\]

where each of $A$, $B$, \dots $Z$ is a single bit. For a given section
of a cryptographic algorithm (an S-box, say), we can construct a
linear expression between one or more bits of the input and one or
more bits of the output. Unless the algorithm is very poor, we will
not be able to construct such an expression that is true for every
possible input. However, some information can be yielded by
considering how often the equation is true for large numbers of inputs
(obtained via known plaintexts).

Consider the 4-bit S-box:

\[
S = \begin{matrix}
  [0, & 2, & 6, & 4, \\
  8, & 10, & 12, & 14, \\
  1, & 5, & 3, & 7, \\
  11, & 9, & 13, & 15]
  \end{matrix}
\]

This is certainly not a good S-box. It's pretty close to being just a
simple 1-bit left rotation. If it were a simple rotation, then by some
definitions it wouldn't even be regarded as an S-box.

This S-box will be used to turn a 4-bit plaintext $(P_0, P_1, P_2,
P_3)$ into a 4-bit cyphertext $(Q_0, Q_1, Q_2, Q_3)$. We can
immediately see that if $P_0 =0$ then $Q_3 = 0$. This gives us a
linear equation for this S-box that is always satisfied, i.e. that has
maximum bias:

\[
P_0 \oplus Q_3 = 0
\]

Let's imagine that this S-box is used as part of a simple cryptosystem
with a 4-bit key:

\[
C = K \oplus S(P)
\]

That is, the plaintext is first substituted into the S-box, then XORed
with the key. We use $Q$ to refer to the result of the S-box, and $C$
for the full cyphertext.

We obtain a couple of known plaintexts:

\begin{align}
(P^1 = 6, & C^1 = 6) \\
(P^2 = 10, & C^2 = 9)
\end{align}

With one known plaintext we could find the key via brute force, which
for a 4-bit key would require 16 operations. The hope is that by
employing linear cryptanalysis we can use the second known plaintext
to cut down this number of operations.

In fact, linear cryptanalysis is of course unnecessary. Since we know
the S-box, we can calculate $S(P)$ for that plaintext, and then XOR it
with the ciphertext to immediately recover the key. Obviously more
sophisticated cryptosystems make this impossible by having multiple
rounds where the intermediate values are unknown to us, so let's
ignore this simple attack.

Consider the linear equation:

\[
P_0 \oplus Q_3 = 0
\]

We know this will always be true. However, we don't know $Q_3$ (the
fourth bit coming out of the S-box), only $C_3$ (the fourth bit of the
cyphertext). But the cyphertext is just a linear combination of the
corresponding bits of the key and the S-box output. Therefore we can
construct a linear equation that will be satisfied:

\[
P_0 \oplus C_3 \oplus K_3 = 0
\]

Substituting in bits from our known plaintext yields a bit from the
key:

\[
0 \oplus 0 \oplus K_3 = 0
\]

This immediately yields that the fourth bit of the key is $0$. We can
brute-force the remaining bits of the key in just 8
operations. Finding this key bit was just a single operation, so this
has saved us time.

\section{Testing}

There should hopefully be unit tests that can be run to verify that
everything tangled correctly. They could look something like this:

<<tests.py>>=
import unittest
from cryptography import substituteSBox

class CryptographyTest(unittest.TestCase):
    def testSBox(self):
        <<testSBox>>

    def testWronglySizedSBox(self):
        sbox = [1, 2, 3]
        self.assertRaises(ValueError,
                          lambda: substituteSBox(sbox, 1))

if __name__ == '__main__':
    unittest.main()
@ 

\section{License}

Copyright (c) 2011 Tim Martin (tim@asymptotic.co.uk)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

\end{document}