4 ms·

Illegal Hashes

67 points by edent 4y ago

umvi 4y ago
> It is somewhat cheap and easy to produce a file with a specific SHA-1 hash. I've never heard this? Who can I pay to create a file with the specific hash "deadbeefdeadbeefdeadbeefdeadbeefdeadbeef" and how much does it cost?
adzm 4y ago
It's an interesting topic but this post barely covers it. The Wikipedia article on illegal numbers is much more informative and interesting. https://en.wikipedia.org/wiki/Illegal_number https://en.wikipedia.org/wiki/Illegal_number
- InitialLastName 4y ago
  The way this is written makes me suspect that the post itself would hash to an illegal number, but I don't have the capacity to check it out.
  - GuB-42 4y ago
    None of the major cryptographic hashes (MD5, SHA-*) have practical preimage attacks. It means pulling off what the author suggests (having a document hash to an illegal number) is impossible in practice, at least for now. It could be possible using a non-cryptographic hash (murmurhash, CRC,...).
theflyingelvis 4y ago
I had some illegal hash once, but it wasn’t numeric.
- checkyoursudo 4y ago
  Dude, everything is numeric.
  - mayankkaizen 4y ago
    That hash was ecstatic.
sli 4y ago
This reminds me. I used to have a small blog that would get basically zero views until the day I brazenly posted that Sony encryption key. Got a million views on that one post in a single day, which was an absolutely wild experience for me.
- Waterluvian 4y ago
  A million views you say. looks around FCKGW…
  - aliqot 4y ago
    https://en.wikipedia.org/wiki/Talk%3AFCKGW https://en.wikipedia.org/wiki/Talk%3AFCKGW
    - Waterluvian 4y ago
      I began typing it out in iOS safari and autocomplete presented me with the entire key. Such nostalgia.
nayuki 4y ago
> Because MD5 is a relatively weak algorithm, it is possible to create deliberate hash "collisions". That is, take some data and manipulate it until it has the same MD5 as a different piece of data. First sentence is true. Second sentence is false - that's called a preimage attack. MD5 is broken for collisions, not preimage or second preimage. > It is somewhat cheap and easy to produce a file with a specific SHA-1 hash. No, that's called a preimage attack. SHA-1 is broken for collision, not preimage or second preimage. ---- Please see this section for the 3 core properties of a cryptographic hash function: https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr... . They appear similar but are very different. In a collision attack, you are allowed to manipulate both message0 and message1 as much as you like until hash(message0) = hash(message1). Because the attacker has so much choice, this is the hardest attack to defend against, and this is how almost every hash function has failed. In a second preimage attack, you are given a target message0 (which you cannot change), and you can manipulate message1 as much as you want until hash(message1) = hash(message0). This would be like making a new SSL certificate with the same hash as another publicly available certificate belonging to someone else that you cannot modify. In a preimage attack, you are given a target hash value h (which was generated from some secret message0 that is not known to you), and you can manipulate message1 as much as you want until hash(message1) = h. This would be like reversing a password hash back to a password.
- lilyball 4y ago
  In general, is it harder to do preimage attacks or second preimage attacks?
  - nayuki 4y ago
    I suspect second preimage attacks are easier because with the given message0, you can see the internal state of the hash function on message0 while you tweak your message1. Whereas in preimage attacks, you are only given the final hash.
    - p1necone 4y ago
dahart 4y ago
I feel like this stokes imagination and/or fear by adding more confusion than clarification… am I alone? It’s unclear that illegal numbers exist outside of intent to communicate the illegal idea. Otherwise all irrationals including pi and e are illegal. And it’s probably possible to view/interpret any data you have in some way that happens to coincide with an illegal number. If anyone was going to have legal trouble for coincidental unintentional hashes, then everyone has a problem, which is exactly why it’s unlikely to go there, it’s clearly absurd. > Decoded into ASCII, that spells I hate the queen This is an example of what I mean - while this hash is theoretically possible, note that hashes are not typically ever displayed as ASCII, so why ASCII? That was a narrative choice in this article. Hashes are almost unanimously displayed as hex, or base64, which have no spaces for good reasons. Side note, it’s extremely rare for a hash to ever make sense when interpreted as ASCII due to needing zero entropy in the first bit of every byte for that to happen (observe they are all zero).
- advisedwang 4y ago
  > It’s unclear that illegal numbers exist outside of intent to communicate the illegal ideal Correct. Intent is important in the law. And when it comes to "Illegal numbers" and copyright in general _provenance_ is important too. I love sharing this article with people: https://ansuz.sooke.bc.ca/entry/23 https://ansuz.sooke.bc.ca/entry/23
