Pokemon Mystery Dungeon DX Friend Password Documentation

pokemon-mystery-dungeon-dx-friend-password-documentation.md

Pokemon Mystery Dungeon DX Friend Password Documentation

Almost all of this was done by reading the disassembly and no debugging tools, so some of this may change over time as more info is found.

This document primarily covers reading the password since creating a password is the exact same process, but in reverse.

Note: There are screenshots in the first comment of this gist which may be good to look at if you don't know much about the game.

Notable locations in the binary

Please note: While the game had some symbols, not everything had symbols, so some of these names are given by me.

Name	Description	Location
JobTicket vtable		.data + 0x3b0ee8
FriendRescueTicket vtable	Inherits from JobTicket	.data + 0x3b0d78
FriendRescueTicket::Serialize	The result is converted to the symbols shown to the player	.text + 0x2812970
FriendRescueTicket::Deserialize	The input of this is provided by players as the rescue password	.data + 0x3b0dd0
DecryptPassword	Includes unshuffling the bytes	.text + 0x264a620
EncryptPassword	Includes shuffling the bytes	.text + 0x264a0a0
GRandom (.NET PRNG)	.NET PRNG or a variant (which makes sense for a Unity game)	.text + 0x2672a60
BitStream vtable		.data + 0x393088
BitStream::ChangeMode	The second argument is mode: 0 = NONE, 1 = READ, 2 = WRITE. This can help determine if a function is writing or reading data	.text + 0x2862bc0
CalculatePasswordHash(?)	Used to seed the RNG and validate the password	.text + 0x2830350
UnpackPassword	Converts a character from the character table to a symbol for the user to see, and splits the data into 6 bit chunks. Used when serializing a password - potentially for obfuscation	.text + 0x264a4b0
PackPassword	Converts an input symbol to a character from the character table, and puts the 6 bit chunks back into 8 bit bytes. Used when deserializing a password	.text + 0x264aa60
characterTable	Used to convert to/from the symbols a player sees	.rodata.1 + 0xc7ef85

Friend Rescue Password Structure

Note: this is the structure after and before serializing. During serialization/deserialization, the data is shifted by 8 bits, and the first byte is a hash used to seed the decryption RNG and validate the data. Due to this, part of the junk data at the bottom of the structure gets cut off when serializing/deserializing.

The data is stored using a bitstream.

Name	Notes	Offset (bits)	Length (bits)
Timestamp	Used to invalidate a password after 7 days	0	32
Unknown Flag	Serialization mode?	32	1
Unknown Flag	Always set to 0?	33	1
Team Name		34	88 (11 bytes)
Dungeon Floor		122	7
Dungeon Id		129	7
Pokemon Species	Last Pokemon who fainted	136	11
Reward		147	2
Unknown		149	2
Junk data	Alternating 1's and 0's depending on whether the bit offset is odd or even, probably to hide multiple zeroes when shuffling/encrypting	151	-

Deserializing

1. Get the friend rescue password from a user's input
   • Each character given by the user is one byte, for a total of 30 bytes
2. Unshuffle the characters using the method below
3. Convert the user's input to utf16 characters using the method below
4. Pack the bits using the method below
   • The result should now be 23 bytes (22.5 bytes of used data)
5. Decrypt the password using the method below
   • Validate the lower byte of the RNG seed matches the calculated hash
6. Copy the data into a bitstream
7. Read the data from the bitstream
8. Validate the data (Ex: Is the Pokemon species under 493, is the dungeon floor under 100, etc. Occurs at the bottom of FriendRescueTicket::Deserialize)

Converting User Input Symbols to Internal Characters

There are 65 symbols a user can use to enter a friend rescue password. Going from left to right, top to bottom, these symbols are assigned numbers from 0-64.

For example "1 Fire" is 0 and "5 Water" is 30.

These numbers are the indexes to the previously mentioned internal character table.

(Hint: You may have noticed something off about this like I did - read the "Fun Facts" section below!)

Packing bits

The serialized data is about 22.5 bytes total (with some junk data at the end), but is unpacked to be 30 bytes before encrypting to display to the user. This is probably a way to obfuscate the data.

1. Put the 22.5 bytes of friend rescue data in a bit stream
2. Use the bit stream to break the data into chunks of 6 bits
   • 22.5 bytes * 8 bits = 180 bits
   • 30 bytes * 6 bits = 180 bits

Decrypting

This occurs during deserialization.

1. Seed the RNG with the first two bytes of the password
2. Get the current character of the password (start from index 2)
3. Advance the RNG to get a random number
4. Subtract the random number from the current character
5. Write the new value back to the byte array of the same index
6. Iterate over the rest of the byte array and repeat steps 2-5
   • Note: At index 22 (the 23rd byte), zero out the first four bits: arr[22] = (arr[22] - rand) & 0xf. This is because there are 22.5 bytes of actual data used
7. Starting from offset 1, calculate the password hash and compare to the first byte of the encrypted password to validate the data
8. Copy the decrypted data into a new bitstream, starting from offset 1
   • The hash byte is no longer used after this

Encrypting

This occurs during serialization. Even though this document primarily covers deserializing, I thought it was also important to mention how the RNG seed is created for encryption.

