The Drunken Bishop Algorithm

https://www.jfurness.uk/the-drunken-bishop-algorithm/

by palsecam • 5 years ago

168 41 5 years ago

nightpool• 5 years ago

Looks like the formatting on the `pre` elements are slightly broken, this is what I see in Chrome: https://i.postimg.cc/4y8s8YZR/image.png

My guess is that this is because you're using 'white-space: pre-wrap' as well as `width: min-content`—meaning that Chrome is wrapping your lines as much as possible to fit them into as small as a width as possible. You can fix this by overriding the default wordpress 'white-space: pre-wrap' styles with 'white-space: pre'.

A shame, because I enjoyed the article! A very interesting look into a part of the OpenSSH code I've always been curious about

FuncTheory3• 5 years ago

Hi there, author here.

I'll take a look at those `pre` elements this weekend. I had no idea they were broken on chrome. In fact... it looks like they're borked on Firefox as well. Thanks for the heads up on how to fix it, Wordpress seems to have been playing around with my formatting recently (probably my poor newbie practices)!

EDIT: That seems to have fixed it. Thanks for flagging it up, please let me know if it's still broken!

quickthrowman• 5 years ago

Thanks for fixing it!

Luc3• 5 years ago

How the comparison is supposed to be displayed:

  +-----[first]-----+    +-----[second]----+
  |       .=o.  .   |    |        ..=o   . |
  |     . *+*. o    |    |       o 0+.. o  |
  |      =.*..o     |    |        X.o. o   |
  |       o + ..    |    |       . * .  .  |
  |        S o.     |    |        S o  .   |
  |         o  .    |    |         o    .  |
  |          .  . . |    |          .    ..|
  |              o .|    |               .o|
  |               E.|    |               Eo|
  +-----------------+    +-----------------+

That's way too much alike IMHO. A more chaotic algorithm would create images that differ more substantially.

whoomp12342• 5 years ago

it might be, but its much easier to spot a difference for a technical eye.

Luc3• 5 years ago

Ideally you'd want spot a change without comparing them side by side, I think.

reificator• 5 years ago

Interested mobile users: Please rotate your screen to see "How the comparison is supposed to be displayed"

Interested HN mods: Yet another request for horizontally scrolling code blocks instead of line wrapping.

Luc3• 5 years ago

Is this better?

  +-----[first]-----+
  |       .=o.  .   |
  |     . *+*. o    |
  |      =.*..o     |
  |       o + ..    |
  |        S o.     |
  |         o  .    |
  |          .  . . |
  |              o .|
  |               E.|
  +-----------------+
  +-----[second]----+
  |        ..=o   . |
  |       o 0+.. o  |
  |        X.o. o   |
  |       . * .  .  |
  |        S o  .   |
  |         o    .  |
  |          .    ..|
  |               .o|
  |               Eo|
  +-----------------+

syrrim• 5 years ago

yet another request

I believe it used to work this way, but they changed it after people complained. Go figure

olejorgenb3• 5 years ago

A fun trick is to cross the eyes so the differences become obvious - a bit easier with more space between them:

    +---[ 1       ]---+                        +---[       2 ]---+
    |       .=o.  .   |                        |        ..=o   . |
    |     . *+*. o    |                        |       o 0+.. o  |
    |      =.*..o     |                        |        X.o. o   |
    |       o + ..    |                        |       . * .  .  |
    |        S o.     |                        |        S o  .   |
    |         o  .    |                        |         o    .  |
    |          .  . . |                        |          .    ..|
    |              o .|                        |               .o|
    |               E.|                        |               Eo|
    +-----------------+                        +-----------------+

jfrunyon2• 5 years ago

The chaotic algorithm is meant to be the hash, not the art-ification. So of course if you take two very similar hashes they will appear very similar.

progbits• 5 years ago

Doing an extra round of hashing wouldn't hurt though, right?

Either the hashes are very different and you can already tell from them (but the art will also be different) or they are very similar (someone trying to sneak a close-enough hash by you) and then the second round of hashing leads to very different art.

