I am trying to improve attack on PKZIP by minimizing workload and requirements, So PKZIP uses this:
key0[i] = key0[i-1]>>8 ^ crctab[key0[i-1]&0xFF ^ plaintext[i]];
key1[i] = (key1[i-1] + (key0[i]&0xFF))* Const + 1;
key2[i] = key2[i-1]>>8 ^ crctab[key2[i-1]&0xFF ^ (key1[i]>>24)];
to update its keystream or internal state and this:
tmp = (key2[i] |3)&0xFFFF; // notice: makes the last 16 bits of key2 odd
key3[i] = ((tmp*(tmp ^ 1))>>8)&0xFF;//notice: this is ((x**2)-x)//256 mod 256 or (x*(x + or - 1))//256 mod 256
ciphertext[i] = plaintext[i] ^ key3[i];
to derive the byte key3 and encrypt plaintext into ciphertext but programs like pkcrak uses key3[i] and key3[i-1] to derive 2**22 possible key2 values for position i, which is too much, so i discovered this:
Given 3 consecutive plaintext values and ciphertext we can derive 3 consecutive key3 values and each key3 value has 256 possible last 16 bit values, which is too much unless the connection between a 16 bit value for key3[i] and key3[i-1] is found.
Hence:
import math
n= int(65536)
x = 0xc90b #this is key2[i-1] |3
y = 0x2f17# this is key2[i] | 3
a = ((x*x) - x) % n # we havent divided this by 256 for simplicity
b = ((y*y) - y) % n # so the result of a ^ b is 16 bit or simply (e<<8)
e = (a ^ b)&0xFF00
#EQUATION
'''
square root of (((x**2) -x) %n xor (256*e)) == square root of (((y**2) -y) %n)
meaning given key3[i] and key3[i-1] we can get e by key3[i-1] xor key3[i]
And since they are only 64 odd last 16 bit values of key2 for each position
the above equation will get a corresponding odd value for y
'''
i = round(math.sqrt((((x*x) - x) %n ^ e)))
j = round(math.sqrt(((y*y) - y) %n))
print(hex(a))
print(hex(b))
print(hex(e))
print(hex(i))
print(hex(j))
So the above code works perfectly and proves my theory but i need to put it into practical and in C so i did this:
#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define CRCPOLY 0xedb88320
#define CONSTx 0x08088405U /* 134775813 */
#define MSB(x) (((x)>>24)&0xFF)
#define MSBMASK 0xFF000000U
#define CRC32(x,c) (((x)>>8)^crctab[((x)^(c))&0xff])
uint32_t crctab[256];
const uint8_t plain[8]= {
0x64, 0x14, 0x9A, 0xC7, 0xB2, 0x96, 0xC0, 0x15
};
uint8_t cipher[8]= {
};
uint8_t key3[8]= {
};
uint32_t k0 = 0x12345678,t0;
uint32_t k1 = 0x23456789,t1;
uint32_t k2 = 0x34567890,t2;
static void mkCrcTab( ){
unsigned int i, j, c;
for( i = 0; i < 256; i++ )
{
c = i;
for( j = 0; j < 8; j++ )
if( c&1 )
c = (c>>1) ^ CRCPOLY;
else
c = (c>>1);
crctab[i] = c;
}
}
int main(){
mkCrcTab( );
uint8_t pw[10] = {
0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x00
};
uint32_t ky0 = k0; // FNV offset basis for 32-bit
uint32_t ky1 = k1; // FNV prime for 32-bit
uint32_t ky2 = k2;
uint16_t tmp;
uint8_t bt;
for (int i = 0; i < 10; i++) {
ky0 = CRC32( ky0, pw[i] );
ky1 = (k1 + (ky0&0xff))*CONSTx + 1;
ky2 = CRC32( ky2, MSB(ky1) );
printf("%08X %08X %08X\n",ky0,ky1,ky2);
}
t0 =ky0;
t1 = ky1;
t2 = ky2;
printf("===================================\n");
for (int i = 0; i < 8; i++) {
ky0 = CRC32( ky0, plain[i] );
ky1 = (k1 + (ky0&0xff))*CONSTx + 1;
ky2 = CRC32( ky2, MSB(ky1) );
printf("%08X %08X %08X\n",ky0,ky1,ky2);
tmp = ky2 | 3;
bt = ((tmp*(tmp ^ 1))>>8)&0xFF;
cipher[i] = plain[i] ^ bt;
key3[i] = bt;
}
printf("===================================\n");
printf("plain : ");
for(int i =0; i <8; i++){
printf("%02X ",plain[i]);
}
printf("\n");
printf("cipher : ");
for(int i =0; i <8; i++){
printf("%02X ",cipher[i]);
}
printf("\n");
printf("key3 : ");
for(int i =0; i <8; i++){
printf("%02X ",key3[i]);
}
printf("\n");
printf("===================================\n");
return 0;
}
And encrypted an 8 byte plaintext into 8 byte ciphertext using keys derived from a password
1234567890
to test my theory further, But when i used the code below to see if the key2 value i found using the above code for position 4 is inside the list of the ones generated by the algorithm, I don't get it the right value and now i am confused whether it's my coding or the algorithm itself is flawed or misinterpreted.
Here is the code for key2 generation:
#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define CRCPOLY 0xedb88320
#define CONSTx 0x08088405U /* 134775813 */
#define KEY2SPACE (1<<12)
#define KEY3(i) (plain[(i)]^cipher[(i)])
#define MSB(x) (((x)>>24)&0xFF)
#define MAXDELTA (0x00FFFFFFU+0xFFU)
#define MSBMASK 0xFF000000U
#define CRC32(x,c) (((x)>>8)^crctab[((x)^(c))&0xff])
uint32_t crctab[256],crcbymsb[256],crcbylsb[256];
uint32_t *key2i;
uint16_t tmptaba[256],tmptabb[256],tmptabc[256],lkpc[65536],lkpa[65536];
uint8_t idxbylsb[256], idxbymsb[256];
int numKey2s = 0;
const uint8_t plain[8]= {
0x64, 0x14, 0x9A, 0xC7, 0xB2, 0x96, 0xC0, 0x15
};
const uint8_t cipher[8]= {
0xEF, 0x20, 0xDC, 0x4C, 0x11, 0x9A, 0x78, 0xEB
};
static void mkCrcTab( ){
unsigned int i, j, c;
for( i = 0; i < 256; i++ )
{
c = i;
for( j = 0; j < 8; j++ )
if( c&1 )
c = (c>>1) ^ CRCPOLY;
else
c = (c>>1);
crctab[i] = c;
crcbymsb[c>>24] = c;
crcbylsb[c&0xFF] = c;
idxbymsb[c>>24] = i;
idxbylsb[c&0xFF] = i;
}
}
void generate( int n ){
int i,j, d;
uint8_t e, ea;
uint32_t cr[4],cr1[4];
uint16_t ls16a,ls16b,ls16c,eq,eq1;
printf("Generating possible key2_%d values...", n );
ea = KEY3(n-1) ^ KEY3(n);
e = KEY3(n-2) ^ KEY3(n-1);
for( i = 3; i < 256; i+=4 ){
ls16b = tmptabb[i];
eq = (int) sqrt( (double) ((256*ea) ^ (ls16b*(ls16b ^ 1))&0xFFFF));
ls16c = lkpc[eq];
cr[0] = crcbylsb[(ls16b>>8) ^ (ls16c&0xFF)];
cr[1] = crcbylsb[(ls16b>>8) ^ ((ls16c-1)&0xFF)];
cr[2] = crcbylsb[(ls16b>>8) ^ ((ls16c-2)&0xFF)];
cr[3] = crcbylsb[(ls16b>>8) ^ ((ls16c-3)&0xFF)];
eq1 = (int) sqrt( (double) ((256*e) ^ (ls16b*(ls16b ^ 1))&0xFFFF));
ls16a = lkpa[eq1];
cr1[0] = crcbylsb[(ls16a>>8) ^ (ls16b&0xFF)];
cr1[1] = crcbylsb[(ls16a>>8) ^ ((ls16b-1)&0xFF)];
cr1[2] = crcbylsb[(ls16a>>8) ^ ((ls16b-2)&0xFF)];
cr1[3] = crcbylsb[(ls16a>>8) ^ ((ls16b-3)&0xFF)];
for(j=0; j <4; j++){
for(d=0; d < 4; d++){
key2i[numKey2s++] = (((cr1[j]>>8) ^ cr[d])&0xFFFF0000) | (ls16c-d);
}
}
}
printf("done.\nFound %d possible key2-values.\n", numKey2s );
}
int main(){
uint16_t kt,bk,idx;
uint8_t dt;
int x=0, y=0, z=0;
key2i = malloc(KEY2SPACE * sizeof(uint32_t));
if (!key2i) {
perror("Memory allocation failed");
exit(EXIT_FAILURE);
}
//load tmptabb
for(uint16_t i=0; i < 0xFFFF; i++){
kt = i | 3;
dt = ((kt*(kt ^ 1))>>8)&0xFF;
if(dt == KEY3(2)){
tmptabb[y++] = i;
}
if(dt == KEY3(3)){
tmptabc[z++] = i;
}
if(dt == KEY3(1)){
tmptaba[x++] = i;
}
}
//load lookup tables
for(int k =3; k < 256; k+=4){
bk = tmptaba[k];
idx = (int) sqrt( (bk*(bk ^ 1))&0xFFFF);
lkpa[idx] = bk;
bk = tmptabc[k];
idx = (int) sqrt( (bk*(bk ^ 1))&0xFFFF);
lkpc[idx] = bk;
}
mkCrcTab();
generate(3);
for(int w =0; w < numKey2s; w++){
printf("%08X\n", key2i[w]);
}
}
I do not know where i went wrong and now i can not continue with my research of finding the mathematical relationship between key2 and key0 because of this.
Thank you.
The problem isn't the code but the calculation itself as written on paper the algorithm states that you can find a unique y value from x value but that's not entirely correct because given x and the equation ((256*e) = ((x*x)-x) mod 65536) xor ((y*y)-y) mod 65536 ) and e they are 64 possible y values.
That is when the code loads the lookup tables (lkpa,lkpc) for position a and c it overwrites the 63 times ending with last possible value being stored ( in the case of lkpc[] it will be 0xf707).
Simply putting this:
printf("resulted index : %d for 16 bit value %04X\n",idx, bk);
After any of these lines:
idx = (int) sqrt( (bk*(bk ^ 1))&0xFFFF);
would allow you to see that 64 odd 16 bit values result in same index, hence overwriting 63 times.
So putting an algorithm on actual working code is challenging because on paper you can not mostly see other possibilities until you have the code running.