lib/extras/randomart.c

   1 /* $OpenBSD: key.c,v 1.98 2011/10/18 04:58:26 djm Exp $ */
   2 /*
   3  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
   4  * Copyright (c) 2008 Alexander von Gernler.  All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include <gnutls_int.h>
  28 #include <gnutls_errors.h>
  29 #include <randomart.h>
  30
  31 /*
  32  * Draw an ASCII-Art representing the fingerprint so human brain can
  33  * profit from its built-in pattern recognition ability.
  34  * This technique is called "random art" and can be found in some
  35  * scientific publications like this original paper:
  36  *
  37  * "Hash Visualization: a New Technique to improve Real-World Security",
  38  * Perrig A. and Song D., 1999, International Workshop on Cryptographic
  39  * Techniques and E-Commerce (CrypTEC '99)
  40  * sparrow.ece.cmu.edu/~adrian/projects/validation/validation.pdf
  41  *
  42  * The subject came up in a talk by Dan Kaminsky, too.
  43  *
  44  * If you see the picture is different, the key is different.
  45  * If the picture looks the same, you still know nothing.
  46  *
  47  * The algorithm used here is a worm crawling over a discrete plane,
  48  * leaving a trace (augmenting the field) everywhere it goes.
  49  * Movement is taken from dgst_raw 2bit-wise.  Bumping into walls
  50  * makes the respective movement vector be ignored for this turn.
  51  * Graphs are not unambiguous, because circles in graphs can be
  52  * walked in either direction.
  53  */
  54
  55 /*
  56  * Field sizes for the random art.  Have to be odd, so the starting point
  57  * can be in the exact middle of the picture, and FLDBASE should be >=8 .
  58  * Else pictures would be too dense, and drawing the frame would
  59  * fail, too, because the key type would not fit in anymore.
  60  */
  61 #define FLDBASE         8
  62 #define FLDSIZE_Y       (FLDBASE + 1)
  63 #define FLDSIZE_X       (FLDBASE * 2 + 1)
  64 char *
  65 _gnutls_key_fingerprint_randomart (uint8_t * dgst_raw, u_int dgst_raw_len,
  66                                    const char *key_type, unsigned int key_size,
  67                                    const char* prefix)
  68 {
  69   /*
  70    * Chars to be used after each other every time the worm
  71    * intersects with itself.  Matter of taste.
  72    */
  73   const char augmentation_string[] = " .o+=*BOX@%&#/^SE";
  74   char *retval, *p;
  75   uint8_t field[FLDSIZE_X][FLDSIZE_Y];
  76   unsigned int i, b;
  77   int x, y;
  78   const size_t len = sizeof(augmentation_string) - 2;
  79   unsigned int prefix_len = 0;
  80
  81   if (prefix)
  82     prefix_len = strlen(prefix);
  83
  84   retval = gnutls_calloc (1, (FLDSIZE_X + 3 + prefix_len) * (FLDSIZE_Y + 2));
  85   if (retval == NULL)
  86     {
  87       gnutls_assert();
  88       return NULL;
  89     }
  90
  91   /* initialize field */
  92   memset (field, 0, FLDSIZE_X * FLDSIZE_Y * sizeof (char));
  93   x = FLDSIZE_X / 2;
  94   y = FLDSIZE_Y / 2;
  95
  96   /* process raw key */
  97   for (i = 0; i < dgst_raw_len; i++)
  98     {
  99       int input;
 100       /* each byte conveys four 2-bit move commands */
 101       input = dgst_raw[i];
 102       for (b = 0; b < 4; b++)
 103         {
 104           /* evaluate 2 bit, rest is shifted later */
 105           x += (input & 0x1) ? 1 : -1;
 106           y += (input & 0x2) ? 1 : -1;
 107
 108           /* assure we are still in bounds */
 109           x = MAX (x, 0);
 110           y = MAX (y, 0);
 111           x = MIN (x, FLDSIZE_X - 1);
 112           y = MIN (y, FLDSIZE_Y - 1);
 113
 114           /* augment the field */
 115           if (field[x][y] < len - 2)
 116             field[x][y]++;
 117           input = input >> 2;
 118         }
 119     }
 120
 121   /* mark starting point and end point */
 122   field[FLDSIZE_X / 2][FLDSIZE_Y / 2] = len - 1;
 123   field[x][y] = len;
 124
 125   /* fill in retval */
 126   if (prefix_len)
 127     snprintf (retval, FLDSIZE_X + prefix_len, "%s+--[%4s %4u]", prefix, key_type, key_size);
 128   else
 129     snprintf (retval, FLDSIZE_X, "+--[%4s %4u]", key_type, key_size);
 130   p = strchr (retval, '\0');
 131
 132   /* output upper border */
 133   for (i = p - retval - 1; i < FLDSIZE_X + prefix_len; i++)
 134     *p++ = '-';
 135   *p++ = '+';
 136   *p++ = '\n';
 137
 138   if (prefix_len)
 139     {
 140       memcpy(p, prefix, prefix_len);
 141       p += prefix_len;
 142     }
 143
 144   /* output content */
 145   for (y = 0; y < FLDSIZE_Y; y++)
 146     {
 147       *p++ = '|';
 148       for (x = 0; x < FLDSIZE_X; x++)
 149         *p++ = augmentation_string[MIN (field[x][y], len)];
 150       *p++ = '|';
 151       *p++ = '\n';
 152
 153       if (prefix_len)
 154         {
 155           memcpy(p, prefix, prefix_len);
 156           p += prefix_len;
 157         }
 158     }
 159
 160   /* output lower border */
 161   *p++ = '+';
 162   for (i = 0; i < FLDSIZE_X; i++)
 163     *p++ = '-';
 164   *p++ = '+';
 165
 166   return retval;
 167 }