Replying to myself again
, but just for fun if we disregard prefix we can fairly easily match 32 bits:
1KbhFQVEUk8wMVtiuBURZAQ1PXnsDUqcag
1EEwcrjaJkWLLZDuZA2Rhob3aVM8NwY5tR
or 40 bits:
1NcE7wksPMcydG7bfsGsGdjf2ckzXSfw1R
1H26EaqCrbdHZk2SvqvZDfPHqYGbYqQsJj
Not going to try for 48 bits on the CPU, but with OpenCL code on a GPU it shouldn't be bad either.
Interesting; I was thinking there probably aren't enough permutations of a default identicon to cover the huge possibility set for Bitcoin addresses, and that pretty much proves it. This sort of attack could be made less likely by modifying the identicon library with some tweaks. Namely, to not allow so many color variations, so an attacker can't just get a purple color close to the other purple (the biggest weakness, I think), but then those bits of the SHA hash have to be re-used as something else.
The default Identicon is a 3x3 grid, but really there's only three different sprites used (corners, edges, and center) and two colors. If you make only the opposing pairs match (top/bottom, left/right, NW/SE, SW/NE, and center), you've got five instead of three, and each pair could have its own color (net gain of 3 colors), without it looking too messy. I need to sit down and figure out how many bits would need to be re-used if the color palette was reduced... I might put my code where my mouth is on this one, since it seems like a fun project to tackle!