- kelnos 4y ago
  > It’s unclear that illegal numbers exist outside of intent to communicate the illegal idea That assumes a sane legal system where intent matters. If we're talking about an authoritarian despot, they might not care if you intended to say something negative about you. Just the fact that you did might be enough.
thriftwy 4y ago
If you publish it with some instructions it is illegal, but if you post something with such hash accidentally you have plausible deniability. Also, try to not infringe where you live. It's quite simple once you understand the basics of law.
- hoosieree 4y ago
  π ...oops, just leaked all the illegal numbers.
  - yarg 4y ago
    Has that been proven (or disproven)? Does every finite string appear in pi? If it does, it'll be the span parameters that are illegal - and (I'm guessing) generally larger than the value that they're encoding.
    - colejohnson66 4y ago
      It has yet to be proven or disproven: https://math.stackexchange.com/questions/216343/does-pi-contain-all-possible-number-combinations https://math.stackexchange.com/questions/216343/does-pi-cont...
- noizejoy 4y ago
  > If you publish it with some instructions it is illegal ... unless you phrase the instructions as what you're not allowed to do[0][1] [0] https://vinepair.com/wine-blog/how-wine-bricks-saved-the-u-s-wine-industry-during-prohibition/ https://vinepair.com/wine-blog/how-wine-bricks-saved-the-u-s... [1] https://grapecollective.com/articles/prohibitions-grape-bricks-how-to-not-make-wine https://grapecollective.com/articles/prohibitions-grape-bric...
  - thriftwy 4y ago
    You're at mercy of courts here and that may or may not work.
