# Random oracle based on SHA-256

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?

• Is this a part of a HW? – kelalaka Apr 21 '20 at 20:20
• @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? – Niklas R. Apr 21 '20 at 20:39
• Interestingly it seems a homework somewhere but the site doesn't provide the update time. – kelalaka Apr 21 '20 at 20:44
• @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. – Niklas R. Apr 21 '20 at 20:49

## 1 Answer

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)".