Protocols/MSNP/MSNP11/Challenges

From NINA Wiki
Revision as of 10:47, 13 May 2022 by Animadoria (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
MSNP Protocol
Version 11
Overview • Challenges
Changes • Example Session
Overview
Introduction • Terms • Clients
Reference
Error List • Commands • Relying Party Suite • Spotlife
Services
XMPP • HTTP Gateway • Tabs • Activities
Documentation
Development Tools • MSNP Grid
Polygamy • URLs used by MSN
Documents
Protocol Versions
Version 21
Version 18
Version 16
Version 15
Version 14
Version 13
Version 12
Version 11
Version 9
Version 8
Version 2
MSNC
Introduction • P2P • Object Descriptor • Display Pictures • File Transfer
Scenarios
Microsoft Messenger for Mac
MSNP on WebTV (MSNTV)


Overview

This section tries to explain how to build your own implementation of the new challenge algorithm which was introduced in MSNP11. All protocol versions that were introduced after MSNP11 (MSNP12, ...) use the same algorithm. Though it was developed mainly for legal reasons and to keep out unwanted guests, it has been reverse engineered.

As you read through this document, we assume that you have basic knowledge about how to handle big data types in your programming language, how Endian orders work, what DWords and QWords are and how to perform logical bitwise operations like xor and and.

Also, your programming language must be able to handle 64 bit integers, the MD5 hashing algorithm and several basic math functions. While a lot of languages, like Visual Basic, Perl and PHP, don't support 64 bit integers by default, it is most of the time possible to build an own implementation for it or by using additional functions which do support them.

Now back to the topic. The new algorithm can be divided in some (small) steps. These steps will be carefully explained to you in the next few sections. Don't be afraid if you lack some knowledge of the things handled in this section, because most of the time the contents are well enough to guide you through the process.

Step 1: The MD5 Hash

The first step in the process of creating the challenge response is creating an MD5 digest from the input string from the server (sent with the CHL command), and a special key, called the "Product Key". For MSNP11, the new Product Key you have to use when creating this hash is YMM8C_H7KCQ2S_KL. At time of writing this Product Key is still valid, even for MSNP12.

Throughout this section, we assume that the received challenge data is 22210219642164014968. It will be used in every example and at the end you will have the right new challenge hash for this data so you can verify your own implementation.

Logically, your hash would look something like this:
md5Hash = MD5_Hex("22210219642164014968YMM8C_H7KCQ2S_KL"); // "ec4917aa5b3017159e3947f8ff981604"

After you have generated this hash you should store it in an array, with each element having a size of 8 bytes. Because the size of the MD5 hash is 32 bytes, you will get 4 elements. Then you can treat each element as a regular hexidecimal number (0xec4917aa, 0x5b301715, 0x9e3947f8, 0xff981604).

These hexadecimal numbers should be written in Little Endian order, this means that you should swap the bytes around in a number of languages (for example PHP and C#, but not Perl and Visual Basic) in order to have access to the values of these integers. You should also take in account the default Endian Order of the system you are working on (for example, Intel machines are LE, while Apple machines are typically using BE).

Once you have stored them in the array, and have converted each of the elements to regular numbers (32 bit unsigned) you should logically AND them with 0x7FFFFFFF. If you want to test if your code correctly swaps the bytes around (if needed) and if the MD5 hash is getting divided correctly, then you could compare them with these values:

1: 0x2a1749ec = 706169324
2: 0x1517305b = 353841243
3: 0x7847399e = 2017933726
4: 0x041698ff = 68589823

After this, the first step is complete and you can proceed to the next step.

Step 2: A new string

The second step in the process is going to make use of the so called "Product ID", which is also sent along in each QRY preceding the challenge hash. The developers at Microsoft figured that they could use this string to create a key out of it. Though this step is fairly simple and re-assembles a lot of the previous steps, we are going to have a look at it.

First, take the challenge data (remember, in our case this is 22210219642164014968) and append the Product ID (PROD0090YUAUV{2B for MSNP11 and onwards) to it. Then you need to make this strings length a multiple of 8 by appending "0"'s to the end (a "zero", NOT a "null" character!). In most language this can be achieved by adding "8 minus (length of string modulo 8)" zeros to the end of the string.

The challenge data appended with the Product ID and zeros:
chlString = "22210219642164014968PROD0090YUAUV{2B";
chlString += new String("0", 8 - (chlString.Length % 8)); // "22210219642164014968PROD0090YUAUV{2B0000"

This time you should not split the string into pieces of 8 bytes, but in pieces of 4 bytes. These pieces should be converted to regular numbers too. However, in this case the chunks do not reassemble a hexidecimal number, but a number in base 255 (in other words, a "DWord" in textual representation). You can convert each chunk by taking its HEX notation and converting that to a number (ie. in the above code, 2221 should be represented as 32323231 in HEX notation, and thus as 0x32323231 as a hexidecimal number).

As with step 1 you should check for the Little Endian order, if necessary. Below is a list of hexidecimal and decimal values of the example above (when converted):

2221: 0x31323232 = 825373234
0219: 0x39313230 = 959525424
6421: 0x31323436 = 825373750
6401: 0x31303436 = 825242678
4968: 0x38363934 = 943077684
PROD: 0x444f5250 = 1146049104
0090: 0x30393030 = 809054256
YUAU: 0x55415559 = 1430345049
V{2B: 0x42327b56 = 1110604630
0000: 0x30303030 = 808464432

If you are done with this, the second step is completed as well and you can proceed to the next step.

Step 3: The 64 bit key

In the third step in the process we are going to create a key based on the data from the previous step. At the bottom of the page you can find this whole step in pseudo code, if some things are not clear by then. The documentation below assumes you have created an array in the previous step, but if you haven't then you'll need to improvise a bit. Though it is highly recommend you do create an array in the previous step, because it will make it way easier in this step.

In the function or subroutine you are making, you need to add two variables. Both of them should have 0 as initial value. The first will be called "High" and the second will be called "Low". Then you should create a loop which walks over each two elements of the array, to keep things simple we will call the current element "N" and the element after it "N + 1".

In the loop you should create a temporary variable and fill it with the value of piece N, which then should be multiplied by 0x0E79A9C1 (decimal 242854337). To prevent the number from overflowing and/or becoming negative (signed vs. unsigned integers) you need to modulate the number by 0x7FFFFFFF. If you have done that, you need the add the value of the variable "High" to it (which will be 0 the first run). The second thing you need to do is to multiply it by the value of the first piece of the MD5 hash (0xec4917aa in our example) and add the second piece of the MD5 hash (0x5b301715 in our example) to it. To keep it from overflowing again, you should modulate it by 0x7FFFFFFF. 

A small snippet of pseudo code what we have done yet:

int high = 0;
int low = 0;

for (int i = 0; i < chlStringArray.Length; i = i + 2) {
  int temp = chlStringArray[i];
  temp = (0x0E79A9C1 * temp) % 0x7FFFFFFF;
  temp += high;
  temp = md5hash[0] * temp + md5hash[1];
  temp = temp % 0x7FFFFFFF;

  ...

}

Next, we need to calculate the high part of the key. This can be done by filling the variable "High" with the value of piece N + 1 (this is also why you need to walk over each two elements). Then we need to add the value we just generated in the temporary variable to it and, you guess it, you keep it from overflowing we should modulate it by 0x7FFFFFFF again. After this you should multiply it by the value of the third piece of the MD5 hash (0x9e3947f8) and add the fourth piece of the MD5 hash (0xff981604) to it. Again, modulate it by 0x7FFFFFFF after this.

At the end of the loop you should add the values from the variable called "High" and the temporary variable to the variable called "Low", you should not modulate this number by 0x7FFFFFFF! As a result of that, the variable "Low" can reach values which are bigger then 32 bits. To handle these big numbers, you can use the BCMath functions in PHP and the BigInt modules in Perl or just the data type long in C#. 

A small snippet of pseudo code for the second part:

for (int i = 0; i < chlStringArray.Length; i = i + 2) {

  ...

  high = chlStringArray[i + 1];
  high = (high + temp) % 0x7FFFFFFF;
  high = md5hash[2] * high + md5hash[3];
  high = high % 0x7FFFFFFF;

  low = low + high + temp;
}

We are now almost done. After the loop, you need to add the second piece of the MD5 hash (0x5b301715) to the variable "High" and the fourth piece (0xff981604) to the variable "Low". Afterwards, you need to modulo both variables again with 0x7FFFFFFF.

To create the key we are looking for, we should take a look at the variables called "High" and "Low". They have been named that way for a reason: they represent respectively the high and low order DWord values of a QWord (Quad Word, 64 bit integer). So if you want to create the key, you need to logically shift the value of the variable "High" 32 bits to the left and add the value of the variable "Low" to it. Note that both parts need to be in Little Endian order. You should verify your code with values in the example! 

The whole snippet of pseudo code to create the key:

int high = 0;
int low = 0;

for (int i = 0; i < chlStringArray.Length; i = i + 2) {
  int temp = chlStringArray[i];
  temp = (0x0E79A9C1 * temp) % 0x7FFFFFFF;
  temp += high;
  temp = md5hash[0] * temp + md5hash[1];
  temp = temp % 0x7FFFFFFF;

  high = chlStringArray[i + 1];
  high = (high + temp) % 0x7FFFFFFF;
  high = md5hash[2] * high + md5hash[3];
  high = high % 0x7FFFFFFF;

  low = low + high + temp;
}

high = (high + md5hash[1]) % 0x7FFFFFFF;
low = (low + md5hash[3]) % 0x7FFFFFFF;
// Gives high = 0x69A5A771 (1772463985 decimal) and low = 0xD4020628 (3556902440 decimal)

long key = (high << 32) + low;
// Gives 0x69a5a771d4020628 (7612674852469737000 decimal)

If your programming language has problems with 64 bit integers, then it may be convenient to ignore the last logical shift and leave the variables "High" and "Low" as to separate variables. If you still were able follow this, then you have completed the third step too and you can proceed to the final step.

Step 4: Using the key

In the final step in the process we are going to create the new challenge hash. Compared the the previous step, this step is fairly simple. Basically you only need to XOR the MD5 hash with the key you created it the previous step. Because there are two variations (a key of 64 bit or a high and low variable both of 32 bit) of this step, I will discuss them both here.

First, I'll start with the 64 bit key. To create the final hash, you need to split the MD5 hash in two parts (both 16 bytes long). These two parts represent the two QWords (64 bit integers) in hexadecimal notation, you can treat these QWords now as regular hexadecimal numbers without having to doubt about the Endian order. You should however check against the final result below, considering some server systems or machines might work different than expected.

Once you have the two parts of the hash you should XOR them with the freshly created key at the previous step. You then need to convert these numbers again to the hexadecimal string representation of it, without the prefixed "0x". If the string is less than 16 characters in length you need to prefix it with "0"'s (Again, zero's, NOT null characters). You are now done and have created the new hash. 

A small snippet of pseude code to create the new challenge hash:

hash = "ec4917aa5b3017159e3947f8ff981604";
hash = hash.Substring(0, 16).ToInt64() ^ key + hash.Substring(16, 16).ToInt64() ^ key;
// Gives "85ecb0db8f32113df79ce0892b9a102c"

Second, I'll discuss if you are using two 32 bit integers. To create the final hash, you need to split the MD5 hash in four parts (both 8 bytes long). These four parts represent the four DWords (32 bit integers) in hexadecimal notation, you can treat these DWords now as regular hexadecimal numbers without having to doubt about the Endian order. You should however check against the final result below, considering some server systems or machines might work different than expected.

Once you have the four parts of the hash you should XOR them with the freshly created variables "High" and "Low" at the previous step. You then need to convert these numbers again to the hexadecimal string representation of it, without the prefixed "0x". If the string is less than 8 characters in length you need to prefix it with "0"'s (Again, zero's, NOT null characters). You are now done and have created the new hash. 

A small snippet of pseude code to create the new challenge hash:

hash = "ec4917aa5b3017159e3947f8ff981604";
hash = hash.Substring(0, 8).ToInt32() ^ high + hash.Substring(8, 8).ToInt32() ^ low + hash.Substring(16, 8).ToInt32() ^ high + hash.Substring(24, 8).ToInt32() ^ low;
// Gives "85ecb0db8f32113df79ce0892b9a102c"

If you use the example values given in the previous steps, the hash should end up being 85ecb0db8f32113df79ce0892b9a102c. It's then being sent like any other hash would be: simply put it in the QRY with the Product ID, payload length (hash length, usually 32 bytes) and then your hash (Separated by a \r\n and no ending \r\n, of course).

Implementations

Example implementations of the MSNP11/12 Challenge Response are available:

MSN Messenger 7.0.0813

MSN Messenger 7.0.0813 uses :

  • Product Key = CFHUR$52U_{VIX5T
  • Product ID = PROD0101{0RM?UBW

Test values: 

Challenge               Response
13038318816579321232    5f6ae998b8fa70c37b62980f71a0e736
23055170411503520698    934ab429609709f4fe70e5fa930993c2
37819769320541083311    40575bf9740af7cad8671211e417d0cb
93662730714769834295    003ed1b1be3ca0d81f83a587ebbe3675
Retrieved from "https://wiki.nina.chat/index.php?title=Protocols/MSNP/MSNP11/Challenges&oldid=4340"