Cryptography-Digest Digest #255, Volume #13 Fri, 1 Dec 00 23:13:01 EST
Contents:
AIM Password Decoding for the Inquisitive v1.02 (full text) (Stephen Anthony Uy)
----------------------------------------------------------------------------
From: Stephen Anthony Uy <[EMAIL PROTECTED]>
Subject: AIM Password Decoding for the Inquisitive v1.02 (full text)
Date: Fri, 01 Dec 2000 19:41:03 -0800
In retrospect, I think it may have been more courteous of me to simply
post my text... please accept my apologies if I'm being annoying.
=====8<=====CUT=====8<=====
AIM Password Decoding for the Inquisitive v1.02
by Stephen Anthony Uy <[EMAIL PROTECTED]>
---
[ Table of Contents ]
1. Disclaimer
2. History
3. Introduction
4. Finding the Encoded Password
5. Analysis
6. Conclusion
7. Table used for Analysis
8. Thanks
---
[ 1. Disclaimer ]
The information in this document in no way represents the
thoughts or opinions of anyone except for the author. This
document is intended for educational use only. This document is
not intended to be used for illegal purposes; if one chooses to
use the information in this document for illegal purposes, the
author will not be held liable for any resultant damages.
This document may be freely distributed, so long as due credit
is given to the author. This document may not be modified. All
digital signatures provided with this document must be preserved
and distributed with this document.
---
[ 2. History ]
20001128.2012
Wrote and analyzed for 36 minutes; the document started
to take form; at the time, I thought that the encoding
was table-driven; as we'll see, I wasn't that far off.
No version number; I originally didn't intend to pursue
this seriously.
20001130.1935
Four hours of work, and I'm done. Hurrah! Version 1.0.
20001131.0141
Bah! I was eating and I realized that I neglected to
construct my pseudocode properly. I also fixed a couple
of lines that went over my 66-character-width limit.
That's what I get for rushing things. Version 1.01.
20001131.0208
Things just keep popping up... I realized that I forgot
to make the ASCII values in section 7 explicitly hex.
So I added "0x" to every value. Then I decided that
tables E2 and E3 were redundant, so I compressed them
both into table E2. Following that, I noticed that
tables L1-L4 and M1-M4 weren't explicitly hex either, so
I fixed those, too.
20001201.0746
Lovely, just lovely. I coded my pseudocode into Java
(my, I love that language!), cleaned up the pseudocode,
and fixed tables E1 and E3; apparently I switched a
couple of keys. I think I'm on my way to the next
version of this thing. Perhaps next time, I'll include
my source code.
20001201.1805
It appears that I switched a couple of values in table
E2 also. Good thing I found it. Then I looked at the
disclaimer, found it slightly lacking, and updated it
with a little more legalese. Then I went through and
edited the text for clarity. Version 1.02.
---
[ 3. Introduction ]
One night, I found myself looking for an AIM password decoder.
Unfortunately, all the ones I found were without source code,
save one (whose name escapes me at the moment). I browsed
through the source, saw a sloppy if/else-based decoder, and
decided right then and there to embark upon my own (amateur)
cryptanalysis of the AIM password encoding scheme. I figured
that I'd get the most enjoyment and satisfaction (and learn the
most too, I guess) if I started from scratch. So I started from
scratch.
What you're reading is the product of that moment of boredom and
my compulsion to finish what I'd started.
---
[ 4. Finding the Encoded Password ]
First things first. If you want to decode an encrypted AIM
password, you first have to be able to find it. Fortunately,
that's easy; AIM stores saved passwords in the registry in this
key:
My Computer\
HKEY_CURRENT_USER\
Software\
America Online\
AOL Instant Messenger (TM)\
CurrentVersion\
Users\
[insert screen name here]\
Login
Inside are two values:
Autologin binary
Password string
Obviously (to most, I'll hazard), the value "Password" contains
the encoded string we're looking for. The format of that string
follows this pattern:
��AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP
The first two characters are always the same: alt+0255.
The part that interests us comes after the initial padding: one
to sixteen doubles of capital ASCII characters ranging from A
through P, each double encoding one character. AIM allows
passwords from four to sixteen characters long, so a working
password will have anywhere from four doubles to sixteen doubles
(eight to thirty-two characters) following the initial
two-character padding.
---
[ 5. Analysis ]
Before I start, I'll define some terminology. I call each set
of two characters after the padding a "double"; the double is an
encoded representation of the ASCII code for that character.
In layman's terms: "AA" is a double.
Since each double is a representation of an ASCII code, I term
the halves of the double the "LSN" and the "MSN" -- that's "less
significant nibble" and "more significant nibble." If you're
semi-versed in computer science, you'll know which half to call
which.
In layman's terms: if "AB" is a double,
then "A" is the MSB and "B" is the LSB.
Lastly, our password is of the format:
��AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP
I needed a layman-like term to call each double, so I decided
to call them "positions" instead of "bytes." Why? It was
arbitrary; I don't really know, myself.
In layman's terms: see that last indented section up
there? We'll call "AA" position 1, "BB"
position 2, and so on until "PP," which is
position 16.
So, I'd started my cryptanalysis: I had a password and an encoded
string associated with that password:
aaaaaaaaaaaaaaaa -> ��CDOFGJHBEACDOEGKHGEPDMNLBFIJLBMA
I tested a few more values, counting the characters each time.
I consistently found that the number of uppercase characters was
twice the number of characters in my password (plus two
characters of padding). The scheme didn't seem very secure,
even given only a few minutes of thought.
---
Table R1: "aaaaaaaaaaaaaaaa" drawn out
aaaaaaaaaaaaaaaa
CD OF GJ HB EA CD OE GK HG EP DM NL BF IJ LB MA
---
I decided to check the values of the letters of the alphabet,
both upper and lower-case. Since I didn't have any automated
way to do it, I did it by hand: I would enter a password, shut
down AIM, refresh my view in regedit, and copy-and-paste the
password value. This process got me the following sets of data
(and section 7, but that comes later):
---
Table R2: Encoded doubles
abcdefghijklm
CD OG GL HE EE CE OC GD HO EE DG NG BJ
ABCDEFGHIJKLM
AD MG EL FE GE AE MC ED FO GE BG PG DJ
nopqrstuvwxyz
CM OL HI GB FD DB PB HO GB FJ CF MD AO
NOPQRSTUVWXYZ
AM ML FI EB HD BB NB FO EB HJ AF OD CO
---
I thought it strange that both 'p' and 'P' didn't match the
the pattern given by the "aaaaaaaaaaaaaaaa" password. I decided
to check the ASCII values of a-z and A-Z:
---
Table 32: ASCII bytes (in hexadecimal)
abcdefghijklm
61 62 63 64 65 66 67 68 69 6A 6B 6C 6D
ABCDEFGHIJKLM
41 42 43 44 45 46 47 48 49 4A 4B 4C 4D
nopqrstuvwxyz
6E 6F 70 71 72 73 74 75 76 77 78 79 7A
NOPQRSTUVWXYZ
4E 4F 50 51 52 53 54 55 56 57 58 59 5A
---
Zounds! Patterns already! Note how the first letters of the
doubles change at both 'P' in the encoded and ASCII. I decided
that I'd need a larger corpus of data if I intended to crack the
scheme, so I constructed the table in section 7.
If you've looked down at section 7, you might be wondering why I
did so much work. Initially, I didn't really expect a pattern;
the encoding is different for every position in the string: just
because "BE" translates to ASCII "0" in the first position
doesn't mean that it'll translate the same way in the second
position -- there's more to it than that. So, to avoid confusion
on my part, I just took a large amount of data. Using the
information in section 7, I made tables of LSNs.
By now, I'd decided that the encoding scheme merely encoded the
ASCII values of the cleartext password. So, since 'A' is ASCII
code 0x41, the encoding scheme encoded '4' (the MSN) into a value,
and '1' (the LSN) into a value.
The tables may be confusing; I'll explain what they mean and how
to use them. For example, take the double "PF" in position 5 --
this gives us the LSN 'F' -- the leftmost column indicates the
position of the double, while the top row indicates the nibble
associated with that LSN. LSB 'F' in position 5 means that the
LSB for the unencoded 5th character is 0x4.
---
Table L1: LSN encodings for 0x0-0x3 per position
0x0 0x1 0x2 0x3
1 C D A B
2 E F G H
3 I J K L
4 A B C D
5 B A D C
6 C D A B
7 F E H G
8 L K J I
9 H G F E
10 O P M N
11 N M O P
12 K L I J
13 E F G H
14 I J K L
15 A B C D
16 B A D C
Table L2: LSN encodings for 0x4-0x7 per position
0x4 0x5 0x6 0x7
1 G H E F
2 A B C D
3 M N O P
4 E F G H
5 F E H G
6 G H E F
7 B A D C
8 P O N M
9 D C B A
10 K L I J
11 J I L K
12 O P M N
13 A B C D
14 M N O P
15 E F G H
16 F E H G
Table L3: LSN encodings for 0x8-0xB per position
0x8 0x9 0xA 0xB
1 K L I J
2 M N O P
3 A B C D
4 I J K L
5 J I L K
6 K L I J
7 N M P O
8 D C B A
9 P O N M
10 G H E D
11 F E H G
12 C D A B
13 M N O P
14 A B C D
15 I J K L
16 J I L K
Table L4: LSN encodings for 0xC-0xF per position
0xC 0xD 0xE 0xF
1 O P M N
2 I J K L
3 E F G H
4 M N O P
5 N M P O
6 O P M N
7 J I L K
8 H G F E
9 L K J I
10 C D A B
11 B A D C
12 G H E F
13 I J K L
14 E F G H
15 M N O P
16 N M P O
---
After going through all of those values, I noticed that the
encoding scheme wasn't the same for the MSBs as it was for the
LSBs (had it been, I think I could have saved a couple hours of
work). So, still with the information in section 7, I decided
to construct the tables for the MSNs as well:
---
Table M1: MSN encodings for 0x0-0x3 per position
0x0 0x1 0x2 0x3
1 E F G H
2 I J K L
3 A B C D
4 B A D C
5 C D A B
6 E F G H
7 I J K L
8 A B C D
9 B A D C
10 C D A B
11 F E H G
12 L K J I
13 H G F E
14 O P M N
15 N M P O
16 K L I J
Table M2: MSN encodings for 0x4-0x7 per position
0x4 0x5 0x6 0x7
1 A B C D
2 M N O P
3 E F G H
4 F E H G
5 G H E F
6 A B C D
7 M N O P
8 E F G H
9 F E H G
10 G H E F
11 B A D C
12 P O N M
13 D C B A
14 K L I J
15 J I L K
16 O P M N
Table M3: MSN encodings for 0x8-0xB per position
0x8 0x9 0xA 0xB
1 M N O P
2 A B C D
3 I J K L
4 J I L K
5 K L I J
6 M N O P
7 A B C D
8 I J K L
9 J I L K
10 K L I J
11 N M P O
12 D C B A
13 P O N M
14 G H E F
15 F E H G
16 C D A B
Table M4: MSN encodings for 0xC-0xF per position
0xC 0xD 0xE 0xF
1 I J K L
2 E F G H
3 M N O P
4 N M P O
5 O P M N
6 I J K L
7 E F G H
8 M N O P
9 N M P O
10 O P M N
11 J I L K
12 H G F E
13 L K J I
14 C D A B
15 B A D C
16 G H E F
---
After constructing those two sets of tables, I could already
convert an encoded password back to its original form, but I
_still_ wasn't satisfied. I was convinced that there were
patterns to the encoding table. So, for ease of viewing, I
constructed the following tables of encoding patterns:
---
Table E1: LSN encoding patterns, unsorted
CDAB GHEF KLIJ OPMN
EFGH ABCD MNOP IJKL
IJKL MNOP ABCD EFGH
ABCD EFGH IJKL MNOP
BADC FEHG JILK NMOP
CDAB GHEF KLIJ OPMN
FEHG BADC NMPO JILK
LKJI PONM DCBA HGFE
HGFE DCBA PONM LKJI
OPMN KLIJ GHEF CDAB
NMPO JILK FEHG BADC
KLIJ OPMN CDAB GHEF
EFGH ABCD MNOP IJKL
IJKL MNOP ABCD EFGH
ABCD EFGH IJKL MNOP
BADC FEHG JILK NMPO
---
Table E2: MSN encoding patterns, unsorted
EFGH ABCD MNOP IJKL
IJKL MNOP ABCD EFGH
ABCD EFGH IJKL MNOP
BADC FEHG JILK NMPO
CDAB GHEF KLIJ OPMN
EFGH ABCD MNOP IJKL
IJKL MNOP ABCD EFGH
ABCD EFGH IJKL MNOP
BADC FEHG JILK NMPO
CDAB GHEF KLIJ OPMN
FEHG BADC NMPO JILK
LKJI PONM DCBA HGFE
HGFE DCBA PONM LKJI
OPMN KLIJ GHEF CDAB
NMPO JILK FEHG BADC
KLIJ OPMN CDAB GHEF
---
There it is! The MSN encoding table _is_ the LSN encoding
table, rotated down four lines! A sorted ordering of the
encoding patterns verifies that the sets are, indeed, the same:
---
Table E3: Encoding patterns, sorted
ABCD EFGH IJKL MNOP
ABCD EFGH IJKL MNOP
BADC FEGH JILK NMPO
BADC FEHG JILK NMPO
CDAB GHEF KLIJ OPMN
CDAB GHEF KLIJ OPMN
EFGH ABCD MNOP IJKL
EFGH ABCD MNOP IJKL
FEHG BADC NMPO JILK
HGFE DCBA PONM LKJI
IJKL MNOP ABCD EFGH
IJKL MNOP ABCD EFGH
KLIJ OPMN CDAB GHEF
LKJI PONM DCBA HGFE
NMPO JILK FEHG BADC
OPMN KLIJ GHEF CDAB
---
Ultimately, this tells us something about our implementation of
this codec: we can use a 16x16 matrix to encode ASCII into this
in constant time, and the same matrix to decode, taking at most
32 steps per byte of decoded password. The absolute greatest
number of steps required to decode an encoded 16-character
password would be 256 steps. Note that this is all implemented
using a matrix, so our performance is still pretty high. I'll
provide pseudocode to handle en/decoding; assume we're given a
16x16 matrix populated with the LSN encoding table:
encode( password ):
for each password character
take character's MSN
take character's LSN
output value at (positionShifted, MSN)
output value at (position, LSN)
decode( encoded ):
for each pair of encoded characters
let first = first character
let second = second character
get MSN associated with (positionShifted, first)
get LSN associated with (position, second)
combine MSN and LSN to get clearChar
output clearChar
And there we go -- an amateur analysis of a shoddy encryption
scheme, complete with decoding table and pseudocode to do it all
yourself; enjoy!
---
[ 6. Conclusion ]
Four hours of work and a couple more hours of writing this are
now behind me. I conclude that the encoding scheme that AIM uses
is horrible. It's so horrible that I, a computer science student
with little-to-no experience in cryptanalysis, was able to break
the encoding scheme in around four hours.
If you let AIM save your password, don't. It's a Bad Idea(c).
---
[ 7. Table used for Analysis ]
Each entry in this table consists of three parts spread
over two lines. The first line has the password that
I entered into AIM and the corresponding ASCII code. The
second line has the encoded doubles of the password. There
are a _lot_ of strings here; surely more than a more
experienced cryptanalyst would have needed; I needed the
extra help.
)))))))))))))))) 0x29
GL KN CB DJ AI GL KM CC DO AH HE JD FN MB PJ II
0000000000000000 0x30
HC LE DI CA BB HC LF DL CH BO GN IK EE NI OA JB
9999999999999999 0x39
HL LN DB CJ BI HL LM DC CO BH GE ID EN NB OJ JI
@@@@@@@@@@@@@@@@ 0x40
AC ME EI FA GB AC MF EL FH GO BN PK DE KI JA OB
NNNNNNNNNNNNNNNN 0x4E
AM MK EG FO GP AM ML EF FJ GA BD PE DK KG JO OP
OOOOOOOOOOOOOOOO 0x4F
AN ML EH FP GO AN MK EE FI GB BC PF DL KH JP OO
PPPPPPPPPPPPPPPP 0x50
BC NE FI EA HB BC NF FL EH HO AN OK CE LI IA PB
QQQQQQQQQQQQQQQQ 0x51
BD NF FJ EB HA BD NE FK EG HP AM OL CF LJ IB PA
RRRRRRRRRRRRRRRR 0x52
BA NG FK EC HD BA NH FJ EF HM AP OI CG LK IC PD
SSSSSSSSSSSSSSSS 0x53
BB NH FL ED HC BB NG FI EE HN AO OJ CH LL ID PC
TTTTTTTTTTTTTTTT 0x54
BG NA FM EE HF BG NB FP ED HK AJ OO CA LM IE PF
UUUUUUUUUUUUUUUU 0x55
BH NB FN EF HE BH NA FO EC HL AI OP CB LN IF PE
VVVVVVVVVVVVVVVV 0x56
BE NC FO EG HH BE ND FN EB HI AL OM CC LO IG PH
WWWWWWWWWWWWWWWW 0x57
BF ND FP EH HG BF NC FM EA HJ AK ON CD LP IH PG
XXXXXXXXXXXXXXXX 0x58
BK NM FA EI HJ BK NN FD EP HG AF OC CM LA II PJ
YYYYYYYYYYYYYYYY 0x59
BL NN FB EJ HI BL NM FC EO HH AE OD CN LB IJ PI
ZZZZZZZZZZZZZZZZ 0x5A
BI NO FC EK HL BI NP FB EN HE AH OA CO LC IK PL
[[[[[[[[[[[[[[[[ 0x5B
BJ NP FD EL HK BJ NO FA EM HF AG OB CP LD IL PK
\\\\\\\\\\\\\\\\ 0x5C
BO NI FE EM HN BO NJ FH EL HC AB OG CI LE IM PN
]]]]]]]]]]]]]]]] 0x5D
BP NJ FF EN HM BP NI FG EK HD AA OH CJ LF IN PM
^^^^^^^^^^^^^^^^ 0x5E
BM NK FG EO HP BM NL FF EJ HA AD OE CK LG IO PP
________________ 0x5F
BN NL FH EP HO BN NK FE EI HB AC OF CL LH IP PO
```````````````` 0x60
CC OE GI HA EB CC OF GL HH EO DN NK BE II LA MB
aaaaaaaaaaaaaaaa 0x61
CD OF GJ HB EA CD OE GK HG EP DM NL BF IJ LB MA
bbbbbbbbbbbbbbbb 0x62
CA OG GK HC ED CA OH GJ HF EM DP NI BG IK LC MD
cccccccccccccccc 0x63
CB OH GL HD EC CB OG GI HE EN DO NJ BH IL LD MC
dddddddddddddddd 0x64
CG OA GM HE EF CG OB GP HD EK DJ NO BA IM LE MF
eeeeeeeeeeeeeeee 0x65
CH OB GN HF EE CH OA GO HC EL DI NP BB IN LF ME
ffffffffffffffff 0x66
CE OC GO HG EH CE OD GN HB EI DL NM BC IO LG MH
gggggggggggggggg 0x67
CF OD GP HH EG CF OC GM HA EJ DK NN BD IP LH MG
hhhhhhhhhhhhhhhh 0x68
CK OM GA HI EJ CK ON GD HP EG DF NC BM IA LI MJ
iiiiiiiiiiiiiiii 0x69
CL ON GB HJ EI CL OM GC HO EH DE ND BN IB LJ MI
jjjjjjjjjjjjjjjj 0x6A
CI OO GC HK EL CI OP GB HN EE DH NA BO IC LK ML
kkkkkkkkkkkkkkkk 0x6B
CJ OP GD HL EK CJ OO GA HM EF DG NB BP ID LL MK
llllllllllllllll 0x6C
CO OI GE HM EN CO OJ GH HL EC DB NG BI IE LM MN
mmmmmmmmmmmmmmmm 0x6D
CP OJ GF HN EM CP OI GG HK ED DA NH BJ IF LN MM
nnnnnnnnnnnnnnnn 0x6E
CM OK GG HO EP CM OL GF HJ EA DD NE BK IG LO MP
oooooooooooooooo 0x6F
CN OL GH HP EO CN OK GE HI EB DC NF BL IH LP MO
pppppppppppppppp 0x70
DC PE HI GA FB DC PF HL GH FO CN MK AE JI KA NB
qqqqqqqqqqqqqqqq 0x71
DD PF HJ GB FA DD PE HK GG FP CM ML AF JJ KB NA
���������������� 0x80
MC AE II JA KB MC AF IL JH KO NN DK PE GI FA CB
���������������� 0x93
NB BH JL ID LC NB BG JI IE LN MO CJ OH HL ED DC
���������������� 0xA2
OA CG KK LC ID OA CH KJ LF IM PP BI NG EK HC AD
���������������� 0xB0
PC DE LI KA JB PC DF LL KH JO ON AK ME FI GA BB
���������������� 0xC0
IC EE MI NA OB IC EF ML NH OO JN HK LE CI BA GB
���������������� 0xD0
JC FE NI MA PB JC FF NL MH PO IN GK KE DI AA HB
���������������� 0xE0
KC GE OI PA MB KC GF OL PH MO LN FK JE AI DA EB
���������������� 0xF1
LD HF PJ OB NA LD HE PK OG NP KM EL IF BJ CB FA
---
[ 8. Thanks ]
Neil -- Thanks for reminding me about that alt+0xyz stuff.
---
Copyright (c) 2000 Stephen Anthony Uy <[EMAIL PROTECTED]>
[EOF]
=====8<=====CUT=====8<=====
email.(ROT-13)[EMAIL PROTECTED]
aim...........................................tsanth
homepage.......................http://www.tsanth.com
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
