Gyazo の URL はどこまで短くできるか

序論

Gyazo というサービスがあります。
スクリーンショットを共有するためのウェブサービスで、撮ったあとにその URL を共有したい人に送るだけで画像を簡単に共有することができます。

その際の画像の URL は次のようになっています。

http://gyazo.com/587011ed4b960eff36ef351efe393e37

Gyazo というアプリケーションの性質上、このURLが推測可能なものであってはいけません。
Gyazo は画像を特定する部分の文字列が32文字で、この文字列は長ければ長いほど推測が難しくなります。

これを8文字にしてはいけないのでしょうか？8文字であったら口頭で伝えることも可能で、新たな利用方法が生まれるかもしれません。
逆に32文字で本当に推測不可能と言えるのでしょうか？本当は1024文字必要なところをコピペの利便性を考えて32文字にしてしまっているのではないでしょうか。

今回は、この文字列をどの程度まで短くしても推測不可能と言えるのか考えてみたいと思います。

ちなみに数学に関しては高校の知識も危ういので、間違っている可能性があります。そのときはぜひ指摘していただけたらと思います。

この先を読み進める前に、自分がこのサービスを作るとしたらどの程度の文字数にするか考えてみると面白いかもしれません。8文字は明らかにダメだろうと思う方は12文字ではどうでしょうか？16文字は？それとも32文字では不安だから64文字くらいにしますか？

見積もり

推測不可能な文字数を決めるためには以下の3つの値をそれぞれ自分で見積もる必要があります。

アップロードされる画像の数は最大でどの程度になるのか
- この画像数を m とおきます
URL を見つけるために総当たり攻撃を仕掛けられたときに何回までのアクセスを許すのか
- この回数を n とおきます
n回の総当たり攻撃を仕掛けられたときに URL が発見される確率をどの程度に抑えたいのか
- この確率を p とおきます

ここでは

$m = 2^{30} \simeq 1,000,000,000$
$n = 2^{20} \simeq 1,000,000$
$p = 1/2^{14} \simeq 0.006%$

と仮定して考えてみたいと思います。

8文字の場合

仮に8文字だとして考えてみましょう。

Gyazo の場合どうやら16進数のようですので $16 ^ 8 = 4,294,967,296$ 通りの URL が存在しうることになります。
画像の数は $2 ^ {30} = 1,073,741,824$ ですので全体の4分の1が利用されることになります。

これでは直感的にもすぐに URL を探し当てられてしまいそうですね。
この簡単な例でどうやって確率を求められるのか式を考えてみましょう。

1回適当な URL を入力するだけで 25% の確率で見つかってしまいます。式は

$\frac{2 ^ {30}}{16 ^ 8} = 25%$

ですね。
2回試した場合はどうでしょうか？

$1 - (1 - \frac{2 ^ {30}}{16 ^ 8}) ^ 2 = \frac{7}{16} \simeq 44%$

なんか一気に難しくなった気がしないでもないですが、答えはそれっぽいですね。

いや、本当は

$1 - (1 - \frac{2 ^ {30}}{16 ^ 8})(1 - \frac{2 ^ {30}}{16 ^ 8 - 1})$

なのかもしれませんが、最大でも $n = 2 ^ {20}$ 程度の試行回数なので、今回はわかりやすくするため上の式で近似…でも問題ないでしょうか？

10回試して正しい URL が発見される確率は

$1 - (1 - \frac{2 ^ {30}}{16 ^ 8}) ^ {10} \simeq 94%$

です。
つまり8文字では $n \simeq 1,000,000$ 回の試行を $p \simeq 0.006%$ 以下に抑えるなんて到底難しそうです。

必要な文字数を計算する

ここから9文字の場合はどうか、10文字の場合はどうかとやっていっても時間がかかるので、この条件をみたす文字数を x とおきましょう。
それを先ほどの計算式に当てはめてみます。

$1 - (1 - \frac{m}{16 ^ x}) ^ n < p$

これを x を求める式に変形してみましょう。

$x > \log_{16} \frac{m}{1 - \sqrt[n]{1 - p}}$

これくらいは簡単ですよね？
もちろん私はグーグル先生に聞きました。

m, n, p にそれぞれ値を代入して計算してみましょう。Ruby だと

m = 2 ** 30
n = 2 ** 20
p = 1.0 / 2 ** 14
Math.log(m / (1 - (1 - p) ** (1.0 / n)), 16)
  => 15.999988993278293

となりました。ということは

$x > 15.999988993278293$

ですので、文字数が16文字あれば見積もった条件を満たすことになります。

条件を緩めてみる

このサービスは少人数で短期間使うだけだし、せいぜい人力で URL 入れてみるくらいの人しかいないと考えて以下の条件にしてみます。

$m = 1,000$
$n = 100$
$p = 1%$

この場合

$x > 5.8115813621245$

となり、6文字で済むことになります。

文字種を増やしてみる

そもそも URL が16進数でなくてはいけない理由はないし、もっと短くしたいと思えば、文字の種類を増やせば短くできるかもしれません。

16進数: 16
数字 + 英小文字: 36
数字 + 英字: 62

62なんて16の約4倍なんだから、16文字必要だったところが4文字で済んでもいいのではないかと期待が膨らみます。
では計算してみましょう。

数字 + 英小文字: 36
$x > \log_{36} \frac{m}{1 - \sqrt[n]{1 - p}} \simeq 12.38$

数字 + 英字: 62
$x > \log_{62} \frac{m}{1 - \sqrt[n]{1 - p}} \simeq 10.75$

13文字と11文字で期待したほどではないかもしれませんが、短くすることが出来ました。

結論

ということで Gyazo の16進数32文字は十分な文字数だということがわかりました。
そもそもこの文字数は MD5 と同じ 128bit ですので、たかがネットワーク越しの総当たり攻撃で見つかってしまっては困ります。

一方で8文字ではやはり少なすぎました。

計算では16文字となりましたが、設定した見積もりで十分なのか定かではないですし、この計算があっているかどうかの保証が全くありません。
どうしてもという理由がなければ長めにしたほうが安全だと思います。