https://www.jfurness.uk/the-drunken-bishop-algorithm/ * Blog * Completed Projects + Probus * Scientific Tools + Hartree-Fock Slater Orbitals for Spherical Atoms + Vibrational Analysis + Energy Level Plotter * Publications Barely Functional Theories Musings on science and game design by James Furness. --------------------------------------------------------------------- The Drunken Bishop Algorithm 28th January 2021 by JFurness --------------------------------------------------------------------- Text to draw: [ ] Board Dimensions: [17 ] [17 ] Hash the input? [*] | Background Color: [#FFFFFF ] Enter some text above to see the ASICII version. --------------------------------------------------------------------- OpenSSH Random Art There's a tradition in my family that everyone takes a turn stirring a secret wish into the yearly christmas pudding. It's important that the wishes remain secret to the wisher or the pudding magics wont work so since moving to America I've implemented a new way of hashing my wish so it can be stirred in via text message without the stirrer knowing the wish. Experts in pudding arcana assure me that pudding magic can reverse any hash function to recover the original wish. Last year I took inspiration from the OpenSSH random art that allows a human to see if two keys are the same more reliably than by comparing simple hex strings. As an example let's compare two hexes: fc94b0c1e5b0987c5843997697ee9fb7 and fc94b0c1e5b0937c5843997697ee9fb7 are they the same? Let's use the random art to find out. +-----[first]-----+ +-----[second]----+ | .=o. . | | ..=o . | | . *+*. o | | o 0+.. o | | =.*..o | | X.o. o | | o + .. | | . * . . | | S o. | | S o . | | o . | | o . | | . . . | | . ..| | o .| | .o| | E.| | Eo| +-----------------+ +-----------------+ Trying to spot the difference in the hex codes is tough but your brain is really good at noticing that the ASCII art are different. I really like the airy feeling of the resulting images, so I thought I'd dig into how they are made. --------------------------------------------------------------------- The Drunken Bishop Algorithm I little online research revealed that OpenSSH uses an algorithm called "The Drunken Bishop" devised by Alexander von Gernler. I then found an excellent analysis and write up by Dirk Loss, Tobias Limmer, and Alexander von Gernler that clearly describes the process and some of its finer features. I expected gnarly cryptography, but to my relief the algorithm is really quite simple and is neatly summarised by a somewhat bizzare short story: 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! Dirk Loss, Tobias Limmer, and Alexander von Gernler - The drunken bishop: An analysis of the OpenSSHfingerprint visualization algorithm To summarise: we create a chess board (17 by 9 for OpenSSH) and place our "Bishop" at the center, marking this as the start. Then we break the input into pairs of bits that define 4 possible moves: {00: up-left (\), 01: up-right (/), 10: down-left(/), 11: down-right (\)} For each pair of bits in the input we move the bishop one space on the board and increment a counter recording how many times we visit each square. Instead of moving off the board at the edges, the bishop slides along the sides as if they were walls. For example, if the bishop is on the right edge of the board and the next move is 01 we simply slide the bishop one space vertically up, incrementing the counter on the new square as normal. Sliding along the walls in this way allows the bishop to change from black to white squares on the chess board. After carrying out all the steps dictated by the input bits we mark down the final position. Finally, the board is drawn simply by assigning a symbol to each position on the board according to how many times it was visited. OpenSSH uses these symbols chosen to reflect "a line of ASCII characters getting thicker": [' ', '.', 'o', '+', '=', '*', 'B', '0', 'X', '@', '%', '&', '#', '/', '^'] The description doesn't define what should be done if a counter is > 13, so I chose to wrap around, this seems unlikely to occur in practice. That's really it for the ASCII. But I couldn't resist getting the HTML out and playing a little more... --------------------------------------------------------------------- Drunken Paintings Rather than draw the board state to a string, there's plenty more we could do with the full vector graphics power of the canvas. I started out by dividing the drawing area to give a distinct position for each square on the bishop's board. The ASCII version works best when the board is wider than it is tall to account for the non-square nature of the monospace font. On the canvas it seems more natural to make a square grid, but there's no requirement to. A larger grid results in longer paths and a more diagonal lattice feel, as this bishop slides onto the other colour squares less frequently. Smaller boards feel busier. A 17 x 17 size seemed to work well. I then decided to quite simply follow the path taken by the bishop drawing a circle at each visited point with a radius equal to the number of times the point was visited. Following the path in the order it was made causes later points to appear on top of earlier points. Filling the circles with a simple colour cycle worked nicely and I was getting a pleasing result in no time. I quickly found that simply pulling the bit pairs directly out of an input string biases towards upward and to the right moves leading to lopsided images. There is a nice connection between the input message and the output image doing this, but the results aren't as visually appealing. Hashing the input with SHA-3 first gives us a fixed length input that nicely explores the full space. I left the option to hash or not open to the user. I'm sure there's lots more could be done with this simple idea. Extending to three dimensions or animating it come to mind. We'll see what comes up before next year's pudding wish needs sending... --------------------------------------------------------------------- 2 comments on "The Drunken Bishop Algorithm" * [5d9bed] Dirk Loss says: 6th August 2021 at 8:55 pm Thank you for mentioning our paper! Here's a little webapp for easy experimentation: http://sshvis.appspot.com/ Dirk Reply + [d6fa9e] JFurness says: 6th August 2021 at 9:03 pm I enjoyed reading it a lot! I hope to one day write an opening to a paper that's as striking as that paper's. Reply --------------------------------------------------------------------- Leave a Reply Cancel reply Your email address will not be published. Required fields are marked * [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment [ ] Name * [ ] Email * [ ] Website [ ] Robot Stopper * four - one = [ ] [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Back to top