A few months back, one of the consultants here at Intrepidus ran across a strange password hash format:
He did some digging, and eventually found an application which would not only create the hashes, it would decrypt them. So it’s not even a hash at all, just a really lousy encryption system. Well, not even encryption. Technically, it’s an encoding. “Citrix CTX1 Encoding”, to be exact. “How does this work?” I wondered. Unfortunately, the person who created the app we downloaded specifically declined to explain the algorithm, so we just moved on.
Then a little while ago I thought it’d be fun to figure out. Using the application as an oracle, I set about encrypting various words to see what happened.
The first thing I noticed is that it seemed to be a binary-level encoding. If I entered gibberish for a password and then tried to decrypt it, I’d get all kinds of high-bit special characters. Then, I noticed that the ciphertext was four times as long as plaintext — that is, any single character encoded to four cipher characters, which I took to calling “quads.” Also, the encryption appeared to be position dependent:
a MEGB aa MEGB KFAA aaa MEGB KFAA MEGB
[I’ll add spaces between cipher quads for readability]
There was also some kind of multiple-character interaction going on:
aa MEGB KFAA ab MEGB KGAD ba MHGC KGAD bb MHGC KFAA
Note how the 2nd quad is the same for “ab” and “ba” and also for “aa” and “bb.”
And, finally, letter case matters:
a MEGB A OEEB
So all that was very interesting. Also interesting is how many letters are in the cipher alphabet. I tried encrypting all letters, numbers, and a bunch of special characters [A-Za-z0-9!-)], and found a total of 16 letters in use, A through P. Also, the distribution of the letters was very uneven, with over 30 As and only 6 Ms. The distribution is even stranger when you look at the data positionally within each ciphertext quad.
Overall 1st 2nd 3rd 4th 33 A 18 A 15 A 31 B 4 B 16 B 11 B 7 C 5 C 1 C 1 C 13 D 7 D 6 D 30 E 11 E 15 E 4 E 15 F 15 F 2 G 8 G 6 G 13 H 19 H 1 H 5 H 7 I 1 I 6 I 11 J 7 J 4 J 29 K 18 K 3 K 8 K 25 L 16 L 9 L 6 M 2 M 4 M 19 N 13 N 6 N 24 O 15 O 9 O 11 P 8 P 3 P
Again, very interesting. Still not totally clear, though a pattern should already be evident (were I paying attention). That data was generated with just a long string…what if we simply encrypt ‘A’, then encrypt ‘B’, then ‘C’, etc., and keep looking at the single quad output from a single character? I’ll throw in some special characters too, which will make sense very shortly.
@ OFEA P PFFA A OEEB Q PEFB B OHEC R PHFC C OGED S PGFD D OBEE T PBFE E OAEF U PAFF F ODEG V PDFG G OCEH W PCFH H ONEI X PNFI I OMEJ Y PMFJ J OPEK Z PPFK K OOEL [ POFL L OJEM \ PJFM M OIEN ] PIFN N OLEO ^ PLFO O OKEP _ PKFP
There’s a very clear pattern happening here. Let’s look at it in binary. Since all the letters in the ciphertext fall in the 0x4x range, we’ll just look at the lower-most nibble of all the ciphertext values. That is, for each of the letters in the ciphertext quad (“OHEC”) we’ll look at the binary values for the lower-most four bits (so, for “C”, which is 0x43 in ASCII, the lowermost nibble would be “0011”):
A 0x41 OEEB 1111 0101 0101 0010 B 0x42 OHEC 1111 1000 0101 0011 C 0x43 OGED 1111 0111 0101 0100 D 0x44 OBEE 1111 0010 0101 0101 P 0x50 PFFA 0000 0110 0110 0001 Q 0x51 PEFB 0000 0101 0110 0010
Look at the last two columns (the 3rd and 4th letters) in each ciphertext quad. There’s a direct correlation to the nibbles of the actual hex value. A 4x in the plaintext causes the 3rd column to be a 5 (or letter E), and a 5x makes it F. The last column is simply one off — a x0 puts an A in the 4th column, an x1, a B, etc. That is, 0-F maps to A-P for both those columns.
There’s a similar system at play for the first two columns, only the input nibbles are first XORed with 0x0A and 0x05 (for high and low nibbles, respectively). That is, 0x41 (“A”) will be mapped to 4 XOR 0x0a, or 0100 ^ 1010, which gives hex 0x0e, or (once mapped to A-P), the ciphertext letter “O,” because 0x0e = 14, and O is the 14th letter (when A is 0). For the lower nibble, we have 1 XOR 5, or 0001 XOR 0101 in binary, which is simply a 4, which maps to the ciphertext letter E.
So we have, for 0x41 “A”, ciphertext of OE (using XORs) and EB (simply mapping 4 to E and 1 to B), or OEEB. Of course, we don’t even need the 1st two columns since the last two are so easy to decode. So not only is this a bad “cipher”, it’s inefficent.
All that only answers how to encrypt the 1st letter. What happens in the subsequent letters? Well, that’s pretty easy too. Remember that, for both AA and BB, the second quad that’s output was KFAA. That’s the case for CC, DD, EE, and in fact any time that the 2nd character is the same as the first. What happens if you XOR a letter with itself? You get 00. What is KFAA in this crazy system? 00. So the 2nd ciphertext quad is the 2nd plaintext letter XORed with the 1st plaintext letter.
Unfortunately, that doesn’t hold true for the 3rd letter. But a little more experimentation shows that it’s simply using a running “sum” of all previous characters XORed together.
Here’s a very simple script to encrypt, and another to decrypt, these really bad password strings:
import sys def encrypt(pt): ct = '' last = 0 for ch in pt: ct += enc_letter(ch, last) last ^= ord(ch) return ct def enc_letter(ch, last=0): c = ord(ch) ^ last h = c / 16 # high nybble l = c % 16 # low nybble a = h ^ 0x0A b = l ^ 0x05 c = h d = l ach = chr(a+0x41) bch = chr(b+0x41) cch = chr(c+0x41) dch = chr(d+0x41) return "%s%s%s%s " % (ach, bch, cch, dch) x = sys.stdin.readline() while x: print encrypt(x.strip()) x = sys.stdin.readline()
import re, sys def decrypt(ct): pt = '' last = 0 for i in range(0, len(ct), 4): pc = dec_letter(ct[i:i+4], last) pt += pc last ^= ord(pc) return pt def dec_letter(ct, last=0): c = (ord(ct) - 1) & 0x0f d = (ord(ct) - 1) & 0x0f x = c*16+d pc = chr(x^last) return pc x = sys.stdin.readline() while x: x = re.sub('[^A-P]', '', x.upper()) print decrypt(x) x = sys.stdin.readline()
The bottom line here, predictably, is: Don’t make your own crypto. This vendor did, and they created something that was pretty much totally useless. On the other hand, it was fun to figure out, so I guess they provided some entertainment.