Adding files from bismuth

1 files changed, 165 insertions, 0 deletions

diff --git a/mkpasswd b/mkpasswd
new file mode 100755
index 0000000..3d681b0
--- /dev/null
+++ b/mkpasswd
@@ -0,0 +1,165 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+"""Generate a random, memorizable password: http://xkcd.com/936/
+
+Example run:
+
+    kragen at inexorable:~/devel/inexorable-misc$ ./mkpass.py 5 12
+    Your password is "learned damage saved residential stages".
+    That's equivalent to a 60-bit key.
+
+    That password would take 2.5e+03 CPU-years to crack
+    on my inexpensive Celeron E1200 from 2008,
+    assuming an offline attack on a MS-Cache hash,
+    which is the worst password hashing algorithm in common use,
+    slightly worse than even simple MD5.
+
+    The most common password-hashing algorithm these days is FreeBSD’s
+    iterated MD5; cracking such a hash would take 5.2e+06 CPU-years.
+
+    But a modern GPU can crack about 250 times as fast,
+    so that same iterated MD5 would fall in 2e+04 GPU-years.
+
+    That GPU costs about US$1.45 per day to run in 2011,
+    so cracking the password would cost about US$3e+09.
+
+I've started using a password generated this way in place of a 9-printable-
+ASCII-character random password, which is equally strong.  Munroe's assertion
+that these passwords are much easier to memorize is correct.  However, there is
+still a problem: because there are many fewer bits of entropy per character
+(about 1.7 instead of 6.6) there is a lot of redundancy in the password, and so
+attacks such as the ssh timing-channel attack (the Song, Wagner, and Tian
+Herbivore attack, which I learned about from Bram Cohen in the Bagdad Café in
+the wee hours one morning, years ago) and keyboard audio recording attacks have
+a much better chance of capturing enough information to make the password
+attackable.
+
+My countermeasure to the Herbivore attack, which works well with 9-character
+password but is extremely annoying with my new password, is to type the
+password with a half-second delay between characters, so that the timing
+channel does not carry much information about the actual characters used.
+Additionally, the lower length of the 9-character password inherently gives the
+Herbivore approach much less information to chew on.
+
+Other possible countermeasures include using Emacs shell-mode, which prompts
+you locally for the password when it recognizes a password prompt and then
+sends the whole password at once, and copying and pasting the password from
+somewhere else.
+
+As you'd expect, this password also takes a little while longer to type: about
+6 seconds instead of about 3 seconds.
+
+"""
+
+import random, itertools, os, sys
+
+def main(argv):
+    try:
+        nwords = int(argv[1])
+    except IndexError:
+        return usage(argv[0])
+
+    try:
+        nbits = int(argv[2])
+    except IndexError:
+        nbits = 11
+
+    filename = os.path.join(os.environ['HOME'], 'opt', 'share', 'wordlist')
+    wordlist = read_file(filename, nbits)
+    if len(wordlist) != 2**nbits:
+        sys.stderr.write("%r contains only %d words, not %d.\n" %
+                         (filename, len(wordlist), 2**nbits))
+        return 2
+
+    display_password(generate_password(nwords, wordlist), nwords, nbits)
+    return 0
+
+def usage(argv0):
+    p = sys.stderr.write
+    p("Usage: %s nwords [nbits]\n" % argv0)
+    p("Generates a password of nwords words, each with nbits bits\n")
+    p("of entropy, choosing words from the first entries in\n")
+    p("$HOME/devel/wordlist, which should be in the same format as\n")
+    p("<http://canonical.org/~kragen/sw/wordlist>, which is a text file\n")
+    p("with one word per line, preceded by its frequency, most frequent\n")
+    p("words first.\n")
+    p("\nRecommended:\n")
+    p("    %s 5 12\n" % argv0)
+    p("    %s 6\n" % argv0)
+    return 1
+
+def read_file(filename, nbits):
+    return [line.split()[1] for line in
+            itertools.islice(open(filename), 2**nbits)]
+
+def generate_password(nwords, wordlist):
+    choice = random.SystemRandom().choice
+    return ' '.join(choice(wordlist) for ii in range(nwords))
+
+def display_password(password, nwords, nbits):
+    print 'Your password is "%s".' % password
+    entropy = nwords * nbits
+    print "That's equivalent to a %d-bit key." % entropy
+    print
+
+    # My Celeron E1200
+    # (<http://ark.intel.com/products/34440/Intel-Celeron-Processor-E1200-(512K-Cache-1_60-GHz-800-MHz-FSB)>)
+    # was released on January 20, 2008.  Running it in 32-bit mode,
+    # john --test (<http://www.openwall.com/john/>) reports that it
+    # can do 7303000 MD5 operations per second, but I’m pretty sure
+    # that’s a single-core number (I don’t think John is
+    # multithreaded) on a dual-core processor.
+    t = years(entropy, 7303000 * 2)
+    print "That password would take %.2g CPU-years to crack" % t
+    print "on my inexpensive Celeron E1200 from 2008,"
+    print "assuming an offline attack on a MS-Cache hash,"
+    print "which is the worst password hashing algorithm in common use,"
+    print "slightly worse than even simple MD5."
+    print
+
+    t = years(entropy, 3539 * 2)
+    print "The most common password-hashing algorithm these days is FreeBSD’s"
+    print "iterated MD5; cracking such a hash would take %.2g CPU-years." % t
+    print
+
+    # (As it happens, my own machines use Drepper’s SHA-2-based
+    # hashing algorithm that was developed to replace the one
+    # mentioned above; I am assuming that it’s at least as slow as the
+    # MD5-crypt.)
+
+    # <https://en.bitcoin.it/wiki/Mining_hardware_comparison> says a
+    # Core 2 Duo U7600 can do 1.1 Mhash/s (of Bitcoin) at a 1.2GHz
+    # clock with one thread.  The Celeron in my machine that I
+    # benchmarked is basically a Core 2 Duo with a smaller cache, so
+    # I’m going to assume that it could probably do about 1.5Mhash/s.
+    # All common password-hashing algorithms (the ones mentioned
+    # above, the others implemented in John, and bcrypt, but not
+    # scrypt) use very little memory and, I believe, should scale on
+    # GPUs comparably to the SHA-256 used in Bitcoin.
+
+    # The same mining-hardware comparison says a Radeon 5870 card can
+    # do 393.46 Mhash/s for US$350.
+
+    print "But a modern GPU can crack about 250 times as fast,"
+    print "so that same iterated MD5 would fall in %.1g GPU-years." % (t / 250)
+    print
+
+    # Suppose we depreciate the video card by Moore’s law,
+    # i.e. halving in value every 18 months.  That's a loss of about
+    # 0.13% in value every day; at US$350, that’s about 44¢ per day,
+    # or US$160 per GPU-year.  If someone wanted your password as
+    # quickly as possible, they could distribute the cracking job
+    # across a network of millions of these cards.  The cards
+    # additionally use about 200 watts of power, which at 16¢/kWh
+    # works out to 77¢ per day.  If we assume an additional 20%
+    # overhead, that’s US$1.45/day or US$529/GPU-year.
+    cost_per_day = 1.45
+    cost_per_crack = cost_per_day * 365 * t
+    print "That GPU costs about US$%.2f per day to run in 2011," % cost_per_day
+    print "so cracking the password would cost about US$%.1g." % cost_per_crack
+
+def years(entropy, crypts_per_second):
+    return float(2**entropy) / crypts_per_second / 86400 / 365.2422
+
+if __name__ == '__main__':
+    sys.exit(main(sys.argv))