Pick and Sort for Graphical Authentication

以下は、Rahartomo らによる論文「Pick and Sort for Graphical Authentication」の詳細な技術的サマリーです。

1. 問題定義

従来のテキストベースの認証（パスワード、PIN）は、記憶のしにくさ、推測やフィッシングへの脆弱性、ユーザーの疲労感という欠点に悩まされています。Passkeys（WebAuthn）や生体認証といった現代の代替手段は改善をもたらしますが、以下のような重大な限界があります。

• Passkeys: 特定のデバイスまたはエコシステムに紐付いており、デバイスが紛失または交換された場合の復旧が困難です。
• 生体認証: ハードウェア、OS、ブラウザからの協調的なサポートがなければ、単独の Web 認証メカニズムとして機能できません。また、生体データが侵害された場合、リセットすることはできません。
• 既存のグラフィカルパスワード: ユーザーが明らかな画像を選択するためエントロピーが低い、単一デバイスシナリオに限定される、複雑なジェスチャーに依存する、または推測しやすい特定の視覚的ホットスポットに依存するなどの問題を抱えています。

著者らは、ログイン速度が重要視されないシナリオ（例：頻度の低いアクセスや二次認証）において、セキュリティ（高エントロピー、推測耐性）と使いやすさ（低い認知的負荷、ゲームのようなインタラクション）の間のギャップを埋めることを目指しています。

2. 手法：「Pick and Sort」方式

著者らは、認識と想起のメカニズムを組み合わせたハイブリッドなグラフィカル認証方式を提案します。

中核的なワークフロー

1. 登録: ユーザーは、カテゴリ化されたプール（例：色、アイコン、形状）から視覚要素のセットを選択し、グリッド内（例：4×4）に特定の空間配置で配置します。
2. 認証: ユーザーは選択した要素を認識し、正確に同じグリッド位置に配置する必要があります。
3. ランダム化: 位置に基づく推測を防ぐため、プロトタイプは各ログイン試行時に要素プールの表示順序をランダム化し、ユーザーが固定された場所の筋力記憶に頼るのではなく、特定のアイテムを能動的に検索することを強制します。

主要な設計特性

• ハイブリッドメカニズム:
  • 認識: ユーザーはプールから選択した画像を識別します（記憶負荷の軽減）。
  • 想起: ユーザーは特定の空間配置を記憶する必要があります（エントロピーの向上）。
• 設定可能性: グリッドサイズ（$n$）と選択する要素の数（$k$）は調整可能です。システムは要素の互いに素なセット（$m$ セット）をサポートします。
• 順序非依存性: 秘密は要素がクリックされた順序ではなく、要素の最終的な配置によって定義されるため、認知的負担が軽減されます。
• エントロピー計算: 理論的なパスワード空間は、互いに素なセットとグリッドの順列を考慮して包含排除の原理を用いて計算されます。この数式は、$m$ セットから $k$ 個の要素を選択して $n \times n$ グリッドに配置するケースを考慮しています。

プロトタイプ実装

• 技術スタック: HTML/CSS/JS（フロントエンド）、Django（バックエンド）、SQLite（データベース）。
• 要素セット: 3 つのキュレーションされたセット：色（40 項目）、アイコン（90 項目）、形状（50 項目）。
• 制約: ユーザーは各セットから少なくとも 1 つの要素を選択し、4×4 グリッドに配置する必要があります。

3. 主要な貢献

1. 新規方式の設計: 認識と想起のバランスを取り、プラットフォーム非依存のグリッドベースのグラフィカル認証手法である「Pick and Sort」の導入。
2. 理論的枠組み: グリッドサイズ、要素選択、セットの制約に基づき、方式の理論的エントロピーを計算するための数学的定式化。
3. 実証的なユーザー調査: 82 名の参加者（未成年を含む）による予備調査。方式の使いやすさ、記憶性、セキュリティ特性を評価。
4. セキュリティ分析: 実証的なシャノンエントロピーと推測性指標（ワークファクター）を用いた、推測攻撃に対する方式の耐性の定量的分析。

