1
$\begingroup$

I'm cryptanalyzing a cipher I've written, which takes a message of arbitrary size and returns a message of the same size. Because of the rotBitcount operation, which rotates the message by the number of one-bits in it, just xoring two ciphertexts is inadequate when doing differential cryptanalysis. So I decided to convolve them instead.

Take two plaintexts, $P$ and $P'$, which are at least 8 bytes long and differ by one bit. Encipher them, getting $C$ and $C'$. Compute the bias of $C$ and $C'$, where $bias(000000)=1$, $bias(111111)=-1$, and $bias(10010110)=0$. Let $b=bias(C)×bias(C')$ be the expected bias of the convolution. Let $n$ be the number of bits. For each $i$ in $0..n-1$, compute $$v_i=1-2\frac{\sum_{j=0}^{n-1}xor(C_j,C'_{(j+i)\mod{n}})}{n}-b$$ as the unbiased convolution of $C$ and $C'$. Compute $V=\sum_{i=0}^{n-1}v^2$. Assuming the null hypothesis that $C$ and $C'$ are independent random bit vectors (the alternative hypothesis means that the cipher is broken), what are the mean and standard deviation of $V$?

$\endgroup$

1 Answer 1

1
$\begingroup$

I did an experiment in which I generated 32-byte bit patterns with biases ranging from $\frac{-3}{4}$ to $\frac{3}{4}$ in steps of $\frac{1}{4}$ by taking up to three pseudorandom bit patterns generated with the cipher and anding and oring them. Then I took two of these bit patterns and computed their unbiased convolution. The mean of $V(C,C')$ turned out to be $(1+bias(C))(1-bias(C))(1+bias(C'))(1-bias(C'))$, where $(1+bias(C))(1-bias(C))$ is related to the variance of the binomial distribution, $np(1-p)$. When I divided the convolutions by the means, thus making the means all 1, the variances of $\frac{V(C,C')}{μ}$ for these various biases all clustered around 0.0078125, which is $\frac{2}{n}$.

Since the standard deviation is a little less than $\frac{1}{11}$, and the number, being a sum of squares, can't be negative, a normal distribution is inappropriate for a statistical test. A chi-square distribution should be better.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .