Image of the glider from the Game of Life by John Conway
Skip to content

The Drunken Bishop For OpenPGP Keys

Almost a year ago, I blogged about the drunken bishop algorithm for OpenSSH key random art. Towards the end of the post, I mentioned that I would be building an OpenPGP implementation. I started doing so in Python, but eventually got sidetracked with other things. Well, I hosted the Scale 12x PGP keysigning party, and after the fact wished that I had finished the OpenPGP drunken bishop implementation. Well, I'll be hosting another PGP keysigning party at OpenWest 2014 next month, and couldn't risk missing another keysigning party where I could introduce the drunken bishop to attendees there.

The OpenPGP implementation follows ALMOST the exact algorithm. The only differences are this:

  1. OpenSSH key fingerprints are MD5 checksums while OpenPGP key fingerprints are SHA1 checksums. As such, a larger board is introduced.
  2. The algorithm for OpenSSH key fingerprints reads the fingerprint in little endian. I felt that this unnecessarily complicates the codebase, so I read the fingerprint in big edian.
  3. For the ASCII art output, the PDF paper mentions that as the bishop visits a square more often, the ASCII character should increase in weight gradually. Unfortunately, it appears this wasn't strictly observed. I've changed the characters that are shown in the art to more accurately reflect the frequency of visits to each square. The starting 'S' and the ending 'E' remain the same.
  4. I added an extra label at the bottom of the random art to depict the 8-bit OpenPGP key ID for that art.

Because it's written in Python, it is slower than its C counterpart for OpenSSH. If I were motivated enough to care, I'd write it in C. But, it's plenty fast for what it's doing, and I'm sure there are performance optimizations I can make to speed things up in the Python script.

I took 9 random keys from my GnuPG public keyring, and am showing them here, as a screenshot, rather than the horrible rendering that is web browsers:

Terminal screenshot showing 9 OpenPGP random art images

As with OpenSSH, these random art images for each public key exists to make verifying OpenPGP keys a bit easier. No doubt that there exist collisions, where more than one key produce the same artwork. When in doubt, verify the hex fingerprint. However, this may be a good alternate method for speeding up keysigning parties, by having each individual verify their key individually, then only speaking up if they feel their key is in error. This way, parties can go straight to identification checking, this eliminating 1/2 to 2/3 of the party. During identification checking, each individual could verify the key random art, fingerprint, etc. while checking photo identification.

A possible handout format for the random art images could look something like this:

+----[DSA 1024]-----+	
|l^  . ^^?^.        |	1) ID: 22EEE0488086060F
|l. . .l:.?         |	UID: Aaron Toponce 
|^ E ...ll          |	Fingerprint: E041 3539 273A 6534
|^. .  ^:.          |	             A3E1 9259 22EE E048
|^ . .  ..          |	Size/Type: 1024/DSA
| . .   . S         |	
|  . .   . .        |	Matches?
|   .     .         |	Fingerprint: ____ ID: ____ Signed: ____
|                   |	
|                   |	
|                   |	
+----[8086060F]-----+

Of course, this is less efficient on paper usage than the traditional table, but it could be improved.

The source code for generating the OpenPGP random art is at https://github.com/atoponce/scripts/blob/master/art.py. It requires an OpenPGP public key file as an argument when executing the script, like so:

$ ./art.py 8086060F.pgp

Hopefully, PGP keysigning party organizers find this useful in streamlining the keysigning process. If not, at least it could be entertaining.

Time Based One Time Passwords - How It Works

Introduction

With all the news about Heartbleed, passwords, and two-factor authentication, I figured I would blog about exactly how two-factor authentication can work- in this case, TOTP, or Time based one time passwords, as defined by The Initiative for Open Authentication (OATH). TOTP is defined in RFC 6238, and is an open standard, which means anyone can implement it, with no worries about royalty payments, or copyright infringements. In fact, TOTP is actually just an extension of HOTP (HMAC based one time passwords), which is defined in RFC 4226. I'll describe HOTP a little bit in this post, but focus primarily on TOTP.

What is two-factor authentication?

First, let's describe the problem. The point of two-factor authentication is to prevent attackers from getting access to your account. Two-factor authentication requires that two tokens be provided for proof of ownership of the account. The first token is something that we're all familiar with- a username and a password. The second token is a bit more elusive, however. It should be something you have, and only you. No one else should be able to come into possession with the same token. The same should be true for usernames and passwords, but we've seen how easily broken a single-factor authentication system is.

Think of two-factor authentication as layers on an onion. The first layer is your username and password. After peeling away that layer, the second layer is a secret token. Three-factor authentication is also a thing, where you can provide something that you are, such as a fingerprint or retinal scan. That would be the third layer in our onion. You get the idea.

However, the second token should not be public knowledge. It must be kept secret. As such, a shared secret is generated between the client and the server. For both HOTP and TOTP, this is just a base-32 random number. This random number, along with a message turns into an HMAC-SHA1 cryptographic hash (which is defined in RFC 2104; also described at Wikipedia).

Importance of Time

Unfortunately, a "shared secret" is a fairly lame form of authentication. First, the user could memorize the secret, no longer making it something the user has. Second, man in the middle attacks on shared secrets are extremely effective. So, we need the ability to prevent the user from memorizing the shared secret, and we need to make man in the middle attacks exceptionally difficult. As such, we turn our shared secret into a moving target.

HOTP, as already mentioned, is the base from which TOTP comes. HOTP uses the same algorithm as described below in this post, except that rather than using time as the moving factor, an 8-byte counter is changed. We need a moving target, because if the token were static, it would be no different than just a second password. Instead, we need the attacker to be constantly guessing as to what the token could be. So, with HOTP, a token is valid until used. Once used, the counter is incremented, and the HMAC-SHA-1 string is recalculated.

TOTP uses the UNIX epoch as its time scale, in seconds. This means that for TOTP, time starts with January 1, 1970 at 00:00.00, and we count the number of seconds that have elapsed since then. By default, we only look at 30 second intervals, on the minute. This means at the top of the minute (zero seconds past the minute), TOTP is refreshed, and again 30 seconds after the minute. TOTP uses a shared secret between the client and the server, so it's important that both the client and the server clocks are synchronized. However, RFC 6238 does allow for some clock skew and drift. As such, when a code is entered, the server will allow for a 30 second window on either side of the code. This means that the code is actually valid for a maximum of 90 seconds. If using NTP on the server, and a mobile phone for the client, then clock drift isn't a concern, as both will be continuously updated throughout the day to maintain accurate time. If NTP or GSM/CDMA broadcasts are not adjusting the clock, then it should be monitored and adjusted as needed.

Computing the HMAC-SHA-1

Hash-based message authentication codes (HMAC) require two arguments to calculate the hash. First, they require a secret key, and second, they require a message. For TOTP (and HOTP), the secret key is our shared secret between the client and the server. This secret never changes, and is the foundation from which our HMAC is calculated. Our message, is what changes. For TOTP, is the time in seconds, since the UNIX epoch rounded to the nearest 30 seconds. For HOTP, it is the 8-byte counter. This moving target will change our cryptographic hash. You can see this with OpenSSL on your machine:

$ KEY=$(< /dev/random tr -dc 'A-Z0-9' | head -c 16; echo)
$ echo $KEY
WHDQ9I4W5FZSCCI0
$ echo -n '1397552400' | openssl sha1 -hmac "$KEY"
(stdin)= f7702ad6254a06f33f7dcb952000cbffa8b3c72e
$ echo -n '1397552430' | openssl sha1 -hmac "$KEY" # increment the time by 30 seconds
(stdin)= 70a6492f088785444fc664e1a66189c6f33c2ba4

Suppose that our HMAC-SHA1 string is "0215a7d8c15b492e21116482b6d34fc4e1a9f6ba". We'll use this image of our HMAC-SHA-1 to help us identify a bit more clearly exactly what is happening with our token:

Image clarifying the HMAC-SHA-1 string, by using 20 divisions of 1 byte each (two characters per division).

Dynamic Truncation

Unfortunately, requiring the user to enter a 40-character hexadecimal string in 30 seconds is a bit unrealistic. So we need a way to convert this string into something a bit more manageable, while still remaining secure. As such, we'll do something called dynamic truncation. Each character occupies 4-bits (16-possible values). So, we'll look at the lower 4-bits (the last character of our string) to determine a starting point from which we'll do the truncating. In our example, the last 4-bits is the character 'a':

Same 20-division image, highlighting the last character of the HMAC-SHA-1 string- character 'a'.

The hexadecimal character "a" has the same numerical value as the decimal "10". So, we will read the next 31-bits, starting with offset 10. If you think of your HMAC-SHA-1 as 20 individual 1-byte strings, we want to start looking at the strings, starting with the tenth offset, of course using the number "0" as our zeroth offset:

Image clarifying the HMAC-SHA-1 string, by using 20 divisions of 1 byte each (two characters per division).

As such, our dynamically truncated string is "6482b6d3" from our original HMAC-SHA-1 hash of "0215a7d8c15b492e21116482b6d34fc4e1a9f6ba":

Same 20-division image, highlighting the first 31-bits of the HMAC-SHA-1 string, starting with the 10th offset.

The last thing left to do, is to take our hexadecimal numerical value, and convert it to decimal. We can do this easily enough in our command line prompt:

$ echo "ibase=16; 6482B6D3" | bc
1686288083

All we need now are the last 6 digits of the decimal string, zero-padded if necessary. This is easily accomplished by taking the decimal string, modulo 1,000,000. We end up with "288083" as our TOTP code:

TOTP: 288083

The user then types this code into the form requesting the token. The server does the exact same calculation, and verifies if the two codes match (actually, the server does this for the previous 30 seconds, the current 30 seconds, and the next 30 seconds for clock drift). If the code provided by the user matches the code calculated by the server, the token is valid, and the user is authenticated.

Conclusion

TOTP, and alternatively HOTP, is a great way to do two-factor authentication. It's based on open standards, and the calculations for the tokens are done entirely in software, not requiring a proprietary hardware or software solution, such as provided by RSA SecurID and Verisign. Also, the calculations are done entirely offline; there is no need to communicate with an external server for authentication handling at all. No calling home to the mothership, to report someone has just logged in. It's platform independent, obviously, and is already implemented in a number of programming language libraries. You can take this implementation further, by generating QR codes for mobile devices to scan, making it as trivial as installing a mobile application, scanning the code, and using the tokens as needed.

Two Factor Authentication with OpenSSH

With all the news about Heartbleed, passwords and two-factor authentication, I figured I would finally get two-factor authentication working with my SSH servers. I've known about it in the past, but haven't done anything about it. Now is the time.

To get two-factor authentication working with your OpenSSH server, you need to install the "libpam-google-authenticator" PAM module on your system. Don't let the package name fool you, however. It is developed by Google, but it does not "phone home" to Google servers at all. It also does not require a Google account. Further, the PAM module is Free and Open Source software, licensed under the Apache 2.0 license.

To install the module on Debian-based systems, run the following:

$ sudo aptitude install libpam-google-authenticator

Once installed, run the google-authenticator(1) command, and answer the resulting questions. The questions offer a balance between increased security and convenience of use. You have the opportunity to create an HMAC-Based One-time Password (HOTP), as specified in RFC 4226, or a Time-based One-time Password (TOTP), as specified in RFC 6238. The only difference, is that with HOTP, each code is dependent on the previous codes, whereas with TOTP, each code is dependent on time. If running NTP on your SSH server, and you're using this with a phone, then TOTP would probably be a better bet, as time will be very closely synchronized, and unlikely to fall out of sync.

The command will create an ANSI QR code that you can scan on your phone to setup the codes. Further, it will print 5 backup codes in the event that you lose your phone, or don't have it, but need to login. Print those backup codes, and store them in your wallet. Just in case you need the codes, they are stored in your ~/.google_authenticator file:

$ cat ~/.google_authenticator 
YXSNFX37ZUZCKVZM
" RATE_LIMIT 3 30
" WINDOW_SIZE 17
" DISALLOW_REUSE
" TOTP_AUTH
74110971
51742064
84348069
78844952
28772212

Now you just need to configure OpenSSH to use OTP as part of the authentication process. There are two configuration files to edit. First, you need to edit the /etc/pam.d/sshd config file, and put "auth required pam_google_authenticator.so" at the bottom of the file:

$ sudo vim /etc/pam.d/sshd
(move to the bottom of the file)
auth required pam_google_authenticator.so

Now change the /etc/ssh/sshd_config file, to allow a challenge and response as part of the authentication process:

$ sudo vim /etc/ssh/sshd
ChallengeResponseAuthentication yes

Restart your OpenSSH server, and you should be good to go:

$ sudo service ssh restart

For an OTP application that you can install on your Android phone, I would personally recommend FreeOTP by Red Hat. It's Free and Open Source software, unlike the Google Authenticator app, and it has increased security in that codes are not displayed by default. Instead, you must tap the refresh button for that site to display the code. Also, I like the display options better with FreeOTP than with Authenticator, but that's personal choice. There currently is not an iOS version of the application in the Apple App Store, but my understanding is that one will make it there soon.

Anyway, happy two-factor authentication on your OpenSSH server!

Heartbleed And Your Passwords

Recently it was discovered that OpenSSL contained a pretty massive security hole that allowed simple TLS clients to retrieve plain text information from a TLS-protected server using the TLS Heartbeat. The advisory is CVE-2014-0160. This has to be one of the most dangerous security vulnerabilities to hit the Internet in a decade. More information can be found at https://heartbleed.com/ (ironically enough, using a self-signed certificate as of this writing).

