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@

8 files changed, 177 insertions, 23 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);
diff --git a/usr.bin/ssh/key.h b/usr.bin/ssh/key.h
index 6873dd7933e..14aac79c2de 100644
--- a/usr.bin/ssh/key.h
+++ b/usr.bin/ssh/key.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: key.h,v 1.26 2006/08/03 03:34:42 deraadt Exp $ */
+/* $OpenBSD: key.h,v 1.27 2008/06/11 21:01:35 grunk Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -42,7 +42,8 @@ enum fp_type {
 };
 enum fp_rep {
 	SSH_FP_HEX,
-	SSH_FP_BUBBLEBABBLE
+	SSH_FP_BUBBLEBABBLE,
+	SSH_FP_RANDOMART
 };
 
 /* key is stored in external hardware */
diff --git a/usr.bin/ssh/readconf.c b/usr.bin/ssh/readconf.c
index 915d20876d8..af180a16c28 100644
--- a/usr.bin/ssh/readconf.c
+++ b/usr.bin/ssh/readconf.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: readconf.c,v 1.165 2008/01/19 23:09:49 djm Exp $ */
+/* $OpenBSD: readconf.c,v 1.166 2008/06/11 21:01:35 grunk Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -447,7 +447,23 @@ parse_flag:
 
 	case oCheckHostIP:
 		intptr = &options->check_host_ip;
-		goto parse_flag;
+		arg = strdelim(&s);
+		if (!arg || *arg == '\0')
+			fatal("%.200s line %d: Missing CheckHostIP argument.",
+			    filename, linenum);
+		value = 0;	/* To avoid compiler warning... */
+		if (strcmp(arg, "yes") == 0 || strcmp(arg, "true") == 0)
+			value = SSHCTL_CHECKHOSTIP_YES;
+		else if (strcmp(arg, "no") == 0 || strcmp(arg, "false") == 0)
+			value = SSHCTL_CHECKHOSTIP_NO;
+		else if (strcmp(arg, "fingerprint") == 0)
+			value = SSHCTL_CHECKHOSTIP_FPR;
+		else
+			fatal("%.200s line %d: Bad CheckHostIP argument.",
+			    filename, linenum);
+		if (*activep && *intptr == -1)
+			*intptr = value;
+		break;
 
 	case oVerifyHostKeyDNS:
 		intptr = &options->verify_host_key_dns;
