fcrackzip/cpmask.c

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

/* CP mask code */

/* The original CP code was written by Hirotsuna Mizuno and is
 * Copyright (c) 1998 Hirotsuna Mizuno <s1041150@u-aizu.ac.jp>
 *
 * I heavily modified his code.
 * as for speed, this algorithm could be improved without end,
 * and alternative algorithms might exist that might be several orders
 * of magnitude faster.
 */

/* this is faster */
typedef unsigned int UI;

static UI image_width;
static UI image_height;
static u8 *image_data;
static UI transform_width;
static UI transform_height;
static u8 *transform_data;

typedef struct
  {
    UI dst_x, dst_y;
    int mirror;
  }
cp_cell;

static UI cp_cells;
static cp_cell *cp_trans;
static int *cp_table;
static UI cp_width;
static UI cp_height;


#define CP_CODE_MAX_LENGTH      16
#define CP_CELL_SIZE            8
#define CP_BPP                  3
#define OFFSET_X                0
#define OFFSET_Y                0

/* the maximum size of the transformed image in cells */
#define MAX_SIZE                4

#define MAX_CP_WIDTH            2048

#define src_pixel(x,y,c) image_data     [((y)*image_width    +(x)) * CP_BPP + (c)]
#define dst_pixel(x,y,c) transform_data [((y)*transform_width+(x)) * CP_BPP + (c)]

static void
load_img (const char *name)
{
  FILE *img;
  UI image_depth;

  if (image_data)
    fprintf (stderr, "cannot load more than one image\n");
  else
    {
      img = fopen (name, "rb");
      if (img)
        {
          if (fscanf (img, "P6 ") == EOF)
            perror ("no BINARY PPM header detected");
          else
            {
              fscanf (img, "#%*[^\012\015] ");  /* comment */
              if (fscanf (img, "%u ", &image_width) != 1)
                fprintf (stderr, "unable to read image width\n");
              else
                {
                  fscanf (img, "#%*[^\012\015] ");      /* comment */
                  if (fscanf (img, "%u ", &image_height) != 1)
                    fprintf (stderr, "unable to read image height\n");
                  else
                    {
                      fscanf (img, "#%*[^\012\015] ");  /* comment */
                      if (fscanf (img, "%u%*[ \012\015] ", &image_depth) != 1)
                        fprintf (stderr, "unable to read image depth\n");
                      else
                        {
                          if (image_depth != 255)
                            fprintf (stderr, "pixel maxval %d (!= 255) is not supported\n", image_depth);
                          else
                            {
                              image_data = (u8 *) malloc (image_width * image_height * CP_BPP);
                              if (!image_data)
                                fprintf (stderr, "unable to allocate memory for image\n");
                              else
                                {
                                  if (fread (image_data, image_width * image_height * CP_BPP, 1, img) != 1)
                                    fprintf (stderr, "unable to read image data\n");
                                  else
                                    {
                                      /*fprintf (stderr, "read image %dx%d, %d\n", image_width, image_height, image_depth); */
                                      file_path[file_count++] = name;
                                    }
                                }
                            }
                        }
                    }
                }
              fclose (img);
            }
        }
    }
}

/* if you are interested, the following code can detect hidden passwords
 * stored in CP-masked-JPEG files.
 */

/*
 * sorry, the detect code was removed ;)
 */

/*----------------------------------------------------------------------------*/

static u8 cp_key[] =
{
0x10, 0x17, 0x13, 0x15, 0x09, 0x08, 0x0a, 0x14, 0x06, 0x05, 0x16, 0x02, 0x0d,
0x03, 0x01, 0x04, 0x19, 0x0c, 0x0f, 0x0e, 0x12, 0x07, 0x0b, 0x18, 0x11, 0x1a
};

static cp_table_lu1[MAX_CP_WIDTH];
static cp_table_lu2[MAX_CP_WIDTH];

