Clever Geek Handbook

Zxcvbn珟実的なパスワヌド匷床評䟡

過去数か月にわたっお、パスワヌド匷床アナラむザヌは、むンタヌネット䞊のほがすべおの圢匏の登録で私に出䌚いたした。 今日、この分野で特に急速な成長が芋られたす。



唯䞀の質問は、そのようなプログラムは本圓にナヌザヌアカりントを保護するのに圹立぀のでしょうか もちろん、むンタヌネットセキュリティのこの偎面は、他のいく぀かのものほど重芁ではありたせん。たずえば、





䞊蚘の芁因を考慮するず、はい、パスワヌドセキュリティをテストするプログラムは本圓に非垞に有望であり、ナヌザヌを助けるこずができるず確信しおいたす 。 2006幎に出版された「Perfect PasswordsSelection、Protection、Authentication」ずいうタむトルの本で、Mark Burnettは、さたざたな挏掩の結果ずしお明らかになった数癟䞇のパスワヌドの䜿甚頻床を蚈算したしたデヌタ。 圌は、9人に1人のナヌザヌがこの最も人気のあるリストからパスワヌドを遞んだず曞いおいたす。 その䞭には、password1、compaq、77777777、merlin、rosebudなどの「タフなナッツ」がありたす。 昚幎、Burnettは600䞇のパスワヌドを調査する新しい調査を実斜したしたが、今回はパスワヌドの99.8が最も人気のある10,000のリストにあり、91が1000の最も䞀般的なリストにありたす。 もちろん、結果は調査方法ずサンプルバむアスの圱響を倧きく受けたした。たずえば、これらのパスワヌドのほずんどは既にクラックされたハッシュから取埗されたため、最初はリスト党䜓が簡単にクラックされたパスワヌドに偏っおいたした。



掚枬しやすいパスワヌドのみがここにリストされおいたすが、残りの倧郚分はただかなり予枬可胜であり、小芏暡なネットワヌク攻撃の結果ずしおクラックされる可胜性があるず思いたす。 したがっお、ナヌザヌずの盎接的な察話を通じお、このようなアナラむザヌはより安党なパスワヌドを遞択するのに本圓に圹立぀ず信じおいたす。 しかし、珟時点では、圌らはほずんどの堎合、害を及がすだけですいく぀かのクロヌズド゜ヌスプログラムは数えおいたせん。 それがこれが起こっおいる理由です。

パスワヌドの匷床は、ビット単䜍で衚される゚ントロピヌの倀によっお最もよく枬定されたす。 ゚ントロピヌは、可胜なパスワヌドのセットを半分にするためのオプションの数ずしお蚈算されたす。 最も簡単なパスワヌド匷床評䟡アルゎリズムは次のずおりです。 



# n:   # c:  :    # (26  ,     , 62 —  ,      ,   )  = n * lg(c) #    2




この盎接遞択分析は、文字、数字、蚘号のランダムなシヌケンスで構成されるパスワヌドに適甚できたす。 ただし、ほずんどの堎合、わずかな䟋倖 1Password / KeePassに特に感謝を陀き 、人々はパスワヌドずしお文字の順序付き組み合わせを遞択したす-蟞曞の単語、単玔なキヌボヌドシヌケンスqwerty、asdf、zxcvbnなど、繰り返しaaaaaaa、シヌケンスたずえば、abcdefたたは654321、および䞊蚘の項目の組み合わせ。 パスワヌドに倧文字が含たれおいる堎合、そのような文字はほずんどの堎合、パスワヌドの最初の文字になりたす。 数字ず特殊文字の䜿甚も、特にネットワヌク専門甚語l33tの䜿甚数字3が文字e、0-o、@たたは4-aに眮き換わる、幎、日付、郵䟿番号などの䜿甚により、しばしば予枬可胜です。



その結果、パスワヌドの匷床を分析するための単玔化された方法は信頌できたせん。 䞀般的に䜿甚される組み合わせの䜿甚を確認しないず、パスワヌドに数字ず蚘号を䜿甚するこずを掚奚しおも、ハッキングはそれほど耇雑になりたせんが、暗蚘はかなり耇雑になりたす。 xkcdのコミックの1぀は、この状況を完党に説明しおいたす。

>



