5 ms·
The problem with hash avatars in general is that people want to use them for identity verification -- and humans are wired to do so automatically -- but technol
by nemo1618 5y ago
The problem with hash avatars in general is that people want to use them for identity verification -- and humans are wired to do so automatically -- but technologically, they cannot provide this. The space of possible avatars (2^256, in this case) is far, far larger than the number of distinct objects that humans can distinguish between. Which means that there will invariably be "collisions:" two avatars that are not identical, but appear identical to humans. As a result, if an attacker can brute-force an avatar that looks very similar to, say, Elon Musk's avatar, they can trivially scam people.
It follows that, since avatars do not provide any proof of identity, there is actually no harm in greatly truncating the hash space when generating them! That is, rather than trying to encode all 256 bits into the avatar, you can use a much more manageable number, like 16. But isn't this too small? Won't there be lots of collisions? Yes -- but that's a feature! If collisions are common, then the average user will be aware that avatar != identity, which makes them less susceptible to scamming. But 16 bits is still enough to meet the real goal of avatars: quickly distinguishing between different people in a conversation (or transaction, or whatever).
(This also shows why making avatars more costly to generate, e.g. with scrypt, can do more harm than good: doing so makes collisions less likely, but still not impossible. Meaning that if a collision does occur, whether accidental or malicious, you are less likely to notice it.)
- sva_ 5y ago> The space of possible avatars (2^256, in this case) is far, far larger than the number of distinct objects that humans can distinguish between. That sounds intriguing to me. Are you aware of any research into this?
- nemo1618 5y agoTo be honest, I have no idea how many distinct objects humans can distinguish between, but I am 99% confident that it is fewer than 2^128, much less 2^256. I suppose it's a somewhat nuanced question, though. For example, if I were shown every avatar in sequence, I'm quite sure I would always notice the "diff" between two consecutive avatars. But the bar that I have in mind is much, much higher: given a sequence of avatars, can I recognize my friend's avatar with 100% accuracy? Given that we can't even do this within the set of <8 billion human faces (we occasionally accost a stranger as though they were a friend), I have to conclude that doing so within a set of 2^256 abstract shapes is entirely hopeless.
- dwpdwpdwpdwpdwp 5y agoIt is definitely a nuanced question. The definition of object is surely up for debate as well. A silly example: if one were to define an object as a string of 64 hex characters, even non-literate people could distinguish between any two distinct objects. echo "hello" | sha256sum >> 5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03 echo "world" | sha256sum >> e258d248fda94c63753607f7c4494ee0fcbe92f1a76bfdac795c9d84101eb317 But were I to briefly glance at a computer screen, I'd probably confuse these next two: e258d248fda94c63753607f7c4494ee0fcbe92f1a76bfdac795c9d84101eb317 e258d248fda94c63753607f7c4494ee0fcbe92f1a76bfaac795c9d84101eb317
- sva_ 5y agoYeah, I should've been more clear. There's no doubt that humans can't distinguish/memorize 2^256 abstract shapes. However, only a small subset of those would have to be memorized - those which are relevant to the individual. I'd agree that this particular pattern doesn't have enough variability for each pattern to be unique enough to reliably identify it, but I'd conjecture that its possible to make such a pattern, which has enough variability and unique characteristics to be recognizable (ignoring the fact that an adversary could make a very similar pattern to mislead the individual - I'm not curious about it for verification.) Your example of the fact that we can't reliably recognize every face on this planet is very interesting. Let's imagine we know n faces which I can reliably distinguish from one another, but now there is a (n+1)th face which I mix up with one of the previous ones. Now lets assume this face would instead have a very unique characteristic, unlike all previous faces - lets imagine for example, the nose on this face is upside down. Surely I'd be able to differentiate it from the previous n faces, hence the issue of identifying it might've been the limited variability/characteristics in the various previous instantiations of a face. So there are a number of characteristics in a face, which have a certain degree of variability, which enable us to distinguish from a number of them. I've been pondering on how many of those characteristics could be combined in an object, and how high the variability could be; to create uniquely identifiable patterns. It probably depends a lot on the meaning we attribute to the pattern, different associations we have to it. I apologize - quite the tangent, I guess. I've just been pondering a lot on this for a project I've been working on for some time.
- deleted 5y ago
- HideousKojima 5y agohttps://www.researchgate.net/publication/236023905_Color_difference_Delta_E_-_A_survey https://www.researchgate.net/publication/236023905_Color_dif...
- g_sch 5y agoIt's a simple order of magnitude calculation. 2^256 is greater than one billion to the eighth power, times 100,000. There are probably several possible ways you could estimate how many different objects a person could distinguish between, but I think it's unlikely you'd come up with even a single billion.
- littlestymaar 5y ago> but I think it's unlikely you'd come up with even a single billion. One billion is really really tiny though, let's just play a game : - Unless you're colorblind, you can easily tell ten hues apart. Let's pick two colors, one with a saturated hue, and the other with a pastel one. That's 100 possibilities. - I'm pretty sure you can easily recognize pictures of a hundred people you've met at some point in your life. Let's pick two of them, that's 10 thousand combinations. - can you recognize ten different road signs? Ten country shapes ? Ten animals ? Ten fictional character? Ten books cover? Ten celebrities? Just pick three categories, and you've got a thousand combinations. Now I'm pretty sure you can tell your grandma sitting under a vivid pink UK shape next to your 9th grade math teacher staring at Bruce Willis holding a giant light blue stop sign apart from any other imaginable combinations. An untrained[1] human brain probably cannot distinguish between 2^256 items, but it's still able to do it for massive numbers. [1]: but maybe it's possible with training: for instance, chess professionals might be able to do it.
- FqOD4xih7Uq6m9Z 5y agoThere might not be 2^256 distinguishable objects but maybe someone can come up with 2^16 distinguishable objects and just string 16 of them together. If there is one character off in a string of 40 hexadecimal characters it is hard to notice but that would be easier to detect in a set of 16 symbols.
- ReactiveJelly 5y agoMemorizing order in a set of 16 similar objects is too difficult for me
- FqOD4xih7Uq6m9Z 5y agoI don't think you would need to memorize the order, just compare them side by side to check that they are the same.
- nemo1618 5y agoIf you have the other avatar available for comparison, you don't need to do so visually -- the computer can compare the raw bytes directly.
- adzm 5y agoOn a related note, I've been experimenting with using a simple word list (like the eff diceware list) to generate strings of words encoding data. Trickiest part is figuring out how to encode padding, and the eventual size of the word list, and how complicated the final solution should be (eg using word lists that are not even binary numbers and leftover bits and all that). The diceware word list is nice since the words are not ambiguous and don't have homophones. I assumed there would be existing implementations of something similar but have not found one that fits criteria other than some that use very small word lists. Diceware has 7776 words and pushing that to 8192 should be feasible and is a bit easier to work with.
- shoghicp 5y agoBIP-39, uses 2048 words, and can all be distinguished from each other using the first four characters of each word. This is used to encode raw binary entropy, but adapting it to arbitrary amounts of data is straightforward. For padding I would suggest either pre-encoding length at the start or using classic block cipher padding (https://en.wikipedia.org/wiki/Padding_(cryptography) https://en.wikipedia.org/wiki/Padding_(cryptography) ) See for BIP-39, wordlists under a folder https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0039.mediawi...
- adzm 5y agoThanks for the reference. This is pretty much what I'd be going for!
- themk 5y agoMany years ago i created https://github.com/luke-clifton/memorable-bits https://github.com/luke-clifton/memorable-bits (Also on hackage [0] but readme is missing) It let's you define a pattern for generating "sentences" from data. It deals with padding, lets you join word lists, or use multiple word lists in a single pattern. Word lists can be any power of 2 long, and the library comes with a few different word lists. [0] https://hackage.haskell.org/package/memorable-bits https://hackage.haskell.org/package/memorable-bits
- timClicks 5y agoThere's no need to distinguish between every object at every comparison. In most applications, you'll only be comparing a few dozen avatars with each other.
- nemo1618 5y agoIn the adversarial case, yes, there is. I agree that avatars help you distinguish among ~a dozen users; what they don't do is provide strong guarantees that the person you're talking to actually is who they claim to be.
- timClicks 5y agoThat's probably a good point. Forging an avatar that is visibly close to the target I am pretending to be is challenging-but-doable.
- andromeduck 5y agoYou might get more milage in if the avatars are unique to the user viewing them rather than identical between users. If the nonce/salt used in generation it itself secure then it'd be phrohibity difficult for adversaries to force a collision without obvious detection, doubly so in communities.
- ReactiveJelly 5y ago"This is what it would look like if your randomart avatar conceived a child with the repo owner's randomart avatar."
- nemo1618 5y agoThat's a good idea! Although, it could still potentially backfire for the same reason as scrypt; now if an adversary is able to obtain your nonce, they are much more likely to fool you. I guess my broader point here (which I neglected to mention in the OP) is that we already have an excellent means of verifying identities: cryptographic signatures. Avatars are fine, but our interfaces need to make it clear that an avatar is just a costume, not a fingerprint. The Hard Problem, as we all know, is tying real-world people (and objects) to virtual-world pubkeys. If we can manage that, the rest is moot.