OTP の謎を解く: トークンのオフライン生成の背後にあるロジック

こんにちは！別の夕方、家に帰る途中、私は郵便受けをチェックすることにしました。私が言っているのはメールの受信箱のことではなく、郵便配達員が物理的な手紙を入れる昔ながらの実際の箱のことです。そして驚いたことに、そこに何かが入った封筒を見つけました。それを開いている間、私はそれが何十年も遅れたホグワーツからの手紙であることを望みながらしばらく過ごしました。しかし、それが銀行からの退屈な「大人向け」の手紙であることに気づき、私は地球に戻らなければなりませんでした。私は本文をざっと読んで、クールな子供たちのための私の「デジタル専用」銀行が地元市場の最大手によって買収されたことに気づきました。そして、新たな始まりのしるしとして、封筒にこれを追加しました:

使用方法の説明書も添えてあります。

あなたも私と同じで、そのような技術革新に一度も出会ったことがない人のために、この手紙から学んだことを共有させてください。新しい所有者は会社のセキュリティ ポリシーを強制することにしました。つまり、すべてのユーザーがセキュリティ ポリシーを適用することを意味します。今後のアカウントでは MFA が有効になります (ちなみに、それは称賛に値します)。そして、上記のデバイスは、銀行口座にログインする際の 2 番目の要素として使用される 6 桁の長さのワンタイム トークンを生成します。基本的には、Authy、Google Authenticator、2FAS などのアプリと同じように動作しますが、物理的な形状が異なります。

それで、試してみたところ、ログインプロセスはスムーズに進みました。デバイスに 6 桁のコードが表示され、それを銀行アプリに入力すると、ログインできました。万歳!しかし、あることが私に衝撃を与えました。これはどのように機能するのでしょうか?何らかの方法でインターネットに接続しているわけはありませんが、銀行のサーバーで受け入れられる正しいコードを生成することに成功しました。うーん...SIMカードかそれに似たものが入っているのでしょうか？まさか！

私の人生は決して同じではないことに気づき、上で述べたアプリ (Authy とその友達) について疑問に思い始めました。私の内なる研究心が目覚めたので、携帯電話を機内モードに切り替えたところ、驚いたことに、オフラインでもまったく問題なく動作することに気付きました。アプリのサーバーが受け入れるコードを生成し続けているのです。面白いですね！

あなたはどうかわかりませんが、私はワンタイムトークンの流れを常に当然のことだと思っており、実際にそれについてきちんと考えたことはありませんでした（特に最近では、特別な理由がない限り、私の携帯電話にインターネットが接続されていないことはめったにありません）私はアウトドアの冒険をしているのですが）、それが私の驚きの根本的な原因でした。それ以外の場合、生成プロセスは純粋にローカルであり、外部アクターから見て安全であるため、セキュリティの観点からこのように動作することは完全に理にかなっています。しかし、それはどのように機能するのでしょうか?

そうですね、Google や ChatGPT などの最新テクノロジーを使用すると、簡単に答えを見つけることができます。しかし、この技術的な問題は私にとって面白そうだったので、まずは自分で解決してみることにしました。

要件

手元にあるものから始めましょう:

• 6 桁のコードを生成するオフライン デバイス
• これらのコードを受け入れ、検証し、正しい場合に緑色の信号を発するサーバー

サーバー検証部分は、サーバーがオフライン デバイスと比較するために同じコードを生成できる必要があることを示唆しています。うーん、それは役に立つかもしれません。

新しい「おもちゃ」をさらに観察すると、さらに多くの発見がもたらされました:

• 一度オフにしてからオフにすると、通常は前と同じコードが表示されます
• ただし、場合によっては変更されることもあります

私が思いついた唯一の論理的説明は、これらのコードには一定の寿命があるということです。 「1-2-3-...-N」形式でその時間を数えようとした話をしたいのですが、それは真実ではありません。大きなヒントは次のようなアプリから得ました。 Authy and Co、私はそこで 30 秒の TTL を見ました。良い発見です。これを既知の事実のリストに追加しましょう。