olejorgenb3• 5 years ago

If the goal is to make it easy to see if two strings are equal, why not display a cryptographic hash of them instead? There is of course a very small chance of collision, but ignoring that? Does the drunken bishop produce unique images given the dimensions and input sequence length used?

fogof• 5 years ago

I think the idea is that when a human checks to see if two hashes are equal, they usually just check the first few bytes, and maybe the last few bytes. You could attack this by grinding out hashes to find two with the same first few bytes.

Of course, you could do something similar with this visual algorithm, but I guess the idea is you are using more of the human visual system so it's harder.

olejorgenb3• 5 years ago

In that case we can hash the hash :D + some random number I guess, otherwise it doesn't help much.

jfrunyon2• 5 years ago

This is, effectively, displaying a cryptographic hash. But hashes are long and filled with lots of the same thing, so some software [also] turns them into other things, like "random art" or using a word list to turn a hash into a "sentence".

memco• 5 years ago

This is answered in the article:

As an example let’s compare two hexes:
fc94b0c1e5b0987c5843997697ee9fb7
and
fc94b0c1e5b0937c5843997697ee9fb7
are they the same? Let’s use the random art to find out.

Sometimes hashes are visually similar and people aren't always able to compare so finding a different way to represent them could help ensure accurate comparison.

What would be interesting though is if you simply chunk the hash into smaller pieces would it be easier to compare?

fc94 b0c1 e5b0 987c 5843 9976 97ee 9fb7
fc94 b0c1 e5b0 937c 5843 9976 97ee 9fb7

I'm sure it depends a lot on the size. If it's a longer string the grid becomes easier, but for shorter strings the chunks would probably suffice.

jedimastert• 5 years ago

I don't know about you, but it took me a solid 2 minutes to see the difference (even with the chunks), and less than a second to see the other one.

The example given is especially difficult with any sort of dyslexia, which is where an more visual comparison would really shine

pbhjpbhj• 5 years ago

I thought the parent meant, provide two hashes, the hash itself and a hash of the hash (a check-hash, if you will).

fc94b0c1e5b0987c5843997697ee9fb7

5e81

fc94b0c1e5b0937c5843997697ee9fb7

d1da

You can see the difference v. clearly now. (hash used is md2 reduced to first and last 2 digits).

dragontamer2• 5 years ago

This kind of nerd-sniped me.

We already have good compression algorithms that describe images that the human-brain can see, as well as the "portion" of images that the human brain can't tell the difference very easily.

In particular: JPEG compression. Similar pictures with similar information are compressed into the same image. JPEG deletes huge chunks of the image's information, under the assumption that the human eye / brain doesn't seem to tell the difference between them.

