3
$\begingroup$

I am given the following problem.

Consider SHA-256 to be a random oracle in a practical application. Construct an (almost) random oracle $\{0,1\}^*→\{0,1\}^{3000}$ based on SHA-256.

Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones? If yes, could I just apply SHA-256 12 times, splitting the input in 12 parts and remove 72 bits, then I will get 3000 bits? Or did I misunderstand?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is this a part of a HW? $\endgroup$
    – kelalaka
    Commented Apr 21, 2020 at 20:20
  • $\begingroup$ @kelalaka The problem is part of a course but it is not homework for any student to hand in. The problem is an exercise and part of a course in cryptography if that counts as "homework" but I don't think so... Because HW/homework is something that a student should hand in right? $\endgroup$
    – Niklas Rosencrantz
    Commented Apr 21, 2020 at 20:39
  • $\begingroup$ Interestingly it seems a homework somewhere but the site doesn't provide the update time. $\endgroup$
    – kelalaka
    Commented Apr 21, 2020 at 20:44
  • 1
    $\begingroup$ @kelalaka My problem set from the course appears to be publicly available and it is exactly the same three exercises but my problem number is 6 instead of 10 which is on the page from your link. $\endgroup$
    – Niklas Rosencrantz
    Commented Apr 21, 2020 at 20:49

1 Answer 1

Reset to default
4
$\begingroup$

Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones?

Yes, that's the meaning of $\{0,1\}^*→\{0,1\}^{3000}$. It would be better to reformulate using the usual shortcut for "digits of zeros and ones": bits. Also, $\{0,1\}^*$ is the set of all bitstrings.

Could I just apply SHA-256 12 times, splitting the input in 12 parts and remove 72 bits, then I will get 3000 bits?

$256\times12-72=3000$, thus you have the domains right. But would that be indistinguishable from a random oracle¹? No. Find how you would make the distinction. Then improve that construction. Ideally, make a proof that if a method could distinguish the refined construction from a random oracle¹, then it could be turned into a method making that distinction for SHA-256.

A random oracle with $k$-bit output is an hypothetical device that accepts a bitstring as input, and

  • if that bitstring was not previously submitted, draws and outputs a random bitstring in $\{0,1\}^k$
  • otherwise outputs the same bitstring as it did for the previous submission of the input bitstring.

¹ With no way to compute SHA-256, and perhaps disregarding the length-extension property of SHA-256, and its input length limitation; some or all of these might be what the question means with "(almost)".

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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