2
$\begingroup$

I would like to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$ such that $p$ is a prime number and $\log_2(p) > 256$. I am wondering if it is a good idea to use the hash function SHA-256.

Since $\log_2(p) > 256$, can I just use the output of SHA-256 and apply the modulo $p$ on it?

I would also like to prevent the all-zero (0000…0000) output from SHA-256, is it correct for example to add the value $1$ to the output of SHA-256? Is there a better way?

$\endgroup$
3
$\begingroup$

A possible method is to build $k=1+\lceil\log_2(p)/256\rceil$ 256-bit hash functions $H_i(x)$ per the HMAC construction, by choosing $k$ arbitrary distinct 512-bit constants $c_i$, by defining $$H_i(x)=\operatorname{SHA-256}\Bigl((c_i\oplus\mathsf{opad})\|\operatorname{SHA-256}\bigl((c_i\oplus\mathsf{ipad})\|x\bigr)\Bigr)$$ then build $$H(x)=\Bigl(\bigl(H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)\bigr)\bmod(p-1)\Bigr)+1$$ where for computation of $\bmod$ the $256k$-bit bitstring $H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)$ is converted to integer per (say) big-endian convention.

$H(x)$ is slightly biased towards zero, but the advantage an adversary can get from that is negligible.


There would be two issues when directly using $H(x)=\operatorname{SHA-256}(x)$ as considered in the question (or $H(x)=\operatorname{SHA-256}(x)\bmod p$ which is equivalent if $\log_2(p)>256$ ):

  • Except for $p$ just above $2^{256}$, it is easy to recognize such $H$ from a random function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$, because $H(x)<2^{256}$.
  • It is quite possible that there exist $x$ with $\operatorname{SHA-256}(x)$ the all-zero 256-bit bitstring, so that $H(x)$ is not in $\mathbb Z_p^*$; however we know no computationally feasible way to exhibit such $x$, thus this might not be a practical issue.
$\endgroup$
  • $\begingroup$ In the RFC 2104, the length of a $c_i$, corresponding to the secret key in HMAC, is equal to 64 bits. It is precised that if the length of $c_i$ if bigger than 64 then we must hash them. So, is it good if I choose randomly 64-bits for all $c_i$? $\endgroup$ – tamhzeo Jun 29 '18 at 17:07
  • 1
    $\begingroup$ @pni: What the above comment says is 64-bit really is the width of the hash's round function, and is taken as 64 bytes as an example in RFC 2104, corresponding to the 512-bit block size of the SHA-256 round function. Thus the HMAC key needs/must not be hashed before being combined with $\mathsf{ipad}$ and $\mathsf{opad}$. $\endgroup$ – fgrieu Jun 29 '18 at 21:38

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.