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;
}