Introduce SSH Fingerprint ASCII Visualization, a technique inspired by the

graphical hash visualization schemes known as "random art", and by
Dan Kaminsky's musings on the subject during a BlackOp talk at the
23C3 in Berlin.

Scientific publication (original paper):
"Hash Visualization: a New Technique to improve Real-World Security",
Perrig A. and Song D., 1999, International Workshop on Cryptographic
Techniques and E-Commerce (CrypTEC '99)
http://sparrow.ece.cmu.edu/~adrian/projects/validation/validation.pdf

The algorithm used here is a worm crawling over a discrete plane,
leaving a trace (augmenting the field) everywhere it goes.
Movement is taken from dgst_raw 2bit-wise.  Bumping into walls
makes the respective movement vector be ignored for this turn,
thus switching to the other color of the chessboard.
Graphs are not unambiguous for now, because circles in graphs can be
walked in either direction.

discussions with several people,
help, corrections and ok markus@ djm@

1 files changed, 104 insertions, 1 deletions

diff --git a/usr.bin/ssh/key.c b/usr.bin/ssh/key.c
index e55955671ef..40fe5b3108b 100644
--- a/usr.bin/ssh/key.c
+++ b/usr.bin/ssh/key.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: key.c,v 1.69 2007/07/12 05:48:05 ray Exp $ */
+/* $OpenBSD: key.c,v 1.70 2008/06/11 21:01:35 grunk Exp $ */
 /*
  * read_bignum():
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -33,6 +33,7 @@
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <sys/param.h>
 #include <sys/types.h>
 
 #include <openssl/evp.h>
@@ -291,6 +292,105 @@ key_fingerprint_bubblebabble(u_char *dgst_raw, u_int dgst_raw_len)
 	return retval;
 }
 
+/*
+ * Draw an ASCII-Art representing the fingerprint so human brain can
+ * profit from its built-in pattern recognition ability.
+ * This technique is called "random art" and can be found in some
+ * scientific publications like this original paper:
+ *
+ * "Hash Visualization: a New Technique to improve Real-World Security",
+ * Perrig A. and Song D., 1999, International Workshop on Cryptographic
+ * Techniques and E-Commerce (CrypTEC '99)
+ * sparrow.ece.cmu.edu/~adrian/projects/validation/validation.pdf
+ *
+ * The subject came up in a talk by Dan Kaminsky, too.
+ *
+ * If you see the picture is different, the key is different.
+ * If the picture looks the same, you still know nothing.
+ *
+ * The algorithm used here is a worm crawling over a discrete plane,
+ * leaving a trace (augmenting the field) everywhere it goes.
+ * Movement is taken from dgst_raw 2bit-wise.  Bumping into walls
+ * makes the respective movement vector be ignored for this turn.
+ * Graphs are not unambiguous, because circles in graphs can be
+ * walked in either direction.
+ */
+#define	FLDSIZE_Y	 8
+#define	FLDSIZE_X	FLDSIZE_Y * 2
+static char *
+key_fingerprint_randomart(u_char *dgst_raw, u_int dgst_raw_len)
+{
+	/*
+	 * Chars to be used after each other every time the worm
+	 * intersects with itself.  Matter of taste.
+	 */
+	char	*augmentation_string = " .o+=*BOX@%&#/^";
+	char	*retval, *p;
+	char	 field[FLDSIZE_X][FLDSIZE_Y];
+	u_int	 i, b;
+	int	 x, y;
+
+	retval = xcalloc(1, (FLDSIZE_X + 3) * (FLDSIZE_Y + 2));
+
+	/* initialize field */
+	memset(field, ' ', FLDSIZE_X * FLDSIZE_Y * sizeof(char));
+	x = FLDSIZE_X / 2;
+	y = FLDSIZE_Y / 2;
+	field[x][y] = '.';
+
+	/* process raw key */
+	for (i = 0; i < dgst_raw_len; i++) {
+		int input;
+		/* each byte conveys four 2-bit move commands */
+		input = dgst_raw[i];
+		for (b = 0; b < 4; b++) {
+			/* evaluate 2 bit, rest is shifted later */
+			x += (input & 0x1) ? 1 : -1;
+			y += (input & 0x2) ? 1 : -1;
+
+			/* assure we are still in bounds */
+			x = MAX(x, 0);
+			y = MAX(y, 0);
+			x = MIN(x, FLDSIZE_X - 1);
+			y = MIN(y, FLDSIZE_Y - 1);
+
+			/* augment the field */
+			p = strchr(augmentation_string, field[x][y]);
+			if (*++p != '\0')
+				field[x][y] = *p;
+
+			input = input >> 2;
+		}
+	}
+
+	/* fill in retval */
+	p = retval;
+
+	/* output upper border */
+	*p++ = '+';
+	for (i = 0; i < FLDSIZE_X; i++)
+		*p++ = '-';
+	*p++ = '+';
+	*p++ = '\n';
+
+	/* output content */
+	for (y = 0; y < FLDSIZE_Y; y++) {
+		*p++ = '|';
+		for (x = 0; x < FLDSIZE_X; x++)
+			*p++ = field[x][y];
+		*p++ = '|';
+		*p++ = '\n';
+	}
+
+	/* output lower border */
+	*p++ = '+';
+	for (i = 0; i < FLDSIZE_X; i++)
+		*p++ = '-';
+	*p++ = '+';
+
+	return retval;
+}
+
 char *
 key_fingerprint(const Key *k, enum fp_type dgst_type, enum fp_rep dgst_rep)
 {
@@ -308,6 +408,9 @@ key_fingerprint(const Key *k, enum fp_type dgst_type, enum fp_rep dgst_rep)
 	case SSH_FP_BUBBLEBABBLE:
 		retval = key_fingerprint_bubblebabble(dgst_raw, dgst_raw_len);
 		break;
+	case SSH_FP_RANDOMART:
+		retval = key_fingerprint_randomart(dgst_raw, dgst_raw_len);
+		break;
 	default:
 		fatal("key_fingerprint_ex: bad digest representation %d",
 		    dgst_rep);