データの打ち込みを回避するために手書き文字をスキャンして認識する

今回の目的

こんにちは。

Link-Uの町屋敷です。

今回は下のような手書き文字をパソコンにスキャンして認識するプログラムを作ろうと思います。

テストではどこに文字があるかの情報は全く与えず、文字の場所がどこにあるのかから機械に算出させます。(訓練データもいちいち座標与えるのがめんどくさかったのでそうなりましたが…)

普通のアルファベットと微妙に違うのがわかるでしょうか。

実はこれらは全部cに線を書き足してabcdeにしています。

何のためにこんなものの認識をしたいかというと、外部に出さないようなデータのアノテーション(ラベル付け)をするときに、項目とそれに対応するcが書かれた紙を用意して、項目に該当する部分だけcをaとかeなどに変更してあとAIに任せれば作業効率が上がるかなって。

自分でスキャンされた手書き文字認識を実装してみる

さっそく始めましょう。

画像中の物体を認識するための手法としてR-CNNを参考にします。

画像からの物体認識では大きく二つのパートがあります。画像の中から文字が書かれている領域の候補を選択するパートとその領域内に書かれた文字が何なのかを認識するパートです。

Kerasで一度にR-CNNをできるものもある(より新しいMask-RCNNですら存在する)ようですが、地道に領域をから候補を選択してCNNをするという方法でやります。

Selective Search

画像の中から文字が書かれている領域の候補を選択する方法としてR-CNNの元論文ではSelective searchが使われています。Selective searchにはpythonのパッケージが公開されているのでサンプルを改造して試してみましょう。入力画像は屋上から撮った写真を400*300にリサイズしたものです。

import selectivesearch
from matplotlib import pyplot as plt
import matplotlib.patches as mpatches

def search(img):
    #img = img[0:300,200:800]
    # perform selective search
    img_lbl, regions = selectivesearch.selective_search(
    #    img, scale=5, sigma=0.25, min_size=20)
        img, scale=5, sigma=5, min_size=30)
    candidates = set()
    for r in regions:
        #excluding same rectangle (with different segments)
        if r['rect'] in candidates:
            continue
        # excluding regions smaller than 2000 pixels
        if r['size'] < 30:
            continue
        # distorted rects
        x, y, w, h = r['rect']
        if h == 0 or w == 0:
            continue
        if w / h > 8 or h / w > 8:
            continue
        candidates.add(r['rect'])

    #draw rectangles on the original image
    fig, ax = plt.subplots(ncols=1, nrows=1, figsize=(6, 6))
    ax.imshow(img)
    for x, y, w, h in candidates:
        rect = mpatches.Rectangle(
            (x, y), w, h, fill=False, edgecolor='red', linewidth=1)
        ax.add_patch(rect)
  
    plt.show()
    return candidates

def test_selective_search():
    im = imread("tower.png")
    search(im[:,:,0:3]) #アルファチャンネルを消す

if __name__ == "__main__":
    test_selective_search()
    learn()
    test()

こんな感じで領域の候補が出力されれば成功です。同じ物体に複数の領域が重なっていますがこれが正しい出力結果です。

Selective searchのパッケージが正しく動作していることが分かったので、さっそく訓練データを入れていきましょう。今回の訓練データは、フォントの大きさが違うcが書かれた紙を4枚印刷し、線を付け加えて作ったa,b,d,eの紙をスキャナーで取り込んで縮小したものです。(縮小したものを使わないとSelective Searchの処理が重い)

実際のものがこれです(aのデータ)、折れとか汚れ(スキャン時にできた)とか雑音はいりまくりです。フォントサイズが変わってもAIが対応できるように微妙にフォントの大きさを変えてますが意味があるかは対称を取ってないのでわかりません。

さてこのままさっきのSelective searchに入れてみましょう。

どえらい結果になります。雑音のせいなので取り除きましょう。

今回は背景が白で黒い文字のみの検出を目指しているのでべたに2値化。

    gray = rgb2gray(im)       # グレイスケールに変換
    whiteRegion = gray > 0.8  # 白部分の雑音除去
    gray[whiteRegion] = 1
    whiteRegion = gray <= 0.8  # 黒部分の雑音除去
    gray[whiteRegion] = 0
    im = gray2rgb(gray)

さてこのままさっきのSelective searchに入れてみましょう。<img class=”alignnone wp-image-337 size-full” src=”https://tech.link-u.co.jp/wp-content/
また、Selective searchの設定も変えましょう。

1文字の認識には長方形の領域はいらないので消去、

また上のほうの小さい文字が認識できてないのでomegaを変更して感度も上げ、画像全体が領域として選択されているのでこれも弾きます。

img_lbl, regions = selectivesearch.selective_search(
img, scale=5, sigma=0.25, min_size=20)
#img, scale=5, sigma=8, min_size=30)
candidates = set()
for r in regions:
#excluding same rectangle (with different segments)
if r['rect'] in candidates:
continue
#excluding regions smaller than 2000 pixels
if r['size'] < 20 or r['size'] > 3000:
continue
# distorted rects
x, y, w, h = r['rect']
if h == 0 or w == 0:
continue
if w / h > 2 or h / w > 2:
continue
candidates.add(r['rect'])

まともになりました。

しかしよく見て見ると一つの文字に複数の領域が重なっています。

もとのR-CNNの論文ではgreedy non-maximum suppressionなどを駆使して除去していますが。今回は汚れなどを除いて背景がなく、文字が重なることもなく、また各文字の大きさも一定なので、単純にある領域に近い領域か存在した場合、領域の中心座標だけ残して領域は全部消し、その点から上下左右16pixを新しい領域にしました。

