🔑

パスワード管理アルゴリズム AiKotoba を作ってみた

2021/12/17に公開

パスワード

SHA-256

PBKDF2

tech

概要

今の時代、パスワードを使わずに生きていくことは不可能と言っていいほど普及している。パスワードはその性質上、自分だけが知っている情報であり、他人に推測されないものでなければならない。そして、パスワードの使いまわしは避けなければならないし、短いパスワードだと突破されやすくなる。

...そんなの全部覚えるのは無理だ！！！！！！
というわけでそれらの問題を解決するアルゴリズムを作ってみた。

名付けて AiKotoba である。

問題を掘り下げる

パスワードに求められることを総務省のページから引っ張ってくると、

名前などの個人情報からは推測できないこと
英単語などをそのまま使用していないこと
アルファベットと数字が混在していること
適切な長さの文字列であること
類推しやすい並び方やその安易な組み合わせにしないこと

とある。また同ページの別章にパスワードを使いまわさないと書かれている。

パスワードマネージャーを使えば解決しそうだが、ツールを使うとマスターパスワード、 google アカウントなどを使うとアカウントのログインパスワードが、安全の担保になる(最近は二要素認証とかが実装されていたりするが、そこには触れないで欲しい。ご都合主義)。マスターパスワードを知っていることが安全であることを保障しているのは脆い。

また、上で二要素認証のことに触れたが(自分から触れるんかーい)、主体認証には一般に3つのカテゴリーがある(マスタリングTCP/IP 情報セキュリティ編 p68 から引用)。

主体の知識による認証
主体の所持するものによる認証
主体の身体的な特性による認証

上記で述べているパスワードは "主体の知識による認証" であり、二要素認証とは3つのカテゴリーのうち2つを使った認証である。例えば、パスワード(主体の知識による認証)と機器を使ったワンタイムパスワード(主体の所持するものによる認証)である。

今回作成する AiKotoba は二要素を使ってパスワードを作成するアルゴリズムである。

AiKotoba アルゴリズム

AiKotoba で使う認証の要素は "主体の知識による認証" と "主体の所持するものによる認証" の二つである。前者はマスターパスワードである phrase で、後者はランダムに作成された 256bit の列 key である。その二つを元にパスワードを作成する。

変数の定義

$key: 256bit の乱数列を 16 進数で表記した文字列
$phrase: マスターパスワード。これは覚えておく
$name: 管理するときの名前("twitter", "account@twitter" etc...)
$seed: パスワード生成の初期値(ばれても、まぁいいっか程度のもの)
$iteration: パスワードハッシュする際のイテレーション回数(デフォルト 65536 回)
$base: パスワードに使える文字の種類(10, 26, 36, 52, 62, 72)
$length: パスワードの長さ(1 から 40 までの整数値)

base について

この base はパスワードに使える文字の種類につながってくる。今回用意したのは 10, 26, 36, 52, 62, 72 の 6 パターン。

10: 0-9
26: a-z
36: a-z0-9
52: A-Za-z
62: A-Za-z0-9
72: A-HJ-NP-Za-km-z1-9#$%&()+-<=>?_^

上記のように指定する。対応順は左から 0, ..., n-1 とする。base72 は独自に作成したもので、似たような文字(I, O, l, 0)を省いた(base58を参考にした)うえで記号を16文字追加している。

核となるアルゴリズム

ここでは AiKotoba の核となっているアルゴリズムを紹介する。

256 bit の導出鍵を作成する
導出鍵からパスワードを生成する
パスワードのチェックサムを計算する

256 bit の導出鍵を作成する

PBKDF2 を用いる。PHP では hash_pbkdf2 という関数が用意されている。

$dk = hash_pbkdf2('sha256', $key . $phrase, $name . $seed, $iteration, 256);

導出鍵からパスワードを生成する

$dk を整数値とみて base 進数に変換し、下位の桁から順に length までを出力。

例: base = 36, length = 3, dk = 123456789 のとき
123456789 を 36 進数に変換すると 21I3V9 になるので、下位の桁から 3 文字 9V3 が出力されるパスワードである。

パスワードのチェックサムを計算する

自分で入力した値(key, phrase, name, seed)があっているかどうかを確認するためにチェックサムを計算する。これについては導入をするかどうか悩んだが、複数の phrase を使い分けたり、seed の作成も隠ぺいしたときにローカルで簡易に確認できる方法があってもいいと思い入れた(その代わり攻撃がしやすくなるが)。チェックサムは下記で求まる 16bit とする。

$checksum = hash_pbkdf2('sha256', $password, $seed, $iteration, 16);

key の管理