これまでの要件をまとめてみましょう:

• 6 桁形式での (ランダムではなく) 予測可能なコード生成
• 生成ロジックは再現可能である必要があり、プラットフォームに関係なく同じ結果を得ることができます
• コードの有効期間は 30 秒です。これは、この時間枠内で生成アルゴリズムが同じ値を生成することを意味します

大きな疑問

わかりましたが、主な疑問は未解決のままです。オフライン アプリはどのようにして他のアプリの値と一致する値を生成できるのでしょうか?彼らの共通点は何でしょうか？

もしあなたが『ロード・オブ・ザ・リング』の世界に興味があるなら、ビルボがゴラムとなぞなぞゲームをして、これを解かせたことを覚えているかもしれません:

これは万物が食いつくものです:
鳥、獣、木、花;
鉄をかじる、鋼を噛む;
硬い石を粉砕して食事にします。
王を殺し、町を廃墟にする、
そして高い山を打ち破る。

ネタバレ注意ですが、バギンズ氏は幸運に恵まれ、偶然正しい答えを思いつきました - 「時間です!」。信じられないかもしれませんが、これはまさに私たちの謎に対する答えでもあります。時計が組み込まれている限り、2 つ (またはそれ以上) のアプリは同じ時刻にアクセスできます。後者は最近では問題になりません。問題のデバイスはそれに適合するのに十分な大きさです。周りを見回してみると、手元の時計、携帯電話、テレビ、オーブン、壁にある時計の時間が同じである可能性が高くなります。私たちはここで何かに夢中になっています。OTP (ワンタイム パスワード) コンピューティングの基礎を見つけたようです!

課題

時間に依存することには特有の課題があります:

• タイムゾーン - どのタイムゾーンを使用しますか?
• クロックは同期が崩れる傾向があり、分散システムではこれが大きな課題です

1 つずつ説明しましょう:

• タイムゾーン: ここでの最も簡単な解決策は、すべてのデバイスが同じゾーンに依存していることを確認することであり、UTC が場所に依存しない適切な候補となる可能性があります
• クロックの同期のずれについては、実際には、それを解決する必要さえなく、ずれが 1 ～ 2 秒以内である限り、避けられないものとして受け入れます。30 秒の TTL を考慮すると許容できるかもしれません。デバイスのハードウェア製造者は、そのようなドリフトがいつ達成されるかを予測できる必要があるため、デバイスはそれを有効期限として使用し、銀行は単純に新しいものと交換するか、それらを接続する方法を用意します。ネットワークに接続して時計を調整します。少なくとも、それが私のここでの一連の思考です。

実装

OK、これで解決したので、時間をベースとして使用してアルゴリズムの最初のバージョンを実装してみましょう。 6 桁の結果に興味があるので、人間が判読できる日付ではなくタイムスタンプに依存するのが賢明な選択のように思えます。そこから始めましょう:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

Go ドキュメントによると、.Unix() は次の値を返します

1970 年 1 月 1 日 (UTC) からの経過秒数。

これは端末に出力されたものです:

Current timestamp:  1733691162

これは良いスタートですが、コードを再実行するとタイムスタンプ値が変わりますが、30 秒間は安定した状態を保ちたいと考えています。さて、簡単な話、それを 30 で割って、その値をベースとして使用しましょう:

// gets current timestamp
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

実行してみましょう:

Current timestamp:  1733691545
Base:  57789718

そしてまた:

Current timestamp:  1733691552
Base:  57789718

基本値は変わりません。少し待ってから、もう一度実行してみましょう:

Current timestamp:  1733691571
Base:  57789719

30 秒のウィンドウが経過したため、基本値が変更されました - うまくいきました!

「30 で割る」ロジックが意味をなさない場合は、簡単な例で説明しましょう。