emmelaich 4y ago
Anyone tried posting the md5 of say the EICAR test virus to see what happens?
nine_k 4y ago
This argument is pretty old. The way it's shown here is needlessly limiting. Consider the library that contains every permutation of letters: «All—the detailed history of the future, the autobiographies of the archangels, the faithful catalog of the Library, thousands and thousands of false catalogs, the proof of the falsity of those false catalogs, a proof of the falsity of the true catalog, the gnostic gospel of Basilides, the commentary upon that gospel, the commentary on the commentary on that gospel, the true story of your death, the translation of every book into every language, the interpolations of every book into all books...» (J.L. Borges, The Library of Babel.) More interesting is to analyze the probability of finding a file with a hash form a particular set. MD5 gives 160 bit; if it's a good hash that does not have large gaps in its values, this is roughly 1.46e+48 values. Let the set of the forbidden values have 1.46 billion elements, that is, 1.46e+9. This should be enough for all the hashes of copyrighted works, and all the forbidden blasphemous utterances. Then the chance of hitting one of them is going to be 1e-39. This chance is so low that it's hard to imagine. Take a mega-lottery with 10M = 1e+7 tickets; it's the chance of winning it six times in a row, by buying a single random ticket every time. This is, of course, assuming that MD5 has no preimage attack; AFAIK such an attack is not known by now.
justin_oaks 4y ago
All of this reminds me of "What colour are your bits?" https://news.ycombinator.com/item?id=24917679 https://news.ycombinator.com/item?id=24917679 The basic idea is that the bits can be illegal not based on the bits themselves, but on the intent with which they're created, the way they're presented, how they're transmitted, etc.
jbandela1 4y ago
Let me tell you about illegal ion movements. You see, nerves transmit impulses by allowing charged particles called ions to enter the nerve cell. All actions a person does could probably be described as a series of ion movements. If those ion movements result in you hitting your neighbor in the nose, then you will probably get in trouble. Hence, illegal ion movements.
justin_oaks 4y ago
It's an interesting idea, but I don't think we should limit this discussion to hashing. We could discuss the same idea with other encoding/processing schemes. For example, you can present two or more different bit strings that appear random, but when XOR'd together produces some "illegal" content. Which of these is illegal to transmit?
dilyevsky 4y ago
Maybe stupid question but has anyone tried incorporating those into bitcoin or some other blockchain? Will that render the whole chain illegal if it’s sufficiently far down?
CodesInChaos 4y ago
Another submission of this article: https://news.ycombinator.com/item?id=33773501 https://news.ycombinator.com/item?id=33773501
motohagiography 4y ago
When I read this, it clicked that the problem wasn't in the hashes - they produce random output. The problem was with the idea that the appearance of random numbers could be construed as meaningful, based on associating them with criticism or being problematized by the people who made the rules against insulting the royalty. When you imagine those people going through every available media and looking for insults against the royalty, and finding one way or another to interpret it that way so they could crack down on the writers - how insane they must have been, or worse malicious, and sometimes just sadistic. If I were to offer some advice based on it, I would suggest that if you think a hash can be problematic, to reflect seriously on where the problem may lie.
zzo38computer 4y ago
Note that you could make up a hash and use it as an encryption key for something (which is unrelated to whatever it is the hash of). It is also possible to use a hash as the encryption key for the data that it is a hash of. It is not too difficult to make up data that the first few bits of the hash match some specific number (although it is a bit slow). For example, you can adjust values of pixels in a picture so that if you make the hash of each scanline independently and then put together the first few bits of the hash of each scanline then it will make up some specific text. Or, to collide the first few bits of a commit (or a file) of a git or fossil repository. You can also do many things involving XOR of hashes with other data (whether you have two or possibly more than two sets of data), etc. But, copyright is bad anyways, and laws that you cannot freedom of speech (e.g. to tell you if you hate or don't hate the queen), is also bad anyways.

67 points by edent 4y ago

umvi 4y ago

> It is somewhat cheap and easy to produce a file with a specific SHA-1 hash. I've never heard this? Who can I pay to create a file with the specific hash "deadbeefdeadbeefdeadbeefdeadbeefdeadbeef" and how much does it cost?

adzm 4y ago

It's an interesting topic but this post barely covers it. The Wikipedia article on illegal numbers is much more informative and interesting. https://en.wikipedia.org/wiki/Illegal_number https://en.wikipedia.org/wiki/Illegal_number

InitialLastName 4y ago
The way this is written makes me suspect that the post itself would hash to an illegal number, but I don't have the capacity to check it out.
- GuB-42 4y ago
  None of the major cryptographic hashes (MD5, SHA-*) have practical preimage attacks. It means pulling off what the author suggests (having a document hash to an illegal number) is impossible in practice, at least for now. It could be possible using a non-cryptographic hash (murmurhash, CRC,...).

theflyingelvis 4y ago

I had some illegal hash once, but it wasn’t numeric.

checkyoursudo 4y ago
Dude, everything is numeric.
- mayankkaizen 4y ago
  That hash was ecstatic.

sli 4y ago

This reminds me. I used to have a small blog that would get basically zero views until the day I brazenly posted that Sony encryption key. Got a million views on that one post in a single day, which was an absolutely wild experience for me.

Waterluvian 4y ago
A million views you say. looks around FCKGW…
- aliqot 4y ago
  https://en.wikipedia.org/wiki/Talk%3AFCKGW https://en.wikipedia.org/wiki/Talk%3AFCKGW
  - Waterluvian 4y ago
    I began typing it out in iOS safari and autocomplete presented me with the entire key. Such nostalgia.

nayuki 4y ago

> Because MD5 is a relatively weak algorithm, it is possible to create deliberate hash "collisions". That is, take some data and manipulate it until it has the same MD5 as a different piece of data. First sentence is true. Second sentence is false - that's called a preimage attack. MD5 is broken for collisions, not preimage or second preimage. > It is somewhat cheap and easy to produce a file with a specific SHA-1 hash. No, that's called a preimage attack. SHA-1 is broken for collision, not preimage or second preimage. ---- Please see this section for the 3 core properties of a cryptographic hash function: https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr... . They appear similar but are very different. In a collision attack, you are allowed to manipulate both message0 and message1 as much as you like until hash(message0) = hash(message1). Because the attacker has so much choice, this is the hardest attack to defend against, and this is how almost every hash function has failed. In a second preimage attack, you are given a target message0 (which you cannot change), and you can manipulate message1 as much as you want until hash(message1) = hash(message0). This would be like making a new SSL certificate with the same hash as another publicly available certificate belonging to someone else that you cannot modify. In a preimage attack, you are given a target hash value h (which was generated from some secret message0 that is not known to you), and you can manipulate message1 as much as you want until hash(message1) = h. This would be like reversing a password hash back to a password.

lilyball 4y ago
In general, is it harder to do preimage attacks or second preimage attacks?
- nayuki 4y ago
  I suspect second preimage attacks are easier because with the given message0, you can see the internal state of the hash function on message0 while you tweak your message1. Whereas in preimage attacks, you are only given the final hash.
  - p1necone 4y ago

dahart 4y ago

I feel like this stokes imagination and/or fear by adding more confusion than clarification… am I alone? It’s unclear that illegal numbers exist outside of intent to communicate the illegal idea. Otherwise all irrationals including pi and e are illegal. And it’s probably possible to view/interpret any data you have in some way that happens to coincide with an illegal number. If anyone was going to have legal trouble for coincidental unintentional hashes, then everyone has a problem, which is exactly why it’s unlikely to go there, it’s clearly absurd. > Decoded into ASCII, that spells I hate the queen This is an example of what I mean - while this hash is theoretically possible, note that hashes are not typically ever displayed as ASCII, so why ASCII? That was a narrative choice in this article. Hashes are almost unanimously displayed as hex, or base64, which have no spaces for good reasons. Side note, it’s extremely rare for a hash to ever make sense when interpreted as ASCII due to needing zero entropy in the first bit of every byte for that to happen (observe they are all zero).

advisedwang 4y ago
> It’s unclear that illegal numbers exist outside of intent to communicate the illegal ideal Correct. Intent is important in the law. And when it comes to "Illegal numbers" and copyright in general _provenance_ is important too. I love sharing this article with people: https://ansuz.sooke.bc.ca/entry/23 https://ansuz.sooke.bc.ca/entry/23
kelnos 4y ago
> It’s unclear that illegal numbers exist outside of intent to communicate the illegal idea That assumes a sane legal system where intent matters. If we're talking about an authoritarian despot, they might not care if you intended to say something negative about you. Just the fact that you did might be enough.

thriftwy 4y ago

If you publish it with some instructions it is illegal, but if you post something with such hash accidentally you have plausible deniability. Also, try to not infringe where you live. It's quite simple once you understand the basics of law.

hoosieree 4y ago
π ...oops, just leaked all the illegal numbers.
- yarg 4y ago
  Has that been proven (or disproven)? Does every finite string appear in pi? If it does, it'll be the span parameters that are illegal - and (I'm guessing) generally larger than the value that they're encoding.
  - colejohnson66 4y ago
    It has yet to be proven or disproven: https://math.stackexchange.com/questions/216343/does-pi-contain-all-possible-number-combinations https://math.stackexchange.com/questions/216343/does-pi-cont...
