Improving security by drawing identicons for SSH keys

If you're ever had to generate an encryption key pair or log into a machine using an SSH client configured with visual host keys, you've probably stumbled upon some random ASCII art gobbledygook like this:

The key fingerprint is:
28:b5:b9:9b:15:0d:ac:04:d8:fc:18:fd:af:1b:65:fd you@somewhere.com
+-----------------+
|   +..           |
|  . +...         |
|     +o.o        |
|    .o.=.o .     |
|    . = S.+ .    |
|     . . +.  .   |
|      . o.    E  |
|       +..       |
|      o ..       |
+-----------------+

That ASCII art is the 16-byte (128-bit) fingerprint of the host key, represented as a procedurally generated image. An identicon, if you will. It was introduced in OpenSSH 5.1 as a way to help humans recognize strings of random characters in a fast and reliable way. If you were to mistakenly connect to a machine with a different host key, you'd be more likely to recognize (or rather, fail to recognize) an image of the key and realise your mistake.

Oh, and if you're curious, you can add VisualHostKey yes to your ~/.ssh/config file to enable this in your shell when connecting to other hosts.

Of imbibing clerics and purses of coins

Before we delve into the algorithm that draws this ASCII art, let's all sit in a circle while I tell the tale of the Drunken Bishop.

Bishop Peter finds himself in the middle of an ambient atrium. There are walls on all four sides and apparently there is no exit. The floor is paved with square tiles, strictly alternating between black and white. His head heavily aching—probably from too much wine he had before—he starts wandering around randomly. Well, to be exact, he only makes diagonal steps—just like a bishop on a chess board. When he hits a wall, he moves to the side, which takes him from the black tiles to the white tiles (or vice versa). And after each move, he places a coin on the floor, to remember that he has been there before. After 64 steps, just when no coins are left, Peter suddenly wakes up. What a strange dream!

Source: The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm, D. Loss et al.

With that amusing story out of the way, let's analyse how that relates to our little project. With Peter walking around randomly in a room, he leaves behind coins on tiles he has visited. After 64 moves, some tiles will contain no coins, while some will have one or more coins on them. If we represent the grid as a 2D plot of the number of coins in each tile, we get the SSH visual host key!

The grid

We start off by defining the size of the room. Per the algorithm, the room size is a rectangle 17 tiles wide by 9 tiles long.

const WIDTH = 17;
const HEIGHT = 9;

We define the origin to be in the top left corner, numbering the tiles in columns (x) and rows (y), starting at 0:

            1111111
  01234567890123456   
 +-----------------+ x
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
 +-----------------+
 y

We mark the starting position with S = [8, 4].

We'll represent the grid of coin counts as a single-dimensional array that lists the values from left-to-right, top-to-bottom order. That way, if we want to look up a value for a particular position, we can use x and y to calculate the index:

const world = Array(WIDTH * HEIGHT).fill(0);
const coins = world[y * WIDTH + x];

The rules of the game

Since we always want to generate the same walking pattern for our bishop given the same fingerprint, we first have to decide how we're going to turn the fingerprint into a list of commands for the bishop to move. We start by defining the four possible moves the bishop can make:

const MOVES = [
  { x: -1, y: -1 }, // ↖
  { x: 1, y: -1 },  // ↗
  { x: -1, y: 1 },  // ↙
  { x: 1, y: 1 }    // ↘
];

We have now defined four commands associated with the integers 0, 1, 2 and 3. If we create a list of these numbers, we can issue these commands in sequence to move the bishop. To do that, we need to split up the fingerprint into pairs of bits.

Let's start with a single byte. A byte is composed of 8 bits:

a9 = 10 10 10 01 => [01, 10, 10, 10]
     ^  ^  ^  ^      ^   ^   ^   ^
#    4  3  2  1      1   2   3   4

