Episode #92: Shifty Passwords

Hal blames Ed

A recent article on lifehacker.com suggested an interesting way of generating difficult to guess passwords: simply move your fingers over to the right one key. Thus, the password "12345" becomes "23456". Not very useful for purely numeric passwords, but with a reasonably large character set it starts to be useful. For example, "CommandLineKungFu" becomes "Vp,,smf:omrLimhGi".

On the GIAC Pen Testing Alumni mailing list (affectionately known as the "GPWN" mailing list), somebody suggested creating a tool to "right shift" strings in a password cracking dictionary to catch folks who relied on this trick for creating passwords. So of course Ed had to go looking for a Windows CMD.EXE solution. I'll let Ed explain later just how well that crazy notion ended up working out for him.

In the Unix world, this is clearly a job for the tr command. tr simply converts one list of characters to another list, so all we have to do is create a list of the characters in normal keyboard order and a corresponding list of the characters "right shifted" one place.

Yeah, I could do this manually. But then I thought it might be fun to throw a little shell fu at the problem:

$ r1='`1234567890-='
$ r1s=`echo $r1 | sed -r 's/(.)(.*)/\2\1/'`
$ echo $r1s
1234567890-=`

Here I'm defining a variable called $r1 which is all of the characters from the top row of the keyboard from left to right. I then create a new variable called $r1s ("$r1 shifted") by using sed to pop the first character off of the front of $r1 and shift it around to the end of the string. In other words, everything will shift right one place when we call tr and the "=" character (the last character in the row) will "wrap around" and become a backtick (the first character in the row).

Now we need to do the same thing again for the first row, but this time we'll be holding the shift key down. Since this is the "upper-case" version of the row, we'll name the variables $R1 and $R1s:

$ R1='~!@#$%^&*()_+'
$ R1s=`echo $R1 | sed -r 's/(.)(.*)/\2\1/'`
$ echo $R1s
!@#$%^&*()_+~

We'll need to repeat this process six more times for the lower- and and upper-case versions of the remaining three rows on the keyboard. Be careful on row #3 where the quote characters are! You'll need to do something like this:

$ r3="asdfghjkl;'"
$ r3s=`echo $r3 | sed -r 's/(.)(.*)/\2\1/'`
$ R3='ASDFGHJKL:"'
$ R3s=`echo $R3 | sed -r 's/(.)(.*)/\2\1/'`

Because $r3 is going to contain a single quote, we quote the string of characters using a double quote, which is fine since the string contains no other special characters that might be interpolated in the double quotes.

When all is said and done, you'll end up with eight variables-- $r1, $R1, $r2, $R2, $r3, $r4, and $R4-- plus their eight "right shifted" versions-- $r1s, $R1s, ... and so on. We can now use these in our tr expression:

$ echo CommandLineKungFu | tr "$r1$R1$r2$R2$r3$R3$r4$R4" "$r1s$R1s$r2s$R2s$r3s$R3s$r4s$R4s"
Vp,,smf:omrLimhGi
$ cat dict.txt | tr "$r1$R1$r2$R2$r3$R3$r4$R4" "$r1s$R1s$r2s$R2s$r3s$R3s$r4s$R4s" >shift-dict.txt

The first command shows you how to "right shift" a single word-- useful for testing to make sure you got your variable settings right. The second command is what you would use to "right shift" an entire password dictionary.

Note that you can easily "unshift" text by simply reversing the order of the arguments to tr:

$ echo CommandLineKungFu | \
 tr "$r1$R1$r2$R2$r3$R3$r4$R4" "$r1s$R1s$r2s$R2s$r3s$R3s$r4s$R4s" | \
 tr "$r1s$R1s$r2s$R2s$r3s$R3s$r4s$R4s" "$r1$R1$r2$R2$r3$R3$r4$R4"
CommandLineKungFu

So we could even use our little tr hack for trivial obfuscation, similar to the old tried and true ROT-13 "cipher".

OK, that's it from the world of the Unix command line. Now get ready to enter some strange waters on the Windows side of the blog...

Tim agreed with Ed that this would be a good idea...it wasn't.

So we need to shift some characters, it is really easy to by hand. In fact, it is so easy I do it by accident every now and then; however, using a windows shell to do the same task is not so easy.

My first attempt at this problem involved arrays. I would load up an array with a row of characters, than make another array with the characters shifted by one. So far so good, but it went downhill fast. Once we have the arrays, it turns into a programming excessive of iterating through each character in the string to be transformed, finding the character in the first array, figuring out its index, get the character of the same index in the second array, output the new character, rinse, and repeat. This solution required I get a visa to visit Scriptland, and it was denied. I needed a better approach.

My second attempt involved hash tables. If you aren't familiar with the hash table data structure, it maps (unique) keys to associated values. For example, if the phonebook were a hash table the keys would be the names, and the values would be the phone numbers. There is a one to one mapping of names to phone numbers. It is designed to lookup names to get phone numbers, but not the other way around.

We want to create a hash table that looks something like this.

Key  Value
---  -----
`    1
1    2
2    3
3    4
4    5
5    6
6    7
7    8
8    9
9    0
0    -
-    =
=    `

If we look up 1 in the hash table, the value returned is 2. We can use this to transform our password. So let's load up the first row.

PS C:\> $ht = @{}
PS C:\> $row = "``1234567890-="
PS C:\> 1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }

We create the hash table, then we create a variable that holds the first row of characters. Actually loading the hash table is a little tricky.

The range operator is used to count from 1 to the length of the $row variable. We then load the hash table one character at a time. We add the first pair where the 0th character in the string (remember base 0) is the key, and the associated value is the 1th character in the string. We continue until we get to the last number in our range. When we get to the last number in the range, the key is the last character in the string, and the value is the first character. We wrap around with our by using the modulus operator (%) since 13 mod 13 = 0.

We continue to load the "capitalized" version of the fist row.

PS C:\> $row = "~!@#$%^&*()_+"
PS C:\> 1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }

We have a problem, after the second row (qwerty) is loaded, the capitalized version of the row stops on the lowercase version. By default, the hash table keys are case insensitive, but we can create a case sensitive hash table.

PS C:\>$ht = New-Object Collections.Hashtable ([StringComparer]::CurrentCulture)

And then load the hash table:

PS C:\>$ht[" "] = " "
PS C:\>$row = "``1234567890-="
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "~!@#$%^&*()_+"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "qwertyuiop[]\"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "QWERTYUIOP{}`|"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "asdfghjkl;'"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "ASDFGHJKL:`""
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "zxcvbnm,./"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }
PS C:\>$row = "ZXCVBNM<>?"
PS C:\>1..($row.Length) | % { $ht[$row[$_ - 1]] = $row[$_ % $row.Length] }