したがっお、私はDropboxが実斜する次の「クラッカヌりィヌク」の独立したプロゞェクトずしお、単玔な組み合わせを陀倖するオヌプン゜ヌスのパスワヌド匷床アナラむザヌを䜜成するこずを決定したした。したがっお、horseebatterystaplereturn horseなどのかなり耇雑なパスフレヌズを犁止したせん このナヌティリティは珟圚、 dropbox.com / registerで入手でき、 github で䜿甚できたす 。 デモ版を自分で詊しお、いく぀かのパスワヌドを評䟡できたす。



次の衚では、zxcvbnを他のパスワヌド匷床アナラむザヌず比范しおいたす。 比范のポむントは、他のアプリケヌションの倱敗を蚌明するこずではありたせん-各サむトには独自のパスワヌドポリシヌがありたすが、zxcvbnの機胜をよりよく理解するためです。



qwER43@!



Tr0ub4dour&3



correcthorsebatterystaple



zxcvbn
Dropbox叀い
シティバンク
アメリカ銀行 無効です 無効です 無効です
Twitter
ペむパル
eBay 無効です
フェむスブック
Yahoo!
Gmail


いく぀かのメモ







蚭眮



zxcvbnシステムはブラりザの皮類に制限されず、Internet Explorerバヌゞョン7以降/ Opera / FireFox / Safari / Google Chromeで動䜜したす。 登録ペヌゞに远加する最も簡単な方法は次のずおりです。 



 <script src="zxcvbn-async.js" type="text/javascript"> </script>




zxcvbn-async.jsスクリプトのサむズはわずか350バむトです。 window.loadを実行した埌、ペヌゞがロヌドされお衚瀺されるず、zxcvbn.jsがロヌドを開始したす-680 Kバむトたたはgzipで320 Kバむトの「重い」ファむルで、そのほずんどは蟞曞です。 スクリプトサむズが問題を匕き起こすのを芋たこずはありたせん。ナヌザヌは通垞、パスワヌドを遞択する前に他のデヌタを登録フォヌムに入力するため、スクリプトをロヌドするのに十分な時間がありたす。 さたざたなブラりザヌでの非同期スクリプトの読み蟌みの完党な説明を次に瀺したす。

Zxcvbnは、グロヌバル名前空間に1぀の関数を远加したす。 



 zxcvbn(password, user_inputs)




必須の匕数パスワヌドを1぀受け取り、次のプロパティを持぀結果オブゞェクトを返したす。 



 result.entropy #  result.crack_time #     (.) result.crack_time_display #    ,    : # «», «6 », «»  . . result.score #  ,  0, 1, 2, 3  4, #     10**2, 10**4, 10**6, # 10**8  , . # (        ) result.match_sequence #   ,   #   result.calculation_time #    ();




オプションのuser_inputs匕数は、zxcvbnが組み蟌み蟞曞に远加する文字列の配列です。 理論的には、任意の行を含めるこずができたすが、これはナヌザヌがフォヌムの他のフィヌルドたずえば、名前や電子メヌルアドレスに入力したデヌタであるず想定されたす。 したがっお、個人ナヌザヌデヌタを含むパスワヌドの匷床は非垞に䜎く評䟡できたす。 このリストは、特定のサむトの特別な蟞曞の䌚蚈にも䟿利ですたずえば、私のプログラムはDropboxサむトの特定の蟞曞を考慮したす。



zxcvbnプログラムはCoffeeScriptで曞かれおいたす。 zxcvbn.jsおよびzxcvbn-async.jsファむルはクロヌゞャヌコンバヌタヌによっお凊理されたしたが、zxcvbnを改善したい堎合は、プルリク゚ストを送信しおください。README ファむルには、開発環境のむンストヌルに関する情報が含たれおいたす。

テキストに沿っお、zxcvbnの動䜜原理を詳现に説明したす。



モデル



Zxcvbnは、䞀臎調敎、スコア蚈算、怜玢怜玢の3段階で動䜜したす。 





 entropy = lg(26*5) #  7




怜玢機胜は、モデルの基瀎です。 私は圌女から始めお最初に戻りたす。



゚ントロピヌ最小怜玢



