As some of you may know, name colors in Mabinogi are not random. The color of your name is related to the text of your name. One can use tools like this to see what color a name is. But how is the color calculated, and can we exploit it at all?
[SIZE="4"]Your Good Name:[/SIZE]
Up till now, you may have taken text on your computer for granted, not sparing a thought for how it works. You hit a button on your keyboard, text shows up on the screen. Easy, right? Well, not exactly. Computers are number machines. How do you turn a letter into a number, so the computer can understand it?
The answer lies in something called a 'codepage'. UTF8 and ASCII are the most common examples of codepages. Basically, with a codepage, every letter has a number that represents it. For example, 'A' is represented by 65. See this link for more codes.
Now for some computer-specific terminology: Computers think of text (called a 'string') as a series of letters (called 'characters' or 'chars'), which are represented as numbers. So, where you see "Hello", the computer sees 72 101 108 108 111.
[SIZE="4"]Hash Functions:[/SIZE]
A hash function is simply a function that takes some input and calculates a number from it. Hash functions are used a lot in computers, for everything from passwords to quality checks. What we're interested in, though, is the hash function that Mabinogi uses on names to turn them into a color.
A Python implementation of the algorithm is in the spoiler tags, but I'll quickly describe its main features below.
[SPOILER="Code"][CODE]def hash(name):
color = [0,0,0] #r, g, b
for i in range(len(name)):
color[i % 3] += ord(name[i])
#endfor
color[0] = (color[0] * 101) % 97 + 159
color[1] = (color[1] * 101) % 97 + 159
color[2] = (color[2] * 101) % 97 + 159
return color [/CODE][/SPOILER]
First, the algorithm converts your name to the numbers it's represented by. Then, it adds up the 1st, 4th, etc characters to get the R component. It adds the 2nd, 5th, etc, to get G, and likewise with B.
Next, each component is multiplied by 101 (A prime number, common in hash functions) and then taken modulo 97. Finally, 159 is added to the component.
The components are combined to get the final color code.
[SIZE="4"]What the Hash Tells Us:[/SIZE]
We can derive some interesting properties from this hash.
First off, the position of a letter in your name controls which color component it impacts. This also explains why Mabi names must be at least 3 characters.
Due to the modulo and addition, each component can only be in the range of 0x9F-0xFF, which rules out dark colored names, like black.
There are (97)^3 possible name colors. This is 912, 673. At first glance, you might think that everyone gets their own name color. However, something called the Birthday Paradox is working against you. Basically, due to the laws of probability explained here, the chances of multiple people having the same name color looks like this:
[Image: http://i.imgur.com/X5thYRa.png]
As you can see, the probability rises dramatically with the number of players. By about 1,000 players, the probability that two players share a color is 50%. By 4,000, it's all but certain.
[SIZE="4"]Exploiting the hash:[/SIZE]
Now that we've looked at the hash in detail, the obvious question is, "can we use our knowledge to manipulate the input to get a desired output?" With good (or cryptographic) hashes, the answer is "No". However, this is not a good hash. Let's review what might help us:
- We know the output range
- We know the input (3~12 alphanumeric characters)
- By math, (a * 101) % 97 is the same as 4a % 97. This is a huge insight, as you'll see later.
- We know that the R, G, and B outputs depend on specific positions. This is also huge.
I've included an example of using this knowledge to break the hash below. Unfortunately, the exploits we can do are limited by the input. There's only so much you can do with 62 letters and a length of 12.
[SIZE="4"]Example exploit: Finding a name given a color[/SIZE]
Let's say that we really like the color white. Specifically, 0xFFFFFF. This means that every component is 0xFF, or 255 in decimal. Since we want them all the same, we just need to find one. I'll pick R, because it's my favorite.
So, we know that R = 255. Now, we just need to work backwards through the hash algorithm. First, 255 - 159 is 96. This means that we need a number a such that 4a % 97 = 96. Now we need to solve for a.
I was lazy and did it the poor man's way, AKA "guess and check". It turns out that 121 is a valid solution to that equation. At this point, we know that we need a name where the 1st, 4th, etc, characters sum to 121.
A quick check of our UTF8 codepage indicates that the letter 'y' has a value of 121. No need to add any other characters. Jackpot! We now know that, to get a value of 255 for the R component, 'y' will do the trick. We can apply this same logic to the G and B, as well.
So, in theory, the name "yyy" should produce the color 0xFFFFFF. A quick run through the simulator, and...
[Image: http://i.imgur.com/iE9HSQ7.png]