在傳統的、基於帳號登入的驗證（authentication）設計中，服務提供者（service provider）需要在資料庫除存帳號與（可能經過處理的）密碼，然後當使用者嘗試登入時，拿著使用者的輸入與資料庫資料做比對，藉此驗證使用者身份。然而這樣的設計有幾個困境，例如傳輸資料可能被竊聽、密碼儲存方式不對、密碼外洩等問題。於是有個更為先進的方法來解決：Secure Remote Password (SRP) Protocol，其設計理念簡單來說，如果服務提供者沒有密碼，他就不用擔心密碼外洩了！此文將簡述傳統方法的困境，並介紹 SRP 的運作機制。
最為傳統的密碼保存方式是使用 Argon2 或 bcrypt 等 Password Hash 來混淆密碼的明文，然後當使用者嘗試登入時，將使用者的密碼輸入算 hash，並與資料庫中的密碼比對，若兩者一樣則使用者所輸入的密碼是對的。
然而這樣的作法有幾個困境：
- 需要相信伺服器端真的有正確實作 Hash，畢竟使用者常常看不出來密碼如何被儲存。負面案例可以看看：我的密碼沒加密。
- 常見的密碼往往可以暴搜 Hash 或有現成的 rainbow table，雖然 salt 通常可以降低被搜到機率，但也不是萬無一失的。
- 如果通訊被竊聽，則使用者的密碼將直接被獲取，攻擊者可以將其用於下一次的驗證。
若要解決傳統 password hashing 的困境，可以採用 zero-knowledge password proof（ZKPP），其核心概念是，使用者（prover）必須要向服務提供者（verifier）證明他知道密碼的值，同時不揭露任何其他與密碼有關的資訊，也就是連密碼的 hash 都不可以揭露給服務提供者；換言之，連服務提供者都不知道密碼是什麼。
Secure Remote Password (SRP) Protocol 便是一個 ZKPP。它是一種進化版的 Password-authenticated key agreement（或通常被稱為 Augmented PAKE），大概有幾個優點：
- 如同前面一再提起的，服務提供者不會有密碼的任何資訊，所以攻擊者拿到資料庫也只能暴力破解
- 因為沒有密碼透過網路傳輸，所以監聽網路傳輸也沒辦法知道什麼
- 可以驗證所溝通的對象是否是仿冒者，所以使用者可以確定他是在跟服務提供者溝通，反之亦然
- 可以建立一個 session key，雖然這不算是一個 authentication 演算法必備的功能
所以接著來看看 SRP 具體是怎麼運作的。SRP 可以分成三個階段：registration, authentication, and verification，顧名思義，分別意味著身份的初始化、身份驗證、驗證溝通對象。其背後的數學則是建立在 discrete logarithms 之上，等看完下面證明應該就可以感受到其與 ElGamal 的相似度了。
首先一開始大家要共同約定一個 Key derivation function (KDF) $H$ 作為後續運算。
Registration
一開始使用者要向服務提供者註冊，用於之後的身份驗證。在此階段，使用者會根據以下流程產生三個值：
- 隨機生成的 salt $s$
- 給定 password（由使用者自訂）與 salt $s$，計算 $x = H(s, password)$
- 生成一個 SRP group，其包含一個很大的質數 $N$ 與一個 generator $g$，並定義 Multiplier parameter $k$ 為 $H(N, g)$，注意接下來的運算都要 $\mod N$
- 透過 $x$ 與 SRP group $(N, g)$ 生成 Verifier $v=g^x$
- 將 $v, s$ 與 SRP group $(N, g)$ 連同 username 傳送給服務提供者，服務提供者會儲存下來
Authentication
在兩邊都有 $v, s$ 與 SRP group 後，服務提供者便可以在完全看不到密碼的情況下驗證使用者的真實性。其流程大致如下：
- 使用者提供 username，要求服務提供者回傳 salt $s$ 與 SRP group $(N, g)$。
- 給定（使用者已知的）password 與 salt $s$，計算 $x = H(s, password)$ 與 Verifier $v = g^x$。
- 使用者生成一個亂數 $a$，並藉由 SRP group 計算其公開的部份 $A=g^a$，將 $A$ 傳給服務提供者，$a$ 則保密。
- 服務提供者生成一個亂數 $b$ ，並藉由 SRP group 計算其公開的部份 $B=kv + g^b$，將 $B$ 傳給使用者，$b$ 則保密。
所以現在使用者有 $(x, a, A, B)$，服務提供者有 $(v, b, B, A)$，而且服務提供者不知道使用者的密碼。於是下一步我們想要確認兩邊可以 derive 出一樣的數值。
- 兩邊個別計算 $u = H(A,B)$
- 使用者用生成一個 session encryption key $S = H((B - kg^x) ^{(a + ux)})$，服務提供者也生成同樣的 session encryption key $S = H((Av^u)^b)$。
快速說明一下這是怎麼推導出來的。
$$ \begin{aligned} H^{-1}(S) &= (B - kg^x) ^{(a + ux)} \newline &= (B - kv)^{(a + ux)} \quad (\because v=g^x) \newline &= (g^b)^{(a + ux)} \quad (\because B = kv + g^b) \newline &= (g^{(a + ux)})^{b} \newline &= (A (g^{ux}))^{b} \quad (\because A = g^a) \newline &= (A v^{u})^{b} \quad (\because v = g^x) \newline &=H^{-1}(S) \end{aligned} $$
（注意上文的 $H^{-1}$ 只是為了避免整個推導過程都要加 $H$ 而有不必要的版面混亂，實際上因為 $H$ 是個 trapdoor function，所以 $H^{-1}$ 是極為困難）
Verification
在 verification 階段，我們希望能確認兩邊生出來的 $S$ 真的是一樣的，一個簡單的方法是：
- 使用者用 session encryption key 加密一串共同擁有的訊息 $m$（例如 username），傳送給服務提供者。
- 服務提供者解密得訊息 $m$，並驗證其正確性，如果兩者相等則成功，不相等則 authentication 時有誤。
- 服務提供者用 session encryption key 加密一串共同擁有的訊息 $m'$，傳送給使用者。
- 使用者解密得訊息 $m'$，並驗證其正確性，如果兩者相等則成功，不相等則 authentication 時有誤。
如此則使用者與服務提供者都可以確認彼此身份正確。
不過這樣仰賴兩個共同已知的字串。目前的 SRP 協定是由現有資訊直接構造出用於驗證的訊息：
- 使用者計算 $M = H(H(N) \oplus H(g), H(username), s, A, B, S)$，傳給服務提供者
- 服務提供者回傳 $H(A, M, K)$
因為竊聽者不會有 $S$，所以可以保證這個字串只有合法的雙方可以獲得，又只要兩邊有一方是不合法的，就無法推導出此。至此就完成驗證程序。
分析
在上面我們已經討論過為何這個演算法是正確的，接著我們要討論為何他是安全的。
首先，如同前面一再提到，在整個溝通過程中，password 和 $x$ 從未離開使用者的裝置，所以服務提供者不知道，竊聽者不知道，只有使用者自己知道。此外，竊聽者也無法得到 session key $S$，這形同於解 discrete logarithms 難題，也因此無法做 MITM，若有使用錯誤 session key 加密的資料，馬上就會被發現。
如果攻擊者取得服務提供者的資料庫，他也只會看到 $v$，但光有 $v=g^x$，無法回推 $x$，更無法知道使用者的密碼，因此他沒辦法假扮成使用者。然而若有服務提供者的資料庫，則他可以假扮成服務提供者，故對使用者而言，透過其他形式的身份認證來驗證服務提供者（e.g. 透過 HTTPS 連線時檢查 certificate），仍然是需要的。
如果有任何 session key 被攻擊者得知，他也無法回推出密碼，因為 session key 有 hash 過而且 $a,b$ 分別只有使用者與服務提供者暫時知道。基於相同理由，如果使用者密碼不幸外流，也無法回推出過去的 session key。
綜觀上述，SRP 協定是安全的。
雜記
完整的 SRP 協定標準可以看 RFC2945。這個演算法最早由 Tim Wu 發表於 NDSS 1998，也算是蠻有歷史的東西了，可惜到現在我知道的只有 1Password 跟 iCloud 有在使用，目前還是以傳統的 password hashing 為主流（甚至很多連 hash 都沒有…）。其實我蠻早就聽過這個演算法了，只是一直沒有深入研究，因為當時對密碼學的認識還不足以讓我看懂。最近終於定下心來好好讀過一次，並把 SRP 演算法中比較核心的部份記錄下來，希望能稍微幫到一些跟我一樣一開始沒看懂的人。
最後附上幾個知名的 implementation：
參考資料
http://srp.stanford.edu/design.html http://srp.stanford.edu/ndss.html https://medium.com/swlh/what-is-secure-remote-password-srp-protocol-and-how-to-use-it-70e415b94a76 https://blog.amis.com/srp-1f28676aa525