I don't wish to cover all the extensive details of this vulnerability. They are large and high in number. However, I do want to address it from the point of passwords, which is something I can handle on this blog. First, let's review the heartbleed vulnerability:

  1. FACT: This vulnerability was introduced into OpenSSL on December 31, 2011.
  2. FACT: This vulnerability was fixed on April 5, 2014.
  3. FACT: Without the TLS heartbeat bounds check, data is leaked in 64KB chunks.
  4. FACT: A TLS client can expose the server's SSL private key, to decrypt future communication, without any special hardware or software.
  5. FACT: This is not a man-in-the-middle (MITM) attack.
  6. FACT: Armed, an attacker can reveal usernames and passwords without anyone knowing.

To demonstrate this, here is a post by Ronald Prins on Twitter:

He demonstrates it on his blog, showing a censored example. What does this mean? This means that if you logged into a server, using SSL during the past two years, your username and password could already be compromised. This includes your email acount, your bank account, or social media accounts, and any others. Of course, if the service takes advantage of two-factor authentication, then that specific account is likely safe. However, if you share passwords between accounts, additional accounts may not be.

I really wish I was joking.

My advice? Time to change passwords to accounts you think you may have used over the past two years. But, before you do so, you need to know if the service is protected against Heartbleed. You can use http://possible.lv/tools/hb/ and http://filippo.io/Heartbleed/ as online Heartbleed testers before logging in with your account credentials.

Protect Against Bit Rot With Parchive

Introduction

Yes, this post was created on April 1. No, it's not an April Fool's joke.

So, I need to begin with post with a story. In 2007, I adopted my daughter, and my wife decided that she wanted to stay home rather than work. In 2008, she quit her job. She was running a website on my web server, which only had a 100G IDE PATA drive. I was running low on space, so I asked if I could archive her site, and move it to my ext4 Linux MD RAID-10 array. She was fine with that, so off it went. I archived it using GNU tar(1), and compressed the archive with LZMA. Before taking her site offline, I verified that I could restore her site with my compressed archive.

From 2008 to 2012, it just sat on my ext4 RAID array. In 2012, I built a larger ZFS RAID-10, and moved her compressed archive there. Just recently, my wife has decided that she may want to go back to work. As such, she wants her site back online. No problem, I thought. I prepared Apache, got the filesystem in order, and decompressed the archive:

$ unlzma site-backup.tar.lzma
unlzma: Decoder error

Uhm...

$ tar -xf site-backup.tar.lzma
xz: (stdin): Compressed data is corrupt
tar: Unexpected EOF in archive
tar: Unexpected EOF in archive
tar: Error is not recoverable: exiting now

Oh no. Not now. Please, not now. My wife has put in hundreds of hours into this site, and many, many years. PDFs, images, other media, etc. Tons, and tons of content. And the archive is corrupt?! Needless to say, my wife is NOT happy, and neither am I.

I'm doing my best to restore the data, but it seems that all hope is lost. From the GNU tar(1) documentation:

Compressed archives are easily corrupted, because compressed files have little redundancy. The adaptive nature of the compression scheme means that the compression tables are implicitly spread all over the archive. If you lose a few blocks, the dynamic construction of the compression tables becomes unsynchronized, and there is little chance that you could recover later in the archive.

I admit to not knowing a lot about the internal workings of compression algorithms. It's something I've been meaning to understand more fully. However, best I can tell, this archive experienced bit rot in the 4 years it was on my ext4 RAID array, and as a result, the archive is corrupt. Had I known about Parchive, and that ext4 doesn't offer any sort of self healing with bit rot, I would have been more careful storing that compressed archive.

Because most general purpose filesystems do not protect against silent data errors, like Btrfs or ZFS, there is no way to fix a file that suffers from bit rot, outside of restoring from a snapshot or backup, or the internal file type has some sort of redundancy. Unfortunately, I learned that compression algorithms have very little to no redundancy in the final compressed file. It makes sense, as compression algorithms are designed to remove redundant data, either using lossy or lossless techniques. However, I would be willing to grow the compressed file, say 15%, if I knew that I could suffer some damage on the compressed file, and still get my data back.

Parchive

Parchive is a Reed-Solomon error correcting utility for general files. It does not handle Unicode, and it does not work on directories. It's initial use was to maintain the integrity of Usenet posts on the Usenet server against bit rot. It has since been used by anyone who is interested in maintaining data integrity for any sort of regular file on the filesystem.

It works by creating "parity files" on a source file. Should the source file suffer some damage, up to a certain point, the parity files can rebuild the data, and restore the source file, much like parity in a RAID array when a disk is missing. To see this in action, let's create a 100M file full of random data, and get the SHA256 of that file:

$ dd if=/dev/urandom of=file.img bs=1M count=100
100+0 records in
100+0 records out
104857600 bytes (105 MB) copied, 7.76976 s, 13.5 MB/s
$ sha256sum file.img > SUM
$ cat SUM
5007501cb7f7c9749a331d1b1eb9334c91950268871ed11e36ea8cdc5a8012a2  file.img

Should this file suffer any sort of corruption, the resulting SHA256 hash will likely change. As such, we can protect the file against some mild corruption with Parchive (removing newlines and cleaning up the output a bit):

$ sudo aptitude install par2
(...snip...)
$ par2 create file.img.par2 file.img
(...snip...)
Block size: 52440
Source file count: 1
Source block count: 2000
Redundancy: 5%
Recovery block count: 100
Recovery file count: 7
Opening: file.img
Computing Reed Solomon matrix.
Constructing: done.
Wrote 5244000 bytes to disk
Writing recovery packets
Writing verification packets
Done

As shown in the output, the redundancy of file is 5%. This means that we can suffer up to 5% damage on the source file, or the parity files, and still reconstruct the data. This redundancy is default behavior, and can be changed by passing the "-r" switch.

If we do a listing, we will see the following files:

$ ls -l file.img*
-rw-rw-r-- 1 atoponce atoponce 104857600 Apr  1 08:06 file.img
-rw-rw-r-- 1 atoponce atoponce     40400 Apr  1 08:08 file.img.par2
-rw-rw-r-- 1 atoponce atoponce     92908 Apr  1 08:08 file.img.vol000+01.par2
-rw-rw-r-- 1 atoponce atoponce    185716 Apr  1 08:08 file.img.vol001+02.par2
-rw-rw-r-- 1 atoponce atoponce    331032 Apr  1 08:08 file.img.vol003+04.par2
-rw-rw-r-- 1 atoponce atoponce    581364 Apr  1 08:08 file.img.vol007+08.par2
-rw-rw-r-- 1 atoponce atoponce   1041728 Apr  1 08:08 file.img.vol015+16.par2
-rw-rw-r-- 1 atoponce atoponce   1922156 Apr  1 08:08 file.img.vol031+32.par2
-rw-rw-r-- 1 atoponce atoponce   2184696 Apr  1 08:08 file.img.vol063+37.par2

Let's go ahead and corrupt our "file.img" file, and verify that the SHA256 hash no longer matches:

$ dd seek=5k if=/dev/zero of=file.img bs=1k count=128 conv=notrunc
128+0 records in
128+0 records out
131072 bytes (131 kB) copied, 0.00202105 s, 64.9 MB/s
$ sha256sum -c SUM
file.img: FAILED
sha256sum: WARNING: 1 computed checksum did NOT match

This should be expected. We've corrupted our file through a simulated bit rot. Of course, we could have corrupted up to 5% of the file, or 5 MB worth of data. Instead, we only wrote 128k of bad data.

Now that we know our file is corrupt, let's see if we can recover the data. Parchive to the rescue (again, cleaning up the output):

$ par2 repair -q file.img.par2 
(...snip...)
Loading "file.img.par2".
Loading "file.img.vol031+32.par2".
Loading "file.img.vol063+37.par2".
Loading "file.img.vol000+01.par2".
Loading "file.img.vol001+02.par2".
Loading "file.img.vol003+04.par2".
Loading "file.img.vol007+08.par2".
Loading "file.img.vol015+16.par2".
Target: "file.img" - damaged. Found 1996 of 2000 data blocks.
Repair is required.
Repair is possible.
Verifying repaired files:
Target: "file.img" - found.
Repair complete.

Does the resulting SHA256 hash now match?

$ sha256sum -c SUM 
file.img: OK

Perfect! Parchive was able to fix my "file.img" by loading up the parity files, recalculating the Reed-Solomon error correction, and using the resulting math to fix my data. I could have also done some damage to the parity files to demonstrate that I can still repair the source file, but this should be sufficient to demonstrate my point.

Conclusion

Hindsight is always 20/20. I know that. However, had I known about Parchive in 2008, I would have most certainly used it on all my compressed archives, including my wife's backup (in reality, a backup is not a backup unless you have more than one copy). Thankfully, the rest of the compressed archives did not suffer bit rot like my wife's backup did, and thankfully, all of my backups are now on a 2-node GlusterFS replicated ZFS data store. As such, I have 2 copies of everything, and I have self healing against bit rot with ZFS.

This is the first time in my life where bit rot has reared its ugly head, and really caused a great deal of pain in my life. Parchive can fix that for those who have sensitive data where data integrity MUST be maintained on filesystems that do not provide protection against bit rot. Of course, I should have also had multiple copies of the archive to have a true backup. Lesson learned. Again.

Parchive is no substitution for a backup. But it is a protection against bit rot.

Creating Strong Passwords Without A Computer, Part III - Off The Grid

Previously, I used entropy as a backdrop for creating strong passwords. It's important that you read that article and fully understand it before moving on with the rest of the series.

So far, I've blogged about generating passwords using systems that your grandma could use. In this case, I have less confidence that my grandma would be willing to give this a go. Not because she's stupid, but because she's impatient. The older I get, the less patience I have for things like this, so I can understand where she's coming from. In this post, we'll be discussing Steve Gibson's paper cipher Off The Grid.

Introduction

Off The Grid is a paper-based cipher for encrypting domain names. The concept is built around the idea of using Latin Squares as a means for creating the cipher. Off The Grid is a 26x26 Latin Square using the English alphabet. In other words, any character appears only one in any given row and column. As a result of the Latin Square, words can be traversed throughout the square, alternating rows and columns. This will be explained further.

Outside of the grid are numbers and non-alphabetic characters. These are used as an additional resource when creating the passwords for your sites. Because the grid itself is a randomized mixture of lowercase and uppercase letters, the grid itself has an entropy of approximately 5.7-bits per character. The outer border consists of the following characters:

0123456789!"#$%&'()*+,/:;<=>?@[$$^{|}~

As such, if using the border to build your passwords, then you have access to 90 total unique characters, bringing your entropy to approximately 6.59-bits per character.

Because we determined that 80-bits of entropy should be the minimum when generating passwords, if your password consists of only the alphabetic characters in the grid, then you should aim at building at least 15-character passwords. If you are including the outer border in your password building, then a 13-character password should be the target.

The grid and border are randomized, minus 12 characters in the center of the top border, so the resulting password is a true random password that can be used for your accounts. Thus, the requirements to build a truly random password with at least 80-bits of entropy is achieved.

Off The Grid

Off The Grid is a finite state machine. This is achieved by traversing the grid from a starting location to an ending location, the rules of which will be described here. After reaching your first ending location, a second traversal is made starting from the first ending location, and ending at a new location. There are exactly 26^2 or 676 states in the Off The Grid system.

In Steve's instructions for building passwords using the grid, you take the first 6 characters of the domain name, and build a resulting password of 12 characters- 2 ciphertext characters for each 1 plaintext character. Unfortunately, as we demonstrated, this doesn't provide us with enough entropy to withstand offline database attacks. As such, I would look at what you want for your target password length. If it's 15 characters, then I would take the first 5 characters of the domain name, and use a ratio of 3:1 rather than 2:1 when building the password. If you want a 16 character password, then you could use the first 4 characters of the domain name, and use a ratio of 4:1, or you could take the first 8 characters of the domain name, and use a ration of 2:1. Keep this in mind, because from here on out, it gets challenging, and you'll need your ratio for later.

Off The Grid can be described in the following steps:

  1. You are always using the domain name for building your passwords.
  2. Determine how many characters from the domain name you will need to build your password.
  3. Find the first character of the domain name in the first row.
  4. Find the second character of the domain name in the column below the first character.
  5. Find the third character of the domain name in the row of the previous character.
  6. Alternate rows and columns until you reach the last character of the domain name.
  7. Starting at your new position, find the first character of the domain name in that row.
  8. Overshoot in that row by the ratio you determined before. If your ratio is 2:1, overshoot 2 characters. If your ratio is 4:1, overshoot 4 characters.
  9. Write down the characters you overshot with. These will build your password.
  10. Now at your new overshot position, find the second character of the domain name in the column below the overshot character.
  11. Overshoot in that column by the ratio you determined before.
  12. Write down the characters you overshot with.
  13. Continue alternating rows and columns, overshooting by your ratio, and writing down the overshot characters until you've traversed the domain name
  14. You now have your password.

PHEW!!!

Building passwords using Off The Grid is tricky. Once you understand the above steps, and practice it, then it will become easy. But the initial understanding of how the system works is a bit a pain in the behind. In the next section, I'll be providing an example.

A Simple Example

Visiting his website, I created the following sample grid that we'll use for this post:

A Sample Off The Grid key.

Suppose we wish to setup a password for example.com, and suppose that example.com does not restrict passwords for our account in anyway. As such, we are fine building passwords with just alphabetic characters. We'll handle how to add non-alphabetic characters to our password in a minute. As such, I need to build a 15-character password. The text "example" is 7 characters. I'll take the first 5 characters "examp" and use a ratio of 3:1 for building my password.

