8 ms·
The image in this post displays its own MD5 hash
- kstrauser 4y agoFrom the discussion: > 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.
- Retr0id 4y agoIn hindsight, I really regret not including the adler32 and crc32 in the image itself too, since I knew them ahead of time. If you inspect them with hexeditor, you'll find they have non-random values :)
- airstrike 4y agoBut to make up for it you started and ended with 1337 so all is forgiven
- nodja 4y agoDoes this mean you could in theory make the adler32 and crc32 part of the md5 hash as well?
- Retr0id 4y agoI could, but I'd have to set adler32==crc32 (doable), otherwise the md5 bruteforce would be too difficult. In fact, I could do this fairly quickly without needing to recompute much at all...
- akprasad 4y agoRelated, from earlier today: "MD5 Collision with CRC32 Preimage" https://news.ycombinator.com/item?id=32956235 https://news.ycombinator.com/item?id=32956235
- Retr0id 4y agoHi everyone - I go into slightly more detail on my twitter thread on the same topic: https://twitter.com/David3141593/status/1573218394358386688 https://twitter.com/David3141593/status/1573218394358386688 (Yes, the PNG also survives being uploaded to twitter) 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/hashquine_by_retr0id.png https://retr0.id/media/a13f403f-fff5-4f40-b9a2-13cce355f61b/... https://pbs.twimg.com/media/FdUxWg-XkAE5FBx?format=png&name=small https://pbs.twimg.com/media/FdUxWg-XkAE5FBx?format=png&name=...
- TheSpiceIsLife 4y agoWas the 1337 at either end of the hash intentional?
- Retr0id 4y agoYes
- deleted 4y ago[deleted]
- kstrauser 4y agoSorry if I overwhelmed your VPS! But seriously, this was super impressive. Well done!
- Retr0id 4y agoIt's still alive, just barely! 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:07
- 4y ago
- inasio 4y agoRelated: Inverting hash functions using SAT and SMT solvers [0] [0] https://blog.lse.epita.fr/2012/07/31/using-sat-and-smt-to-defeat-simple-hashing-algorit.html https://blog.lse.epita.fr/2012/07/31/using-sat-and-smt-to-de...
- nextaccountic 4y agoYou can also mine Bitcoin with SAT solvers. And if the difficulty is high enough, it will be more efficient than the current brute force methods methods https://jheusser.github.io/2013/02/03/satcoin.html 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-search-for-hashcash-proof-of-work-used-by-Bitcoin https://www.quora.com/Are-SAT-solvers-faster-than-linear-sea... https://github.com/jheusser/satcoin https://github.com/jheusser/satcoin an implementation
- pvillano 4y agoThe relevance/connection of the following now escapes me but I already wrote it so here it is. 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.
- tacker2000 4y agoImpressive! This is the true “hacking” spirit!
- zeven7 4y agoIs there an MD5 hash string that hashes to itself?
- AustinDev 4y agoProbably not but, would love to be proven wrong. To get this stuff to work you have to add a ton of garbage data to the end of the file from what I understand which you can't really do with a string.
- rileymat2 4y agoIt is interesting that the OP used “hash string” instead of MD5 value. I’d wager that if you dove into string encodings that you would find some.
- kadoban 4y agoThere's not _that_ many encodings that feel natural enough. Maybe: bytes, ascii/utf-8/latin1/etc. (all equiv.), utf-16, utf-32, maybe ebcdic. 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).
- Retr0id 4y agoThere are more options if you consider whitespace. You can separate the digit pairs with single or double spaces (or in groups of 4, etc. etc.), and end the line with nothing, or \n, or \r\n
- kadoban 4y agoGood call, \n and \r\n feel like good ideas. Separating digits feels like it'd look a little cheap to me, but I'd still be impressed.
- rileymat2 4y ago
- XCSme 4y agoThis looks impressive. 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?
- Retr0id 4y ago> Can an attacker generate a collision having the MD5 hash without knowing the salt? Depending on how the salt is applied, yes.
- XCSme 4y agoLet's say I append 128 random bytes to the input string.
- Retr0id 4y agoTrivially broken. Ignoring the adler32 and crc32 checksums, I can retroactively adjust the hex digits in the image without affecting the resultant hash, even with a suffix - as long as I know what the final hash is.
- imranhou 4y agoAssuming that you are able to easily trigger the hashing with salt enough times for you to adjust the image... right? Any idea (ballpark) how many such test iterations would you need? Great work btw!
- Retr0id 4y agoApproximately 1
- XCSme 4y agoI was talking about basic string hashing (not images), so I guess that would be even simpler. > 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.
- thrdbndndn 4y agoAll the reply links other than #2 don't work. Any idea?
- Retr0id 4y agoI disabled replies to save server resources, it would probably be down right now, otherwise. If you have access to another fediverse instance, you should be able to view them that way.
- userbinator 4y agoWhat's the estimated compute cost currently to do this for SHA-1?
- komalkumri 4y agoHy
- caster_cp 4y agoThis is beautiful. Douglas Hofstadter would be proud. 1337 at the end got me.
- 9woc 4y agoSomeone did a GIF version before: https://github.com/Rogdham/gif-md5-hashquine https://github.com/Rogdham/gif-md5-hashquine
- omoikane 4y agoThere was also an animated GIF version: https://news.ycombinator.com/item?id=13823704 https://news.ycombinator.com/item?id=13823704 From this thread: https://twitter.com/i/events/838685002703466497 https://twitter.com/i/events/838685002703466497
- jabbany 4y agoI keep imagining the fantasy scenario where some day I stumble on a software download or repo or something. Nothing special, no fanfare, just a random piece of code to do some random task. 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 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/gestalt.pdf https://vision.cornell.edu/se3/wp-content/uploads/2014/09/ge...
- andreareina 4y agoTrying to find that hash by iterating on the manifest hash (as opposed to e.g. manipulating whitespace etc) would eventually succeed approximately 1/e of the time. Better get cracking!
- alexjurkiewicz 4y agoSounds like the basilisk collection: https://suricrasia.online/unfiction/basilisk/ https://suricrasia.online/unfiction/basilisk/
- lelandbatey 4y agoIn reading that page, I was super taken in and immediately wanted to get a copy of the collection; trying to follow the links left me sad to realize it's a fictional story, but it's an amazing piece of fiction none the less.
- mizzao 4y agoYeah, it reminded me of the Three-Body Problem... "hard" science fiction that's believable as an extension of what we currently know
- 9woc 4y agoI did a ELI5 writeup on this. Hope someone finds it useful: https://tongwing.woon.sg/blog/image-which-displays-its-own-md5-hash/ https://tongwing.woon.sg/blog/image-which-displays-its-own-m...
- Waterluvian 4y agoI found it useful. Thank you so much.
- jfdi 4y agoThank you!
- Linda703 4y ago[dead]
- allisdust 4y agoIs this possible only because md5 is weak? Is it possible to do the same with sha2 or sha1?
- infofarmer 4y agoYes. Not yet.
- googlryas 4y agoYup - it's possible to do with any hash algorithm. You can also do it with any hash value. A key point here is that there are a ton of pixels in this image whose value can be changed slightly without disturbing the image. The # of variants possible quickly starts to dwarf the # of valid hash values possible, to the point where you can find the hash eventually, if you just keep looking.
- posedge 4y agoGiven that an md5 hash is 128 bit, by simple brute force, you would need to try 2^128 variants (in expectation) to find the matching hash. Thats rougly 10^38 combinations. That's a huge number, I can't imagine that the author simply hashed variants until one happened to match, there must habe been some other technique involved.
- MonkeyClub 4y agoThis definitely gets extra points, made me snicker... twice. 1337!
- eimrine 4y agoAre there any quines where an image or something contains not only one representation of MD5 of itself but also a MD5 of same image but without a quine (2 hashes)? 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.
- account42 4y ago> 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.
- cat_plus_plus 4y agoGood job, can we just try to make sure this is the last MD5-insecurity demonstration effort ever? Anyone who is not convinced is never going to be convinced. At the same time, MD-5 or even CRC-32 unintentional collisions are too unlikely to worry about in most practical scenarios. Future computational efforts would do well to improve tampering resistance or unintentional corruption detection rather than re-litigating the obvious.
- Helmut10001 4y agoCan someone explain why the image displays a Dragon that eats itself? Mere coincidence?
- gammalost 4y agoIt's a reference to quine. A program which has it's own source as output. A fun brain teaser that I recommend trying
- Helmut10001 4y agoGreat, thanks. Now this all makes sense.
- michaelcampbell 4y agoNeat. This reminds me (somewhat obliquely) of a shareware library in the 80's that allowed a c-compiled binary on windows to be aware of its own CRC-32. The idea was to prevent hex-tampering.
- aabbcc1241 4y agoOriginally I through blockchain is a linked list that points to the hash of next block. (The actual blockchain block points to it's previous block)