• タイムスタンプが 1 を返すと想像してください
• 厳密に型指定されたプログラミング言語を使用している場合と同様に、1 を 30 で割ると、結果は 0 になります。整数を整数で割ると別の整数が返され、浮動小数点部分は関係ありません
• これは、タイムスタンプが 0 から 29 の間である間、次の 30 秒間は 0 を取得することを意味します
• タイムスタンプが値 30 に達すると、除算の結果は 1 になり、60 になるまで (2 になります)、以下同様です

これでもっと理解できると思います。

ただし、6 桁の結果が必要であるため、すべての要件がまだ満たされているわけではありません。現在のベースは 8 桁ですが、将来のある時点で 9 桁に達する可能性もあります。 。さて、もう 1 つの単純な数学トリックを使用しましょう。基数を 1 000 000 で割って余りを取得します。リマインダーは 0 から 999 999 までの任意の数値にすることができますが、それより大きくなることはありません。

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

fmt.Sprintf(" d", code) 部分は、コード値が 6 桁未満の場合に備えて先頭にゼロを追加します。たとえば、1234 は 001234 に変換されます。
この投稿のコード全体はここにあります。

このコードを実行してみましょう:

Current timestamp:  1733691162

よし、6 桁のコードを取得できたぞ！でも、ここでは何かがおかしいと思いませんか？私がこのコードをあなたに渡し、あなたが私と同時にそれを実行すると、あなたも私と同じコードを取得することになります。これでは安全なワンタイム パスワードにはなりませんね。ここに新しい要件があります:

• ユーザーごとに結果は異なるはずです

もちろん、ユーザー数が 100 万人を超える場合、これが 6 桁ごとに可能な最大の一意の値であるため、一部の衝突は避けられません。しかし、これらはまれであり、技術的に避けられない衝突であり、現在のようなアルゴリズム設計上の欠陥ではありません。

賢い数学的トリックが単独でここで役立つとは思いません。ユーザーごとに個別の結果が必要な場合、それを実現するにはユーザー固有の状態が必要です。エンジニアであると同時に多くのサービスのユーザーである私たちは、サービスが API へのアクセスを許可するためにユーザーごとに一意の秘密キーに依存していることを知っています。ユーザーを区別するために、このユースケースにも秘密キーを導入しましょう。

秘密鍵

秘密キーを 1 000 000 から 999 999 999 までの整数として生成するための単純なロジック:

// gets current timestamp
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

秘密キー間の重複を防ぐ方法として pkDb マップを使用しており、重複が検出された場合は、一意の結果が得られるまで生成ロジックをもう一度実行します。

このコードを実行して秘密キーのサンプルを取得しましょう:

Current timestamp:  1733691545
Base:  57789718

コード生成ロジック内でこの秘密キーを使用して、秘密キーごとに異なる結果が得られることを確認してみましょう。私たちの秘密鍵は整数型であるため、私たちができる最も簡単な方法は、それを基本値に追加し、残りのアルゴリズムをそのまま維持することです。

Current timestamp:  1733691552
Base:  57789718

秘密鍵ごとに異なる結果が生成されることを確認してみましょう:

Current timestamp:  1733691571
Base:  57789719

結果は私たちが望んでいた通りになりました:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds:
base := current / 30
fmt.Println("Base: ", base)

// makes sure it has only 6 digits:
code := base % 1_000_000

// adds leading zeros if necessary:
formattedCode := fmt.Sprintf("%06d", code)
fmt.Println("Code: ", formattedCode)

魅力的な働きをします!これは、秘密鍵が私のようなユーザーに送信される前に、コードを生成するデバイスに挿入される必要があることを意味します。銀行にとっては、それはまったく問題ではありません。

もう終わりですか?ただし、使用した人工的なシナリオに満足している場合に限ります。アカウントを持っているサービス/Web サイトに対して MFA を有効にしたことがある場合は、Web リソースが、選択した第 2 要素アプリ (Authy、Google Authenticator、2FAS など) で QR コードをスキャンするように求めていることに気づいたかもしれません。 ) アプリにシークレット コードを入力し、その瞬間から 6 桁のコードの生成を開始します。あるいは、コードを手動で入力することもできます。