/* this is a bottleneck */
static void
cp_set_pw (u8 * pw, u8 * pw_end)
{
  u8 *cursor;
  int i, j, x, y, len;
  int *table;
  cp_cell *trans;

  len = pw_end - pw;

  for (i = x = y = 0, table = cp_table, trans = cp_trans;
       i < cp_cells;
       i++)
    {
      *table++ = -1;
      trans->dst_x = x;
      trans->dst_y = y;
      trans->mirror = 0;
      trans++;

      if (++x == cp_width)
        {
          x = 0;
          y++;
        }
    }

  x = cp_cells - 1;
  y = len + cp_cells % len;

  for (i = 0, cursor = pw; i < cp_cells; i++)
    {
      x = cp_key[*cursor - 'A'] + x + y;

      if (++cursor == pw_end)
        cursor = pw;

      if (x >= cp_cells)
        x -= cp_cells;

      if (x >= cp_cells)
        x -= cp_cells;

      while (cp_table[x] != -1)
        {
          ++x;
          if (x >= cp_cells)
            x = 0;
        }

      cp_table[x] = i;
      y++;

      if (++i >= cp_cells)
        break;

      x = cp_key[*cursor - 'A'] + x + y;

      if (++cursor == pw_end)
        cursor = pw;

      if (x >= cp_cells)
        x -= cp_cells;

      if (x >= cp_cells)
        x -= cp_cells;

      while (cp_table[x] != -1)
        {
          if (x == 0)
            x = cp_cells;

          x--;
        }

      cp_table[x] = i;
      y++;
    }

  for (i = 0, j = cp_cells - 1; i < j; i++, j--)
    {
      cp_trans[cp_table[i]].dst_x = cp_table_lu1[j];
      cp_trans[cp_table[i]].dst_y = cp_table_lu2[j];
      cp_trans[cp_table[j]].dst_x = cp_table_lu1[i];
      cp_trans[cp_table[j]].dst_y = cp_table_lu2[i];

      if ((cp_table[i] ^ cp_table[j]) & 1)
        {
          cp_trans[cp_table[i]].mirror = 1;
          cp_trans[cp_table[j]].mirror = 1;
        }
    }
}

/*----------------------------------------------------------------------------*/

static void
cp_do_mask (void)
{
  UI x, y, src_x, src_y;
  UI u, v, dst_x, dst_y;
  UI xx;
  int rot;
  cp_cell *cell = cp_trans;

  for (y = 0; y < cp_height; ++y)
    {
      for (x = 0; x < cp_width; ++x)
        {
          {
            u = cell->dst_x;
            v = cell->dst_y;
            rot = cell->mirror;
            cell++;
            dst_x = x * CP_CELL_SIZE + OFFSET_X;
            dst_y = y * CP_CELL_SIZE + OFFSET_Y;
            src_x = u * CP_CELL_SIZE + OFFSET_X;
            src_y = v * CP_CELL_SIZE + OFFSET_Y;
          }

#define   COPY(sx,sy,dx,dy) do { \
            u8 *s = &src_pixel (src_x + (sx), src_y + (sy), 0); \
            u8 *d = &dst_pixel (dst_x + (dx), dst_y + (dy), 0); \
            *d++ = *s++;        \
            *d++ = *s++;        \
            *d++ = *s++;        \
          } while(0)

          if (dst_x + CP_CELL_SIZE <= transform_width &&
              dst_y + CP_CELL_SIZE <= transform_height)
            {
              if (rot)
                {
                  /* this is shit */
                  for (xx = CP_CELL_SIZE - 1; xx--;)
                    {
                      COPY (xx + 1, 0, 0, xx + 1);
                      COPY (0, xx, xx, 0);
                      COPY (xx, CP_CELL_SIZE - 1, CP_CELL_SIZE - 1, xx);
                      COPY (CP_CELL_SIZE - 1, xx + 1, xx + 1, CP_CELL_SIZE - 1);
                    }
                }
              else
                {
                  for (xx = CP_CELL_SIZE; xx--;)
                    {
                      COPY (xx + 1, 0, xx + 1, 0);
                      COPY (0, xx, 0, xx);
                      COPY (xx, CP_CELL_SIZE - 1, xx, CP_CELL_SIZE - 1);
                      COPY (CP_CELL_SIZE - 1, xx + 1, CP_CELL_SIZE - 1, xx + 1);
                    }
                }
            }

#undef COPY
        }
    }