256bit の乱数列を紛失してしまうと事実上同じパスワードを作成することができない。なのでその乱数列はなくしてもいいように厳重に管理しておくべきである。ただ、デジタルのデータだといつ飛んでしまうかわからないのでアナログな方法で保管しておくべきである。

256bit をそのまま紙に書き写すのはナンセンスである。そこで目を付けたのがビットコインなどで同様の目的で使われている BIP39 である。
BIP39 とは2048単語を準備して 0 から 2047 を対応させたもの、つまり単語と 11bit の値が一対一に対応している。単語はいろんな言語が用意されていて、もちろん日本語もある。少しややこしいが 1 行目の "あいこくしん" が 0 を、2048 行目の "われる" が 2047 を指している。

実際のプログラム

上記を PHP でプログラミングしてみた。
https://github.com/firedial/AiKotoba

実際に使ってみた

初期設定

鍵の生成。

$ php create_key.php
$ cat .key
8f6d3a485a7deda9c31791079ef5dd4c582bcc144ddc16d8027b82c4eb3a5bc7

※この key は本来晒してはいけない情報であることに注意

バックアップのワードを出力。

$ php key_backup.php
たんか
しゃちょう
だんろ
にんぷ
ほっさ
ふっかつ
いっせい
ゆでる
いきなり
りきせつ
せのび
つうわ
そんざい
みほん
こっか
ねんぴ
うなずく
はいご
でこぼこ
あらわす
こくさい
ていこく
すける
わかれる

※この情報も晒してはいけない

バックアップを取って鍵を削除。

$ php key_backup.php > .words
$ rm .key

.key がない状態だと .words ファイルから復元を試みる。

$ php key_backup.php
$ cat .key
8f6d3a485a7deda9c31791079ef5dd4c582bcc144ddc16d8027b82c4eb3a5bc7

使い方

お待ちかね。本題の使い方。

$ php main.php 
name: twitter
phrase: 
seed: 
password: V)C%^3%A4=g6xJJ>
checksum: e617

phrase, seed は見えないように設定してある(それぞれ "phrase", "seed" を入力)。これで twitter のパスワードを "V)C%^3%A4=g6xJJ>" に設定すればよい。

記号が使えない場合は base を変える必要がある。base に 62 を指定することによって英数字のみで構成されたものが出力される。

$ php main.php -b 62
name: twitter
phrase: 
seed: 
password: IPM6s2LPVt7FL4yo
checksum: 2e8d

16 文字以外のパスワードが欲しい場合は長さを指定する。

$ php main.php -l 30
name: twitter
phrase: 
seed: 
password: V)C%^3%A4=g6xJJ>-56u=)?un4)Pne
checksum: 9a55

セキュリティを強化するためにイテレーション回数も増やせる。

$ php main.php -i 100000
name: twitter
phrase: 
seed: 
password: PPw1RYystCV%P%>M
checksum: 5a4f

それらの設定を全て指定することもできる。

$ php main.php -b 26 -l 40 -i 256
name: twitter
phrase: 
seed: 
password: gcfxpkysdzxttgqonsszjtwcszzzlonmapraqktd
checksum: 60b5

考察

phrase を複数作ることによって用途別に管理できる

phrase は一つである必要はない。phraseA は重要なアカウント用なので長くして、phraseB は捨て垢用なので適当でいい、とかの使い分けができる。

phrase から別の phrase を作ることができる

上記の応用パターン。phrase から name と seed を決めて新たに phrase を作ることができる。つまり木構造で管理できる。この際、新しく作った phrase は覚える前提である。覚えずに毎回作っていたら元の phrase を最初から使っておけばいい。上記と違う点は、忘れたときに元の phrase さえ覚えていたら思い出すことができる。

seed の作成方法も隠ぺいすることによってより安全になる(?)

基本的にアルゴリズムを隠ぺいすることによる安全性の担保はよくないとされている。なので、この方法は気休め程度であるが、一個人の作成アルゴリズムを解読しようとするのはよっぽど物好きな人に限られるので、しておいてもいいかもしれない。

key を複数作ることによって用途別に管理できる(?)

phrase と同じように key も複数作って用途別で管理できるのでは？と思うかもしれない。実際そうである。ただ、実際に使う場面を考えると、複数 key を使ったところで同じ場所に管理されることになるだろう。key の目的は主体の所持するものによる認証であり、もし一つの key が漏れると同時に他の key も漏れることが想像に難くない。なので key を複数管理するメリットはあまりないと考える。

余談

名前を決めるのに少し考えた。最初は "secret_maker" で、次に思いついたのが "AiKotoba" である。合言葉をもじって言葉合にして "ことのはあい" や "ことのはあわせ" も考えた。あとは "言葉世界(ことのはせかい)" も思いついたが、某アニメが連想されるのでやめた。