Randomart

When using OpenSSH, you may see ASCII art from time to time, like:

+--[ED25519 256]--+
|                 |
|     .           |
|      o          |
|     o o o  .    |
|     .B S oo     |
|     =+^ =...    |
|    oo#o@.o.     |
|    E+.&.=o      |
|    ooo.X=.      |
+----[SHA256]-----+

This is output^[1] of the randomart SSH Key visualization algorithm, intended to leverage the user's visual pattern matching to quickly recognize (or not) a remote host key. It's known as the Drunken Bishop's algorithm, contributed to the OpenSSH codebase by Alexander von Gernler in 2008.

Alexander von Gernler on 2008-06-11:

Introduc[ing] 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)

The implementation is small, and remains relatively unchanged. Its current implementation is in OpenSSH's sshkey.c ^[2]. It works by iterating over the input byte sequence, 2 bits at a time, mapping the 4 possibilities to the diagonals (00: ↖, 01: ↗, 10: ↙, 11: ↘), incrementing the counter in each visited cell, and mapping the counters to output characters. In Gernler's words:

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.

Why?

I became interested in learning more about this algorithm while reading The Chronicles of Osreth. In The Grief of Stones the main character makes a couple of pilgrimages, each of which end with a token to remember it by. I wanted to make a digital token for folks making a digital pilgrimage to this site, and remembered seeing the SSH randomart. So I found the algorithm, implemented it in OCaml for fun, and generated a token, which now lives somewhere on the site 😎.

Other Reading

• What is randomart produced by ssh-keygen?
• What is the randomart image for?
• Drunken Bishop - Re:Factor

OCaml Implementation

For the OCaml implementation, I kept it as imperative as the C implementation, but made it a functor for easy parameterization of "constants".

module type PARAMETERS = sig
  (* Must be odd values so there is a center cell. *)
  val x : int
  val y : int

  (** Characters used to draw the field *)
  val augmentation_string : string
  
  (** Header for the first line, e.g. "RSA 2048". *)
  val header : string
end

module Make (P : PARAMETERS) = struct
  (* Validate parameters when the functor is applied. *)
  let () =
    if P.x mod 2 = 0 || P.y mod 2 = 0 then
      invalid_arg "x and y must be odd";
    if String.length P.augmentation_string < 3 then
      invalid_arg "augmentation_string must be >= 3 chars";

    (* Ensure the header fits within the field's interior
       width. The first line is rendered as:
         '+' <dashes> '[' ^ header ^ ']' <dashes> '+'
       where the interior width (between the two '+') is
       [x]. The bracketed header block has length
       [2 + String.length header], which must therefore be
       ≤ [x]. *)
    let min_header_len = 2 + String.length P.header in
    if min_header_len > P.x then
      invalid_arg
        (Printf.sprintf
          "header too long – needs %d columns but x is %d"
          min_header_len P.x)

  let aug_len = String.length P.augmentation_string - 1

  let clamp v ~min_val ~max_val =
    if v < min_val then min_val else
    if v > max_val then max_val else v

  let fingerprint (dgst_raw : bytes) : string =
    (* Field initialisation *)
    let field = Array.init P.x (fun _ -> Array.make P.y 0) in
    let start_x, start_y = P.x / 2, P.y / 2 in
    let x, y = ref start_x, ref start_y in

    (* Process bytes: each byte encodes 4 2-bit movements. *)
    for i = 0 to Bytes.length dgst_raw - 1 do
      let input = ref (Char.code (Bytes.get dgst_raw i)) in
      for _ = 0 to 3 do
        (* Bit 0 -> X movement, Bit 1 -> Y movement *)
        x := !x + (if (!input land 0x1) <> 0 then 1 else -1);
        y := !y + (if (!input land 0x2) <> 0 then 1 else -1);

        (* Keep coordinates inside the field. *)
        x := clamp !x ~min_val:0 ~max_val:(P.x - 1);
        y := clamp !y ~min_val:0 ~max_val:(P.y - 1);

        (* Augment the field, skip start ('S')/end ('E'). *)
        if field.(!x).(!y) < aug_len - 2 then
          field.(!x).(!y) <- field.(!x).(!y) + 1;

        (* Next 2-bit command. *)
        input := !input lsr 2;
      done
    done;

    (* Mark starting and ending points. *)
    field.(start_x).(start_y) <- aug_len - 1;  (* 'S' *)
    field.(!x).(!y)           <- aug_len;      (* 'E' *)

    (* Build ASCII art in a buffer. *)
    let buf = Buffer.create 128 in

    (* Center [HEADER] within available width. *)
    let head_blk = "[" ^ P.header ^ "]" in
    let head_blk_len = String.length head_blk in
    let lead_dashes = (P.x - head_blk_len) / 2 in
    let trail_dashes = P.x - head_blk_len - lead_dashes in
    Buffer.add_char buf '+';
    Buffer.add_string buf (String.make lead_dashes '-');
    Buffer.add_string buf head_blk;
    Buffer.add_string buf (String.make trail_dashes '-');
    Buffer.add_char buf '+';
    Buffer.add_char buf '\n';

    (* Body rows. *)
    for yy = 0 to P.y - 1 do
      Buffer.add_char buf '|';
      for xx = 0 to P.x - 1 do
        let idx = min field.(xx).(yy) aug_len in
        Buffer.add_char buf P.augmentation_string.[idx]
      done;
      Buffer.add_char buf '|';
      Buffer.add_char buf '\n';
    done;

    (* Bottom border *)
    Buffer.add_char buf '+';
    Buffer.add_string buf (String.make P.x '-');
    Buffer.add_char buf '+';

    Buffer.contents buf
end

(* ------------------------------------------------ *)
(* Default instance with original OpenSSH constants *)
(* ------------------------------------------------ *)

module DefaultParams = struct
  let base = 8
  let y = base + 1     (* 9  *)
  let x = base * 2 + 1 (* 17 *)
  let augmentation_string = " .o+=*BOX@%&#/^SE"
  let header = " RSA 2048"
end

include Make (DefaultParams)