30 Jan 2009

When I played a Dungeons and Dragons campaign back in college, I thought it would be interesting to take notes and chronicled the campaign as a short story. I have shared a piece of it already, but I can't remember too many more details. It would have been a lot of work to do it all.

Well, a couple of years ago, Shamus Young put in the huge effort and did document a campaign that he ran. It is called The Twenty Sided Tale. If you enjoy tabletop games, or are interested in them, I strongly recommend reading through it. Hell, even if you want to read a great story, I recommend it.

Sprinkled in between the story's paragraphs are DM notes where Shamus gives some in-game context to the events. It provides some information about what the players know and reasoning about their decisions. The most interesting are his insights as a DM. It is really quite inspiring. Shamus knows his games.

The story is really amazing as well. He actually had two unrelated stories going that the players managed to merge together perfectly all by accident. The end was so fantastic that it gave me chills the first time I read it.

If you're still here, go click that link and start reading.

16 Jan 2009

I came across the Ultra High Security Password Generator the other day, which uses a very high quality pseudo-random number generator to generate passwords and keys. The idea is not to use the full 63 characters as a password, but rather a contiguous subset, such as the first 8 characters.

The website is served securely, so no middle man can sniff at it. If you trust the maintainer not to store the generated numbers somewhere, which he claims not to be doing, then you can use it as a nice password generation service. If you are nervous about matching password possibilities to your IP, then grab a batch through the Tor network.

In terms of brute-force attacks, each letter from hexadecimal characters is worth 4 bits, from random printable ASCII characters is worth about 6.6 bits, and alpha-numeric is worth about 6 bits.

If you go with the set of printable ASCII characters, 6 to 8 characters (39 to 52 bits) should be good enough for an account password, where an attacker must guess through an attempt-limiting authentication system. 8 to 12 characters (53 to 79 bits) should be plenty for a passphrase used as an encryption key, where an attacker can brute force passphrase attempts at his leisure.

I wouldn't use this website for any serious encryption, though. If he is logging generated passwords, he will have a nice short list of possible passphrases to try against your encryption. So don't use it for your GPG passphrase. Generate those locally.

This is where the purpose of my post comes in! He describes the pseudo-random number generator he uses to generate the random numbers at the top of the page. It's the AES block cipher in cipher-block chaining (CBC) mode encrypting a 128-bit counter. A picture (well, diagram) is worth a thousand words,

Note that the diagram is actually being explicit about CBC mode, so the AES cipher in the diagram is in electronic codebook (ECB) mode. I missed this myself when initially interpreting the diagram and writing my implementation. Here is the same diagram with the AES cipher already in CBC mode,

I don't know if he designed this himself or not. I implemented it in C to study it a bit. You can grab it here with git (or follow the link and get a snapshot),

git clone http://git.nullprogram.com/aesrng.git

To build it, you will need libgcrypt installed (with headers).

Here is about 100 megabytes analyzed with ent, a pseudo-random number sequence test program.

Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 100000000 byte file by 0 percent.

Chi square distribution for 100000000 samples is 275.58, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.5095 (127.5 = random).
Monte Carlo value for Pi is 3.141182766 (error 0.01 percent).
Serial correlation coefficient is 0.000005 (totally uncorrelated = 0.0).

Wow! These results are great! This is exactly what you would see if you ran 100 megabytes of /dev/random, a true random number generator, through ent. It is also pretty fast, generating that 100 megabytes on my laptop in about 7 seconds. That's much faster than Linux's /dev/urandom (over a minute here), whose ent results aren't quite as good, either.

Note: Before you go using this somewhere important you should make sure this PRNG has been peer reviewed and carefully studied by professionals with cryptanalysis. It may have fundamentals flaws. I only found this on a website somewhere!

Still, that's a pretty damn cool pseudo-random number generator.

The generator is only useful if you want to generate more than 512 bits worth of numbers, because it takes 512 bits of randomly generated numbers to initialize the generator. If you want to generate a single password if the same strength, give this a shot,

head -c 50 /dev/random | tr -cd "A-Za-z0-9@#\!\$%^&*()_+=-~;,.<>/[]{}|?:'\\\`" && echo

It uses a true random number generator and selects from 94 printable ASCII characters (space not included).

04 Jan 2009

Try it out right now if you don't feel like reading: my fantasy name generator. I need your help designing some name patterns.

Whether choosing a name for my character in a fantasy game or populating a world which I pretend to myself that I will one day DM, I have always gone to the RinkWorks Fantasy Name Generator. The author of this tool, Samuel Stoddard, gives some history on how he came to design and develop it.

It works by using pattern to select sets of letters to put together into a name. There is a thorough, long description on the website. Unfortunately, he didn't share his source code and so we can see how he did it.

Therefore, I used his description to duplicate his generator.

You can grab a copy here with git,

git clone http://git.nullprogram.com/fantasyname.git

It includes a command line interface as well as a web interface, which I am running and linked to at the beginning of this post for you to use. The code is available under the same license as Perl itself.

I used Perl and the Parse::RecDescent parser generator. Thanks to this module, it essentially comes down to about 40 lines of code. The name pattern is executed, just like a computer program, to generate a name. Here is the BNF grammar I came up with,

LITERAL ::= /[^|()<>]+/

TEMPLATE ::= /[-svVcBCimMDd']/ 

literal_set ::= LITERAL | group

template_set ::= TEMPLATE | group

literal_exp ::= literal_set literal_exp | literal_set

template_exp ::= template_set template_exp | template_set

literal_list ::= literal_exp "|" literal_list | literal_exp "|" | literal_exp

template_list ::= template_exp "|" template_list | template_exp "|" | template_exp

group ::= "<" template_list ">" | "(" literal_list ")"

name ::= template_list | group

The program is just that, decorated with some bits of Perl. Since I came up with it, I have found that it is slightly different than Mr. Stoddard's generator, in that his allows empty sets anywhere. Mine only allows them at the end of lists. For example, this is valid for his generator,

<|B|C>(ikk)

But to work in mine, the empty item must be moved to the end,

<B|C|>(ikk)

This can be adjusted my making the proper changes to the grammar, which I haven't figured out yet.

Another problem with mine is that Parse::RecDescent is slooooowwwww. Ridiculously slow. Maybe I designed the grammar poorly? This is probably the biggest problem. Even simple patterns can take several seconds to generate names, specifically with deeply nested patterns. For example, this can take minutes,

<<<<<<<s>>>>>>>

Before you go thinking you are going to tank my server, I have written the web interface so that it limits the running time of the generator. If you want to do something fancy, use your own hardware. ;-)

There is also a problem that it will silently drop invalid pattern characters at the end of the pattern. This has to do with me not quite understanding how to apply Parse::RecDescent yet.

And this is where I need your help. I have had some trouble coming up with good patterns. I don't even have a good default, generic fantasy name pattern. Here are some of mine,

<s|B|Bv|v><V|s|'|V><s|V|C> # default
<i|Cd>D<d|i> # idiot
<V|B><V|vs|Vs> # short

None of which I am very satisfied.

You can design patterns for Nordic names, Gallic names, Tolkienesque Middle Earth names, orc names, idiot names, dragon names, dwarf names, elf names, Wheel of Time names, and so on. There is so much potential available with this tool.

You can see what patterns people have been trying in the log file. To suggest one to me, e-mail me some patterns, or even better, clone my git repository and add one to it yourself (then ask me to pull from you). This way your credit will stay directly attached to it with a commit.

Good luck!