Odd password scrambling algorithm

Question

I'm researching an application that has password scrambling algorithm that I've not seen before. I generated a few passwords (the max. length allowed is 8 chars), and got the following results:

password:     0  0  0  0  0  0  0  3
scrambled:    W1 U6 W1 U6 W1 U6 W1 X2

password:     0  0  0  0  0  0  0  2
scrambled:    W1 U6 W1 U6 W1 U6 W1 M7

password:     0  0  0  0  0  0  0  1
scrambled:    W1 U6 W1 U6 W1 U6 W1 F2

password:     0  0  0  0  0  0  0  0
scrambled:    W1 U6 W1 U6 W1 U6 W1 U6

password:     1  2  3  4  5  6  7  8
scrambled:    H9 G6 B5 G3 F8 Q7 X8 O9

The scrambling is clearly reversible. I'm thinking worse comes to worse I could generate a dictionary mapping but I'm thinking there'd be a cleverer way of going about this.

Has anyone encountered something like this before?

Update

More Values and noted:

• 0 behaves quite differently than other characters
• @ is also noteworthy (constant at every position)
• algorithm can't or won't process passwords of less than 3 chars

4  4  4  4  4  4  4  4
A2 S5 K9 G3 Y6 U0 M4 E8

3  3  3  3  3  3  3  3
L4 Z5 B5 R1 R5 F7 H6 X2

2  2  2  2  2  2  2  2
W6 G6 S0 C0 K4 U3 C8 M7

1  1  1  1  1  1  1  1
H9 N6 F6 J8 D3 J0 B0 F2

1  0  0  0  0  0  0  3
H9 U6 W1 U6 W1 U6 W1 X2

a  b  a  b  a  b  a  b
H1 E3 B8 W6 Z4 S0 X1 K4

b  b  b  b  b  b  b  b
S8 E3 O2 W6 G6 S0 C0 K4

a  a  a  a  a  a  a  a
H1 L3 B8 H5 Z4 D7 X1 Z8

A  B  C
N6 C0 L0

B  B  B  B  B  B  B  B
M7 Y1 I1 Q5 A5 I9 S8 E3

A  B  A  B  A  B  A  B
B0 Y1 V6 Q5 T3 I9 R0 E3

A  A  A  A  A  A  A  A
B0 F2 V6 B4 T3 X5 R0 T7

A  A  A  A  A  A  A
J0 B0 F2 V6 B4 T3 X5

A  A  A  A  A  A
D3 J0 B0 F2 V6 B4

A  A  A  A  A
J8 D3 J0 B0 F2

A  A  A  A
F6 J8 D3 J0

A  A  A
N6 F6 J8

@  @  @  @
M2 M2 M2 M2

#  #  #  #
P2 B9 F3 T4

*  *  *  *
A9 A1 U7 Q9

!  !  !  !
Z4 D7 X1 Z8

General rule for a brute-force approach to un-scrambling these passwords:

In a string of length L, a given char at position N will always have the same value.

IE: In 8 character long passwords, if the first char is A, it will always be encoded the same way.

NB: I've figured out the "brute-force" way of unscrambling these, but I would love to know the algorithm used for scrambling the passwords. If anyone has experience on reversing these kind of things I would love some tips on how to proceed from here.

Answer 1

Many of the tips I'm about to suggest require excessive use of the scrambler. They're not dictionary attacks, but they do include a lot of password scrambling for the purpose of collecting data. If your goal is to do this without too many test probes against the function, or you are not able to do it, i don't really have many tips.

Integers

Integers are easy to work with, and anyone who implements a scrambling of their own would probably be operating on integers, not strings. Finding a correspondence between the two symbol tokens (J8, D9, etc.) and integers could be crucial. Since all numbers and letters are represented there are 26*20=260 different tokens to work with. 260 is comfortably close to 256, which might suggest that the tokens are just an encoding for bytes.

The intuitive approach is to interpret Xn as 10*X+n, where X is the index of the letter X and n an integer between 0 and 9. This is ruled out by the token Z8 which would correspond to the integer 258, which is too large for a byte. In a similar manner several other encodings can be ruled out, at least these simple linear combinations:

