Shuffle Hash

(Difference between revisions)

Revision as of 17:16, 26 April 2010

The Shuffle Hash is a cryptographic hashing algorithm I'm working on developing with the intention that it can be performed by hand. The name comes from the fact that it's designed to be performed using a deck (or partial deck) of cards, a la the Solitaire cipher.

1 Motivation
2 Algorithm
3 Use for Passwords

Motivation

The primary motivation for this is for use in password generation. My usual password mechanism relies on a single strong "core" password that I've committed to memory. To create service-specific passwords, I add an associated prefix to my password, like "gmail" for my Gmail account, "twitter" for Twitter, etc. Then, I pass the concatenated string through a hash algorithm, encode the output in Base-64, and use that as the password for that service. Now if one of those passwords gets compromised, the attacker will have access to that account, but won't feasibly be able to reverse it to figure out what my core password is, so they won't be able to get into any other accounts. This is why it's really important not to use the same password for everything, but doing it my why means I only have to remember one good password, and I can derive the rest from that.

The problem is, standard cryptographic hashing algorithms aren't feasible to do without a computer. That means if the service I'm trying to log on to is the computer itself, I'm out of luck. Even if I'm already on the computer, I still need access to a secure implementation of the hash which is not always easy to come by.

Hence, it would be great if there was a secure has algorithm that is reasonable to perform by hand when necessary. Obviously, you would opt for a computer implementation when available and secure, but it should be very practical to do it by hand, as well.

Algorithm

This is the current algorithm I'm working on:

Start with a deck of N cards arranged in numerical order from 0 up to N-1.
Data is fed in as values in the closed range [0, N-1].
1. For instance, a standard 52-card deck could represent all the upper- and lower- case letters in the English alphabet. A 26-card deck could represent all the letters in one case. Or you can use any custom alphabet with N elements.
For each value that is fed in, search through the deck till you find that value.
Cut the deck into a top part and a bottom part, so that the found card is the first card in the bottom part.
Move the found card to become the first card in the top part.
Move the next card beneath the found card (now at the front of the bottom part) to the bottom of the top part.
1. If there is no other card beneath the found one (i.e., the bottom part is empty after moving the found card), just wrap around, so the next card is actually the one that was on top).
Put the top part beneath the bottom part.

So for instance, if we have a small deck of 9 cards:

[ 0 1 2 3 4 5 6 7 8 ]

And we feed in 5, we cut the deck like this:

[ 0 1 2 3 4 ]   [ 5 6 7 8]

Where 0 is at the front of the top part, and 5 (the found card) is at the top of the bottom part. Now we move the found card up to the front of the top part:

[ 5 0 1 2 3 4 ]     [ 6 7 8 ]

And then move the "next" card to the back of the top half:

[ 5 0 1 2 3 4 6 ]     [ 7 8 ]

And put the top under the bottom:

[ 7 8 ]   [ 5 0 1 2 3 4 6 ]
[ 7 8 5 0 1 2 3 4 6 ]

The edge case is when the found card is the last in the deck. Say we start with a fresh deck of 9 cards:

[ 0 1 2 3 4 5 6 7 8 ]

And we feed in 8. When we cut, we get:

[ 0 1 2 3 4 5 6 7 ]   [ 8 ]

Now there's no card after the found card (the 8), so we have to wrap around and take it from the start:

[ 1 2 3 4 5 6 7 ]     [ 8 0 ]

Now we can continue as usual:

[ 8 1 2 3 4 5 6 7 ]    [ 0 ]
[ 8 1 2 3 4 5 6 7 0 ]  [ ]
[ ]   [ 8 1 2 3 4 5 6 7 0 ]
[ 8 1 2 3 4 5 6 7 0 ]

So you'll notice all this actually does is swap the first and last card.

Use for Passwords

Let me just remind everyone that this algorithm is a work in progress and that I am very much an amateur cyptographer. I'm still looking into the security of this algorithm (and if anyone has any input, please contact me.

The most direct way to use this for passwords is to feed in your sites-specific prefix ("gmail", "twitter", etc), then feed in your core password, then take X cards from the top of the resulting deck. If the deck has N cards, and you take the top X for use as your password, there are N-permute-X possible passwords, which is simple N!/(N-X)!. So for instance, if you have a full 52-card deck, and you take 10 cards as your password, there are 52!/42!, or a little over 5.7e16 (57 quadrillion), possible passwords. This works out to about 55 bits of information (maximum).