So now we have hash table that contains our character mapping, and we can use it for our transformations.

C:\> "CommandLineKungFu".ToCharArray() | % { $ht[$_] }
V
p
,
,
s
...

Each character is output separately, not what we wanted. We can use some .NET to put the string back together.

PS C:\>[system.string]::join("",("CommandLineKungFu".ToCharArray() |
% { $ht[$_] }))

Vp,,smf:omrLimhGi

The Join function takes two parameters, a separator and an array of elements to concatenate. This gives us pretty output.

We can even take the passwords from a file and shift them:

PS C:\> cat password.lst | % { [system.string]::join("",($_.ToCharArray() |
% { $ht[$_] })) }

Now that was pretty ugly, but it can only get worse.

Ed Gets Worse
Sometimes, when dealing with cmd.exe, I feel like I'm working with the Ruprecht of shells, a reference to the movie Dirty Rotten Scoundrels. I mean, Hal's auto-generating his shifts with bash and Tim is building frickin' hash tables. Ruprecht-shell and I, though, don't have such fancy capabilities and constructs. As I mentioned in Episode #82 (under the headline Ed's Got Sed), we can make substitutions of individual characters or groups of characters. That is, if we want to change every a in a password to s, we could run:

C:\> cmd.exe /v:on /c "set stuff=abcdef & set stuff=!stuff:a=s! & echo !stuff!"
sbcdef

When I initially approached this problem, I started at that a, and went forward in my abc's, making a into s, b into n, c into v, and so on for the shift right. Big mistake. Consider:

C:\> cmd.exe /v:on /c "set stuff=abcdef & set stuff=!stuff:a=s! & set stuff=!stuff:b=n!
& set stuff=!stuff:c=v! & set stuff=!stuff:d=f! & set stuff=!stuff:e=r!
& set stuff=!stuff:f=g! & echo !stuff!"
snvgrg

Uh-oh. See those two g's? The first comes from the d that was shifted to a f, which was then later shifted to g. The second comes from the f, which was shifted to a g. Doh! Shifting alphabetically just won't work, because of the potential for multi-shifts. Tim then pointed out that we could avoid this problem if we shifted more carefully, not going alphabetically, but instead relying on the keyboard order itself to prevent double shifting entirely. If we are going to shift right one slot on the keyboard, we want to start doing that with the keys on the right hand side of the keyboard, and move our way left-ward.

Putting all of that together, here is the command to perform the alteration:

C:\> cmd.exe /v:on /c "set stuff=abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789
& set stuff=!stuff:^-=^=! & set stuff=!stuff:0=^-! & set stuff=!stuff:9=0!
& set stuff=!stuff:8=9! & set stuff=!stuff:7=8! & set stuff=!stuff:6=7! & set stuff=!stuff:5=6!
& set stuff=!stuff:4=5! & set stuff=!stuff:3=4! & set stuff=!stuff:2=3! & set stuff=!stuff:1=2!
& set stuff=!stuff:^[=^]! & set stuff=!stuff:p=^[! & set stuff=!stuff:o=p! & set stuff=!stuff:i=o!
& set stuff=!stuff:u=i! & set stuff=!stuff:y=u! & set stuff=!stuff:t=y! & set stuff=!stuff:r=t!
& set stuff=!stuff:e=r! & set stuff=!stuff:w=e! & set stuff=!stuff:q=w! & set stuff=!stuff:^;=^'!
& set stuff=!stuff:l=^;! & set stuff=!stuff:k=l! & set stuff=!stuff:j=k! & set stuff=!stuff:h=j!
& set stuff=!stuff:g=h! & set stuff=!stuff:f=g! & set stuff=!stuff:d=f! & set stuff=!stuff:s=d!
& set stuff=!stuff:a=s! & set stuff=!stuff:^.=^/! & set stuff=!stuff:^,=^.! & set stuff=!stuff:m=^,!
& set stuff=!stuff:n=m! & set stuff=!stuff:b=n! & set stuff=!stuff:v=b! & set stuff=!stuff:c=v!
& set stuff=!stuff:x=c! & set stuff=!stuff:z=x! & echo !stuff!"
snvfrghjokl;,mp[wtdyibecux-234567890snvfrghjokl;,mp[wtdyibecux-234567890

See? The command is so simple that it practically types itself. Actually, I think this wins the record for the longest command we've ever had on this blog.

Of course, this only shifts lower-case characters (and unshifted numbers). If you really want to shift upper case as well, you can add those transforms to the above syntax. I can think of no better way to spend a Spring day.

And, in the immortal words of Ruprecht.... THANK YOU. ;)