Cognito の SRP 認証フローを理解する

# はじめに
Cognito の認証では SRP プロトコルに対応しているフローがあります。
SRP ってパスワードが平文でインターネット上を流れないからセキュアなんだろうなぁ、というふわっとした理解で、使用する際も SDK が勝手によしなにやってくれるため、細かいことが何も分かりません。
そこで、SRP とは何ぞや、Cognito ではどうやって使われているんだ、という部分を調べてみました。

# SRP とは
RFC 2945 で定義されていました。
ネットワーク認証方式の１つであり、暗号化されていない通信路でもパスワードを使用した認証を安全に行うためのプロトコルとのことらしいです。
パスワードを直接サーバーに送信するのではなく、特定の計算式に基づいて計算した値にして送信するため、パスワードが通信経路を直接流れることがないとのこと。
クライアントとサーバー間で共有の秘密鍵の生成を行うことができるようです。

なんとなく概要がわかった気がするのでもう少し詳細を見てみます。

>Abstract
>
>   This document describes a cryptographically strong network
   authentication mechanism known as the Secure Remote Password (SRP)
   protocol.  This mechanism is suitable for negotiating secure
   connections using a user-supplied password, while eliminating the
   security problems traditionally associated with reusable passwords.
   This system also performs a secure key exchange in the process of
   authentication, allowing security layers (privacy and/or integrity
   protection) to be enabled during the session.  Trusted key servers
   and certificate infrastructures are not required, and clients are not
   required to store or manage any long-term keys.  SRP offers both
   security and deployment advantages over existing challenge-response
   techniques, making it an ideal drop-in replacement where secure
   password authentication is needed.

https://datatracker.ietf.org/doc/html/rfc2945

## SRP のフロー
SRP の流れを簡単に図示すると以下のようになります。（RFC 等を読んでみての私の理解です。）
```mermaid
sequenceDiagram
    participant A as Client
    participant B as Server
    autonumber
    Note left of A: ユーザー名／パスワードを設定してユーザーを登録する
    A ->> B: ユーザー登録: ユーザー名, パスワード
    Note right of B: Client からの情報をもとにユーザーを登録する
    Note right of B: Salt, Verifier を算出して保存し、ユーザー名から参照できるようにする
    Note left of A: a を生成して A を計算する
    Note left of A: 認証を開始するために、ユーザー名, A を Server に送信する
    A ->> B: 認証開始: ユーザー名, A
　　Note right of B: ユーザー名から Salt, Verifier を取得し、Client に送信する
  　Note right of B: b を生成して B を計算し、Client に送信する
    B -->> A: Salt, Verifier、B
    Note left of A: a と Server から受け取った情報から共通鍵を算出する
  　Note right of B: b と Client から受け取った情報から共通鍵を算出する
   Note over A, B: 共通鍵が一致することを検証する
```

特定の計算式を用いて Client, Server 側で各自計算を行うことで、パスワードの情報を使用した共通鍵の生成を行います。
生成した共通鍵が一致することが確認できれば、その作成に使用したパスワードの値も一致するよね、といった仕組みになっています。

細かい仕様を見てみます。
SRP にはバージョンがあるようで、現在は SRP-6 が主流なようです。Cognito でも SRP-6 が使用されていそうです。
SRP-6 の計算方式に関して、RFC 5054 に分かりやすい記載がありました。

https://datatracker.ietf.org/doc/html/rfc5054#section-2.6

登場する値は以下となります。
>This document uses the variable names defined in [SRP-6]:
>
>      N, g: group parameters (prime and generator)
>
>      s: salt
>
>      B, b: server's public and private values
>
>      A, a: client's public and private values
>
>      I: user name (aka "identity")
>
>      P: password
>
>      v: verifier
>
>      k: SRP-6 multiplier

また、各値を算出する計算式は以下となります。
> The premaster secret is calculated by the client as follows:
>
>        I, P = <read from user>
>        N, g, s, B = <read from server>
>        a = random()
>        A = g^a % N
>        u = SHA1(PAD(A) | PAD(B))
>        k = SHA1(N | PAD(g))
>        x = SHA1(s | SHA1(I | ":" | P))
>        <premaster secret> = (B - (k * g^x)) ^ (a + (u * x)) % N
>
>   The premaster secret is calculated by the server as follows:
>
>        N, g, s, v = <read from password file>
>        b = random()
>        k = SHA1(N | PAD(g))
>        B = k*v + g^b % N
>        A = <read from client>
>        u = SHA1(PAD(A) | PAD(B))
>        <premaster secret> = (A * v^u) ^ b % N