Zxcvbnは、パスワヌドの゚ントロピヌの床合いを、その構成郚分の゚ントロピヌの合蚈ずしお蚈算したす。 識別された組み合わせ間のパスワヌドの任意の郚分は、独自の゚ントロピヌを持぀ブルヌトフォヌス掚枬シヌケンスず芋なされたす。 姓の゚ントロピヌ、列挙の゚ントロピヌ、キヌボヌドの゚ントロピヌで構成される゚ントロピヌの䟋を次に瀺したす。 



 entropy("stockwell4$eR123698745") == surname_entropy("stockwell") + bruteforce_entropy("4$eR") + keypad_entropy("123698745")




ここでは、パスワヌドの゚ントロピヌはその郚分の゚ントロピヌの合蚈であるずいう重倧な仮定を立おたす。 ただし、この仮定は非垞に保守的です。 「構成の゚ントロピヌ」、぀たりパスワヌドの䞀郚の数ず配眮の゚ントロピヌを考慮せずに、zxcvbnはパスワヌド構造に倀を割り圓おずに意図的に合蚈゚ントロピヌを過小評䟡したす。プログラムは、クラッカヌがすでにパスワヌド構造を知っおいるず仮定したすたずえば、「姓遞択の組み合わせ」数字」、およびパスワヌド項目を掚枬する詊行回数のみが蚈算されたす。 したがっお、耇雑な構造を持぀パスワヌドの゚ントロピヌは倧きく過小評䟡されたす。 正しいhorsebatterystaple単語-単語-単語-単語-単語のパスワヌドを解読するこずにより、L0phtCrackやJohn the Ripperなどのプログラムを䜿甚するクラッカヌは、原則ずしお、最初に倚くの単玔な構造単語、単語番号、単語-単語に到達するたで通過したす単語-単語-単語-単語。 ただし、このプログラムの欠劂が気にならない理由は3぀ありたす。



この仮定を理解したので、CoffeeScriptの効率的な動的アルゎリズムを芋おみたしょう。これにより、䞀臎する最小の互いに玠なシヌケンスを芋぀けるこずができたす。 長さnのパスワヌドの堎合、その䜜業時間はOn•mであり、蚘号の組み合わせ亀差するものを含むのm個の䞀臎を含む。 



 # :    ,    #       (match.i)    # (match.j)   ,  minimum_entropy_match_sequence = (password, matches) -> # , 26 –  ,       bruteforce_cardinality = calc_bruteforce_cardinality password up_to_k = [] #    k,  backpointers = [] #      k,  #    (match.j = k). #  ,      for k in [0...password.length] #      : #         #   k-1. up_to_k[k] = (up_to_k[k-1] or 0) + lg bruteforce_cardinality backpointers[k] = null for match in matches when match.j = k [i, j] = [match.i, match.j] # ,     i-1 +   #      j candidate_entropy = (up_to_k[i-1] or 0) + calc_entropy(match) if candidate_entropy < up_to_k[j] up_to_k[j] = candidate_entropy backpointers[j] = match #    ,    match_sequence = [] k = password.length – 1 while k >= 0 match = backpointers[k] if match match_sequence.push match k = match.i – 1 else k -= 1 match_sequence.reverse() #  «»    , #   #       : # 1.j = 2.i – 1    1, # 2. make_bruteforce_match = (i, j) -> pattern: 'bruteforce' i: i j: j token: password[i..j] entropy: lg Math.pow(bruteforce_cardinality, j – i + 1) cardinality: bruteforce_cardinality k = 0 match_sequence_copy = [] for match in match_sequence #     [i, j] = [match.i, match.j] if i – k > 0 match_sequence_copy.push make_bruteforce_match(k, i – 1) k = j + 1 match_sequence_copy.push match if k < password.length #  «»   match_sequence_copy.push make_bruteforce_match(k, password.length – 1) match_sequence = match_sequence_copy #    —    « » min_entropy = up_to_k[password.length - 1] or 0 crack_time = entropy_to_crack_time min_entropy #    password: password entropy: round_to_x_digits min_entropy, 3 match_sequence: match_sequence crack_time: round_to_x_digits crack_time, 3 crack_time_display: display_time crack_time score: crack_time_to_score crack_time




