The image in this post displays its own MD5 hash

https://retr0.id/notice/ANqlvFZD1eIqjmRiFc

by kstrauser • 4 years ago

766 130 4 years ago

kstrauser3• 4 years ago

From 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.

Retr0id23• 4 years ago

In 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• 4 years ago

But to make up for it you started and ended with 1337 so all is forgiven

nodja• 4 years ago

Does this mean you could in theory make the adler32 and crc32 part of the md5 hash as well?

akprasad• 4 years ago

Related, from earlier today: "MD5 Collision with CRC32 Preimage" https://news.ycombinator.com/item?id=32956235

Retr0id23• 4 years ago

Hi everyone - I go into slightly more detail on my twitter thread on the same topic: 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/...

https://pbs.twimg.com/media/FdUxWg-XkAE5FBx?format=png&name=...

TheSpiceIsLife• 4 years ago

Was the 1337 at either end of the hash intentional?

Retr0id23• 4 years ago

Yes

kstrauser3• 4 years ago

Sorry if I overwhelmed your VPS! But seriously, this was super impressive. Well done!

Retr0id23• 4 years ago

It'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

amluto2• 4 years ago

Neat. Following some links:

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.)

nullc• 4 years ago

you need a solution that only applies each available perturbation zero or one times

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.

Retr0id23• 4 years ago

you can solve your underdetermined system of 32 equations with 36 unknowns using your favorite technique

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)

wanderfowl• 4 years ago

This is wildly impressive. Thank you for doing and sharing this, and the 1337 on either end is just icing on the cake. It's also a beautiful example of just how broken MD5 is. I wish I'd had this to show my students 3 weeks ago when teaching about collision attacks.

Looking forward to your next project: SHA3-512 :D

inasio• 4 years ago

Related: Inverting hash functions using SAT and SMT solvers [0]

[0] https://blog.lse.epita.fr/2012/07/31/using-sat-and-smt-to-de...

nextaccountic• 4 years ago

You 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

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

pvillano• 4 years ago

The 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• 4 years ago

Impressive! This is the true “hacking” spirit!

zeven7• 4 years ago

Is there an MD5 hash string that hashes to itself?

AustinDev• 4 years ago

Probably 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.

rileymat22• 4 years ago

It 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.

manimino4• 4 years ago

Neat question. The best answer seems to be an HN thread from 13 years ago (!) which posits that the chance of one existing is ~63%:

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?

Retr0id23• 4 years ago

Funny timing, I was joking about this percentage mere days ago - https://retr0.id/notice/ANnYouw6w2di8XvcNE

manimino4• 4 years ago

Follow-up -- If you repeatedly do MD5(MD5(MD5(something))), how long will it take to find a repeat value?

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...

XCSme3• 4 years ago

This 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?

Retr0id23• 4 years ago

Can an attacker generate a collision having the MD5 hash without knowing the salt?

Depending on how the salt is applied, yes.

XCSme3• 4 years ago

Let's say I append 128 random bytes to the input string.

kadoban4• 4 years ago

Trying to make md5 safe is annoying enough, and has few enough benefits, that it's basically a waste of time.

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).

londons_explore2• 4 years ago

There are no known attacks against MD5 as long as the data you hash is not controllable by the attacker.

You should still use a different hash algorithm though.

mrb2• 4 years ago

That's like saying "There are no known attacks against MD5 as long as you don't try to attack it"

oconnor663• 4 years ago

MD5 is vulnerable to both length extension and chosen prefix collisions, so I think an attacker can generate a collision even without knowing the prefix, just by observing a single output. That said, I'm also pretty sure HMAC-MD5 is still unbroken in practice.

thrdbndndn• 4 years ago

All the reply links other than #2 don't work. Any idea?

Retr0id23• 4 years ago

I 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.

userbinator2• 4 years ago

What's the estimated compute cost currently to do this for SHA-1?

