x/crypto/scrypt: implementation not compliant with RFC 7914?

[michaelsbradleyjr]

See: https://tools.ietf.org/html/rfc7914. In particular, Section 2: scrypt Parameters:

The CPU/Memory cost parameter N ("costParameter") must be larger than 1, a power of 2, and less than 2^(128 * r / 8). The parallelization parameter p ("parallelizationParameter") is a positive integer less than or equal to ((2^32-1) * 32) / (128 * r).

Compare with: https://github.com/golang/crypto/blob/master/scrypt/scrypt.go#L200.

That is, it doesn't enforce N < 2^(128 * r / 8) as far as I can tell (I'm not fluent in Go). In the Go playground I find that N's upper limit when r is 1 is 16777215 such that N=262144, r=1, p=8 won't cause scrypt to choke even though it should per the RFC.

Context: ethereum/go-ethereum#19977.

[bcmills]

CC @bradfitz @agl @FiloSottile

[as]

Amusingly, if the Go implementation isn't RFC compliant, then the reference implementation itself may not be either. It does not seem to check N < 2^(128 * r / 8). Also, I can't find any discussion on why the inequality exists in the first place*

For context[1]:
N is the memory/computing power available
r is described as the latency-bandwidth product of the memory subsystem
p is the level of parallelism

The Go implementation also looks a lot like the reference implementation, and performs similar checks. Here are the sanity checks done with N and r taken from that implementation's source code from the tarsnap archive:

http://www.tarsnap.com/scrypt/scrypt-1.3.0.tgz
crypto_scrypt-ref.c:/crypto_scrypt/

	if ((r > SIZE_MAX / 128 / p) ||
#if SIZE_MAX / 256 <= UINT32_MAX
	    (r > SIZE_MAX / 256) ||
#endif
	    (N > SIZE_MAX / 128 / r)) {
		errno = ENOMEM;
		goto err0;
	}

*The original scrypt paper[1] does not explicit give the inequality N < 2^(128 * r / 8), but the ROMix algorithm defines N as the integer work metric, and limits it to N < 2^(k/8), where k is the bit-length of the hash function's output.

[1] https://www.tarsnap.com/scrypt/scrypt.pdf

[michaelsbradleyjr]

See @tniessen's analysis:

The algorithm ROMix limits N to < 2^(k/8) (section 5), where k is the length of the output produced by BlockMix (section 6), so k = 2 * r * x, where x is the output length of Salsa20/8, so x = 64, yielding the limit 2^(k / 8) = 2^(2 * x * r / 8) = 2^(128 * r / 8). Which is precisely the limit specified in RFC7914.

[as]

This seems like a valid analysis, but I have little bandwidth to verify its soundness at this time. I suggest compiling the reference implementation and verifying that it accepts the non-compliant parameters.

Depending on the results, it could lead to a more-actionable outcome: if there is a bug in the reference implementation, and that implementation changes as a result of that bug, there is more reason to fix that bug in Go.

However, all of these parameters are controlled by the caller outside the package and the "fix" involves reducing the robustness. A simple workaround would be to wrap the function or validate the arguments prior to the function call.

It would be very useful to understand the practical impact of violating the inequality N < 2^(128 * r / 8) to gauge whether this is worth the backwards-incompatible runtime behavior.

[michaelsbradleyjr]

A significant practical impact is that if other implementations follow the spec while Go doesn't that can lead to non-portability between implementations, i.e with respect to parameters passed to scrypt. In fact, it's already happened: the go-ethereum project includes test data that relies on Go's scrypt's non-RFC-compliant behavior, though that wasn't a deliberate choice by go-ethereum's maintainers at the time the test data was generated (several years ago).

When that test data is used with an RFC-compliant implementation there will be an error/exception, e.g. with Node.js' built-in scrypt, introduced in Node v10.5.0.

A simple workaround would be to wrap the function or validate the arguments prior to the function call.

