The image in this post displays its own MD5 hash
retr0.id
retr0.id
The pleroma instance linked in the OP is hosted on a very tiny VPS with no CDN, I fear it may fall over - if it does, consider swapping to the twitter URL.
Direct links to the image itself:
https://retr0.id/media/a13f403f-fff5-4f40-b9a2-13cce355f61b/...
https://pbs.twimg.com/media/FdUxWg-XkAE5FBx?format=png&name=...
CPU[*****************************************************************************100.0%] Tasks: 49, 30 thr; 1 running
Mem[||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||****641M/768M] Load average: 2.51 2.12 2.01
Swp[|||||||||||||||||||||||| 215M/768M] Uptime: 166 days(!), 19:40:07And then we have something like our zabbix proxies, and when they passed a couple tens of thousands of items, we had to increase it's cache memory... from 16MB to a glorious 64MB. Such a splurge. And the server is using a whole 128MB for its write caches. Or our Grafanas are using a total of about 500MB of memory server side total to chew through oodles of data.
But then I have other stuff running on huge node and struggling to process 10 messages per second and falling over whenever load increases by 10%.
(╯°□°）╯︵ ┻━┻
> Since there are 36 pairs of blocks, there are 2^36 possible combinations, for each message. If we enumerate them all and check the resulting CRC, we'd have a reasonable chance of stumbling across the target CRC (0xdeadbeef) by chance - since there are only 2^32 possible CRC32 results.
> This is a feasible computation, but it would be a bit slow, probably on the order of minutes - infeasible as part of the inner-loop of a larger attack (such as a PNG hashquine!). Fortunately, there's a trick we can use to speed this up. [Meet in the middle.]
Wait a sec, CRC32 (and Adler32 IIRC) are linear — they are the “sum”, for all positions i in the input, of f(i, message[i]). (The actual details of f are irrelevant here.). For CRC32, “sum” is xor and, for Adler32, I think it’s the sum of pairs of u16 values. (No serious Galois field arithmetic needed — the Galois sum in the representation used by CRC32 is xor.)
So those 36 pairs each give a pair of vectors in the 32-dimensions space of checksums. Start with the message with all the a blocks. One at a time, switch a single block to its b value and calculate the change in the checksum, which can be done from the command line :). Each of those changes is a vector in checksum space, and they should form a basis with respectable probability m. You know the change you want to produce in the checksum from the all-a state to the correct checksum, and you can solve your underdetermined system of 32 equations with 36 unknowns using your favorite technique.
(Hmm. I haven’t written this out for real. I’m fairly confident it will work for CRC, since CRC’s checksum space has order 2 — solving the linear system will give 0 or 1 for each variable (i.e. colliding block), and you can read off the answer. For Adler32, the space is order 2^16, but you need a solution that only applies each available perturbation zero or one times. Off the top of my head, there are probably some good algorithms for this, but it’s maybe not trivial.)
I'd usually go to wagner's k-tree algorithm for a modular subset sum problem.
But these are pretty small instances and you shouldn't need to use a particularly memory efficient algorithm. So for example, splitting the space of all choices in two, enumerating all combinations on each side and searching for a meet-in-the middle should also work.
What's the time complexity of your favorite technique?
(I'm a bit out-of-the-loop on the specifics of equation solving techniques - I let Z3 do this kind of thing for me, and take an educated guess on whether I'll finish during my lifetime or not)
I would expect the linear algebra approach to win by orders or magnitude.
Looking forward to your next project: SHA3-512 :D
Inside the repo or zip, is a simple text manifest file. The file has some bog standard readme stuff and then lists all the files and their hashes, you know, so you can check nothing's corrupted whatnot.
But in that list of files, is a line item for the manifest file itself and along with its own hash! Something that on the surface looks completely innocuous but becomes profoundly impressive as you ponder it.
Kind of a low-key [fridge brilliance](https://tvtropes.org/pmwiki/pmwiki.php/Main/FridgeBrilliance) kind of flex.
[Bonus] I'm also reminded of this paper: https://vision.cornell.edu/se3/wp-content/uploads/2014/09/ge...
proof-of-superiority if you will.
As a bonus challenge: fix the spelling of "missile" (mis-spelled as "missle" throughout, in 200+ occurrences), while maintaining the layout.
It's like the realization arrived at the same time from two different directions. Thank you!
(One of the FAQ questions in the guide helped)
Rot13 it or something at least (unicode upside-down, etc).
Agree this would be cool. But there would be one last realisation after contemplating it for just a little longer. The sheer number CPU cycles that would have to have been committed to achieving it would be awful. Like Bitcoin mining but orders of magnitude even more wasteful.
It could maaaaaaaybe be done using multiple collisions that exploit the structure of a DEFLATE-compressed stream, so that you can control the extracted zip contents on a byte-by-byte basis - but I haven't figured that out just yet. Watch this space!
Again, to me this is the exact same problem as this self-referential PNG file, which is a very cool trick but which can be (demonstrably) computed with limited compute resources.
And you never answered how this manifest is somehow different than the self-referential png.
It seems we do not understand each other (unfortunately HN comments are not the best avenue for deep discussions) so this will be my last post on this thread as we both have better things to do than talking past each other.
But in the cat and mouse between games trying to introduce DRM and this being instantly defeated each time because the DRM code was being removed by gamers/hackers... a company started making patches, and at the end of the patch was a bunch of what looked like garbage code, binpacked to create a certain size patch. It look erroneous. But patch arrived, then weeks and months later another patch, and so it went all the while the cat and mouse continued. Then finally DRM was enabled, and the question was how? How was this done when it hadn't been caught before? The answer was that all those fragments of code weren't innocuous or meaningless, it wasn't binpacking at all... the DRM code had been split into many fragments, shipped disguised as binpacking over a lot of patches, and by the time this was figured out the whole package had been delivered.
I'm not for copyright or DRM, but I did think that an elegant move.
> This was particularly tricky to make work because the image data in a PNG needs to have a valid adler32 checksum, and a valid crc32 checksum.
In fact, I could do this fairly quickly without needing to recompute much at all...
I guess it should be pretty likely to exist if you try them all, but the search is likely very computationally difficult unless I'm forgetting some particular weakness in md5 (quite possible).
https://news.ycombinator.com/item?id=614079
However, it appears no one has actually discovered it yet, if it exists.
A more tractable question might be to find a cycle in the MD5 hash space, like a->b->c->d->a. So one might ask, what is the shortest MD5 cycle found so far?
Assuming MD5 is random, this is the birthday problem. Since MD5 is 128 bits, you need about 10^19 hashes to get a repeat. [1]
The MD5 hashrate on an RTX 3090 is about 65 billion hashes per second. [2]
Dividing that out, about 4 GPU-years would be needed to find a repeat in this brute-force way.
[1] https://en.wikipedia.org/wiki/Birthday_attack#Mathematics
[2] https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace7210...
I think the math still works if you do that. But the cycle would have to be contained entirely within one of the individual runs. So that could potentially take longer.
The tricky part would be combing through the 160 exabytes of output to find the cycle.
I don't think you get to leave that out of the O(?) of this problem
MD5 is 128 bits so that’s 2^128 keys. And it’s 32 bytes for the output, so that’s really 2^133 bytes. Which is 10^38 which we don’t even have a unit for yet. Apparently it’s 100 million queccabytes.
You can get that down to two million queccabytes if you use a Bloom filter.
As long as you can keep 31 partial hashes in memory at a time, which is trivial, you don't have to rerun the work so far to increment the last digit by 1. I think I may have written the code for this at one point. I'll have to look around and see if I can find it.
That’s calculable in cpu hours, not GPU years. If the answer is one then you’re done. If it’s not then you test N=2 in 4 GPU years, rather than 8. As N increases the answer becomes less interesting, and the cost goes quadratic.
From this thread: https://twitter.com/i/events/838685002703466497
[0] https://blog.lse.epita.fr/2012/07/31/using-sat-and-smt-to-de...
https://jheusser.github.io/2013/02/03/satcoin.html
> Bitcoin Difficulty and Assumptions
> A very intriguing, and perhaps unintuitive property of the algorithm proposed is that with increasing bitcoin difficulty, or equally lower target, the search could become more efficient, at least in theory. This is because we can assume more about the structure of a valid hash -- a lower target means more leading zeros which are assumed to be zero in the SAT-based algorithm.
> If this is true and is a substantial effect then this is an important issue since the rate of the money supply is regulated with the difficulty. The higher the difficulty, the less likely it is that an individual block has a valid nonce. However, conventional mining algorithms always have to perform the same amount of work (i.e. try 4 billion nonce values) to reject a block. On the other hand, "Satcoin" miners will get progressively faster which could lead to imbalances in the controlled supply. These are all just speculations and depend on many factors, first and foremost how well the SAT-based approach can be improved and whether the probability of finding a valid nonce does not dwarf the efficiency gain of the algorithm.
https://www.quora.com/Are-SAT-solvers-faster-than-linear-sea...
https://github.com/jheusser/satcoin an implementation
I want to detect cheating in high level chess by estimating the humanness of chess moves with AI. The idea is simple. Take a huge database of GM matches, run stockfish on each position and train a classifier to map position+move to human/fish/both. Hopefully this can be done with less compute than coming up with the moves themselves
The problem is that if "fishy" moves can be identified, they can also be avoided. This could be done with adversarial training or just by using the above as a filter on stockfish output.
If not, is that any harder considering how badly MD5 is broken? For example, BMP image format seems perfect for this kind of quines because user can check one predetermined hash, that edit image in any simple image editor and check another predetermined hash.
That is assuming there is only one BMP version, which is not true.
(The actual blockchain block points to it's previous block)
Is an MD5 hash still "safe" if you use a salt? Can an attacker generate a collision having the MD5 hash without knowing the salt?
Depending on how the salt is applied, yes.
Great work btw!
> I can retroactively adjust the hex digits in the image without affecting the resultant hash
My point is: I give you a hash H, can you generate a collision by finding a string X, so that when I append an (unknown to you) salt S then MD5(X + S) = H.
EDIT: To make it clear, the only feedback you get when you try X is whether the final hash matches, you don't get the resulting hash each time.
What you can do trivially is find 2 strings X1 and X2 such that md5(X1) == md5(X2). In this case seeding the way you described won't help because md5(X1+S) will equal md5(X2+S) due to the way MD5 works
I _think_ that would do it though, if your salt is private and secure enough and you apply it the right way. I easily could be missing an attack though, so take with a large grain of salt (heh).
You should still use a different hash algorithm though.
Developer writes some code and publishes it. It's big, so he puts it on an untrusted CDN, and also publishes an MD5 hash of the code (not via the CDN).
User downloads the code from the CDN, and verifies the published hash matches.
A malicious CDN couldn't make an evil file with a matching hash, based on known attacks against MD5, unless they could influence the Developer to get certain data into the original file.
Then the CDN, by definition, would control the data that the end-user (downloader) hashes.
But I understand the confusion: londons_explore meant to write "there are no known (practical) preimage attacks" against MD5, which is true, since the only theoretical preimage has a complexity 2^123 or so.