For the purposes of this algorithm, we take the pairs of bits and turn them into an array of integers, from least to most significant (numbered by # in the diagram). To do this, we use a bit of bitwise math.

In case you're unfamiliar with why I chose 3 for the mask: 3 === 0b11 in binary form.

const splitByteIntoCommand = byte => ([
  byte & 3,           //  11   11   11  [11]
  (byte >>> 2) & 3,   //  11   11  [11]  11
  (byte >>> 4) & 3,   //  11  [11]  11   11
  (byte >>> 6) & 3    // [11]  11   11   11
]);

A single byte is represented by two hexadecimal characters, so in order to generate the list of commands from a given host key, we need to split the string into pairs to convert them into a single byte:

const parseCommands = hexString => {
  const commands = [];

  // loop over all the characters in the hex string in steps of 2
  for (let i = 0; i < hexString.length; i += 2) {

    // take a pair of hex characters
    const value = parseInt(hexString.slice(i, i + 2), 16);

    // split the byte into 4 commands and append them to the list
    commands.push(...splitByteIntoCommand(value));
  }

  return commands;
}

We now have a function that can take a host key fingerprint as a 32-character hexadecimal string and convert it to an array of commands.

Making things move

Our bishop now has a world to move in and a list of commands we'd like him to perform. Let's make a function that will take the state of the world, the position of the bishop and a single command to calculate the next state.

// ensures the returned value is always min <= x <= max
const clamp = (min, max, x) =>
  Math.max(min, Math.min(max, x));

const nextPosition = (position, move) => {
  // look up direction to move in the rules lookup
  const delta = MOVES[move];

  // return a new position while ensuring the bishop doesn't stray
  // outside of the room
  return {
    x: clamp(0, WIDTH - 1, position.x + delta.x),
    y: clamp(0, HEIGHT - 1, position.y + delta.y)
  };
};

const step = (world, position, command) => {

  // create a copy of the world state
  const newWorld = Array.from(world);

  // drop a coin in the current position
  newWorld[position.y * WIDTH + position.x] += 1;

  // return the new world state and the next position
  return [newWorld, nextPosition(position, command)];
}

To loop through the list of commands, we'll make another function that will run through the commands, starting with an empty room. This function will just return the state of the world after the given number of steps.

Note: the start and end positions are assigned the values 15 and 16 because we want to be able to see where the bishop started and ended the walk.

const simulate = (commands, steps = commands.length) => {

  // start in the middle of the grid
  const start = { x: 8, y: 4 };

  // set the inital position to the starting position
  let position = start;

  // make the initial world empty
  let world = Array(WIDTH * HEIGHT).fill(0);

  // loop over the requested number of steps
  for (let i = 0; i < steps; i++)

    // calculate the next world state and position
    [world, position] = step(world, position, commands[i]);

  // remember the last position calculated
  const end = position;

  // set the starting position to 15
  world[start.y * WIDTH + start.x] = 15;

  // set the ending position to 16
  world[end.y * WIDTH + end.x] = 16;

  return world;
}

Drawing the grid

So far, we just have a flat array of the number of coins in each tile, but we still have to draw the histogram. The algorithm prescribes the characters that represent the possible values of coins in a tile:

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
   .  o  +  =  *  B  O  X  @  %  &  #  /  ^  S  E

We can encode the table as a single string:

const SYMBOLS = ' .o+=*BOX@%&#/^SE';

To look up the symbol for a particular number of coins, we can just use the index of the string to give us the symbol to use for that count (the symbol for 4 coins is SYMBOLS[4]).

To draw the world, we'll map the integers to the characters in the string above, then draw the grid by splitting the string into equal length of WIDTH.

const draw = (world, width, height, status = '') => {
  // turn coin counts into histogram symbols
  const drawing = world
    .map(cell => SYMBOLS[cell % SYMBOLS.length])
    .join('');

  // draw the top border
  const result = ['+' + '-'.repeat(width) + '+'];

  // loop through each row
  for (let i = 0; i < height; i++)
    result.push('|' + drawing.slice(i * width, (i + 1) * width) + '|');

  // draw the bottom border
  result.push('+' + '-'.repeat(width) + '+');

  // return the lines, joined with a newline
  return result.join('\n'); 
};

Making it interesting

Showing the end result is great, but it would be interesting to see the bishop actually stumble through the room while it's running. Luckily, the simulation lets us specify the number of steps we want the bishop to perform, so we can just draw the state of the world for each step on every animation frame:

const displayDiv = document.getElementById('display');

const run = (commands, steps = 0) => {
  const world = simulate(commands, steps);
  displayDiv.textContent = draw(world, WIDTH, HEIGHT)
    + `\n${steps} steps`;
  if (steps < commands.length)
    requestAnimationFrame(() => run(commands, steps + 1));
};

Put it all together, and we have an amusing toy to play with!