Yes, that's possible, and I've taken that approach. It's rather awkward, though, to explain to users why libraries I'm working on complain about parameters that go-ethereum / Go handles just fine: "sorry, those scrypt parameters are not RFC compliant and won't work with Node's compliant implementation."

I agree that:

It would be very useful to understand the practical impact of violating the inequality N < 2^(128 * r / 8)

Maybe we can loop-in Colin Percival? I could @ mention him (cperciva) but will leave that to your discretion.

[FiloSottile]

We should first ascertain whether the reference implementation has the same bug, and then loop in Colin if so. In that case what we do would depend on whether the reference implementation fixes it, and on the impact of violating the bounds. If the reference implementation is unaffected, we should just fix our implementation to be RFC compliant.

[michaelsbradleyjr]

Sounds good. I don't have a lot of experience with C and am fumbling around a bit trying to "ascertain whether the reference implementation has the same bug".

I'll report back with steps/results if I can confirm one way or another. However, please let me know whether you'll be waiting on me or plan to conduct a test yourselves, as I'll probably need to get some help from a coworker to avoid spending too much time figuring out the tooling. I think it's just a matter of changing some values in scrypt-1.3.0/tests/libscrypt-kdf/sample-libscrypt-kdf.c and then compiling and running it...

[as]

However, please let me know whether you'll be waiting on me or plan to conduct a test yourselves, as I'll probably need to get some help from a coworker to avoid spending too much time figuring out the tooling. I think it's just a matter of changing some values in scrypt-1.3.0/tests/libscrypt-kdf/sample-libscrypt-kdf.c and then compiling and running it...

@michaelsbradleyjr I can do this part, stand by for results.

[as]

To save time, compiling the sample test was achieved by simply running the following commands in the scrypt-1.3.0 directory.

    ./configure --enable-libscrypt-kdf
    make install

When executed, the binary scrypt-1.3.0/tests/libscrypt-kdf/sample-libscrypt-kdf outputs:

scrypt(): success

We edit the source file and add a print statement:

int
main(void)
{
	printf("N=%d r=%d p=%d\n", N, r, p);

We now compile and re-run the program to output whether the scrypt_kdf function succeeds with the default values (expected) and then the subsequent values given by @michaelsbradleyjr

N=16384 r=8 p=1
scrypt(): success

N=262144 r=1 p=8
scrypt(): success

Conclusion: The scrypt_kdf function does not validate the inequality N < 2^(128 * r / 8)

/cc @FiloSottile

[michaelsbradleyjr]

Thank you @as, much appreciated. So, the questions seem to boil down to:

1. Why does the reference scrypt impl not validate the restriction N < 2^(128 * r / 8) per RFC 7914: Section 2: scrypt Parameters?
2. What are the impacts, if any, of violating that inequality?
3. Even if the answer to (2) is "none", what are the implications re: KDF input-portability across RFC compliant vs. non-compliant implementations?
4. Again if the answer to (2) is "none", then could the restriction on N be dropped in a revision to RFC 7914?

---

Noting again that at present re: (2) and (4) there are already real-world implications, e.g. Node.js >= 10.5.0 being compliant vs. Go to-date; c.f. ethereum/go-ethereum#19977 and nodejs/node#28799 (comment).

[michaelsbradleyjr]

@cperciva

[cperciva]

That slipped into the RFC by accident. I think it may have originally been intended to say N < 2^(128 * r * 8), just to ensure that the mod-N reduction is meaningful -- but that condition is trivially satisfied.

We haven't gotten around to submitting an Errata Report for the RFC yet...

[tniessen]

My original analysis that @michaelsbradleyjr referred to in #33703 (comment) was wrong. I actually found the mistake (incorrect conversion between bits/bytes) in the RFC and filed errata a few months ago. See 5971, 5972, and 5973.

[komuw]

Following confirmation by cperciva(#33703 (comment)) should this ticket be closed? cc @michaelsbradleyjr michaelsbradleyjr