DEV Community

skaunov
skaunov

Posted on

Cryptopals #42: personal impressions

Atm I just finished #47, and starting #48. But I need a little break, so I decided get back to this notes and publish them for a bit of relaxation. Spoiler: #47 and #48 are on Mr. Bleichenbacher too. So much of him, a genius man, I guess. But these challenges feel like they worth it, no complains.

This one is easy to find a good write-up, so let me describe how I didn't solve it. Actually I'm not unique here, again. (Will add link to a write-up describing the same problem which blocked me.) Though, I completed the code for the solution, and it was a really well math preparation for next challenges.

So here's a couple of question this challenge left me with, and kind of an answer to one of them, describing what blocked me from solving it.

The first of my question was: does it really still present? I mean "We find new instances of it every other year or so.", but when does this statement is still relevant? Then I was caught by surprise how much this padding scheme still in use as default.

So, it's really hard for me to say how wide these intriguing parameters (exponent = 3) are in use since the time challenges were introduced. But if we take a little bit more global look (especially from perspective of following challenges of the set), then we will conclude that entire PKCS1* scheme is a problem. And 'oh, boy', how default is this one. It turns out that given the frequency of its misuse (remember that once a couple of years note?) it were receiving patchy workarounds one by one, making it even more tricky to implement correctly in turn. So the main conclusion seems to be: use other padding schemes! OAEP, PSS, switch to modern cryptography...

It could be not that bad in this particular challenge, but globally it's very illustrative. And the answer... As soon authors didn't mentioned hash to use with the challenge, I stuck with the most default currently: SHA-256. And the thing is it doesn't leave so much space for garbage in the end of the payload, so you basically run out of variations to construct a cube for most of the messages. So maybe sha-256 kind of solves the local problem that was present to us. (Obviously at the time of introduction SHA-1 was the go to choice, and its solution isn't constrained so tightly.)

On the other hand my conclusion(s) should be taken with a bit of salt. I really tried during the challenge to nullify garbage at all (unsuccessfully), then to solve the problem mathematically, and ended up with computational solution. The one thing that was bugging me is that more mathematical checks were telling that there is a solution, but computational were just exhausting the space for it. Maybe it's the one I could revisit later, though I bet the solution indicated by math approach just need some more space for the garbage bytes.

This one last question would be interesting to discuss with other Cryptopals in anyone would drop a look here! Leave a comment, share your experience.

Top comments (0)