弱いパスワードフィルタ-Bloom filter

Weak passwords

too short

予測可能個人情報:氏名、電話番号、住所、誕生日など

しかも最近はパスワード自体がこんなに弱いと危険になり、攻撃の仕方が急速に進んでいるので発見しやすくなっています.
Modern approach for attacking

Parallel computation: using GPUs

Better algorithms to generate potential passwords: better understanding, probabilistic modeling

Password file access control

/etc/passwordで、以前はほほほ:だからいかなるプレイヤーも近づくことができます;

でも最近は/etc/shadowaccessible only by superuser.

despite all protections, password file can still be leaked. 👉🏻 そのため、別の政策を取る必要がある.

password policy

user education

computer-generated password

reactive password checking

complex password policy

Unixのパスワードシステムも以前よりずっとよくなりましたが、別の政策を制定する必要があります.bad password設定をいっそ阻止すべきです.
bad passwordは判別を解析することもできる.Entropyの概念を導入すればよい.
Entropy ✨

情報−理論エントロピーは熱力学におけるエントロピーとは異なる.

Shannon entropy is the most well-known, but there are others.

最小エントロピーを使用する必要があります!:more appropriate for passwords.

Min-Entropy
:任意のxについて、特定の暗号xからの確率で最大のP[X=x]値.
最大確率が最小エントロピーであるのは,確率値にlogと−をとるためである.
パスワードポリシーのエントロピーが大きいほど良いことを知っていますか>上記の例では、Xは均一に分布している.このとき,夏年エントロピーと同様の結果が現れる.でも!!!
次の例に示すように、unifion分布がない場合は、異なる値が表示されます.エントロピーは小さい場合をよく捉えている.夏のエントロピーはn/2であり,最小エントロピーは1であり,悪い状況をうまく克服した.
要するに、badspasswordを様々な方法で事前に取得し、ユーザーがこのpasswordを設定することを阻止すればよい...問題があります.
Bloom filter - password checking

problems with the dictionary of 'bad' passwords
いいえ.🥺 結局、悪いパスワードも保存する必要があるという欠点があります.
space: large space needed if it contains many passwords
time: if the dictionary is large, searching could take time

Bloomfilterはこの問題を解決しました!🙂
Bloom filter..
有限セットDのデータ構造を格納する.

For each x, you can ask B if x is in d or not.
ブルームフィルタが「xはD内にない」と答えたら、xは本当にありません.
逆に、「xはDの中にある」と答えたら、xはあるかもしれないし、ないかもしれない.😇

誤り確率を制御することができます.(control the size of B)

データセットDを記憶するには、パスワード最大長lビット*パスワード個数d=|D|(Dの大きさ)の記憶空間が必要となる.

「ファイルルームフィルタ」を使用するにはN-bit(名前変更)のみ

どうすればいいですか.

H(x)=yの場合、yビットは1に設定される.あとでフィルタリングするときにxが入ってきたらyが1かどうかを確認するので使えません
Bloom filterのエラー率
kはハッシュ関数の個数,Nはブルームフィルタの大きさ,dは我々が格納したデータの個数である.
Dにはありませんが、フィルタでは1の確率に設定します.N,k,dを適切に設定して誤り率を低減することができる.d=1,000,000の場合、ターゲットエラー確率p=0.01k=6.
N/d=9.6だからこそ、N = 9.6 * 1,000,000でいい!ヒューヒューいう💕
9.6 * 10^6 bis = 1.2MB. ブルームフィルタのサイズを1.2 MBに設定するだけです.
👉🏻 すべてのデータセットDを格納するのに必要なサイズ8 MBよりもはるかに小さい.🤗
整理するとBloomfilter分析で...

YESが出現する確率=xはDに属さず,BはすべてのH i(x)に対して1に設定される確率である.

Pr[for all i, H_(x) is already set to 1]
= Pr[for all i, H_i(x) = H_j(x_l) for some j and l]
= Pr[for all i, it is not that for all j and l, H_i(x) ≠ H_j(x_l)]
= (1 - (1-1/N)^d*k)^k

H iは独立ランダム関数と仮定した.

bloom filterはbad passwordのフィルタリングに必要なストレージのコストを削減🙂