1
$\begingroup$

If I have a set of $N$-byte input values to be hashed using SHA-256, then what are the mapping functions for each of the 256 bits of the output?

It seems to me that hashes are one-way partially because we don't know the input size, but if we did know the size to be $N$, then I expect to find a generalized mapping functions for each of the 256 output bits as functions of the $N$ input bits.

To be clear, I am not trying to find an input for a given output - I am happy for a mapping to still be a 1-way function. Say, for 1000 bits of input, each output bit may be a function of all 1000 bits, or perhaps fewer, or perhaps with extra variables (S-box etc):

ox = f(i0, i1,...1N, s0, s1,...)
for the Xth output bit as a function of up to $N$ input bits and other variables.

In theory, should this be possible? If not, why not? If yes, what are some tips to learning all 256 mapping functions from the algorithm?

$\endgroup$
  • 2
    $\begingroup$ Hint: Even restricted to a fixed input size like 256 bits we have no reason to doubt SHA-256's preimage resistance. Try plugging the SHA-256 formula into a SAT solver and see how far you get before the terrible fabled oom killer comes for you in the night, or you get bored of waiting. $\endgroup$ – Squeamish Ossifrage Dec 17 '17 at 6:07
  • $\begingroup$ Thanks @SqueamishOssifrage. First off - love the name! Secondly, the SAT Solver idea was good, and has been discussed on SE here and externally here. I'm linking them in this comment for future readers. Thanks for the insight. $\endgroup$ – hamx0r Dec 18 '17 at 5:06
1
$\begingroup$

No this is not possible.

Basically SHA-2 consists of many rounds where the input is confused using irreversible functions. Each time such an irreversible function is called another variable is introduced. Furthermore these functions are not operating on a single input/output bit (of course) - they are dependent on all the input bits due to the inherent transposition.

So the reverse function will consist of many many variables, that cannot be simplified to a function without one. Any SAT solver will happily break its teeth on it. And that's why you cannot just create a generalized mapping function.

For attacks usually a reduced number of rounds are used, trying to expand them to the full hash later. And if your input $N$ is small enough then you could simply use brute force or an attack using a rainbow table... but that's about it.

$\endgroup$
  • $\begingroup$ Hopefully my "Jip en Janneke" language (language for children) stands up against the critical review by my friends here :) I'm a bit uncertain about my "no SAT-solver can solve this" jumping to "there is why you cannot jut create a generalized mapping function". Any hints welcome. $\endgroup$ – Maarten Bodewes Dec 18 '17 at 10:50
  • $\begingroup$ Thanks for your comment. To clarify, I'm not looking for a reversible mapping (ie I'm not trying to find an input for a given output), but rather looking for a mapping of input bits to each output bit. I've clarified the question and added a form of the mapping I'm looking for. $\endgroup$ – hamx0r Dec 19 '17 at 16:41
  • $\begingroup$ Oh, you mean like this newer question? Sorry, but that I really could not extract that from your question. $\endgroup$ – Maarten Bodewes Dec 19 '17 at 18:28

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.