b = 10*X + n
b = 10*(26-X) + n
b = (26-X) + 26*n
b = 10*(26-X) + (9-n)
b = (26-X) + 26*(9-n)

In order to rule out the guesses for encoding that we do, knowing what tokes appear in the scrambles is very helpful. If the tokens are an encoding for bytes, then there should be 260-256=4 tokens that don't ever appear. Finding these tokens could give valuable hints. If all tokens do occur at some point, that'd be a valuable hint as well.

Boxes

The scrambles for the passwords ('AAA', 'AAAA', 'AAAAA' ...) give us useful information. We can by observing deduce that the scrambling function for a single symbol is a function f(symbol, integer) -> token where the integer i is the sum of the length of the password and the index of the symbol. Eg. f(A, 4+1) = f(A, 3+2) = J8. In general f(symbol, length + index) is constant for all lengths and indexes.

A  A  A  A
F6 J8 D3 J0

A  A  A
N6 F6 J8

Since the password is limited to 8 symbols, we have 8+8 = 16 different scrambling functions g_n(symbol) -> token to find. Whether these functions are dependent on the integer 'n' (ie. length + index) is hard to establish from the available data. The functions g_n could be implemented as lookup tables and follow no pattern at all.

@

The @ character has me stumped, but maybe it is for recognizing scrambled email addresses. Email addresses are longer that 8 symbols and could imply that the scrambling works with longer input as well, which in it's turn would suggest that the functions g_n are dependent of n (theorem of laziness, nobody makes more than 16 random lookup tables)

Building the lookup tables

This could be done by simply scrambling all passwords aa...a, bb...b ... ^^...^, and using the relationship of length and position to decide which function g_n the scrambled result belongs to. This data will also help in finding out what and how the tokens encode data.

Looking at the tables

If we built tables for all repeating alphabetic passwords of length 8, ie. aaaaaaaa, bbbbbbb, etc. we could visualize the scrambled results as an 8x26 image. Humans are good at looking images so the most simple things (such as linearity) are easily seen from the image. Looking for horizontal, vertical, square or diagonal artifacts in an image can say a lot about the algorithm used to scramble the passwords. This approach is very organic and requires some scripting/programming skills.

My visualization approach would be the following:

• generate scrambles for all passwords of 8 repeating ASCII characters (or bytes, if possible)
• convert the tokens into bytes using some simple scheme (eg. a linear combination)
• save the bytes as a binary file bytes.gray
• use the ImageMagick convert utility: convert -size 8x256 -depth 8 bytes.gray bytes.png
• look at the image and try to find patterns

Answer 2

This sequence:

a  b  a  b  a  b  a  b
H1 E3 B8 W6 Z4 S0 X1 K4

b  b  b  b  b  b  b  b
S8 E3 O2 W6 G6 S0 C0 K4

a  a  a  a  a  a  a  a
H1 L3 B8 H5 Z4 D7 X1 Z8

tells that there is a key being used to scramble the input password, much like XOR, except most uses of XOR would output in hex while this output is base36?

This sequence

A  B  A  B  A  B  A  B
B0 Y1 V6 Q5 T3 I9 R0 E3

A  A  A  A  A  A  A  A
B0 F2 V6 B4 T3 X5 R0 T7

A  A  A  A  A  A  A
J0 B0 F2 V6 B4 T3 X5

A  A  A  A  A  A
D3 J0 B0 F2 V6 B4

makes me think there are different keys for different length strings.

So, I'm guessing the algorithm takes the plaintext 'a', takes the ascii value of 'a' (97) converts it to base36 (2P), XORs it with the respective value in the key and gives the base36 value of H1.

EDIT: it doesn't appear to be base36. Whatever the encoding scheme in use, I'm still guessing that it uses XOR. It would help explain the behavior of zero since zero XORed with X is always X.

If that is true, the process is reversible and the keys can be found, removing the need to brute force or make lookup tables.