Keygen for eCDP

eCDP_keygen.py

#!/usr/bin/env python3

# Keygen for McDonald's eCDP(eCrew Development Program),
# a Nintendo DS software to train employees.
# This keygen is for the only dumped Japanese version of eCDP.
# ROM: https://archive.org/details/mcdonalds-japan-ecdp-rom-training-nintendo-ds-cartridge-dump

# Usage: Select the third option in main menu, enter two 6-digit numbers as you like,
# and use this script to calculate the third code.

def rol(n, rotation, width=32):
    rotation %= width
    if rotation == 0:
        return n
    n &= (2**width-1)
    return (n << rotation) | (n >> (width - rotation))

def gen_index(sum_offset, length):
    if length == 0:
        return 0
    if length <= sum_offset:
        count = 0x1c
        seed = sum_offset >> 4
        if length <= seed >> 0xc:
            count -= 0x10
            seed = seed >> 0x10
        if length <= seed >> 4:
            count -= 8
            seed = seed >> 8
        if length <= seed:
            count -= 4
            seed = seed >> 4

        # Doing bitwise operation in Python is painful...
        sum_offset = rol(sum_offset, count)
        sum_offset *= 2
        carry = (sum_offset & (2**32)) != 0
        for i in range(count, 32):
            seed = seed * 2 + (~length & 2**32-1) + 1
            seed += 1 if carry else 0
            carry = (seed & (2 ** 32)) != 0
            seed = seed & (2**32-1)
            if not carry:
                seed += length
                seed = seed & (2 ** 32 - 1)
            sum_offset *= 2
            carry = (sum_offset & (2 ** 32)) != 0
            sum_offset &= (2 ** 32-1)
        pass
        return seed
    else:
        return sum_offset

def gen_index_2(sum_offset, length):
    # Well, didn't expect that.
    return sum_offset % length

def calc_shorten_index(input_merge):
    hex_char = "0123456789ABCDEF" # located at 0x0225189c
    sum_offset = 0
    for c in input_merge:
        sum_offset += hex_char.index(c)
    return gen_index(sum_offset, 7)
    pass

def shuffle(input_merge, shuffle_index):
    # located at 0x02251948
    shuffle_map = [[0x01,0x0A,0x16,0x04,0x07,0x18,0x0C,0x10,0x05,0x17,0x09,0x03,0x12,0x08,0x15,0x13,0x0B,0x02,0x0F,0x0D,0x11,0x0E,0x06,0x14],
                   [0x07,0x0C,0x0E,0x11,0x09,0x16,0x10,0x06,0x14,0x0D,0x01,0x02,0x12,0x08,0x13,0x0B,0x0F,0x0A,0x18,0x15,0x04,0x05,0x03,0x17],
                   [0x0F,0x04,0x09,0x03,0x06,0x07,0x11,0x12,0x15,0x16,0x02,0x08,0x05,0x17,0x0C,0x0D,0x01,0x18,0x0B,0x14,0x0E,0x10,0x13,0x0A],
                   [0x02,0x0A,0x0E,0x12,0x0B,0x03,0x0C,0x06,0x13,0x07,0x11,0x09,0x15,0x18,0x10,0x17,0x14,0x0F,0x04,0x01,0x05,0x08,0x16,0x0D],
                   [0x0B,0x02,0x09,0x16,0x14,0x01,0x12,0x11,0x15,0x06,0x0F,0x17,0x07,0x10,0x0C,0x0E,0x08,0x18,0x13,0x03,0x0A,0x0D,0x04,0x05],
                   [0x09,0x0F,0x05,0x0D,0x16,0x15,0x12,0x11,0x03,0x0A,0x04,0x10,0x0E,0x14,0x02,0x01,0x13,0x0C,0x06,0x0B,0x17,0x18,0x07,0x08],
                   [0x12,0x02,0x0C,0x09,0x0D,0x0E,0x04,0x07,0x16,0x14,0x17,0x01,0x11,0x03,0x10,0x15,0x08,0x0A,0x05,0x13,0x0B,0x18,0x0F,0x06]]
    shuffle_method = shuffle_map[shuffle_index]
    shuffled_str = ""
    for i in range(0x18):
        shuffled_str += input_merge[shuffle_method[i]-1]
    return shuffled_str
    pass

def hex2ints(hex_str):
    result = []
    for i in range(6):
        result.append(int(hex_str[4*i:4*i+4], 16))
    return result

def ints_encrypt(numbers):
    key = 0x3e0f83e1 # located at 0x02251364
    result = []
    for i in range(6):
        r0 = numbers[i] >> 0x1f
        mul = key * numbers[i]
        r2, r6 = mul & (2**32-1), mul >> 32
        r6 = r0 + r6 >> 3
        mul = 0x21 * r6
        r0, r2 = mul & (2**32-1), mul >> 32
        r6 = numbers[i] - r0
        result.append(r6 + 1)
    return result

