2
$\begingroup$

In this answer, it is mentioned that

Easier instantiation of random oracles. Some security proofs rely on the so-called random oracle model to prove the security of a given scheme. Normally you'd use some artificial construction around a fixed-size hash function to get the desired output size, but with XOFs you can just plug them right in without having to fear any mistakes on your side potentially breaking the proofs (most people don't know/understand in many cases, me included).

and NIST.FIPS.202 says

Extendable-output functions are different from hash functions, but it is possible to use them in similar ways, with the flexibility to be adapted directly to the requirements of individual applications, subject to additional security considerations.

Actually, we can create arbitrary length from the hash functions by $h_0 = H(m)$ then $h_i = H(h|i), i>0$ and the output is $h_0\|h_1\|\ldots$ - I'm not claiming this is collision-free.

At page 24 of the NIST document, however, with the section titled as Additional Consideration for Extendable-Output Functions;

XOFs have the potential for generating related outputs—a property that designers of security applications/protocols/systems may not expect of hash functions.

So;

  • Why XOFs are better than Hash Functions in modeling Random oracles?
Improve this question
$\endgroup$
2
  • $\begingroup$ The title probably should be edited to be more precise. I don't one is inherently "better" than another in the sense that one is more secure (or anything like that). It seems that "more convenient" or some other phrase would be less confusing. $\endgroup$
    – Future Security
    Commented Sep 12, 2019 at 17:52
  • $\begingroup$ @FutureSecurity done $\endgroup$
    – kelalaka
    Commented Sep 13, 2019 at 13:33

1 Answer 1

Reset to default
3
$\begingroup$

Suppose you are instantiating a cryptosystem, such as RSA-FDH signatures with 2048-bit modulus, or EdDSA over a $b$-bit curve for $b \gg 256$ like edwards448, which needs a sizable hash function modeled by a random oracle. But the hash functions available at your disposal are only SHA-2.

  • EdDSA needs a $2b$-bit hash function. For edwards25519, it was enough to use SHA-512, but not for edwards448.

  • RSA-FDH with a 2048-bit modulus needs a ${\approx}2048$-bit hash function. None of the SHA-2 hash functions are big enough for this.

What do you do? In order to instantiate one of these cryptosystems, you have to pick some way to compose the SHA-2 functions into a larger-output hash function. It's not a priori obvious what instantiation to choose.

  1. One might naively choose $H(x) \mathbin\| H(H(x)) \mathbin\| \dotsb \mathbin\| H^n(x)$, but this is manifestly not indifferentiable from a random oracle. (You and I might not choose this, but I have seen people reach for it in practice.)
  2. One might choose $H(x \mathbin\| 1) \mathbin\| H(x \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(x \mathbin\| n)$; of course, one must also choose how wide the numbers are, how they're padded, etc.
  3. One might choose $H(H(x) \mathbin\| 1) \mathbin\| H(H(x) \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(H(x) \mathbin\| n)$ like you suggested, but it's not clear what purpose the extra $H(x)$ serves.

Personally I would choose option (2) with little-endian 64-bit integers, but justifying that choice requires further thought and explanation, and not everyone will make the same choice. With a standard XOF there is no need to think about these questions: you just ask SHAKE128 for as long an output as you want.

This is part of why Ed448 was designed not to use SHA3-512 (in some counter mode or whatever) by analogy with Ed25519's use of SHA-512, but instead uses SHAKE256 with an appropriately long output. The complexity of the OAEP standard arises in part because there were no XOFs available so one had to be invented (the ‘MGF’); it would have been much simpler and easier to understand if XOFs were available.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So, in short, the length issue is plus for Xofs. What about the Xofs' generating related output, isn't it a negative for choice? Actually, my idea was OR, sorry if not clear. $\endgroup$
    – kelalaka
    Commented Sep 11, 2019 at 15:14
  • 2
    $\begingroup$ Not really, because if you want to use it for two separate purposes you can just tag the purposes in the input (‘domain separation’). $\endgroup$
    – Squeamish Ossifrage
    Commented Sep 11, 2019 at 15:17
  • $\begingroup$ So, you are saying related output can be easily mitigated by (‘domain separation’)? $\endgroup$
    – kelalaka
    Commented Sep 11, 2019 at 15:21
  • 2
    $\begingroup$ If $H$ is a random oracle, then the functions $x \mapsto H(\text{‘foo’} \mathbin\| x)$ and $x \mapsto H(\text{‘bar’} \mathbin\| x)$ are independent random oracles (perhaps with slightly smaller inputs). The SHA-3 and related standards already use other mechanisms of domain separation, namely slightly different padding rules, to distinguish SHA3-256 from SHAKE128-256 and to distinguish them both from KMAC128-256. $\endgroup$
    – Squeamish Ossifrage
    Commented Sep 11, 2019 at 15:34

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.