count_xato.coffee 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
  1. matching = require '../lib/matching'
  2. scoring = require '../lib/scoring'
  3. fs = require 'fs'
  4. byline = require 'byline'
  5. sprintf = require('sprintf-js').sprintf
  6. check_usage = () ->
  7. usage = '''
  8. Run a frequency count on the raw 10M xato password set and keep counts over CUTOFF in
  9. descending frequency. That file can be found by googling around for:
  10. "xato 10-million-combos.txt"
  11. Passwords that both:
  12. -- fully match according to zxcvbn's date, year, repeat, sequence or keyboard matching algs
  13. -- have a higher rank than the corresponding match guess number
  14. are excluded from the final password set, since zxcvbn would score them lower through
  15. other means anyhow. in practice this rules out dates and years most often and makes room
  16. for more useful data.
  17. To use, first run from zxcvbn base dir:
  18. npm run build
  19. then change into data-scripts directory and run:
  20. coffee count_xato.coffee --nodejs xato_file.txt ../data/passwords.txt
  21. '''
  22. valid = process.argv.length == 5
  23. valid = valid and process.argv[0] == 'coffee' and process.argv[2] in ['--nodejs', '-n']
  24. valid = valid and __dirname.split('/').slice(-1)[0] == 'data-scripts'
  25. unless valid
  26. console.log usage
  27. process.exit(0)
  28. # after all passwords are counted, discard pws with counts <= COUNTS
  29. CUTOFF = 10
  30. # to save memory, after every batch of size BATCH_SIZE, go through counts and delete
  31. # long tail of entries with only one count.
  32. BATCH_SIZE = 1000000
  33. counts = {} # maps pw -> count
  34. skipped_lines = 0 # skipped lines in xato file -- lines w/o two tokens
  35. line_count = 0 # current number of lines processed
  36. normalize = (token) ->
  37. token.toLowerCase()
  38. should_include = (password, xato_rank) ->
  39. for i in [0...password.length]
  40. if password.charCodeAt(i) > 127
  41. # xato mostly contains ascii-only passwords, so in practice
  42. # this will only skip one or two top passwords over the cutoff.
  43. # were that not the case / were this used on a different data source, consider using
  44. # a unidecode-like library instead, similar to count_wikipedia / count_wiktionary
  45. console.log "SKIPPING non-ascii password=#{password}, rank=#{xato_rank}"
  46. return false
  47. matches = []
  48. for matcher in [
  49. matching.spatial_match
  50. matching.repeat_match
  51. matching.sequence_match
  52. matching.regex_match
  53. matching.date_match
  54. ]
  55. matches.push.apply matches, matcher.call(matching, password)
  56. matches = matches.filter (match) ->
  57. # only keep matches that span full password
  58. match.i == 0 and match.j == password.length - 1
  59. for match in matches
  60. if scoring.estimate_guesses(match, password) < xato_rank
  61. # filter out this entry: non-dictionary matching will assign
  62. # a lower guess estimate.
  63. return false
  64. return true
  65. prune = (counts) ->
  66. for pw, count of counts
  67. if count == 1
  68. delete counts[pw]
  69. main = (xato_filename, output_filename) ->
  70. stream = byline.createStream fs.createReadStream(xato_filename, encoding: 'utf8')
  71. stream.on 'readable', ->
  72. while null != (line = stream.read())
  73. line_count += 1
  74. if line_count % BATCH_SIZE == 0
  75. console.log 'counting tokens:', line_count
  76. prune counts
  77. tokens = line.trim().split /\s+/
  78. unless tokens.length == 2
  79. skipped_lines += 1
  80. continue
  81. [username, password] = tokens[..1]
  82. password = normalize password
  83. if password of counts
  84. counts[password] += 1
  85. else
  86. counts[password] = 1
  87. stream.on 'end', ->
  88. console.log 'skipped lines:', skipped_lines
  89. pairs = []
  90. console.log 'copying to tuples'
  91. for pw, count of counts
  92. if count > CUTOFF
  93. pairs.push [pw, count]
  94. delete counts[pw] # save memory to avoid v8 1GB limit
  95. console.log 'sorting'
  96. pairs.sort (p1, p2) ->
  97. # sort by count. higher counts go first.
  98. p2[1] - p1[1]
  99. console.log 'filtering'
  100. pairs = pairs.filter (pair, i) ->
  101. rank = i + 1
  102. [pw, count] = pair
  103. should_include pw, rank
  104. output_stream = fs.createWriteStream output_filename, encoding: 'utf8'
  105. for pair in pairs
  106. [pw, count] = pair
  107. output_stream.write sprintf("%-15s %d\n", pw, count)
  108. output_stream.end()
  109. check_usage()
  110. main process.argv[3], process.argv[4]