From proff Fri May 17 20:35:25 1996 Received: (proff@localhost) by suburbia.net (8.7.4/Proff-950810) id UAA18685 for best-of-security; Fri, 17 May 1996 20:35:25 +1000 Received: from toad.com (toad.com [140.174.2.1]) by suburbia.net (8.7.4/Proff-950810) with ESMTP id UAA17032 for ; Fri, 17 May 1996 20:09:10 +1000 Received: (from majordom@localhost) by toad.com (8.7.5/8.7.3) id CAA26793 for coderpunks-outgoing; Fri, 17 May 1996 02:04:16 -0700 (PDT) Received: from infinity.c2.org (infinity.c2.org [140.174.185.11]) by toad.com (8.7.5/8.7.3) with ESMTP id CAA26786 for ; Fri, 17 May 1996 02:04:01 -0700 (PDT) Received: (from raph@localhost) by infinity.c2.org (8.7.4/8.6.9) id CAA09153; Fri, 17 May 1996 02:03:52 -0700 (PDT) Community ConneXion: Privacy & Community: Date: Fri, 17 May 1996 02:03:50 -0700 (PDT) From: Raph Levien To: coderpunks@toad.com Subject: Snowflakes as visual hashes Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: proff Precedence: bulk Hi coderpunks, When Ian posted his visprint code a few weeks ago, I suggested snowflakes as a possible alternative. Here's the code. The design was motivated by a number of factors. First and foremost, each hash should correspond to a unique snowflake. If any two snowflakes can be distinguished on careful inspection, then the cryptographic soundness is equivalent to that of the hash. Ian's visprint makes a stronger assumption about the hash, because it is possible to construct two hash values that lead to very similar visprints (for example, any permutation of the equations). Thus, the rest of the design is based on the principle of making it as easy as possible to distinguish any two snowflakes. The most efficient method, from an information theoretic point of view, would be to just lay the bits down on a grid. However, this would just look like random bits to most people. So I added two additional constraints. First, the snowflake has D6 symmetry (the same as real snowflakes). The second constraint is that the snowflake is connected - no isolated black triangles. This encourages the bits to fall into patterns that may be more recognizable to the eye. Use the code the same way as Ian's visprints, i.e. echo string | md5sum | flake | xv - The code has two known problems: first, it's a bit slow (written for simplicity rather than efficiency), and second, it's possible for the rendered snowflake to exceed the square, thus losing bits at the outer edge. It's easy enough to fix both problems, but I figured on keeping things as simple as possible for the first cut. I'm very interested to hear what people think about these snowflakes, and especially how they compare to visprints. The visprints may be more aesthetically pleasing (especially in color ;-), but I think there is a case to be made that snowflakes are more useful in cryptography. Raph /* Snowflake code by Raph Levien Accept a 32 hex digit hash on input, output a PBM of a snowflake unique to that hash value. */ #include #include typedef char color; #define gray 0 #define white 1 #define black 2 /* should probably be an enum, but I can't remember the syntax */ #define maxa 256 #define maxb 128 color flake[maxa][maxb]; #define maxx 512 #define maxy 512 #define s 7.0 #define s34 0.8660254 void printflake (void) { int i, j; int a, b, a1; double c, d; printf ("P1\n%d %d\n", maxx, maxy); for (j = 0; j != maxy; j++) { for (i = 0; i != maxx; i++) { c = (i - (maxx/2)) / (s * s34); d = ((maxy/2) - j) / s; d -= c * 0.5; a = 2 * floor (d); b = floor (c); c = c - floor (c); d = d - floor (d); if (d + c >= 1) a++; /* symmetries here - just like folding paper */ if (b < 0) { a = 1 + a + 2 * b; b = -b - 1; } if (a < 0) if (a & 1) { b += (a+1)/2; a = -1 - a; } else { b += a/2; a = -1 - a; } if (b < 0) { a = 1 + a + 2 * b; b = -b - 1; } if (2 * b > a) if (a & 1) { a1 = a; a = 1 + 2 * b; b = (a1 - 1) / 2; } else { a1 = a; a = 2 * b; b = a1/2; } if (a < 0 || b < 0 || a >= maxa || b >= maxb) printf ("0"); else if (flake[a][b] == black) printf ("1"); else if (flake[a][b] == white) printf ("0"); else printf ("%d", (i ^ j) & 1); } printf ("\n"); } } unsigned char hash[32]; int hashptr; void readhash (void) { int j; fread (hash, 32, 1, stdin); for(j=0;j<32;++j) { unsigned char c = hash[j]; if (c >= '0' && c <= '9') hash[j] = c-'0'; else if (c >= 'a' && c <= 'f') hash[j] = c-('a'-10); else if (c >= 'A' && c <= 'F') hash[j] = c-('A'-10); else hash[j] = 0; } hashptr = 0; } int hasheof (void) { return (hashptr == 128); } int hashbit (void) { int bit; bit = ((hash[hashptr >> 2] & (8 >> (hashptr & 3))) != 0); hashptr++; return bit; } int rn; void seedrand (void) { rn = 0x1234; } int nextrand (void) { rn = ((rn << 1) & 0x7fff | ((rn >> 13) ^ (rn >> 14)) & 1); return rn; } typedef struct coord { int a; int b; } coord; coord frontier[1024]; int frontier_n; void add_to_frontier (int a, int b) { /* Add coord to frontier if not already present. */ int i; for (i = 0; i < frontier_n; i++) if (frontier[i].a == a && frontier[i].b == b) return; frontier[i].a = a; frontier[i].b = b; frontier_n++; } void del_from_frontier (int a, int b) { /* Delete coord from frontier, if present. */ int i; for (i = 0; i < frontier_n; i++) if (frontier[i].a == a && frontier[i].b == b) frontier[i] = frontier[--frontier_n]; } void add_if_gray (int a, int b) { /* Add to frontier, but only if gray and within the 30 degree slice. */ if (a < 0 || b < 0 || 2 * b > a) return; if (flake[a][b] == gray) add_to_frontier (a, b); } void fill (int a, int b, int bit) { /* color a gray pixel, based on the value of the given bit */ del_from_frontier (a, b); if (bit) { flake[a][b] = black; add_if_gray (a + 1, b); add_if_gray (a - 1, b); if (a & 1) add_if_gray (a - 1, b + 1); else add_if_gray (a + 1, b - 1); } else flake[a][b] = white; } int main (int argc, char **argv) { int i, j; int a, b; for (a = 0; a != maxa; a++) for (b = 0; b != maxb; b++) flake[a][b] = gray; flake[0][0] = black; frontier[0].a = 1; frontier[0].b = 0; frontier_n = 1; readhash (); seedrand (); j = 0; while (!hasheof ()) { /* choose a random frontier value */ i = nextrand () % frontier_n; /* fprintf (stderr, "(%d, %d)\n", frontier[i].a, frontier[i].b); */ if (frontier[i].b && ((j < 16) || (j % 3))) fill (frontier[i].a, frontier[i].b, hashbit ()); else fill (frontier[i].a, frontier[i].b, 1); j++; } for (a = 0; a != maxa; a++) for (b = 0; b != maxb; b++) if (flake[a][b] == gray) flake[a][b] = white; #if 0 /* turn on if you want to see the frontier */ for (i = 0; i < frontier_n; i++) flake[frontier[i].a][frontier[i].b] = gray; #endif printflake (); return 0; }