def get_candidate(img_path):
    def is_checked(checked, test_point,r):
        for c in checked:
            if np.linalg.norm(c - test_point) < r:
                return True
        return False

    im = imread(img_path)
    gray = rgb2gray(im)       # グレイスケールに変換
    whiteRegion = gray > 0.8  # 白部分の雑音除去
    gray[whiteRegion] = 1
    whiteRegion = gray <= 0.8  # 黒部分の雑音除去
    gray[whiteRegion] = 0
    # = median(gray, disk(1))
    #gray = denoise_wavelet(gray) #ごましお雑音除去
    im = gray2rgb(gray)
    cand = search(im)
    print(np.shape(im))
    g_img = np.asarray(gray)
    checked_points = []
    images = []
    ren = 16
    for c in cand:
        xc = int(c[0] + c[2]/2)
        yc = int(c[1] + c[3]/2)
        if len(checked_points) is not 0:
            if is_checked(checked_points, np.array([xc,yc]), 10):
                continue
        image = resize(g_img[yc-ren:yc+ren,xc-ren:xc+ren], (28,28))
        images.append(image)
        #X = np.array([image])

        #plt.imshow(X[0], cmap='gray')
        checked_points.append(np.array([xc,yc]))
        #plt.show()
    return images, checked_points

これをa,b,c,d,eの5枚に行います。これで教師データとして画像データを取り出すことができます。

しかし、ラベルデータがないので

CNN

作ったデータセットでCNNの識別器を作ります。

スクリプトは以下の通り。

def learn():
    import glob
    img_pathes = glob.glob("..\\..\\Documents\\dataset\\abcde\\learn\\scan\\*.*")

    x = np.array([])
    y = np.array([])
    for ip in img_pathes:
        print(ip)
        if "a_" in ip:
            i = 0
        elif "b_" in ip:
            i = 1
        elif "c_" in ip:
            i = 2
        elif "d_" in ip:
            i = 3
        elif "e_" in ip:
            i = 4
        else:
            raise("Unexpected File is Loaded")


        imgs, _ =  get_candidate(ip)
        nimgs = np.array(imgs)
        x = np.append(x, nimgs)
        print(len(x))
        y = np.append(y, np.array(len(imgs) * [i]))
        print(len(y))
    x = np.reshape(x, (-1,28,28))
    seed = 123
    (X_train, X_valid, Y_train, Y_valid) = train_test_split(x, y, test_size=0.15, random_state=seed)
    learn_cnn(X_train, X_valid, Y_train, Y_valid)
    py = load_predict(x)
    for a,b,c in zip(x,y,py):
        if not b == np.argmax(c):
            print((b,c))
            plt.imshow(a, cmap='gray')
            plt.show()

def learn_cnn(X_train, X_test, Y_train, Y_test):
    X_train = X_train.reshape(X_train.shape[0], 28, 28, 1).astype('float32')
    X_test  = X_test.reshape(X_test.shape[0], 28, 28, 1).astype('float32')

    #X_train = X_train / 255
    #X_test  = X_test / 255
    # one hot encode outputs
    Y_train = np_utils.to_categorical(Y_train)
    Y_test  = np_utils.to_categorical(Y_test)

    num_classes = Y_test.shape[1]


    # create model
    model = Sequential()
    model.add(Conv2D(64, (5, 5), input_shape=(28, 28, 1), activation='relu'))
    model.add(MaxPooling2D(pool_size=(4, 4)))
    model.add(Conv2D(32, (3, 3), activation='relu'))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    model.add(Dropout(0.2))
    model.add(Flatten())
    model.add(Dense(128, activation='relu'))
    model.add(Dense(5, activation='softmax'))

    # Compile model
    model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
    model.fit(X_train, Y_train, validation_data=(X_test, Y_test), epochs=500, batch_size=200, verbose=2)

    # Final evaluation of the model
    scores = model.evaluate(X_test,Y_test, verbose=0)
    print("CNN Error: %.2f%%" % (100-scores[1]*100))

    model.save('weights.model')

Kerasのサンプルに畳み込み層とプーリング層を追加したものです。多分これが最善ではないです。

パラメータを変えるなど各種改造をするときは、testデータを使わずtrainデータを分割して評価して最善のものを目指します。

このような結果が出力されます。テストデータのうち2パーセント間違えたことがわかります。

また、このスクリプトは、学習後に間違えたデータを表示します。

この2つのデータを間違えたようです。(実際は左がa右がd)

試行錯誤繰り返し、満足したところでtestデータを使って認識結果を出力してみましょう。

教師データを分割していましたが、もったいないのですべてを教師データとしてもう一度CNNを学習させます。

learn_cnn(x, X_valid, y, Y_valid)

テストデータは最初に貼ったデータと

このスパースなデータです。

いつものGPUのideapadS720のスピードの差はこちら

GPUのほうが6倍くらい速いです。

一回大量データかつモデルが複雑な場合もやらねばなあ。

で、文字の識別結果は以下の通り。

画像の中の?はCNNの出力を見てAIに自信がなさそうな時に付けています。自信度がなぜわかるか具体的に書くと今回CNNの出力は5クラスの識別問題なので5次元のベクトルで、それぞれが0から1の値を持っています。5つの次元は[a,b,c,d,e]を表します。

例えば、わかりやすいaの画像が入力された場合5次元のベクトルは[1, 0 , 0, 0, 0]に近い値を出力します。少しdとまぎらわしいaが入力された場合[0.8, 0, 0, 0.2, 0]のような値を出します。このベクトルの数値を見ることによってAIの自信度がわかるということです。

1つめは4ミスでしたが2つ目はノーミスでした。もう少し教師データを増やせば2つぐらいは減らせると思います。丁寧に書けば使えるかなといった感じです。

まとめ

今回はスキャンした手書き文字を認識するプログラムを作りました。

字をきれいに書けば使える程度のものは作れたと思います。

プログラム全文