diff --git a/usr.bin/ssh/readconf.h b/usr.bin/ssh/readconf.h
index 6257f4b2f52..5c16a0ba6c8 100644
--- a/usr.bin/ssh/readconf.h
+++ b/usr.bin/ssh/readconf.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: readconf.h,v 1.72 2008/01/19 23:09:49 djm Exp $ */
+/* $OpenBSD: readconf.h,v 1.73 2008/06/11 21:01:35 grunk Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -123,6 +123,10 @@ typedef struct {
 
 }       Options;
 
+#define SSHCTL_CHECKHOSTIP_NO	0
+#define SSHCTL_CHECKHOSTIP_YES	1
+#define SSHCTL_CHECKHOSTIP_FPR	2
+
 #define SSHCTL_MASTER_NO	0
 #define SSHCTL_MASTER_YES	1
 #define SSHCTL_MASTER_AUTO	2
diff --git a/usr.bin/ssh/ssh-keygen.1 b/usr.bin/ssh/ssh-keygen.1
index 877935053b8..36249b28879 100644
--- a/usr.bin/ssh/ssh-keygen.1
+++ b/usr.bin/ssh/ssh-keygen.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: ssh-keygen.1,v 1.75 2007/05/31 19:20:16 jmc Exp $
+.\"	$OpenBSD: ssh-keygen.1,v 1.76 2008/06/11 21:01:35 grunk Exp $
 .\"
 .\"  -*- nroff -*-
 .\"
@@ -37,7 +37,7 @@
 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: May 31 2007 $
+.Dd $Mdocdate: June 11 2008 $
 .Dt SSH-KEYGEN 1
 .Os
 .Sh NAME
@@ -257,11 +257,12 @@ RFC 4716 SSH Public Key File Format.
 This option allows importing keys from several commercial
 SSH implementations.
 .It Fl l
-Show fingerprint of specified public key file.
+Show fingerprint and ASCII art representation of specified public key file.
 Private RSA1 keys are also supported.
 For RSA and DSA keys
 .Nm
-tries to find the matching public key file and prints its fingerprint.
+tries to find the matching public key file and prints its fingerprint
+and representation.
 .It Fl M Ar memory
 Specify the amount of memory to use (in megabytes) when generating
 candidate moduli for DH-GEX.
diff --git a/usr.bin/ssh/ssh-keygen.c b/usr.bin/ssh/ssh-keygen.c
index 5fcb13f0c03..42ce538b15f 100644
--- a/usr.bin/ssh/ssh-keygen.c
+++ b/usr.bin/ssh/ssh-keygen.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keygen.c,v 1.166 2008/05/19 15:46:31 djm Exp $ */
+/* $OpenBSD: ssh-keygen.c,v 1.167 2008/06/11 21:01:35 grunk Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1994 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -496,7 +496,7 @@ do_fingerprint(struct passwd *pw)
 {
 	FILE *f;
 	Key *public;
-	char *comment = NULL, *cp, *ep, line[16*1024], *fp;
+	char *comment = NULL, *cp, *ep, line[16*1024], *fp, *ra;
 	int i, skip = 0, num = 0, invalid = 1;
 	enum fp_rep rep;
 	enum fp_type fptype;
@@ -514,9 +514,12 @@ do_fingerprint(struct passwd *pw)
 	public = key_load_public(identity_file, &comment);
 	if (public != NULL) {
 		fp = key_fingerprint(public, fptype, rep);
+		ra = key_fingerprint(public, fptype, rep);
 		printf("%u %s %s\n", key_size(public), fp, comment);
+		verbose("%s\n", ra);
 		key_free(public);
 		xfree(comment);
+		xfree(ra);
 		xfree(fp);
 		exit(0);
 	}
@@ -574,8 +577,11 @@ do_fingerprint(struct passwd *pw)
 			}
 			comment = *cp ? cp : comment;
 			fp = key_fingerprint(public, fptype, rep);
+			ra = key_fingerprint(public, fptype, SSH_FP_RANDOMART);
 			printf("%u %s %s\n", key_size(public), fp,
 			    comment ? comment : "no comment");
+			verbose("%s\n", ra);
+			xfree(ra);
 			xfree(fp);
 			key_free(public);
 			invalid = 0;
@@ -595,12 +601,14 @@ print_host(FILE *f, const char *name, Key *public, int hash)
 	if (print_fingerprint) {
 		enum fp_rep rep;
 		enum fp_type fptype;
-		char *fp;
+		char *fp, *ra;
 
 		fptype = print_bubblebabble ? SSH_FP_SHA1 : SSH_FP_MD5;
 		rep =    print_bubblebabble ? SSH_FP_BUBBLEBABBLE : SSH_FP_HEX;
 		fp = key_fingerprint(public, fptype, rep);
-		printf("%u %s %s\n", key_size(public), fp, name);
+		ra = key_fingerprint(public, fptype, SSH_FP_RANDOMART);
+		printf("%u %s %s\n%s\n", key_size(public), fp, name, ra);
+		xfree(ra);
 		xfree(fp);
 	} else {
 		if (hash && (name = host_hash(name, NULL, 0)) == NULL)
@@ -1438,10 +1446,15 @@ passphrase_again:
 
 	if (!quiet) {
 		char *fp = key_fingerprint(public, SSH_FP_MD5, SSH_FP_HEX);
+		char *ra = key_fingerprint(public, SSH_FP_MD5,
+		    SSH_FP_RANDOMART);
 		printf("Your public key has been saved in %s.\n",
 		    identity_file);
 		printf("The key fingerprint is:\n");
 		printf("%s %s\n", fp, comment);
+		printf("The key's randomart image is:\n");
+		printf("%s\n", ra);
+		xfree(ra);
 		xfree(fp);
 	}
 
diff --git a/usr.bin/ssh/ssh_config.5 b/usr.bin/ssh/ssh_config.5
index d6f3fbf80b8..28ac724c862 100644
--- a/usr.bin/ssh/ssh_config.5
+++ b/usr.bin/ssh/ssh_config.5
@@ -34,8 +34,8 @@
 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.\" $OpenBSD: ssh_config.5,v 1.106 2008/06/10 18:21:24 dtucker Exp $
-.Dd $Mdocdate: June 10 2008 $
+.\" $OpenBSD: ssh_config.5,v 1.107 2008/06/11 21:01:35 grunk Exp $
+.Dd $Mdocdate: June 11 2008 $
 .Dt SSH_CONFIG 5
 .Os
 .Sh NAME
@@ -161,6 +161,10 @@ will additionally check the host IP address in the
 file.
 This allows ssh to detect if a host key changed due to DNS spoofing.
 If the option is set to
+.Dq fingerprint ,
+not only the host IP address will be checked, but also an ASCII art
+representation of the key will be printed.
+If the option is set to
 .Dq no ,
 the check will not be executed.
 The default is
diff --git a/usr.bin/ssh/sshconnect.c b/usr.bin/ssh/sshconnect.c
index 7cd5e28a953..73ab03da31d 100644
--- a/usr.bin/ssh/sshconnect.c
+++ b/usr.bin/ssh/sshconnect.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect.c,v 1.203 2007/12/27 14:22:08 dtucker Exp $ */
+/* $OpenBSD: sshconnect.c,v 1.204 2008/06/11 21:01:35 grunk Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -589,7 +589,7 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 	Key *file_key;
 	const char *type = key_type(host_key);
 	char *ip = NULL, *host = NULL;
-	char hostline[1000], *hostp, *fp;
+	char hostline[1000], *hostp, *fp, *ra;
 	HostStatus host_status;
 	HostStatus ip_status;
 	int r, local = 0, host_ip_differ = 0;
@@ -723,6 +723,13 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 				logit("Warning: Permanently added the %s host "
 				    "key for IP address '%.128s' to the list "
 				    "of known hosts.", type, ip);
+		} else if (options.check_host_ip == SSHCTL_CHECKHOSTIP_FPR) {
+			fp = key_fingerprint(host_key, SSH_FP_MD5, SSH_FP_HEX);
+			ra = key_fingerprint(host_key, SSH_FP_MD5,
+			    SSH_FP_RANDOMART);
+			logit("Host key fingerprint is %s\n%s\n", fp, ra);
+			xfree(ra);
+			xfree(fp);
 		}
 		break;
 	case HOST_NEW:
@@ -758,6 +765,8 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 				snprintf(msg1, sizeof(msg1), ".");
 			/* The default */
 			fp = key_fingerprint(host_key, SSH_FP_MD5, SSH_FP_HEX);
