Re: Factor

The OpenSSH project is a widely available tool for working with the SSH protocol in a variety of ways on a variety of operating systems. Their project description states:

OpenSSH is the premier connectivity tool for remote login with the SSH protocol. It encrypts all traffic to eliminate eavesdropping, connection hijacking, and other attacks. In addition, OpenSSH provides a large suite of secure tunneling capabilities, several authentication methods, and sophisticated configuration options.

One of the interesting features that it contains is a method of visualizing public key fingerprints to allow a user to more easily see that a key has changed by examining a visual output that looks something like this:

+----[RSA 2048]---+
|        . o.+o  .|
|     . + *  +o...|
|      + * .. ... |
|       o + .   . |
|        S o   .  |
|         o     . |
|          .     o|
|               .o|
|               Eo|
+------[MD5]------+

This is the Drunken Bishop algorithm, a variant of a technique called random art that was originally described in the paper Hash Visualization: a New Technique to improve Real-World Security. You can see more information about it in The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm.

This OpenSSH feature is controlled by the VisualHostKey flag:

VisualHostKey

If this flag is set to yes, an ASCII art representation of the remote host key fingerprint is printed in addition to the fingerprint string at login and for unknown host keys. If this flag is set to no (the default), no fingerprint strings are printed at login and only the fingerprint string will be printed for unknown host keys.

This can be enabled by adding to your ~/.ssh/config:

VisualHostKey yes

Or by adding this option in your ssh command:

$ ssh -o VisualHostKey=yes your.host.name

Implementation

We are going to be implementing this in the Factor programming language.

The algorithm begins by defining a visual board – by default 9 rows by 17 columns – and a starting position in the middle of the board. Each 8-bit byte of input is split into 2-bit groups which indicate where the bishop moves:

As the bishop moves around the board diagonally, it increments a counter in each cell. However, the bishop cannot move through the walls on the edge of the board, remaining stuck in whichever direction is blocked.

CONSTANT: WIDTH 17
CONSTANT: HEIGHT 9

:: drunken-bishop ( bytes -- board )
    HEIGHT [ WIDTH 0 <array> ] replicate :> board
    HEIGHT 2/ :> y!
    WIDTH 2/ :> x!

    15 x y board nth set-nth ! starting position

    bytes [
        { 0 -2 -4 -6 } [
            shift 2 bits {
                { 0b00 [ -1 -1 ] }
                { 0b01 [ -1  1 ] }
                { 0b10 [  1 -1 ] }
                { 0b11 [  1  1 ] }
            } case :> ( dy dx )
            dy y + 0 HEIGHT 1 - clamp y!
            dx x + 0 WIDTH 1 - clamp x!
            x y board nth [ dup 14 < [ 1 + ] when ] change-nth
        ] with each
    ] each

    16 x y board nth set-nth ! ending position

    board ;

The output is rendered using an .o+=*BOX@%&#/^ alphabet with S for the starting position and E for the ending position specially rendered:

CONSTANT: SYMBOLS " .o+=*BOX@%&#/^SE"

: drunken-bishop. ( bytes -- )
    drunken-bishop [ SYMBOLS nths print ] each ;

We can try this out and see that it works:

IN: scratchpad "fc94b0c1e5b0987c5843997697ee9fb7"
               hex-string>bytes drunken-bishop.
       .=o.  .   
     . *+*. o    
      =.*..o     
       o + ..    
        S o.     
         o  .    
          .  . . 
              o .
               E.

This is available in the drunken-bishop vocabulary in a recent development version.