// A simple guess-and-determine solution for ZC4 cipher
// Copyright (c) 2008 by Marcos el Ruptor
// Warning! ZC4 is insecure.
// Use it for educational purposes only, as a challenge for students.

// Finds the initial keyed state given a known pt/ct pair with a
// sufficiently long consecutive repetition of some byte in it.
// For the sake of testing, the plaintext is a sequence of 73-byte wide repetitions.
// Only one byte needs to be guessed to recover the whole secret state.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ITEMS			256
#define swap2(a,b)		(t=a,a=b,b=t)
#define u32				unsigned long
static u32				acc,x[ITEMS];

static u32 inv (const u32 n)	{u32 i;for(i=0;i<ITEMS;i++)if(x[i]==n)return i;__asm {int 3};}
static u32 zc4 (const u32 n)	{u32 t;acc=    (acc+      x[n])%ITEMS ;swap2(x[n],x[acc]);return acc=(x[acc]   +x[n])%ITEMS;}
static u32 zc4i(const u32 n)	{u32 t;acc=inv((acc+ITEMS-x[n])%ITEMS);swap2(x[n],x[acc]);return acc=(acc+ITEMS-x[n])%ITEMS;}

static u32		pt[ITEMS*ITEMS], ct[ITEMS*ITEMS];

void main (void)
{
	u32			i, j, k, t, known, start;
	u32			g, d, z[ITEMS];
	
	// generate a random keyed state:
	__asm {rdtsc}; __asm {mov t,eax}; srand (t);
	for (i = 0; i < ITEMS; i++) x[i] = i;
	for (i = 0; i < ITEMS*3; i++) j = rand(), swap2 (x[i%ITEMS], x[j%ITEMS]);
	__asm {rdtsc}; __asm {mov t,eax}; srand (t);
	acc = rand() % ITEMS;
	// debug output
	printf ("%02X:\n", acc); for (i = 0; i < ITEMS; i++) printf ("%02X%s", x[i], (i%32==31)?"\n":" "); printf ("\n");
	// produce the plaintext and the ciphertext:
	for (j = 0; j < ITEMS*ITEMS; j++)
	{
		ct[j] = zc4(pt[j] = (j/73)%ITEMS) ^ pt[j];
	}
	// find the key
	for (start = 1; start < ITEMS*(ITEMS-4); start++)
	{
		// try starting from a few different locations (this can be accelerated significantly of course)
		printf ("%d\r", start);
		for (g = 0; g < ITEMS; g++)
		{
			// guess
			memset (z, -1, sizeof (z));
			z[pt[start-1]] = g;
			known = 1;
			for (j = start; j < ITEMS*(ITEMS-2); j++)
			{
				// determine
				acc = ct[j-1] ^ pt[j-1];
				if (z[pt[j]] >= ITEMS) break;	// guessing another byte here can improve the odds at the cost of performance
				d = ((ct[j] ^ pt[j]) - z[pt[j]]) % ITEMS;
				k = (z[pt[j]] + acc) % ITEMS;
				if (z[k] >= ITEMS) known++;
				z[k] = z[pt[j]];
				z[pt[j]] = d;
				if (known >= ITEMS)
				{
					// check our guess
					acc = ct[j] ^ pt[j]; memcpy (x, z, sizeof (x));
					for (i = 0; (i < ITEMS*2) && (i+j+1 < ITEMS*ITEMS); i++)
					{
						if (zc4(pt[j+i+1]) != (ct[j+i+1] ^ pt[j+i+1])) goto _next; // Damn C won't break out of two loops!
					}
					// rewind
					acc = ct[j] ^ pt[j]; memcpy (x, z, sizeof (x));
					for (i = j; i != -1; i--) zc4i (pt[i]);
					// output the initial keyed state
					printf ("Round %d:\n\n", j);
					printf ("%02X:\n", acc);
					for (i = 0; i < ITEMS; i++) printf ("%02X%s", x[i], (i%32==31)?"\n":" "); printf ("\n");
					return;
				}
			}
		_next:;
		}
	}
}