LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mayukorin

【roadmap.sh で勉強】ハッシュ関数 MD5・SHA Family・Scrypt・Bcrypt を比較してみた

Posted at

こんにちは！mayukorin です！私は現在 roadmap.sh というサイトで Backend に関する技術を勉強しているのですが，せっかくなので学んだことを記事にしていきたいと思います！

今回は，「Hashing algorithms」についてです！

そもそもハッシュ化とは？

元の文字列を不規則な文字列に変換すること．変換に使われる関数をハッシュ関数と言う．ハッシュ関数で変換された文字列をダイジェスト値と言う．

ハッシュ関数が満たすべき性質

  1. 弱衝突耐性：ある文字列 m1 が与えられたとき， hash(m1) = hash (m2)　かつ m1 ≠ m2 となるような文字列 m2 を求めることはできない．
  2. 強衝突耐性：hash(m1) = hash (m2)　かつ m1 ≠ m2 となるような文字列 m1, m2 を求めることはできない．

ハッシュを使う目的

データの改竄・欠落の検知に使われます．例えば，データの送信前と受信後にデータに対してダイジェスト値を求めてそれが一致していれば，データの改竄・欠落がないことを示すことができます（弱衝突耐性より，同じダイジェスト値になるような別のデータは存在しないため）．

代表的なハッシュ関数

roadmap.sh では以下4つが代表的なハッシュ関数として紹介されていました．

  • MD5
  • SHA Family
  • Scrypt
  • Bcrypt

MD5 （Message-Digest Algorithm 5）

MD5 は，1991年に MIT の Ronald Rivest 教授によって設計されたハッシュ関数です．任意の長さの文字列を入力として，128ビットのダイジェスト値を出力します．しかし，MD5には以下2つの問題点があると言われています．

  • 強衝突耐性の突破：[1] によると， 標準的なノートパソコンで1分以内に強衝突耐性を突破できるものがあったらしい．
  • MD5ハッシュを高速計算可能：コンピュータの進歩により，MD5ハッシュ値を高速に計算できるようになった．例えば，攻撃者は複数のパスワードに対するハッシュ値を高速に計算できるので，辞書攻撃のリスクが上がる．

SHA （Security Hash Algorithm） Family

SHA-0, SHA-1, SHA-2, SHA-3 の4種類あり，それらをまとめて SHA Family と呼ぶ．

SHA-0

1991年に，SHA Family の中で最初に発表された．160 ビットのダイジェスト値を生成する．しかしすぐに欠点が発見されたらしい．

SHA-1

1995年に，SHA-0の欠点を修正して発表された．SHA-0 と同様に，160 ビットのダイジェスト値を生成する．しかし，2005年にSHA-1に対する攻撃手法が発見され，2017年には強衝突耐性の突破が確認された．

SHA-2

2001年に，SHA-1を改良して発表された．ダイジェスト値の長さにバリエーションがあり（224，256，384，512ビット），それに応じて名前がつけられている．例えば，SHA-256はダイジェスト値の長さが256ビット，SHA-384はダイジェスト値の長さが384ビット．現時点では，SHA-2に対する有効な攻撃手法は見つかっていない．

SHA-3

2012年に公募により発表された．ダイジェスト値の長さは，224，256，384，512ビットに加えて可変長もできる（ダイジェスト値が長い方が安全）．ダイジェスト値の計算方法が，SHA-1, SHA-2 とは大きく異なるらしい．

Scrypt

2009年に発表された鍵導出関数（鍵導出関数は，パスワードなどから鍵を生成する関数．ハッシュ関数とほぼ同じで，出力値を暗号化・復号化の鍵として利用することがあるかどうかの違いという認識ですが，間違っていたら教えていただきたいです🙇‍♀️）．
ハッシュ化するのに膨大な計算量・メモリを使用するように設計されているため，辞書攻撃が困難．

Bcrypt

1999年に発表された鍵導出関数．Blowfish暗号をベースにしている．以下3点の利点がある．

  • Blowfish暗号をベースにした鍵のセットアップに時間がかかるため，辞書攻撃を緩和できる．
  • 鍵のセットアップの反復回数を設定できる．攻撃者が高性能なハードウェアを使用しても，反復回数を増やすことで対抗できる．
  • ハッシュ化に，パスワードに加えてsalt（ランダム文字列）を使用する．そのため，同じパスワードでも異なるハッシュ値を生成でき，レインボーテーブル攻撃1に対抗できる（salt は， Scrypt でも使っているっぽい）．

各ハッシュ関数の実行時間を測定してみた．

Python で，MD5・SHA-256・Scrypt・Bcryptの計算時間を測定してみました．ただし，マシンのスペックは 2-core • 8GB RAM • 32GB です．

実行時間計測に使ったコードはこちらからご覧になれます！

md5_hash.py
import hashlib
import time

def calc_md5_hash(plain_text):
    start_time = time.time()
    hash = hashlib.md5(plain_text.encode()).hexdigest()
    end_time = time.time()
    return hash, end_time-start_time
sha256_hash.py
import hashlib
import time