私がこれを取り上げたのは、業界で使用されている実際の秘密鍵の形式を覗くことが可能であることに言及するためです。これらは通常、次のような 16 ～ 32 文字の長さの Base32 エンコードされた文字列です:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

ご覧のとおり、これは私たちが使用した整数秘密鍵とはまったく異なり、この形式に切り替える場合、アルゴリズムの現在の実装は機能しません。ロジックを調整するにはどうすればよいでしょうか?

文字列としての秘密キー

簡単なアプローチから始めましょう。次の行があるため、コードはコンパイルされません。

Current timestamp:  1733691162

これ以降、PK は文字列型になります。では、それを整数に変換してみませんか?もっとエレガントでパフォーマンスの高い方法はありますが、私が思いついた最も簡単な方法は次のとおりです。

// gets current timestamp
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

これは String データ型の Java hashCode() 実装から大きく影響を受けており、このシナリオには十分です。

調整されたロジックは次のとおりです:

Current timestamp:  1733691545
Base:  57789718

ターミナル出力は次のとおりです:

Current timestamp:  1733691552
Base:  57789718

なるほど、6 桁のコードがありました。うまくいきました。次の時間枠に到達するのを待って、再度実行してみましょう:

Current timestamp:  1733691571
Base:  57789719

うーん...それは機能しますが、コードは基本的に前の値の増分です。これは良くありません。この方法では OTP が予測可能であり、その値があり、それがどの時刻に属するかを知ることは非常に困難です。秘密キーを知らなくても、同じ値の生成を簡単に開始できます。このハックの簡単な疑似コードは次のとおりです:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds:
base := current / 30
fmt.Println("Base: ", base)

// makes sure it has only 6 digits:
code := base % 1_000_000

// adds leading zeros if necessary:
formattedCode := fmt.Sprintf("%06d", code)
fmt.Println("Code: ", formattedCode)

keepWithinSixDigits は、999 999 の次の値が 000 000 であることを確認し、6 桁の制限の可能性内に値を維持します。

ご覧のとおり、これは重大なセキュリティ上の欠陥です。なぜそれが起こるのでしょうか？基本的な計算ロジックを見ると、それが 2 つの要素に依存していることがわかります:

• 現在のタイムスタンプを 30 で割った値
• 秘密鍵のハッシュ

ハッシュは同じキーに対して同じ値を生成するため、その値は定数です。現在の / 30 については、30 秒間は同じ値になりますが、ウィンドウが経過すると、次の値は前の値の増分になります。すると、base % 1_000_000 は見たとおりに動作します。以前の実装 (秘密キーを整数として使用) にも同じ脆弱性がありましたが、テストが不足していたため、それに気づきませんでした。

電流 / 30 を何かに変換して、その値の変化をより目立つようにする必要があります。

分散 OTP 値

それを実現するには複数の方法があり、いくつかのクールな数学トリックが存在しますが、教育目的のため、使用するソリューションの読みやすさを優先しましょう。現在の / 30 を別の変数ベースに抽出し、次のように組み込みます。それをハッシュ計算ロジックに組み込みます:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

このように、基数は 30 秒ごとに 1 ずつ変化しますが、hash() 関数ロジック内で使用された後、実行される一連の乗算により diff の重みが増加します。

更新されたコード例は次のとおりです:

Current timestamp:  1733691162

実行してみましょう:

// gets current timestamp
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

ドーン！なぜここでマイナス値が出たのでしょうか？そうですね、int64 の範囲を使い果たしたようです。そのため、値をマイナスに制限して最初からやり直しました。私の Java 仲間は、hashCode() の動作からこれに精通しています。 修正は簡単です。結果から絶対値を取得します。そうすれば、マイナス記号は無視されます:

Current timestamp:  1733691545
Base:  57789718

修正を加えたコードサンプル全体を次に示します:

Current timestamp:  1733691552
Base:  57789718

実行してみましょう:

Current timestamp:  1733691571
Base:  57789719