Since serialization is the opposite process of deserialization, we start with a bitstream of the friend rescue data.

1. Copy the friend rescue data into a new buffer starting from offset 1
   • This means offset 0 is empty
2. Get a one byte hash of the data, starting from offset 1
3. Store the hash byte at offset 0 of the buffer
4. Use the first two bytes of the buffer to create the RNG seed: buffer[0] | (buffer[1] << 8)
5. Seed the RNG
6. Get the current character of the password (start from offset 2)
7. Advance the RNG to get a random number
8. Add the current character to the random number
9. Write the new value to the same spot in the buffer

Unshuffling

1. Create a new array
2. newArray[unshuffledIndex] = originalArray[shuffledIndex]

Shuffled index	Unshuffled index
0	3
1	0x1b
2	0xd
3	0x15
4	0xc
5	9
6	7
7	4
8	6
9	0x11
10	0x13
0xb	0x10
0xc	0x1c
0xd	0x1d
0xe	0x17
0xf	0x14
0x10	0xb
0x11	0
0x12	1
0x13	0x16
0x14	0x18
0x15	0xe
0x16	8
0x17	2
0x18	0xf
0x19	0x19
0x1a	10
0x1b	5
0x1c	0x12
0x1d	0x1a

Fun facts

• Since each code is 6 bits, there are only 64 possible characters that can be used (0-63), but there are 65 characters in the symbol table. "X Star" is never used for passwords
• Certain letters that are easily mistaken for numbers are removed from the internal character table (ex: "l" and "o"). Since these are never shown to the user, this hints the internal character table could have been used for debugging purposes
• The game uses .NET's PRNG (or a variant), however there's also a linear congruent PRNG with the same interface. The vtable is at .data + 0x3915C8

I'm glad I can help!

The default next method is correct, and you'll want the lower 8 bits of the difference.

Oops - hash isn't quite the right word to use here (I'll have to update the above docs). If I recall correctly, calculating the first byte of the seed is done by getting the sum of all the bytes starting from offset 1, then getting the result of ~(sum + (sum >> 8)) & 0xff. Afterwards, the game makes sure this value is equal to the first byte of the array.

Thanks! Two followups:

• is the seed correct, just the integer represented by the first 16 bits?
• does "the lower 8 bits of the difference" mean lower eight bits of a two's complement representation of the negative numbers produced, or is there something else here?

1. Yep, that should be correct
2. Since each element in a byte array holds a single byte, it's effectively casting the difference of the encrypted byte from the random number to a single byte

Right, okay, thanks. I apologize for the lengthy message, but I would appreciate it if you could check my work / implementation of this test case.

The password is below, and you can see the rescue details here:

Pf8sPs4fPh Xe3f7h1h2h 5s8w3h9s3f
Xh4wMw4s6w 8w9w6e2f8h 9f1h2s1w8h

My understanding of the deserialize method:

• unshuffles the code
• converts each of 30 symbols into 6 bits, then mushes them together into a 180-bit string
• splits that into 22 full bytes + 1 half byte
• takes the first 2 bytes to seed the RNG
• for index 2 - 21, get a random number, subtract it from that byte, take the lower eight bits, put them in that position in the array
• and for index 22, do the same but keep only the bottom 4 bits (this isn't affecting anything yet)
• do some hash stuff I haven't implemented yet

I believe that, after unshuffling, the rest of deserialization leaves bytes 0 and 1 unchanged. We then drop the first byte and copy the remaining 172 bits into a bitstream, and that should be the deserialized data.

The most basic issue is that the timestamp isn't right; the first eight bits of the timestamp from the link above (1586811085) should be 0101 1110, but with my implementation we get 0111 0000. The timestamp I get in practice is in 2029, which is obviously wrong.

That first byte should be the same as the second byte of the encrypted password, since the RNG procedure doesn't affect the first two bytes. The encrypted password is just the original password after being unshuffled, whose first three characters are characters 17, 18, and 23 of the original password, which are Mw 4s 2f => alphabet positions 36, 55, 1 => binary 100100 110111 000001. Reinterpreting this as two bytes + change gives us 1001 0011 [0111 0000]. That's not what the leading byte of the timestamp needs to be.

I apologize for the copious amount of detail, but I'm wondering if you're able to spot the hole in what I'm doing here. My guess is that it's from either the RNG procedure (am I taking the lower 8 bits correctly?) or from converting the byte array into a bitstream at the end, but I am not sure; the RNG shouldn't affect the leading byte of the timestamp, at the very least. My implementation is here; I'd appreciate any help.

Hey, sorry for the late response.

The only thing I noticed was how the seed is getting created here - https://github.com/tuchandra/pmdrtdx/blob/master/rescue.py#L323

The switch uses little endian. When using little endian, reading a uint at index 0 from a byte array of [0x01, 0x02, 0x03, 0x04] will result in 0x04030201. It looks like the seed from line 323 may need to have index 0 and 1 swapped so that seed = (byteArray[1] << 8) | byteArray[0].

Aside from that, I'm not able to spot any other issues at the moment.

Ah thanks!

That makes sense. I found a reference implementation here that was just posted, and staring at that helped me uncover a few more errors as well.

Thanks so much for your help!