Description
lets say for a random permutation of length n, this code takes x seconds to complete (n 100_000).
task 1. you should find a sequence of n numbers, so that this code takes at least 100x seconds to complete.
bonus task: write a similar code using unordered_map that cannot be DOSed.
jeffli6789 on 1:48 PM 07/12/2020: This one is nice! Just give it a really long sequence that has the same numbers and it will hang.
erfan on 9:11 AM 07/13/2020: I really doubt your solution
Please verify that the binary isn't still waiting for more numbers, as it should answer in at most 100 seconds on a modern CPU
Also, the numbers should be carefully chosen, a random or a long sequence won't magically work
Anyway if you're sure, you can post the sequence you used
erfan on 9:17 AM 07/13/2020: As a hint,
The first line of input (stdin) takes n.
After that it reads n numbers, your carefully crafted sequence.
Also, it can be proved that from the set of all sequences of a
fixed length n, the code finishes fastest for the ones with the same numbers repeated
jeffli6789 on 2:14 AM 07/14/2020: I got the idea is to create a lot of collisions to DOS the unordered_map. But yeah, the program itself is a bit slow that I give 10k numbers to it and it never finishes. No matter its a random list or 10k 1s. by the way, if the program can print something when it reads all the input, it would be easier to see whether the solution is correct or wrong. That said, I do not think the program is still waiting for inputs. It just hangs for 10k inputs. Originally, I think it should handle 10k random numbers pretty well, so when I send 10k 1s and it hangs, I thought I solved it.
jeffli6789 on 2:16 AM 07/14/2020: My solution is probably wrong bc I did not trigger the collision in the correct way. But since I get the idea I will skip for this. Nice challenge and thx!
jeffli6789 on 2:22 AM 07/14/2020: Ohhh, my bad, yeah, it is still waiting for input. The problem is if I input too many chars at a time, maybe its truncated. I will get back to this later
erfan on 2:49 AM 07/14/2020: If you are pretty sure that you know how to trigger collision in unordered_map, then congrats!
But I myself, with the knowledge of source code, spent around 2 hrs to find a working solution; the point is you absolutely have to have a deep dive into GCC source code, and that's the whole idea around this crackme.
even if you compile a similar code with a different version of GCC, your current solution might not work.
Sure there are blogs that explain how to trigger lots of collisions for GCC x.y, but AFAIK they don't work for this one.
And still, the bonus task is pretty good. you might hash input integers using SHA1, and then there would absolutely be no way to efficiently find a couple of collisions, let alone lots of them, but the intended way to do this is to make minimal changes to some simple reference unordered_map code.
jeffli6789 on 5:26 AM 07/14/2020: I do not have a working collision method but I remember seeing some materials on this topic so I assume it would not be too hard to make it work. I am not sure whether gcc source code is related. Because I think the relevant implementation is in glibc C++ runtime implementation.
jeffli6789 on 5:27 AM 07/14/2020: Its definitely worth trying to come up with a concrete collision method and a working exploit, though I am not sure how motivated I am to do it. Anyway, thx for the crakcme! If I get back on this I will let you know.
jeffli6789 on 5:33 AM 07/14/2020: btw, if its convenient for you, pls join the crackmes.one discord server (shown on the front page) so we can communicate faster (if you would like) ^_^