Karl.Frank <Karl.Frank@freecx.co.uk> wrote:
On 09.05.16 02:28, Rich wrote:
Karl.Frank<Karl.Frank@freecx.co.uk> wrote:
On 08.05.16 23:09, Rich wrote:
Karl.Frank<Karl.Frank@freecx.co.uk> wrote:
Did you realise that there is a KSA (Key Schedule Algorithm)?
A chain is only as strong as its weakest link.
With this weak a link early on in the chain, there seems to be
little point in attacking the KSA itself at this point.
Additionally, this much weakness in the permutation algorithm does
not bode well for the robustness of the KSA.
I can understand that you were so over-excited in your believing by
breaking an algorithm that fast and easy. And I must admit that you
did so very well, explained everything, gave examples, did the whole
calculation. I'm a bit impressed how fast you worked it out.
But even if the seeds are producing duplicate first initial states
*before* the actual key is applied during the key schedule algorithm,
it really doesn't weaken the encryption algorithm. Just imagine -
what I have mentioned in one of my previous answers - the first
initial setup of the state array would be like
for (i=0; i<256; i++) {
SBox[i] = i;
}
Do you really consider this as a weakness of the encryption algorithm,
just because there is only *one* possible first initial setup of the
internal state array?
One step at a time. One does not begin with an analysis of these
things as a whole, one picks apart the individual pieces first, finding
weaknesses in each. Then when one gets to the whole, one already knows
all the weaknesses of each component piece.
The next step has not yet been done (simply because I've run out of
extra time to spare to poke at it for the moment).
I agree with you. No need to hurry. Perhaps it may be helpful if I give
you the hint that it might be worth taking a closer look at the first 8
to 16 byte output of SBox8 right after the KSA. I have discovered
something - as mentioned earlier in another answer - which is a bit
similar to these problems RC4 has.
And I have decided to leave the source code of SBox8 as it is for now,
just for the sake of a potentially successful attack.
You've discovered that the first few bytes output by your algorithm are
not quite as "random" as they should be (much like with RC4 where it is
recommended to run the algorithm a few cycles first before using its
output to eliminate the highly coorelated bytes that occur first.
This is because your KSA shuffle routine is not a good shuffle (it is
not Fisher-Yates, so it exhibits terrible bias).
Results from an analysis of running 256 sequential keys through PIA/KSA
together are below (shortened to fit here on Usenet, run the code to
generate the full table, and pipe the output into "less -S"):
Histogram of SBox[] after KSA for key[3] from 0 to 0xff:
SBox[i]:
0 1 2 3 4 5 6 7 8 9 10 11 12
Val: =============================================================
15: 0 0 0 2 0 0 0 0 0 0 1 1 91
49: 104 0 0 0 0 0 0 0 0 0 0 0 0
4d: 0 0 104 0 0 0 0 1 0 0 0 0 0
71: 0 0 0 2 0 0 0 0 0 0 95 0 0
78: 0 110 0 0 0 0 0 1 0 0 0 0 0
98: 0 0 0 0 0 102 0 0 0 0 0 0 0
c3: 0 0 0 2 0 0 0 0 0 99 0 0 0
f6: 0 0 0 1 104 0 0 0 0 0 0 0 0
fc: 0 0 0 0 0 0 93 0 0 0 0 0 0
fe: 0 0 0 0 0 0 0 0 100 0 0 1 0
What this table means is that for the code below, when performing 256
PIA/KSA initializations, for byte 0 of SBox[], the byte value 0x49
appeared in 104 out of the 256 tests.
For byte 1 of the SBox[], the value 78 appeared in that position for
110 of the tests.
For SBox[12], byte value 0x15 appeared in this position in 91 of the
tests.
And so forth.
Here is the C code that generates the full table (note, very wide, use
less -S to view the output in a tabular form):
===cut===
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
/* The code below for SBox8_PIA was copied from
* http://www.freecx.co.uk/crypto/SBox8/Definition_SBox8.php. See that
* page for licensing information */
/* It has been modified to compute a histogram of byte values in the SBox[]
* array after the KSA has been run */
#define swap(X,Y) { uint8_t T = X; X = Y; Y = T; }
static uint8_t a, b, c, d, j;
static uint8_t SBox[256];
void SBox8_PIA(uint32_t seed) {
if (seed == 0) {
a = 14;
b = 59;
c = 23;
d = 77;
} else {
a = ( seed & 0xff);
b = ((seed >> 8) & 0xff);
c = ((seed >> 16) & 0xff);
d = ((seed >> 24) & 0xff);
}
// Shifting to the next odd Value of each Variable
// in Order to generate an alternating Permutation
uint8_t t = ((b ^ c) + d);
t |= 1;
// Initialise the alternating Permutation
// into the internal State Array
for (int i=0; i<256; i++) {
a += t;
SBox[i] = a;
}
}
void SBox8_KSA(uint8_t key[], uint8_t keyLen) {
// Shuffle the Key into the Permutation
// of the internal State Array
for (int i=0; i<256; i++) {
d = i % keyLen;
a += SBox[b];
b += SBox[a];
c = a + b + i + key[d];
swap(SBox[c], SBox[i]);
}
// a,b and c are not explicitly set to zero
// but keep on carrying over their values
j=0;
}
/* Test harness code below */
int main(int argc, char ** argv) {
/* 75, 124, 88 were picked at random */
uint8_t key[4] = {75, 124, 88, 0};
unsigned int sbox_histogram[256][256];
memset(&sbox_histogram, 0, sizeof(int)*256*256);
for (int i=0; i<256; i++) {
SBox8_PIA(0x000000ff);
key[3] = i & 0xff;
SBox8_KSA(key, 4);
for (int idx=0; idx<256; idx++) {
sbox_histogram[idx][SBox[idx]]++;
}
}
printf("Histogram of SBox[] after KSA for key[2-3] from 0 to 0xff:\n");
printf(" SBox[i]:\n ");
for (int i=0; i<256; i++) {
printf("%5d", i);
}
printf("\nVal: ");
for (int i=0; i<256; i++) {
printf("=====");
}
printf("\n");
for (int byte=0; byte<256; byte++) {
printf("%02x: ", byte);
for (int idx=0; idx<256; idx++) {
printf("%4d ", sbox_histogram[idx][byte]);
}
printf("\n");
}
}
===cut===
Apply the following patch to the C code above to run the PIA/KSA for
2^24 sequential key values:
===cut===
--- sbox8.testksa1.c 2016-05-09 07:45:15.512395374 -0400
+++ sbox8.testksa2.c 2016-05-09 07:38:36.250435024 -0400
@@ -67,34 +67,40 @@
int main(int argc, char ** argv) {
/* 75, 124, 88 were picked at random */
- uint8_t key[4] = {75, 124, 88, 0};
+ uint8_t key[4] = {75, 0, 0, 0};
unsigned int sbox_histogram[256][256];
memset(&sbox_histogram, 0, sizeof(int)*256*256);
- for (int i=0; i<256; i++) {
- SBox8_PIA(0x000000ff);
- key[3] = i & 0xff;
- SBox8_KSA(key, 4);
- for (int idx=0; idx<256; idx++) {
- sbox_histogram[idx][SBox[idx]]++;
- }
+ for (int y=0; y<256; y++) {
+ key[1] = y & 0xff;
+ for (int x=0; x<256; x++) {
+ key[2] = x & 0xff;
+ for (int i=0; i<256; i++) {
+ SBox8_PIA(0x000000ff);
+ key[3] = i & 0xff;
+ SBox8_KSA(key, 4);
+ for (int idx=0; idx<256; idx++) {
+ sbox_histogram[idx][SBox[idx]]++;
+ }
+ }
+ }
}
- printf("Histogram of SBox[] after KSA for key[2-3] from 0 to 0xff:\n");
- printf(" SBox[i]:\n ");
+ printf("Histogram of SBox[] after KSA for key[2-3] from 0x0 to 0xffff:\n");
+ printf(" SBox[i]:\n ");
for (int i=0; i<256; i++) {
- printf("%5d", i);
+ printf("%7d ", i);
}
- printf("\nVal: ");
+ printf("\nVal: ");
for (int i=0; i<256; i++) {
- printf("=====");
+ printf("=======");
}
printf("\n");
for (int byte=0; byte<256; byte++) {
printf("%02x: ", byte);
for (int idx=0; idx<256; idx++) {
- printf("%4d ", sbox_histogram[idx][byte]);
+ printf("%7d ", sbox_histogram[idx][byte]);
}
printf("\n");
}
===cut===
And this result will appear (after abount a minute of runtime on my
machine, significantly trimmed here for Usenet):
Histogram of SBox[] after KSA for key[2-3] from 0x0 to 0xffff:
SBox[i]:
0 1 2 3 4 5 6 7
Val: ===============================================================
49: 6326448 25595 24779 25206 0 25481 24735 2973
f6: 1164 26074 26103 26952 5982575 26428 26467 26654
I left only the two worst items in the list. Byte value 49 appears in
position SBox[0] six million times out of the 2^24 trials (37.71% of
the trials), and oddly, never appears in position SBox[4].
Byte value f6 only appears 1,164 times in position [0], but appears
almost six million times in position [4] (35.66% of the trials).
Viewing the full table from running the code (use less -S to view) will
show a large bias for many byte values (not all are in the millions,
many are six digits instead of five digits). But this bias in the
initial KSA scramble likely leads to a situation where some number of
the first bytes of your output keystream are not as random as they
should be, at least until the additional mixing the keystream generator
performs takes effect and undoes the bias from the KSA.
So your design appears to suffer from the same issue that RC4 suffers
from, the start of the keystream is weaker than later portions of the
keystream.