# Attacking Scrypt Under Access Pattern Leakage

Could cache-timing channels (such as exist for certain block ciphers) somehow be made use of in order to extract memory-access pattern information if both the attacker and user are NOT in a shared compute cluster?

Sub-questions:

• If not, how can an attacker do so if they both share one physical machine?
• Is scrypt's memory-hardness exploitable if both the attacker and user are NOT in a shared compute cluster, at all?
• How many memory address locations are required to be known in order to mount an efficient dictionary attack against that user’s scrypt-hashed password in constant space?
• Scrypt uses a hash underneath, not a block cipher. Commented Jun 24, 2016 at 21:16
• Please do no respond so blatantly. Side-channel attacks can also be applied against one-way functions and cache-timing ones are not an exception for that matter. Commented Jun 24, 2016 at 21:18

Did a bit of research and found this paper (published one year after the question was posted). According to it, it is theoretically possible to reduce scrypt to PBKDF2, e.g. eliminate the memory hardness property of scrypt with the use of cache timing attacks.

Expanding more on the content of the paper, it described that the ROMix (in the paper it is denoted as MHMIX) function of scrypt is vulnerable to cache timing attacks. ROMix is described by the below pseudo-code :

   Algorithm scryptROMix

Input:
r       Block size parameter.
B       Input octet vector of length 128 * r octets.
N       CPU/Memory cost parameter, must be larger than 1,
a power of 2, and less than 2^(128 * r / 8).

Output:
B'      Output octet vector of length 128 * r octets.

Steps:

1. X = B

2. for i = 0 to N - 1 do
V[i] = X
X = scryptBlockMix (X)
end for

3. for i = 0 to N - 1 do
j = Integerify (X) mod N
where Integerify (B[0] ... B[2 * r - 1]) is defined
as the result of interpreting B[2 * r - 1] as a
little-endian integer.
T = X xor V[j]
X = scryptBlockMix (T)
end for

4. B' = X


They describe that the following part of ROMix is vulnerable to cache timing attacks :

        j = Integerify (X) mod N
T = X xor V[j]
X = scryptBlockMix (T)


Their analysis is the following :

As previously mentioned, A is the array that gives scrypt its memory-hard property. A stores all the repeated hashes of B, such that A[n] = Mixn (B), where Mixn (B) is the result of hashing B n times (e.g. Mix2 (B) = Mix(Mix(B,I),I)). In the above lines of code, elements of A are chosen to be used in calculation of the scrypt result by interpreting hash results, which are unique to and derived from secret information (the evaluation of PBKDF2 on the user’s password), as integers and using them to index through A (with the variable k). Since these memory accesses are dependent on the password, patterning the memory accesses observed during an execution of scrypt will give information about the result of the evaluation of PBKDF2 in the first step of the scrypt algorithm.

In my opinion their justification on their argument isn't really deep, it's a student paper after all. Let's analyze it a little bit more.

Before we begin, scrypt was specified in this RFC 7914 and also a good reference can be found on its Wikipedia article. First of all, obviously, the memory access is made on this line of code T = X xor V[j]. In the best case scenario what we can get from a cache timing attack is the index j. We have to keep in mind that in this step : T = X xor V[j] the X value that is used is the application of the function scryptBlockMix() on X, N-1 times. For simplicity, let's assume that we are somehow be able to recover the value of X, however note this will never be possible in practice since the j = Integerify(X) function drops a large part of X. Now, we see that in the ideal scenario where we know X and j in the 3rd step, we still don't know the contents of the V array for the T = X xor V[j] operation. From my understanding this attack, in an ideal scenario, reduces the security of scrypt by a few calls to scryptBlockMix depending on the success of the attack and how many js it will be able to capture. It is notable that it offers no information for B' (the returned value), since after the last access to the memory T is XORed with V[j] where we don't know the contents of the V array.

To summarize:

• Does this paper describe a practical attack? : No
• Does this paper describe a method to theoretically bypass the memory-hardness of scrypt? No, in the ideal scenario it may reduce its security by a few calls to scryptBlockMix.

So, I think Maarten Bodewes was correct.