First step is to locate the letter 'e' in the first row. You can decide to use any row, or column for your first letter. However, the goal is to be consistent, as using a different row or column for the same domain will produce different results. In these examples, I'll be starting in the first row. In this example, it's in the 25th column from the left edge. Now I locate the 'x' in the 25th column. It's in the 18th row from the top in the 25th column. Now I look along that row for 'a'. I continue in this manner, until I've worked out "examp". On my example card, my path after phase 1 would look like this:

Tracing the text 'examp' on our sample OTG key.

Now I'm in a new location ready to start creating my password. This is phase 2, the overshoot phase. Because I ended looking for 'p' in the same row as 'a', I'm going to switch to looking for 'e' in the same column as 'p' to start this phase. In other words, I am constantly alternating row, column, row, column, etc., even when switching phases. However, rather than stopping at the letter 'e', I will overshoot by by 3 characters, recording the characters I have overshot.

So, I find 'e' then continue moving 3 characters in the column, reaching 'a' in my example grid. The 3 characters that were overshot were 'Mta'. These are the first 3 characters of my domain password for example.com.

I now look for 'x' in the same row as my overshot 'a'. I will again overshoot by 3 characters to the letter 'P'. The overshot characters in that row were 'zhP', and are the second set of characters for my password. Thus, up to this point, my password for example.com has become 'MtazhP'.

I will continue alternating rows and columns, overshooting by 3 characters, writing down the overshot characters as my password, until I overshot every character in "examp". My password is "MtazhPfoYgpJvWy", and my path would have looked like this in phase 2 (the domain path is traced in red, with the overshoot characters traced in blue):

Tracing the text 'examp' again, this time overshooting by 3 characters on our sample OTG key.

Notice that my overshoot needed to wrap around the card. This should be expected in phase 2, and wrapping around the card is appropriate.

Make sure that you fully understand these two phases of creating your password before continuing. You want to make sure you get it right every time for every domain, without error.

Handling non-alphabetic characters

Now it's time to get a bit ugly. Up to this point, the OTG system only generates passwords with alphabetic characters. It does not generate passwords with anything else. This can be problematic for sites that require the use of non-alphabetic characters in the password. Further, some domains may have a '.', '-' or digit as part of the domain. These non-alphabetic characters are not part of the inner OTG grid, so creating a password with them is impossible.

This is where the outer border comes into play. First notice that a digit and non-alphanumeric character are always opposite of each other on the border. This is by design. In our case, opposite of '#' on the top border is a '2' on the bottom border. Opposite of the ',' on the bottom border, is the digit '8' on the top border, and so forth. Let's first discuss how to add non-alphabetic characters to our passwords:

Letting the OTG choose

While traversing the grid in phase 2, building your password, you can incorporate the border into your overshoot. In my previous example of "example.com", we traced out the word "examp", and overshot with 3 characters, all of the form <grid><grid><grid>. Rather, we could have used our 3rd overshoot character to be our border character. As such, our pattern would have been <grid;><grid><border>. In that case, we would stop at the 2nd overshoot character, rather than the border, to find the rest of our characters in our domain. As a result, for every character in the domain, there will be a non-alphabetic character:

Sample OTG showing a possible path for building a password with non-alphabetic characters.

In this case, the password for example.com would be "Mt.bA1oQ7cZ[IA2"

This example also brings up a good point: when the overshoot character is the same character as the next character that you need to traverse to, then skip one more character. In other words, notice that with "examp", when we travel to "x", our overshoot character is "A". This is the next character that we would be traveling to. So, I overshot one more character to "W", then traveled to my "a" in "examp". If you think that exception sucks, you're right. It does. It's just another rule that can introduce human error into the equation.

Further, notice that I needed to wrap around the card, as we already expressed earlier. Yet, my border character technically came after "c" and before "Z". However, I still put the border character at the end. I am doing this for consistency with the rest of the password, so I don't have to keep yet another rule in my head.

Letting the OTG help

In this case, some sites do not allow non-alphanumeric characters in the password. In other words, it's letters and digits only. Part of the border pattern is that there is exactly one digit in the border for every row and every column. So, rather than overshooting to a non-alphanumeric character, you could just use the number in that row or column instead. This way, our previous password would be "Mt5bA1oQ7cZ7IA2".

Tack something onto the beginning or end

Of course, you could always just tack a special character or two at the beginning or end of the password. Your logic for how this is accomplished is up to you. You could use the beginning row/column border character in phase-2, or the ending row/column border character. Whatever makes the most sense for you.

Handling domains with non-alphabetic characters

Unfortunately, some domains have non-alphabetic characters in their domain name. Although seldom, they do exist, and OTG can't completely rule out the possibility that they will not be encountered. As such, in the center of the top border are 12 characters- the digits 0 through 9, the period and the dash. If these characters are encountered as part of traveling through the OTG with the domain, then travel to the character in the first row immediately below that character in the same column. For example, if your domain had a "5" in the domain, then you would travel to "f" in the first row in our example OTG card. If there are consecutive numbers in your domain, then unfortunately, I am not sure exactly how that is to be handled.

Criticisms, Thoughts and Conclusion

DOUBLE PHEW!!!

If you have made it to this point, you're determined to learn OTG. In my opinion, Steve's OTG paper system has some pretty serious problems:

  • The rules are technical and many, making the entire system very cumbersome to use.
  • Overall, creating your passwords are slow, slow, slow. Hopefully you store them in an encrypted database for retrieval, because recreating them is very slow, and not something you want to be fighting with when under stress.
  • Due to the cumbersome nature of OTG, creating your passwords can be very error prone.
  • The size of the OTG card is too large to fit into your wallet to carry with you, and see the characters on the grid without a magnifying glass.
  • If the card is lost, and the card is attributed to you, because you are using domains to create the passwords, the attacker could easily figure out the password to your accounts with the card. As such, you may want to prepend a 1- or 2-character salt onto the domain before beginning phase 1.

These are probably my biggest criticisms of the OTG system. While slick for a paper-based encryption system, it's a lot of visual scanning and lookups, a lot of rules and exceptions to remember, and a lot of areas that can create errors. Some die-hards may use this for their passwords, but I don't think I can recommend it, even to some of the most nerdy, security conscious friends I have.

In my opinion, the PasswordCard is a much more elegant system that doesn't require the user to keep a lot of rules and exceptions in their head, and if the card is lost, the attacker still has a great amount of work to do figuring out what the password is, and to which account it belongs to.

To be fair, the OTG system is marked as "Work in Progress", so there may be adjustments to the system in the future that make it more of an elegant system for creating passwords. But I think the whole thing will need to be reworked, as traversing a Latin Square to create passwords is just too cumbersome for practical use.

Creating Strong Passwords Without A Computer, Part II - The PasswordCard

Previously, I used entropy as a backdrop for creating strong passwords. It's important that you read that article and fully understand it before moving on with the rest of the series.

Continuing our series about creating strong passwords without a computer, we look at a method I've blogged about in the past: The PasswordCard. The idea is simple: carry around a card with you, that has all of your passwords written down in plaintext, obfuscated with additional text surrounding the password. Let's look at it in more detail.

The Passwordcard Idea

The PasswordCard is a GPLv3 web application that generates a small credit-card sized card that you can fit into your wallet for password generation. The way you would generate a password is simple. Suppose you wanted to generate a password for an online account, such as an email provider. You could pull out your PasswordCard, determine a starting location, a direction, and a length, and use the resulting characters for your password. Because the PasswordCard is a two-dimensional table of characters, the direction of your password can take any direction, such as left, right, up, down, diagonally, spiral, or any combination of directions. Because the length of your password can theoretically be infinite, so too would be the search space, if someone were to get access to your card.

The PasswordCard uses the following character sets when generating a card on the site:

  • alphanumeric: "23456789abcdefghjkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"
  • alphanumeric plus symbols: "23456789abcdefghjkmnpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ@#$%&*<>?€+{}[]()/\"
  • numeric: "0123456789"

As such, you can expect the following entropy sizes per character when creating a card:

  • Alphanumeric (55 unique characters): 5.78-bits.
  • Alphanumeric plus symbols (76 unique characters): 6.25-bits.

When checking the box "check this for an area with only digits", it doesn't change the search space for the already existing alphanumeric output that is default when loading the page. It only creates 4 rows of digits for easy PIN generation. Your entropy per character is only increased when checking the box "check this to include symbols".

A Practical PasswordCard

Before beginning, let's use a sample card to work from. This is card 7327e6c258cb3d52, in case you also want to generate it for following along:

Sample PasswordCard

To generate a password, you would need to pick a starting location for your password. You'll notice that there are 29 columns and 8 rows. The columns are identified by symbols, while the rows are identified both by a color and a number. For each account, all you need to remember are 3 things:

  • The starting location (should be different for every account).
  • The direction (should be the same for each account).
  • The length (should be the same for each account).

This should be easier to remember than "NyFScbUJ>X7j?", but your brain might be wired differently than mine.

Because this PasswordCard is using both alphanumeric and non-alphanumeric characters on the card, and our entropy per character is approximately 6.25-bits, and further, because we established that we need a minimum of 80-bits of entropy in our passwords, we should generate at least a 13-character password off of the card.

Some PasswordCard Direction Ideas

Most of those who are using the PasswordCard to generate their passwords, are probably just reading the passwords left-to-right. I would not recommend this, as it's the lowest hanging fruit for an attacker, if they have access to a hashed password database, and your password card. Instead, I would recommend doing something non-standard for the password direction. Let's consider a few examples, each of them starting at ⊙4 on the PasswordCard:

Wall Bouncing

When hitting a wall, when either travelling diagonally or otherwise, when you hit a wall, you could "bounce" off the wall much like a pool ball would when playing billiards:

Sample PasswordCard showing a path bouncing off of the walls.

In this case, the password would be "f+zwWYB[5\C<u".

Wall Bending

Rather than bouncing off the wall like pool balls, you could "bend" along the wall, much like turning a corner when driving on a street:

Sample PasswordCard showing a path bending along the wall.

In this case, the password would be "f%efcEBnNQk7\".

Pac-Man Walls

Another alternative would be to treat the walls as a topological spheroid, much like Pac-Man. In other words, when you come to the edge of the room, you travel out the other side on the same row, or the same column, continuing in your direction:

Sample PasswordCard showing a path Pac-Man might take when traveling to the edge of our wall.

In this case, the password would be "f+zwrpt9n2B&y".

Spiral paths

My last example shows a spiral path, starting from the same location as the previous examples, this case moving clockwise:

Sample PasswordCard showing a spiral path.

In this case, the password would be "fY+%FqvGYerrz".

As a strong suggestion, whatever direction and length you take for your passwords, you should keep them consistent. If you decide to do a 13-character clockwise spiral for one account, you should do a 13-character clockwise spiral for all of your accounts. The only thing changing is the location of the password. This will greatly simplify identifying each password for each account. If you change up the lengths and directions, and well as the starting location for each account, you run the risk of having a very difficult time finding the correct password for that account. If your brain has that mental capacity, then the more power to you. Otherwise, I would keep it consistent.

A Couple Thoughts

The nice thing about the PasswordCard, is that all of your passwords are already written down for you in plaintext. However, if a password cracker were to get access to your card, they would need to know which starting location belongs to which account, the direction the password takes, as well as the length of the password. This is too many variables for an attacker to make efficient use of his time. His time would be better spent taking the character sets off of the card, and building an incremental brute-force search. Provided your password has sufficient entropy, you will likely thwart the attack.

There are a couple disadvantages with the PasswordCard, however. The first is that this is not well suited for the blind. Unlike Diceware, which can be easily adapted for the blind, this is a bit more of a challenge. While I'm not asserting that it's impossible, it certainly seems difficult to practically reproduce. The second disadvantage is the use of the "€" euro symbol. The PasswordCard is developed by a Java developer in the Euro Zone. While it makes sense for him to include the character, it alienates those that don't easily have access to it on their keyboards, such as those using the basic ASCII character set. As such, you may want to refresh your browser, generating random cards until you find one without the "€" character in its output.

Lastly, you will definitely want to print a second card, and keep it somewhere safe as a backup, should you lose the original. Keeping the card in your wallet or purse makes the most sense, as your wallet or purse is likely the most protected object in your possession, next to your phone and keys. But, should you lose the card, you will want to get access to your passwords, which will mean getting access to your backup copy.

Conclusion

I personally like the PasswordCard. It's simple, small, and doesn't require me to carry a lot of items with me, such as dice and a large word list. My only concern is being able to choose a new starting location for each account. I'm not as random as I would think when finding a starting location, so I wrote a script to handle that for me. But it's clean, out of the way, and works really well. When I don't have an account password memorized, I can pull out the card, remember where it starts, and just start typing. Generation is quick, and remember password locations is easy. Highly recommended.

Creating Strong Passwords Without A Computer, Part I - Diceware

Previously, I used entropy as a backdrop for creating strong passwords. It's important that you read that article and fully understand it before moving on with the rest of the series.

Now let's begin generating passwords. We'll start off first with Diceware.

Diceware

Diceware meets these 2 qualifications that we should use when building our passwords. However, Diceware prefers to call them "passphrases", rather than passwords, as your password will actually be multiple words stringed together, rather than just a single word. The passphrase is built by rolling 5 fair 6-sided dice (or 1 fair 6-sided die rolled 5 times), and looking up the results in a word list.

The word list comprises of 7,776 words (the total number of combinations from 5 fair 6-sided dice). Each word has a look up number that corresponds to the dice roll. For example, if you rolled "44311", then your first word from the word list would be "oint". I say "first word", because you now need to make another roll. You need to continue rolling until your passphrase contains at least 80-bits of entropy.

Because there are 7,776 possible words in the word list, then each word contains about 12.95 bits of entropy. This means you will need to roll your 5 dice seven times (six rolls will only produce 77.7-bits of entropy) to achieve the minimum. Starting with my first word, and rolling six more times, here are the results of my dice rolls:

