0
$\begingroup$

Home brewed cryptography is strongly discouraged because it is so easy to get it wrong.

Even if we leverage a known good hash function, one example, sha256, here by referred to as g() and use it in conjunction with a home-brew function b(), we can reduce our security because we have reduced our entropy; example:

g(b('secret')) will be less secure than just g('secret') if b() is collision prone.

Proving (I am not using prove in the strictest mathematical sense) a hash function is more secure than another is a herculean task that requires a lot of time from cryptography experts, and is beyond the scope of this question.

However, let's say no crypto-hash function that suits my needs currently implemented on my platform so I want to home-brew. If I am okay with worse performance, ect, and simply want to ensure it is not less secure than a known good function g() it leverages extensively.

For example, if we define b() to be g(g(g(g(g(g(g(g(g('secret'))))))))) we know that b() is not less secure than g()

Are there a set of quick set of guidelines that can be leveraged to ensure a derivative home-brew function is not less secure than the function it uses?

One example function b() might look something like this where it mainly uses a propriety logic as salt for g() (please do not think that this is intended as a replacement for random salt!!):

b() is defined as g('secret' + b1('secret'))

$\endgroup$
  • $\begingroup$ Note g^n(x) has more collisions than g, it is not trivially at least as secure. $\endgroup$ – Meir Maor Jan 14 '18 at 13:21
1
$\begingroup$

Yes, standard reduction proofs usually do the trick.

Reductions proofs usually work this way: Assume you can break property X of the new primitive, show how this capability (when used as black-box oracle) can be used to break property Y (with X=Y being allowed) on the old / standard primitive. Because property Y holds for the old primitive, you know also know property X holds for the new one by contraposition.

Concretely, you usually want at least collision resistance and preimage resistance.

So let's do an example with collision resistance:
Let $g(x)=f(x)\parallel h(x)$ with $f,g$ being collision resistant. We want to show that $g$ is collision resistant. Assume we have a collision on $g$, that is we know $x\neq x'$ such that $g(x)=g(x')$. Now by construction this means that $f(x)\parallel h(x)=f(x')\parallel h(x')$. Assuming $f$ has a fixed output length (as is usual with hashes), this means that $f(x)=f(x')$ needs to hold, but because we assumed $f$ to be collision resistant, this is clearly impossible and thus $g$ is collision resistant if $f$ is (actually $g$ is collision resistant if at least one of $f,h$ is, but this is about the basic principle).

As for $b(x):=g(x\parallel b_1(x))$, this is obviously collision resistant if $g$ is. Assume we knew $x\neq x'$ such that $b(x)=b(x')$, then we have $g(x\parallel b_1(x))=g(x'\parallel b_1(x'))$ but up to naming this is equivalent to saying $g(y)=g(y')$ which is a collision on $g$ if $y\neq y'$. Now because $y=x\parallel b_1(x)$ and $y'=x'\parallel b_1(x)$ with $x\neq x'$, clearly these are inequal because the leading part(s) consisting of $x$ and $x'$ are unequal. Thus we have constructed a collision on $g$ from a collision on $b$ and because $g$ is assumed to be collision resistant, this means that $b$ is as well.

$\endgroup$
  • $\begingroup$ thanks for the great and timely answer! I have to admit though, it is a little over my head. Also, would you mind letting me know if my final example where the homebrew function is appended to the 'secret' before being passed to the known good function would not be less secure? $\endgroup$ – TheCatWhisperer Jan 12 '18 at 22:01
  • $\begingroup$ @TheCatWhisperer are you asking for preimage resistance or for collision resistance (or some other property / use case of $g(x)=g(x\parallel b_1(x))$? $\endgroup$ – SEJPM Jan 12 '18 at 22:04
  • $\begingroup$ I have no doubt that the above function will be as preimage resistant as the function from which it derives. So I am talking collision resistant as it is much less obvious. does || mean concatenate? $\endgroup$ – TheCatWhisperer Jan 12 '18 at 22:07
  • 1
    $\begingroup$ @TheCatWhisperer yes it does mean concatenate. And for collision resistance in this case I fear one has to look into how these functions are built / find a stronger assumption for $g$ I will look more into that when I have time (-> not right now :( ) $\endgroup$ – SEJPM Jan 12 '18 at 22:10
  • $\begingroup$ we can assume that g is collision resistant (it would likely be sha512) $\endgroup$ – TheCatWhisperer Jan 12 '18 at 22:12

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.