+			ra = key_fingerprint(host_key, SSH_FP_MD5,
+			    SSH_FP_RANDOMART);
 			msg2[0] = '\0';
 			if (options.verify_host_key_dns) {
 				if (matching_host_key_dns)
@@ -772,10 +781,11 @@ check_host_key(char *hostname, struct sockaddr *hostaddr, u_short port,
 			snprintf(msg, sizeof(msg),
 			    "The authenticity of host '%.200s (%s)' can't be "
 			    "established%s\n"
-			    "%s key fingerprint is %s.\n%s"
+			    "%s key fingerprint is %s.\n%s\n%s"
 			    "Are you sure you want to continue connecting "
 			    "(yes/no)? ",
-			    host, ip, msg1, type, fp, msg2);
+			    host, ip, msg1, type, fp, ra, msg2);
+			xfree(ra);
 			xfree(fp);
 			if (!confirm(msg))
 				goto fail;
@@ -1046,18 +1056,20 @@ static int
 show_key_from_file(const char *file, const char *host, int keytype)
 {
 	Key *found;
-	char *fp;
+	char *fp, *ra;
 	int line, ret;
 
 	found = key_new(keytype);
 	if ((ret = lookup_key_in_hostfile_by_type(file, host,
 	    keytype, found, &line))) {
 		fp = key_fingerprint(found, SSH_FP_MD5, SSH_FP_HEX);
+		ra = key_fingerprint(found, SSH_FP_MD5, SSH_FP_RANDOMART);
 		logit("WARNING: %s key found for host %s\n"
 		    "in %s:%d\n"
-		    "%s key fingerprint %s.",
+		    "%s key fingerprint %s.\n%s\n",
 		    key_type(found), host, file, line,
-		    key_type(found), fp);
+		    key_type(found), fp, ra);
+		xfree(ra);
 		xfree(fp);
 	}
 	key_free(found);