def calc_sha256_hash(plain_text):
    start_time = time.time()
    hash = hashlib.sha256(plain_text.encode()).hexdigest()
    end_time = time.time()
    return hash, end_time-start_time
scrypt_hash.py
import pyscrypt
import os
import time

def calc_scrypt_hash(plain_text):
    start_time = time.time()
    salt = os.urandom(16)
    hash = pyscrypt.hash(password=plain_text.encode(), salt=salt, N=8192, r=8, p=1, dkLen=32).hex()
    end_time = time.time()
    return hash, end_time-start_time

N は反復回数，r はブロックサイズ，pは並列度係数です．この N,r,pは計算量・メモリに影響するらしいです．今回は，[3]に倣ってN=8192, r=8, p=1としています．

bcrypt_hash.py
import bcrypt
import time

def calc_bcrypt_hash(plain_text):
    start_time = time.time()
    cost = 12
    hash = bcrypt.hashpw(plain_text.encode(), bcrypt.gensalt(rounds=cost)).hex()
    end_time = time.time()
    return hash, end_time-start_time

bcrypt_hash.py で出てくる cost は先ほど説明した反復回数に関するパラメータです．

main.py
from md5_hash import calc_md5_hash
from sha256_hash import calc_sha256_hash
from scrypt_hash import calc_scrypt_hash
from bcrypt_hash import calc_bcrypt_hash


if __name__ == '__main__':

    # hash計算にかかる時間を測定
    common_passwords = ["password", "123456", "qwerty", "admin", "letmein", "welcome", "123abc", "password1", "12345", "abcdef"]
    md5_avg_time = 0
    sha256_avg_time = 0
    scrypt_avg_time = 0
    bcrypt_avg_time = 0

    for password in common_passwords:
        md5_avg_time += calc_md5_hash(password)[1]
        sha256_avg_time += calc_sha256_hash(password)[1]
        scrypt_avg_time += calc_scrypt_hash(password)[1]
        bcrypt_avg_time += calc_bcrypt_hash(password)[1]

    print('md5 average time: {}, sha256 average time: {}, scrypt average time: {}, bcrypt average time: {}'.format(md5_avg_time/len(common_passwords), sha256_avg_time/len(common_passwords), scrypt_avg_time/len(common_passwords), bcrypt_avg_time/len(common_passwords)))

ハッシュ化を10回繰り返して平均実行時間を測定した結果がこちらです．

ハッシュ関数 平均実行時間 [s]
MD5 1.43e-5
SHA-256 3.70e-6
Scrypt 10.79
Bcrypt 0.26

意外にも SHA-256 の実行時間が一番短いという結果になりました．Scrypt・Bcrypt は，MD5・SHA-256よりも実行時間が$10^4$倍以上長いので，確かにMD5・SHA-256よりは辞書攻撃に有効と言える気がします．また，ScryptがBcryptよりも実行時間が長くなりましたが，それはパラメータの値による気がします．

Scrypt・Bcrypt の costパラメータを変えてみた

Scrypt・Bcrypt の costパラメータを変えたときの実行時間の変化を見てみました．

反復回数Nを変えたときのScryptの実行時間が以下の通りです．なお，Nは2の累乗である必要があるみたいです．

N 平均実行時間 [s]
8192 10.79
16384 21.01
32768 42.09

costを変えたときのBcryptの実行時間が以下の通りです．

cost 平均実行時間 [s]
12 0.26
13 0.53
14 1.06
15 2.12
16 4.25
17 8.49
18 16.97
19 33.97
20 67.93

costを1増やすと，実行時間がおよそ2倍になっていることがわかります．bcryptの反復回数は$2^{cost}$で決まるからみたいです．

scrypt・bcryptを比較すると，bcryptの方がcostパラメータを変えたときの平均実行時間の増加率が大きいことがわかりました！

まとめ

以上まとめです！何か間違っている点などありましたら教えていただきたいです！よろしくお願いします🙇‍♀️

  • 代表的なハッシュ関数として，MD5・SHA Family・Scrypt・Bcryptを調べた
  • MD5は，ハッシュ関数として満たさなければならない強衝突耐性が突破されてしまった
  • Scrypt・Bcryptは，平均実行時間がMD5・SHA Familyに比べてとても長いため，その分辞書攻撃に有効そう
  • ハッシュ時に，ランダムな文字列であるソルトも付加すると，レインボーテーブル攻撃に有効．
  • Bcryptの方が，Scryptよりもcostパラメータに対する実行時間の増加率が大きい

参考文献

[1] IETF, "Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithm", 2011.
[2] https://www.techtarget.com/searchsecurity/definition/MD5
[3] https://cryptobook.nakov.com/mac-and-key-derivation/scrypt
[4] https://auth0.com/blog/hashing-in-action-understanding-bcrypt/#What-is--bcrypt-
[5] https://ja.wikipedia.org/wiki/Secure_Hash_Algorithm

  1. パスワードとそれに対応するハッシュ値の組み合わせを事前に用意しておき，入手したハッシュ値からパスワードを割り出す攻撃． ↩

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?