noizejoy 4y ago
> If you publish it with some instructions it is illegal ... unless you phrase the instructions as what you're not allowed to do[0][1] [0] https://vinepair.com/wine-blog/how-wine-bricks-saved-the-u-s-wine-industry-during-prohibition/ https://vinepair.com/wine-blog/how-wine-bricks-saved-the-u-s... [1] https://grapecollective.com/articles/prohibitions-grape-bricks-how-to-not-make-wine https://grapecollective.com/articles/prohibitions-grape-bric...
- thriftwy 4y ago
  You're at mercy of courts here and that may or may not work.

emmelaich 4y ago

Anyone tried posting the md5 of say the EICAR test virus to see what happens?

nine_k 4y ago

This argument is pretty old. The way it's shown here is needlessly limiting. Consider the library that contains every permutation of letters: «All—the detailed history of the future, the autobiographies of the archangels, the faithful catalog of the Library, thousands and thousands of false catalogs, the proof of the falsity of those false catalogs, a proof of the falsity of the true catalog, the gnostic gospel of Basilides, the commentary upon that gospel, the commentary on the commentary on that gospel, the true story of your death, the translation of every book into every language, the interpolations of every book into all books...» (J.L. Borges, The Library of Babel.) More interesting is to analyze the probability of finding a file with a hash form a particular set. MD5 gives 160 bit; if it's a good hash that does not have large gaps in its values, this is roughly 1.46e+48 values. Let the set of the forbidden values have 1.46 billion elements, that is, 1.46e+9. This should be enough for all the hashes of copyrighted works, and all the forbidden blasphemous utterances. Then the chance of hitting one of them is going to be 1e-39. This chance is so low that it's hard to imagine. Take a mega-lottery with 10M = 1e+7 tickets; it's the chance of winning it six times in a row, by buying a single random ticket every time. This is, of course, assuming that MD5 has no preimage attack; AFAIK such an attack is not known by now.

