scrypt: `Params::new` rejects valid scrypt parameters due to an incorrect constraint copied from RFC 7914

[smessmer]

Summary

Params::new rejects valid scrypt parameters due to an incorrect constraint copied from RFC 7914. The check n < 2^(128 * r / 8) (i.e. log_n < r * 16) is the result of a bits-vs-bytes unit error in the RFC. The correct bound from the original scrypt paper is N < 2^(128 * r), which is cryptographically irrelevant for all practical parameters. This causes interoperability failures, most notably for r=1 where the incorrect bound rejects log_n >= 16 (i.e. N >= 65536).

Details

The error

In params.rs (lines 88–93), the following check is enforced:

// This check required by Scrypt:
// check: n < 2^(128 * r / 8)
// r * 16 won't overflow since r128 didn't
if (log_n as usize) >= r * 16 {
    return Err(InvalidParams { log_n, r: r as u32, p: p as u32 });
}

This implements the constraint stated in RFC 7914 Sections 2, 5, and 6. However, this constraint contains a unit error.

RFC errata

Three errata have been filed against RFC 7914 documenting this error:

• Erratum 5971 — Section 2
• Erratum 5972 — Section 5
• Erratum 5973 — Section 6

All three recommend removing the upper bound constraint entirely, since the correct bound (N < 2^128 in the tightest case) far exceeds any practical value of N.

Derivation from the original paper

In Colin Percival's original paper (Stronger Key Derivation via Sequential Memory-Hard Functions, BSDCan'09), the generic ROMix algorithm (page 6) requires:

N < 2^(k/8)

where k is in bits — the output length of the hash function H.

For scrypt's concrete SMix (Definition 3, page 10), the hash function is BlockMix, which operates on 2r blocks of 64 bytes = 128r bytes = 1024r bits. Therefore k = 1024r.

Correct substitution: N < 2^(1024r / 8) = 2^(128r)

The RFC authors substituted the byte count (128r) where the bit count (1024r) was needed, arriving at N < 2^(128r / 8) = 2^(16r) — off by a factor of 8 in the exponent.

Practical impact

For r=1:

Bound	Limit	Max log_n
RFC (incorrect)	N < 2^16 = 65,536	15
Correct	N < 2^128	127

This means commonly-used parameters like log_n=18, r=1 (used in Ethereum test vectors) or log_n=20, r=1 are rejected despite being perfectly valid.

For r=8 (the typical value), the incorrect bound gives log_n < 128, which is not a practical limitation — but the check is still wrong in principle.

Note on the Integerify cap

The errata note that for r >= 5, the effective bound is capped at 2^512 rather than 2^(128r), because scrypt's Integerify function interprets only B_{2r-1} — a single 64-byte (512-bit) block — as a little-endian integer. So the complete correct bound is N < 2^(min(128r, 512)), which for the tightest case (r=1) is N < 2^128 — astronomically large and irrelevant in practice.

Precedent in other implementations

• Tarsnap reference C implementation: Does not have this check — only validates N is a power of 2, overflow guards, and r * p < 2^30.
• Go (x/crypto/scrypt): Does not enforce the RFC constraint.
• OpenSSL: Enforces the incorrect RFC constraint. An attempt to remove it was closed after the reported issue was attributed to a separate memory limit.
• Ethereum ecosystem: go-ethereum's test vectors include N=262144, r=1, p=8, which violates the RFC bound (N < 2^16 = 65536 for r=1) despite being perfectly valid. This has caused interoperability issues in strict implementations (go-ethereum#19977, eth-account#181).

Suggested fix

Remove the incorrect bound check (lines 88–93 of params.rs). The correct theoretical bound is irrelevant for all practical parameters, so no replacement check is needed — matching the behavior of the reference C implementation.

[tarcieri]

This seems like a dup of #546

[smessmer]

True it's a duplicate, hadn't seen that. Looks like the author there offered to make a PR but never got a response for whether this fix is desired. Well, in case it is, I created a PR at #867 .