premaster secret と記載があるものが、最終的に求める共通鍵となります。

共通鍵の算出には、Diffie-Hellman 鍵交換が使用されています。
Diffie-Hellman 鍵交換は、離散対数問題を扱うことで暗号化されていない通信路でも安全に暗号鍵を共有するための暗号プロトコルらしいです。
詳細については下記の Wikipedia などを参考にしてください。 

https://ja.wikipedia.org/wiki/%E3%83%87%E3%82%A3%E3%83%95%E3%82%A3%E3%83%BC%E3%83%BB%E3%83%98%E3%83%AB%E3%83%9E%E3%83%B3%E9%8D%B5%E5%85%B1%E6%9C%89

SRP では鍵の計算を行う際に、ユーザーのパスワードの情報を計算に組み込むことで、パスワードをもとにした共通鍵を生成します。(x,v の算出に使用)
Client と Server は各自のみが知っている値（a,b）を計算に使用して算出した値（A,B）を交換し、その値とパスワードの値をもとに共通鍵を作成します。
各自が生成した共通鍵が一致することを確認できれば、その算出に使用したパスワードも一致することとなります。

お互いに交換する値は A,B となり、パスワードや各自のみが知っている値(a,b)が通信路に流れることはありません。
また、A,B が盗聴されたとしても、離散対数問題の困難性によって盗聴者が共通鍵を生成することは困難です。（算出は理論上は可能ですが、現在のコンピュータでは計算に天文学的な時間を要するため、実用的には不可能となります。）


なお、フロー図の 1 にあるように、前提としてユーザー登録の際にはパスワードを Client から Server に送信する必要があります。
Server はパスワードから Verifier を算出して保管します。パスワードは保管しません。
以降の認証では Verifier が計算に使われるため、Server がパスワードを知っている必要はありません。

上記の情報を参考に、Cognito での SRP の実装を見てみます。

# Cognito における SRP

