To generate the md5 hash "1a4f182a05210f17ed1397abf900d3ee" I've used three common lowercase English words (rank ≤1000), one username of some Manifold user, and their userId. For example, the following string matches my constraints: "if MayMeta then use saz6JvvXt2Woe0iXUTBz3KqCQ863", but produces a wrong md5 hash: "51fd8fbb0e0a26e3461b0f7c4bcc0095". The relative order of the 3 words, the username, and the userId is not defined. The string matches the following regular expression: ^\w+(?: \w+){4}$
Whoever provides a justified upper bound on how fast the "1a4f182a05210f17ed1397abf900d3ee" md5 hash can be cracked on a modern CPU using the constraints I provided will receive a Ṁ50 manalink from me. Bonus Ṁ50 if they list reasonable assumptions that can lower this upper bound at least 1000-fold.
Whoever first cracks this md5 hash and posts the source string in the comments will receive a Ṁ500 manalink from me.
If this hash is cracked before August 31st, 2023, 23:59:59 UTC then this market will resolve YES, otherwise NO.
* This is a puzzle market, created to raise awareness of md5 hash cracking techniques. I am not sharing the source string with anyone, and it doesn't exist anywhere on the internet. I myself will not bet on this market.
Related questions
🏅 Top traders
| # | Name | Total profit |
|---|---|---|
| 1 | Ṁ623 | |
| 2 | Ṁ30 | |
| 3 | Ṁ22 | |
| 4 | Ṁ17 | |
| 5 | Ṁ16 |
@something612 good job!
The encoded string was my prediction that firstuserhere will climb to #1 spot in the leaderboard by now, which didn't come true :)
How can I send you the Ṁ500 manalink?
@something612 whoops, wasn't aware of this feature. I'm not up to date with Manifold stuff, mostly just maintaining my existing markets :)
Sent you a managram 👌
There were 29572 users on Manifold when I scraped them on Jul 23rd. A brute force search will be searching 1000^3×29572×5! input strings, where the 5! is the number of possible orderings of the 3 words, username and user ID. So that's 3.3×10^15 possible input strings.
Sometimes two or more of the words will be the same (sometimes the username will be the same as one or more words as well), so there aren't always 5! unique permutations, so we're overcounting a bit, but it's pretty insignificant.
My laptop gets through these at a rate of 2 million hashes per second with an implementation in Python (strangely, an implementation in C written by GPT4 is slightly slower). That gives 53 years to check them all.
That's single core, and It's trivially parallelisable, so on a modern CPU it could take less time, approximately by a factor of the number of cores you have.
Given the parallelisability, you could probably get your factor of 1000 by running it on a GPU or ten, or a cluster of 100 10-core computers or similar. But I'm unaware of possible algorithmic speedups.
If you did get your factor of 1000, that would take it down to 19 days - that being within the market's duration makes me think some speedup probably exists that you had in mind when you made the market.
@chrisjbillington that's a really good assessment of the task complexity, and I generally agree with the numbers you derived, so I'm sending you a Ṁ100 manalink through Discord ;)
I would only add that 5! doesn't overcount by "a bit" but actually overcounts by x7.5, cuz 5! / (4*4) = 7.5.
Plus, it's reasonable to assume, that the 3 chosen words are not entirely random, and are not equally probable. So if higher ranked words are prioritized we should expect the correct solution to be found sooner than in ~1000^3*C/2 combinations.
Similarly, it's reasonable to assume that the users are not equally likely to be used for such a market. There are a ton of inactive, dead, temporary, and test accounts that should have the least priority in an efficient search.
Those three considerations alone already can yield a >1000-fold speedup, even before going into solutions that use GPUs.
@ArunJohnson for simplicity let's go with https://simple.wiktionary.org/wiki/Wiktionary:Most_frequent_1000_words_in_English (BNC)
If someone finds a different input with the same hash, would that count?
@jskf any string that matches the stated conditions + produces the said md5 hash would resolve this market YES, but given that the top 1000 most common English words are all of length <=14 (thus the implied max length of the entire string is around 100) I think there will be only one such matching string.