3 ms·

Hi everyone - I go into slightly more detail on my twitter thread on the same topic: https://twitter.com/David3141593/status/1573218394358386688 https://twitter

Hi 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 ago
Was the 1337 at either end of the hash intentional?
- Retr0id 4y ago
  Yes
- deleted 4y ago
  [deleted]
kstrauser 4y ago
Sorry if I overwhelmed your VPS! But seriously, this was super impressive. Well done!
- Retr0id 4y 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
  - kstrauser 4y ago
    My Mastodon instance cries in how little RAM you're able to run that on. I'm envious.
    - tetha 4y ago
      Stuff like that is turning into one of our running gags at work. You have all these machine learning processes and our legacy java applications gobbling up memory by the dozen of gigabytes, or our newer java apps being a bit less greedy but still gigabyte sized - and it's never enough. And 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.
      - hbogert 4y ago
        It's still ridiculous that we ever thought giving Java processes so much memory was normal. I'm very happy golang and rust are getting more main stream.
        tetha 4y ago
        Indeed. In some cases, I find the memory need to be plausible. For example, our logging ES has nodes running with 32GB of heap, but these nodes are indexing and searching ~900GB of logs each. That's, per node, actually in line with our larger postgres instances, running at 32 - 64GB or memory on 600GB - 800GB of dataset. Or our logstash needs 4-8G go go through 2k messages per second. 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%.
  - NavinF 4y ago
    > 768M (╯°□°）╯︵ ┻━┻
  - exikyut 4y ago
amluto 4y 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 4y 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.
- Retr0id 4y ago
wanderfowl 4y 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

TheSpiceIsLife 4y ago

Was the 1337 at either end of the hash intentional?

Retr0id 4y ago
Yes
deleted 4y ago
[deleted]

kstrauser 4y ago

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

Retr0id 4y 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
- kstrauser 4y ago
  My Mastodon instance cries in how little RAM you're able to run that on. I'm envious.
  - tetha 4y ago
    Stuff like that is turning into one of our running gags at work. You have all these machine learning processes and our legacy java applications gobbling up memory by the dozen of gigabytes, or our newer java apps being a bit less greedy but still gigabyte sized - and it's never enough. And 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.
    - hbogert 4y ago
      It's still ridiculous that we ever thought giving Java processes so much memory was normal. I'm very happy golang and rust are getting more main stream.
      - tetha 4y ago
        Indeed. In some cases, I find the memory need to be plausible. For example, our logging ES has nodes running with 32GB of heap, but these nodes are indexing and searching ~900GB of logs each. That's, per node, actually in line with our larger postgres instances, running at 32 - 64GB or memory on 600GB - 800GB of dataset. Or our logstash needs 4-8G go go through 2k messages per second. 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%.
- NavinF 4y ago
  > 768M (╯°□°）╯︵ ┻━┻
- exikyut 4y ago

amluto 4y 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 4y 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.
Retr0id 4y ago

wanderfowl 4y 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