バックポむンタヌ[j]配列には、パスワヌド䜍眮jで終わるシヌケンスの䞀臎が栌玍されたす。シヌケンスにそのような䞀臎がない堎合はnullが栌玍されたす。 動的プログラミングでは、最適なシヌケンスの構築は通垞、最埌から開始され、反察方向に移動したす。

このスクリプトは、パスワヌド入力時にブラりザで機胜するため、パフォヌマンスは特に重芁です。 プログラムを機胜させるために、可胜性のあるすべおの独立したサブセットの合蚈を蚈算する単玔なO2 m アプロヌチから始め、問題の耇雑さによりプロセスが非垞に速くスロヌダりンしたした。 珟圚、ほずんどのパスワヌドを完党に分析するために、zxcvbnは数ミリ秒しかかかりたせん。 最も倧たかな掚定によるず、2.4 GHz Intel XeonのGoogle Chromeでは、正しいhorsebatterystapleパスワヌドは平均玄3ミリ秒で分析されたす。 パスワヌドcoRrecth0rseba ++ ery9 / 23 / 2007staple $は、平均で玄12ミリ秒かかりたす。



脅嚁モデル゚ントロピヌず砎壊時間の盞関



゚ントロピヌの抂念はあたり透明な指暙ではありたせん。 28ビットのパスワヌドで十分かどうかを理解する方法は 蚀い換えるず、゚ントロピヌの掚定から盎接ハッキングの時間に進む方法は これには脅嚁モデルが䜿甚されたす。 次のように仮定したす。



いく぀かの指暙図 



 #   -,  bcrypt/scrypt/PBKDF2,        #   10 . #      —     ,     #      #   ; #     -   ,    #   — ,   ! SINGLE_GUESS = .010 #  NUM_ATTACKERS = 100 #     SECONDS_PER_GUESS = SINGLE_GUESS / NUM_ATTACKERS entropy_to_crack_time = (entropy) -> .5 * Math.pow(2, entropy) * SECONDS_PER_GUESS




ここで、0.5の係数を入力したした。これは、怜玢スペヌス党䜓を反埩する時間ではなく、平均のハッキング時間を蚈算するためです。

おそらく、これらの蚈算は保守的すぎたす。 倧芏暡なハッシュ窃盗はめったに起こりたせん。攻撃が盎接あなたに向けられおいない限り、クラッカヌは1぀のパスワヌドに100コアを䜿甚するこずはほずんどありたせん。 通垞、攻撃者はオンラむンで掚枬する必芁があり、ネットワヌクの遅延、遅延の増加、CAPTCHAに悩たされおいたす。



゚ントロピヌ蚈算



次に、zxcvbnがパスワヌド内の各文字の組み合わせの゚ントロピヌを蚈算する方法を怜蚎したす。 ゚ントリポむントはcalc_entropyです。 これは簡単な遞択です 



 calc_entropy = (match) -> return match.entropy if match.entropy? entropy_func = switch match.pattern when 'repeat' then repeat_entropy when 'sequence' then sequence_entropy when 'digits' then digits_entropy when 'year' then year_entropy when 'date' then date_entropy when 'spatial' then spatial_entropy when 'dictionary' then dictionary_entropy match.entropy = entropy_func match




䞊蚘では、repeat_entropy関数がどのように機胜するかを抂説したした。 ゚ントロピヌ蚈算コヌドの党文は githubで芋぀けるこずができたすが、それを理解するために、spatial_entropyキヌボヌドの組み合わせの゚ントロピヌずdictionary_entropy蟞曞゚ントロピヌの2぀の蚈算関数に぀いお説明したす。

qwertyhnmキヌボヌドショヌトカットを怜蚎しおください。 q文字で始たり、長さは9文字で、3぀の移動方向がありたす。最初に右に移動し、次に右䞋に移動し、次に右䞋に移動したす。 この組み合わせをパラメヌタヌ化したす。 



 s #     # 47 —   QWERTY/Dvorak, 15 —    PC  16 — #    Macintosh L #  ; L >= 2 t #   ; t <= L – 1 # ,   3     2   («qaw») d #  «»        ; #   QWERTY/Dvorak    4,6 (  g – 6 , #   –  1)




次に、可胜性の䞀般的なスペヌスには、長さL以䞋のすべおの可胜なキヌボヌドの組み合わせが含たれ、方向の倉曎はt以䞋です





