在傳統的、基於帳號登入的驗證(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