komalkumri• 4 years ago

caster_cp• 4 years ago

This is beautiful. Douglas Hofstadter would be proud. 1337 at the end got me.

9woc2• 4 years ago

Someone did a GIF version before: https://github.com/Rogdham/gif-md5-hashquine

omoikane• 4 years ago

There was also an animated GIF version: https://news.ycombinator.com/item?id=13823704

From this thread: https://twitter.com/i/events/838685002703466497

jabbany• 4 years ago

I 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) kind of flex.

[Bonus] I'm also reminded of this paper: https://vision.cornell.edu/se3/wp-content/uploads/2014/09/ge...

andreareina• 4 years ago

Trying 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• 4 years ago

Sounds like the basilisk collection: https://suricrasia.online/unfiction/basilisk/

lelandbatey• 4 years ago

In 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.

spiddy• 4 years ago

That would be a great, and terrifying at the same time, first contact response message to us.

proof-of-superiority if you will.

woleium3• 4 years ago

same category as this. See if you can spot what's so amazing about it. https://gamefaqs.gamespot.com/snes/588741-super-metroid/faqs...

FabHK• 4 years ago

Wow. First I thought it was only the disclaimer, but it's all the way down. How much work must that have been!?

jtokoph• 4 years ago

I had to Google what was so special about this guide. Now that I know, I'm trying to find some justification to spoil it in this thread.

rntksi• 4 years ago

If it took you a lot of time to notice it like I did: <spoiler> it's the paragraph justification

romwell3• 4 years ago

Thank you for the bonus! This is the best kind of humor :)

anonymous_sorry• 4 years ago

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.

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.

danbruc• 4 years ago

Or they "just" broke the hash algorithm.

panic• 4 years ago

If you define HASH(data) = SHA3(data) xor SHA3(manifest), then the manifest will always have a zero hash. This trick can be useful if you need to create a cycle in a hash-addressed list (e.g., an object-oriented class hierarchy where inheritance is by hash of the class definition—the definition of the base class would have a zero hash and could inherit from itself).

Darkstryder6• 4 years ago

To me this can be done with a simple collision attack (assuming you can fiddle with some bytes inside the manifet file while freezing everything else in advance), which can be found under a second for MD5 with a laptop, and a few hundred thousands dollars of cloud resources for SHA1.

Retr0id23• 4 years ago

No, that takes a preimage attack, which doesn't exist (yet? I'm not too optimistic, personally).

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!

buro9• 4 years ago

One kind of that was when DRM rolled out... my memory is fuzzy on what this is as it's a vague recollection of an article once read and I hope someone will recall it and link it.

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.

h2odragon• 4 years ago

DirectTV Hu card updates: https://threadreaderapp.com/thread/1054964796506939392.html

9woc2• 4 years ago

I did a ELI5 writeup on this. Hope someone finds it useful: https://tongwing.woon.sg/blog/image-which-displays-its-own-m...

Waterluvian• 4 years ago

I found it useful. Thank you so much.

jfdi• 4 years ago

Thank you!

allisdust• 4 years ago

Is this possible only because md5 is weak? Is it possible to do the same with sha2 or sha1?

infofarmer• 4 years ago

Yes. Not yet.

googlryas• 4 years ago

Yup - 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• 4 years ago

Given 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• 4 years ago

This definitely gets extra points, made me snicker... twice. 1337!

eimrine• 4 years ago

Are 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• 4 years 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• 4 years ago

Good 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.

Helmut100012• 4 years ago

Can someone explain why the image displays a Dragon that eats itself? Mere coincidence?

gammalost• 4 years ago

It's a reference to quine. A program which has it's own source as output. A fun brain teaser that I recommend trying

Helmut100012• 4 years ago

Great, thanks. Now this all makes sense.

michaelcampbell• 4 years ago

Neat. 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• 4 years ago

Originally 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)

The image in this post displays its own MD5 hash

Related Stories