Cognito では InitiateAuth API と RespondToAuthChallenge API を使用することでユーザーを認証することが可能です。
[認証フローはいくつか用意されています](https://docs.aws.amazon.com/ja_jp/cognito-user-identity-pools/latest/APIReference/API_InitiateAuth.html#CognitoUserPools-InitiateAuth-request-AuthFlow)が、SRP プロトコルを使用して認証を行う場合は USER_SRP_AUTH 認証フローを使用します。

認証フローについては詳細が記載された公式ドキュメントもありました。

https://docs.aws.amazon.com/ja_jp/cognito/latest/developerguide/amazon-cognito-user-pools-authentication-flow.html

USER_SRP_AUTH を使用する場合の認証フローを図示すると以下のようになります。

```mermaid
sequenceDiagram
    participant A as Client
    participant B as Cognito
    autonumber
    Note left of A: USERNAME<br>SRP_A<br>SECRET_HASH
    A ->> B: InitiateAuth: USER_SRP_AUTH
    Note right of B: SALT<br>SECRET_BLOCK<br>SRP_B, USERNAME<br>USER_ID_FOR_SRP
    B -->> A: ChallengeName: PASSWORD_VERIFIER
    Note left of A: TIMESTAMP<br>USERNAME<br>PASSWORD_CLAIM_SECRET_BLOCK<br> PASSWORD_CLAIM_SIGNATURE
    A ->> B: RespondToAuthChallenge: PASSWORD_VERIFIER
    Note right of B: tokens
    B -->> A: AuthenticationResult
```

Client → Cognito のリクエストは2回となっており、各 API を必要なパラメータをセットして実行します。
実際に認証を行う際に必要となるパラメータの算出方法については公式ドキュメントに詳細な記載がなさそうでした。
SDK には SRP 認証に必要なパラメータの計算処理の実装がされているようなので、今回は SDK（Amplify JS） の実装を参考に確認します。

https://github.com/aws-amplify/amplify-js/blob/master/packages/amazon-cognito-identity-js/src/AuthenticationHelper.js

フロー図に沿って、各フローでの詳細な処理について説明します。

### 0. ユーザー登録
認証フローの図には登場していませんが、前提としてユーザーが作成されている必要があります。
Cognito では [SignUp API](https://docs.aws.amazon.com/ja_jp/cognito-user-identity-pools/latest/APIReference/API_SignUp.html) がユーザー登録のために使用されます。

ユーザー登録時にはユーザー名とパスワードが設定されます。
この際に、Cognito 側では Salt, Verifier を算出して保存していると考えられます。
Verifier は ユーザー名, Salt, パスワードを使用して以下の計算式で求められます。
>   The verifier (v) is computed based on the salt (s), user name (I),
>   password (P), and group parameters (N, g).  The computation uses the
>   [SHA1] hash algorithm:
>
>        x = SHA1(s | SHA1(I | ":" | P))
>        v = g^x % N

https://datatracker.ietf.org/doc/html/rfc5054#section-2.4

上記の計算式と異なる点として、SDK の実装ではハッシュ化に SHA256 が使われていたので、Verifier の計算もハッシュアルゴリズムは SHA256 が使われていそうです。

また、x の算出時 の SHA1(I | ":" | P) の計算時に、I の前にユーザープールの情報も含めていそうです。具体的には、SHA256( <ユーザープールの情報> I | ":" | P) のような計算となっていそうです。

なお、実際の Cognito 側の実装は知る由もないので、記載している情報が正しいとは限らない点はご了承ください。


### 1. InitiateAuth: USER_SRP_AUTH

認証を開始する際には InitiateAuth API を実行します。
必要なパラメータについては API Reference に記載があります。

https://docs.aws.amazon.com/ja_jp/cognito-user-identity-pools/latest/APIReference/API_InitiateAuth.html

今回は AuthFlow として USER_SRP_AUTH を使用するので、下記の情報をリクエストに含める必要があります。
```
{
    'AuthFlow': 'USER_SRP_AUTH',
    'ClientId': 'xxxx',
    'AuthParameters': {
        'CHALLENGE_NAME': 'SRP_A',
        'SRP_A': 'xxxx',
        'USERNAME': 'xxxx',
    }
}
```
上記のうち、SRP_A に関しては Client 側で計算してあげる必要があります。
それ以外の値に関しては、使用するアプリクライアントやユーザーの情報となります。

#### SRP_A の算出
RFC に記載があった計算式から、SRP_A は以下のように計算すればよさそうです。
```
a = random()
A = g^a % N
```

SDK の実装を見ていきます。

a はランダムな値となります。
128 byte のランダム文字列の mod N を計算した値を使用しているようです。

```
	/**
	 * helper function to generate a random big integer
	 * @returns {BigInteger} a random value.
	 * @private
	 */
	generateRandomSmallA() {
		const hexRandom = randomBytes(128).toString('hex');

		const randomBigInt = new BigInteger(hexRandom, 16);
		const smallABigInt = randomBigInt.mod(this.N);

		return smallABigInt;
	}
```

A の算出に必要な N, g の値については Cognito 側で定義されています。
Cognito 側の SRP_B の計算でも使用される値となるので、独自の値は使えません。こちらの値を使用する必要があります。

```
const initN =
	'FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1' +
	'29024E088A67CC74020BBEA63B139B22514A08798E3404DD' +
	'EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245' +
	'E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED' +
	'EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D' +
	'C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F' +
	'83655D23DCA3AD961C62F356208552BB9ED529077096966D' +
	'670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B' +
	'E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9' +
	'DE2BCBF6955817183995497CEA956AE515D2261898FA0510' +
	'15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64' +
	'ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7' +
	'ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B' +
	'F12FFA06D98A0864D87602733EC86A64521F2B18177B200C' +
	'BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31' +
	'43DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF';

...

	constructor(PoolName) {
		this.N = new BigInteger(initN, 16);
		this.g = new BigInteger('2', 16);
		this.k = new BigInteger(
			this.hexHash(`00${this.N.toString(16)}0${this.g.toString(16)}`),
			16
		);
 
```
N については RFC 3526 で定められた値のようです。

https://datatracker.ietf.org/doc/html/rfc3526#section-4



上記の値を用いて A = g^a % N を計算します。
```
	/**
	 * Calculate the client's public value A = g^a%N
	 * with the generated random number a
	 * @param {BigInteger} a Randomly generated small A.
	 * @param {nodeCallback<BigInteger>} callback Called with (err, largeAValue)
	 * @returns {void}
	 * @private
	 */
	calculateA(a, callback) {
		this.g.modPow(a, this.N, (err, A) => {
			if (err) {
				callback(err, null);
			}

			if (A.mod(this.N).equals(BigInteger.ZERO)) {
				callback(new Error('Illegal paramater. A mod N cannot be 0.'), null);
			}

			callback(null, A);
		});
	}
```

計算結果の A がリクエストに必要な SRP_A の値となります。


### 2. ChallengeName: PASSWORD_VERIFIER
InitiateAuth API のレスポンスとして、下記の情報が返却されます。
```
{
  'ChallengeName': 'PASSWORD_VERIFIER',
  'ChallengeParameters': {
    'SALT': 'xxxx',
    'SECRET_BLOCK': 'xxxx',
    'SRP_B': 'xxxx',
    'USERNAME': 'xxxx',
    'USER_ID_FOR_SRP': 'xxxx'
  }
}
```

Salt はユーザー登録時に Cognito 側で生成された値となります。

SECRET_BLOCK に関しては何の値なのか情報がないのですが、Cognito 独自の値で、恐らく認証の管理を行うためのセッション ID として使われているのではないかと思います。
3 のフローで、生成した共通鍵で SECRET_BLOCK に対して署名を行った値を Cognito に送信します。Cognito 側は署名を検証することで、生成した共通鍵が一致することを確認していると考えられます。

SRP_B については以下の計算式で算出します。
```
b = random()
k = SHA1(N | PAD(g))
B = k*v + g^b % N
```

### 3. RespondToAuthChallenge: PASSWORD_VERIFIER
2 で PASSWORD_VERIFIER チャレンジが返却されたので、RespondToAuthChallenge でチャレンジに応答します。
下記の情報をリクエストに含む必要があります。
```
{
    'ChallengeName': 'PASSWORD_VERIFIER',
    'ClientId': 'xxxx',
    'ChallengeResponses': {
        'TIMESTAMP': 'xxxx',
        'USERNAME': 'xxxx',
        'PASSWORD_CLAIM_SECRET_BLOCK': 'xxxx',
        'PASSWORD_CLAIM_SIGNATURE': 'xxxx'
    }
}
```

https://docs.aws.amazon.com/ja_jp/cognito-user-identity-pools/latest/APIReference/API_RespondToAuthChallenge.html

PASSWORD_CLAIM_SECRET_BLOCK は 2 のレスポンスに含まれる SECRET_BLOCK の値となります。

TIMESTAMP は PASSWORD_CLAIM_SIGNATURE を算出する際に使用したタイムスタンプの値となります。

PASSWORD_CLAIM_SIGNATURE については、算出した共通鍵で SECRET_BLOCK に署名を行った値となります。

#### 共通鍵の算出
RFC の記載から、計算方法は以下となります。
```
u = SHA1(PAD(A) | PAD(B))
k = SHA1(N | PAD(g))
x = SHA1(s | SHA1(I | ":" | P))
<premaster secret> = (B - (k * g^x)) ^ (a + (u * x)) % N
```

SDK の実装を確認します。

共通鍵の算出では下記のメソッドが定義されています。
個別の値の計算で呼び出しているメソッドは実際にコードを見て確認してみてください。
x の算出には、ユーザープールの情報も使用されているようです。
```
/**
 * Calculates the final hkdf based on computed S value, and computed U value and the key
 * @param {String} username Username.
 * @param {String} password Password.
 * @param {BigInteger} serverBValue Server B value.
 * @param {BigInteger} salt Generated salt.
 * @param {nodeCallback<Buffer>} callback Called with (err, hkdfValue)
 * @returns {void}
 */
getPasswordAuthenticationKey(
    username,
    password,
    serverBValue,
    salt,
    callback
) {
    if (serverBValue.mod(this.N).equals(BigInteger.ZERO)) {
        throw new Error('B cannot be zero.');
    }

    this.UValue = this.calculateU(this.largeAValue, serverBValue);

    if (this.UValue.equals(BigInteger.ZERO)) {
        throw new Error('U cannot be zero.');
    }

    const usernamePassword = `${this.poolName}${username}:${password}`;
    const usernamePasswordHash = this.hash(usernamePassword);

    const xValue = new BigInteger(
        this.hexHash(this.padHex(salt) + usernamePasswordHash),
        16
    );
    this.calculateS(xValue, serverBValue, (err, sValue) => {
        if (err) {
            callback(err, null);
        }

        const hkdf = this.computehkdf(
            Buffer.from(this.padHex(sValue), 'hex'),
            Buffer.from(this.padHex(this.UValue.toString(16)), 'hex')
        );

        callback(null, hkdf);
    });
}
 ```

なお、ハッシュ値の計算の実装は以下となりますが、SHA256 が使用されているようです。
```
/**
 * Calculate a hash from a bitArray
 * @param {Buffer} buf Value to hash.
 * @returns {String} Hex-encoded hash.
 * @private
 */
hash(buf) {
    const str =
        buf instanceof Buffer ? CryptoJS.lib.WordArray.create(buf) : buf;
    const hashHex = SHA256(str).toString();

    return new Array(64 - hashHex.length).join('0') + hashHex;
}

/**
 * Calculate a hash from a hex string
 * @param {String} hexStr Value to hash.
 * @returns {String} Hex-encoded hash.
 * @private
 */
hexHash(hexStr) {
    return this.hash(Buffer.from(hexStr, 'hex'));
}
```

共通鍵の算出ができたら、PASSWORD_CLAIM_SIGNATURE を生成します。

#### PASSWORD_CLAIM_SIGNATURE の算出
SECRET_BLOCK に対して算出した共通鍵で署名を行っていることが確認できます。
実装されているファイルが AuthenticationHelper.js とは異なっていたので注意してください。

packages/auth/src/providers/cognito/utils/signInHelpers.ts
```
const hkdf = await authenticationHelper.getPasswordAuthenticationKey({
    username,
    password,
    serverBValue,
    salt,
});

const dateNow = getNowString();

const challengeResponses = {
    USERNAME: username,
    PASSWORD_CLAIM_SECRET_BLOCK: challengeParameters?.SECRET_BLOCK,
    TIMESTAMP: dateNow,
    PASSWORD_CLAIM_SIGNATURE: getSignatureString({
        username,
        userPoolName,
        challengeParameters,
        dateNow,
        hkdf,
    }),
} as Record<string, string>;
```

packages/auth/src/providers/cognito/utils/srp/getSignatureString.ts
```
export const getSignatureString = ({
	userPoolName,
	username,
	challengeParameters,
	dateNow,
	hkdf,
}: {
	userPoolName: string;
	username: string;
	challengeParameters: Record<string, any>;
	dateNow: string;
	hkdf: SourceData;
}): string => {
	const bufUPIDaToB = textEncoder.convert(userPoolName);
	const bufUNaToB = textEncoder.convert(username);
	const bufSBaToB = urlB64ToUint8Array(challengeParameters.SECRET_BLOCK);
	const bufDNaToB = textEncoder.convert(dateNow);

	const bufConcat = new Uint8Array(
		bufUPIDaToB.byteLength +
			bufUNaToB.byteLength +
			bufSBaToB.byteLength +
			bufDNaToB.byteLength,
	);
	bufConcat.set(bufUPIDaToB, 0);
	bufConcat.set(bufUNaToB, bufUPIDaToB.byteLength);
	bufConcat.set(bufSBaToB, bufUPIDaToB.byteLength + bufUNaToB.byteLength);
	bufConcat.set(
		bufDNaToB,
		bufUPIDaToB.byteLength + bufUNaToB.byteLength + bufSBaToB.byteLength,
	);

	const awsCryptoHash = new Sha256(hkdf);
	awsCryptoHash.update(bufConcat);
	const resultFromAWSCrypto = awsCryptoHash.digestSync();
	const signatureString = base64Encoder.convert(resultFromAWSCrypto);

	return signatureString;
};
```


### 4. AuthenticationResult
3 の RespondToAuthChallenge API の結果として、正常に認証されるとトークンが返却されます。
```
{
   "AuthenticationResult": { 
      "AccessToken": "xxxx",
      "ExpiresIn": xxxx,
      "IdToken": "xxxx",
      "RefreshToken": "xxxx",
      "TokenType": "xxxx"
   }
}
```

認証の際には、Cognito 側では共通鍵を算出し、RespondToAuthChallenge API に含まれる PASSWORD_CLAIM_SIGNATURE の署名を検証していると考えられます。
署名が正しいものであると検証できる（= Client と使用している鍵が一致する）ことが確認できれば、共通鍵の算出にはユーザーのパスワードの値が使用されているため、正しいパスワードが使用されていることが確認できたことになります。


# おわりに
Cognito における SRP の実装について調べてみました。
何をやってるかわからないけど、なんか動いてるし安全らしいからヨシ！という状況から、完全に理解した状態になれました。
鍵交換方式のアルゴリズム的な部分など、なかなかに理解に苦労した部分もありましたが、自分の知らないことがわかるようになると楽しいですね。

あくまで、自分で調べてみて理解した情報なので、記載したことが間違っている場合もあることはご了承ください。
もし間違ってる部分がありましたら教えていただけますと幸いです。