Last weekend I played in Hack.lu CTF with Maple Bacon, where we placed 24th out of 174 teams. For once, I decided to look at a reversing challenge and ended up solving it!
For a more concise version, check out this post.
Pycoin [146]
A friend gave me this and he says he can not reverse this… but this is just python?
We’re given a Python bytecode file (pycoin.pyc) and asked to reverse it.
Running python3 pycoin.pyc, we’re greeted with
please supply a valid key:
Supposedly, entering anything other than the valid key/flag leaves us with the output of “invalid key”.
What are .pyc files?
The typical implementation of Python we use is CPython — it compiles python source code into lower-level Python machine instructions that look something like this:
L. 1 0 JUMP_FORWARD 4 'to 4'
2 LOAD_GLOBAL 99 99
4_0 COME_FROM 112 '112'
4_1 COME_FROM 0 '0'
4 LOAD_CONST 0
6 LOAD_CONST ('md5',)
8 IMPORT_NAME hashlib
10 IMPORT_FROM md5
The main point of having bytecode (.pyc) files is to reduce compilation time when you reuse the same files without changes.
After a bit of searching around, I found uncompyle6: a decompiler that translates Python bytecode back into source code. Running pip install uncompyle6 followed by uncompyle6 pycoin.pyc successfully decompiles the bytecode:
# uncompyle6 version 3.7.4
# Python bytecode 3.8 (3413)
# Decompiled from: Python 3.8.10 (default, Jun 2 2021, 10:49:15)
# [GCC 9.4.0]
# Embedded file name: challenge_generated.py
# Compiled at: 2021-10-27 14:40:15
# Size of source mod 2**32: 2836 bytes
import marshal
marshalled = b'\xe3\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00@\x00\x00\x00\xf3\xf0\x01\x00\x00n\x02tcd\x00d\x01l\x00m\x01Z\x01\x01\x00e\x02e\x03d\x02\x83\x01\x83\x01\xa0\x04\xa1\x00Z\x05e\x06e\x05\x83\x01d\x03k\x02\x90\x01o\xcee\x05d\x00\x19\x00d\x04k\x02\x90\x01o\xcee\x05d\x05\x19\x00e\x05d\x00\x19\x00d\x06\x17\x00k\x02\x90\x01o\xcee\x05d\x07\x19\x00e\x05d\x05\x19\x00e\x05d\x00\x19\x00\x18\x00d\x08n\n]\x02n\x02n\x02r\x04q\x04\x17\x00k\x02\x90\x01o\xcee\x05d\t\x19\x00d\nk\x02\x90\x01o\xcee\x05d\x0b\x19\x00e\x05d\x0c\x19\x00d\t\x14\x00d\r\x18\x00k\x02\x90\x01o\xcee\x05d\x0e\x19\x00e\x07e\x05\x83\x01d\x0f\x18\x00k\x02\x90\x01o\xcee\x05d\x06\x19\x00e\x05d\x10\x19\x00\x17\x00e\x05d\x11\x19\x00\x17\x00d\x12k\x02\x90\x01o\xcee\x08e\te\x05d\x10\x19\x00\x83\x01d\x07\x14\x00\x83\x01d\x05\x17\x00e\x05d\x13\x19\x00k\x02\x90\x01o\xcee\x05d\x14\x19\x00d\x15\x16\x00d\x03k\x02\x90\x01o\xcee\x05d\x13\x19\x00e\x05d\x14\x19\x00d\x07\x14\x00k\x02\x90\x01o\xcee\x01e\x05d\x11\x19\x00d\x16\x14\x00\x83\x01\xa0\n\xa1\x00d\x00\x19\x00d\x05\x18\x00e\x05d\t\x19\x00k\x02\x02\x00\x02\x00\x90\x01o\xcee\x05d\x0c\x19\x00d\x17k\x02\x90\x01o\xcee\x05d\x18\x19\x00e\x05d\x19\x19\x00d\x07\x1b\x00d\x07\x18\x00k\x02\x90\x01o\xcee\x05d\x1a\x19\x00e\x05d\x11\x19\x00e\x05d\x14\x19\x00\x14\x00d\x1b\x16\x00d\x07\x14\x00d\x05\x18\x00k\x02\x90\x01o\xcee\x05d\x19\x19\x00e\x05d\x18\x19\x00e\x05d\x13\x19\x00A\x00e\x05d\x1c\x19\x00A\x00d\t\x14\x00d\x1d\x18\x00k\x02\x90\x01o\xcee\x05d\x1c\x19\x00d\x1ek\x02Z\x0be\x0ce\x0b\x90\x01r\xe6d\x1fe\x05\xa0\r\xa1\x00\x9b\x00\x9d\x02n\x02d \x83\x01\x01\x00d!S\x00)"\xe9\x00\x00\x00\x00)\x01\xda\x03md5z\x1aplease supply a valid key:\xe9\x10\x00\x00\x00\xe9f\x00\x00\x00\xe9\x01\x00\x00\x00\xe9\x06\x00\x00\x00\xe9\x02\x00\x00\x00\xe9[\x00\x00\x00\xe9\x03\x00\x00\x00\xe9g\x00\x00\x00\xe9\x04\x00\x00\x00\xe9\x0b\x00\x00\x00\xe9*\x00\x00\x00\xe9\x05\x00\x00\x00i*\x05\x00\x00\xe9\x07\x00\x00\x00\xe9\n\x00\x00\x00i\x04\x01\x00\x00\xe9\t\x00\x00\x00\xe9\x08\x00\x00\x00\xe9\x11\x00\x00\x00\xf3\x01\x00\x00\x00a\xe97\x00\x00\x00\xe9\x0c\x00\x00\x00\xe9\x0e\x00\x00\x00\xe9\r\x00\x00\x00\xe9 \x00\x00\x00\xe9\x0f\x00\x00\x00\xe9\x17\x00\x00\x00\xe9}\x00\x00\x00z\x0bvalid key! z\x0einvalid key :(N)\x0eZ\x07hashlibr\x03\x00\x00\x00\xda\x03str\xda\x05input\xda\x06encode\xda\x01k\xda\x03len\xda\x03sum\xda\x03int\xda\x03chr\xda\x06digestZ\x07correct\xda\x05print\xda\x06decode\xa9\x00r)\x00\x00\x00r)\x00\x00\x00\xfa\r<disassembly>\xda\x08<module>\x01\x00\x00\x00sF\x00\x00\x00\x0c\x02\x10\x03\x0e\x01\n\xff\x04\x02\x12\xfe\x04\x03\x1a\xfd\x04\x04\n\xfc\x04\x05\x16\xfb\x04\x06\x12\xfa\x04\x07\x1a\xf9\x04\x08\x1e\xf8\x04\t\x0e\xf7\x04\n\x12\xf6\x04\x0b"\xf5\x04\x0c\n\xf4\x04\r\x16\xf3\x04\x0e"\xf2\x04\x0f&\xf1\x04\x10\n\xee\x02\x15'
exec(marshal.loads(marshalled))
# okay decompiling pycoin.pyc
Running this file in Python produces the same prompt asking the user for a key, so at least we’re doing something right.
So… what does marshal do?
After looking more into the marshal module, I realized it was a way of serializing Python objects (converting them into a binary format) — however, the documentation says that ‘marshal exists mainly to support reading and writing the “pseudo-compiled” code for Python modules of .pyc files’. A similar (and more common) module for serialization is pickle.
Notably, the function marshal.loads converts the serialized bytes-like object to a Python code object, which we can then analyze with other libraries.
For example, if we want to print out the constants of the marshalled object, we can write:
import marshal
marshalled = b'\xe3\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00@\x00\x00\x00\xf3\xf0\x01\x00\x00n\x02tcd\x00d\x01l\x00m\x01Z\x01\x01\x00e\x02e\x03d\x02\x83\x01\x83\x01\xa0\x04\xa1\x00Z\x05e\x06e\x05\x83\x01d\x03k\x02\x90\x01o\xcee\x05d\x00\x19\x00d\x04k\x02\x90\x01o\xcee\x05d\x05\x19\x00e\x05d\x00\x19\x00d\x06\x17\x00k\x02\x90\x01o\xcee\x05d\x07\x19\x00e\x05d\x05\x19\x00e\x05d\x00\x19\x00\x18\x00d\x08n\n]\x02n\x02n\x02r\x04q\x04\x17\x00k\x02\x90\x01o\xcee\x05d\t\x19\x00d\nk\x02\x90\x01o\xcee\x05d\x0b\x19\x00e\x05d\x0c\x19\x00d\t\x14\x00d\r\x18\x00k\x02\x90\x01o\xcee\x05d\x0e\x19\x00e\x07e\x05\x83\x01d\x0f\x18\x00k\x02\x90\x01o\xcee\x05d\x06\x19\x00e\x05d\x10\x19\x00\x17\x00e\x05d\x11\x19\x00\x17\x00d\x12k\x02\x90\x01o\xcee\x08e\te\x05d\x10\x19\x00\x83\x01d\x07\x14\x00\x83\x01d\x05\x17\x00e\x05d\x13\x19\x00k\x02\x90\x01o\xcee\x05d\x14\x19\x00d\x15\x16\x00d\x03k\x02\x90\x01o\xcee\x05d\x13\x19\x00e\x05d\x14\x19\x00d\x07\x14\x00k\x02\x90\x01o\xcee\x01e\x05d\x11\x19\x00d\x16\x14\x00\x83\x01\xa0\n\xa1\x00d\x00\x19\x00d\x05\x18\x00e\x05d\t\x19\x00k\x02\x02\x00\x02\x00\x90\x01o\xcee\x05d\x0c\x19\x00d\x17k\x02\x90\x01o\xcee\x05d\x18\x19\x00e\x05d\x19\x19\x00d\x07\x1b\x00d\x07\x18\x00k\x02\x90\x01o\xcee\x05d\x1a\x19\x00e\x05d\x11\x19\x00e\x05d\x14\x19\x00\x14\x00d\x1b\x16\x00d\x07\x14\x00d\x05\x18\x00k\x02\x90\x01o\xcee\x05d\x19\x19\x00e\x05d\x18\x19\x00e\x05d\x13\x19\x00A\x00e\x05d\x1c\x19\x00A\x00d\t\x14\x00d\x1d\x18\x00k\x02\x90\x01o\xcee\x05d\x1c\x19\x00d\x1ek\x02Z\x0be\x0ce\x0b\x90\x01r\xe6d\x1fe\x05\xa0\r\xa1\x00\x9b\x00\x9d\x02n\x02d \x83\x01\x01\x00d!S\x00)"\xe9\x00\x00\x00\x00)\x01\xda\x03md5z\x1aplease supply a valid key:\xe9\x10\x00\x00\x00\xe9f\x00\x00\x00\xe9\x01\x00\x00\x00\xe9\x06\x00\x00\x00\xe9\x02\x00\x00\x00\xe9[\x00\x00\x00\xe9\x03\x00\x00\x00\xe9g\x00\x00\x00\xe9\x04\x00\x00\x00\xe9\x0b\x00\x00\x00\xe9*\x00\x00\x00\xe9\x05\x00\x00\x00i*\x05\x00\x00\xe9\x07\x00\x00\x00\xe9\n\x00\x00\x00i\x04\x01\x00\x00\xe9\t\x00\x00\x00\xe9\x08\x00\x00\x00\xe9\x11\x00\x00\x00\xf3\x01\x00\x00\x00a\xe97\x00\x00\x00\xe9\x0c\x00\x00\x00\xe9\x0e\x00\x00\x00\xe9\r\x00\x00\x00\xe9 \x00\x00\x00\xe9\x0f\x00\x00\x00\xe9\x17\x00\x00\x00\xe9}\x00\x00\x00z\x0bvalid key! z\x0einvalid key :(N)\x0eZ\x07hashlibr\x03\x00\x00\x00\xda\x03str\xda\x05input\xda\x06encode\xda\x01k\xda\x03len\xda\x03sum\xda\x03int\xda\x03chr\xda\x06digestZ\x07correct\xda\x05print\xda\x06decode\xa9\x00r)\x00\x00\x00r)\x00\x00\x00\xfa\r<disassembly>\xda\x08<module>\x01\x00\x00\x00sF\x00\x00\x00\x0c\x02\x10\x03\x0e\x01\n\xff\x04\x02\x12\xfe\x04\x03\x1a\xfd\x04\x04\n\xfc\x04\x05\x16\xfb\x04\x06\x12\xfa\x04\x07\x1a\xf9\x04\x08\x1e\xf8\x04\t\x0e\xf7\x04\n\x12\xf6\x04\x0b"\xf5\x04\x0c\n\xf4\x04\r\x16\xf3\x04\x0e"\xf2\x04\x0f&\xf1\x04\x10\n\xee\x02\x15'
code = marshal.loads(marshalled)
print(code.co_consts)
This outputs: (0, ('md5',), 'please supply a valid key:', 16, 102, 1, 6, 2, 91, 3, 103, 4, 11, 42, 5, 1322, 7, 10, 260, 9, 8, 17, b'a', 55, 12, 14, 13, 32, 15, 23, 125, 'valid key! ', 'invalid key :(', None)
Now, we can again use the uncompyle6 library to decompile the code object:
from uncompyle6.main import decompile
import marshal
marshalled = b'\xe3\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00@\x00\x00\x00\xf3\xf0\x01\x00\x00n\x02tcd\x00d\x01l\x00m\x01Z\x01\x01\x00e\x02e\x03d\x02\x83\x01\x83\x01\xa0\x04\xa1\x00Z\x05e\x06e\x05\x83\x01d\x03k\x02\x90\x01o\xcee\x05d\x00\x19\x00d\x04k\x02\x90\x01o\xcee\x05d\x05\x19\x00e\x05d\x00\x19\x00d\x06\x17\x00k\x02\x90\x01o\xcee\x05d\x07\x19\x00e\x05d\x05\x19\x00e\x05d\x00\x19\x00\x18\x00d\x08n\n]\x02n\x02n\x02r\x04q\x04\x17\x00k\x02\x90\x01o\xcee\x05d\t\x19\x00d\nk\x02\x90\x01o\xcee\x05d\x0b\x19\x00e\x05d\x0c\x19\x00d\t\x14\x00d\r\x18\x00k\x02\x90\x01o\xcee\x05d\x0e\x19\x00e\x07e\x05\x83\x01d\x0f\x18\x00k\x02\x90\x01o\xcee\x05d\x06\x19\x00e\x05d\x10\x19\x00\x17\x00e\x05d\x11\x19\x00\x17\x00d\x12k\x02\x90\x01o\xcee\x08e\te\x05d\x10\x19\x00\x83\x01d\x07\x14\x00\x83\x01d\x05\x17\x00e\x05d\x13\x19\x00k\x02\x90\x01o\xcee\x05d\x14\x19\x00d\x15\x16\x00d\x03k\x02\x90\x01o\xcee\x05d\x13\x19\x00e\x05d\x14\x19\x00d\x07\x14\x00k\x02\x90\x01o\xcee\x01e\x05d\x11\x19\x00d\x16\x14\x00\x83\x01\xa0\n\xa1\x00d\x00\x19\x00d\x05\x18\x00e\x05d\t\x19\x00k\x02\x02\x00\x02\x00\x90\x01o\xcee\x05d\x0c\x19\x00d\x17k\x02\x90\x01o\xcee\x05d\x18\x19\x00e\x05d\x19\x19\x00d\x07\x1b\x00d\x07\x18\x00k\x02\x90\x01o\xcee\x05d\x1a\x19\x00e\x05d\x11\x19\x00e\x05d\x14\x19\x00\x14\x00d\x1b\x16\x00d\x07\x14\x00d\x05\x18\x00k\x02\x90\x01o\xcee\x05d\x19\x19\x00e\x05d\x18\x19\x00e\x05d\x13\x19\x00A\x00e\x05d\x1c\x19\x00A\x00d\t\x14\x00d\x1d\x18\x00k\x02\x90\x01o\xcee\x05d\x1c\x19\x00d\x1ek\x02Z\x0be\x0ce\x0b\x90\x01r\xe6d\x1fe\x05\xa0\r\xa1\x00\x9b\x00\x9d\x02n\x02d \x83\x01\x01\x00d!S\x00)"\xe9\x00\x00\x00\x00)\x01\xda\x03md5z\x1aplease supply a valid key:\xe9\x10\x00\x00\x00\xe9f\x00\x00\x00\xe9\x01\x00\x00\x00\xe9\x06\x00\x00\x00\xe9\x02\x00\x00\x00\xe9[\x00\x00\x00\xe9\x03\x00\x00\x00\xe9g\x00\x00\x00\xe9\x04\x00\x00\x00\xe9\x0b\x00\x00\x00\xe9*\x00\x00\x00\xe9\x05\x00\x00\x00i*\x05\x00\x00\xe9\x07\x00\x00\x00\xe9\n\x00\x00\x00i\x04\x01\x00\x00\xe9\t\x00\x00\x00\xe9\x08\x00\x00\x00\xe9\x11\x00\x00\x00\xf3\x01\x00\x00\x00a\xe97\x00\x00\x00\xe9\x0c\x00\x00\x00\xe9\x0e\x00\x00\x00\xe9\r\x00\x00\x00\xe9 \x00\x00\x00\xe9\x0f\x00\x00\x00\xe9\x17\x00\x00\x00\xe9}\x00\x00\x00z\x0bvalid key! z\x0einvalid key :(N)\x0eZ\x07hashlibr\x03\x00\x00\x00\xda\x03str\xda\x05input\xda\x06encode\xda\x01k\xda\x03len\xda\x03sum\xda\x03int\xda\x03chr\xda\x06digestZ\x07correct\xda\x05print\xda\x06decode\xa9\x00r)\x00\x00\x00r)\x00\x00\x00\xfa\r<disassembly>\xda\x08<module>\x01\x00\x00\x00sF\x00\x00\x00\x0c\x02\x10\x03\x0e\x01\n\xff\x04\x02\x12\xfe\x04\x03\x1a\xfd\x04\x04\n\xfc\x04\x05\x16\xfb\x04\x06\x12\xfa\x04\x07\x1a\xf9\x04\x08\x1e\xf8\x04\t\x0e\xf7\x04\n\x12\xf6\x04\x0b"\xf5\x04\x0c\n\xf4\x04\r\x16\xf3\x04\x0e"\xf2\x04\x0f&\xf1\x04\x10\n\xee\x02\x15'
code = marshal.loads(marshalled)
print(decompile(3.8, code))
Aside from a parse error, we receive a full 285 lines of Python assembly:
L. 1 0 JUMP_FORWARD 4 'to 4'
2 LOAD_GLOBAL 99 99
4_0 COME_FROM 112 '112'
4_1 COME_FROM 0 '0'
4 LOAD_CONST 0
6 LOAD_CONST ('md5',)
8 IMPORT_NAME hashlib
10 IMPORT_FROM md5
L. 3 12 STORE_NAME md5
14 POP_TOP
16 LOAD_NAME str
18 LOAD_NAME input
20 LOAD_STR 'please supply a valid key:'
22 CALL_FUNCTION_1 1 ''
24 CALL_FUNCTION_1 1 ''
26 LOAD_METHOD encode
L. 6 28 CALL_METHOD_0 0 ''
30 STORE_NAME k
32 LOAD_NAME len
34 LOAD_NAME k
36 CALL_FUNCTION_1 1 ''
38 LOAD_CONST 16
40 COMPARE_OP ==
L. 7 42_44 JUMP_IF_FALSE_OR_POP 462 'to 462'
46 LOAD_NAME k
48 LOAD_CONST 0
50 BINARY_SUBSCR
L. 6 52 LOAD_CONST 102
54 COMPARE_OP ==
L. 8 56_58 JUMP_IF_FALSE_OR_POP 462 'to 462'
60 LOAD_NAME k
62 LOAD_CONST 1
64 BINARY_SUBSCR
66 LOAD_NAME k
68 LOAD_CONST 0
70 BINARY_SUBSCR
72 LOAD_CONST 6
L. 6 74 BINARY_ADD
76 COMPARE_OP ==
L. 9 78_80 JUMP_IF_FALSE_OR_POP 462 'to 462'
82 LOAD_NAME k
84 LOAD_CONST 2
86 BINARY_SUBSCR
88 LOAD_NAME k
90 LOAD_CONST 1
92 BINARY_SUBSCR
94 LOAD_NAME k
96 LOAD_CONST 0
98 BINARY_SUBSCR
100 BINARY_SUBTRACT
102 LOAD_CONST 91
L. 6 104 BREAK_LOOP 116 'to 116'
106 FOR_ITER 110 'to 110'
L. 10 108 BREAK_LOOP 112 'to 112'
110 JUMP_FORWARD 114 'to 114'
112_0 COME_FROM 108 '108'
112 POP_JUMP_IF_FALSE 4 'to 4'
114_0 COME_FROM 110 '110'
114 JUMP_BACK 4 'to 4'
116_0 COME_FROM 104 '104'
116 BINARY_ADD
L. 6 118 COMPARE_OP ==
120_122 JUMP_IF_FALSE_OR_POP 462 'to 462'
124 LOAD_NAME k
126 LOAD_CONST 3
128 BINARY_SUBSCR
130 LOAD_CONST 103
132 COMPARE_OP ==
134_136 JUMP_IF_FALSE_OR_POP 462 'to 462'
138 LOAD_NAME k
140 LOAD_CONST 4
142 BINARY_SUBSCR
L. 6 144 LOAD_NAME k
146 LOAD_CONST 11
L. 12 148 BINARY_SUBSCR
150 LOAD_CONST 3
152 BINARY_MULTIPLY
154 LOAD_CONST 42
156 BINARY_SUBTRACT
158 COMPARE_OP ==
160_162 JUMP_IF_FALSE_OR_POP 462 'to 462'
164 LOAD_NAME k
L. 6 166 LOAD_CONST 5
168 BINARY_SUBSCR
L. 13 170 LOAD_NAME sum
172 LOAD_NAME k
174 CALL_FUNCTION_1 1 ''
176 LOAD_CONST 1322
178 BINARY_SUBTRACT
180 COMPARE_OP ==
182_184 JUMP_IF_FALSE_OR_POP 462 'to 462'
186 LOAD_NAME k
188 LOAD_CONST 6
190 BINARY_SUBSCR
192 LOAD_NAME k
194 LOAD_CONST 7
L. 6 196 BINARY_SUBSCR
198 BINARY_ADD
L. 14 200 LOAD_NAME k
202 LOAD_CONST 10
204 BINARY_SUBSCR
206 BINARY_ADD
208 LOAD_CONST 260
210 COMPARE_OP ==
212_214 JUMP_IF_FALSE_OR_POP 462 'to 462'
216 LOAD_NAME int
218 LOAD_NAME chr
220 LOAD_NAME k
222 LOAD_CONST 7
224 BINARY_SUBSCR
226 CALL_FUNCTION_1 1 ''
228 LOAD_CONST 2
L. 6 230 BINARY_MULTIPLY
232 CALL_FUNCTION_1 1 ''
L. 15 234 LOAD_CONST 1
236 BINARY_ADD
238 LOAD_NAME k
240 LOAD_CONST 9
242 BINARY_SUBSCR
244 COMPARE_OP ==
246_248 JUMP_IF_FALSE_OR_POP 462 'to 462'
250 LOAD_NAME k
L. 16 252 LOAD_CONST 8
254 BINARY_SUBSCR
256 LOAD_CONST 17
258 BINARY_MODULO
260 LOAD_CONST 16
262 COMPARE_OP ==
264_266 JUMP_IF_FALSE_OR_POP 462 'to 462'
268 LOAD_NAME k
L. 6 270 LOAD_CONST 9
272 BINARY_SUBSCR
L. 17 274 LOAD_NAME k
276 LOAD_CONST 8
278 BINARY_SUBSCR
280 LOAD_CONST 2
282 BINARY_MULTIPLY
284 COMPARE_OP ==
286_288 JUMP_IF_FALSE_OR_POP 462 'to 462'
290 LOAD_NAME md5
292 LOAD_NAME k
294 LOAD_CONST 10
296 BINARY_SUBSCR
298 LOAD_CONST b'a'
300 BINARY_MULTIPLY
302 CALL_FUNCTION_1 1 ''
304 LOAD_METHOD digest
306 CALL_METHOD_0 0 ''
L. 6 308 LOAD_CONST 0
310 BINARY_SUBSCR
L. 18 312 LOAD_CONST 1
314 BINARY_SUBTRACT
316 LOAD_NAME k
318 LOAD_CONST 3
320 BINARY_SUBSCR
L. 6 322 COMPARE_OP ==
324 ROT_TWO
L. 19 326 ROT_TWO
328_330 JUMP_IF_FALSE_OR_POP 462 'to 462'
332 LOAD_NAME k
334 LOAD_CONST 11
336 BINARY_SUBSCR
338 LOAD_CONST 55
340 COMPARE_OP ==
342_344 JUMP_IF_FALSE_OR_POP 462 'to 462'
346 LOAD_NAME k
L. 6 348 LOAD_CONST 12
350 BINARY_SUBSCR
L. 20 352 LOAD_NAME k
354 LOAD_CONST 14
356 BINARY_SUBSCR
358 LOAD_CONST 2
360 BINARY_TRUE_DIVIDE
362 LOAD_CONST 2
364 BINARY_SUBTRACT
366 COMPARE_OP ==
368_370 JUMP_IF_FALSE_OR_POP 462 'to 462'
372 LOAD_NAME k
374 LOAD_CONST 13
376 BINARY_SUBSCR
378 LOAD_NAME k
380 LOAD_CONST 10
382 BINARY_SUBSCR
384 LOAD_NAME k
L. 6 386 LOAD_CONST 8
388 BINARY_SUBSCR
L. 21 390 BINARY_MULTIPLY
392 LOAD_CONST 32
394 BINARY_MODULO
396 LOAD_CONST 2
398 BINARY_MULTIPLY
400 LOAD_CONST 1
402 BINARY_SUBTRACT
404 COMPARE_OP ==
406_408 JUMP_IF_FALSE_OR_POP 462 'to 462'
410 LOAD_NAME k
412 LOAD_CONST 14
414 BINARY_SUBSCR
416 LOAD_NAME k
418 LOAD_CONST 12
420 BINARY_SUBSCR
422 LOAD_NAME k
424 LOAD_CONST 9
426 BINARY_SUBSCR
L. 6 428 BINARY_XOR
430 LOAD_NAME k
L. 22 432 LOAD_CONST 15
434 BINARY_SUBSCR
436 BINARY_XOR
438 LOAD_CONST 3
440 BINARY_MULTIPLY
L. 4 442 LOAD_CONST 23
L. 25 444 BINARY_SUBTRACT
446 COMPARE_OP ==
448_450 JUMP_IF_FALSE_OR_POP 462 'to 462'
452 LOAD_NAME k
454 LOAD_CONST 15
456 BINARY_SUBSCR
458 LOAD_CONST 125
460 COMPARE_OP ==
462_0 COME_FROM 448 '448'
462_1 COME_FROM 406 '406'
462_2 COME_FROM 368 '368'
462_3 COME_FROM 342 '342'
462_4 COME_FROM 328 '328'
462_5 COME_FROM 286 '286'
462_6 COME_FROM 264 '264'
462_7 COME_FROM 246 '246'
462_8 COME_FROM 212 '212'
462_9 COME_FROM 182 '182'
462_10 COME_FROM 160 '160'
462_11 COME_FROM 134 '134'
462_12 COME_FROM 120 '120'
462_13 COME_FROM 78 '78'
462_14 COME_FROM 56 '56'
462_15 COME_FROM 42 '42'
462 STORE_NAME correct
464 LOAD_NAME print
466 LOAD_NAME correct
468_470 POP_JUMP_IF_FALSE 486 'to 486'
472 LOAD_STR 'valid key! '
474 LOAD_NAME k
476 LOAD_METHOD decode
478 CALL_METHOD_0 0 ''
480 FORMAT_VALUE 0 ''
482 BUILD_STRING_2 2
484 JUMP_FORWARD 488 'to 488'
486_0 COME_FROM 468 '468'
486 LOAD_STR 'invalid key :('
488_0 COME_FROM 484 '484'
488 CALL_FUNCTION_1 1 ''
490 POP_TOP
Analyzing the bytecode instructions
At first glance, the code seems to perform checks on specific characters of the key, relying on simple operations such as BINARY_ADD and BINARY_XOR. Luckily, Python has a documentation detailing each of the instructions.
After loading the hashlib library, the instructions perform multiple comparisons, each jumping to
JUMP_IF_FALSE_OR_POP 462 ‘to 462’
if the comparison produces false. Looking at the last section of the code, we can infer that this likely terminates the program and produces “invalid key :(”. So, we need to find a string that satisfies all of these comparisons. There are too many to go into detail, but some examples include:
46 LOAD_NAME k
48 LOAD_CONST 0
50 BINARY_SUBSCR # k[0]
L. 6 52 LOAD_CONST 102
54 COMPARE_OP == # k[0] == 102
L. 8 56_58 JUMP_IF_FALSE_OR_POP 462 'to 462'
Which performs a simple check to see if the first character of the string (k) is 102 (‘f’).
And
290 LOAD_NAME md5
292 LOAD_NAME k
294 LOAD_CONST 10
296 BINARY_SUBSCR # k[10]
298 LOAD_CONST b'a'
300 BINARY_MULTIPLY # k[10] * b'a'
302 CALL_FUNCTION_1 1 ''
304 LOAD_METHOD digest # md5(k[10] * b'a')
306 CALL_METHOD_0 0 ''
L. 6 308 LOAD_CONST 0
310 BINARY_SUBSCR # md5(k[10] * b'a')[0]
L. 18 312 LOAD_CONST 1
314 BINARY_SUBTRACT # md5(k[10] * b'a')[0] - 1
316 LOAD_NAME k
318 LOAD_CONST 3
320 BINARY_SUBSCR # k[3]
L. 6 322 COMPARE_OP == # md5(k[10] * b'a')[0] - 1 == k[3]
324 ROT_TWO
L. 19 326 ROT_TWO
328_330 JUMP_IF_FALSE_OR_POP 462 'to 462'
Which calculates the first byte of the md5 hash for (k[10] * ‘a’), subtracts 1, and compares it with k[3]
After going through each of these comparisons, we can compile a list of the different checks:
k[0] = 102
k[0] + 6 = k[1]
k[2] = k[1] - k[0] + 91
k[3] = 103
k[4] = k[11] * 3 - 42
k[5] = sum_of_chars(k) - 1332
k[6] + k[7] + k[10] = 260
int(chr(k[7]) * 2) + 1 = k[9]
k[8] % 17 = 16
k[9] = 2 * k[8]
md5(k[10] * b'a')[0] - 1 = k[3]
k[11] = 55
k[12] = k[14]/2 - 2
k[13] = 2 * [(k[10] * k[8]) % 32] - 1
k[14] = (k[12] ^ k[9] ^ k[15]) * 3 - 23
Notice that there are 15 equations and 15 characters to solve for, which works out perfectly! We can find the first few characters with some simple arithmetic. Similarly, we can solve for k[7], k[8], and k[9] since there are only a few possibilities. Finally, with a little brute force, we can uncover the rest of the characters.
Flag: flag{5f92de703d}
whatthehecc [198]
Go hecc it! nc flu.xxx 20085
#!/usr/bin/env python3
import sys
import shlex
import subprocess
from Cryptodome.PublicKey import ECC
from Cryptodome.Hash import SHA3_256
from Cryptodome.Math.Numbers import Integer
import time
# util
def run_cmd(cmd):
try:
args = shlex.split(cmd)
return subprocess.check_output(args).decode('utf-8')
except Exception as ex:
return str(ex)
def read_message():
return sys.stdin.readline()
def send_message(message):
sys.stdout.write('### {0}\r\n>'.format(message))
sys.stdout.flush()
# crypto stuff
def hash(msg):
h_obj = SHA3_256.new()
h_obj.update(msg.encode())
return Integer.from_bytes(h_obj.digest())
def setup(curve):
key = ECC.generate(curve=curve)
return key
def blind(msg, pub):
r = pub.pointQ * hash(msg)
return r
def sign(r, key):
r_prime = r * key.d.inverse(key._curve.order)
date = int(time.time())
nonce = Integer.random_range(min_inclusive=1,max_exclusive=key._curve.order)
z = f'{nonce}||{date}'
R = r_prime + (key._curve.G * hash(z))
s = (key.d - hash(z)) % key._curve.order
# return (R, s, z)
# we can not give away z or this is unsafe: x = s+h(z)
return R, s
def verify(msg, sig, pub):
R, s = sig
if s in [0,1,''] and s > 0:
return False
tmp1 = s * pub._curve.G
tmp2 = - pub.pointQ
tmp3 = tmp2 + R
return tmp1 + tmp3 == hash(msg) * pub._curve.G
## ok ok here we go
def main():
while True:
send_message('Enter your command:')
cmd = read_message().strip()
if cmd == 'sign':
send_message('Send cmd to sign:')
cmd = read_message().strip()
if(cmd in ['id', 'uname', 'ls', 'date']):
r = blind(cmd, pubkey)
sig = sign(r, key)
send_message(f'Here you go: {sig[0].x}|{sig[0].y}|{sig[1]}|{cmd}')
else:
send_message('Not allowed!')
elif cmd == 'run':
send_message('Send sig:')
sig = read_message().strip()
tmp = sig.split('|')
if len(tmp) == 4:
x = int(tmp[0])
y = int(tmp[1])
s = int(tmp[2])
c = tmp[3]
sig = (ECC.EccPoint(x, y, curve='P-256'), s)
if(verify(c, sig, pubkey)):
out = run_cmd(c)
send_message(out)
else:
send_message('Invalid sig!')
else:
send_message('Invalid amount of params!')
elif cmd == 'show':
send_message(pubkey)
elif cmd == 'help':
send_message('Commands: exit, help, show, run, sign')
elif cmd == 'exit':
send_message('Bye :) Have a nice day!')
break
else:
send_message('Invalid command!')
if __name__ == '__main__':
key = setup('P-256')
pubkey = key.public_key()
main()
We’re given a server that can sign certain messages with elliptic curves; since the flag is located at ./flag.txt, we need to forge a signature for cat flag or a similar command.
Examining the sign and verify functions, we notice that they differ from the standard ECDSA signature algorithm.
Signing
We can begin by looking at how the signature and verification processes work. Here, I’ll use the notation:
- Q: public key
- d: private key
- G: generator
- H(msg): hash(msg)
The signature process starts with r = blind(cmd, pubkey), where cmd is limited to ‘id’, ‘uname’, ‘ls’, ‘date’. Looking at the blind function:
$$r = H(\text{cmd}) * Q$$
def sign(r, key):
r_prime = r * key.d.inverse(key._curve.order)
date = int(time.time())
nonce = Integer.random_range(min_inclusive=1,max_exclusive=key._curve.order)
z = f'{nonce}||{date}'
R = r_prime + (key._curve.G * hash(z))
...
The function then creates an r_prime variable and a random nonce. Writing R in terms of our previous expressions:
$$R = r' + G * H(z) = H(\text{cmd}) * Q * d^{-1} + G * H(z) = H(\text{cmd}) * G + G * H(z)$$
s = (key.d - hash(z)) % key._curve.order
Additionally, we have:
$$s = d - H(z)$$
Verifying
Now, we can look at how the verification algorithms works if we pass in:
$$(R, s) = (H(\text{cmd}) * G + G * H(z), d - H(z))$$
tmp1 = s * pub._curve.G
tmp2 = - pub.pointQ
tmp3 = tmp2 + R
Then, the values of the tmp variables are:
$$\begin{align}\text{tmp1} &= s * G = (d - H(z)) * G = d * G - G * H(z) = Q - G * H(z)\\ \text{tmp2} &= -Q\\ \text{tmp3} &= R - Q = H(\text{cmd}) * G + G * H(z) - Q\end{align}$$
return tmp1 + tmp3 == hash(msg) * pub._curve.G
Notice that when we add tmp1 and tmp3 to perform the final check, almost all of the variables cancel out:
$$\text{tmp1} + \text{tmp3} = [H(\text{cmd}) * G + G * H(z) - Q] + [Q - G * H(z)] = H(\text{cmd}) * G$$
Thus, the verification holds if we supply $R$ and $s$ that satisfy the equation above:
$$(R, s) = (H(\text{cmd}) * G + G * H(z), d - H(z))$$
Forging a signature
Initially, I had thought of recovering the private key $d$ from a signature since we have two unknowns ($H(z)$ and $d$) and two equations. Unfortunately, this turned out to be just as hard as the ECDLP, so I turned toward directly forging a signature instead.
Notice that we can rearrange the equation for $s$ to:
$$\begin{align}H(z) = d - s\end{align}$$
Substituting this into the expression for R gives:
$$R = H(\text{cmd}) * G + G * H(z) = H(\text{cmd}) * G + G * (d - s) = H(\text{cmd}) * G + Q - G * s$$
In other words, we’ve managed to get rid of the nonce ($H(z)$) and construct a (seemingly) valid signature of:
$$(R, s) = (H(\text{cmd}) * G + Q - G * s, s)$$
Now we can check if our forged signature passes the verification.
tmp1 = s * pub._curve.G
tmp2 = - pub.pointQ
tmp3 = tmp2 + R
The values of the tmp variables are:
$$\begin{align}\text{tmp1} &= s * G \\ \text{tmp2} &= -Q\\ \text{tmp3} &= R - Q = H(\text{cmd}) * G + Q - G * s - Q = H(\text{cmd}) * G - G * s\end{align}$$
And so,
$$\text{tmp1} + \text{tmp3} = s * G + H(\text{cmd}) * G - G * s = H(\text{cmd})$$
We’ve succesfully forged a signature for any $\text{cmd}$ we want!
A local proof of concept:
...
Q = pubkey.pointQ
G = key._curve.G
r = blind('ls', pubkey)
R1, s1 = sign(r, key)
R = hash('cat flag') * G + Q + s1 * (-G)
sig = (ECC.EccPoint(R.x, R.y, curve='P-256'), int(s1))
assert(verify('cat flag', sig, pubkey))
Flag: flag{d1d_you_f1nd_chakraborty_mehta}