4. 結果

この調査には 82 名の参加者が関与し、そのうち 59 名が最初のログイン段階を完了し、43 名がすべての 3 つの段階（登録、1 日目、10 日目、28 日目）を完了しました。

使いやすさとパフォーマンス

• 登録時間: 平均約 50 秒。20 歳未満の若年層は高齢層よりも速かった。
• ログイン時間: 成功した試行の平均約 22 秒。テキストベースの方法よりも遅いものの、段階を通じて一貫していた。
• 成功率:
  • 段階 1（1 日目）: 58% の成功率。
  • 以降の段階（10 日目/28 日目）: 74% に向上。
  • 観察: 成功率は練習によって向上し、28 日間の空白後も方式は記憶され続けていた。
• 維持率: 参加者の 72.88% がすべてのフェーズを完了した。

セキュリティとエントロピー

• 要素選択: ユーザーは通常 3〜5 個の要素を選択した。「黒」が最も頻繁に選ばれた色であった。
• パターンバイアス: ユーザーは単純で再現性のあるパターンを好んだ。
  • 水平線: 23 回。
  • L 字型: 19 回。
  • 対角線: 9 回。
  • 複雑なパターン（正方形など）は稀であった。
• 実証的エントロピー:
  • 観測された固有の秘密の総数: 59。
  • シャノンエントロピー: 5.85 ビット（サンプルサイズに対する理論的最大値に接近）。
  • 推測性: 攻撃者が最も一般的な秘密を最初に推測する場合、以下の回数が必要となる。
    • 10% のアカウントを侵害するには 5 回の推測。
    • 50% のアカウントを侵害するには 29 回の推測。
  • 注: 理論的エントロピーは高い（約 120 ビット）が、実際のエントロピーはユーザーが単純なパターンを好むバイアスによって制限されている。

5. 意義と限界

意義

• アクセシビリティ: この方式は、テキストパスワードを困難に感じるが「ゲームのような」視覚的インターフェースに関与できる特定の人口統計（例：子供、高齢者）に非常に適しています。
• 補完的な役割: Passkeys や生体認証を代替するものではなく、高度なハードウェアサポートが利用できないブラウザベースの環境における、堅牢なフォールバックまたは二次認証手段として機能します。
• 展開可能性: 専用ハードウェアを必要とせず、タッチまたはクリックインターフェースを備えたあらゆるデバイスで動作します。

限界と妥当性への脅威

• 内的妥当性: 参加者は各自のデバイスから遠隔地を使用しており、画面サイズや入力方法にばらつきが生じた。調査後の満足度調査は実施されなかった。
• 外的妥当性: サンプルは大学ネットワークおよび個人的なつながりから抽出されたため、人口統計的多様性が欠けている可能性がある。
• セキュリティの欠陥: この調査は肩越し覗き見（ショルダーサーフィング）などの現実世界の敵対的攻撃をシミュレートしなかった。単純なパターン（線、L 字型）を好む傾向が観測されたことは、ガイダンスなしではユーザーが実効エントロピーを低下させる可能性があることを示唆している。
• 不足している機能: プロトタイプには「パスワードを忘れた場合」のメカニズムが欠けており、誤拒否率（FRR）と誤受入率（FAR）の測定を妨げた。

結論

「Pick and Sort」は、設定可能なグリッドベースのグラフィカル認証方式が、セキュリティと使いやすさの間の実用的なバランスを提供し得ることを示している。ログイン時間は従来の方法よりも長いものの、この方式は頻度の低いアクセスシナリオや特定のユーザーグループに対して有望である。今後の研究は、単純なパターンを抑制するインターフェースの洗練、アクセシビリティのための要素の多様性の拡大、大規模な縦断的研究の実施に焦点を当てる。