justin_oaks 4y ago

All of this reminds me of "What colour are your bits?" https://news.ycombinator.com/item?id=24917679 https://news.ycombinator.com/item?id=24917679 The basic idea is that the bits can be illegal not based on the bits themselves, but on the intent with which they're created, the way they're presented, how they're transmitted, etc.

jbandela1 4y ago

Let me tell you about illegal ion movements. You see, nerves transmit impulses by allowing charged particles called ions to enter the nerve cell. All actions a person does could probably be described as a series of ion movements. If those ion movements result in you hitting your neighbor in the nose, then you will probably get in trouble. Hence, illegal ion movements.

justin_oaks 4y ago

It's an interesting idea, but I don't think we should limit this discussion to hashing. We could discuss the same idea with other encoding/processing schemes. For example, you can present two or more different bit strings that appear random, but when XOR'd together produces some "illegal" content. Which of these is illegal to transmit?

dilyevsky 4y ago

Maybe stupid question but has anyone tried incorporating those into bitcoin or some other blockchain? Will that render the whole chain illegal if it’s sufficiently far down?

CodesInChaos 4y ago

Another submission of this article: https://news.ycombinator.com/item?id=33773501 https://news.ycombinator.com/item?id=33773501

motohagiography 4y ago

When I read this, it clicked that the problem wasn't in the hashes - they produce random output. The problem was with the idea that the appearance of random numbers could be construed as meaningful, based on associating them with criticism or being problematized by the people who made the rules against insulting the royalty. When you imagine those people going through every available media and looking for insults against the royalty, and finding one way or another to interpret it that way so they could crack down on the writers - how insane they must have been, or worse malicious, and sometimes just sadistic. If I were to offer some advice based on it, I would suggest that if you think a hash can be problematic, to reflect seriously on where the problem may lie.

zzo38computer 4y ago

Note that you could make up a hash and use it as an encryption key for something (which is unrelated to whatever it is the hash of). It is also possible to use a hash as the encryption key for the data that it is a hash of. It is not too difficult to make up data that the first few bits of the hash match some specific number (although it is a bit slow). For example, you can adjust values of pixels in a picture so that if you make the hash of each scanline independently and then put together the first few bits of the hash of each scanline then it will make up some specific text. Or, to collide the first few bits of a commit (or a file) of a git or fossil repository. You can also do many things involving XOR of hashes with other data (whether you have two or possibly more than two sets of data), etc. But, copyright is bad anyways, and laws that you cannot freedom of speech (e.g. to tell you if you hate or don't hate the queen), is also bad anyways.