def ints2str(numbers):
    chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZ" # located at 0x022518b0
    s = ""
    for i in numbers:
        s += chars[i-1]
    return s

def calc_serial_code(mac_code, code1, code2):
    full_code = mac_code.upper() + code1 + code2
    shorten_index = calc_shorten_index(full_code)
    shuffle_str = shuffle(full_code, shorten_index)
    shuffle_numbers = hex2ints(shuffle_str)
    encrypted_numbers = ints_encrypt(shuffle_numbers)
    serial_code = ints2str(encrypted_numbers)
    return serial_code

print("eCDP Keygen by lazydog")
# My NO$GBA emulator shows "0009BF000031"
mac = input("Input MAC address:")
rest_no = input("Input Restaurant No.:")
manage_no = input("Input Management No. of DS card:")
print("Here's your serial:", calc_serial_code(mac, rest_no, manage_no))
print("Have fun!")

So it turns out the mysterious code is actually MAC address, my fault.
Also, check out another keygen that was done right before mine.
https://github.com/KuromeSan/eCDP-Serial-Code

Those weird algos you have there to create an index are even simpler than you think. There are 7 shuffle tables of 24 bytes each and the table is simply chosen by adding all values in the concatenated string containing mac, store and store management number and then taking modulo 7 from the result which puts it in the 0-6 range. So you can simplify alot in your code =)
Oh yeah with one minor weirdness: if the value from adding all bytes together is less than 7, the first shuffle table is chosen.
Btw adding the values together means taking the char2hex value from each byte, so F is 15 etcetera.
For instance: 115689A is 1+1+5+6+8+9+10
As the mac in the string makes sure you never have an added value of less than 7, you can even skip that check.

There is even more about modulo 7 to be investigated btw ;-)

Oh yeah and after the shuffling is done, each group of 4 hexchars is converted to an integer, that modulo 33 and used as index in the password alphabet which yields final 6 character password.

Credits for the algo to you and SilicaAndPina, I only simplified some things which hopefully make the algo clearer

Thanks for your information! "Less than 7" behavior is correct. Although "mov r0, 0h" at 0x0200AF18 sets r0 to 0, but it in fact uses r1 as return value (mov r0, r1 at 0x2251544). "Modulo 33" is yet another algorithm to calculate modulo smartly by using multiplication. After some simple calculation, it's easy to find out the "key" 0x3E0F83E1 is ceil(0x800000000 / 33), which I may explain in the future.

I'm busy with my exams until around New Year. So an update for this script may be applied after that.

So it turns out the mysterious code is actually MAC address, my fault.
Also, check out another keygen that was done right before mine.
https://github.com/KuromeSan/eCDP-Serial-Code

Those weird algos you have there to create an index are even simpler than you think. There are 7 shuffle tables of 24 bytes each and the table is simply chosen by adding all values in the concatenated string containing mac, store and store management number and then taking modulo 7 from the result which puts it in the 0-6 range. So you can simplify alot in your code =)
Oh yeah with one minor weirdness: if the value from adding all bytes together is less than 7, the first shuffle table is chosen.
Btw adding the values together means taking the char2hex value from each byte, so F is 15 etcetera.
For instance: 115689A is 1+1+5+6+8+9+10
As the mac in the string makes sure you never have an added value of less than 7, you can even skip that check.
There is even more about modulo 7 to be investigated btw ;-)
Oh yeah and after the shuffling is done, each group of 4 hexchars is converted to an integer, that modulo 33 and used as index in the password alphabet which yields final 6 character password.
Credits for the algo to you and SilicaAndPina, I only simplified some things which hopefully make the algo clearer

Thanks for your information! "Less than 7" behavior is correct. Although "mov r0, 0h" at 0x0200AF18 sets r0 to 0, but it in fact uses r1 as return value (mov r0, r1 at 0x2251544). "Modulo 33" is yet another algorithm to calculate modulo smartly by using multiplication. After some simple calculation, it's easy to find out the "key" 0x3E0F83E1 is ceil(0x800000000 / 33), which I may explain in the future.

I'm busy with my exams until around New Year. So an update for this script may be applied after that.

Dont understand the ceil part, but that is no problem.
I created a pull request for KuromeSan’s repo with a Java Swing App with an optimized and simplified algorithm, you might want to check out my change there, also has JUnit5 tests: https://github.com/cruuud/eCDP-Serial-Code
It is in a feature branch, the project ending with Java

Btw, were you aware there is a master serialcode that works for any store and storemanagement combination?

Dont understand the ceil part, but that is no problem.

ceil() is probably the wrong way to put this out. That magic number is the modular inverse of 33 mod 0x100000000 (https://www.wolframalpha.com/input/?i=33%5E-1+mod+0x100000000).

Still I don't know why it takes the upper half of 64 bit results and does some operation with it. Normally you only look at the results within the mod space (in this case mod 0x100000000 aka 32-bit integer, etc.) when you "divide" or multiply by the inverse value. Maybe some better bit and number theory magicians can answer my question.