[HN Gopher] The Drunken Bishop Algorithm
___________________________________________________________________
The Drunken Bishop Algorithm
Author : palsecam
Score : 113 points
Date : 2021-08-05 07:20 UTC (1 days ago)
(HTM) web link (www.jfurness.uk)
(TXT) w3m dump (www.jfurness.uk)
| dragontamer wrote:
| 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).
| [deleted]
| mleonhard wrote:
| 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?
| dragontamer wrote:
| The DCT of the JPEG algorithm converts all images into the
| sum of these 256-distinct images: https://upload.wikimedia.or
| g/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 0 _Coefficient(0,0) through 15_
| Coefficient(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 wrote:
| 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 wrote:
| The author implemented exactly this. The interactive example at
| the top of the page has a 'Hash the input?' checkbox.
| selimthegrim wrote:
| Furness is a postdoc in my department; glad to see him on here!
| [deleted]
| holler wrote:
| neat! was thinking how this could be used as a way to handle
| default avatars for a website by hashing the user name
| FuncTheory wrote:
| 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.
| holler wrote:
| very cool, I may just try that out for my website, thanks!
| Luc wrote:
| 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.
| reificator wrote:
| 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.
| Luc wrote:
| 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 wrote:
| >yet another request
|
| I believe it used to work this way, but they changed it after
| people complained. Go figure
| jfrunyon wrote:
| 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 wrote:
| 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.
| c3534l wrote:
| Doing an extra round of hashing wouldn't do anything. If
| they were different before, now they might be the same. If
| the hashing algorithm is worth its salt (pun intended) then
| the original hash will be just as random as the hash of the
| hash, providing nothing of value.
| [deleted]
| olejorgenb wrote:
| 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|
| +-----------------+ +-----------------+
| whoomp12342 wrote:
| it might be, but its much easier to spot a difference for a
| technical eye.
| Luc wrote:
| Ideally you'd want spot a change without comparing them side
| by side, I think.
| dloss wrote:
| Well explained. Here's a little webapp for easy experimentation
| with the algorithm: http://sshvis.appspot.com/
| olejorgenb wrote:
| 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 wrote:
| 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.
| olejorgenb wrote:
| In that case we can hash the hash :D + some random number I
| guess, otherwise it doesn't help much.
| jfrunyon wrote:
| 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 wrote:
| 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 wrote:
| 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
| FuncTheory wrote:
| I spent quite a bit of time looking for the most devious
| swap I could. I still struggle to see it!
| pbhjpbhj wrote:
| 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).
| nightpool wrote:
| 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
| FuncTheory wrote:
| 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 wrote:
| Thanks for fixing it!
| [deleted]
___________________________________________________________________
(page generated 2021-08-06 23:00 UTC)