This is a good strong password for most typical everyday uses, and fairly easy. The hardest part if actually arranging the deck in numerical order to being with. It's not that hard, but it's not that easy, either. If you're willing to work with a a full 52-card deck, then you can get significantly stronger passwords by choosing more letters (making X bigger). For instance, using 12 cards out of 52 gives you 66 bits, and choosing 14 gives you 77 bits.

A half deck is a little easier to sort, and still gives you 26 cards. Taking 10 cards as your password gives 44 bits, 12 cards give you 52 bits, and 14 cards gives you 59 bits. Those are probably pretty good for most people.

Cutting down to a single suit is really quick and easy to sort, and gives you a 13-card deck. However, 10 cards doesn't quite get you 30 bits, which isn't really that strong. 12 cards from 13 gives you 32.5 bits, which isn't much better.

The Need to Feed

Note that when I'm talking about the number of bits in a password, this is the maximum number of bits the password can contain. To get there, you still need to feed in at least that much information. For a 52-card deck, each value has 5.7 bits. To get your 10-card/55-bit password, you need to feed in at least 10 values. For the 12-card/66-bit password, you'll need to feed 12.

The 26-card deck only has 4.7 bits per card. In this case, your 12-card/52-bit password needs 11 feeds (that'll get you very close, anyway, 51.7 bits). For the single suit deck, you only get 3.7 bits per card fed, so for 12-cards/32.5-bits, you need to feed 9 cards in.

Strong "Core" Passwords Still Needed

But we're still talking about a maximum here. Each value chosen out of 52 possible values only gives you 5.7 bits if you choose it randomly. If the "core" password you feed into the hash is "password", then you still only have about 2 bits of information in the hash (I'm spit-balling that "password" is one of the top-four passwords).