//  {FILE *f=fopen("x.ppm","wb"); fprintf (f,"P6 %d %d %d ",transform_width,transform_height,255); fwrite(transform_data,transform_width*transform_height*CP_BPP,1,f); fclose(f); }
}

static void
cp_cleanup (void)
{
  if (cp_table)
    free (cp_table);

  if (cp_trans)
    free (cp_trans);
}

static void
init_cpmask (void)
{
  UI i;

  assert (image_data);
  cp_width = image_width / CP_CELL_SIZE;
  cp_height = image_height / CP_CELL_SIZE;
  cp_cells = cp_width * cp_height;
  cp_table = (int *) malloc (sizeof (int) * cp_cells);
  cp_trans = (cp_cell *) malloc (sizeof (cp_cell) * cp_cells);

  if (cp_width > MAX_CP_WIDTH)
    {
      printf ("maximum image width in this version is %d\n", MAX_CP_WIDTH * CP_CELL_SIZE);
      exit (1);
    }

  for (i = 0; i < MAX_CP_WIDTH; i++)
    {
      cp_table_lu1[i] = i % cp_width;
      cp_table_lu2[i] = i / cp_width;
    }

  transform_width = image_width < CP_CELL_SIZE * MAX_SIZE ? image_width : CP_CELL_SIZE * MAX_SIZE;
  transform_height = image_height < CP_CELL_SIZE * MAX_SIZE ? image_height : CP_CELL_SIZE * MAX_SIZE;

  transform_data = (u8 *) malloc (transform_width * transform_height * CP_BPP);
}

