【パスワードクラッキング】/etc/shadowのパスワードを解析してみる

## これは何?

Unix系OSではユーザのパスワードは`/etc/shadow`にハッシュとして管理されています。
このハッシュからパスワードを解析できるかいろいろ調べて試してみたことを書きます。
何がいいたかったかというと`/etc/shadow`のハッシュアルゴリズムはcryptってライブラリ使ってるんだへーという話。

---

## ハッシュとは(ざっくり)

あるデータを入力に指定した時に固定長のユニークな値を返してくれる関数をハッシュ関数，ユニークな値をハッシュといいます。
ハッシュのこの性質はデータの改ざん検知に利用されます。

```shell
cat test.txt
hello

md5sum test.txt
b1946ac92492d2347c6235b4d2611184  test.txt

# ファイルを改ざん
echo world >> test.txt
 md5sum test.txt
0f723ae7f9bf07744445e93ac5595156  test.txt
```

このようにデータに対してユニークな値であるハッシュが得られるため，ハッシュを記録しておけばファイルが改ざんされているかどうかを判定することができるのです。

また，ハッシュの特徴として不可逆であるということがあげられます。
base64によるエンコードは可逆変換であるため，変換後の値からもとの値を簡単に求めることができます。
以下の例は文字列helloをbase64に変換後にもとに戻しています。

```shell
echo "hello" | base64
aGVsbG8K
echo "aGVsbG8K" | base64 -d
hello
```

ハッシュではこのようなことはできず，求めたハッシュから直接元の値を計算することはできません。

このようなハッシュのもつ，

1. ユニークな値を得られる
2. 不可逆性
によりパスワードを管理するのに使われます。
サービスの提供者はユーザの入力したパスワードが正しいかを判定する必要がありますが，パスワードを平文で保存しておくと攻撃者により取得された際にパスワードが漏洩してしまうからです。
パスワードのハッシュを保存しておけば，万が一ハッシュが外部に漏洩したとしても元の文字列にハッシュ関数を適用して得られるハッシュと漏洩したハッシュが一致しない限りは攻撃者がパスワードを知ることができないためセキュリティ対策のベストプラクティスの一つとして知られています。

---

## どうすればハッシュからパスワードを得られるか

基本的には総当り攻撃に分類される手法が取られます。
大量の文字列に対してハッシュ関数を適用して得られたハッシュと解析対象のハッシュを比較することを続ければ理論上パスワードを得ることはできます。

ただし，これを実施するにあたっては使用しているハッシュアルゴリズムがわかっていることが前提になります。

### ハッシュのセキュリティ対策

大きく分けて

- ソルト
- ストレッチング
の2種類の対策があります。
ソルトはある文字列をハッシュ化する前にランダムな文字列を付与することで同じ文字列でも異なるハッシュ値を得ることができるようになります。
ストレッチングはハッシュ化する前に何度もハッシュ関数を適用することで計算量を増やすことで総当り攻撃に対する耐性を高めることができます。

---

## Linuxでのログインパスワードの管理

Linuxではユーザの情報は基本的に`/etc/passwd`に保存されています。
構造は以下のようになっています。
`ユーザ名:パスワード:ユーザID:グループID:ユーザ情報:ホームディレクトリ:ログインシェル`

```shell
cat /etc/passwd
root:x:0:0:root:/root:/bin/bash
ntp:x:132:141::/nonexistent:/usr/sbin/nologin
sigma:x:10002:1998::/summer/user10:/bin/ksh
```

:::note info
ユーザIDが0のユーザはrootユーザです。
ログインシェルが不要なユーザは`/usr/sbin/nologin`を指定することでログインを禁止することができます。
:::

昔はパスワード領域にユーザのパスワードが平文で保存されていましたが，現在は`/etc/shadow`にハッシュ化されたパスワードが保存されています。
`/etc/shadow`は以下のような構造になっています。
`ユーザ名:$ハッシュアルゴリズム:$ソルト$ハッシュ値:その他の情報`

```shell
sudo cat /etc/shadow
sigma:$6$supersugoisaltda$aGNLnFiImN.8qxP2VoYYCR0Q57uwPsU1ECrLCiTw9A5y68PZKCSsx9J1.EyTjdEwvfF.eJI7.4RlcA4Hswl2./:18765:0:99999:7:::
```

例えば上の例ではハッシュアルゴリズムは`$`6のためSHA-512が使用されており，ソルトは`supersugoisaltda`でこれを元に生成されたハッシュ値は`aGNLnFiImN.8qxP2VoYYCR0Q57uwPsU1ECrLCiTw9A5y68PZKCSsx9J1.EyTjdEwvfF.eJI7.4RlcA4Hswl2./`であることがわかります。

---

## ハッシュの解析

今回は`/etc/shadow`に保存されているハッシュを解析してみます。
ハッシュの解析を始める前にハッシュ化が何を使って行われているのかを調べます。
すると`crypt`というC製のライブラリが使われていることがわかりました。
こちらのライブラリはPythonからも使用できます。

