RandomWalk-Auth

RandomWalk-Auth combines deterministic random walks with the Schnorr identification protocol to deliver passwordless, zero-knowledge authentication. A user remembers only a seed; the browser derives a long random-walk trace from that seed, hashes it into a Schnorr private key, and proves knowledge of the corresponding public key without ever disclosing the seed or the walk. Because the server stores only public keys and ephemeral challenges, even a database leak reveals nothing reusable.

Status: This repository is a research proof-of-concept. The advantages below describe the concept, but the code has not been hardened or formally audited for production use.

Why Random Walks?

• Deterministic but explainable derivation – Turning a memorable seed into a 1,024-step walk and then into a Schnorr key pair lets users re-derive their credentials anywhere without syncing secrets, while still giving a visual narrative for “what happens to my seed?”
• Zero-knowledge by design – Registration uploads only the public key; login reveals only (t, c, s) tuples from the Schnorr Σ-protocol. Even a full backend dump leaks nothing reusable.
• Minimal server state – The server never needs password hashes or encrypted blobs, just (user_id, public_key) plus short-lived challenges, simplifying leakage impact analysis compared with OPAQUE/SRP-style schemes.
• PoC-friendly UX – Random walks create a tangible intermediate artifact for demos/education before the protocol is hardened for production.

Protocol Overview

1. Parameter agreement – Client and server share the RFC 3526 2048-bit MODP group (g = 2, q = (p−1)/2).
2. Key derivation (client only) – The browser runs a 1,024-step seed-driven random walk via seedrandom, hashes the walk with SHA-256, and maps the digest to a Schnorr private key x. The public key is y = g^x mod p.
3. Registration – The client posts (user_id, y) to /register; the seed and walk never leave the device.
4. Interactive proof – For login, the client samples a nonce r, sends the commitment t = g^r mod p to /auth/start, receives a random challenge c, and responds with s = r + c·x mod q at /auth/finish. Acceptance requires g^s ≡ t · y^c (mod p).

This is the classical Schnorr Σ-protocol: it is complete, sound under the discrete-log assumption, and honest-verifier zero-knowledge. Because the private key is deterministically tied to the walk, knowing the seed is equivalent to knowing the witness.

Random-Walk-Derived Keys

• Alphabet: U, D, L, R, S
• Walk length: 1,024 steps (configurable in static/script.js)
• PRNG: seedrandom seeded with the user-provided seed
• Digest material: ${seed}|${walk}
• Private key extraction: x = (int(sha256hex) mod (q−1)) + 1

Changing the seed changes the walk and therefore the key pair, keeping the seed as the user’s sole secret while the server remains stateless beyond the public key.

API Surface

Endpoint	Method	Description
/register	POST	Stores (user_id, public_key); rejects duplicates or malformed keys.
/auth/start	POST	Accepts {user_id, commitment}, returns {session_id, challenge} while caching the tuple for SESSION_TTL_SECONDS.
/auth/finish	POST	Verifies the Schnorr equation with cached data and returns {"result": "success"} or HTTP errors.

Sessions live in SQLite with TTL-based cleanup and per-user limits, and they are always tied to the requesting user_id to block replay.

Running Locally

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
FLASK_APP=app.py flask run --cert=adhoc

Open https://127.0.0.1:5000/ (or another HTTPS/localhost origin) and use the UI to register and authenticate; all cryptographic work happens inside the browser.

Security Properties

• Zero knowledge – Under an honest verifier, the Schnorr protocol leaks no information about x, and the server stores only public keys.
• Forward secrecy of seeds – Stealing the database or intercepting /auth/start traffic does not reveal the seed; each session uses fresh randomness.
• Deterministic enrollment – Users can regenerate keys anywhere by re-entering the seed; no server-side state synchronisation is required.
• Extensibility – The same public keys can back other proofs (signatures, tokens, etc.) without altering seed derivation logic.

Remaining Work

• Harden session storage (e.g., Redis with expiry) for multi-instance deployments.
• Rate-limit /auth/start per user to reduce online guessing.
• Optionally wrap the protocol in WebAuthn or include device-bound secrets for multi-factor flows.
• Commission a formal security review before production use; this repository is still a research prototype.

Operational Notes

• Database schema expectations: delete or migrate old user.db files before upgrading; only users and sessions tables are supported.
• Session storage lives in SQLite with TTL cleanup and a per-user cap of 5 pending proofs.
• HTTPS/localhost is enforced in the browser; run behind TLS when handling real secrets.
• static/seedrandom.min.js is vendored locally to avoid CDN tampering.
• See docs/theory.md for a deeper math/Threat-model discussion (English + Japanese).

---

RandomWalk-Auth (日本語)

RandomWalk-Auth は、決定的なランダムウォークと Schnorr 識別プロトコルを組み合わせ、パスワード不要のゼロ知識認証を実現します。ユーザーはシードだけを覚えておき、ブラウザがシードからランダムウォーク列を生成して秘密鍵を導出、鍵を開示せずに正当性を証明します。サーバーは公開鍵と一時チャレンジしか保持しないため、データベースが流出しても再利用可能な情報は得られません。