static int
crack_cpmask (gen_func genfunc, callback_func cbfunc)
{
  unsigned long minimum = 1 << 31;
  unsigned long current;
  int changed = -1;
  int x, y;

  do
    {
      if (changed >= 4 && verbosity)
        printf ("checking pw %s\r", pw), fflush (stdout);

      if (changed < 0)
        pw_end = pw + strlen (pw);

      cp_set_pw (pw, pw_end);
      cp_do_mask ();

#define P(x,y,c) (UI)dst_pixel((x),(y),(c))
      current = 0;

      for (x = CP_CELL_SIZE; x < transform_width; x += CP_CELL_SIZE)
        for (y = transform_height; y--;)
          {
            current += abs (P (x - 1, y, 0) - P (x, y, 0));
            current += abs (P (x - 1, y, 1) - P (x, y, 1));
            current += abs (P (x - 1, y, 2) - P (x, y, 2));

            if (current > minimum)
              goto overflow;
          }

      for (y = CP_CELL_SIZE; y < transform_height && current < minimum; y += CP_CELL_SIZE)
        for (x = transform_width; x-- && current < minimum;)
          {
            current += abs (P (x, y - 1, 0) - P (x, y, 0));
            current += abs (P (x, y - 1, 1) - P (x, y, 1));
            current += abs (P (x, y - 1, 2) - P (x, y, 2));

            if (current > minimum)
              goto overflow;
          }
#undef P

overflow:
      if (current < minimum)
        {
          char info[80];

          minimum = current + 99;

          sprintf (info, "badness %ld", current);

          if ((changed = cbfunc (pw, info)))
            return changed;
        }

    }
  while ((changed = genfunc ()));

  return 0;
}
Revision:	1.1
Committed:	Mon Aug 4 07:09:50 2008 UTC (15 years, 9 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	initial check-in, also 1.0 check-in
#	User	Rev	Content
1	root	1.1	#include <stdio.h>
2			#include <stdlib.h>
3			#include <assert.h>
4
5			/* CP mask code */
6
7			/* The original CP code was written by Hirotsuna Mizuno and is
8			* Copyright (c) 1998 Hirotsuna Mizuno <s1041150@u-aizu.ac.jp>
9			*
10			* I heavily modified his code.
11			* as for speed, this algorithm could be improved without end,
12			* and alternative algorithms might exist that might be several orders
13			* of magnitude faster.
14			*/
15
16			/* this is faster */
17			typedef unsigned int UI;
18
19			static UI image_width;
20			static UI image_height;
21			static u8 *image_data;
22			static UI transform_width;
23			static UI transform_height;
24			static u8 *transform_data;
25
26			typedef struct
27			{
28			UI dst_x, dst_y;
29			int mirror;
30			}
31			cp_cell;
32
33			static UI cp_cells;
34			static cp_cell *cp_trans;
35			static int *cp_table;
36			static UI cp_width;
37			static UI cp_height;
38
39
40			#define CP_CODE_MAX_LENGTH 16
41			#define CP_CELL_SIZE 8
42			#define CP_BPP 3
43			#define OFFSET_X 0
44			#define OFFSET_Y 0
45
46			/* the maximum size of the transformed image in cells */
47			#define MAX_SIZE 4
48
49			#define MAX_CP_WIDTH 2048
50
51			#define src_pixel(x,y,c) image_data [((y)image_width +(x)) CP_BPP + (c)]
52			#define dst_pixel(x,y,c) transform_data [((y)transform_width+(x)) CP_BPP + (c)]
53
54			static void
55			load_img (const char *name)
56			{
57			FILE *img;
58			UI image_depth;
59
60			if (image_data)
61			fprintf (stderr, "cannot load more than one image\n");
62			else
63			{
64			img = fopen (name, "rb");
65			if (img)
66			{
67			if (fscanf (img, "P6 ") == EOF)
68			perror ("no BINARY PPM header detected");
69			else
70			{
71			fscanf (img, "#%[^\012\015] "); / comment */
72			if (fscanf (img, "%u ", &image_width) != 1)
73			fprintf (stderr, "unable to read image width\n");
74			else
75			{
76			fscanf (img, "#%[^\012\015] "); / comment */
77			if (fscanf (img, "%u ", &image_height) != 1)
78			fprintf (stderr, "unable to read image height\n");
79			else
80			{
81			fscanf (img, "#%[^\012\015] "); / comment */
82			if (fscanf (img, "%u%*[ \012\015] ", &image_depth) != 1)
83			fprintf (stderr, "unable to read image depth\n");
84			else
85			{
86			if (image_depth != 255)
87			fprintf (stderr, "pixel maxval %d (!= 255) is not supported\n", image_depth);
88			else
89			{
90			image_data = (u8 ) malloc (image_width image_height * CP_BPP);
91			if (!image_data)
92			fprintf (stderr, "unable to allocate memory for image\n");
93			else
94			{
95			if (fread (image_data, image_width * image_height * CP_BPP, 1, img) != 1)
96			fprintf (stderr, "unable to read image data\n");
97			else
98			{
99			/fprintf (stderr, "read image %dx%d, %d\n", image_width, image_height, image_depth); /
100			file_path[file_count++] = name;
101			}
102			}
103			}
104			}
105			}
106			}
107			fclose (img);
108			}
109			}
110			}
111			}
112
113			/* if you are interested, the following code can detect hidden passwords
114			* stored in CP-masked-JPEG files.
115			*/
116
117			/*
118			* sorry, the detect code was removed ;)
119			*/
120
121			/----------------------------------------------------------------------------/
122
123			static u8 cp_key[] =
124			{
125			0x10, 0x17, 0x13, 0x15, 0x09, 0x08, 0x0a, 0x14, 0x06, 0x05, 0x16, 0x02, 0x0d,
126			0x03, 0x01, 0x04, 0x19, 0x0c, 0x0f, 0x0e, 0x12, 0x07, 0x0b, 0x18, 0x11, 0x1a
127			};
128
129			static cp_table_lu1[MAX_CP_WIDTH];
130			static cp_table_lu2[MAX_CP_WIDTH];
131
132			/* this is a bottleneck */
133			static void
134			cp_set_pw (u8 * pw, u8 * pw_end)
135			{
136			u8 *cursor;
137			int i, j, x, y, len;
138			int *table;
139			cp_cell *trans;
140
141			len = pw_end - pw;
142
143			for (i = x = y = 0, table = cp_table, trans = cp_trans;
144			i < cp_cells;
145			i++)
146			{
147			*table++ = -1;
148			trans->dst_x = x;
149			trans->dst_y = y;
150			trans->mirror = 0;
151			trans++;
152
153			if (++x == cp_width)
154			{
155			x = 0;
156			y++;
157			}
158			}
159
160			x = cp_cells - 1;
161			y = len + cp_cells % len;
162
163			for (i = 0, cursor = pw; i < cp_cells; i++)
164			{
165			x = cp_key[*cursor - 'A'] + x + y;
166
167			if (++cursor == pw_end)
168			cursor = pw;
169
170			if (x >= cp_cells)
171			x -= cp_cells;
172
173			if (x >= cp_cells)
174			x -= cp_cells;
175
176			while (cp_table[x] != -1)
177			{
178			++x;
179			if (x >= cp_cells)
180			x = 0;
181			}
182
183			cp_table[x] = i;
184			y++;
185
186			if (++i >= cp_cells)
187			break;
188
189			x = cp_key[*cursor - 'A'] + x + y;
190
191			if (++cursor == pw_end)
192			cursor = pw;
193
194			if (x >= cp_cells)
195			x -= cp_cells;
196
197			if (x >= cp_cells)
198			x -= cp_cells;
199
200			while (cp_table[x] != -1)
201			{
202			if (x == 0)
203			x = cp_cells;
204
205			x--;
206			}
207
208			cp_table[x] = i;
209			y++;
210			}
211
212			for (i = 0, j = cp_cells - 1; i < j; i++, j--)
213			{
214			cp_trans[cp_table[i]].dst_x = cp_table_lu1[j];
215			cp_trans[cp_table[i]].dst_y = cp_table_lu2[j];
216			cp_trans[cp_table[j]].dst_x = cp_table_lu1[i];
217			cp_trans[cp_table[j]].dst_y = cp_table_lu2[i];
218
219			if ((cp_table[i] ^ cp_table[j]) & 1)
220			{
221			cp_trans[cp_table[i]].mirror = 1;
222			cp_trans[cp_table[j]].mirror = 1;
223			}
224			}
225			}
226
227			/----------------------------------------------------------------------------/
228
229			static void
230			cp_do_mask (void)
231			{
232			UI x, y, src_x, src_y;
233			UI u, v, dst_x, dst_y;
234			UI xx;
235			int rot;
236			cp_cell *cell = cp_trans;
237
238			for (y = 0; y < cp_height; ++y)
239			{
240			for (x = 0; x < cp_width; ++x)
241			{
242			{
243			u = cell->dst_x;
244			v = cell->dst_y;
245			rot = cell->mirror;
246			cell++;
247			dst_x = x * CP_CELL_SIZE + OFFSET_X;
248			dst_y = y * CP_CELL_SIZE + OFFSET_Y;
249			src_x = u * CP_CELL_SIZE + OFFSET_X;
250			src_y = v * CP_CELL_SIZE + OFFSET_Y;
251			}
252
253			#define COPY(sx,sy,dx,dy) do { \
254			u8 *s = &src_pixel (src_x + (sx), src_y + (sy), 0); \
255			u8 *d = &dst_pixel (dst_x + (dx), dst_y + (dy), 0); \
256			d++ = s++; \
257			d++ = s++; \
258			d++ = s++; \
259			} while(0)
260
261			if (dst_x + CP_CELL_SIZE <= transform_width &&
262			dst_y + CP_CELL_SIZE <= transform_height)
263			{
264			if (rot)
265			{
266			/* this is shit */
267			for (xx = CP_CELL_SIZE - 1; xx--;)
268			{
269			COPY (xx + 1, 0, 0, xx + 1);
270			COPY (0, xx, xx, 0);
271			COPY (xx, CP_CELL_SIZE - 1, CP_CELL_SIZE - 1, xx);
272			COPY (CP_CELL_SIZE - 1, xx + 1, xx + 1, CP_CELL_SIZE - 1);
273			}
274			}
275			else
276			{
277			for (xx = CP_CELL_SIZE; xx--;)
278			{
279			COPY (xx + 1, 0, xx + 1, 0);
280			COPY (0, xx, 0, xx);
281			COPY (xx, CP_CELL_SIZE - 1, xx, CP_CELL_SIZE - 1);
282			COPY (CP_CELL_SIZE - 1, xx + 1, CP_CELL_SIZE - 1, xx + 1);
283			}
284			}
285			}
286
287			#undef COPY
288			}
289			}
290			// {FILE f=fopen("x.ppm","wb"); fprintf (f,"P6 %d %d %d ",transform_width,transform_height,255); fwrite(transform_data,transform_widthtransform_height*CP_BPP,1,f); fclose(f); }
291			}
292
293			static void
294			cp_cleanup (void)
295			{
296			if (cp_table)
297			free (cp_table);
298
299			if (cp_trans)
300			free (cp_trans);
301			}
302
303			static void
304			init_cpmask (void)
305			{
306			UI i;
307
308			assert (image_data);
309			cp_width = image_width / CP_CELL_SIZE;
310			cp_height = image_height / CP_CELL_SIZE;
311			cp_cells = cp_width * cp_height;
312			cp_table = (int ) malloc (sizeof (int) cp_cells);
313			cp_trans = (cp_cell ) malloc (sizeof (cp_cell) cp_cells);
314
315			if (cp_width > MAX_CP_WIDTH)
316			{
317			printf ("maximum image width in this version is %d\n", MAX_CP_WIDTH * CP_CELL_SIZE);
318			exit (1);
319			}
320
321			for (i = 0; i < MAX_CP_WIDTH; i++)
322			{
323			cp_table_lu1[i] = i % cp_width;
324			cp_table_lu2[i] = i / cp_width;
325			}
326
327			transform_width = image_width < CP_CELL_SIZE * MAX_SIZE ? image_width : CP_CELL_SIZE * MAX_SIZE;
328			transform_height = image_height < CP_CELL_SIZE * MAX_SIZE ? image_height : CP_CELL_SIZE * MAX_SIZE;
329
330			transform_data = (u8 ) malloc (transform_width transform_height * CP_BPP);
331			}
332
333			static int
334			crack_cpmask (gen_func genfunc, callback_func cbfunc)
335			{
336			unsigned long minimum = 1 << 31;
337			unsigned long current;
338			int changed = -1;
339			int x, y;
340
341			do
342			{
343			if (changed >= 4 && verbosity)
344			printf ("checking pw %s\r", pw), fflush (stdout);
345
346			if (changed < 0)
347			pw_end = pw + strlen (pw);
348
349			cp_set_pw (pw, pw_end);
350			cp_do_mask ();
351
352			#define P(x,y,c) (UI)dst_pixel((x),(y),(c))
353			current = 0;
354
355			for (x = CP_CELL_SIZE; x < transform_width; x += CP_CELL_SIZE)
356			for (y = transform_height; y--;)
357			{
358			current += abs (P (x - 1, y, 0) - P (x, y, 0));
359			current += abs (P (x - 1, y, 1) - P (x, y, 1));
360			current += abs (P (x - 1, y, 2) - P (x, y, 2));
361
362			if (current > minimum)
363			goto overflow;
364			}
365
366			for (y = CP_CELL_SIZE; y < transform_height && current < minimum; y += CP_CELL_SIZE)
367			for (x = transform_width; x-- && current < minimum;)
368			{
369			current += abs (P (x, y - 1, 0) - P (x, y, 0));
370			current += abs (P (x, y - 1, 1) - P (x, y, 1));
371			current += abs (P (x, y - 1, 2) - P (x, y, 2));
372
373			if (current > minimum)
374			goto overflow;
375			}
376			#undef P
377
378			overflow:
379			if (current < minimum)
380			{
381			char info[80];
382
383			minimum = current + 99;
384
385			sprintf (info, "badness %ld", current);
386
387			if ((changed = cbfunc (pw, info)))
388			return changed;
389			}
390
391			}
392			while ((changed = genfunc ()));
393
394			return 0;
395			}