Proof-of-Work を利用した CAPTCHA 方式の提案

動作サンプル

本記事の内容を実装とし、動作する状態のサンプルを公開している。
Sakaki – A Cryptographic PoW CAPTCHA system
サンプルは運用停止中のためリンク解除。

はじめに

本記事は、Proof-of-Work (PoW) を利用した CAPTCHA 方式 (PoW CAPTCHA) を提案する。
本記事では、主に以下の内容を取り扱う。

  • CAPTCHA の性質と原理
  • 新たな CAPTCHA 方式の必要性
  • PoW CAPTCHA の提案と実装

CAPTCHA について

自動化された操作とは

機械装置などが人の手を介さずに動作し、何らかの操作を行うことである。
ここでは、プログラムされたコンピューターによる操作を扱う。

  • Web ページクローラー
  • SNS 上などの許可されたロボット
  • SNS 上などのスパム投稿ロボット
  • 不正認証試行ロボット
  • アカウント自動作成ロボット

CAPTCHA とは

自動化された操作を抑止する機構のことである。
従来、操作を行っているのが人であるか否かを判別するものとして実装されている。(これが CAPTCHA の本来の意味である。)

  • 画像によるもの
    変形回転した文字を読み取らせる
    特定の被写体を含む写真を選択させる
  • 音声によるもの
    文字の名前や単語を聞き取らせる
reCAPTCHA
reCAPTCHA

従来の方式の問題点

従来の方式は、昨今急速に進化している深層学習などの機械学習技術によって、自動的に通過できるようになっている。
最新の研究によれば、Google が提供する reCAPTCHA v3 は強化学習によって 95% 以上の確率で通過できる
もとより、機械学習は人間の学習機能を機械で実現しようというものであり、操作を行っているのが人であるか否かを判別する方式は CAPTCHA としての実効性を失いつつある。

PoW CAPTCHA の提案

これからの CAPTCHA

操作を行っているのが人であるか否かを判別する以外の方法によって、自動化された操作を抑止する CAPTCHA 方式が必要である。
そこで本記事は、計算資源を要求することによる CAPTCHA 方式を提案する。
なお、ここでは空間計算資源を要求する (Proof-of-Work/PoW) 方式を考える。

計算資源とは

ある計算を行うために必要な資源のことである。

  • 時間計算資源
    ある計算を行うために必要な時間
    その量を時間計算量という
  • 空間計算資源
    ある計算を行うために必要な情報の記憶領域
    その量を空間計算量という

PoW とは

時間のかかる計算をさせ、その結果を検証することである。

  • 大きな素数の生成
  • 大きな合成数の素因数分解
  • 暗号学的一方向性関数の計算値の逆算
    Bitcoin をはじめとした多くの暗号通貨の採掘及び合意形成方式に採用

PoW CAPTCHA の先例

Coinhive

  • Web ページに設置したスクリプトによって暗号通貨 Monero を採掘
  • Monero の採掘は PoW 方式
  • これをそのまま Coinhive captcha として転用したものが公式に存在
  • 資金難のため 2019 年 3 月 8 日 (UTC) にサービス終了

法的な問題

Coinhive 事件

  • 神奈川県警察など全国の警察がウェブサイトに Coinhive を設置した運営者ら 21 名を検挙
  • 警察と検察は Coinhive の設置が不正指令電磁的記録に関する罪に当たると主張
  • このうち 1 事件について横浜地裁が無罪判決も検察側が控訴し未だ進行中 (2019 年 4 月現在)

PoW CAPTCHA の実装

必要なこと

安全性

  • 十分な検証

低コスト

  • 小さなプログラム
  • 少ない要求記憶領域
  • 低消費電力

公平性

  • 最小の環境による格差

一方向性関数とは

PoW を実現するために、一般には暗号学的ハッシュ関数などの一方向性関数を利用する。

これは、

y = f(x)
より
x から y を求めるのは簡単であるが
y から x を求めるのは難しい

というものである。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です