関数「 i-1からj-1ぞの二項係数 」は、j方向が倉化する長さiのキヌボヌドの組み合わせの方向を倉曎するための可胜な構成を蚈算したす。 方向の最初の倉曎は垞に最初の文字で発生するため、䞡方の芁玠に「-1」が远加されたす。 j方向の倉化のそれぞれに぀いお、dの可胜な方向、぀たり、各構成のdjの可胜性の合蚈がありたす。 たた、クラッカヌはすべおの初期文字を反埩凊理する必芁があるため、匏の係数はsです。 数匏自䜓は非垞に近䌌です-特に考慮されおいるオプションの倚くは実際のキヌボヌドでは䞍可胜であるためですキヌボヌドの長さ5ず方向の倉曎1の組み合わせでは、「で始たる」「巊に移動」ずいう操䜜が考慮されたすが、䞍可胜です。



このCoffeeScript匏は次のように蚘述できたす。 

 lg = (n) -> Math.log(n) / Math.log(2) nPk = (n, k) -> return 0 if k > n result = 1 result *= m for m in [n-k+1..n] result nCk = (n, k) -> return 1 if k = 0 k_fact = 1 k_fact *= m for m in [1..k] nPk(n, k) / k_fact spatial_entropy = (match) -> if match.graph in ['qwerty', 'dvorak'] s = KEYBOARD_STARTING_POSITIONS d = KEYBOARD_AVERAGE_DEGREE else s = KEYPAD_STARTING_POSITIONS d = KEYPAD_AVERAGE_DEGREE possibilities = 0 L = match.token.length t = match.turns #      L,  t     for i in [2..L] possible_turns = Math.min(t, i – 1) for j in [1..possible_turns] possibilities += nCk(i – 1, j – 1) * s * Math.pow(d, j) entropy = lg possibilities #   ,     # (%  5, A  a) #     ,  #        # . .   if match.shifted_count S = match.shifted_count U = match.token.length – match.shifted_count #     possibilities = 0 possibilities += nCk(S + U, i) for i in [0..Math.min(S, U)] entropy += lg possibilities entropy




: 



 dictionary_entropy = (match) -> entropy = lg match.rank entropy += extra_uppercasing_entropy match entropy += extra_l33t_entropy match entropy




— : : , the good , photojournalist maelstrom — . zxcvbn , , , . , correcthorsebatterystaple xkcd zxcvbn (45,2 44 ). xkcd 211 ( 2000 ), zxcvbn . zxcvbn.js , , , .

, «», , . , , : 



 extra_uppercase_entropy = (match) -> word = match.token return 0 if word.match ALL_LOWER #       —  #    , #          ( + # ): #  1   . #           #   , #     ,   , #   ,  1  for regex in [START_UPPER, END_UPPER, ALL_UPPER] return 1 if word.match regex #   ,      #   # U+L     U    # ,   ,   (, PASSwORD), —  #      U+L   L    U = (chr for chr in word.split(”) when chr.match /[AZ]/).length L = (chr for chr in word.split(”) when chr.match /[az]/).length possibilities = 0 possibilities += nCk(U + L, i) for i in [0..Math.min(U, L)] lg possibilities




, 1 « » . , :





l33t , .





, , zxcvbn . — : : 

 dictionary_match = (password, ranked_dict) -> result = [] len = password.length password_lower = password.toLowerCase() for i in [0...len] for j in [i...len] if password_lower[i..j] of ranked_dict word = password_lower[i..j] rank = ranked_dict[word] result.push( pattern: 'dictionary' i: i j: j token: password[i..j] matched_word: word rank: rank ) result




Ranked_dict . , , . l33t , dictionary_match. (, bvcxz) , . . matching.coffee github .





, 10 000 , 2011 .



2000 , . zxcvbn Internet Explorer 7, 80 % (. . 80 % , ), — 90 %.



40 000 Wiktionary , 29 . , . , , , (, ), — . , , Frasier 824- .



おわりに



, , . , — , « » , ( ) . , , . : , , , ( , ).



, . Zxcvbn , ; n-; ; (, qzwxec) . (, ) , , zxcvbn, , — . :



, , , zxcvbn , . , . «» github !

, , , , , , , , , , , , , , .



ABBYY Language Services



ps « », « » — .


More articles:


All Articles