Why not do this in reverse: Turn a 128-bit hash into a 128-bit JPEG image through "some manner". Would that work? Maybe a bit of work needs to be done (ensure that colorblind users see the same result... so fully random JPEG images isn't useful).

Maybe monochrome JPEG images? Surely a 32x32 monochrome image (1024 pixels * 8-bit monocrhome == 8192 bits of data) will be sufficient space for 128-bits or 256-bits to "crawl" around?

-----------

Take a very-low quality JPEG compression, but be inspired from the JPEG matrix for discrete cosine transforms for how many "bits" to spend.

It seems like JPEG is a 16x16 macroblock (256 pixels). 4-macroblocks would make a 32x32 image. If we're working with a huge hash (ex: 512-bit SHA3), that's 128-bits of data we'll need to differentiate per 16x16 macroblock.

That seems usable?? Converting the JPEG into ASCII art though would be the hardest part though! But I feel like that part has been solved already by weird Linux programs (play Doom on a Linux console and whatnot)

EDIT: https://github.com/hzeller/timg Seems like modern consoles can view very crude low-resolution images. Something like a 32x32 picture is probably usable on modern consoles.

-------

JPEGs have that whole "discrete fourier cosine transform" thing that grossly complicates the algorithm though. PNGs are simpler: largely run-length encoding based off of zlib compression.

The idea of a "white" block being copied for "0 to 15" pixels (4-bits given to the runlength-encoder, 4-bits selected for the "color") might be an easier "artification" step with more obvious differences in display.

512-bits / 8 (4-bit color + 4-bit runlength) == 64 runs. A 32x32 square has 1024 pixels, so your 64-runs of average length 7.5 will average 480-pixels long (well within the 1024-pixels of a 32x32 square == 1024 pixel square).

mleonhard• 5 years ago

I think the JPEGs could be useful without converting to ASCII art. Could you use JPEG decoding to convert hashes into small and visually-distinct images?

dragontamer2• 5 years ago

The DCT of the JPEG algorithm converts all images into the sum of these 256-distinct images: https://upload.wikimedia.org/wikipedia/commons/2/23/Dctjpeg....

Those 64-images are called the "coefficients of a Discrete Fourier Transform", and the magic of FFT means that all images can be represented by a sum of those 64 images.

The images on the bottom right are "harder" for the eye to recognize, while the images on the top-left are "easier" for the eye to recognize. JPEG standard spends "more bits" on the top left images, and "fewer bits" on the bottom right images.

----------

Our controls are as follows: we can multiply an image with a value (ex: 4-bits give us 0Coefficient(0,0) through 15Coefficient(0,0)). We should give more bits to the ones our eyes can see (ex: more bits to Coefficient(0,0)), while giving fewer bits to the bottom-right coefficients / images (ex: the bottom right checkerboard pattern looks very similar to the checkerboards around it. We probably want to spend 0-bits on that pattern, never to use it at all so that our eyes can distinguish our patterns more)

bluepnume• 5 years ago

If the objective is to get the maximum 'visual' difference for two hashes, why not re-hash both of them first? That results in any small changes causing a huge difference in the final outputs.

rahimnathwani• 5 years ago

The author implemented exactly this. The interactive example at the top of the page has a 'Hash the input?' checkbox.

mmahemoff2• 5 years ago

If the hash is doing its job, two similar inputs should already yield completely different hashes and therefore different visuals.

Each visual is a representation of a single hash. If it was designed to compare two hashes, it could simply show a true/false status because the only purpose is to see if they match.

tene• 5 years ago

Yes, that's correct, but if you get similar visualization for similar hashes, then you've got a much larger target to hit in your search space if you're trying to produce a value whose hash has a visualization that's close enough to pass manual inspection, which would circumvent the purpose of this hash visualization.

selimthegrim• 5 years ago

Furness is a postdoc in my department; glad to see him on here!

holler2• 5 years ago

neat! was thinking how this could be used as a way to handle default avatars for a website by hashing the user name

FuncTheory3• 5 years ago

You absolutely could do that. I think symmetry often looks nice in these things, so you could start to get a bit creative with the algorithm and decide that the first 2 bits denote symmetry like {0: None, 1: Vertical Mirror, 2: Horizontal Mirror, 3: 4-fold rotational}.

There's a whole tonne of procedural generation tricks you could employ to get interesting aesthetics pretty quickly.

holler2• 5 years ago

very cool, I may just try that out for my website, thanks!

dloss• 5 years ago

Well explained. Here‘s a little webapp for easy experimentation with the algorithm: http://sshvis.appspot.com/

publicola1990• 5 years ago

That does seem like an interesting variation in the way the bishop moves in chess board, is there a chess variant which uses this bishop movement scheme?

furyofantares• 5 years ago

Anyone else spot the difference in the hex immediately but have some difficulty with the textual image?

thanksforfish• 5 years ago

Turning off the hashing toggle, I ended up trying to draw some shapes.

    zzzzmmmmaaaa2222

For example is a box. Sort of fun.

withinboredom• 5 years ago

My real name is quite awesome looking and looks like a spaceship.

The Drunken Bishop Algorithm

Related Stories