```python3
import crypt

# ハッシュ化(sha-512)
crypt.crypt("パスワード", $6$ + "supersugoisaltda")
```

つまり，`パスワード`の部分を変えて大量にハッシュを生成し，`/etc/shadow`と一致するハッシュを見つけることができればLinuxのログインパスワードがわかります。

想定パスワードを考えるのは面倒なので，`rockyou.txt`というパスワードリストを使って総当り攻撃を行った例がこちらです。

```python3
# coding: utf-8
"""_summary_
/etc/shadowハッシュに対する辞書攻撃を行うサンプル
NOTE: /etc/shadowのハッシュ化はcryptというライブラリで行われている。
"""
import crypt
import requests
import re
from typing import Union, List


def get_rockyou_list(url: str) -> Union[None, List[str]]:
    """_summary_

    Args:
        url (str): rockyou.txt url

    Returns:
        password_list (List[str])
    """
    print(f"DOWNLOADING PASSWORD LIST...\n{url}")
    response = requests.get(url)

    if response.status_code == 200:
        password_list = response.text.splitlines()
        return password_list
    else:
        print(f"Error: Failed to download file (status code: {response.status_code})")
        return None


def main():
    # FIXME: shadowには/etc/shadowの一行をそのままコピペする
    shadow = "sigma:$6$supersugoisaltda$aGNLnFiImN.8qxP2VoYYCR0Q57uwPsU1ECrLCiTw9A5y68PZKCSsx9J1.EyTjdEwvfF.eJI7.4RlcA4Hswl2./:18765:0:99999:7:::"  # FIXME: this is sample

    match = re.match(r'.*\:(\$[0-9]\$)(\S+)\$(\S+)', shadow)
    hash_algorithm = match.group(1)  # $1$ = MD5，$2$ = Blowfish，$5$ = sha256，$6$ = sha512
    salt = match.group(2)
    hash_part = match.group(3).split(':')[0] # NOTE: ハッシュ部分より後ろをsplitで削除している
    print(f"TARGET SHADOW INFO={hash_algorithm}, {salt}, {hash_part}")
    target_hash = hash_algorithm + salt + "$" + hash_part

    rockyou_url = "https://github.com/brannondorsey/naive-hashcat/releases/download/data/rockyou.txt"
    password_list = get_rockyou_list(rockyou_url)
    password_list[7] = "h0b1gsy6"

    # password listのpasswordを使ってhashを生成して一致するまで試す
    for pw in password_list:
        tmp_hash = crypt.crypt(pw, hash_algorithm + salt)
        print(f"{pw}, {tmp_hash}")
        if tmp_hash == target_hash:
            print(f"=====CONGRATURATION!!! RAW PASSWORD IS\n{pw}\n=====")
            break


if __name__ == "__main__":
    main()

```

[最新のソースはこちら](https://github.com/RyosukeDTomita/shadow_cracker)にあります。
サンプルのハッシュは`password`というパスワードを`supersugoisaltda`というソルトでSHA-512でハッシュ化したものです。
実行してみるとパスワードが"password"であることがわかりました。

```shell
python3 shadow_cracker.py
TARGET SHADOW INFO=$6$, supersugoisaltda, aGNLnFiImN.8qxP2VoYYCR0Q57uwPsU1ECrLCiTw9A5y68PZKCSsx9J1.EyTjdEwvfF.eJI7.4RlcA4Hswl2./
DOWNLOADING PASSWORD LIST...
https://github.com/brannondorsey/naive-hashcat/releases/download/data/rockyou.txt
123456, $6$supersugoisaltda$hyD4E6YynORuFlf4uRrf4Vvgg3okBUFL3fVklxXKVrJKjsBxiGf83FsSUsrBykCHJNXCJniayBz694vbmUEdW/
12345, $6$supersugoisaltda$gnfHQ9Twx6vhGwQZho49cWz76O2uV67V3YN2zMWru.t3xnKxXH1YTUIx6pwE46SXE4pJE5UCkXHcqosPReLFs1
123456789, $6$supersugoisaltda$.WpOfr9vbv0EefXj8WGv/jOTuEcJAEj6kZzgY2Ha.eZjkEK4aqdGacmbdojfCWg3Don2jWcPv4xNI5HhjiVGu.
password, $6$supersugoisaltda$aGNLnFiImN.8qxP2VoYYCR0Q57uwPsU1ECrLCiTw9A5y68PZKCSsx9J1.EyTjdEwvfF.eJI7.4RlcA4Hswl2./
=====CONGRATURATION!!! RAW PASSWORD IS
password
=====

```

ここからわかる教訓としては他の人が使う可能性のあるパスワードを使うと総当たり攻撃で解析されてしまう可能性があがるため，複雑かつ推測困難なパスワードを使うことが大切です。

---

## まとめ

- パスワードはハッシュ化して保存することでセキュリティを向上させることができる
- Linuxでは`/etc/shadow`に`crypt`というライブラリを使ってハッシュ化されたパスワードが保存されている
- 総当り攻撃によりハッシュからパスワードを解析できる可能性がある。一般的なパスワードを避けることで解析される可能性を下げることができる