44311 oint
12115 alum
16335 cg
64566 xs
22213 cut
43221 mutt
53143 scar

Or, "ointalumcgxscutmuttscar", which is 23 total characters in length. This is a semi-lengthy password, no doubt, but it meets our criteria to be truly random and contains sufficient entropy. Further, because the word list can be printed, you can generate secure, and strong passwords without the aid of a computer.

Variation 1- Portable Diceware

Carrying around a word list of 7,776 words might not be very practical. After all, if you store it in your wallet, assuming you can hold something about 10-by-30 characters on each side of a card, you would need to print close to 175 cards to fit all the Diceware word list. This just isn't practical. You could store the word list as a PDF, and carry it on your phone, but not everyone has a phone capable of installing a PDF reader, and we're trying to achieve this without the aid of any computing device. Let's dig further.

For carrying around only one or two cards in your wallet, we'll need to generate some tables. Thankfully the tables are small, and you can still generate secure passwords. Unfortunately, the passwords will not be as easy to remember as using the original word list. Consider the following table:

If first roll=1 or 2               3 or 4               5 or 6
           Second Roll          Second Roll          Second Roll
         1  2  3  4  5  6     1  2  3  4  5  6     1  2  3  4  5  6

T  1     A  B  C  D  E  F     a  b  c  d  e  f     !  @  #  $  %  ^     
h  2     G  H  I  J  K  L     g  h  i  j  k  l     &  *  (  )  -  =
i  3     M  N  O  P  Q  R     m  n  o  p  q  r     +  [  ]  {  }  \  
r  4     S  T  U  V  W  X     s  t  u  v  w  x     |  `  ;  :  '  "
d  5     Y  Z  0  1  2  3     y  z  ~  _  sp       <  >  /  ?  .  ,
   6     4  5  6  7  8  9

In this case, I will only need 3 fair 6-sided dice (or 1 fair 6-sided die rolled three times), rather than 5. Suppose I roll "614". The "6" means I would use the third table. The "1" means the first column in the third table, and the "4" is the fourth row in the 1st column of the third table, or "|". All 94 printable ASCII characters, plus the space, are represented in these tables. Each character gives about 6.57-bits of entropy, which means you would only need to roll your 3 fair 6-sided dice thirteen times to get enough entropy to meet our requirement for at least 80-bits of entropy.

As an example, consider the following rolls:

614 622 224 461 424 155 565 113 255 322 136 631 544

This would produce:

614 |
622 *
224 T
461 f
424 t
155 2
565 ,
113 M
255 2
322 h
136 6
631 #
544 :

Or "|*Tft2,M2h6#:" as our password. This password contains 85.41-bits of entropy, and was created at random. The characters "sp" represent the ASCII space. If you reach a table blank on any of your rolls, such as rolling "616", or "365", just roll again.

If you only need to create a password that uses just letters and numbers, then you only need to use the first table, and you only need two dice. However, each character only gives about 5.17-bits of entropy. As such, we would need a 16-character password to achieve our 80-bits minimum.

There are other variations on the tables with dice that you can use, such as generating random hexadecimal strings, random decimal numbers, special characters, and other requirements. See the Diceware FAQ for more information.

Variation 2- Dictionaryware

While carrying around a word list in your wallet or purse might not be practical, you may have a dictionary in your bookshelf, or the place you are visiting might have a dictionary you can borrow. The tricky part about dictionaries, however, is determining your search space, so you can accurately calculate entropy. Thankfully, we just need to put on our thinking caps, do a bit of math, and we can arrive at a good number.

My Merriam-Webster Dictionary contains approximately 57,000 defined words, across 820 pages of printed text. This averages to 70 dictionary words page. Each page is divided into two columns, which gives me about 35 dictionary words per column. I'll use the same 5 fair 6-sided dice I used in my initial Diceware. Because my dictionary book contains 3 numbers for its page number, the first 3 dice will tell me the page number of the dictionary. The 4th die will tell me which column the word will come from; if the die is odd (1, 3, or 5), the first (left) column is used, if the die is even (2, 4, or 6), then the second (right) column is used. The 5th die will tell me the word in that column, which means only using the first 6 words in each column.

As an example, if my roll was "56351", then I would turn to page "563", use the first column on the page, and the first word, which is "Pullman".

Obviously, there are a great number of pages skipped, and a lot of words skipped. To understand how much entropy each word provides, I need to figure out how many words are available given my limitations with 6-sided dice. First, the following pages in my dictionary are skipped:

  • 1-110 (a-calm)
  • 167-210 (convolution-disgust)
  • 267-310 (festoon-GQ)
  • 367-410 (inhale-litigious)
  • 467-510 (natty-patchwork)
  • 567-610 (QM-rumble)
  • 667-820 (stab-zymurgy)

That's a total of 484 pages eliminated from the book, which means I only have 336 valid pages to use. Because I can only choose the first 6 words from each column, or 12 words per page, that gives me 4,032 total words available to pick from. As such, each word provides about 11.98-bits of entropy, which means I need at least 7 words from my dictionary to reach my 80-bits entropy minimum for my passphrase.

As an example, if I use my rolls that I used at the beginning of this post, then my result would be:

44311 midday
12115 castled
16335 constancy
64566 skew
22213 drag
43221 maunder
53143 plantain

Or "middaycastledconstancyskewdragmaunderplantain". That's 45 characters in length, which is rather lengthy to achieve the minimum amount of entropy as our initial Diceware roll at the start of this post. This is due to the possibility of words in the English language being longer than 7 characters, which doesn't exist in our Diceware list. As such, you will likely get longer passphrases using an English dictionary versus using the Diceware list.

Some points to take into consideration when using "Dictionaryware":

Different dictionaries will need to be adjusted as necessary to accommodate the number of pages, and the number of columns. You just need to make sure that the dice are picking the word, and not you. If your dictionary is smaller than 600 pages, you may need to come up with a system handling the numbers 0, 7, 8, & 9 to get sufficient entropy. Additional dice rolls or a look up table could work, but it complicates the process.

Some dictionaries might define a word two, three, or times, based on it being a noun, verb, adjective or abbreviation. This will reduce our total search space, which will reduce our entropy per word. So, in my example of 11.98-bits of entropy per word, this is a maximum. It may require a bit more work to determine a more accurate entropy estimate.

Variation 3- Coinware

Even carrying around dice can be impractical. However, it is much more likely that you are carrying around spare change in your pockets, or have some sitting in a desk drawer at work. Provided that the coin flips fairly between heads and tails, you can flip a coin to build your passphrase.

Preferably, you'll want to use 3 separate coins (penny, nickel, dime), but if you only have a single penny, or 3 pennies, that will work too. The idea is that you toss the three coins, which will identify a single throw of a die. So, 15 coin tosses will determine your 5 dice rolls. Using Coinware requires the following look up table:

    Results of Coin Toss
      Penny Nickel Dime
 
D  1    T     T     T
i  2    T     T     H
e  3    T     H     T
   4    T     H     H
R  5    H     T     T
o  6    H     T     H
l  *    H     H     T
l  *    H     H     H

If your coin tosses produce a "*", re-flip your coins. As such, to get the dice roll of "44311", I would have needed to get the following coin flips:

THH 4
THH 4
THT 3
TTT 1
TTT 1

This would produce my word "oint" from the Diceware word list. I would then need to proceed six more times to get my seven words necessary for reaching my 80-bits of entropy minimum. If you think that flipping 3 coins for 1 die roll is a lot of work, you're right. It is. You would be better off getting some dice.

Dice Considerations

I would be amiss if I didn't mention something about the randomness of dice itself. No doubt, dice can be loaded, imbalanced, burned, and/or lopsided to favor certain sides. For obvious reasons, you should avoid using "bad dice" when generating your Diceware passphrases. You want random to be on your side as much as possible (you want a "strong password", don't you?). Every side of each die should be equally as likely as the other five sides.

Unfortunately, "gaming dice" that you get from your local hobby store, or that come with board games, aren't fair 6-sided dice. But, they're probably "good enough". In other words, one die may favor a "4" due to imperfections in the die material, weighting it on the "3", while another die may favor a "6", because it has had more material drilled out of it than the "1". Finally, one die may have a more chamfered corner or edge than the rest of the corners or edges, slightly favoring a specific number or pair of numbers. Taking these imperfections, and the position the dice fall with respect to the others will probably give you enough randomness as to not be repeatable from throw-to-throw.

If you want to see if your dice favor numbers, get a tall cylinder, such as a large water bottle. Fill it with water, and drop in your die, then seal off the top. The die will sink to the bottom. Turn over the cylinder, let the die drop to the bottom, and record its number. You should do this at least 30 times for a decent sample size. In fact, the larger the sample size, the more accurate the results. Each number should come up 1/6 of the time, for that die. See Playing Fair with the Chi Square Test of Homogeneity for more information about testing fairness in dice.

However, there are "precision dice", or "casino quality dice" which are guaranteed to have each number equally as likely as the other six within a .0001 margin of error between any two numbers (in other words, if you threw the die 10,000 times, a favored number would come up 1 more time than another). If you live close to a casino, you can probably purchase used casino dice on the cheap. Even though the corners and edges will be slightly chamfered, thus beginning to show slight favoring in numbers, they are still likely more "fair" than your store-bought dice, and will probably continue to exhibit more fairness in each throw for a good long while.

If you search for "precision casino dice", you will find some listings on Amazon, eBay, and other locations. Most of these dice have razor edges and corners, meaning they are not rounded, and the corners are sharp. As such, the dice don't "roll" as well as dice purchased from a hobby store. They tend to land with a solid fall on the number. This also means they won't roll off your table when throwing them. Many of these dice will be transparent, so you can see the pip depth, and will also have a serial number printed on the die if purchased in a set. These dice are more expensive, but they will be the best choice in choosing fair 6-sided dice.

Rix Dice are precision machined metal dice, with chamfered corners and edges for better rolling. They'll last longer than acrylic or plastic dice, and the creator, Amber Rix, has paid attention to the dice being fair. They might be a consideration, if you plan on rolling them a lot. They are the most expensive precision dice I've come across, but probably the most durable too.

Conclusion

Diceware, and it's variants, can be a secure way for generating strong passwords that would withstand even the most sophisticated offline attacks on a hashed password database (which is the real threat). If you pay attention to entropy and randomization, then you'll create strong passwords that we qualified at the beginning of this post. As such, even the most powerful brute force searches on a hashed database, won't reveal your password. And Diceware makes it easy to remember your password, using only lowercase letters.

Creating Strong Passwords Without A Computer, Part 0 - Understanding Entropy

I've written a new series that investigates the art of creating very strong passwords without the aid of a computer. Sure, there are many software applications that will generate strong passwords for you, each with their own advantages and disadvantages. They're so plentiful, that it would be impossible to outline them all. However, generating passwords without the aid of a computer can be a very challenging, yet very rewarding process. It may even be impractical or impossible for you to install software on the computer you're using at the moment, when you need to generate a password.

Introduction

Before we start diving into passwords, we need to define what a "strong password" is. I've defined this many times on this blog, and as long as I keep blogging about passwords, I'll continue to define it. A "strong password" is one that is defined by entropy. The more the entropy, the stronger the password. Further, a "strong password" is one that is defined by true randomness, which means it was not influenced by a human being during the creation.

We're told that passwords must have the following characteristics when creating them:

  • Passwords should be long.
  • Passwords should contain both uppercase and lowercase letters.
  • Passwords should contain digits.
  • Passwords should contain special punctuation characters.
  • Passwords should be unique for every account.
  • Passwords should be easy to remember.
  • Passwords should not be written down.
  • Passwords should not be based on dictionary words.
  • Passwords should not contain birthdates, anniversaries, other other personally identifiable information.

These rules can be difficult, because remembering all these rules make passwords difficult to remember, especially if you have a unique password for every account. It's almost like creating a witches brew, just so you can create the perfect password potion:

Double, double toil and trouble;
Fire burn and cauldron bubble.
Fillet of a fenny snake,
In the cauldron boil and bake;
Eye of newt, and toe of frog,
Wool of bat, and tongue of dog,
Adder’s fork, and blind-worm’s sting,
Lizard’s leg, and howlet’s wing,
For a charm of powerful trouble,
Like a hell-broth boil and bubble.

Personally, I find it all a bit confusing, and even more annoying that security-conscious blogs endorse that garbage. I tend to keep things much more simple:

  • A password must contain great amounts of entropy (we'll quantify this in a minute).
  • A password must be truly random (no human interference).

So, what is entropy, and how do we quantify it? Let's begin.

Defining Entropy

Entropy can be found in many fields of study. Abstractly, entropy is defined as:

1. a thermodynamic quantity representing the unavailability of a system's thermal energy for conversion into mechanical work, often interpreted as the degree of disorder or randomness in the system.
2. lack of order or predictability; gradual decline into disorder. "a marketplace where entropy reigns supreme".

So entropy is a measure of disorder, or unpredictability. For our needs, we'll use entropy from Claude Shannon's Information Theory, a branch of Mathematics, which is defined mathematically as follows:

Definition of entropy.

where:

  • H = entropy in binary bits.
  • L = the number of symbols chosen for your message (length).
  • N = Total number of unique possibilities each symbol could be.

Or, if you would like to enter this on your calculator:

Entopy equation suitable for calculator entry.

This can be proven quite simply. First off, let us define the logarithm. As with standard mathematics, we'll define it as the inverse of the exponential function. In other words:

Definition of the logarithm.

Suppose we want to find the entropy size of of a 13-character password taking advantage of all 94 possible printable symbols on the ASCII keyboard. Then, if all 94 printable symbols are a valid choice for each of the 13 characters in my passphrase, then to find the total number of combinations that my password could be, we write it as:

logarithm2

Now, a property of logarithms is the ability to change base. Because entropy is defined in bits, or base-2, I'll change the base of my logarithm, as follows:

logarithm3

Rewritting the equation, we get the following result:

logarithm4

And thus, we've arrived at our conclusion.

This assumes that the message was chosen completely at random. However, if there is human intervention in creating the message, then the equation gets much more difficult. As such, for the point of this post, and most of my posts detailing entropy, we'll assume that the password or message was chosen completely at random.

Some Entropy Equation Examples

If you create a message from lowercase letters only, then the number of unique possibilities for each symbol is 26, as there are only 26 letters in the English alphabet. So, each character provides only 4.7 bits of entropy:

Entropy example equation 1.

If you created a message from lowercase letters, uppercase letters and digits, then the number of unique possibilities for each symbol is 62, as there are 26 unique lowercase letters, 26 unique uppercase letters, and 10 digits in the English language. So, each character would provide only 5.95 bits of entropy:

Entropy example equation 2.

A Needle In A Haystack

Knowing how much entropy is needed when creating a password can be tricky. Is 50-bits enough? Do I need 60-bits instead? 80-bits? 128? 256? More? In order to get a good firm grasp on quantifying entropy, I want to first create an analogy:

Entropy is to a haystack, as your password is to a needle.

Finding your password means searching through your entropy space. Your password should have a minimum amount of entropy. That means that the password will NOT be found in entropy spaces smaller than what your password is defined in. So if your haystack, or entropy, is 256-bits in size, your needle, or password, should not be found in 255-bit haystacks, or smaller.

To quantify this a bit, in a previous post, I demonstrated that a SHA1 hash has an output space of 61-bits due to cryptanalysis techniques, and it turns out that it was far too small. At the time of this writing, the bitcoin network is processing 2^61 SHA256 hashes every 76 seconds using specialized hardware called ASICs. The computing power is only going to grow also, as there is financial gain to be made from mining.

In other words, with these ASICs, 30 quadrillion pieces of hay can be analyzed every second. If your haystack has 2^61 pieces of hay, one of which is actually your needle, this haystack can be fully processed in 76 seconds flat.

How Entropy Relates To Passwords

If you continue using the same bitcoin network model for our speed benchmark, then at 30 quadrillion pieces of hay (passwords) every second, to completely exhaust the full output space, for the following haystack sizes, it would take:

  • 64-bits: 10 minutes.
  • 72-bits: 2 days.
  • 80-bits: 15 months.
  • 88-bits: 327 years.

In the past, I've shown that 72-bits of entropy (your haystack) seems to be sufficient for passwords (your needle) using the RSA 72-bit distributed computing project on distributed.net. After analyzing the bitcoin network mining operations, and how trivial it is to build specialized ASICs for these tasks, I'm beginning to think that you should have at least 80-bits of entropy for your passwords. As computing gets more and more stronger, that number will continue to increase.

As a result, to create a "strong password", I would recommend the following:

  • A password must contain at least 80-bits of entropy.
  • A password must be truly random.

Conclusion

Entropy is how we measure unpredictability. If we need any sort of unpredictability, such as finding passwords (needles in a haystack), then the more entropy we have, the better off we are. On computer systems, entropy is stored in what's called an "entropy pool". The larger the pool, the more reliably the operating system can generate true random numbers for security applications, such as GPG and long term SSL keys. The same can be said for passwords. The more entropy we have, the better off our passwords can become.

So, don't starve yourself by selecting weak 8-10 character passwords, and trying to generate random data in your head. Generate real random passwords and use large amounts of entropy.

The Reality of SHA1

Many people don't understand crypto. That's okay. I don't either. But, I do get math, and I want to show you something SIGNIFICANT that affects your everyday habits online.

It's been demonstrated that MD5 is broken. It's now trivial to find what are called "collisions". This is where two completely different inputs hash to the same output. Here is a demonstration: http://www.mscs.dal.ca/~selinger/md5collision/

SHA1 was meant to be a replacement for MD5. MD5 has an output space of only 128-bits, where as SHA1 has an output space of 160-bits. SHA1 is also designed differently than MD5, and is meant to not suffer the same sort of weaknesses or attacks that MD5 faces. However, over time, cryptographers have been able to severely attack SHA1, and as a result, they've all been warning us to get off SHA1, and move to SHA2. It should take 2^160 operations to find a collision with SHA1, however using the Birthday Paradox, we can have a probability of 50% of finding a SHA1 collision in about 2^80 operations. However, cryptanalysists have torn down SHA1 to a complexity of only 2^61 operations. Even better.

An output size of only 61-bits is small. For comparison sake, the distributed computing project http://distributed.net cracked the 64-bit RSA key in just over 5 years at a snails pace of 102 billion keys per second: http://stats.distributed.net/projects.php?project_id=5. The motivation was prompted by a $10,000 dollar award from RSA labratories to find the secret key encrypting a message.

Granted, you don't need to search the entire 64-bit keyspace to find the key. It's just as likely you'll find the key immediately at the start of your search, as it is to find the key at the end of your search. But it shows how reachable 64-bits is. The reduced search space of 61-bits from SHA1's attack vector is 8x smaller in search space than the 64-bits of that RSA secret key challenge. So, at 102 billion hashes per second, it's reasonable to conclude that you could exhaust the 61-bit search space somewhere between 6 and 9 months.

This is far too slow. Let's look at another comparison. Bitcoin.

First, Bitcoin uses SHA256 rather than SHA1 as part of its mining algorithms. According to http://blockchain.info/charts/hash-rate, the Bitcoin network is processing about 30 million gigahashes per second. That's 30 quadrillion hashes per second. The size of 61-bits is a mere 2.3 quintillion hashes. Let's do some math:

2.3 quintillion hashes divided by 30 quadrillion hashes per second = 76 seconds.

What does this mean? The Bitcoin network is currently working over 2^61 SHA256 hashes every minute and 16 seconds. If this were SHA1, we could brute force 1,150 SHA1 collisions every day.

Why should you care? Because when you connect to a server with SSH, SHA1 is likely presented as the hash. When you use your browser to connect to an HTTPS site using SSL, SHA1 is lkely presented as the hash. When you encrypt something with OpenPGP, or cryptographically sign a key or document, SHA1 is likely presented as the hash.

It's the case that most of your encrypted communication online is using SHA1 in one way or another. And yet, it's well within our reach to process 1,150 SHA1 collisions EVERY. SINGLE. DAY. It's long over due that we replace SHA1 with SHA2 or SHA3. Not because some theoretical proof says so, but because we can actually do it.

SCALE 12x PGP Keysigning Party

This year, at SCALE 12x, I'll be hosting the PGP keysigning party. What is a keysigning party, and why should you attend? Maybe this will clear things up.

What is a keysigning party?

A PGP keysigning party is an event where PGP users meet together to exchange identity information and PGP fingerprints. Typically, at a conference such as SCALE 12x, PGP parties are common. The whole idea of the party is to expand the global "Web of Trust". In reality, however, you attend a keysigning party, because you share interests in cryptography, or you are interested in communicating privately with others. Usually, you can expect 10-20 people to attend keysigning parties at Linux conferences, sometimes more, sometimes less.

What is the Web of Trust?

The Web of Trust is just a logical mapping of exchanged identities. When at the keysigning party, you will exchange photo identification with each other as wall as PGP fingerprints. You do this for two reasons, and two reasons only: to verify that you have the correct key and to verify that the owner of that key is who they say they are. That's it. When you leave the party, you will sign every key that you have personally identified. By doing so, you bring that key into your own personal Web of Trust. An arrow from you to them indicates that you have signed their key. If they return the favor, and sign your key, then a return arrow from them to you will result.

It's not too difficult to create a personal Web of Trust that you can view. I have blogged about it in the past at https://pthree.org/2013/03/01/create-your-own-graphical-web-of-trust-updated/. It's interesting to see the large groupings of signatures. It's clear that there was a PGP keysigning party in those large groups.

What do I bring to a keysigning party?

You really only need three things with you when you come to the party:

  1. Something to write with, like a pen or pencil.
  2. A government issued photo identification at a minimum. Additional identification is appreciated.
  3. Your own printout of your PGP key fingerprint

That last item is important. Very important. If you didn't bring item #3, then most PGP keysigning party organizers will not allow you to participate. In order to printout your PGP key fingerprint, run the following command at your terminal:

$ gpg -K --fingerprint

Print that out on a piece of paper, and bring it with you to the party. Some conferences, such as SCALE 12x, will print your PGP fingerprint on your conference badge. This will allow you to sign keys anywhere anytime. All you need to do is verify that the fingerprint on your personal printout matches the fingerprint on the conference badge. Then you may use your conference badge fingerprint at the party.

It's important that you bring your own copy of your PGP key fingerprint, however. The keysigning party organizer will handout a printout of all the PGP key fingerprints for everyone in attendance. This is to verify that the organizer downloaded your correct and current key(s). You will read off your fingerprint from your personal printout, and everyone else will verify the fingerprint on their printout.

What happens before the party?

All that needs to be done, is every attendant must submit their public PGP key to the party organizer. Typically, there is a deadline on when keys can be submitted. It's important that you adhere to that deadline. The party organize then prints out on paper a list of every PGP key fingerprint of those who are attending. If you submit your key late, it will not be on the paper, and as such, many party orgasizers will not let you participate.

What happens at the party?

The key party organizer will pass out sheets of paper with every PGP key fingerprint that has been submitted. Typically, party organizers will also explain the importance of the party, why cryptography, and other things related to crypto. Then, he will explain how the party will proceed, at which point every attendee will read their PGP key fingerprint from their own printout. Everyone else in attendance will verify that the organizer has the correct key by following along on the handout. This is done for everyone in attendance.

After fingerprints have been verified, we then get into two equal lines, facing each other. While facing someone in the line opposite if you, you introduce yourself, explain where your key is on the handout, and exchange government issued identification. After identification has been exchanged, everyone in both lines takes 1/2 step to their right. This will put you in front of a new person to repeat the process. Those at the ends turn around, facing the opposite direction, and continue shuffling to their right. Think of the whole process as one large conveyor belt.

Once you are facing the person you started with, then everyone should have successfully verified everyone else's identity and key. At this point, the party is typically over.

What happens after the party?

This is the most critical step of the whole process, and for some reason, not everyone does it. Now that you have your handout with all the keys printed on it, you need to sign every key that you have personally identified. What you attended was a KEYSIGNING party. This means that you must SIGN KEYS. I know I'm putting a lot of emphasis on this, but I have personally attended close to a dozen PGP keysigning parties, and I would say the rate of signing keys is about 70%, unless I annoy them week in and week out to sign my key, then I'll get a return close to 90%. It blows my mind that people spent a great amount of time at the PGP keysigning party, then don't actually do anything about it.

There are a lot of utilities out there for keysigning party events that make attempts at making the whole process easier. In all reality, the only "difficult" or troublesome part about it is, is converting the fingerprints you have on paper to your computer. Some PGP keysigning organizers will already have a party public keyring, that they will email to those who attended, with only the keys of those that attended. If that's the case, you have it easy. Otherwise, you must do something like the following:

$ gpg --recv-keys 0x<KEYID>

Where "<KEYID>" is the last 16 characters of the person's fingerprint. After you have their public key, then you can sign it with the following command for each key:

$ gpg --default-cert-level 3 --sign-key 0x<KEYID>

It's important that you add the "--default-cert-level 3" as part of the signing process. This certification level says that you have done very careful checking, and you are 100% confident that the key in question belongs to the owner, and that you have personally verified the owner's identity.

After you have signed the key, it is courtesy to email them their public key with your signature. As such, you will need to export their key from your public keyring. You should do this for each key:

$ gpg --armor --output /tmp/0x<KEYID>.asc --export 0x<KEYID>

Attach "/tmp/0x<KEYID>.asc" to your encrypted email, and send it off.

Additional Information

  • Should I bring a computer to the keysigning party? No. It's not necessary, and many party organizers consider it a security liability. Things like swapping around USB sticks could infect viruses or other badware. If secret keys are on the computer, it's possible they could be compromised. Even worse, the physical computer itself could get damaged. It's generally best to just leave the computer in your backback or hotel room, and attend the party without it.
  • Why should I care about signing PGP keys? Have you ever stopped to think about certificate authorities? When you create an SSL certificate signing request, you ship the CSR off to the CA, along with $200, and they returned a signed key. You then install your key on your web server, and browsers automatically trust data encrypted with it. All because you paid someone money. PGP keys do not have a centralized authority. As such, signing keys is done in an ad hoc manner. Further, money is not exchanged when signing keys. Instead, signing keys is done in person, with face-to-face contact. When you sign a key, you are ultimately saying that you have verified the owner is who they claim to be, and that the key you just signed belongs to them. As a result, a decentralized Web of Trust is built.
  • What is the Web of Trust really? The PGP Web of Trust is a decentralized web of connected keys, where the connection is made by cryptographically signing keys. The larger and more connected the Web of Trust is, the stronger the trust becomes for people to send private data to each other within that web. It sounds all geeky and mathematical, but if you just sit back and think about it, it makes sense. No money is involved, like using CAs. No blind trust is involved, such as the behavior of browsers. It's you and me, meeting face-to-face, claiming we are who we say we are, and claiming we own the key we have. Now, after this meeting, I can rest assured that if you send me cryptographically signed data from your key, I know it came from you, and no one else. If you send me encrypted data, I have a copy of your public key, and can decrypt it knowing that you were the one encrypting it. The Web of Trust is just that- establishing trust.
  • What is the PGP Strong Set? The largest and most connected Web of Trust is called the PGP Strong Set. There are more keys in this Web of Trust than any other. The way you get into the PGP Strong Set is by having someone in the Strong Set sign your key. A great deal of analysis has been done on the Strong Set. You can read about that analysis at http://pgp.cs.uu.nl/plot/. You can get key statistics such as mean signature distance (MSD), and calculate the distance from one key in the strong set to another key, such as yours that may not be in the strong set. My key, 0x8086060F is in the Strong Set. If ever I am at a keysigning party, and I sign your key, your key will also be included in the Strong Set.

Announcing d-note: A Self Destructing Notes Application

I'm pleased to announce something I've been working on, on and off, for over a year. Introducing d-note, a self hosted web application with self destructing notes. d-note is written in Python using the Flask web framework.

d-note comes from the idea that sending private information across the Internet can be very insecure. Ask yourself- how often you've sent usernames and passwords in chat or email, either across the global Internet, or even inside of your work's Intranet? Maybe you've sent PINs, SSNs, credit cards, or other sensitive information too. Or maybe you haven't, but someone you know has.

d-note aims to solve this problem. With d-note, notes are compressed and encrypted with Blowfish on disk, using either a shared key stored on the server, or a private key which is not stored. When a note is created, the sender is given a random URL which will link to the note. That URL can only be viewed once, and when viewed, it is immediately destroyed on the server. If you try to visit the note again, because it doesn't exist, a standard 404 error will be raised.

Here are the current features in this release:

  • Data is compressed with zlib, then encrypted with Blowfish. Never at any point is the note in plaintext on the filesystem.
  • Form submission is protected by the browser minting a Hashcash token. This will prevent form spam, and POST denial of service attacks. As such, JavaScript must be enabled.
  • The note can be encrypted with a separate private key. This private key must be securely communicated to the recipient, so they may decrypt the note. The private key is not stored on the server.
  • The note can also be protected with a duress key, in case someone is trying to coerce the decryption key out of you. The duress key will immediately and silently destroy the note, without decrypting it, and redirect the browser to a standard 404 error.
  • Notes are destroyed immediately upon viewing. They are destroyed by securely overwriting the note with random data before removing it from the underlying filesystem.
  • Notes can be shared with mobile devices, by scanning a QR code. This allows you to share the note via SMS, email, instant message, or some other application installed on your mobile device.
  • Unread notes are automatically and securely destroyed after 30 days.
  • d-note tries its best at preventing the browser from caching the session. With that said, the back button is still functional.

Because the application uses Hashcash to protect the submission form, JavaScript must be enabled to post a note. Don't worry, there is no identifying or tracking software in the default source code. Further, it may take your browser a few seconds to mint a valid token, before the form is submitted (it may even take longer if using a mobile device to create the note).

Due to the nature of this application, some best practices and precautions should be made:

  • The web application MUST be served over HTTPS.
  • The server administrator hosting the d-note application could have modified the source code to store private keys, or even the notes in plaintext. As such, don't put all of your eggs in one basket. Give the usernames over one channel, and use d-note for the passwords, or vice versa. Even better, host this on your own web server, where you have full control.
  • Storing the encrypted notes in a ramdisk would be the most secure. However, if the web server stops, unread notes will be lost.

There are still some things that need to be done, such as improving the overall look and feel with much needed CSS, and making the site a bit more dynamic with JavaScript. I'm also debating on creating account support, so you can view which notes you've created, and which ones have not been read. In the long term, I'd like to create an API, so you can create notes from other sources, such as the command line, or mobile device apps.

However, for the time being, it works, it's feature complete (for a 0.1 release), and it's mostly bug free. If you would like to try a demo of d-note, you can visit https://ae7.st/d/. It's currently using a self-signed certificate. As such, to verify you have the right server, the certificate fingerprints are:

MD5 Fingerprint=5A:E1:4E:B6:31:B8:3D:69:B1:D6:C0:A7:6B:46:FE:67
SHA1 Fingerprint=55:89:CD:C0:D4:85:CC:A5:DE:30:11:5D:9C:C9:12:1C:5C:9D:10:C5
SHA256 Fingerprint=12:91:BB:4C:E8:2F:1C:0C:D9:96:AF:4E:1D:8C:F7:B0:A8:07:70:C5:9C:89:B8:94:EE:E2:2A:D6:19:43:17:A4

The Drunken Bishop Cipher Is Weak

Well, it turns out that my own hand cipher is incredibly weak. When I initially started designing it, using a chessboard felt a lot like an S-box lookup. There has been a great deal of research into S-boxes since the release of DES, and many ciphers today use them. What plagued me from day one, and I should have listened to my own intuition, is my chessboard key remains static throughout the entire operation. Unlike the Solitaire Cipher, by Bruce Schneier, where the cards in the deck are dynamically changing all the time. To get an idea of S-boxes, check out this AES animation (flash), which I think describes AES very well.

With ciphers, you need an ingredient of non-linearity in the system. Otherwise, your cipher can fall victim to linear cryptanalysis. Initially, I had thought, incorrectly I might add, that by using the ciphertext as the starting direction of the bishop's walk, I was introducing the non-linearity that I needed. Turns out this isn't the case. Let's use my board from my initial announcement, and the trivial example of "AAAAAAAAAAAAAAA" as my plaintext. Here's my board:

cipher-board-random

As per the algorithm, the bishop starts in "a1", which is valued at "38". Converted to binary, this gives us "100110", which means his travel is "SW" (no move), "NE", then finally "SW". He's back in the corner from which he started. Okay. No problem. Let's continue with the cipher then. Let's setup our worksheet. The character "A" as the value of "0", so my plaintext is:

  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
+38
 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
 38

Now we take our ciphertext, 38, and use this as the start of our next bishop walk. As you can immediately see, we have a problem. He stays stuck in the corner, and we get the following result:

  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
+38 38 38 38 38 38 38 38 38 38 38 38 38 38 38
 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38

Our ciphertext is thus "mmmmm mmmmm mmmmm". While this may not seem like a practical example, it draws up a very real problem: this cipher is subject to a chosen plaintext attack. And, despite my best efforts to ensure that there are no repeated rounds in the cipher, here's a trivial example that shows they still exist. As such, the cipher is terribly linear.

The BIG PROBLEM with this cipher, and one that was hanging over my head the entire time I was designing it, is that the board key remains static. However, all is not over. Ultimately, the board is just an 8x8 matrix. As such, we should be able to do some matrix operations, such as multiplicitive inverses, exclusive OR, addition, subtraction, and so forth. This might be a major problem when writing the board down on a piece of paper, but this is trivial for a calculator, such as the HP-48 to do. But then we lose the allure of using a pure hand cipher, as we begin relying on computing tools to manage the internal state of the system. At this point, why not just use a typical computer, and use a cipher that has been tried and true, such as AES?

I must admit that I was sloppy when designing the cipher. I didn't take my abstract algebra and linear algebra into account. I should have looked at the math when initially designing it. Peter Maxwell, on the Cryptography Discussion mailing list, pointed out the following:

If you view the moving-the-bishop as an s-box lookup, and apply it to itself three times (composition), you end up with another s-box of the same size, lets call it S. Given S doesn't change, things should be rather easy indeed. If your cipher is then roughly akin to C[n] = P[n] + S[ C[n-1] ] with all operations taken modulo 2^6 the problem should now be a little more obvious.

Indeed. Basically, the cipher is weak due to two inherent problems with the system:

  1. The internal state of the system is static.
  2. The cipher does not contain a non-linear component.

I really want to use a chessboard for a cipher. I think it would be a fantastic tool that you could basically hide in plain sight. But, given the initial design of this cipher, and how weak it really is, it just doesn't work. The drunken bishop may make pretty ASCII art pictures for SSH server keys, but when in comes to cryptography, it's had just too much wine to be practical.

I'll hang this one up as a learning exercise, and move on. Designing hand ciphers is much more difficult than I had initially thought.

The Drunken Bishop Cipher

Background

Ever since learning Bruce Schneier's Solitaire Cipher, I was interested in creating a hand cipher of my own. Unfortunately, I'm just an amateur cryptographer, and a lousy one at that. So I didn't have any confidence in creating my own hand cipher. However, after learning about the SSH ASCII art, and the drunken bishop, I was confident that I could turn this into a hand cipher. So, that's exactly what I did.

Even though this is technically a hand cipher, and I've done my best to address some of the shortcomings internal to the system, I am not a genius mathematician. So, I can look at some of the numbers specifically, and give a broad sense of what the shortcomings might be, but I have not invested into a full scale cryptanalysis of the cipher. If someone stumbles upon this post, and is interested in launching such an attack, I would be interested in your feedback.

This post is lengthy, so I'll separate everything with <h2> headers for easier visibility (a standard with my blog posts lately, it seems).

Cipher Design Overview

All that is needed is a standard 8x8 checker or chess board, and a marker, such as the bishop chess piece, or a checker, to make its way around the board. Each square on the board will be assigned a unique value from 0 through 63. The board should be assigned randomly, as this choice of number assignments is your key to encrypting and decrypting messages. However, at the end of this post, I'll give a few ideas on how you can key the board reliably without the need to communicate a random board.

This cipher is a stream cipher. As with all stream ciphers, the output of n depends entirely on the accuracy of n-1. If n-1 is incorrect, then the rest of the process will be incorrect, and encrypting the plaintext from that point forward will be incorrect, which means decryption will not be possible. Thankfully, the board number assignments are static, so it shouldn't be difficult to double check your work, unlike the Solitaire Cipher, which requires keeping a backup copy of your keyed deck.

Because there are 64 squares on the board, this allows us to use a base64 system for encryption and decryption. As such, we can use uppercase letters, lowercase letters, and digits. This will provide 62 of the characters. So, we can throw in white space, and padding at the end of the message, giving us our full 64 characters. One drawback with most hand ciphers is the lack of numbers support in the message. Either you have to spell out the numbers, lengthening the message, and as a result the time to encrypt and decrypt it, or you need to truncate them out, possibly creating confusion for the person decrypting the message. By having uppercase and lowercase letter support, we can now differentiate between proper names and not.

The Board

First, you must arrange the chess board such that square "a1" is in the lower left corner, as would be standard in a tournament chess match. This square should be black. Instead of referring to this corner as "a1", we'll refer to it as the "southwest corner", or just "SW". The other three corners on the board will be identified analogously: the lower right corner, or "h1" will be identified as the "southeast corner, or just "SE". The upper left corner, or "a8" will be identified as the "northwest corner", or "NW". Finally, the upper right corner, or "h8" will be identified as the "northeast corner", or just "NE".

Now that we've identified the corners, we need to identify the edges of the board that are not a corner. On the bottom of the board, we'll identify this as edge "B", and the top of the board as edge "T". The left edge of the board will be identified as edge "L", and the right of the board as edge "R". Every additional square that is not identified as an edge or a corner will be identified as a middle or "M".

After making these identifications, our board should have the following layout:

A standard chess board with our identifying markers SW, SE, NW, NE, B, T, L, R and M on every square.

The Bishop's Movement

As in standard chess, the bishop may only move diagonal across the board. In standard chess, if the bishop is on a black square, then he will remain on the black square throughout game play. Our bishop is drunk, unfortunately. So, when our bishop encounters an edge; specifically, "B", "T", "L", or "R", then it's possible our bishop might switch space color from black to white, or from white to black. Any other time, our bishop is always moving diagonal as he would normally.

So, we need to accommodate for when our bishop hits the wall or a corner, and still wishes to move. Let's look at the bottom edge first. Suppose our bishop traveled to square "e1" which has the value of "44" in our key. If the bishop wishes to move either diagonally NE or NW, that move in unrestricted. However, if the bishop wishes to move SW from square "e1", then it would step onto the white square "d1". If the bishop wishes to move SE from square "e1", then it would step onto the white square "f1". Similar rules hold for the other three edges. In summary then:

  • If at "B", and wishes to move SW, then the new square is (n-1,1).
  • If at "B", and wishes to move SE, then the new square is (n+1,1).
  • If at "T", and wishes to move NW, then the new square is (n-1,8).
  • If at "T", and wishes to move NE, then the new square is (n+1,8).
  • If at "L", and wishes to move NW, then the new square is (a,n+1).
  • If at "L", and wishes to move SW, then the new square is (a,n-1).
  • If at "R", and wishes to move NE, then the new square is (h,n+1).
  • If at "R", and wishes to move SE, then the new square is (h,n-1).

If any additional movement is needed from an edge, then this means the bishop wishes to move away from the edge towards the middle of the board, and as such, it would do so in a standard diagonal manner, staying on its same color.

Now that we've handled the four edges of the board, we need to handle the four corners. The movement is analogous to the edges, except for one move:

  • If at "SW", and wishes to move SW, no movement is made.
  • If at "SE", and wishes to move SE, no movement is made.
  • If at "NW", and wishes to move NW, no movement is made.
  • If at "NE", and wishes to move NE, no movement is made.

If in the corner, and any other movement needs to be made, then use the previous edge rules.

Knowing these rules, we can now describe where our drunk bishop moves when he lands on any square on the board. Now, we just need to generate a random board, which will determine the bishop's movement. When generating a random board, all 64 numbers from 0 through 63 must be assigned to a square. Each chessboard key is one of 64 factorial, or about the same size as a 296-bit symmetric key. Below is one such board that could be generated:

A standard chess board with the numbers 0 through 63 assigned randomly to all the squares, one number per square. In this example,the SW corner was assigned 38, SE was assigned 32, NW was assigned 42, and NE was assigned 57. Further, the bottom edge was assigned the numbers 4, 30, 52, 44, 8, 36, and 32. The top edge was assigned 58, 27, 12, 15, 53, 7, and 57. The left edge was assigned 6, 55, 45, 26, 50, 62, and 38. The right edge was assigned 47, 46, 14, 37, 19, and 11. The middle squares were assigned randomly with the remaining numbers.
.

Generating the stream

Because the board is now a static key, and doesn't change like the cards in the Solitaire Cipher, there is the possibility that the bishop could land on the same square at the end of the algorithm that he did at the start of the algorithm. As such, from that point forward, the same number would be generated in our stream, and our message would fall victim to a frequency analysis attack. If this doesn't happen, it is still possible that the bishop could land on a square at the end of his drunken walk that we've landed on before. This means our bishop will be caught in an infinite loop, generating the same sequence of numbers.

To accommodate for both of these shortcomings, rather than use the number he is on for the start of his next walk, we will use the addition of the plaintext number and the stream number to produce an output number. This output number will determine the beginnings of his next walk.

Each character in the plaintext will be given a value according to section 3 of RFC 3548. The only adjustments that will be made, is whitespace will be filled with the forward slash "/", and we will both pad the message modulo 5, as is standard with hand ciphers, and replace the full stop period with the plus character "+" at the end. The other punctuation and special characters must be stripped from the plaintext, as our base64 system cannot handle them.

So, our plaintext message "Attack at dawn." would be converted to "Attack/at/dawn+" before we begin encrypting.

The Four Movements

The bishop always starts on the SW square, or "a1" at the beginning of each message. In order to know which way to travel, each square on the board describes three movements. This is done by converting the decimal number into binary, zero padded up to 6 bits wide. As such, the decimal number "0" will be the binary number "000000". The decimal number 38 will be the binary number "100110", and so forth. We'll call our 6-bit binary number a "word" for this cipher, even though in computer science, you learn that a binary word is 8 bits. We'll take our binary word, and divide it into 3 sections: the first two bits, the middle two bits, and the last two bits.

So, for the case of "38", the binary word divided up would be "10" for the first two bits, "01" for the middle two bits, and "10" for the last two bits. There are four combinations that each of these bit pairs could be: "00", "01", "10", or "11". Because the bishop can move diagonally in one of four directions, each of these bit pairs describes the direction for each of his 3 moves. We will describe our movements as follows:

  • 00- NW
  • 01- NE
  • 10- SW
  • 11- SE

So for the number "38", where our bishop starts in our random key that we chose earlier, the bishop would move "10" or SW, which would mean no movement, "01" or NE to square "b2", and finally "10" or SW, back to "a1". So, already we see that we have an inherent problem with the system, in that starting with "38" prevents the bishop from moving around the board. However, we'll add this to our plaintext number, and use our output number as the direction for the next walk. So, we won't be stuck for long.

The Drunken Bishop Algorithm

The algorithm is defined with the following steps:

  1. Convert the previous output number to binary, and move the the bishop three spaces as described above based on this output number.
  2. Convert the number of the square the bishop landed on to binary, and again move the bishop three spaces as based on this number.
  3. Convert the number of the square the bishop landed on to binary, and again move the bishop three spaces as based on this number.
  4. The bishop should have made a total of 9 movements. Note the number the bishop has landed on. This is your stream number.
  5. Add the stream number to the plaintext number and to the index number modulo 64. This is your output number.

Repeat the algorithm as necessary until you have generated all the output numbers to encrypt your message. To decrypt the message, follow the same algorithm above, but instead of addition modulo 64, use subtraction modulo64 to get back to the plaintext.

Encryption Example

For simplicity sake, we will use the chessboard key generated above, and we will encrypt "We confirm the delivery of 4 packages.". First, let's pad it modulo 5. We end up with "We confirm the delivery of 4 packages.++". Now convert all full stop periods to "+" and all spaces to "/". We now have:

We/confirm/the/delivery/of/4/packages+++

Now me must convert each character to their decimal equivalent as found in RFC 3548, section 3. Thus, we end up with the numbers "22 30 63 28 40 39 31 34 43 38 63 45 33 30 63 29 30 37 34 47 30 43 50 63 40 31 63 56 63 41 26 28 36 26 32 30 44 62 62 62". Before the bishop starts the drunken walk around the board, let's setup a workspace, so it will be easy to do our modulo 64 addition. The top line will contain my plaintext numbers, the second line will contain our stream number. Both of these numbers will be added modulo 64 to produce our output number. I will be zero padding the decimal numbers as necessary:

  22 30 63 28 40 39 31 34 43 38 63 45 33 30 63 29 30 37 34 47 30 43 50 63 40 31 63 56 63 41 26 28 36 26 32 30 44 62 62 62
+ 
  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Now our bishop is ready to take his random walk across the board. Let's use our key above, so you can follow along. Our bishop always starts at square SW or "a1". This has a value of "38" which is "100110" in binary. So, the bishop moves "SW", "NE", "SW", placing him back on the same square. We do this two more times, and our bishop has not moved. So, we write the number down as our stream number, and add it to 22 modulo 64:

  22 30 63 28 40 39 31 34 43 38 63 45 33 30 63 29 30 37 34 47 30 43 50 63 40 31 63 56 63 41 26 28 36 26 32 30 44 62 62 62
+ 38
  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
  60

Our output number is 60, so we convert this to binary, and get "111100". So, the bishop moves "SE", "SE", "NW", placing him on square "b2" with a value of "35". We now convert 35 to binary, and get "100011". So, the bishop now moves "SW", "NW", "SE", placing him on square "a2" with a value of "04". We now convert 04 to binary, and get "000100". So, our bishop make the final move of "NW", "NE", "NW", placing him on square "d1" with a value of "26". We write down 26 in our worksheet, add to to 30 modulo 64, to get our output number of "56":

  22 30 63 28 40 39 31 34 43 38 63 45 33 30 63 29 30 37 34 47 30 43 50 63 40 31 63 56 63 41 26 28 36 26 32 30 44 62 62 62
+ 38 26
  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
  60 56

Now we convert 56 to binary, and get "111000", and work our way through the algorithm getting our third output number. We continue in like fashion until our worksheet is complete:

  22 30 63 28 40 39 31 34 43 38 63 45 33 30 63 29 30 37 34 47 30 43 50 63 40 31 63 56 63 41 26 28 36 26 32 30 44 62 62 62 <--- plaintext
+ 38 26 04 26 09 31 14 13 59 41 59 41 46 14 13 14 13 35  4 38 31 14 13 59 41 13 35 38 50 39  6 48 16 14 27 31 14 59 56 59 <--- final bishop square
  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
  60 56 03 54 49 06 45 47 38 15 58 22 15 44 12 43 13  8 38 21 61 57 63 58 17 44 34 30 49 16 32 12 52 40 59 61 58 57 54 57 <--- output number

Which in turn gives us the ciphertext:

84D2x GtvmP 6WPsM rrImV 94/6R siexQ gM0q7 96525

Decryption Example

To decrypt our ciphertext from above, we must first convert the characters back to their RFC 3548 values. We'll refer to this number as our "input number". Our bishop will start in the SW corner, or square "a1" as he did for our encryption example. Also, like with did with encryption, we'll convert the "a1" number to binary for the first walk. After that, we'll use the ciphertext input numbers to determine his path. Lastly, we need to subtract modulo 64, rather than add, to reverse our work.

So, as we did with our encryption example, let's setup our workspace:

  60 56 03 54 49 06 45 47 38 15 58 22 15 44 12 43 13  8 38 21 61 57 63 58 17 44 34 30 49 16 32 12 52 40 59 61 58 57 54 57 <--- ciphertext number
- 38                                                                                                                      <--- final bishop square
  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
  22                                                                                                                      <--- plaintext

Now convert "56" to binary, and have it do it's walk, 3 times, just like you would for encryption. You'll find that it ends up on square value "26". Subtract this value from our 2nd ciphertext number, to get back to our plaintext value of "30". Continue in a like manner, converting the ciphertext number to binary, starting the walk, doing two more binary conversions, to land on the right square. Subtract that number modulo 64, and you'll uncover your plaintext.

Observations

You may have noticed that you are always using the ciphertext number, either when encrypting, or decrypting, to start the bishop's initial walk. After which, the bishop makes two more walks around the board, based on the number he landed on. Because we are using the ciphertext number for the initial walk, we need to lengthen his path for a few reasons:

  1. When decrypting, the additional walks places the bishop elsewhere in the board, preventing any knowledge of the key.
  2. When both encrypting and decrypting, the 3 walks make it possible for the bishop to reach any number on the board, regardless of his location. This prevents our cipher from being focused on a set of squares based on his initial location.
  3. By using the ciphertext to start the initial walk, we prevent the possibility of the bishop from getting stuck walking in a circle. A simple example is with the number "38" in the SW corner, that would normally prevent him from making any movement on the board. IE: his ending the location is the same as his starting location.

Setting up an 8x8 key grid might be difficult. Certainly not much more difficult than keying a 52-card deck randomly. There may be creative ways to key the board, such as using previously played chess games, using passphrases, or some other method. I haven't had time to think about those yet. If you have good ideas, I'm very interested. At the moment, the best way to key the board, is to use a computer to randomly create a board assignment, and securely communicate the random assignment to your recipient.

This cipher is a stream cipher, as already mentioned. As such, it is absolutely critical that you get every movement of the bishop right, and that your mathematics is exact. If you make a mistake, and continue encrypting the message after the mistake, the ciphertext may not be decipherable to plaintext. Double check your movements.

Further, as with all symmetric ciphers, DO NOT USE THE SAME KEY TWICE. If the same key is used for two different messages, say C1 and C2, it's simple mathematics to extract the key. Think of it like this:

(A+K) = C1
(B+K) = C2
C1-C2 = (A+K)-(B+K) = A+K-B-K = A-B+K-K = A-B

In other words, using the same key, reveals the plaintext messages. This might not be trivial for you to pull off, but it is for a serious cryptographer. Don't share the key across messages. Just generate a new key every time you wish to encrypt.

Lastly, I have found this cipher a bit faster to encrypt and decrypt messages than the solitaire cipher, but I make no guarantees to its strength. However, this is real cryptography. Not stenography or obscurity. This cipher is a pseudo random number generator, that you apply to your plaintext to produce a random output. I still have work to do to, such as frequency analysis, and discovering if any bias exists, but upon initial inspection, it seems to hold up well. As with all cryptography, however, only time will tell.

Drunken Bishop Cipher Recommendations

  1. Although a chess board can be use, it's not required. If you can draw an 8x8 grid on a piece of paper, populated with the random key, then you are ready to start encrypting and decrypting.
  2. Never share a key when encrypting messages. Always use a different key.
  3. Use a number 2 pencil, and not ink, when doing your work. Ink bleeds, and can leave traces of your message or work.
  4. Use ungummed cigarette paper when actually doing your work. They burn completely, but slowly.
  5. Do as much of the work in your head as possible, and no not write on impressionable surfaces, such as a pad of paper.
  6. Work with a candle or a lighter. If someone breaks in while you are encrypting or decrypting messages, calmly burn the papers containing your work.
  7. Assume that Big Brother is aware that you are using the Drunken Bishop to encrypt and decrypt your messages. The secret lies in the 8x8 grid key, not in the algorithm. Of course, this doesn't mean you need to advertise that you are using the Drunken Bishop either. The ciphertext should appear as random as possible, with no obvious clues as to how it was created.
  8. Practice makes perfect. After practicing the Drunken Bishop, you should be able to immediately convert a number from 0 through 63 to binary without any external tools. This will speed things up.
  9. Which reminds me, the Drunken Bishop is slow, although not as slow as Solitaire. It will probably take you about 30 seconds per character. Keep that in mind; you may need a quiet, secure place with several hours. However, you shouldn't have cramped hands while working the Drunken Bishop, like you get with Solitaire.

Disclaimer

I am not a professional cryptographer. I study cryptography as a hobby. As such, I do not make any guarantees about the security of this cipher. However, I have studied RC4, as well as stream ciphers in general, and have a thorough understanding of the "big picture" as to what the internals of the cipher should be doing. The Drunken Bishop does its best to follow these practices. I graduated with a degree in Applied Mathematics, and have taken and studied Number Theory, as applied to cryptography.

I have not done any cryptanalysis on this cipher yet. My next goal is to write a Python program that can read a generated 8x8 key, read a text file, and encrypt and decrypt it. Only then will I be able to get more insight into the output that the Drunken Bishop provides, such as biases or other internal problems that I have not addressed. If you go ahead and write a utility to do this testing, and find some interesting results, I would be interested in your feedback, and will publish your results here on this post.

Cryptanalysis

Turns out this cipher is incredibly weak. It suffers from two problems that make it fall victim to linear cryptanalysis and a chosen plaintext attack:

  1. The chessboard (an S-box) remains static during the algorithm.
  2. There is no non-linear component to the system.

It turns out, designing hand ciphers is incredibly difficult. However, I wrote a follow-up post describing how weak it really is.

ZFS Administration, Appendix D- The True Cost Of Deduplication

Table of Contents

Zpool Administration ZFS Administration Appendices
0. Install ZFS on Debian GNU/Linux 9. Copy-on-write A. Visualizing The ZFS Intent Log (ZIL)
1. VDEVs 10. Creating Filesystems B. Using USB Drives
2. RAIDZ 11. Compression and Deduplication C. Why You Should Use ECC RAM
3. The ZFS Intent Log (ZIL) 12. Snapshots and Clones D. The True Cost Of Deduplication
4. The Adjustable Replacement Cache (ARC) 13. Sending and Receiving Filesystems
5. Exporting and Importing Storage Pools 14. ZVOLs
6. Scrub and Resilver 15. iSCSI, NFS and Samba
7. Getting and Setting Properties 16. Getting and Setting Properties
8. Best Practices and Caveats 17. Best Practices and Caveats

This post gets filed under the "budget and planning" part of systems administration. When planning out your ZFS storage pool, you will need to make decision about space efficiency, and the cost required to build out that architecture. We've heard over and over that ZFS block deduplication is expensive, and I've even mentioned it on this blog, but how expensive is it really? What are we looking at out of pocket? That's what this post is about. We'll look at it from two perspectives- enterprise hardware and commodity hardware. We should be able to make some decent conclusions after looking into it.

We're only going to address storage, not total cost which would include interconnects, board, CPU, etc. Those costs can be so variable, it can make this post rather complicated. So, let's stick with the basics. We're going to define enterprise hardware as 15k SAS drives and SLC SSDs, and we'll define commodity hardware as 7200 SATA drives and MLC SSDs. In both cases, we'll stick with high quality ECC DDR3 RAM modules. We'll use a base ZFS pool of 10TB.

So, without further ado, let's begin.

Determining Disk Needs

Before we go off purchasing hardware, we'll need to know what we're looking at for deduplication, and if it's a good fit for our data needs. This can bee a hard puzzle to solve, without actually storing all the data in the pool, and seeing when you end up. However, here are a few ideas for coming to that solution (the "three S tests"):

  1. Sample Test: Get a good representative sample of your data. You don't need a lot. Maybe 1/5 of the full data. Just something that represents what will actually be stored. This will be the most accurate test, provided you get a good sample- the more, the better. Store that sample on the deduplicated pool, and see where you end up with your dedupratio.
  2. Simulation Test: This will be less accurate than the sample test above, but it can still give a good idea of what you'll be looking at. Run the "zfs -S" command, and see where the cards fall. This will take some time, and may stress your pool, so run this command off hours, if you must do it on a production pool. It won't actually deduplicate your data, just simulate it. Here is actual an actual simulation histogram from my personal ZFS production servers:
    # zdb -S
    Simulated DDT histogram:
    
    bucket              allocated                       referenced          
    ______   ______________________________   ______________________________
    refcnt   blocks   LSIZE   PSIZE   DSIZE   blocks   LSIZE   PSIZE   DSIZE
    ------   ------   -----   -----   -----   ------   -----   -----   -----
         1    5.23M    629G    484G    486G    5.23M    629G    484G    486G
         2     860K   97.4G   86.3G   86.6G    1.85M    215G    190G    190G
         4    47.6K   4.18G   3.03G   3.05G     227K   19.7G   14.2G   14.3G
         8    11.8K    931M    496M    504M     109K   8.49G   4.25G   4.33G
        16    3.89K    306M   64.3M   68.3M    81.8K   6.64G   1.29G   1.37G
        32    5.85K    499M    116M    122M     238K   17.9G   4.64G   4.86G
        64    1.28K   43.7M   20.0M   21.0M     115K   3.74G   1.69G   1.79G
       128    2.60K   50.2M   20.0M   22.0M     501K   9.22G   3.62G   3.99G
       256      526   6.61M   3.18M   3.62M     163K   1.94G    946M   1.06G
       512      265   3.25M   2.02M   2.19M     203K   2.67G   1.72G   1.86G
        1K      134   1.41M    628K    720K     185K   2.13G    912M   1.02G
        2K       75   1.16M    188K    244K     222K   3.37G    550M    716M
        4K       51    127K   85.5K    125K     254K    657M    450M    650M
        8K        2      1K      1K   2.46K    26.7K   13.3M   13.3M   32.8M
       16K        1     512     512   1.94K    31.3K   15.6M   15.6M   60.7M
     Total    6.15M    732G    574G    576G    9.38M    920G    708G    712G
    
    dedup = 1.24, compress = 1.30, copies = 1.01, dedup * compress / copies = 1.60
  3. Supposed Test: Basically, just guess. It's by far the least accurate of our testing, but you might understand your data better than you think. For example, is this 10TB server going to be a Debian or RPM package repository? If so, the data is likely highly duplicated, and you could probably get close to 3:1 savings, or better. Maybe this server will store a lot of virtual machine images, in which case the base operating system will be greatly duplicated. Again, your ratios could be very high as a result. But, you know what you are planning on storing, and what to expect.

Now you'll have a deduplication ratio number. In my case, it's 1.24:1. This number will help us "oversubscribe" our storage. In order to determine how much disk to purchase, our equation should be:

Savings = Need - (Need / Ratio)

With my ratio of 1.24:1, which is running about a dozen virtual machines, rather than purchasing the full 10TB of disk, we really only need to purchase 8TB of disk. This is a realistic expectation. So, I can save purchasing 2TB worth of storage for this setup. The question then becomes whether or not those savings are worth it.

Determining RAM Needs

Ok, now that we know how much disk to purchase, we now need to determine how much RAM to purchase. Already, we know that the deduplication table (DDT) will occupy no more than 25% of installed RAM, by default. This is adjustable with the kernel module, but we'll stick with default for this post. So, we just need to determine how large that 25% is, so we can understand exactly how much RAM will be needed to safely store the ARC without spilling over to spinning platter disk. In order to get a handle on this metric, we have two options:

  1. Counting Blocks: With the "zdb -b" command, you can count the number of currently used blocks in your pool. As with the "zdb -S" command, this will stress your pool, but it will give you the most accurate picture of what to expect with a deduplication table. Below is an actual counting of block on my production servers:
    # zdb -b pool
    
    Traversing all blocks to verify nothing leaked ...
    
            No leaks (block sum matches space maps exactly)
    
            bp count:        11975124
            bp logical:    1023913523200      avg:  85503
            bp physical:   765382441472      avg:  63914     compression:   1.34
            bp allocated:  780946764288      avg:  65214     compression:   1.31
            bp deduped:             0    ref>1:      0   deduplication:   1.00
            SPA allocated: 780946764288     used: 39.19%

    In this case, I have 11975124 used blocks, and my 2 TB pool is 39.19% full, or 784GB. Thus, each block is about 70KB in size. You might see something different. According to Oracle, each deduplicated block will occupy about 320 bytes in RAM. Thus, 2TB divided by 70KB blocks gives a total storage space of about 30,700,000 total blocks. 30,700,000 blocks multiplied by 320 bytes, is 9,824,000,000 bytes, or 9.8GB of RAM for the DDT. Because the DDT is no more than 25% of RAM, I need at least 39.2GB, or basically 40GB of installed RAM to prevent the DDT from spilling to spinning platter disk. Of course, I'll also need space for the kernel and user applications to reside in RAM to prevent constant swapping, so I'll need more than the bare 40GB minimum.

  2. Rule of Thumb: This is our "rule of thumb" rule that you've read in this series, and elsewhere on the Internet. The rule is to assign 5GB of RAM for every 1TB of disk. This ratio comes from the fact that a deduplicated block seems to occupy about 320 bytes of storage in RAM, and your blocks could occupy anwhere between 512 bytes to 128KB, usually averaging about 64KB in size. So, the ratio sits around 1:208, which is where we come up with the "5GB RAM per 1TB disk" metric. So with a 10TB pool, we can expect to need 50GB of RAM for the DDT, or 200GB of RAM for the ARC.

In both cases, these RAM installations might just be physically or cost prohibitive. In my servers, the motherboards do not allow for more than 32GB of physically installed RAM modules. So 40GB isn't doable. As such, is deduplication out of the question? Not necessarily. If you have a fast SSD, something capable of 100k IOPS, or roughly the equivalent of your RAM install, then you can let the DDT spill out of RAM onto the L2ARC, and performance will not be impacted. A 256GB SSD is much more practical than 200GB of physical RAM modules, both in terms of physical limitations and cost prohibition.

Enterprise Hardware

Without SSD
15k SAS drives don't come cheap. Currently, the Seagate Cheetah drives go for about $1 per 3GB, or about $330 per 1TB. So, for the 8TB we would be spending on disk, we would be spending about $2600 for disk. We already determined that we need about 200GB of space for the ARC. If we need to fit everything in RAM, and our motherboard will support the install size, then ECC registered RAM goes for about $320 per 16GB (how convenient). I'll need at least 14 sticks of 16GB RAM modules. This would put my RAM cost at about $4480. Thus my total bill for storage only would be $7080. I'm only saving $670 by not purchasing 2 disks to save on deduplication.

With SSD
Rather than purchasing 14 16GB memory modules, we could easily purchase an enterprise 256GB fast SLC SSD for about $500. A 256GB SSD is attractive, because as an L2ARC, it will be storing more than just the DDT, but other cached pages from disk. The SSD could also be partitioned to store the ZIL, acting as a SLOG. So, we'll only need maybe 16GB installed RAM (2x8GB modules for dual channel), which would put our RAM cost at $320, our SSD cost at $500 and our drive cost at $2600, or $3420 for the total setup. This is half of the initial price using only ECC RAM to fit the DDT. That's significant, IMO. Again, I only saved $670 by not purchasing 2 disks.

Commodity Hardware

Without SSD
7200 SATA drives come cheap these days. ZFS was designed with commodity disk in mind, knowing it's full of failures and silent data corruption. I can purchase a single 2TB disk for $80 right now, brand new. Four of those put my total cost at $320. However, the ECC RAM doesn't change, and if I needed 14 of the 16GB sticks as with my enterprise setup, then I can count on my total cost for this commodity setup at $4800. But, a RAM install of that size does not make sense for a "commodity" setup, so let's reduce the RAM footprint, and add an SSD.

With SSD
A fast commodity SSD puts us at the MLC SSDs. The 256GB Samsung 840 Pro is going for $180 right now, and can sustain 100k IOPS, which could possibly rival your DDR3 RAM. So, again sticking with 4 2TB drives at $320, 16GB of RAM at $320 and our Samsung SSD at $180 our total cost for this setup is $820, only saving $80 by not purchasing an additional 2TB SATA drive. This is by far the most cost effective solution.

Additional Hidden Costs & SSD Performance Considerations

When we made these plans on purchasing RAM, we were only considering the cost of storing the ARC and the DDT. We were not considering that your operating system will still need room outside of the ARC to operate. Most ZFS administrators I know won't give more than 25% of RAM to the ARC, on memory intensive setups, and no more than 50% on less memory intensive setups. So, for our 200GB ARC requirement, it may be as much as 400GB of RAM, or even 800GB. I have yet to administer a server with that sort of RAM install. So, SSDs all of the sudden become MUCH more attractive.

If you decide to go the route of an SSD for an L2ARC, you need to make sure that it performs on par with your installed RAM, otherwise you'll see a performance hit when doing lookups in your DDT. It's expected for DDR3 RAM to have a rate of 100k to 150k sustained sequential read/write IOPS. Getting an SSD to perform similarly means getting the high end SATA connected SSDs, or low end PCIe connected, such as the OCZ RevoDrive.

However, suppose you don't purchase an SSD that performs equally with your DDR3 modules. Suppose your DDR3 sustains 100k IOPS, but your SSD only does 20k IOPS. That's 5x as slow as DDR3 (spinning 7200 RPM disk only sustains about 100 IOPS). With as frequently as ZFS will be doing DDT lookups, this is a SIGNIFICANT performance hit. So, it's critical that your L2ARC can match the same bandwidth as your RAM.

Further, there's a hidden cost with SSDs, and that's reliability. Typical enterprise SLC SSDs can endure about 10k write cycles, with wear leveling, before the chips begin to wear down. However, for commodity, more "consumer grade" SSDs, they will only sustain about 3k-5k write cycles. Don't fool yourself though. For our 256GB SSD, this means you can write 256GB 10,000 times, or 2.56PB worth of data on a SLC SSD, or 256GB 3,000 times, or 768TB on an MLC SSD. That's a lot of writing, assuming again, that the SSDs have wear leveling algorithms on board. But, the SSD may fail early, which means the DDT spilling to disk, and completely killing performance of the pool. By putting a portion of the DDT on the SSD, the L2ARC becomes much more write intensive, as ZFS expands the DDT table for new deduplicated blocks. Without deduplication, the L2ARC is less write intensive, and should be very read intensive. So, by not using deduplication, you can lengthen the life of the SSD.

Conclusion

So, now when you approach the CFO with your hardware quote, with a dedup ratio of 1.24:1, it's going to be a hard sell. With commodity hardware using an SSD, you're getting close to your savings in disk (10.25:1), as compared to enterprise hardware where you're spending much, much more to get close to those space savings (5.10:1). But, with commodity hardware, you're spending 1/4 of the enterprise equivalent. In my opinion, it's still too costly.

However, if you can get your ratio close to 2:1, or better, then it may be a good fit. You really need to know your data, and you really need to be able to demonstrate that you will get solid ratios. A storage server of virtual machines might be a good fit, or where you have redundant data that is nearly exactly the same. For general purpose storage, especially with a ratio of 1.24:1, it doesn't seem to be worth it. However, you're not out of luck, if you wish to save disk.

For good space savings on your disk, that you get nearly for free, I strongly encourage compression. Compression doesn't tax the CPU, even for heavy workloads, provides similar space savings (in my example above, I am getting a 1.3:1 compression ratio versus 1.24:1 dedup ratio), doesn't require an expensive DDT, and actually provides enhanced performance. The extra performance comes from the fact that highly compressable data does not need to physically write as much data to slow spinning platter, and also does not need to read as much physical disk. Your spinning disk is the slowest bottleneck in your infrastructure, so anything you can do to optimize the reads and writes could provide large gains. Compression wins here.

Hopefully, this post helps you analyze your deduplication plans, and identify the necessary costs.

Switch to our mobile site