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
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,...).
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.
> 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.
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.
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.
Yeah - I would imagine with some hash functions it doesn't make much difference whether you have access to message0, or just the hash of message0. Whereas with other hash functions it might make a lot of difference.
It's never going to be better to only have the hash vs having the message itself though.
In general, preimage would be harder than second preimage because you have less information(just the hash of message0) whereas for second preimage you know the message and the hash(because you can obviously compute the latter from the former).
What about cases where the hash output isn't properly distributed across all possible outputs. Could some specific hash outputs be easier to find preimages for, and therefore have weaker preimage resistance? The idea here being that if you take some arbitrary message it's unlikely to produce one of these weaker hashes, but by simply selecting a weak hash directly you can find a message for it.
Or is this just too contrived and no function ends up working this way in practice?
Well, theoretically, I'm sure it's possible to construct it that way, but I think your intuition that this doesn't happen in practice is correct.
I don't have any justification for that though other than it would seem like a strange thing in an algorithm designed to be resistant to these things for the output distribution to be skewed like that.
Edit:
Thinking about it some more, if some inputs give weaker(to preimage attack) hashes, then for those specific inputs, second preimage could only possibly be slower by the extra time needed to compute the hash and do the preimage attack. Which is generally insignificant next to the time it takes to do the preimage attack.
I think in these attacks are usually talked about in terms of an arbitrary, not specially selected, message / hash.
When wikipedia says "Given a hash value h, it should be difficult to find ....", "h" there is any arbitrary hash.
For example, I can tell you the md5 preimage for 5f4dcc3b5aa765d61d8327deb882cf99. Google can tell you that one. That doesn't mean there's a real preimage attack for md5 since given any arbitrary h, I cannot tell you what hashes to it.
> The idea here being that if you take some arbitrary message it's unlikely to produce one of these weaker hashes, but by simply selecting a weak hash directly you can find a message for it.
You don't get to select the weak hash, like "5f4dcc3b5aa765d61d8327deb882cf99" in this case, to prove you have a preimage attack.
What's the threshold for this though? If you choose the hash and I have to produce the preimage, that scenario means you could always pick a "strong" hash, but if e.g. 50% of hashes are "weak" hashes, then a completely randomly selected hash would have a 50% chance of being "weak" and therefore attackable. If I can break 50% of randomly-selected hashes, does that count? Or would it have to be more like producing a preimage for hashes generated by randomly-selected inputs (and therefore the "weak" hashes in this scenario would be unlikely to be produced).
>> 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 second preimage attack. SHA-1 is broken for collision, not preimage or second preimage
To use an analogy people might be familiar with, it's like the birthday paradox; you can find two people with the same birthday without looking too hard, but it's a lot more work to start with one person's birthday and then try to find someone else with that exact birthday. Right now, we can fairly easily find pairs of MD5/SHA1 hashes that are the same, but it's not currently feasible to start with one input to the hash function and then find some different input that produces the exact same hash.
> > 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 second preimage attack. SHA-1 is broken for collision, not preimage or second preimage.
I think that's backwards. Producing a file with a specific SHA-1 hash is a preimage attack while producing a file with the same hash as another file is a second preimage attack.
Not that it matters for SHA-1 where both aren't broken yet.
> Q: Is it possible to make a file get an arbitrary MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3, or the same hash as another file?
> A: No.
From the SHA-1 citation:
> "Finding a practical collision attack breaks the hash function badly of course, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides," Thomas Peyrin, one of the researchers told ZDNet via email over the weekend.
> > That is, take some data and manipulate it until it has the same MD5 as a different piece of data.
> Second sentence is false - that's called a preimage attack.
It's actually rather poorly specified description of either, tbh. I don't think this is a charitable read of the sentence.
Formally, a second preimage game has one party (the adversary to your algorithm) generate some data and and a second party (your algorithm) generate some other different data, with a hash that matches that of the unmodified data chosen by the first party.
A collision attack lets your algorithm choose both pieces of data, and the adversary simply verifies the hashes match.
Most collision attacks, going back to Wang's original attack on md5, generate a random string and manipulate it until certain preconditions hold and hope that its pair's hash matches, and otherwise try again until one matches. (Where pair is defined as some inversion under the constraint system -- usually the same block with certain bits flipped).
But that description sounds awfully like the original vague description. :-)
Edit to add: the OP is misinformed about preimage attacks being easy, outside of specific scenarios like rainbow tables and the like. For the general case of arbitrary hashes it is hard.
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).
> 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
> 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.
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.
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.
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.
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?
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.
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.
43 comments
[ 14.5 ms ] story [ 1496 ms ] threadIt could be possible using a non-cryptographic hash (murmurhash, CRC,...).
looks around
FCKGW…
Such nostalgia.
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#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.
It's never going to be better to only have the hash vs having the message itself though.
Or is this just too contrived and no function ends up working this way in practice?
I don't have any justification for that though other than it would seem like a strange thing in an algorithm designed to be resistant to these things for the output distribution to be skewed like that.
Edit:
Thinking about it some more, if some inputs give weaker(to preimage attack) hashes, then for those specific inputs, second preimage could only possibly be slower by the extra time needed to compute the hash and do the preimage attack. Which is generally insignificant next to the time it takes to do the preimage attack.
When wikipedia says "Given a hash value h, it should be difficult to find ....", "h" there is any arbitrary hash.
For example, I can tell you the md5 preimage for 5f4dcc3b5aa765d61d8327deb882cf99. Google can tell you that one. That doesn't mean there's a real preimage attack for md5 since given any arbitrary h, I cannot tell you what hashes to it.
> The idea here being that if you take some arbitrary message it's unlikely to produce one of these weaker hashes, but by simply selecting a weak hash directly you can find a message for it.
You don't get to select the weak hash, like "5f4dcc3b5aa765d61d8327deb882cf99" in this case, to prove you have a preimage attack.
> 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 second preimage attack. SHA-1 is broken for collision, not preimage or second preimage
To use an analogy people might be familiar with, it's like the birthday paradox; you can find two people with the same birthday without looking too hard, but it's a lot more work to start with one person's birthday and then try to find someone else with that exact birthday. Right now, we can fairly easily find pairs of MD5/SHA1 hashes that are the same, but it's not currently feasible to start with one input to the hash function and then find some different input that produces the exact same hash.
I think that's backwards. Producing a file with a specific SHA-1 hash is a preimage attack while producing a file with the same hash as another file is a second preimage attack.
Not that it matters for SHA-1 where both aren't broken yet.
From the MD5 citation:
> Q: Is it possible to make a file get an arbitrary MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3, or the same hash as another file?
> A: No.
From the SHA-1 citation:
> "Finding a practical collision attack breaks the hash function badly of course, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides," Thomas Peyrin, one of the researchers told ZDNet via email over the weekend.
> > That is, take some data and manipulate it until it has the same MD5 as a different piece of data.
> Second sentence is false - that's called a preimage attack.
It's actually rather poorly specified description of either, tbh. I don't think this is a charitable read of the sentence.
Formally, a second preimage game has one party (the adversary to your algorithm) generate some data and and a second party (your algorithm) generate some other different data, with a hash that matches that of the unmodified data chosen by the first party.
A collision attack lets your algorithm choose both pieces of data, and the adversary simply verifies the hashes match.
Most collision attacks, going back to Wang's original attack on md5, generate a random string and manipulate it until certain preconditions hold and hope that its pair's hash matches, and otherwise try again until one matches. (Where pair is defined as some inversion under the constraint system -- usually the same block with certain bits flipped).
But that description sounds awfully like the original vague description. :-)
Edit to add: the OP is misinformed about preimage attacks being easy, outside of specific scenarios like rainbow tables and the like. For the general case of arbitrary hashes it is hard.
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).
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
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.
Also, try to not infringe where you live.
It's quite simple once you understand the basics of law.
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.
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...
[1] https://grapecollective.com/articles/prohibitions-grape-bric...
I've never heard this? Who can I pay to create a file with the specific hash "deadbeefdeadbeefdeadbeefdeadbeefdeadbeef" and how much does it cost?
«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.
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.
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.
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?
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.
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.