The best way to choose a core password? Just use your deck of cards (what ever size deck you're going to use for the hash, since this defines the maximum value you can feed in). Shuffle it up 5 or 6 or 10 times, turn the deck face down, and choose one randomly from the somewhere in the middle. That's the first value in your password. Put that card back (anywhere you want), shuffle it up a few more times, and randomly choose your second card. Keep going till you have enough. This is your randomly chosen core password which you'll want to commit to memory. If it helps, convert the cards to letters and make up a sentence from those letters. For instance, if I chose (for a 26-card deck) 8-clubs, Q-diamonds, 3-diamonds, J-clubs, 6-diamonds; this might correspond to the letters 'h', 'y', 'p', 'k', and 's'. I might remember this as "Hey, you! Please keep still!". (Of course, that password only has 23.5 bits, so I would want to add several more letters).

Password Table

The following table shows some bit counts for different length passwords under different scenarios. The "Hand Size" refers to the number of cards you take from the shuffled/hashed deck to use as your password.

Deck Size	Hand Size	Maximum Bit-Strength	Minimum Core Size
52	14	77.03	14
52	12	66.42	12
52	10	55.67	10
26	14	59.55	13
26	12	52.04	11 (gives 51.7 bits)
26	10	44.13	10
24	14	57.25	13
24	12	50.20	11
24	10	42.69	10
16	14	43.25	11
16	12	39.67	10
16	10	34.76	9
13	13	32.54	9
13	12	32.54	9
13	10	29.95	8 (gives 29.6 bits)

Putting it in Perspective

For reference, most people (well, those who actually use somewhat secure passwords), pick from an alphabet of no more than 94 characters (that's even a pretty huge stretch: it's every upper- and lower- case letter, all the digits, and all 32 special characters present on most keyboards). Each of these characters is a little less than 6.6 bits, so an 8 character password has less than 53 bits, a 10 character password has almost 66 bits.

As a more realistic reference: there are probably short of 230000 words in the English language[1]. A frightening number of people have passwords based on an English word. For each words, there might be 3 or 4 digits mixed in (that's being pretty generous). Letters and symbols might be substituted (like '@' for 'a', etc) to add "security". I think that allowing for 4 different substitutions per letter (on average) is pretty generous. Figuring people may substitute 2 or 3 of the letters in this way gives 4^3 or 64 variations per password. We should account for upper- and lower- case as well: that's two more variations per character, figure most people's passwords aren't more than 8 characters (no reference, just a shot in the dark), so that's another 2^8, or 256 variations per password. Factor in the 10000 variations by adding 4 digits, and you get 230000*64*256*10000, not quite 38 trillion different passwords, which is equivalent to about 45.1 bits. And honestly, that's being extraordinarily generous, most people just pick a dictionary word, add a digit or two (or none), and call it a day. Realistically, I'd say a typical person might have 25 bits of information in their password, absolute max.

For yet more context, a typical computer can potentially run 3 or 4 billion instructions per second (per core). Round up to 10, and figure a computer might have 2 or 3 cores (but we'll go with 10, just to be safe), and that a big time attacker might have the equivalent of 1000 or so dedicated computers on the job (that's one hell of a botnet, remember, we're talking about the equivalent of dedicated systems), you're talking about 100 trillion instructions per second. If they could test one password with a single instruction, they will have tried every one of your 57 quadrillion possible passwords (10 cards from a 52-card deck) in 57 thousand seconds, or about 15.8 hours.

That's not very much, but it's going to take a lot of more than 1 instruction to try a password. Let's say 100 instructions to try a password. Now you're looking at 1580 hours, or a little over 65 days. To be fair, the expected number of passwords that need to be tried before finding the right one is only half of that, so we're actually looking at 33 days. If you're protecting national or corporate secrets or something of equivalent value to an attacker, you're going to want more security than this. However, if you're protecting your Facebook account, I doubt anyone is going to dedicate this much of their resources to breaking in, especially when in the same time they could probably crack a hundred or more accounts of people using dictionary words as passwords.

Actually, if the password is for some kind of network service (as opposed to, say, an encrypted file that the attacker has direct access to), then you need to count in the overhead of actually contacting the service and trying the password. I'd be seriously surprised if even a sophisticated attacker with a massive botnet could try more than a billion passwords per second for an online service. That brings the expected time to about 9 years.

So the bottom line of all this estimating is that for the average person who wants to protect their email, home computer system, Facebook account, etc.; 40 bits of information in the password should be plenty. That's already going to be more than thirty-two-thousand times harder to crack than the "typical" 25-bit password.

Alternate Method

There is an alternate method that you can use to increase the strength of your password arbitrarily, even while using a smaller deck. In this method, you use the hash more like a pseudo random number generator (PRNG). In this case, you need two core passwords, which I'll call the "seed" and the "key".

You start by feeding in the service-specific prefix, as usual, then the seed. The prefix sets up the deck into a service-specific "initial" state so that the result is different for every service, just like in the other method. The seed then puts the deck into a "you-specific" state (actually and you-and-site-specific state). Once you're done with the seed, you start feeding in characters from your "key". Each time you feed in a character, you use the last card from the deck as the next character of your output. It's important to use the last card, because the first card is the "found" card from your key. When you're done, you should have the same number of output characters as there are in your key. These are your password.

The strength of your password can be made arbitrarily strong by extending your key. For instance, using a 13-card deck, each card (and therefore each output character) has 3.7 bits. To get a 50-bit password, use a 14 character key (which will actually get you 51.8 bits). It doesn't matter that the deck itself only can only hold 32.5 bits at a time (13!), because the randomness actually comes from your key. If you want a smaller key with the same security, you just need to use a bigger deck. For instance, a 26-card deck can get you 50 bits with and 11 character key (gives 51.7 bits), and a 52-card deck gives 50 bits with a 9 letter key (51.3 bits).

(Strictly speaking, the shorter key from the larger is no easier to remember/store, because it contains the same amount of information. E.g., you don't need to remember as long of a sequence of letters, but for each letter you need to remember if it's upper or lower case.)

What you're really doing here is encrypting your key to produce the password. However, you're doing it with a pseudo-random cipher that's specific to you and specific to the service (more accurately, specific to this particular combination of service-prefix and seed). The seed doesn't really add any security to the password itself, meaning that the password is no harder for an attacker to guess with or without a seed. What it does is protect your key if the password is compromised (which is the whole point of the hashing).

Retrieved from "http://bmearns.net/wwk/view/Shuffle_Hash"

Category: Cryptography

Cryptography

From the World Wide Wiki