# Is there any known malleability of scrypt outputs?

The scenario is single-use passphrase-based non-interactive message authentication.

The obvious try to do this is to chose a random salt of the appropriate length and send:

concat(workfactor, salt, message,
mac(scrypt(workfactor, salt, passphrase), message)).


That protocol is as secure as scrypt is a non-malleable key derivation function (with regards of changing of workfactor and salt).

1. Is there any publicly known malleability of scrypt?
2. Are there any better protocols for this scenario?
-
The proposed construction nicely fits the intended use case of scrypt. If this construction was unsafe for any reason other than a weakness of the MAC, that would be a blow to scrypt, and very much a surprise. – fgrieu Apr 5 '12 at 6:41
I'm mainly checking if scrypt has been examined in the context of an attacker who can change the stored work factor and salt. $\:$ (It seems to me that in most uses of scrypt, an attacker can't change either of those.) – Ricky Demer Apr 5 '12 at 6:48
Non-malleability w.r.t. to salt follows from the definition of Scrypt and PBKDF2, and the non-malleability of HMAC_SHA256 w.r.t. the message, and some reasonable assumptions. Non-malleability w.r.t. workfactor is more or less difficult to argument, and hard (if possible) to prove, depending on how you map workfactor to various security parameters of Scrypt, and how rigorous the argument needs to be. But beware that any legitimate party holding the passphrase must enforce a minimum workfactor (including the verifier, which could be abused into a passphrase-checking oracle). – fgrieu Apr 6 '12 at 7:25
Well, one could expect/hope that using the verifier as a passphrase-checking oracle would be the only way to exploit the verifier not having a minimum workfactor. $\:$ (I was imagining workfactor determining maxtime, with no memory restriction.) $\;\;$ – Ricky Demer Apr 6 '12 at 21:34
@fgrieu: Would you mind posting something like your comment above as an answer? – Ilmari Karonen Feb 1 '13 at 14:46

Non-malleability of Scrypt w.r.t. to salt (as well as passphrase) follows from the definition of Scrypt (which simply pass that salt to that input of PBKDF2); the definition of PBKDF2 (which uses the salt followed by a non-malleable encoding of an integer as a massage passed to HMAC_SHA256); the non-malleability of HMAC_SHA256 w.r.t. the message; and perhaps some reasonable assumptions also critical to Scrypt's soundness. Non-malleability w.r.t. to salt and passphrase should be a design goal of any good PBKDF.

Non-malleability of Scrypt w.r.t. workfactor is more difficult to argument, and hard (if possible) to prove, depending on how rigorous the argument needs to be, and how one maps the term workfactor to the three security parameters of Scrypt (number of iterations, amount of RAM used, and allowance for parallelization). In my opinion, no attack better than brute force is feasible: this is an issue of provable security only, and entering the workfactor(s) in the salt would restore that.

Beware that in some protocols, independently of any weakness in Scrypt (or whatever PBKDF is used), it could be necessary that a legitimate party holding the passphrase enforce a minimum workfactor, for fear of being abused into a fast passphrase-checking oracle.

I do not know any established PBKDF improving on Scrypt.

-