5
$\begingroup$

I am trying to understand how scrypt works. I am referring to the Algorithm section of scrypt's Wikipedia page. There I find this BlockMix function:

Function BlockMix(B):
    (B0, ... , B2r-1) ← B
    X ← B2r−1
    for i = 0 to 2r − 1 do
        X ← H(X ⊕ Bi)
        Yi ← X
    end for
    Output ← (Y0, Y2, ... , Y2r−2, Y1, Y3, ... , Y2r−1)

Now, as far as my understanding goes, this means: expand an r-bytes block into its single bytes, namely, B0, ..., B2r-1. Set X to the last byte, and propagate some perturbation by updating X with H(X ⊕ Bi). Finally return the output bytes, somehow shuffled (first the even, then the odds).

What I don't understand is the meaning of that H function. It's nowhere specified what it is. I guess it is a function that inputs one byte and outputs one byte. Is that a commonly known function? H usually stands for hash. Should I just pick any random bijection between the numbers in [0, 255]?

Anyone answering my question might as well consider to add this information to the Wikipedia page, to help the next reader.

Improve this question
$\endgroup$
3
  • $\begingroup$ In the original paper by Percival (tarsnap.com/scrypt/scrypt.pdf) BlockMix(.) is parameterised by a function H which is a hash function (modelled, later, as a random oracle). $\endgroup$
    – ckamath
    Jan 19, 2017 at 15:08
  • $\begingroup$ Ok, that helps. So maybe here blockmix is the implementation of an efficient hash function? $\endgroup$
    – Matteo Monti
    Jan 19, 2017 at 15:19
  • $\begingroup$ I stand corrected: the function ROMix_H(.,.) is the "ideal" sequential memory-hard function (MHF) that comes with a security proof under the assumption that H is a random oracle. Since ROMix_H does not fare well in practice, [Per] introduced (as you point out) a "custom" hash function (HF) called BLOCKMix_{H,r}(.) where H is a HF "which is fast while not possessing excess internal parallelism" ([Per] recommends Salsa20/8). But the drawback is that the resulting MHF (SMix_r(B,N):=ROMix_{BLOCKMix_{H,r}}(B,N)) is not provably memory-hard. I hope this helps. $\endgroup$
    – ckamath
    Jan 19, 2017 at 15:55

1 Answer 1

Reset to default
2
$\begingroup$

I'll sum up the comments: according to the original paper, $H$ is any hash function which, ideally, uses limited parallelism$^1$, with Salsa20/8 being a candidate.

Footnote 1: In order to make the resulting memory-hard function less susceptible to attacks (which make an essential use of parallelism).

Improve this answer
$\endgroup$

Your Answer

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

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