トークンをデータベースに保存する際のベストプラクティスを考えてみた
はじめに
あるイベントで、UUID4に基づいて生成したトークンをハッシュ化する際にソルトが必要かについて議論が交わされました。本記事では、トークンを安全に保存するためにはどのような手法が安全かつ効率的か調査した結果を共有します。
用語
この記事を読んでいく上で最低限知っておく必要があることを書いておきました。すでに知っているよという方は次の章へ進んでください。
UUID
UUIDはウィキペディアで以下のように紹介されています。
UUID（Universally Unique Identifier）とは、ソフトウェア上でオブジェクトを一意に識別するための識別子である。UUIDは128ビットの数値だが、16進法による550e8400-e29b-41d4-a716-446655440000というような文字列による表現が使われることが多い。元来は分散システム上で統制なしに作成できる識別子として設計されており、したがって将来にわたって重複や偶然の一致が起こらないという前提で用いることができる[1]。
簡単にまとめると、重複が起こらないという前提で用いることができるオブジェクトを識別するための識別子です。長さは128ビットで、16進数表記されることが多いです。
UUIDの標準化として、RFC4122が公開されています[1]。PythonのUUIDはRFC4122に基づいて実装されています[2]。
UUID4はUUIDの中でもランダム性に富んでおり、128ビットのうち4ビットのバージョン情報と2ビットのバリアントを除いた122ビットが乱数または擬似乱数の値となっています。したがって、UUID4の取りうる値は約
SHA-256
SHA-256についてはIT用語辞典が分かりやすかったので引用させてください。
SHA-256とは、任意の長さの原文から固定長の特徴的な値を算出するハッシュ関数（要約関数）の一つ。どんな長さの原文からも256ビットのハッシュ値を算出することができる。
(引用元: https://e-words.jp/w/SHA-256.html)
SHA-256は256ビットのハッシュ値(一方向性関数で計算した値)を算出できます。SHA-256はSHA-2の一部で、NIST(アメリカの暗号等の標準化機関、耐量子暗号のコンペティションとか色々やってる)がFIPS 180-4で標準化しています。FIPS 180-4は公開されているので興味があったら見てみるといいと思います。
ソルト
ソルトは、原文に一意のランダムな文字列を加える手法です。ソルトを行ってからハッシュ化すると、同じ原文から違うハッシュ値が算出されるので、原文が単純な場合でもハッシュ値から原文を推測することが困難になります。
ストレッチング
ストレッチングはハッシュ化した値をさらにハッシュ化することで復元を困難にする手法です。ストレッチングはやればやるほど強固になるのですが、その分計算時間がかかります。一般的には10000回程度行うと良いらしいです。
bcrypt
bcryptは上記のハッシュ化、ソルトの付与とストレッチングを行い、パスワードを適切に保存するためのツールです。
比較手法
本記事では、2つの手法を暗号学、ベンチマークの観点から比較します。
- UUIDをそのままハッシュ化して保存
- UUIDをbcryptでハッシュ化して保存
暗号学的な観点から
誕生日のパラドックス
誕生日のパラドックスでは、Nビットのハッシュ関数において、あるハッシュ値から原文を探し出すために必要な試行回数の期待値は
ハッシュ値から原文を求める方法
ハッシュ関数から原文を求める方法は大きく分けて2種類存在します。
- 辞書を作成し、その辞書に基づいて攻撃する
- ランダムな値をハッシュ関数に入れて、ハッシュ値と原文の対応表を作る
- ランダムな値をハッシュ関数に入れて、入力値とハッシュ値の対応から還元関数を作成する
2番目、３番目の手法をRainbow Table Attackといいます。
現在(2022年3月)におけるコンピュータの能力
2010年代前半まではCPUを用いた解析が主流でしたが、2020年代はGPUを用いた解析が主流となっています。今日現在(2022年3月)において一般人が購入できる最も高性能なGPUがRTX3090であるため、HashcatというツールでRTX3090のハッシュ値計算能力を見ていこうと思います。今回はRTX3090の4枚差しで計測された結果を参考にさせていただきました。
Hashcat
Hashcatはハッシュ値を総当たりや辞書、それらを組み合わせた方法で解析できるツールです
SHA-256(ソルトなし)
ソルトなしの場合、以下の結果となっていました。
---------------------------
* Hash-Mode 1400 (SHA2-256)
---------------------------
Speed.#1.........: 8104.0 MH/s (337.78ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#2.........: 7985.8 MH/s (342.69ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#3.........: 8070.7 MH/s (339.19ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#4.........: 8246.0 MH/s (331.94ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#*.........: 32406.5 MH/s
この結果を見ると、1秒間に324億回計算ができるため、誕生日のパラドックスの期待値を当てはめるとUUID4は
SHA-256(ソルトあり)
ソルトありの場合、実行結果は以下のとおりとなっていました。
--------------------------------------
* Hash-Mode 1410 (sha256($pass.$salt))
--------------------------------------
Speed.#1.........: 8150.0 MH/s (335.79ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#2.........: 8009.8 MH/s (341.51ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#3.........: 8108.3 MH/s (337.50ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#4.........: 8286.3 MH/s (330.28ms) @ Accel:32 Loops:1024 Thr:1024 Vec:1
Speed.#*.........: 32554.5 MH/s
UUID4+ソルト10文字の場合、組み合わせは
bcrypt
bcrypt(ストレッチング32回)を使ったとき、実行時間は以下のとおりとなっていました。
----------------------------------------------------------------
* Hash-Mode 3200 (bcrypt $2*$, Blowfish (Unix)) [Iterations: 32]
----------------------------------------------------------------
Speed.#1.........: 107.3 kH/s (222.19ms) @ Accel:1024 Loops:32 Thr:24 Vec:1
Speed.#2.........: 108.2 kH/s (220.50ms) @ Accel:1024 Loops:32 Thr:24 Vec:1
Speed.#3.........: 105.8 kH/s (225.64ms) @ Accel:1024 Loops:32 Thr:24 Vec:1
Speed.#4.........: 107.5 kH/s (222.17ms) @ Accel:1024 Loops:32 Thr:24 Vec:1
Speed.#*.........: 428.7 kH/s
bcryptでは1秒間に42.8万回しか計算が行えません。したがって、誕生日のパラドックスの期待値を当てはめるとUUID4は
小話 雪崩効果
雪崩効果は、入力が1ビット違うと出力の半分以上ビットが反転することをいいます[3]。
SHA2では入力が1ビット違うと全く違う出力になると書いてある本が多いのですが、実際は入力が1ビット違うだけではほぼ同じ出力となってしまいます。これがあるため、ソルトの長さは十分でなければならないのです。
我々は本質を見誤っているのではないか？
今回の目標はトークンを安全に保管することであり、トークンが安全であることは勝手に決めつけていました。トークンをUUIDで生成することに関して何の疑問も抱かなかったわけですが、もしかしたらUUIDが安全ではないのではないか、という疑問です。
UUID4は暗号学的に安全か
UUID4は122ビットがランダムです。そこまではあっているのですが、暗号学的乱数を使う必要ことは明記されていません。実際、RFC4122ではこのように定義してあります。
For UUID version 4, the timestamp is a randomly or pseudo-randomly generated 60-bit value, as described in Section 4.4.
暗号学的乱数ではなく、擬似乱数を使ってもいい。そのような一文が書かれている以上、UUID4が暗号学的に安全かどうかは実装を見るしかありません。
Pythonの実装を読んでみる
Pythonではuuidモジュールが公式で用意されています。まずはドキュメントを読んでみましょう。
ドキュメントを読むと、
uuid.uuid4()
ランダムな UUID を生成します。
としか書いてありません。これだけでは断定ができないため、実装を読むこととします。ソースコード: Lib/uuid.pyをクリックすると、uuid4の実装は以下のようになっています。
def uuid4():
"""Generate a random UUID."""
return UUID(bytes=os.urandom(16), version=4)
よかった。os.urandom()は内部のエントロピーを貯めておく/dev/urandomから乱数を生成しており、十分にセキュアと言えるでしょう。
１２２ビットは本当に安全なのか？
私は疑り深い性格なのでまだUUIDをトークンとして使っていいと言い切れません。そこで、122ビットの乱数が本当に安全か過去の文献を調査しました。するとOAuthのRFC6749に興味深い記述を見つけました。
RFC6749の10.10. Credentials-Guessing Attacksにはこう書かれています。
The authorization server MUST prevent attackers from guessing access tokens, authorization codes, refresh tokens, resource owner passwords, and client credentials.
The probability of an attacker guessing generated tokens (and other credentials not intended for handling by end-users) MUST be less than or equal to 2^(-128) and SHOULD be less than or equal to 2^(-160).
つまり、誕生日のパラドックスを考慮すると256ビット以上の長さのトークンにしなければならず、320ビット以上のトークンだとなお良いということです。OAuth2.1のRFCのドラフトであるThe OAuth 2.1 Authorization Framework draft-ietf-oauth-v2-1-05[4]にも同じことが書かれているため、トークンは256ビット以上が望ましく、UUIDの122ビットの乱数では全く足りないと言えるのではないでしょうか。
代替案
Pythonでの代替案として、secrets.token_hex()が挙げられます。実際にコードを読んでみると、暗号学的に安全な乱数生成がなされておりこれが現状のベストプラクティスではないかと思います。
from random import SystemRandom
_sysrand = SystemRandom()
def token_bytes(nbytes=None):
"""Return a random byte string containing *nbytes* bytes.
If *nbytes* is ``None`` or not supplied, a reasonable
default is used.
>>> token_bytes(16) #doctest:+SKIP
b'\\xebr\\x17D*t\\xae\\xd4\\xe3S\\xb6\\xe2\\xebP1\\x8b'
"""
if nbytes is None:
nbytes = DEFAULT_ENTROPY
return _sysrand.randbytes(nbytes)
def token_hex(nbytes=None):
"""Return a random text string, in hexadecimal.
The string has *nbytes* random bytes, each byte converted to two
hex digits. If *nbytes* is ``None`` or not supplied, a reasonable
default is used.
>>> token_hex(16) #doctest:+SKIP
'f9bf78b9a18ce6d46a0cd2b0b86df9da'
"""
return binascii.hexlify(token_bytes(nbytes)).decode('ascii')
from os import urandom as _urandom
## ------------------------------------------------------------------
## --------------- Operating System Random Source ------------------
class SystemRandom(Random):
"""Alternate random number generator using sources provided
by the operating system (such as /dev/urandom on Unix or
CryptGenRandom on Windows).
Not available on all systems (see os.urandom() for details).
"""
def random(self):
"""Get the next random number in the range [0.0, 1.0)."""
return (int.from_bytes(_urandom(7), 'big') >> 3) * RECIP_BPF
def getrandbits(self, k):
"""getrandbits(k) -> x. Generates an int with k random bits."""
if k < 0:
raise ValueError('number of bits must be non-negative')
numbytes = (k + 7) // 8 # bits / 8 and rounded up
x = int.from_bytes(_urandom(numbytes), 'big')
return x >> (numbytes * 8 - k) # trim excess bits
def randbytes(self, n):
"""Generate n random bytes."""
# os.urandom(n) fails with ValueError for n < 0
# and returns an empty bytes string for n == 0.
return _urandom(n)
def seed(self, *args, **kwds):
"Stub method. Not used for a system random number generator."
return None
def _notimplemented(self, *args, **kwds):
"Method should not be called for a system random number generator."
raise NotImplementedError('System entropy source does not have state.')
getstate = setstate = _notimplemented
まとめ
かなり脱線してしまいましたが、今回の結論は次のとおりです。
- 122ビットの乱数でもソルトは必ず必要である
- 122ビットだとソルトがあったとしても解読の期待値は2年程度となってしまう
- 乱数部分が122ビットだとOAuthの基準に適合しないため、
secrets.token_hex()で256ビット以上のトークンを生成するのが安全
Discussion