もう一度実行して、OTP 値が配布されていることを確認してみましょう:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds:
base := current / 30
fmt.Println("Base: ", base)

// makes sure it has only 6 digits:
code := base % 1_000_000

// adds leading zeros if necessary:
formattedCode := fmt.Sprintf("%06d", code)
fmt.Println("Code: ", formattedCode)

なるほど、ついにまともな解決策ができました!

実際、それは私が手動実装プロセスをやめた瞬間でした。私は楽しみを共有し、何か新しいことを学んだのでした。ただし、それは最善の解決策でもなければ、私が今後も続けていきたい解決策でもありません。とりわけ、これには大きな欠陥があります。ご覧のとおり、ハッシュ ロジックとタイムスタンプ値のせいで、私たちのロジックは常に大きな数値を扱います。つまり、1 または 2 で始まる結果を生成できる可能性は非常に低いことを意味します。より多くのゼロ: 完全に有効であっても、 012345 、 001234 など。そのため、可能な値が 100,000 個足りません。これは、アルゴリズムの可能な結果の数の 10% です。この方法では、衝突の可能性が高くなります。カッコ悪い!

ここからどこへ行くか

実際のアプリケーションで使用される実装については詳しく説明しませんが、興味がある方のために、一読の価値のある 2 つの RFC を紹介します。

• HOTP: HMAC ベースのワンタイム パスワード アルゴリズム
• TOTP: 時間ベースのワンタイム パスワード アルゴリズム

そして、上記の RFC に基づいて意図した方法で動作する疑似コードの実装は次のとおりです。

Current timestamp:  1733692423
Base:  57789747
Code:  789747

ご覧のとおり、これに非常に近づいていますが、元のアルゴリズムではより高度なハッシュ (この例では HMAC-SHA1) が使用され、出力を正規化するためにいくつかのビット単位の演算が実行されます。

セキュリティに関する考慮事項: 自分で構築するのではなく再利用する

しかし、この話を終える前にもう 1 つ取り上げておきたいことがあります。それはセキュリティです。 OTP を生成するロジックを独自に実装しないことを強くお勧めします。それを実行してくれるライブラリがたくさんあるからです。エラーの余地は非常に大きく、悪意のある者によって発見され悪用される脆弱性はすぐそこにあります。

生成ロジックを正しく作成し、テストでカバーしたとしても、他にも問題が発生する可能性があります。たとえば、6 桁のコードを総当たり攻撃するのにどれくらいの時間がかかると思いますか?実験してみましょう:

// gets current timestamp:
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

このコードを実行してみましょう:

Current timestamp:  1733691162

そしてもう一度:

// gets current timestamp
current := time.Now().Unix()
fmt.Println("Current timestamp: ", current)

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

ご覧のとおり、単純なブルートフォース for ループによるコードの推測には約 70 ミリ秒かかります。これは、OTP の寿命よりも 400 倍高速です。 OTP メカニズムを使用するアプリ/Web サイトのサーバーは、たとえば、試行が 3 回失敗した後、次の 5 秒または 10 秒間は新しいコードを受け入れないようにすることで、これを防ぐ必要があります。この方法では、攻撃者は 30 秒以内に 18 回または 9 回の試行しか受けられませんが、これは 100 万個の可能な値のプールには十分ではありません。

他にもこのような見落としがちなものがあります。したがって、繰り返しますが、これを最初から構築するのではなく、既存のソリューションに頼ってください。

とにかく、今日は何か新しいことを学べたことを願っています。この時点から OTP ロジックは謎ではなくなります。また、人生のある時点で、再現可能なアルゴリズムを使用してオフライン デバイスに値を生成させる必要がある場合、どこから始めればよいかがわかります。

この記事を読んでいただきありがとうございます。楽しんでください! =)

追伸新しい投稿を公開するとメールが届きます - ここから購読してください

追記他のクールな子供たちと同じように、私も最近 Bluesky アカウントを作成しました。フィードをもっと楽しくするために協力してください =)

以上がOTP の謎を解く: トークンのオフライン生成の背後にあるロジックの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。