md5 - Posted: February Thu 16th 5:19 PM (Never Expires) - Format: text
  1. I am the person who did the original writeup on Heartattack (the OpenSSL bug) and who cracked the MD5 compression function. We are now diving into full MD5.
  3. As we do this, it is now important to start beginning the discussion about where this is ultimately going. Some of you have seen that there is more to this than just OpenSSL, and that the real point is this mathematical technique popping up at the end.
  5. It is pretty important that this stuff gets out. PLEASE CIRCULATE AND TTL THIS. And to make sure people understand we're not going to be wasting their time, we're also going to be posting ZKPs that various crypto standards are broken, so they can see this is for real.
  7. So far MD5 is mostly dead. We can also see the blockchain has been altered, showing that SHA256 is dead. Rumors are floating around of an RSA ZKP by stuff being embedded in the Bitcoin **input** scripts (meaning: holy shit). But, I am not going to post them here just yet, in hopes that the Bitcoin devs can go do something about it before it blows up.
  10. Instead, it is time to get into where this is REALLY going. HOW are we breaking all of these crypto standards?
  13. In short, THE PUNCHLINE:
  16. The entire thing circles around a novel mathematical technique that can be thought of in several equivalent ways:
  18. 1. In dry applied math terms, a huge breakthrough in our understanding of ALL complex systems (cryptographic, biological, sociological, business, neurological, psychological -- anything).
  19. 2. In philosophical terms, an algorithmic version of "the scientific method" itself.
  20. 3. In comp-sci terms, the existence of a "universal algorithm" that can solve a very large class of problems (possibly all of them).
  21. 4. In machine learning terms, something like a "fundamental theorem of machine learning."
  22. 5. In AI terms, the foundation of something like a true, strong AI.
  23. 6. In Silicon Valley terms, literally an algorithmic version of "The Lean Startup," where you throw this algorithm into something like a hash function and have it build, measure, iterate towards the solution.
  24. 7. In cryptographic terms, a "vulnerability" in most current encryption standards, which will need to be patched with a class of strengthened algorithms.
  27. All of these things are actually the same thing. The central idea is simple. You automate the following process:
  29. 1. First, you do a little experiment on the problem you want to solve: hash function you want to break, or part of the brain you want to model, or an A/B test on your marketing campaign, or the song you want to write, or whatever it is.
  30. 2. Then, you gather results.
  31. 3. Then you perform some analytics on how well your experiment worked. How close were you to the mark?
  32. 4. Then, once you have your results, you come up with a hypothesis about what you could tweak to improve it. What if you tried this thing instead?
  33. 5. ITERATE. Go back to #1. Repeat until you get the solution.
  36. This approach is the way humans approach everything. Try things, gather results, change something, try again.
  38. Go A/B test your product, see what works, change things, etc. Bounce this song off of people, see if they like it. Try this technique when engaging in social interaction, see how well it works, if not tweak it. That sort of thing.
  41. The magic technique is essentially:
  43. *** Formalize the above as a computer algorithm, and then have a computer run "science" on your problem trillions of times per second. ***
  45. Let's paint an even clearer picture.
  47. If you're trying to solve a hash function -- well, none of these hash functions are "perfect." They all have patterns which can be exploited to create things like preimage or collision attacks.
  49. So how do you magically find them?
  51. You set this little guy up and throw it into a hash function. It goes in there and tries a bunch of random crap, and then algorithmically does "science." It's almost as though you've created a little person, or a computer "startup" that now needs to "bootstrap." The hash function is "nature," a big forest with trees in it. So how does the little human get out of the woods? It tries everything, trillions of times a second, and iterates in all possible directions, keeping track of what's working and what's not.
  54. Now, if you're used to a lot of BS from the math or crypto community, at this point you're probably intrigued, but you want to see how this works. HOW do you tie it together, how do you formalize it? After all, some of these ideas are great, but sound pretty vague.
  56. You're probably saying: Do an "experiment," then do some kind of "analysis," then "iterate." OK, but *WHAT* experiment do you want to do, *WHAT* is this magic analysis do you perform, and *HOW* do you iterate?
  59. The answer, amazingly, is: JUST USE SCIENCE AGAIN.
  62. Let's look at a real-life example of how this works.
  64. Suppose you're solving a problem. You want to build a great product, or a great marketing campaign, or write a hit single, or whatever it is. But you have no manual, so you just have to dive into the deep end of the pool.
  66. Initially, you try a bunch of stuff, but it's all hit-or-miss. Some things worked, other things didn't.
  68. For example: suppose you write a song, and nobody likes it. You want to tweak it to make it better. But how do you know what "good" even is? How do you analyze the song to determine whether it is "good?" And, if you are going to change it, what do you change? The melody? The harmony? Something else?
  70. Or, suppose you're starting a business, but it's failing. You want to tweak it to not have it fail. But how are you determining how successful it is? What data-driven metrics are you looking at? And if things are not working, what do you iterate? Is it the product? The market? The channel strategy? What?
  75. That is literally the answer. You get that this magic "science" thing involves analyzing and iterating, but you don't know how to do that. So you just do MORE science on those unknown parts. Try a bunch of analysis methods, try iterating in a bunch of random ways. Keep doing it until you figure it out.
  77. And THAT is the central idea. THAT, right there, is what ties it all together. Once you see it -- once it really clicks -- you will spend the rest of your day marveling at how beautiful, and amazing, this universe is that we live in.
  79. To make this intuitive, this is how human beings approach life. If your life sucks, you just go try everything to change it. In business, you change the product, you change the market, you change the melody and the harmony. You try different metrics and see which are most accurate. You just try everything and learn which approaches work.
  81. Every time you run into a problem that you don't know how to solve, you use "science" to solve it.
  84. And THAT is the conceptual idea leading to the mathematical breakthrough described previously. It is an automated system of testing, measuring, and iterating, done trillions of times per second.
  86. Rather than trying literally "everything," we try a random sample of "everything" that gives us good insight within a fairly simple margin of error. And if we don't know how to use the algorithm, we use it again on itself.
  88. The precise formalization of the above concept is something we are calling the "Universal Algorithm," similarly to Turing's Universal Machine.
  91. Now, for those of you REALLY following, there are probably a few questions that come to mind. If we are trying EVERYTHING, how do we even know what counts as "good" within the problem anymore? Is there anything we can hold onto?
  93. The answer is YES, and we'll be digging into that next. This algorithm will be shown to have some basically jaw-dropping mathematical properties, which we will not get into here (and which are being left as a bit of a teaser). Suffice to say that when you apply this algorithm to the SAT problem, things get VERY interesting.
  95. That's it for now, but I hope this stimulates some discussion. Please circulate this around to the machine learning community and get them in here, because we're going to be backing this up by smashing through cryptography standards left and right now.

Enter new version of [ md5 ] :

Paste Options:

Recent Pastes:

14 days ago


27 days ago


185 days ago


207 days ago


221 days ago


223 days ago


230 days ago


260 days ago


1230 days ago