ハッシュ値を解析する方法

# はじめに
本記事はハッシュ値を解析する方法について記載しています。

ハッシュ値を解析する方法を学ぶことで、MD5やSHA-1など安全性が低下しているハッシュ関数を使用するリスクについて理解できます。

## ハッシュ関数の重要性
一般的な会員制のWebサイトを提供するシステムではユーザーIDと、パスワードの組み合わせで認証を行なっています。

パスワードなどの機密情報をデータベースにプレーンテキストで保存し、データ侵害が発生した場合、何が起きるかは言うまでもありません。最近、発生した以下のニュースが記憶に新しいです。

- [「ディスクユニオン」 70万人余の会員の個人情報 漏えいか](https://www3.nhk.or.jp/news/html/20220629/k10013694311000.html)

このような事故を防ぐためには、パスワードはプレーンテキストで保存せずに、盗まれたとしても解読できないように**暗号化**または、**ハッシュ化**などの対策が求められます。

暗号化とハッシュ化はそれぞれ仕組みが異なるため、違いを理解した上でシステムに適用するのが重要です。
暗号化は鍵を必要とするため、鍵の管理が発生し、可逆的な変換を提供します。
一方、ハッシュ化は鍵管理が不要です。また、一方向性の性質を持ち不可逆な変換になるため、ハッシュ値からパスワードを求めることは計算量的に困難です。

以上を踏まえて、暗号化の場合は鍵の安全性についても担保する必要があることから、データベースではハッシュ化が多く利用されています。

ハッシュ関数の重要性について以下の動画が参考になります。

https://www.youtube.com/watch?v=cczlpiiu42M&t=39s

## ハッシュ関数
[ハッシュ関数](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0)は任意の長さの入力データを基に、固定長のビット列を出力する関数のことです。
また、ハッシュ関数によって求められる**ハッシュ値**はメッセージダイジェスト（MD）とも呼ばれています。

```math
ハッシュ値：y=ハッシュ関数：H（入力データ：x）
```

ハッシュ関数には次のような性質が求められます。
書籍などによっては一部呼称が異なる場合があります。

- 衝突発見困難性
    - ハッシュ値が一致する`H（x） = H（x'）`となるような異なる2つの入力データ`x, x'`を求めることが計算量的に困難であること。
- 第2原像計算困難性
    - 入力データ`x`とそれに対するハッシュ値`y = H（x）`が与えられた時に、同一のハッシュ値を生成する`H（x） = H（x'） AND x ≠ x'`となるような別のメッセージ`x'`求めることが計算量的に困難であること。
- 現像計算困難性（一方向性）
    - ハッシュ値`y = H（x）`が与えられた時に、ハッシュ値を生成する入力データ`x`を求めることが計算量的に困難であること。

概念として入力データが同じ場合は常に同じハッシュ値が生成され、入力データが少しでも異なればそのハッシュ値は異なります。
そして、これら性質は衝突発見困難性→第2原像計算困難性→現像計算困難性（一方向性）の順に困難になります。

:::note
ハッシュ関数のこのような性質はメッセージ認証や、デジタル署名などの用途で使用されています。
:::

## ハッシュ値を解析する方法
便利なハッシュ値ですが、ブルートフォース攻撃でクラックされる可能性があります。

特定したいパスワードのハッシュ値と、ハッシュ関数にパスワードのワードリストを入力データにして実行されたハッシュ値が同等かどうか確認することで、パスワードを特定することができます。

また、[レインボーテーブル](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%82%A4%E3%83%B3%E3%83%9C%E3%83%BC%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB)などを用いて効率的にパスワードクラックすることも可能です。
レインボーテーブルを使用した攻撃に対してはソルト（salt）を使用するのが有効な対策です。ソルトはパスワードに付加する文字列を指し、ランダムな性質を持ちます。運用に耐え得るためには少なくとも20文字程度の長さが求められます。

:::note alert
MD5とSHA1はハッシュ衝突攻撃と呼ばれるものに対して脆弱であることが証明されている弱いハッシュアルゴリズムです。
:::

### ハッシュ値の識別
ハッシュ形式が不明なハッシュ値は**hash-identifie**などを使用することで、ハッシュ形式を推定することができます。

文字列`test`のmd5のハッシュ値は`098f6bcd4621d373cade4e832627b4f6`です。
以下、文字列`test`のハッシュ値を例に、各種ツールの使い方について解説しています。

#### hash-identifier
以下のコマンドを実行し、` HASH:`に求めたいハッシュ値を入力します。
`Possible Hashs:`の先頭はMD5になるため、`098f6bcd4621d373cade4e832627b4f6`はMD5を推定していることが期待できます。

`$ hash-identifier`

```console
   #########################################################################
   #     __  __                     __           ______    _____           #
   #    /\ \/\ \                   /\ \         /\__  _\  /\  _ `\         #
   #    \ \ \_\ \     __      ____ \ \ \___     \/_/\ \/  \ \ \/\ \        #
   #     \ \  _  \  /'__`\   / ,__\ \ \  _ `\      \ \ \   \ \ \ \ \       #
   #      \ \ \ \ \/\ \_\ \_/\__, `\ \ \ \ \ \      \_\ \__ \ \ \_\ \      #
   #       \ \_\ \_\ \___ \_\/\____/  \ \_\ \_\     /\_____\ \ \____/      #
   #        \/_/\/_/\/__/\/_/\/___/    \/_/\/_/     \/_____/  \/___/  v1.2 #
   #                                                             By Zion3R #
   #                                                    www.Blackploit.com #
   #                                                   Root@Blackploit.com #
   #########################################################################
--------------------------------------------------
 HASH: 098f6bcd4621d373cade4e832627b4f6

Possible Hashs:
[+] MD5
[+] Domain Cached Credentials - MD4(MD4(($pass)).(strtolower($username)))

Least Possible Hashs:
[+] RAdmin v2.x
[+] NTLM
[+] MD4
[+] MD2
[+] MD5(HMAC)
[+] MD4(HMAC)
[+] MD2(HMAC)
[+] MD5(HMAC(Wordpress))
[+] Haval-128
[+] Haval-128(HMAC)
[+] RipeMD-128
[+] RipeMD-128(HMAC)
[+] SNEFRU-128
[+] SNEFRU-128(HMAC)
[+] Tiger-128
[+] Tiger-128(HMAC)
[+] md5($pass.$salt)
[+] md5($salt.$pass)
[+] md5($salt.$pass.$salt)
[+] md5($salt.$pass.$username)
[+] md5($salt.md5($pass))
[+] md5($salt.md5($pass))
[+] md5($salt.md5($pass.$salt))
[+] md5($salt.md5($pass.$salt))
[+] md5($salt.md5($salt.$pass))
[+] md5($salt.md5(md5($pass).$salt))
[+] md5($username.0.$pass)
[+] md5($username.LF.$pass)
[+] md5($username.md5($pass).$salt)
[+] md5(md5($pass))
[+] md5(md5($pass).$salt)
[+] md5(md5($pass).md5($salt))
[+] md5(md5($salt).$pass)
[+] md5(md5($salt).md5($pass))
[+] md5(md5($username.$pass).$salt)
[+] md5(md5(md5($pass)))
[+] md5(md5(md5(md5($pass))))
[+] md5(md5(md5(md5(md5($pass)))))
[+] md5(sha1($pass))
[+] md5(sha1(md5($pass)))
[+] md5(sha1(md5(sha1($pass))))
[+] md5(strtoupper(md5($pass)))
--------------------------------------------------
```

ハッシュ値は直接引数にも指定できます。

`$ hash-identifier 098f6bcd4621d373cade4e832627b4f6`

参考：[Hash-identifie](https://www.kali.org/tools/hash-identifier/)

:::note warn
`hash-identifie`コマンドの出力結果について、ほとんどの場合、最初に表示されるハッシュ形式が正解であることを推定していますが、常にそうであるとは限りません。
:::

#### hashid
**hashid**もハッシュの識別や解析を行うためのツール（Pythonスクリプト）です。
`hashid`の引数にハッシュ値を渡して実行します。引数にはファイル名も指定できます。

`$ hashid 098f6bcd4621d373cade4e832627b4f6`

```console
Analyzing '098f6bcd4621d373cade4e832627b4f6'
[+] MD2 
[+] MD5 
[+] MD4 
[+] Double MD5 
[+] LM 
[+] RIPEMD-128 
[+] Haval-128 
[+] Tiger-128 
[+] Skein-256(128) 
[+] Skein-512(128) 
[+] Lotus Notes/Domino 5 
[+] Skype 
[+] Snefru-128 
[+] NTLM 
[+] Domain Cached Credentials 
[+] Domain Cached Credentials 2 
[+] DNSSEC(NSEC3) 
[+] RAdmin v2.x 

```

参考：[Hashid](https://www.kali.org/tools/hashid/)

### ハッシュ値の解析
ハッシュ値の解析はツールと、ワードリストを使用します。
ワードリストの使い方として、パスワードが推定できる場合は事前に絞り込んだワードリストを用意しておくことで、処理を効率化できます。

#### John the Ripper
[**John the Ripper**](https://ja.wikipedia.org/wiki/John_the_Ripper)はサーバー内のユーザーの弱いパスワードを見つけるためのツールです。
解析したいハッシュの形式と、ワードリストを指定してを実行します。

以下はハッシュの形式がmd5で、ワードリストに`rockyou.txt`を指定している例です。
ハッシュ値のパスワードは`test`であることが解析できています。

`$ john --format=raw-md5 --wordlist=/usr/share/wordlists/rockyou.txt hash.txt`

```console
Using default input encoding: UTF-8
Loaded 1 password hash (Raw-MD5 [MD5 256/256 AVX2 8x3])
Warning: no OpenMP support for this hash type, consider --fork=12
Press 'q' or Ctrl-C to abort, almost any other key for status
test             (?)     
1g 0:00:00:00 DONE (2022-08-03 01:09) 100.0g/s 16627Kp/s 16627Kc/s 16627KC/s tyson4..tauruz
Use the "--show --format=Raw-MD5" options to display all of the cracked passwords reliably
Session completed. 
```

`john`コマンドを実行すると、ホームディレクトリ配下にログが出力されます。

`$ ls -al ~/.john/`

```console
合計  16
drwx------  2 kali kali 4096  7月 17 14:49 .
drwxr-xr-x 27 kali kali 4096  7月 17 14:49 ..
-rw-------  1 kali kali  880  7月 17 14:49 john.log
-rw-------  1 kali kali   61  7月 17 14:49 john.pot
```

参考：[John](https://www.kali.org/tools/john/)

#### hashcat
**hashcat**はCPUベースのハッシュパスワードをクラックするツールです。

オプションでは様々なハッシュ形式を指定できます。
`-m`でハッシュ形式、`-a`でアタックモードを指定します。
ハッシュ形式やアタックモードで指定する番号が不明な場合は`man`コマンドで確認できます。
また、ハッシュ形式については[Example hashes](https://hashcat.net/wiki/doku.php?id=example_hashes)から様々な種類のリストが確認できます。

以下はハッシュ形式がmd5、アタックモードがStraight、解析するハッシュテキストに`hash.txt`、ワードリストに`rockyou.txt`を指定しています。

`$ hashcat -m 0 -a 0 hash.txt /usr/share/wordlists/rockyou.txt`

```console
hashcat (v6.2.5) starting

OpenCL API (OpenCL 3.0 PoCL 3.0+debian  Linux, None+Asserts, RELOC, LLVM 13.0.1, SLEEF, DISTRO, POCL_DEBUG) - Platform #1 [The pocl project]
============================================================================================================================================
* Device #1: pthread-AMD Ryzen 5 5600X 6-Core Processor, 6895/13855 MB (2048 MB allocatable), 12MCU

Minimum password length supported by kernel: 0
Maximum password length supported by kernel: 256

Hashes: 1 digests; 1 unique digests, 1 unique salts
Bitmaps: 16 bits, 65536 entries, 0x0000ffff mask, 262144 bytes, 5/13 rotates
Rules: 1

Optimizers applied:
* Zero-Byte
* Early-Skip
* Not-Salted
* Not-Iterated
* Single-Hash
* Single-Salt
* Raw-Hash

ATTENTION! Pure (unoptimized) backend kernels selected.
Pure kernels can crack longer passwords, but drastically reduce performance.
If you want to switch to optimized kernels, append -O to your commandline.
See the above message to find out about the exact limits.

Watchdog: Temperature abort trigger set to 90c

Host memory required for this attack: 3 MB

Dictionary cache hit:
* Filename..: /usr/share/wordlists/rockyou.txt
* Passwords.: 14344385
* Bytes.....: 139921507
* Keyspace..: 14344385

098f6bcd4621d373cade4e832627b4f6:test                     
                                                          
Session..........: hashcat
Status...........: Cracked
Hash.Mode........: 0 (MD5)
Hash.Target......: 098f6bcd4621d373cade4e832627b4f6
Time.Started.....: Wed Jul 20 22:31:09 2022 (0 secs)
Time.Estimated...: Wed Jul 20 22:31:09 2022 (0 secs)
Kernel.Feature...: Pure Kernel
Guess.Base.......: File (/usr/share/wordlists/rockyou.txt)
Guess.Queue......: 1/1 (100.00%)
Speed.#1.........: 14317.0 kH/s (0.18ms) @ Accel:1024 Loops:1 Thr:1 Vec:8
Recovered........: 1/1 (100.00%) Digests
Progress.........: 172032/14344385 (1.20%)
Rejected.........: 0/172032 (0.00%)
Restore.Point....: 159744/14344385 (1.11%)
Restore.Sub.#1...: Salt:0 Amplifier:0-1 Iteration:0-1
Candidate.Engine.: Device Generator
Candidates.#1....: greenacre -> floryna
Hardware.Mon.#1..: Temp: 76c Util:  8%

Started: Wed Jul 20 22:31:01 2022
Stopped: Wed Jul 20 22:31:11 2022
```

上記の例では`Status`が`Cracked`と出力されているため、クラックできたことを示します。

`--show`を付けて解析結果について確認することができます。

`$ hashcat -m 0 -a 0 hash.txt /usr/share/wordlists/rockyou.txt --show`

```console
098f6bcd4621d373cade4e832627b4f6:test
```

再度、実行した場合は以下のような出力になります。

```console
hashcat (v6.2.5) starting

OpenCL API (OpenCL 3.0 PoCL 3.0+debian  Linux, None+Asserts, RELOC, LLVM 13.0.1, SLEEF, DISTRO, POCL_DEBUG) - Platform #1 [The pocl project]
============================================================================================================================================
* Device #1: pthread-AMD Ryzen 5 5600X 6-Core Processor, 6895/13855 MB (2048 MB allocatable), 12MCU

Minimum password length supported by kernel: 0
Maximum password length supported by kernel: 256

INFO: All hashes found in potfile! Use --show to display them.

Started: Wed Jul 20 22:50:46 2022
Stopped: Wed Jul 20 22:50:46 2022

```

再実行したい場合は、`hashcat.potfile`ファイルを削除します。

`$ rm /home/＜ユーザ名＞/.local/share/hashcat/hashcat.potfile`

参考：[Hashcat](https://www.kali.org/tools/hashcat/)

### その他
その他、ハッシュ関連のツールについて以下に記載しています。

#### ssh2john
`ssh2john`コマンドはSSHの秘密鍵をjohn形式に変換にすることができます。
以下SSHの秘密鍵として`id_rsa`をクラックする場合の例です。

例として`ssh-keygen`コマンドを実行し、パスワードは`123456`でSSHの鍵ペアを作成します。

`$ ssh-keygen `

```console
Generating public/private rsa key pair.
Enter file in which to save the key (/home/kali/.ssh/id_rsa): /tmp/id_rsa
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /tmp/id_rsa
Your public key has been saved in /tmp/id_rsa.pub
The key fingerprint is:
SHA256:8mJUizsLAV+mEuHiQFkNr6022608b/rUEMv+kmrDtKs kali@kali
The key's randomart image is:
+---[RSA 3072]----+
| .+oo            |
|.o ...           |
|o +  .o..        |
|o. +o+.oo.       |
| ...+.++S        |
|   ..+.+o        |
|   ++ *oo.       |
|  . =OoB.        |
|   EoB%+..       |
+----[SHA256]-----+
```

`ssh2john`コマンドでSSHの秘密鍵をjohn形式に変換にします。

`$ ssh2john id_rsa > hash.txt`

`john`コマンドでクラックします。パスワード`123456`についてクラックできました。

`$ john --wordlist=/usr/share/wordlists/rockyou.txt hash.txt`
    
```console
Created directory: /home/kali/.john
Using default input encoding: UTF-8
Loaded 1 password hash (SSH, SSH private key [RSA/DSA/EC/OPENSSH 32/64])
Cost 1 (KDF/cipher [0=MD5/AES 1=MD5/3DES 2=Bcrypt/AES]) is 2 for all loaded hashes
Cost 2 (iteration count) is 16 for all loaded hashes
Will run 12 OpenMP threads
Press 'q' or Ctrl-C to abort, almost any other key for status
123456           (id_rsa)     
1g 0:00:00:01 DONE (2022-08-01 00:46) 0.9803g/s 94.11p/s 94.11c/s 94.11C/s 123456..yellow
Use the "--show" option to display all of the cracked passwords reliably
Session completed. 
```

#### hashdeep
`hashdeep`コマンドはオプションでディレクトリ構造を再帰的に掘り下げながら、任意の数のファイルに対して複数のハッシュまたはメッセージダイジェストを計算します。

以下の例ではファイル名`test`で中身が`test`のハッシュ値を計算しています。

`$ echo test > test`
`$ hashdeep test`

```console
%%%% HASHDEEP-1.0
%%%% size,md5,sha256,filename
## Invoked from: /tmp
## $ hashdeep test
## 
5,d8e8fca2dc0f896fd7cb4cb0031ba249,f2ca1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da52e6ccc26fd2,/tmp/test
```

参考：[Hashdeep](https://www.kali.org/tools/hashdeep/)

## ハッシュ解析に便利なサイト
オンラインでもハッシュ解析に便利なサイトが色々あります。
このようなサイトを使用することで、MD5やSHA1のハッシュ値は簡単に解析できます。

- ハッシュ値の生成
    - [MD5 Hash Generator](https://www.md5hashgenerator.com/)
- ハッシュ値の解析
    - [CrackStation](https://crackstation.net/)
    - [Hash Analyzer](https://www.tunnelsup.com/hash-analyzer/)
    - [Hash Toolkit](https://hashtoolkit.com/)

# おわりに
パスワードなどの機密情報はデータベースにプレーンテキストで保存しないようにしましょう。
パスワードを保護するために、MD5とSHA1のような安全性の低いハッシュ関数は使用しないようにしましょう。

また、システムを利用する側からしても、パスワードは推測しにくい複雑なパスワードを設定し、2要素認証を設定するなどのセキュリティ対策が重要です。

## 参考
- [パスワードの取り扱い](https://www.ipa.go.jp/security/awareness/vendor/programmingv1/pdf/b09_01.pdf)
- [メッセージ・ダイジェストとデジタル署名](https://www.ibm.com/docs/ja/ibm-mq/7.5?topic=ssfksj-7-5-0-com-ibm-mq-sec-doc-q009810--htm)
- [hashcat](https://hashcat.net/hashcat/)