儲存密碼的方法：Java 的 Scrypt KDF 演算法

使用 Scrypt 的原因可以參考 [1-2]，其中 [2] 是比較主要的原因～
大概是說一般常見的密碼儲存方法是使用 One-Way Hash Function 來把密碼變成一串亂碼，儲存在系統上
但不管使用哪種雜湊演算法，其實都不夠安全～主要原因來自於雜湊演算法的兩點特徵：

1、Recognizability
一般雜湊演算法有著同一個明文不管做幾次雜湊，都可以產出相同的雜湊碼的特性。但這就提供了攻擊者一種攻擊方式，他們可以事先產生好各種雜湊碼，入侵後去對資料庫做比對，比對到一樣的雜湊碼，就可以得知原本使用者使用的密碼是什麼了。

2、Speed
雜湊演算法最常見的用途是作為驗證訊息的正確性的途徑，因此多數都可以很快算出結果。但很快算出結果的意思同時也表示攻擊者在很短的時間內就可以測試很多次密碼。

而常見的解法是 Salting 跟 Stretching～大概就是加上 seed 跟重複做好幾次雜湊。
接著就進入主題～[2] 的建議是做密碼儲存時，使用 Adaptive Key Derivation Functions 是比較安全的選擇
因為 Adaptive Key Derivation Functions 就是同時實作了 Salting 跟 Stretching。
而其中 [2] 作者個人的建議，其中一部分節錄如下：

If you are designing a new system which either relies on encryption to store very sensitive information using a weak secret (user passwords), or where it is imperative that nobody guesses any of the passwords in any reasonable amount of time, you should investigate if there is a solid implementation of scrypt for the language or framework you're using.

看起來好像 Scrypt 蠻威的樣子 XD～所以就先來嘗試使用它了！

純 Java 版的 Scrypt 實作可以從 [3] 下載～使用時也非常簡單：

int N=16384;
int r=8;
int p=1;
// Generate hashed string.
String hashed = SCryptUtil.scrypt("password", N, r, p);
System.out.println("Hashed string: " + hashed);
// Check password.
System.out.println("Check 'password': " + SCryptUtil.check("password", hashed));
System.out.println("Check 'password123': " + SCryptUtil.check("password123", hashed));

輸出如下：

Hashed string: $s0$e0801$NX+j1R4xVJ9Alv8+7DJtYw==$FwubaXLtiAJ47zGrf+/oaCFiQYEH2u5CygM5nFbYwbA=
Check 'password': true
Check 'password123': false

至於上面的 N、r、p 的用途，可以參考看看 [4]。
根據 [4] 的討論中網友 gimpf 的回應，節錄以下關於 N、r、p 的描述：

N: General work factor, iteration count.
r: blocksize in use for underlying hash; fine-tunes the relative memory-cost.
p: parallelization factor; fine-tunes the relative cpu-cost.

大概是說 p 會決定相對的 CPU 使用率、r 會決定相對的記憶體使用量，而 N 好像會決定產生的 hashed string 的強度吧。

N、r、p 的數字範圍，從 [3] 的原始碼中有以下這段檢查：

if (N < 2 || (N & (N - 1)) != 0) throw new IllegalArgumentException("N must be a power of 2 greater than 1");

if (N > MAX_VALUE / 128 / r) throw new IllegalArgumentException("Parameter N is too large");
if (r > MAX_VALUE / 128 / p) throw new IllegalArgumentException("Parameter r is too large");

可以看出 p 會決定 r 的範圍、r 會決定 N 的範圍，而 N 最小不能小於 2，且必須是 2 的次方。

關於執行時間的部份，在我測試的電腦上（Intel Core i7-M620 + 6GB DDR3），產生 hashed string 和驗證密碼的平均時間都約是 250ms 上下。

參考資料：
1、Most secure password hash algorithm(s)?
2、Storing Passwords Securely（中譯版：[翻譯] 安全的儲存密碼 (Storing Passwords Securely)）
3、scrypt
4、What are optimal scrypt work factors?