\documentclass[a4paper,10pt]{article}
%opening
\title{Key-Data-Paired Differential Cryptanalysis}
\author{Luke Kenneth Casson Leighton}
\begin{document}
\maketitle
\begin{abstract}
Traditional Block cipher Differential Cryptanalysis finds relationships between one single bit of a key and a single bit of output, in one fixed location in the output block. The new technique described in this paper, which is being named Key-Data-Paired Differential Cryptanalysis, locates relationships between groups of bits in keys and groups of bits in output blocks (instead of just single bits in fixed locations). Using even as little as 512 blocks of known plaintext on a 128-bit block cipher (for example Rijndael-128), the correlations between groups are sufficient to derive statistical probabilities for individual bits in the key being 0 or 1. If there are no correlations, we anticipate these probabilities to indicate correct guesses for each bit to average 64 bits. Whilst only a few runs so far have been performed (taking 6 hours each), what is actually being consistently shown is about 76 bits being guessed, with one run going as high as 81 bits. Research is underway to ascertain whether those statistical probabilities can be used in a feedback loop to gain better accuracy, by generating weighted keys based on the previous probabilities.
\end{abstract}
\section{Introduction}
Block cipher design is based on the assumption that there will be no inter-relationships detectable between any bits of the key and any bits of the encrypted data, no matter what the input data is, and no matter how much input data is given. Cryptanalysis challenges this assumption. The analysis which is being called Key-Data-Paired Differential Analysis makes the assumption that there are inter-relationships between groups of bits in a key and groups of bits in the data.
Some rather unusual but perfectly reasonable statistical analysis is used to spot such inter-relationships, and, using a known plaintext attack, derive probabilities for certain bits of the key. As of yet, it is not possible to determine which bits have been correctly guessed and which have not: obviously, it is only by means of really knowing the key that the guesses can be confirmed as correct in the first place. Refinement of the rather crude process being used at present may yield better results in the future.
The analysis has startling implications for the design of block ciphers, not least is that the whole principle on which block ciphers are founded may be flawed. The key principle of block cipher design is that it is mathematically challenging to locate inter-relationships between groups of key bits and data bits, in the simple function $O = E(K, D)$. Some cryptographers have designed block ciphers with Tweaks, where there is additional feedback into the algorithm ($O = E(K, D, Tweak)$ or $O = Etweak(K, D)$ ) that would make the type of attack described in this paper ineffective. However, in its simplest form, this paper demonstrates that ECB mode ciphers, designed on the traditional $O = E(K, D)$ design, is likely to be fundamentally flawed.
\section{Deriving the 3D Key-Data Histogram}
The first step is as follows:
For any 128-bit key-data pair, first perform an encrypt $Ob=E(K,D)$. This will be called the baseline (for a given key-data pair). Then, perform 16384 (128 by 128) encrypts, by changing one bit of the key and one bit of the data in each encrypt $Onm = E(K xor (1<