4
$\begingroup$

It's a basic question I guess, but I don't know the answer and I don't think that anyone asked it.

Suppose I built a system, it relies on MD5 for security, suddenly I read am article on how easy are MD5 to crack nowadays.

Not being able to implement other algorithms, I multiply the MD5 hash by Pi, and some Fibonacci sequence then divide it by 0.5 and multiplied it by a random string that I generated using a secure generator. I obtain a totally different string

Then I use a function from my program to reverse all that I have done and then pass the original MD5 Hash to be decrypted.

The example I gave is simple, you can over complicate it as much as you like. Suppose you're a hacker, not knowing what I did to the MD5 hash, would you be able to crack it?

$\endgroup$
  • 1
    $\begingroup$ The problem here is not "could someone crack it" (which without knowledge of what you'd done would usually be quite hard), but "how long can the flaws in the source code remain secret" (which is hard in a different way, you don't get to control it, and there is no principle to base a proof of security on - e.g you cannot even explain to your boss why your protocol is secure). Once someone knows that all they need is a couple of multiplies and then use a known attack on MD5, then your security is broken. I suspect this question is a duplicate, but cannot find what it is a duplicate of . . . $\endgroup$ – Neil Slater Nov 13 '15 at 23:00
  • 7
  • 4
    $\begingroup$ The answer is trivially "yes" since every secure encryption algorithm can be viewed as "added complexity" on top of the flawed identity cipher (which encrypts all plaintext to itself). But that is probably not the answer you wanted.. you need to be an expert to work out how to complicate it in a way that adds security. $\endgroup$ – Thomas Nov 14 '15 at 2:58
  • 2
    $\begingroup$ @Thomas You probably should post The answer… as an answer instead of a comment… it makes up-voting much easier and wraps up the question at the same time. ;) $\endgroup$ – e-sushi Nov 14 '15 at 19:54
  • $\begingroup$ I doubt, most of these comments and answers make much sense for the author of the question. In short: If you're not an expert in cryptography, then most likely don't improve security at all - not even a tiny bit. "It looks different" is not a suitable measure for security. Even classical ciphers achieve that. The most basic rule for using cryptography: "Don't implement it yourself". If you're a software engineer, the best way to handle this is by designing the system s.t. you can exchange your cryptographic library if required. $\endgroup$ – tylo Nov 16 '15 at 12:56
8
$\begingroup$

There's a problem with boundaries here; how much "complication" is allowed? I could argue that SHA-2 is a complication of SHA-1 because they both use a Merkle-Damgård construction and have other similar elements. Then again, they are significantly different internally.

On the other hand the addition of a single bitwise rotation did make SHA-1 significantly more secure. Of course it has now proven to be not secure enough but that was after decades of good service.

SHA-1 differs from SHA-0 only by a single bitwise rotation in the message schedule of its compression function; this was done, according to the NSA, to correct a flaw in the original algorithm which reduced its cryptographic security.

This also shows another problem with the question: what is secure enough? Obviously SHA-1 is not secure enough, but it is at least protected against some attacks on SHA-0. SHA-2 is much more secure than SHA-1, but it is still vulnerable against length extension attacks which SHA-3 is not.

In general you cannot just apply some random function to the inner workings or output of an insecure function. Cryptographic functions need proof (or at least a well reasoned strong indication if a prove cannot be constructed) to be secure. For instance, if the bitwise rotation was only performed on the output of SHA-0 then the result would not have been secure.

So unfortunately the answer is: it depends on the change being made and - in a practical sense - the reasoning behind it.


With regard to your scheme: it only changes the end result of the hash, using operations that - according to your own text - should be reversible. Furthermore, you require the algorithm itself to be secure.

There are two major problems with this:

  • you lack a clear indication why this would make the MD5 hash more secure, trying a lot of mathematical constants and operators would likely break the scheme;
  • keeping the algorithm itself safe breaks the Kerckhoffs principle, you should not rely on keeping the algorithm safe.

Kerckhoffs principle and the reasons for making an algorithm public is clearly explained in this answer on Crypto.

| improve this answer | |
$\endgroup$
  • $\begingroup$ One other example is that even though MD5 is broken, HMAC-MD5 is still secure. $\endgroup$ – Daan Bakker Nov 16 '15 at 1:37
  • 2
    $\begingroup$ @DaanBakker But that's not really due to the merits of HMAC, but rather because HMAC-MD5 aims to be a PRF (and thus derives most of its strength form a key unknown to the attack) whereas MD5 tries to be a collision resistant hash. $\endgroup$ – CodesInChaos Nov 16 '15 at 10:17
  • $\begingroup$ @CodesInChaos: Whould using HMAC-MD5 with a fixed key not still be secure, for the same usage as normal MD5? $\endgroup$ – Nova Nov 16 '15 at 21:06
  • $\begingroup$ @Nova No. A collision in the inner hash trivially turns into a collision of HMAC. What HMAC does fix, even without a key (or a key known to the attacker) is length extension attacks. $\endgroup$ – CodesInChaos Nov 16 '15 at 21:35
1
$\begingroup$

Complicating an Algorithm will not make it more secure. The better approach is to avoid the "Security by Obscurity" approach, assume that your algorithm is publicly accessible. Focus instead on the security of the key such as making sure your code/algorithm during processing doesn't leak important clues about the key.

| improve this answer | |
$\endgroup$
1
$\begingroup$

I'm to answer your question and say that yes, complicating an algorithm can make it secure. But I'm also going to define complicate the way I want to define it, not necessarily the way you want to define it.

The Luby-Rackoff theorem tells us that if we have a good enough round function, you can make a secure cipher with enough rounds. In specific, if your function is a PRF, then three or four rounds is good enough. Of course, if there's a flaw in your function, you need more rounds. The general lesson of LR is that if you build a cipher from a simple function, you can construct a secure cipher out of it with enough rounds.

When my team made Threefish as part of Skein, this was an important part of our idea of the "security budget." We made our function as simple as possible and did lots of rounds. Seventy-two of them, to be exact. Part of our design was always looking at an option with the question, "would you like to do X, or would you like N more rounds?" In almost all cases, more rounds is better.

So there you have my rationale on why yes, you can complicate MD5 into a secure function. Use MD5 as a round function, make a Feistel cipher, then turn that into hash function using MMO or DM chaining and then Alice is your Auntie. You get a secure hash function. It's also going to be slow, by the way, at least four times as slow as MD5. I leave why I picked four as an exercise for you.

However, you didn't do that.

You took an MD5 number, multiplied it by a constant, and then did some other — stuff. I don't quite understand all of what you said, but that's okay. I'll point out that if you multiply by $\pi$ then 0.5, you're really multiplying by $\pi/2$ which is just another constant. I definitely don't understand what you mean by Fibonacci here, and I'll presume that your random string is the same string on every calculation.

So what you've done is construct $MD5'(s) := MD5(s) \times (\pi/2 \times R \times Fib) := MD5(s) \times K$ and you fooled yourself into thinking that because you did a bunch of work generating a constant that it was complicated. Multiplication is simple.

If someone generates an attack on MD5, like stuffing you a collision, then their attack works on your function. In short, what you're calling complicating the function isn't what a mathematician-cryptographer would call complicating it, and you don't make the function secure because you aren't doing enough work.

Does this make sense?

You're much better off picking a modern hash function, like Skein, Blake2, or Keccak.

We'd be best off backing all the way out and ask what problem you're really trying to solve.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.