ステータス: 本リポジトリは研究的な PoC です。ここで列挙する優位点はコンセプトとして確認できる性質であり、実運用向けのハードニングや正式なセキュリティレビューはまだ行っていません。

ランダムウォークを選ぶ理由

• 決定的かつ説明しやすい導出 — 覚えやすいシードから 1,024 ステップのウォークを生成し、その後に鍵へ写像することで、どの端末でも同じ鍵を再現でき、かつ視覚的に「シードはこう処理される」と説明できます。
• ゼロ知識性を維持 — 登録時に送信するのは公開鍵のみ、ログイン時に動くのは Schnorr Σ プロトコル由来の (t, c, s) だけで、サーバーからシードやウォークを復元する手掛かりは得られません。
• 最小限のサーバー状態 — サーバーが保持するのは (user_id, public_key) と短命チャレンジのみで、パスワードハッシュや暗号化済み秘密を抱え込む必要がなく、漏洩時の影響範囲が明確です。
• PoC としての価値 — ランダムウォークという中間表現があることで、概念説明や教育目的のデモがしやすく、本番向けハードニング前の検証基盤として活用できます。

プロトコル概要

1. パラメータ共有 – クライアントとサーバーは RFC 3526 の 2048bit MODP グループ（g = 2, q = (p−1)/2）を共有します。
2. 鍵導出（クライアントのみ） – ブラウザが seedrandom を用いて 1,024 ステップのランダムウォークを生成し、SHA-256 でハッシュして Schnorr 秘密鍵 x に写像します。公開鍵は y = g^x mod p です。
3. 登録 – クライアントは /register に (user_id, y) を送信し、シードやウォークは送信しません。
4. 対話型証明 – ログイン時はクライアントがノンス r を選び、コミットメント t = g^r mod p を /auth/start に送信、サーバーからチャレンジ c を受け取り、s = r + c·x mod q を /auth/finish へ返答します。検証条件は g^s ≡ t · y^c (mod p) です。

このプロトコルは Schnorr Σ プロトコルそのものであり、完全性・健全性（離散対数仮定）・誠実検証者ゼロ知識性を満たします。秘密鍵はランダムウォークに決定的に結び付いているため、シードの所持と証明者知識は同値です。

ランダムウォーク由来の鍵

• 文字集合: U, D, L, R, S
• ウォーク長: 1,024 ステップ（static/script.js で変更可）
• 疑似乱数: seedrandom（シードで初期化）
• ハッシュ入力: ${seed}|${walk}
• 秘密鍵生成: x = (int(sha256hex) mod (q−1)) + 1

シードを変えればウォークと鍵ペアも完全に変化するため、利用者はシードだけを秘密として保持し、サーバーは公開鍵以外の状態を持つ必要がありません。

API 一覧

エンドポイント	メソッド	説明
/register	POST	(user_id, public_key) を保存。重複ユーザーや不正な鍵は拒否。
/auth/start	POST	{user_id, commitment} を受け取り、{session_id, challenge} を返却しつつ一定時間キャッシュ。
/auth/finish	POST	キャッシュ済みデータで Schnorr 方程式を検証し、成功なら {"result": "success"} を返す。

セッション情報は SQLite 上で TTL 付き・ユーザー ID と紐付けて保持し、リプレイや無制限なセッション滞留を防ぎます。

ローカルでの実行

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
FLASK_APP=app.py flask run --cert=adhoc

https://127.0.0.1:5000/ を開いて UI から登録と認証を行ってください。主要な暗号処理はすべてブラウザ内で完結します。

セキュリティ特性

• ゼロ知識性 – 誠実な検証者の下で Schnorr は秘密鍵 x を漏らしません。サーバーは公開鍵のみを保持します。
• シードの前方秘匿性 – データベース流出や /auth/start 盗聴が起きても、各セッションが新しい乱数を使うためシードや再利用可能な秘密は漏れません。
• 決定的な再生成 – シードを再入力すればどこでも同じ鍵を再生成でき、サーバー側で追加状態を持つ必要がありません。
• 拡張性 – 同じ公開鍵を署名やトークンなど別用途に流用でき、シード導出ロジックを変更する必要がありません。

今後の課題

• 複数インスタンス運用に備えて、有効期限付き Redis などでセッションを堅牢化する。
• /auth/start をユーザー単位でレート制限し、オンライン総当たりを抑制する。
• 必要に応じて WebAuthn でラップする、あるいは端末固有秘密を追加して多要素化する。
• 本番展開前に正式なセキュリティレビューを実施する。

運用上の注意

• サポートする DB スキーマは users と sessions のみ。旧 user.db は削除または移行してください。
• セッションは SQLite 上で TTL 管理され、ユーザーごとに同時 5 件に制限しています。
• ブラウザ側で HTTPS / localhost を強制しているため、実環境では TLS を構成してください。
• static/seedrandom.min.js はリポジトリに同梱し、CDN 改ざんリスクを避けています。
• 詳細な理論背景や脅威モデルは docs/theory.md を参照してください（英語＋日本語）。