Linuxのパスワードクラッキングで学べたことを書いてみる
※あたりまえですが
本資料にハッキングを推奨する意図はありません
Motivation
大手SIerなどに入社すると，会社から応用情報とかネスペなどを受けるように言われますよね．
こう言う話こそ「大手っぽいなあ」と思えますが，この手の資格試験って基礎が網羅的にカバーできて重要だよなと思います．私は元々エンジニアではなかったので，そうした基礎を身につけるために興味があったセキュリティスペシャリストを受けてみることにしました．
このブログはその勉強の過程で実際に手を動かしながら学べたことを書いたものです．
トピックを並べるとこんな感じです．
- パスワードクラッキング
- Linuxのパスワード
- ハッシュ関数
- 誕生日のパラドックス
- エンコード・暗号化とハッシュの違い
- John the Ripper
- GPUって何で早いの
パスワードクラッキングとは
言って仕舞えばパスワードクラッキングとはパスワード無理矢理見つけることだと思うのですが，一応Wikipediaによると以下のように説明されています．
コンピュータシステムで保存あるいは伝達されるデータからパスワードを割り出すクラッキング手法
出所：Wikipedia
攻撃手法を大別すると，以下のような種類があります．
ブルートフォース攻撃
片っ端からパスワードを試す．当然効率は悪いが，時間とマシンパワーさえあれば理論上必ずクラックできる．
辞書攻撃
あらかじめ用意した単語リストをもとに様々な派生パスワードを作り当たるか試す．
パスワードリスト攻撃
過去のパスワード漏洩事例で確認されているパスワードから試して効率よくヒットさせる．
Have I been pwnedにある過去の漏洩パスワードリストは2020年11月に更新版で6億個にも及び，そのリストはダウンロードできます．個人情報に配慮されパスワードを生の文字列で配布せずにハッシュ化したもので配布している点や，ダウンロードが非常に大きな帯域幅を取るのでtorrentと呼ばれる分散peer to peerのダウンロード方法を推奨している点なども参考になります．
Linuxのパスワード
Linuxのユーザーログイン時に利用するパスワードは，/etc/shadow というファイルに保存されています．
昔は/etc/passwd に存在したのですが，パスワードだけはReadアクセスもsudo権限が必要なファイルに置くようになったようです．
└─# ls -lhatr /etc/passwd
-rw-r--r-- 1 root root 3.3K Jun 3 11:34 /etc/passwd
└─# ls -lhatr /etc/shadow
-rw-r----- 1 root shadow 1.9K Jun 3 11:34 /etc/shadow
（shadowファイルは othersの'r'権限がついていない）
実際にshadowファイルを開くと，パスワードがどのように保存されているかわかります．
└─# cat /etc/shadow
…
test1:$6$coolsalt$lBwFVYyzAmmx6k3N5shu4OFCnLmzNjuFhrZLwbch8ruVxelHjD7Kl8bArJd.Ncc3nbf.4xvaEGEjolJGMp6Xf/:18781:0:99999:7:::
（test1というユーザーのパスワード）
パスワードはもちろん平文で保存されているわけではなく，ハッシュという形で保存されています．というわけでハッシュについて勉強してみました．
ハッシュ関数
パスワードをあのようなランダムな文字列に変えるハッシュ関数というものがあります．Wikipediaによると以下のように説明されています．
A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
出所：Wikipedia
つまり，ハッシュ関数ではどんな文字数のインプットでも固定長の文字数に変換されます．
（'yuta'というインプットに対するハッシュ値）
ハッシュ関数にはMD5やSHA512など様々な種類があるのですが，求められる性質がいくつかあります．
1. 一方向性
出力値から入力値を求めることが困難
2. 第2原像計算困難性
ある入力に対して同じハッシュを生む別の入力を求めることが困難
3. 衝突困難性
同じハッシュを生む2つの入力を求めることが困難
私の場合は読んでいてどれも結局同じことを言ってるように思えてしまい，特に2つ目と3つ目を分けて書く意味があまりわかりませんでした．これは後述する誕生日のパラドックスを知ることでよりクリアになります．
誕生日のパラドックス
第2原像計算困難性と衝突困難性は違いがわかりにくいので，誕生日のパラドックスと呼ばれる小話を紹介したいと思います．
例えば，職場の中であなたと同じ誕生日の人がいるか考えるとします．
この時理論的には253人いると確率50％以上であなたと同じ誕生日の人がいるそうです．
では，あなたと同じかどうかは無視して職場に誕生日被りがいるかを考えるとどうなるか．
実は23人いると確率50％以上で誕生日被りが起きるのです．
これが誕生日のパラドックスと呼ばれるもので，直感と異なる理論的帰結からパラドックスと呼ばれています．
あなたと同じ誕生日の人を見つけようと思ったら，何人くらい探さないといけないのかを示しているのが第2原像計算困難性であり，”誕生日被り”を発見しようと思ったら何人くらい集めないといけないのかを示すのが衝突困難性です．後者の方がラクなのがわかりますよね．前者は強衝突耐性・後者は弱衝突耐性とも呼ばれるようです．
パスワードクラッキングは，ハッシュ関数の「第2原像計算困難性（強衝突耐性）」を破ろうとする作業になります．
ちなみに弱衝突耐性を高めないといけない例としてデジタル署名の偽造という例があるので興味のある人は読んでみると面白いです．
ハッシュとエンコーディングと暗号化と
本題からそれますがハッシュのような”ランダムな長い文字列”というのはプログラミングをしていると様々なところで目にします．しかし，それらの解像度を上げるとより面白いです．
例えば，認証で使われるJWTトークンはピリオドで3つの部分に分かれます（ヘッダ・ペイロード・シグニチャ）．ヘッダとペイロードはBase64エンコードされているだけで，デコードすれば簡単に元の情報が得られます．変換アルゴリズムさえわかれば誰でも双方向の処理ができます．
他にも，HTTPSではTLS（Transport Layer Security）プロトコルヘッダがHTTPヘッダの前についているのですが，このプロトコルのRecordプロトコルには公開鍵暗号化方式で暗号化されたデータが載っています．秘密鍵がわかれば元の情報が得られますが，そうでない場合普通はどんなメッセージが載っているのかわかりません．
このようにランダムに見える文字列も，エンコードなのか暗号化なのかハッシュなのか（またはその組み合わせ）気にしてみると面白いです．
ハッシュ（Hash）
一方向，ハッシュから元の値を出すのは原理的に不可能
エンコード（Encode）
アルゴリズムがわかれば元に戻せる
暗号化（Encrypt）
アルゴリズムだけではなく鍵がわかっていないと元に戻せない
本当はただのBase64エンコードなのに暗号化文字列だと思って安易に外部サーバーに送信したりクエリパラメーターに乗っけたりすると思わぬ事故を招くので気をつけたいところです．
John the Ripper
Linuxのパスワードクラッキングに話を戻しましょう．
John the Ripperはオープンソースのパスワードセキュリティ監査ツールです．Unix, Mac, WindowsなどさまざまなOSに対応しており，Wordpress，SSHなどにも使えるようです．日本語に訳すなら「切り裂きジョン」ということになります．
実際に使ってみる
ローカルで実行
John the Ripperをインストールしたら，あとは以下の2つを実行するだけでクラッキングが行われます．
└─# unshadow /etc/passwd /etc/shadow > crackme.txt
└─# john --wordlist=/usr/share/john/password.lst --rules crackme.txt
＊なるべく普段使いのユーザーパスワードを対象にしないよう，サンドボックスやVM上でやるのをお勧めします．一応Dockerで試す場合のDockerfileサンプルを貼っておきます．
FROM kalilinux/kali-rolling
RUN mkdir /your-directory
RUN apt update -y
RUN apt install -y kali-tools-passwords\
&& apt install -y vim
COPY . /your-directory
VOLUME /your-directory
CMD echo "This is security inspector running on Kali Linux"
GPU積んだEC2で実行
今回はg4dn.xlargeというNVIDIAのGPUが載ったインスタンスを使いました．これでも一番安いのを選んだつもりですが1時間0.71ドルはなかなかのお値段です．．
クラッキング自体の手順はローカル実行とほぼ同じですが，少しだけ事前準備が必要です．
ざっくり言うと追加的に必要なのは以下の2点です：
- GPUドライバのインストール
- CUDAのインストール
# GPUのスペック確認
lspci | grep -i nvidia
# このあたりのドライバやUtilの型番はGPUによって異なるので，以下コマンドはあくまで実装当時の例です
sudo apt install nvidia-utils-460-server
https://www.nvidia.com/Download/driverResults.aspx/169408/en-us
sudo apt-get update
sudo apt install nvidia-driver-440
sudo apt install nvidia-cuda-toolkit
sudo apt-get install build-essential libssl-dev
# John the Ripper install
wget https://www.openwall.com/john/k/john-1.9.0-jumbo-1.tar.gz
tar xfz john-1.9.0-jumbo-1.tar.gz
cd john-1.9.0-jumbo-1/src
./configure
make -s -j 4
# 正常にインストールできたか確認
sudo ./john --list=opencl-devices
sudo ./john --list=formats --format=opencl
ちなみにうまくインストールできているとこんな感じになります．
$ sudo ./john --list=opencl-devices
Platform #0 name: NVIDIA CUDA, version: OpenCL 1.2 CUDA 11.0.228
Device #0 (1) name: Tesla T4
Device vendor: NVIDIA Corporation
Device type: GPU (LE)
Device version: OpenCL 1.2 CUDA
Driver version: 450.102.04 [recommended]
Native vector widths: char 1, short 1, int 1, long 1
Preferred vector width: char 1, short 1, int 1, long 1
Global Memory: 15109 MB (ECC)
Global Memory Cache: 1280 KB
Local Memory: 48 KB (Local)
Constant Buffer size: 64 KB
Max memory alloc. size: 3777 MB
Max clock (MHz): 1590
Profiling timer res.: 1000 ns
Max Work Group Size: 1024
Parallel compute cores: 40
CUDA cores: 2560 (40 x 64)
Speed index: 4070400
Warp size: 32
Max. GPRs/work-group: 65536
Compute capability: 7.5 (sm_75)
Kernel exec. timeout: yes
PCI device topology: 00:03.6
Johnコマンドを利用するときはformatを指定することでCPUではなくGPUを使って計算が実行されます．
unshadow /etc/passwd /etc/shadow > crackme.txt
# 必要なハッシュアルゴリズムによって以下を使い分ける
sudo ./john --format=sha512crypt-opencl crackme.txt
sudo ./john --format=md5crypt crackme.txt
sudo ./john --format=sha512crypt crackme.txt
ちなみにこれが実行中のGPUのメトリクス．
$ nvidia-smi
Sun Mar 28 06:08:12 2021
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 450.102.04 Driver Version: 450.102.04 CUDA Version: 11.0 |
|-------------------------------+----------------------+----------------------+
| GPU Name Persistence-M| Bus-Id Disp.A | Volatile Uncorr. ECC |
| Fan Temp Perf Pwr:Usage/Cap| Memory-Usage | GPU-Util Compute M. |
| | | MIG M. |
|===============================+======================+======================|
| 0 Tesla T4 Off | 00000000:00:1E.0 Off | 0 |
| N/A 52C P0 69W / 70W | 118MiB / 15109MiB | 98% Default |
| | | N/A |
+-------------------------------+----------------------+----------------------+
+-----------------------------------------------------------------------------+
| Processes: |
| GPU GI CI PID Type Process name GPU Memory |
| ID ID Usage |
|=============================================================================|
| 0 N/A N/A 780 G /usr/lib/xorg/Xorg 4MiB |
| 0 N/A N/A 7675 C ./john 111MiB |
+-----------------------------------------------------------------------------+
ちなみになぜGPU？
こういう計算はGPUが得意というのは結構多くの人が直感的に知っていると思うのですが，「あれ何でなんだろう」と思ったのでこの辺りも調べてみました．
マイクロアーキテクチャとしてはGPGPU（General Purpose GPU）はALU（最後の最後でコンピュータがビット演算する装置）の数がCPUより桁違いに多い．なので並列処理（Parallelism）が得意で並列処理に向く処理は全体としてGPUがCPUより早くこなせる．パスワードクラッキングは入力パスワードだけを変化させて同じ処理をさせるので並列しやすいからGPUと相性がいい．というのが説明になるのかなと思います．
CPU要らなくない？と言いたいところですがコア単体での処理（clock frequency）はCPUの方が高いですし，いろんな処理をこなすのには適しているようです．
CPUというのは長年レイテンシの最小化を追求してきたが，GPUというのはスループットの最大化を目指した成果であるという説明は個人的に刺さりました．
そして手順の中にあったCUDAというのはGPGPUに並列処理を実行させるためのAPI（WebAPIというより本来の意味のAPI）です．
GPUのマイクロアーキテクチャについてはこの動画が一番わかりやすかったです．
ハッキング手法としての特徴
ハッキング手法として実際には以下のような手順がとられるようです．
- フィッシングやOSコマンドインジェクション脆弱性をついたRCE（リモートコードエグゼキューション）などでsudoユーザー権限のコマンドが実行できるようにする
- shadowファイルを攻撃者の用意するリモートサーバーへ送信する
- 取得したハッシュをGPUを積んだ攻撃者のサーバー上でクラッキングする
クラッキングがオフラインで行われる点が怖いところです（ちなみにWiFiパスワードクラッキングも同様です）．表面的で恐縮ですが守る側としては最低限の対処はしておきたいところです．
1の防衛策
- ＜予防＞OSやライブラリの日頃のアップデート
2の防衛策
- ＜検知＞不信な通信を検知できるようにする
3の防衛策
- ＜予防＞推測しにくい単語を使う・パスワード長を長めに設定
まとめ
Linuxのパスワードクラッキングというテーマこそ実用性の低いものですが，これだけでも結構多くのことを勉強できるのではないかと思います．
セキュリティを勉強することはLinuxとネットワークを勉強することに他ならず，純粋な学びが多いのでこれからも続けていこうと思います．
長文ですが読んでいただきありがとうございました!!
＊speakerdeck
参考文献
パスワードクラッキング
ハッシュ関数，ハッシュ・エンコード・暗号化
誕生日のパラドックス
John the Ripper
実装Memo
Discussion