drunken_bishop.c

Go to the documentation of this file.

/* ========================================================================== */
/*! \file
 * \brief Drunken bishop randomart algorithm
 *
 * Copyright (c) 2015-2020 by the developers. See the LICENSE file for details.
 *
 * A description and analysis of this algorithm can be found here:
 * <br>
 * http://dirk-loss.de/sshvis/drunken_bishop.pdf
 *
 * If nothing else is specified, function return zero to indicate success
 * and a negative value to indicate an error.
 */
 
 
/* ========================================================================== */
/* Include headers */
 
#include "posix.h"  /* Include this first because of feature test macros */
 
#include <string.h>
 
#include "digest.h"
#include "encoding.h"
#include "main.h"
 
 
/* ========================================================================== */
/*! \addtogroup DIGEST */
/*! @{ */
 
 
/* ========================================================================== */
/* Constants */
 
/* Message prefix for DIGEST module */
#define MAIN_ERR_PREFIX  "DIGEST: "
 
 
/* ========================================================================== */
/* Create and print randomart image using "drunken bishop" algorithm
 *
 * Every 2 bits of data are translated to a move on the field. The bits are
 * mapped to the moves in pairs with most significant byte first and least
 * significant bit pair (of every byte) first. Example:
 *
 * Data        fc     :      94     :      b0     : ... :      b7
 * Bits   11 11 11 00 : 10 01 01 00 : 10 11 00 00 : ... : 10 11 01 11
 *         |  |  |  |    |  |  |  |    |  |  |  |          |  |  |  |
 * Move    4  3  2  1    8  7  6  5   12 11 10  9   ...   64 63 62 61
 *
 * The field is initialized with SP (whitespace) and every time the bishop moves
 * to a field its value is incremented. The value of a field is printed using
 * the following characters:
 *
 *  1:  .
 *  2:  o
 *  3:  +
 *  4:  =
 *  5:  *
 *  6:  B
 *  7:  O
 *  8:  X
 *  9:  @
 * 10:  %
 * 11:  &
 * 12:  #
 * 13:  /
 * 14:  ^
 *
 * Exceptions: The start field is marked with 'S' and the end field with 'E'.
 */
 
static void  drunken_bishop(const char*  prefix,
                            const unsigned char*  data, size_t  data_len)
{
   const char  trace[] = " .o+=*BOX@%&#/^SE";
   const unsigned int  trace_start = 15U;
   const unsigned int  trace_end = 16U;
   unsigned int  field[DIGEST_RA_X][DIGEST_RA_Y];
   size_t  x = DIGEST_RA_X / (size_t) 2;
   size_t  y = DIGEST_RA_Y / (size_t) 2;
   size_t  x_lim = DIGEST_RA_X - (size_t) 1;
   size_t  y_lim = DIGEST_RA_Y - (size_t) 1;
   size_t  i;
   unsigned int  ii;
   unsigned int  move[4];
 
   /* Initialize field */
   for(i = 0; i < DIGEST_RA_Y; ++i)
   {
      for(ii = 0; (size_t) ii < DIGEST_RA_X; ++ii)  { field[ii][i] = 0; }
   }
   field[x][y] = trace_start;
 
   /* Split data into 2bit groups */
   for(i = 0; i < data_len; ++i)
   {
      for(ii = 0; ii < 4; ++ii)
      {
         /* Extract direction */
         move[ii] = ((unsigned int) data[i] & (3U << ii * 2U)) >> ii * 2U;
 
         /* Move on field */
         switch(move[ii])
         {
            case 0U:
            {
               if(x)  { --x; }
               if(y)  { --y; }
               break;
            }
            case 1U:
            {
               if(x_lim > x)  { ++x; }
               if(y)  { --y; }
               break;
            }
            case 2U:
            {
               if(x)  { --x; }
               if(y_lim > y)  { ++y; }
               break;
            }
            case 3U:
            {
               if(x_lim > x)  { ++x; }
               if(y_lim > y)  { ++y; }
               break;
            }
            default:
            {
               PRINT_ERROR("Bishop was too drunk (bug)");
               break;
            }
         }
 
         /* Update field content */
         if(14U > field[x][y]) { field[x][y] += 1U; }
      }
   }
   field[x][y] = trace_end;
 
   /* Print top line */
   printf("%s+", prefix);
   for(x = 0; x < DIGEST_RA_X; ++x)  { printf("-"); }
   printf("+\n");
   /* Print field */
   for(y = 0; y < DIGEST_RA_Y; ++y)
   {
      printf("%s|", prefix);
      for(x = 0; x < DIGEST_RA_X; ++x)  { printf("%c", trace[field[x][y]]); }
      printf("|\n");
   }
   /* Print bottom line */
   printf("%s+", prefix);
   for(x = 0; x < DIGEST_RA_X; ++x)  { printf("-"); }
   printf("+\n");
 
   return;
}
 
 
/* ========================================================================== */
/*! \brief Create randomart image of a key
 *
 * \param[in]  prefix  Prefix to prepend for each output line
 * \param[in]  buf     Pointer to data buffer
 * \param[in]  len     Length of data in buffer
 *
 * The data from \e buf is hashed with the SHA2-256 algorithm to create a
 * fingerprint. The first 16 bytes of this fingerprint are used to create a
 * randomart image with the drunken bishop algorithm.
 *
 * \return
 * - 0 on success
 * - Negative value on error
 */
 
int  digest_randomart(const char*  prefix, const char*  buf, size_t  len)
{
   int  res = -1;
   unsigned char  md[DIGEST_SHA2_256_LEN];
   const char*  fingerprint = NULL;
 
   /* Calculate SHA2-256 hash of data */
   res = digest_sha2_256(buf, len, md);
   if(!res)
   {
      res = enc_mime_encode_base64(&fingerprint, (const char*) md,
                                   DIGEST_SHA2_256_LEN);
      if(!res)
      {
         printf("%sKey fingerprint is SHA256:%s\n", prefix, fingerprint);
         /*
          * Create randomart
          *
          * Use with 16 bytes of data (resulting in 64 moves of the bishop,
          * matching a 17x9 field size).
          */
         drunken_bishop(prefix, md, 16);
      }
   }
   enc_free((void*) fingerprint);
 
   /* Check for error */
   if(res)  { PRINT_ERROR("Creating randomart image failed"); }
 
   return(res);
}
 
 
/*! @} */
 
/* EOF */