Miku Music Machine
Handout
I’ve created the Miku Music Machine (MMM for short)! Just give it an input, and it will use coding and algorithms™ to generate a beautiful personalized tune based on your prompt. Can you compose a song that pleases Miku?
And we are also given a file called mmm-v2.exe.
First analysis
Let’s first have a look at the binary with file:
$ file mmm-v2.exe
mmm-v2.exe: PE32+ executable (console) x86-64, for MS Windows, 6 sections
So let’s open a VM and run the binary.
C:>mmm-v2.exe
Usage: mmm-v2.exe <prompt>
C:>mmm-v2.exe hello
You should work on the length of your prompt!
We can see that the binary expects a prompt as an argument of a certain length. Let’s have a look with IDA now.
By renaming some variables, we obtain something like this:
int __fastcall main(int argc, const char **argv, const char **envp)
{
__int64 input_length; // rax
__int64 counter; // rbp
int should_be_418; // edi
__int64 index_note; // rbx
__int64 sub_counter; // r14
unsigned __int8 xor_result; // si
H**MIDI**OUT phmo; // [rsp+70h] [rbp+18h] BYREF
if ( argc < 2 )
{
printf("Usage: %s <prompt>\n", *argv);
return 1;
}
input_length = -1LL;
do
++input_length;
while ( argv[1][input_length] );
if ( input_length != 50 )
{
printf("You should work on the length of your prompt!\n");
return 1;
}
counter = 0LL;
if ( midiOutOpen(&phmo, 0, 0LL, 0LL, 0) )
{
printf("Failed to open **MIDI** device.\n");
}
else
{
should_be_418 = 22;
index_note = 22LL;
do
{
sub_counter = 4LL;
xor_result = to_be_xor_array[counter] ^ argv[1][counter];
do
{
if ( (xor_result & 3) != 0 )
{
switch ( xor_result & 3 )
{
case 1:
++should_be_418;
++index_note;
break;
case 2:
should_be_418 += 21;
index_note += 21LL;
break;
case 3:
--should_be_418;
--index_note;
break;
}
}
else
{
should_be_418 -= 21;
index_note -= 21LL;
}
function_list[index_note]();
midiOutShortMsg(phmo, dwMsg);
Sleep(0x1Eu);
xor_result >>= 2;
--sub_counter;
}
while ( sub_counter );
++counter;
}
while ( counter < 50 );
Sleep(0x3E8u);
midiOutReset(phmo);
midiOutClose(phmo);
if ( should_be_418 == 418 )
{
printf("That was beautiful!\n");
return 0;
}
printf("I think you should work on your music.\n");
}
return 1;
}
So what does this code actually do?
- It checks that the input length is exactly 50 characters.
- It opens a MIDI (Musical Instrument Digital Interface) device.
- It then iterates over each character of the input, performing a Xor with
to_be_xor_arrayand incrementingshould_be_418based on the values of two-bit blocks. - It generates MIDI messages based on that value and sends them to the MIDI device.
- Finally, it checks if a certain condition (
should_be_418 == 418) is met to determine if the input was “beautiful” or not.
By looking at the different functions of the function_list with IDA, we can see something like this:
char sub_1400025F0()
{
dwMsg = 4083600;
return 41;
}
Therefore, I first assumed that this function was only setting the dwMsg variable, which is used to send MIDI messages.
Just with this first look, we can understand that our objective is to find the path to have should_be_418 equal to 418 after the loop.
Trying to find out what I am missing
This challenge was in the hard category, therefore I thought it was a bit too simple and that there would be numerous solutions, but I still decided to try to better understand this challenge by rewriting it in Python. To do so, I only used what seems significant to me, to have a cleaner code that I can work on.
This is the first version of the my_copy.py file:
data_to_be_xored = [ 0x09, 0x40, 0x11, 0xe4, 0x1c, 0x81, 0x92, 0xdb, 0x0b, 0x75, 0x26, 0x6a, 0x2f, 0x7f, 0xdd, 0xd2, 0x52, 0x21, 0x76, 0x9f, 0xdf, 0x8e, 0x8f, 0xcd, 0x9f, 0x84, 0x61, 0x3f, 0x6d, 0x7a, 0x87, 0x1e, 0x21, 0x99, 0xc7, 0x65, 0xdc, 0xc8, 0x4a, 0x22, 0x7d, 0x28, 0x64, 0x69, 0xdc, 0x20, 0x34, 0xed, 0xfb, 0xd7 ]
should_be_418 = 22
inp = input("Enter 50 caracters: ")
if len(inp) != 50:
print("Input must be exactly 50 characters.")
exit(1)
for i in range(len(inp)):
assert ord(inp[i]) >= 0x20 and ord(inp[i]) <= 0x7e, "Input characters must be in the range 0x20 to 0x7e."
inp = [ord(c) for c in inp]
for counter in range(50):
xor_value = data_to_be_xored[counter] ^ inp[counter]
for sub_counter in range(4, 0, -1):
if (xor_value & 3) != 0:
match xor_value & 3:
case 1:
should_be_418 += 1
case 2:
should_be_418 += 21
case 3:
should_be_418 -= 1
else:
should_be_418 -= 21
xor_value >>= 2
if should_be_418 == 418:
print("win")
else:
print(f"lose, got {should_be_418}, expected 418")
This function simply does the same operations using data_to_be_xored and the matching on group of 2 bits but it doesn’t implement MIDI operations, as I first thought there were not relevant.
This script is quite functional, but as I said previously, there are a multiple number of solutions. Let’s try to play a bit with the binary and IDA Windows debugger to see what we are missing.
By testing with some other inputs, I had an error in IDA:
7FFC5F9A6490: unknown exception code C0000409 (exc.code c0000409, tid 3896)
So I decided to dig and to find out exactly where it happens. After some debugging, I found that it happens when should_be_418 equals 0xdd in the function that is called __guard_xfg_dispatch_icall_fptr.
This function was called when trying to call a function pointer, so when doing this function_list[index_note]();, but I decided to check on the internet to see what it really does.
After some research, I found two interesting articles:
- How the MSVC Compiler Generates XFG Function Prototype Hashes by Quarkslab
- Exploit Development: Between a Rock and a (Xtended Flow) Guard Place: Examining XFG by Connor McGarr
And I learned about CFG and XFG. They are both protection against function pointer overwrite on Windows.
CFGstands for Control Flow Guard. When calling a function pointer, it checks that the address pointed is already registered in a bitmap of valid addresses. The issue with this technique is that an attacker can still overwrite the function pointer, but he will have to use other functions already registered in the bitmap to perform his attack.XFGstands for Xtended Flow Guard. It is an evolved version ofCFG. The specificity ofXFGis that it checks the function prototype using a hash. This hash is composed of the number of parameters, the type for each parameter, if the function is variadic or not, the calling convention and the return type. This means that even if an attacker can overwrite the function pointer, he will have to use a function with the same prototype as the original one.
In our case here, we can see that the program is using XFG, as there is a hash check:
So how can the program be more restrictive under XFG for our challenge ?
- Maybe some functions in
function_listdoes not have the same prototype as a “regular” function, so when the program tries to check the hash, it fails. - Maybe some functions in
function_listare not registered in the bitmap, therefore they cannot be called.
The first thing I did was to check the bitmap, and then the function signatures.
Checking the bitmap
As found on one of the articles above, there is a tool called dumpbin.exe that can be used to extract this bitmap. After installing it, and doing dumpbin /LOADCONFIG mmm-v2.exe, I got the following output:
Microsoft (R) COFF/PE Dumper Version 14.44.35213.0
Copyright (C) Microsoft Corporation. All rights reserved.
Dump of file C:\mmm-v2.exe
File Type: EXECUTABLE IMAGE
Section contains the following load config:
00000140 size
0 time date stamp
0.00 Version
0 GlobalFlags Clear
0 GlobalFlags Set
0 Critical Section Default Timeout
0 Decommit Free Block Threshold
0 Decommit Total Free Threshold
0000000000000000 Lock Prefix Table
0 Maximum Allocation Size
0 Virtual Memory Threshold
0 Process Affinity Mask
0 Process Heap Flags
0 CSD Version
0000 Dependent Load Flag
0000000000000000 Edit List
0000000140073E38 Security Cookie
0000000140060300 Guard CF address of check-function pointer
0000000140060310 Guard CF address of dispatch-function pointer
00000001400603C8 Guard CF function table
123 Guard CF function count
10817500 Guard Flags
CF instrumented
XFG instrumented
FID table present
Protect delayload IAT
Delayload IAT in its own section
Export suppression info present
Long jump target table present
0000 Code Integrity Flags
0000 Code Integrity Catalog
00000000 Code Integrity Catalog Offset
00000000 Code Integrity Reserved
0000000000000000 Guard CF address taken IAT entry table
0 Guard CF address taken IAT entry count
0000000000000000 Guard CF long jump target table
0 Guard CF long jump target count
0000000000000000 Dynamic value relocation table
0000000000000000 Hybrid metadata pointer
0000000000000000 Guard RF address of failure-function
0000000000000000 Guard RF address of failure-function pointer
00000000 Dynamic value relocation table offset
0000 Dynamic value relocation table section
0000 Reserved2
0000000000000000 Guard RF address of stack pointer verification function pointer
00000000 Hot patching table offset
0000 Reserved3
0000000000000000 Enclave configuration pointer
000000014006BBE4 Volatile metadata pointer
0000000000000000 Guard EH continuation table
0 Guard EH continuation count
0000000140060308 Guard XFG address of check-function pointer
0000000140060318 Guard XFG address of dispatch-function pointer
0000000140060320 Guard XFG address of dispatch-table-function pointer
0000000140060328 CastGuard OS determined failure mode
0000000140060330 Guard memcpy function pointer
Guard CF Function Table
Address
--------
X 0000000140001010
[...]
Volatile Metadata
18 size
2 min version (8002)
2 max version (8002)
000000000006BBFC volatile access RVA table
5FC volatile access RVA table size
000000000006C1F8 volatile range info table
68 volatile range info table size
Volatile Access RVA Table
Address
--------
00000001400049C4
[...]
Volatile Info Range Table
Ranges
-------
0000000140001010 - 00000001400049A3
[...]
Summary
4000 .data
5000 .pdata
13000 .rdata
1000 .reloc
5F000 .text
1000 _RDATA
The section that we are going to focus on is the Guard CF function table, which contains the addresses of the functions that are registered in the bitmap.
Let’s extract it and store it in an array called available_functions. And let’s also extract the function map in IDA to have the relation between the offset and the function, and store it in a variable called mapping_functions.
With that information, we can now build the list of authorized values that we can “step in” with the variable should_be_418.
from mapping_function import mapping_functions
from available_or_not import available_functions
base = 0x140073040
offset = 0
authorized = []
while base + offset * 8 in mapping_functions:
funct = mapping_functions[base + offset * 8]
if funct in available_functions:
authorized.append(offset)
offset += 1
print(f"authorized = {authorized}")
Which gives us the following output:
authorized = [22, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 43, 47, 55, 57, 59, 61, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 78, 80, 82, 87, 93, 97, 99, 106, 107, 108, 110, 112, 114, 115, 116, 117, 118, 120, 121, 122, 123, 124, 131, 133, 139, 143, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 164, 165, 166, 169, 179, 187, 190, 192, 194, 196, 197, 198, 199, 200, 201, 202, 204, 206, 208, 213, 215, 217, 219, 223, 225, 227, 229, 232, 234, 235, 236, 237, 238, 240, 241, 242, 244, 246, 247, 248, 249, 250, 253, 259, 267, 271, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 288, 290, 291, 292, 295, 299, 301, 303, 305, 307, 309, 311, 313, 316, 318, 319, 320, 322, 324, 326, 328, 330, 332, 334, 339, 341, 345, 349, 351, 355, 358, 359, 360, 362, 364, 365, 366, 367, 368, 370, 372, 373, 374, 376, 379, 381, 383, 387, 393, 395, 397, 400, 402, 404, 405, 406, 408, 409, 410, 412, 413, 414, 416, 418]
So we now have the list of authorized values that we can step on while incrementing or decrementing should_be_418.
Our my_copy.py file can now be updated to take this into account:
data_to_be_xored = [ 0x09, 0x40, 0x11, 0xe4, 0x1c, 0x81, 0x92, 0xdb, 0x0b, 0x75, 0x26, 0x6a, 0x2f, 0x7f, 0xdd, 0xd2, 0x52, 0x21, 0x76, 0x9f, 0xdf, 0x8e, 0x8f, 0xcd, 0x9f, 0x84, 0x61, 0x3f, 0x6d, 0x7a, 0x87, 0x1e, 0x21, 0x99, 0xc7, 0x65, 0xdc, 0xc8, 0x4a, 0x22, 0x7d, 0x28, 0x64, 0x69, 0xdc, 0x20, 0x34, 0xed, 0xfb, 0xd7 ]
authorized = [ 0x16, 0x18, 0x19, 0x1a, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x2b, 0x2f, 0x37, 0x39, 0x3b, 0x3d, 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x4a, 0x4b, 0x4e, 0x50, 0x52, 0x57, 0x5d, 0x61, 0x63, 0x6a, 0x6b, 0x6c, 0x6e, 0x70, 0x72, 0x73, 0x74, 0x75, 0x76, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x83, 0x85, 0x8b, 0x8f, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa4, 0xa5, 0xa6, 0xa9, 0xb3, 0xbb, 0xbe, 0xc0, 0xc2, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcc, 0xce, 0xd0, 0xd5, 0xd7, 0xd9, 0xdb, 0xdf, 0xe1, 0xe3, 0xe5, 0xe8, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xf0, 0xf1, 0xf2, 0xf4, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfd, 0x103, 0x10b, 0x10f, 0x112, 0x113, 0x114, 0x115, 0x116, 0x117, 0x11a, 0x11b, 0x11c, 0x11d, 0x11e, 0x120, 0x122, 0x123, 0x124, 0x127, 0x12b, 0x12d, 0x12f, 0x131, 0x133, 0x135, 0x137, 0x139, 0x13c, 0x13e, 0x13f, 0x140, 0x142, 0x144, 0x146, 0x148, 0x14a, 0x14c, 0x14e, 0x153, 0x155, 0x159, 0x15d, 0x15f, 0x163, 0x166, 0x167, 0x168, 0x16a, 0x16c, 0x16d, 0x16e, 0x16f, 0x170, 0x172, 0x174, 0x175, 0x176, 0x178, 0x17b, 0x17d, 0x17f, 0x183, 0x189, 0x18b, 0x190, 0x192, 0x194, 0x195, 0x196, 0x198, 0x199, 0x19a, 0x19c, 0x19d, 0x19e, 0x1a0, 0x1a2]
should_be_418 = 22
inp = input("Enter 50 caracters: ")
if len(inp) != 50:
print("Input must be exactly 50 characters.")
exit(1)
for i in range(len(inp)):
assert ord(inp[i]) >= 0x20 and ord(inp[i]) <= 0x7e, "Input characters must be in the range 0x20 to 0x7e."
inp = [ord(c) for c in inp]
for counter in range(50):
xor_value = data_to_be_xored[counter] ^ inp[counter]
for sub_counter in range(4, 0, -1):
if (xor_value & 3) != 0:
match xor_value & 3:
case 1:
should_be_418 += 1
case 2:
should_be_418 += 21
case 3:
should_be_418 -= 1
else:
should_be_418 -= 21
xor_value >>= 2
if should_be_418 not in authorized:
print(f"Character {counter} with value {hex(inp[counter])} is not authorized.")
exit(1)
if should_be_418 == 418:
print("win")
else:
print(f"lose, got {should_be_418}, expected 418")
Finding the last conditions
After looking at the bitmap, my plan was to check the different functions to see if their signatures match that of a “regular” function, so if they have the same number of arguments, the same return type and so on.
But while looking at the different functions, I came across interesting things. For example, this is a “regular” function:
And these were the two other function types that I found:
So one function just stops execution by doing a RtlFailFast and the other one Xor some code with 0x7D. By looking at the code that is Xored in placed, we can see that it is the code that triggers the RtlFailFast.
By just doing a search on IDA, we can then find the six functions that are performing a Xor to enable six other functions, that originally were stopping the program. Therefore, the Xor function “unlocks” another function, and we can represent that by using a dictionary.
from mapping_function import mapping_functions
from available_or_not import available_functions
unlock_map = {
0x140001570: 0x1400014F0,
0x140002970: 0x1400023D0,
0x140003650: 0x140001410,
0x140003F30: 0x140002710,
0x140004210: 0x140002110,
0x140004430: 0x140001790
}
base = 0x140073040
offset = 0
authorized = []
while base + offset * 8 in mapping_functions:
funct = mapping_functions[base + offset * 8]
if funct in unlock_map.keys():
unlock_map[offset] = unlock_map[funct]
del unlock_map[funct]
if funct in unlock_map.values():
key = list(unlock_map.keys())[list(unlock_map.values()).index(funct)]
unlock_map[key] = offset
elif funct in available_functions:
authorized.append(offset)
offset += 1
print(f"authorized = {authorized}")
print(f"unlock_map = {unlock_map}")
Which gives us the following output:
authorized = [22, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 43, 47, 55, 57, 59, 61, 64, 65, 66, 67, 68, 69, 70, 71, 74, 75, 78, 80, 82, 87, 93, 97, 99, 106, 107, 108, 110, 112, 114, 115, 116, 117, 118, 120, 121, 122, 123, 124, 131, 133, 139, 143, 148, 149, 150, 151, 152, 153, 154, 155, 157, 158, 159, 160, 161, 162, 164, 165, 166, 169, 179, 187, 190, 192, 194, 196, 197, 198, 199, 200, 201, 202, 204, 206, 208, 213, 215, 217, 219, 223, 225, 227, 229, 232, 234, 235, 236, 237, 238, 240, 241, 242, 244, 246, 247, 248, 249, 250, 253, 259, 267, 271, 274, 275, 276, 277, 278, 279, 282, 283, 284, 285, 286, 288, 290, 291, 292, 295, 299, 301, 303, 305, 307, 309, 311, 313, 316, 318, 319, 320, 322, 324, 326, 328, 330, 332, 334, 339, 341, 345, 349, 351, 355, 358, 359, 360, 362, 364, 365, 366, 367, 368, 370, 372, 373, 374, 376, 379, 381, 383, 387, 393, 395, 400, 402, 404, 405, 406, 408, 409, 410, 412, 413, 414, 416, 418]
unlock_map = {26: 72, 153: 281, 187: 280, 235: 76, 368: 397, 383: 156}
We now have all the conditions to solve our problem.
Solving the problem
As there are only two ways to move (+-1 and +-21), we can consider that we are on a 2D grid, with only some available cells and some cells that can be opened by stepping on other ones.
To do so, I decided to have some fun and build a little game. This game will give the flag while I solve it.
data_to_be_xored = [ 0x09, 0x40, 0x11, 0xe4, 0x1c, 0x81, 0x92, 0xdb, 0x0b, 0x75, 0x26, 0x6a, 0x2f, 0x7f, 0xdd, 0xd2, 0x52, 0x21, 0x76, 0x9f, 0xdf, 0x8e, 0x8f, 0xcd, 0x9f, 0x84, 0x61, 0x3f, 0x6d, 0x7a, 0x87, 0x1e, 0x21, 0x99, 0xc7, 0x65, 0xdc, 0xc8, 0x4a, 0x22, 0x7d, 0x28, 0x64, 0x69, 0xdc, 0x20, 0x34, 0xed, 0xfb, 0xd7 ]
authorized = [22, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 43, 47, 55, 57, 59, 61, 64, 65, 66, 67, 68, 69, 70, 71, 74, 75, 78, 80, 82, 87, 93, 97, 99, 106, 107, 108, 110, 112, 114, 115, 116, 117, 118, 120, 121, 122, 123, 124, 131, 133, 139, 143, 148, 149, 150, 151, 152, 153, 154, 155, 157, 158, 159, 160, 161, 162, 164, 165, 166, 169, 179, 187, 190, 192, 194, 196, 197, 198, 199, 200, 201, 202, 204, 206, 208, 213, 215, 217, 219, 223, 225, 227, 229, 232, 234, 235, 236, 237, 238, 240, 241, 242, 244, 246, 247, 248, 249, 250, 253, 259, 267, 271, 274, 275, 276, 277, 278, 279, 282, 283, 284, 285, 286, 288, 290, 291, 292, 295, 299, 301, 303, 305, 307, 309, 311, 313, 316, 318, 319, 320, 322, 324, 326, 328, 330, 332, 334, 339, 341, 345, 349, 351, 355, 358, 359, 360, 362, 364, 365, 366, 367, 368, 370, 372, 373, 374, 376, 379, 381, 383, 387, 393, 395, 400, 402, 404, 405, 406, 408, 409, 410, 412, 413, 414, 416, 418]
unlock_map = {26: 72, 153: 281, 187: 280, 235: 76, 368: 397, 383: 156}
unlock_map_keys = list(unlock_map.keys())
unlock_map_values = list(unlock_map.values())
unlock_map_colors = [f"\033[{num+32}m" for num in range(len(unlock_map_keys))]
dimension = (21, 21)
current_position = 22
end = 418
list_move = []
def get_result_xor(value):
if value == 21:
return 2
if value == 1:
return 1
if value == -1:
return 3
if value == -21:
return 0
def compute_flag():
flag = ""
for i in range(len(list_move)//4):
actual_char = 0
for j in range(4):
xor_value = get_result_xor(list_move[i*4 + j])
actual_char |= xor_value << (j * 2)
actual_char ^= data_to_be_xored[i]
flag += chr(actual_char)
return flag
def print_maze():
for i in range(dimension[0]):
for j in range(dimension[1]):
actual = i * dimension[1] + j
if actual == current_position:
print("\033[31mP\033[0m", end="")
elif actual == end:
print("\033[31mE\033[0m", end="")
elif actual in unlock_map_keys:
index = unlock_map_keys.index(actual)
print(f"{unlock_map_colors[index]}K\033[0m", end="")
elif actual in unlock_map_values:
index = unlock_map_values.index(actual)
print(f"{unlock_map_colors[index]}D\033[0m", end="")
elif actual in authorized:
print(" ", end="")
else:
print("\u2588", end="")
print()
print(f"Current position: {current_position}, End position: {end}")
print(f"Current flag: {compute_flag()}")
def move():
print("Possible moves: w (up), a (left), s (down), d (right)")
m = input("> ").strip().lower()
if m == 'w':
return -21
if m == 's':
return 21
if m == 'a':
return -1
if m == 'd':
return 1
while True:
print_maze()
act_move = move()
if act_move == None:
print("Invalid move, try again.")
continue
new_position = current_position + act_move
if 0 > new_position or new_position > dimension[0] * dimension[1] or new_position not in authorized:
print("Invalid move, try again.")
continue
list_move.append(act_move)
if new_position == end:
print("Congratulations!")
print("Flag:", compute_flag())
break
if new_position in unlock_map_keys:
index = unlock_map_keys.index(new_position)
authorized.append(unlock_map_values[index])
del unlock_map_keys[index]
del unlock_map_values[index]
del unlock_map_colors[index]
current_position = new_position
if len(list_move) == 200:
print("You have reached the maximum number of moves.")
break
And when I finally solved it:
Possible moves: w (up), a (left), s (down), d (right)
> s
Congratulations!
Flag: SEKAI{https://www.youtube.com/watch?v=J---aiyznGQ}
I know I could also perform a DFS, but as the maze was relatively small (200 inputs), I decided to do it manually, and it was fun to do so.
I also made a script to create a GIF.
list_move= [21, 21, 1, 1, 1, 1, -21, -21, 21, 21, 1, 1, 1, 1, 21, 21, 1, 1, 1, 1, 21, 21, -1, -1, 21, 21, -1, -1, -1, -1, 21, 21, -1, -1, -1, 1, 1, 1, -21, -21, 1, 1, 1, 1, -21, -21, 1, 1, -21, -21, -21, -21, -21, -21, 1, 1, 21, 21, 21, 21, 1, 1, 21, 21, 1, 1, 21, -21, -1, -1, -21, -21, -1, -1, -21, -21, -21, -21, -1, -1, 21, 21, 21, 21, 21, 21, -1, -1, 21, 21, -1, -1, -1, -1, 21, 21, 21, 21, -1, -1, 21, 21, 21, 21, 21, -21, -21, -21, -21, -21, 1, 1, -21, -21, -21, -21, 1, 1, 1, 1, -21, -21, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 21, 21, -1, -1, -1, -1, 21, 21, 21, 21, 1, 1, 21, 21, 21, 21, 1, 1, -1, -1, -21, -21, -21, -21, -1, -1, -21, -21, -21, -21, 1, 1, 1, 1, -21, -21, 1, 1, -21, -21, -21, -21, -21, -21, 1, 1, 21, 21, 21, 21, 1, 1, 21, 21, 1, 1, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21]
authorized = [22, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 43, 47, 55, 57, 59, 61, 64, 65, 66, 67, 68, 69, 70, 71, 74, 75, 78, 80, 82, 87, 93, 97, 99, 106, 107, 108, 110, 112, 114, 115, 116, 117, 118, 120, 121, 122, 123, 124, 131, 133, 139, 143, 148, 149, 150, 151, 152, 153, 154, 155, 157, 158, 159, 160, 161, 162, 164, 165, 166, 169, 179, 187, 190, 192, 194, 196, 197, 198, 199, 200, 201, 202, 204, 206, 208, 213, 215, 217, 219, 223, 225, 227, 229, 232, 234, 235, 236, 237, 238, 240, 241, 242, 244, 246, 247, 248, 249, 250, 253, 259, 267, 271, 274, 275, 276, 277, 278, 279, 282, 283, 284, 285, 286, 288, 290, 291, 292, 295, 299, 301, 303, 305, 307, 309, 311, 313, 316, 318, 319, 320, 322, 324, 326, 328, 330, 332, 334, 339, 341, 345, 349, 351, 355, 358, 359, 360, 362, 364, 365, 366, 367, 368, 370, 372, 373, 374, 376, 379, 381, 383, 387, 393, 395, 400, 402, 404, 405, 406, 408, 409, 410, 412, 413, 414, 416, 418]
unlock_map = {26: 72, 153: 281, 187: 280, 235: 76, 368: 397, 383: 156}
unlock_map_keys = list(unlock_map.keys())
unlock_map_values = list(unlock_map.values())
unlock_map_colors = [(100, 100, 100), (100, 100, 0), (100, 0, 100), (0, 100, 100), (100, 50, 0), (50, 0, 100)]
from PIL import Image
Multiplication = 50
img = Image.new('RGB', (21*Multiplication, 21*Multiplication), color = 'white')
pixels = img.load()
current_position = 22
end = 418
def create_player(pixels, i, j):
for x in range(i*Multiplication, (i+1)*Multiplication):
for y in range(j*Multiplication, (j+1)*Multiplication):
pixels[x, y] = (255, 0, 0)
def create_end(pixels, i, j):
for x in range(i*Multiplication, (i+1)*Multiplication):
for y in range(j*Multiplication, (j+1)*Multiplication):
pixels[x, y] = (0, 255, 0)
def create_unlock(pixels, i, j, color):
for x in range(i*Multiplication, (i+1)*Multiplication):
for y in range(j*Multiplication, (j+1)*Multiplication):
pixels[x, y] = color
def create_authorized(pixels, i, j):
for x in range(i*Multiplication, (i+1)*Multiplication):
for y in range(j*Multiplication, (j+1)*Multiplication):
pixels[x, y] = (255, 255, 255)
def create_unauthorized(pixels, i, j):
for x in range(i*Multiplication, (i+1)*Multiplication):
for y in range(j*Multiplication, (j+1)*Multiplication):
pixels[x, y] = (0, 0, 0)
for tour in range(len(list_move) + 1):
if tour != 0:
current_position += list_move[tour - 1]
if current_position in unlock_map_keys:
index = unlock_map_keys.index(current_position)
authorized.append(unlock_map_values[index])
del unlock_map_keys[index]
del unlock_map_values[index]
del unlock_map_colors[index]
for i in range(21):
for j in range(21):
actual = i + j*21
if actual == current_position:
create_player(pixels, i, j)
elif actual == end:
create_end(pixels, i, j)
elif actual in unlock_map_keys:
index = unlock_map_keys.index(actual)
create_unlock(pixels, i, j, unlock_map_colors[index])
elif actual in unlock_map_values:
index = unlock_map_values.index(actual)
create_unlock(pixels, i, j, unlock_map_colors[index])
elif actual in authorized:
create_authorized(pixels, i, j)
else:
create_unauthorized(pixels, i, j)
img.save(f'gif/create_image_{tour}.png')
images = [Image.open(f"gif/create_image_{i}.png") for i in range(len(list_move) + 1)]
output_gif_path = "output.gif"
images[0].save(
output_gif_path,
save_all=True,
append_images=images[1:],
duration=100,
loop=0
)
Conclusion
This challenge was really fun to solve, and it’s not a challenge where you have to understand a very hard algorithm, but rather to understand how CFG and XFG work, so pretty interesting.