from keras.models import Sequential
from keras.layers import Dense
from keras.layers import Dropout
from keras.layers import Flatten
from keras.layers.convolutional import Conv2D
from keras.layers.convolutional import MaxPooling2D
from keras import backend as K
from keras.utils import np_utils
from sklearn.model_selection import train_test_split
import numpy as np
from matplotlib import pyplot as plt
import matplotlib.patches as mpatches
from decimal import *
import skimage
from skimage.filters.rank import median
from skimage.morphology import disk
from skimage.transform import resize
from skimage.restoration import denoise_wavelet
from skimage.io import imread
from skimage.color import rgb2gray, gray2rgb
from PIL import Image, ImageDraw, ImageFont
import selectivesearch
import time

def load_predict(X):
    X  = X.reshape(X.shape[0], 28, 28, 1).astype('float32')
    #X = X / 255
    # create model
    model = Sequential()
    model.add(Conv2D(64, (5, 5), input_shape=(28, 28, 1), activation='relu'))
    model.add(MaxPooling2D(pool_size=(4, 4)))
    model.add(Conv2D(32, (3, 3), activation='relu'))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    model.add(Dropout(0.2))
    model.add(Flatten())
    model.add(Dense(128, activation='relu'))
    model.add(Dense(5, activation='softmax'))

    # Compile model
    model.compile(loss='sparse_categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
    model.load_weights('weights.model')
    return model.predict(X)

def search(img):
    #img = img[0:300,200:800]
    # perform selective search
    img_lbl, regions = selectivesearch.selective_search(
        img, scale=5, sigma=0.25, min_size=20)
        #img, scale=5, sigma=8, min_size=30)
    candidates = set()
    for r in regions:
        #excluding same rectangle (with different segments)
        if r['rect'] in candidates:
            continue
        # excluding regions smaller than 2000 pixels
        if r['size'] < 20 or r['size'] > 3000:
            continue
        # distorted rects
        x, y, w, h = r['rect']
        if h == 0 or w == 0:
            continue
        if w / h > 2 or h / w > 2:
            continue
        candidates.add(r['rect'])

    #draw rectangles on the original image
    #fig, ax = plt.subplots(ncols=1, nrows=1, figsize=(6, 6))
    #ax.imshow(img)
    #===========================================================================
    # for x, y, w, h in candidates:
    #     rect = mpatches.Rectangle(
    #         (x, y), w, h, fill=False, edgecolor='red', linewidth=1)
    #     ax.add_patch(rect)
    #===========================================================================

    #plt.show()
    return candidates

def test_selective_search():
    im = imread("a_scan.png")
    search(im[:,:,0:3])

def learn():
    import glob
    #img_pathes = glob.glob("..\\..\\Documents\\dataset\\abcde\\learn\\*.*")
    #img_pathes += glob.glob("..\\..\\Documents\\dataset\\abcde\\learn\\scan\\*.*")
    img_pathes = glob.glob("..\\..\\Documents\\dataset\\abcde\\learn\\scan\\*.*")

    x = np.array([])
    y = np.array([])
    for ip in img_pathes:
        print(ip)
        if "a_" in ip:
            i = 0
        elif "b_" in ip:
            i = 1
        elif "c_" in ip:
            i = 2
        elif "d_" in ip:
            i = 3
        elif "e_" in ip:
            i = 4
        else:
            raise("Unexpected File is Loaded")


        imgs, _ =  get_candidate(ip)
        nimgs = np.array(imgs)
        x = np.append(x, nimgs)
        print(len(x))
        y = np.append(y, np.array(len(imgs) * [i]))
        print(len(y))
    x = np.reshape(x, (-1,28,28))
    seed = 123
    (X_train, X_valid, Y_train, Y_valid) = train_test_split(x, y, test_size=0.15, random_state=seed)
    #learn_cnn(x, X_valid, y, Y_valid)
    learn_cnn(x, X_valid, y, Y_valid)
    py = load_predict(x)
    for a,b,c in zip(x,y,py):
        if not b == np.argmax(c):
            print((b,c))
            plt.imshow(a, cmap='gray')
            plt.show()

def learn_cnn(X_train, X_test, Y_train, Y_test):
    t = time.time()
    X_train = X_train.reshape(X_train.shape[0], 28, 28, 1).astype('float32')
    X_test  = X_test.reshape(X_test.shape[0], 28, 28, 1).astype('float32')

    #X_train = X_train / 255
    #X_test  = X_test / 255
    # one hot encode outputs
    Y_train = np_utils.to_categorical(Y_train)
    Y_test  = np_utils.to_categorical(Y_test)

    num_classes = Y_test.shape[1]


    # create model
    model = Sequential()
    model.add(Conv2D(64, (5, 5), input_shape=(28, 28, 1), activation='relu'))
    model.add(MaxPooling2D(pool_size=(4, 4)))
    model.add(Conv2D(32, (3, 3), activation='relu'))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    model.add(Dropout(0.2))
    model.add(Flatten())
    model.add(Dense(128, activation='relu'))
    model.add(Dense(5, activation='softmax'))

    # Compile model
    model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
    model.fit(X_train, Y_train, validation_data=(X_test, Y_test), epochs=500, batch_size=200, verbose=2)

    # Final evaluation of the model
    scores = model.evaluate(X_test,Y_test, verbose=0)
    print("CNN Error: %.2f%%" % (100-scores[1]*100))

    model.save('weights.model')
    print(time.time()-t)

def get_candidate(img_path):
    def is_checked(checked, test_point,r):
        for c in checked:
            if np.linalg.norm(c - test_point) < r:
                return True
        return False

    im = imread(img_path)
    gray = rgb2gray(im)       # グレイスケールに変換
    whiteRegion = gray > 0.8  # 白部分の雑音除去
    gray[whiteRegion] = 1
    whiteRegion = gray <= 0.8  # 黒部分の雑音除去
    gray[whiteRegion] = 0
    # = median(gray, disk(1))
    #gray = denoise_wavelet(gray) #ごましお雑音除去
    im = gray2rgb(gray)
    cand = search(im)
    print(np.shape(im))
    g_img = np.asarray(gray)
    checked_points = []
    images = []
    ren = 16
    for c in cand:
        xc = int(c[0] + c[2]/2)
        yc = int(c[1] + c[3]/2)
        if len(checked_points) is not 0:
            if is_checked(checked_points, np.array([xc,yc]), 10):
                continue
        image = resize(g_img[yc-ren:yc+ren,xc-ren:xc+ren], (28,28))
        images.append(image)
        #X = np.array([image])

        #plt.imshow(X[0], cmap='gray')
        checked_points.append(np.array([xc,yc]))
        #plt.show()
    return images, checked_points

def test():
    import glob
    img_pathes = glob.glob("..\\..\\Documents\\dataset\\abcde\\test\\*")

    label_to_char = ["a", "b", "c", "d", "e"]
    i = -1
    for ip in img_pathes:
        x = np.array([])
        y = np.array([])
        print(ip)
        imgs, points =  get_candidate(ip)
        nimgs = np.array(imgs)
        x = np.append(x, nimgs)
        print(len(x))
        y = np.append(y, np.array(len(imgs) * [i]))
        print(len(y))

        x = np.reshape(x, (-1,28,28))
        seed = 123
        pre_y = load_predict(x)
        im = Image.open(ip)
        draw = ImageDraw.Draw(im)
        font = ImageFont.truetype("C:\\Windows\\Fonts\\meiryob.ttc", 16)
        for py, p in zip(pre_y, points):
            pst = np.argsort(py)
            max_val = np.max(py)
            am1, am2 = pst[-1], pst[-2]
            if   max_val > 0.95:
                draw.text((p[0]+16, p[1]), label_to_char[am1], fill=(255, 0, 0), font=font)
            elif max_val > 0.8:
                draw.text((p[0]+16, p[1]), label_to_char[am1] +"," + label_to_char[am2] + "?", fill=(255, 0, 0), font=font)
            elif max_val > 0.4:
                draw.text((p[0]+16, p[1]), label_to_char[am1] +"," + label_to_char[am2] + "??", fill=(255, 0, 0), font=font)
            else:
                draw.text((p[0]+16, p[1]), "?", fill=(255, 0, 0), font=font)
        im.save("hand_only_sparse.png")
        im.show()

if __name__ == "__main__":
    #test_selective_search()
    learn()
    test()

GPUを使って無線LANをクラックする話・準備編

<Youtuber語法>ブンブン・ハロー、Link-U。どうも、平藤です。

えーそれでは今日はね、無線LANのパスワードをクラックするPyrit、これのほうを、CPUとかGPUで動かしてみようと思いまーす。</Youtuber語法>

はい。というわけで、弊社の業務用無線LANルータ、SSIDがその名も「zoi」のWPA2-PSKのパスワードをCPUやGPUでクラックすることで、機械学習とはまた違った「アプリケーション」でのパフォーマンスを実測してみたいと思います。

パケットをキャプチャする

ちなみに写真はオフィスにある会議室の机の下です。いつもと見慣れない風景で、ちょっとかっこよくない?…そうでもないか。

なにはなくとも、まずは攻撃するために、ルータがスマホをパスワードで認証して通信を開始する「ハンドシェイク」の瞬間のパケットをキャプチャしましょう。以下、わたしの使っているMacBook Pro + OSX HighSierraでWPA2-PSKのパケットをキャプチャする方法を説明します。Linuxでの方法は他の人に譲ることにします。餅は餅屋なので。

まずは次のコマンドで、どんな電波が飛んでるかをチェックします:

sudo /System/Library/PrivateFrameworks/Apple80211.framework/Versions/Current/Resources/airport -s

結果はこんな感じです:

% sudo
/System/Library/PrivateFrameworks/Apple80211.framework/Versions/Current/Resources/airport -s
Password:
SSID BSSID RSSI CHANNEL HT CC SECURITY (auth/unicast/group)
LU-MOBILE 00:1a:eb:b2:c3:b6 -66 112,-1 Y JP WPA2(PSK/AES,TKIP/TKIP)
PAI-AP2.4G1 34:76:c5:4d:a7:c8 -76 10,-1 Y JP WPA(PSK/AES,TKIP/TKIP) WPA2(PSK/AES,TKIP/TKIP)
PAI-AP2.4G2 06:76:c5:4d:a7:c8 -75 10,-1 Y JP NONE zoi 00:1a:eb:ac:51:20 -44 9 Y JP WPA2(PSK/AES/AES)
LU-MOBILE 00:1a:eb:b2:c3:b5 -54 6 Y JP WPA2(PSK/AES,TKIP/TKIP)
RADIX01 4c:e6:76:ae:00:1e -86 6 Y -- WPA(PSK/AES,TKIP/TKIP) WPA2(PSK/AES,TKIP/TKIP)
Eviry24G c0:25:a2:89:b2:72 -61 7 Y JP WPA2(PSK/AES/AES)
GW-office_G1 34:3d:c4:86:83:d0 -90 3 Y -- WPA2(PSK/AES/AES)
zoi 00:1a:eb:ac:51:30 -54 40 Y JP WPA2(PSK/AES/AES)

まぁ色々と出てきますが、今回注目なのはこの一番最後の行です:

zoi 00:1a:eb:ac:51:30 -54  40      Y  JP WPA2(PSK/AES/AES)

ここから、SSID「zoi」のBSSID(MACアドレス)が「00:1a:eb:ac:51:30」なこと、チャンネルが40chなことが読み取れますので、これをメモっておきます。

おっと、ここで質問をいただきました。

「zoiは上にもチャンネル9のやつがあるけど?」

良い質問です。おっしゃる通りです。いやまぁ今わたしが考えた質問なんですが。

チャンネルは13番までがいわゆる「2.4GHz」帯で、それ以降は「5GHz」帯になります。 2.4GHz帯の方をキャプチャしても、もちろん構いません。当たり前ですが、パスワードはどの周波数でも共有なので、クラックできればどちらも同じパスワードが得られます。ただ、これも当たり前ですが、ハンドシェイクが行われている場面をキャプチャできなければクラックには使えません。見てない家政婦は事件も解決できないってやつです。手元にあるどんな一般的なご家庭にもありそうな最近のスマホは5GHz帯をデフォルトで使うようになっているようでしたので、これからは40chだけに着目していきます。

で、次に、実際にキャプチャするコマンドがこちらになります(en0は内臓無線LANアダプタのデバイス名です):

% sudo /System/Library/PrivateFrameworks/Apple80211.framework/Versions/Current/Resources/airport en0 sniff 40
Password:
Capturing 802.11 frames on en0.
^CSession saved to /tmp/airportSniffGUDQbe.cap.

最後に表示されたのがキャプチャされた結果のファイルです。これをPyritに解析してもらう事になります。

ああ、一つ注意があります。これを使うとMacの無線LANが一切使えなくなって、ネットも使えなくなります。ダウロードとかsshの接続が切れても困らない時にやってください。あと、この理由があるので、MacBook Proだけではキャプチャはできません。スマホか何か他のデバイスが必要です。

あともう一つ注意としては、スマホの「設定」画面でWiFiをon-offしただけではハンドシェイクは行われません。再起動してください。今回は4回ほど再起動しました。…回数に「おまじない」以上の意味はありませんので、ハンドスピナー的に飽きるまで再起動してください。

これももう一つ注意ですが。tcpdumpはWPA2のハンドシェイクが終わった後のパケットしか見れません。つまり、クラックには利用できません。なんでかというと、それはそもそもtcpdumpのキャプチャするレイヤーがWPA2より一つ上なのと、tcpdumpの使ってBarkley Packet Filterの制限もあるような気がするのですが、OSXのカーネルに立ち入るのは今日は流石に勘弁しといてやりましょうぜ。でもフォーマットはtcpdumpの読み書きできるpcapフォーマットです。なんかちょっと不思議な気分。

WPA2-PSKで「おててつなぐ」ところを観察

さて。この無線LANルータ(厳密にはブリッジ)「zoi」は、WPA2-PSKによって隣のオフィスの人や、たまにやってくる「おらけんま」ことテイルゲーターから守られております。このWPA2-PSKを倒すには、まずこの敵のことをよく観察して理解しなければなりません。これはゲームの攻略だけでなく無線LANクラックにおいても同じです。たぶん。というわけで、さきほどキャプチャした実際のやりとりを眺めながら、WPA2-PSKでパスワード認証する仕組みを実際に見てみましょう。

すぐ上に書いた通り、キャプチャしたファイルはtcpdumpで読めますが、細かい情報に関しては表示してくれないようでしたので、GUIでパケットの情報が見れるWiresharkを使います。鮫好きにもやさしいブログなのです。嘘です。

ビーコン

WiFiに接続しようって時に、無線LANのルーターのリストがスマホに表示されますよね?そのためにルーターが虚空に向かって己の存在をシャウトしている様子がこちらです:

上でハイライトされてる行を見ると、SSID=zoiの「ビーコン」フレームであることや、「zoi」がアライド・テレシス製な事も書いてあります。だいたい1/10秒ごとに射出されているようなので、人間の時間スケール的には「常時叫びっぱなし」といったところでしょうか。ちなみに、さらにProbe-requestというメッセージをスマホから叫ぶと、「誰かいるか〜!?」と聞くことができます。機械にとっては、1/10秒っていうのは「永遠」なんでしょうね。

さて、中身を見ていきましょう。300バイトの中に密に詰まったたくさんの情報があって情報の大洪水に流されそうになりますが、淡々と情報を見ていくと「RSN Information」というところにAESと書いてあります。もっというと、PSKというのも下の方に書いてあります。ここで「zoiでつなぐ時はAESで暗号化してPSKで認証するんだぞい!」と叫んでいるわけです。秒間10回も。ええ、無線LANルータの仕事も大変なのですよ。

アソシエーション手続き

無線LANルータを見つけたら「繋がせていただけないでしょうか?」とまずは声を掛ける「アソシエーション手続き」が始まります。ただ、ここでは「繋ぎたいんですが」と申し出るだけです。玄関で言うならピンポンを押して「佐川急便でーす」という行為に近いでしょうか。

秒間10回ビーコンが叫んでいることもあって、これを手動で探すのは難しいです。そんな時は、上の「表示フィルタ」ってところに「wlan.fc.type_subtype eq 11」と打ち込んでみてください

Authentication Request

「佐川急便でーす」に相当するように、SONYのMACアドレス(スマホ)からアライド・テレシスのMACアドレス(zoi)へのメッセージである旨が記載されています。

Authenticationリクエストは、Authenticationリクエストといいつつ、単に名乗るだけです。パスワードに関係する内容をやりとりしたりはしません。もっというと、歴史的事情があって今は形骸化しているらしいです。まさに「あいさつ」ですね。

パスワードをクラックするのには関係ないので一切無視してもいいんですが、この辺も「そういえばそもそも無線LANってどうやって繋がってんだ!?」という見学気分で流れるように見ていきまます。こういう経験の積み重ねがいざという時のネットワークデバッグに…役立つといいね。

Association Request

形骸化したAuthenticationリクエストの代わりに色々な情報が詰まっているのが、Associationリクエストです。パケットを眺めてみると、図のようにデータレートが書かれています。「zoi」は54MBit/secまでしか対応してないらしいです。知らなかった…。

ここには接続するために必要な細々とした情報はたくさん乗っていますが、パスワードとか認証に関係する情報は乗っていません。なので、これも流していきますよ。

Keyメッセージ

次に続く「Key」メッセージがパスワードで認証するために使われるメッセージです。4つあるので、「4-way handshake」と言います。玄関の例えでいうなら、窓から見える佐川の制服、声(先週と同じ人だ!とか)、手元にある再配達表なんかを見て、本当にドアの向こうにいるのが佐川のお兄さんであって、全然関係ない消火器を売る人とかでないことを確信してドアを開けるためのやりとりです。

今はざっくり見ていただくだけで良いのですが、「パスワード」を直接送っているわけではないことを観察しましょう。当たり前です。パスワード、つまり「あいことば」を直接喋ってしまったら、こうやってずっと「聞いて」いれば、すぐ「あいことば」がバレてしまいます。もっと「ふしぎな方法」で、こっそり、ひっそり、でも堂々と、こうやってやりとりしています。

これに関しては今後の記事でもっとくわしく書く予定ですが、お互いに事前に共有したパスワード(PSK)を共有している同士で、この”Nonce”とか”IV”とかなんとかついてる、4つのメッセージを使って「ある計算」をすれば、「あいことば」を直接喋らなくとも、「我々は同じ合言葉を共有しあった仲間だ!」と確信しあえる…らしいことは覚えておきましょう。まぁもっとも、我々はこれからその「連帯感」「信頼感」を全力でぶち壊す側に回るわけですが。ふふっ、いい気味だ。

Pyritをビルドする

ここから話は手元のMacBook Proから、リモートのGPUやCPUのいっぱい積まれたUbuntuサーバへと話が変わります。

次はPyritのビルドです。無線LANクラック道は、長く険しい坂なのです。打ち切りにならない程度に頑張っていきましょう。

Pyritは実はビルドなんかしなくてもaptで入ります。

$ apt search pyrit
ソート中... 完了
全文検索... 完了
pyrit/xenial 0.4.0-5 amd64
  GPGPU-driven WPA/WPA2-PSK key cracker

pyrit-opencl/xenial 0.4.0-1 amd64
  OpenCL extension module for Pyrit

pyrite-publisher/xenial 2.1.1-11 amd64
  Convert html and text documents to palm DOCformat

wifite/xenial,xenial 2.0r85-1 all
  Python script to automate wireless auditing using aircrack-ng tools

が、見てもらえばわかるとおり、OpenCLバージョンは入ってもCUDAバージョンは入らないのと、これから改造して遊ぼう〜とか考えるとビルドする方がいいので、ビルドしていきます。

必要なライブラリのインストール

粛々とインストールしましょう。環境によっては足りないやつとかもあるかもしれませんが、その辺は柔軟にお願いします:

sudo apt install clang libpcap-dev openssl-dev python-virtualenv libpython-all-dev

ソースのclone

今後改造することもあるかもしれないのでわたしの個人リポジトリにforkしてしまいましたので、そこからcloneしてください。

git clone https://github.com/ledyba/Pyrit
cd Pyrit

CPU版のビルド

CPUだけで解析するやつを一旦ビルドしましょう。

そのための呪文は次に置いておくので唱えてください。

# venv環境を作って有効にします。Pyritは2.7じゃないと動かない…。
$ virtualenv .env --python=/usr/bin/python2.7
$ . .env/bin/activate

# Pythonからcapファイルを見るためのライブラリです。
# 古い2.3.3でないと動かないので、バージョンを指定してインストール。
$ pip install "scapy==2.3.3"

# ビルド。
$ python setup.py build

# 己の作ったvenv環境にいることを確認(しないとたまに間違えるので…)
$ which python
/home/psi/src/Pyrit/.env/bin/python

# インストール
$ python setup.py install

…「ビルド方法」って出てくる結果は単純なのにどうしてこうも試行錯誤が必要なんだろう?

ちなみに上記の呪文でMacでもビルドして実行できるはずなのですが、「scapyが見つからない」という謎のエラーメッセージがでるのでMacの人は注意してください(うそつけちゃんとバージョン指定して入れたやんけ)。わたしは今日のところは諦めました。

なにはなくともビルドできたはずですので、次の呪文を唱えてCPUが48個あることを確認します。

$ pyrit list_cores
Pyrit 0.5.1 (C) 2008-2011 Lukas Lueg - 2015 John Mora
https://github.com/JPaulMora/Pyrit
This code is distributed under the GNU General Public License v3+

The following cores seem available...
#1:  'CPU-Core (SSE2/AES)'
#2:  'CPU-Core (SSE2/AES)'
#3:  'CPU-Core (SSE2/AES)'
#4:  'CPU-Core (SSE2/AES)'
#5:  'CPU-Core (SSE2/AES)'
#6:  'CPU-Core (SSE2/AES)'
#7:  'CPU-Core (SSE2/AES)'
#8:  'CPU-Core (SSE2/AES)'
#9:  'CPU-Core (SSE2/AES)'
#10:  'CPU-Core (SSE2/AES)'
#11:  'CPU-Core (SSE2/AES)'
#12:  'CPU-Core (SSE2/AES)'
#13:  'CPU-Core (SSE2/AES)'
#14:  'CPU-Core (SSE2/AES)'
#15:  'CPU-Core (SSE2/AES)'
#16:  'CPU-Core (SSE2/AES)'
#17:  'CPU-Core (SSE2/AES)'
#18:  'CPU-Core (SSE2/AES)'
#19:  'CPU-Core (SSE2/AES)'
#20:  'CPU-Core (SSE2/AES)'
#21:  'CPU-Core (SSE2/AES)'
#22:  'CPU-Core (SSE2/AES)'
#23:  'CPU-Core (SSE2/AES)'
#24:  'CPU-Core (SSE2/AES)'
#25:  'CPU-Core (SSE2/AES)'
#26:  'CPU-Core (SSE2/AES)'
#27:  'CPU-Core (SSE2/AES)'
#28:  'CPU-Core (SSE2/AES)'
#29:  'CPU-Core (SSE2/AES)'
#30:  'CPU-Core (SSE2/AES)'
#31:  'CPU-Core (SSE2/AES)'
#32:  'CPU-Core (SSE2/AES)'
#33:  'CPU-Core (SSE2/AES)'
#34:  'CPU-Core (SSE2/AES)'
#35:  'CPU-Core (SSE2/AES)'
#36:  'CPU-Core (SSE2/AES)'
#37:  'CPU-Core (SSE2/AES)'
#38:  'CPU-Core (SSE2/AES)'
#39:  'CPU-Core (SSE2/AES)'
#40:  'CPU-Core (SSE2/AES)'
#41:  'CPU-Core (SSE2/AES)'
#42:  'CPU-Core (SSE2/AES)'
#43:  'CPU-Core (SSE2/AES)'
#44:  'CPU-Core (SSE2/AES)'
#45:  'CPU-Core (SSE2/AES)'
#46:  'CPU-Core (SSE2/AES)'
#47:  'CPU-Core (SSE2/AES)'
#48:  'CPU-Core (SSE2/AES)'

うーん。壮観かな。

PyritはGPGPUで解析できるのがウリなのですが、CPUの時もご覧の通り、SSE2とAES系の命令を使ってアクセラレーションしてくれるらしいです。

GPU版のビルド

CUDA版とOpenCL版があるのですが、今日はCUDA版をインストールします。

$ cd modules/cpyrit_cuda/
$ python build install

手元の環境では一発でうまくいったのでよかったのですが、うまく行かなかった人は、この何語かもよくわからない本家のIssueを参考に頑張ってください。コマンドが読めればきっとなんとかなる。はず。

GPU付きで実行する

以上でインストールは完了ですが、設定ファイルでCUDAをONにしないとCUDAは有効になりません

$ cat ~/.pyrit/config
default_storage = file://
limit_ncpus = 0
rpc_announce = true
rpc_announce_broadcast = false
rpc_knownclients =
rpc_server = false
use_CUDA = true
use_OpenCL = false
workunit_size = 75000

CUDAを使うために、use_CUDA = trueとしてください。

virtualenv使ってるのに、これだけ$HOME/.pyritにあるのすごい変な感じがするんですが、まぁ、置いておきましょう。

以上で有効にしたら、以前と同じコマンドを打った時にCUDAデバイスが表示されるようになるはずです:

$ pyrit list_cores
Pyrit 0.5.1 (C) 2008-2011 Lukas Lueg - 2015 John Mora
https://github.com/JPaulMora/Pyrit
This code is distributed under the GNU General Public License v3+

The following cores seem available...
#1:  'CPU-Core (SSE2/AES)'
(略)
#48:  'CPU-Core (SSE2/AES)'

The following CUDA GPUs seem aviable...
#1:  'CUDA-Device #1 'Tesla V100-PCIE-16GB''
#2:  'CUDA-Device #2 'Tesla V100-PCIE-16GB''
#3:  'CUDA-Device #3 'GeForce GTX 1080 Ti''
#4:  'CUDA-Device #4 'GeForce GTX 1080 Ti''

いぇーい。

実測する前にベンチマークをする

ここまでだいぶ長かったので、いちばん美味しい解析はまた今度にとっておくことにして、Pyrit付属の「ベンチマーク」を実行して遊んで終わりとしましょう。…美味しいものを最初に食べる派のみなさん、すいません。

$ pyrit benchmark
Pyrit 0.5.1 (C) 2008-2011 Lukas Lueg - 2015 John Mora
https://github.com/JPaulMora/Pyrit
This code is distributed under the GNU General Public License v3+

Running benchmark (134716.6 PMKs/s)... /

Computed 134716.61 PMKs/s total.
#1: 'CPU-Core (SSE2/AES)': 558.2 PMKs/s (RTT 2.8)
#2: 'CPU-Core (SSE2/AES)': 525.5 PMKs/s (RTT 3.1)
#3: 'CPU-Core (SSE2/AES)': 576.1 PMKs/s (RTT 2.8)
#4: 'CPU-Core (SSE2/AES)': 582.1 PMKs/s (RTT 2.9)
#5: 'CPU-Core (SSE2/AES)': 516.2 PMKs/s (RTT 2.9)
#6: 'CPU-Core (SSE2/AES)': 575.0 PMKs/s (RTT 2.9)
#7: 'CPU-Core (SSE2/AES)': 635.2 PMKs/s (RTT 2.8)
#8: 'CPU-Core (SSE2/AES)': 513.1 PMKs/s (RTT 2.9)
#9: 'CPU-Core (SSE2/AES)': 500.3 PMKs/s (RTT 2.8)
#10: 'CPU-Core (SSE2/AES)': 546.0 PMKs/s (RTT 2.7)
#11: 'CPU-Core (SSE2/AES)': 502.4 PMKs/s (RTT 3.1)
#12: 'CPU-Core (SSE2/AES)': 549.2 PMKs/s (RTT 3.1)
#13: 'CPU-Core (SSE2/AES)': 588.1 PMKs/s (RTT 3.0)
#14: 'CPU-Core (SSE2/AES)': 487.7 PMKs/s (RTT 2.9)
#15: 'CPU-Core (SSE2/AES)': 612.9 PMKs/s (RTT 2.9)
#16: 'CPU-Core (SSE2/AES)': 615.7 PMKs/s (RTT 2.7)
#17: 'CPU-Core (SSE2/AES)': 548.0 PMKs/s (RTT 2.9)
#18: 'CPU-Core (SSE2/AES)': 572.3 PMKs/s (RTT 2.9)
#19: 'CPU-Core (SSE2/AES)': 568.8 PMKs/s (RTT 2.9)
#20: 'CPU-Core (SSE2/AES)': 589.1 PMKs/s (RTT 2.8)
#21: 'CPU-Core (SSE2/AES)': 546.5 PMKs/s (RTT 2.9)
#22: 'CPU-Core (SSE2/AES)': 570.1 PMKs/s (RTT 2.9)
#23: 'CPU-Core (SSE2/AES)': 552.7 PMKs/s (RTT 3.1)
#24: 'CPU-Core (SSE2/AES)': 571.3 PMKs/s (RTT 3.0)
#25: 'CPU-Core (SSE2/AES)': 518.7 PMKs/s (RTT 2.8)
#26: 'CPU-Core (SSE2/AES)': 544.2 PMKs/s (RTT 2.8)
#27: 'CPU-Core (SSE2/AES)': 560.4 PMKs/s (RTT 2.8)
#28: 'CPU-Core (SSE2/AES)': 569.5 PMKs/s (RTT 2.9)
#29: 'CPU-Core (SSE2/AES)': 566.7 PMKs/s (RTT 3.0)
#30: 'CPU-Core (SSE2/AES)': 552.7 PMKs/s (RTT 2.9)
#31: 'CPU-Core (SSE2/AES)': 518.4 PMKs/s (RTT 3.0)
#32: 'CPU-Core (SSE2/AES)': 613.1 PMKs/s (RTT 3.1)
#33: 'CPU-Core (SSE2/AES)': 597.8 PMKs/s (RTT 2.6)
#34: 'CPU-Core (SSE2/AES)': 572.2 PMKs/s (RTT 3.1)
#35: 'CPU-Core (SSE2/AES)': 577.3 PMKs/s (RTT 2.9)
#36: 'CPU-Core (SSE2/AES)': 597.6 PMKs/s (RTT 3.0)
#37: 'CPU-Core (SSE2/AES)': 558.5 PMKs/s (RTT 3.0)
#38: 'CPU-Core (SSE2/AES)': 560.2 PMKs/s (RTT 3.0)
#39: 'CPU-Core (SSE2/AES)': 523.3 PMKs/s (RTT 2.8)
#40: 'CPU-Core (SSE2/AES)': 566.2 PMKs/s (RTT 3.0)
#41: 'CPU-Core (SSE2/AES)': 594.0 PMKs/s (RTT 2.8)
#42: 'CPU-Core (SSE2/AES)': 544.6 PMKs/s (RTT 3.0)
#43: 'CPU-Core (SSE2/AES)': 512.6 PMKs/s (RTT 3.0)
#44: 'CPU-Core (SSE2/AES)': 558.7 PMKs/s (RTT 3.2)
#45: 'CPU-Core (SSE2/AES)': 596.8 PMKs/s (RTT 2.9)
#46: 'CPU-Core (SSE2/AES)': 579.3 PMKs/s (RTT 2.8)
#47: 'CPU-Core (SSE2/AES)': 562.6 PMKs/s (RTT 2.8)
#48: 'CPU-Core (SSE2/AES)': 605.8 PMKs/s (RTT 3.1)
CUDA:
#1: 'CUDA-Device #1 'Tesla V100-PCIE-16GB'': 125707.5 PMKs/s (RTT 0.4)
#2: 'CUDA-Device #2 'Tesla V100-PCIE-16GB'': 118158.6 PMKs/s (RTT 0.4)
#3: 'CUDA-Device #3 'GeForce GTX 1080 Ti'': 113215.9 PMKs/s (RTT 0.4)
#4: 'CUDA-Device #4 'GeForce GTX 1080 Ti'': 97661.2 PMKs/s (RTT 0.4)

PMKs/sっていうのが、「パスワードを一秒間に何回試したか」です。Pyritは、パスワードを総当たり(ブルートフォース)でクラックします。銀行の暗証番号とかロッカーや自転車の鍵で例えると、0000から9999まで全部ためす感じです。アホな戦略を計算力で全力でごり押していくのが、Pyritスタイル。たぶん。

じっと数字を眺めていると、こんなところに気が付きます:

  • CPU48コアを全部束るとだいたい3万パスワード/secで、12万パスワード/secのTesla1台の1/4くらい

まぁCPUはかなり頑張った方なんじゃないでしょうか?「みんなで同じこと(クラック)をデータ(パスワード)だけ差し替えて計算する」のはGPUのもっとも得意とするところなので、健闘していると思います。

  • GTXとTeslaでほとんど差がない

これ結構ショックなんですが。Teslaはとってもたかいんだぞー。ただ、ひょっとすると、これは「最適化のしがいがある」と捉える事も可能かもしれません。Teslaの方が潜在的な能力があるのは確かなはずなので、ここまで差がないのは、なんか違和感があります。もう少し詳しくプロファイリングする甲斐があるというものでしょう。技術ブログってやつにはこういうのが必要なんですよ。たぶん。

無論、単純にベンチマークが実態と乖離してるだけで、実データを使うとそうでもない可能性もあります。

  • このサーバが全力を出すと、zoiのパスワード([a-z]が11文字)を総当たりクラックするのに200年くらい掛かる

まぁ200年も業務データがクラックされなければ十分なんじゃないでしょうか。誰もクラックされたデータがなんだったのか、思い出せなくなってる頃だと思います。

ただPyritも一番アホな「総当たり攻撃」だけではなく「辞書攻撃」もするので、場合によってはすぐクラックできる可能性はあります。

ああ。あと。最初の方に出てる「Computed 134716.61 PMKs/s total.」ってのがなんか変な気がするので、次までにその辺はデバッグしておきますね。

<Youtuber語法>ご静聴、ありがとう!
気に入ってくれたみんなはRSSリーダーに登録したり↓↓のソーシャルボタンとかで拡散してね</Youtuber語法>