PwdCheck CTF
This challenge is done by providing a c file.
The file can be downloaded here: https://marcan.st/transf/pwdcheck.c
The contents are as below:
#include <stdint.h>
#include <stdio.h>
#define u uint8_t
#define c uint16_t
#define t uint32_t
#define o putchar
u r[16]={0};
c m[256]={
0x0082, 0x1945, 0x1f55, 0x060f, 0x00f7, 0x05f2, 0x04f3, 0x01f5, 0x061f,
0x1f53, 0x0b4f, 0x0722, 0x0231, 0x0877, 0x1f03, 0x00e7, 0x0aef, 0x1f05,
0x00d6, 0x09df, 0x04de, 0x015d, 0x1f4b, 0x034f, 0x241c, 0x1f41, 0x0bf4,
0x066f, 0x1f4c, 0x010f, 0x00f0, 0x0001, 0x0012, 0x0023, 0x0034, 0x0045,
0x0056, 0x0067, 0x007f, 0x1f01, 0x029f, 0x1f00, 0x039f, 0x2202, 0x1fc8,
0x03f0, 0x2252, 0x1fb6, 0x03f1, 0x2252, 0x1f0f, 0x03f2, 0x2252, 0x1fec,
0x03f3, 0x2252, 0x1f6c, 0x03f4, 0x2252, 0x1f94, 0x03f5, 0x2252, 0x1fad,
0x03f6, 0x2252, 0x1f5d, 0x03f7, 0x2252, 0x383a, 0x381c, 0x380a, 0x380a,
0x380c, 0x381a, 0x381a, 0x3848, 0x3849, 0x3853, 0x3844, 0x382d, 0x3863,
0xffff, 0x1fa9, 0x3fef, 0x3fc8, 0x3fc0, 0x3fc5, 0x3fdc, 0x3fdb, 0x3fcc,
0x3f89, 0x3f93, 0x3f84, 0x3ff9, 0x3fa3, 0xffff,
};
u p;
u s[7];
void test(t h, t l)
{
p=0;
s[0]=1;
r[0]=h>>24;r[1]=h>>16;r[2]=h>>8;r[3]=h;
r[4]=l>>24;r[5]=l>>16;r[6]=l>>8;r[7]=l;
while(1) {
u w = m[p]>>12, x = (m[p]>>8)&0xf, y=(m[p]>>4)&0xf, z=m[p]&0xf;
if(w==0) switch(x) {
case 0: r[y]=r[z]; break;
case 1: r[y]+=r[z]; break;
case 2: r[y]-=r[z]; break;
case 3: s[1]=r[y]==r[z];s[2]=r[y]!=r[z];s[3]=r[y]<r[z];s[4]=r[y]>r[z];s[5]=r[y]<=r[z];s[6]=r[y]>=r[z]; break;
case 4: r[y]|=r[z]; break;
case 5: r[y]&=r[z]; break;
case 6: r[y]^=r[z]; break;
case 7: r[y]=~r[z]; break;
case 8: r[y]=-r[z]; break;
case 9: r[y]<<=r[z]; break;
case 10: r[y]>>=r[z]; break;
case 11: r[y]*=r[z]; break;
}
else if (w==1) r[x]=m[p];
else if (w==2&&s[x]) p=m[p]-1;
else if (w==3) o(m[p]^r[x]);
else if (w==15) break;
p++;
}
}
int main(int argc, char **argv)
{
uint32_t khi, klo;
printf("Enter 64bit key (hex): ");
scanf("%8x%8x", &khi, &klo);
test(khi, klo);
return 0;
}
First analysis
From a rapid glance, we determine from the switch this is a simple CPU interpreter. First steps are:
- Removing the unnecessary #define
- Removing the prompt for the password
We undertsand that this is an 8bits machine with 16bits instruction encoding.
Disassembler
It’s pretty easy to write a disassembler for this encoding.
data=[
0x0082, 0x1945, 0x1f55, 0x060f, 0x00f7, 0x05f2, 0x04f3, 0x01f5, 0x061f,
0x1f53, 0x0b4f, 0x0722, 0x0231, 0x0877, 0x1f03, 0x00e7, 0x0aef, 0x1f05,
0x00d6, 0x09df, 0x04de, 0x015d, 0x1f4b, 0x034f, 0x241c, 0x1f41, 0x0bf4,
0x066f, 0x1f4c, 0x010f, 0x00f0, 0x0001, 0x0012, 0x0023, 0x0034, 0x0045,
0x0056, 0x0067, 0x007f, 0x1f01, 0x029f, 0x1f00, 0x039f, 0x2202, 0x1fc8,
0x03f0, 0x2252, 0x1fb6, 0x03f1, 0x2252, 0x1f0f, 0x03f2, 0x2252, 0x1fec,
0x03f3, 0x2252, 0x1f6c, 0x03f4, 0x2252, 0x1f94, 0x03f5, 0x2252, 0x1fad,
0x03f6, 0x2252, 0x1f5d, 0x03f7, 0x2252, 0x383a, 0x381c, 0x380a, 0x380a,
0x380c, 0x381a, 0x381a, 0x3848, 0x3849, 0x3853, 0x3844, 0x382d, 0x3863,
0xffff, 0x1fa9, 0x3fef, 0x3fc8, 0x3fc0, 0x3fc5, 0x3fdc, 0x3fdb, 0x3fcc,
0x3f89, 0x3f93, 0x3f84, 0x3ff9, 0x3fa3, 0xffff]
operations={
0: 'MOV r{0}, r{1}',
1: 'MOV r{0}, r{0}+r{1}',
2: 'MOV r{0}, r{0}-r{1}',
3: 'UPF r{0}, r{1}',
4: 'MOV r{0}, r{0}|r{1}',
5: 'MOV r{0}, r{0}&r{1}',
6: 'MOV r{0}, r{0}^r{1}',
7: 'MOV r{0}, ~r{1}',
8: 'MOV r{0}, -r{1}',
9: 'MOV r{0}, r{0}<<r{1}',
10: 'MOV r{0}, r{0}>>r{1}',
11: 'MOV r{0}, r{0}*r{1}',
}
jmpcnd={
0: 'JMP',
1: 'JEQ',
2: 'JNE',
3: 'JL ',
4: 'JG ',
5: 'JLE',
6: 'JGE',
7: 'INVALID'
}
def disassemble(char, loc):
#print(hex(char))
opcode, opadd, reg1, reg2= (char >> 12), (char >> 8)&0xf, (char>>4)&0xf, (char&0xf)
word=char&0xff
#print(opcode,opadd, reg1, reg2)
r=hex(loc)+': '
if opcode==0:
r+=operations[opadd].format(reg1, reg2)
elif opcode==1:
r+='MOV r{},{}'.format(opadd, hex(word))
elif opcode==2:
r+='{} {}'.format(jmpcnd[opadd], hex(word))
elif opcode==3:
r+='OUT r{}^{}'.format(opadd, hex(word))
elif opcode==15:
r+='HALT'
return r
for l, i in enumerate(data[:]):
print(disassemble(i, l))
We obtain the following disassembly:
0x00: MOV r8, r2
0x01: MOV r9,0x45
0x02: MOV r15,0x55
0x03: MOV r0, r0^r15
0x04: MOV r15, r7
0x05: MOV r15, r15&r2
0x06: MOV r15, r15|r3
0x07: MOV r15, r15+r5
0x08: MOV r1, r1^r15
0x09: MOV r15,0x53
0x0a: MOV r4, r4*r15
0x0b: MOV r2, ~r2
0x0c: MOV r3, r3-r1
0x0d: MOV r7, -r7
0x0e: MOV r15,0x3
0x0f: MOV r14, r7
0x10: MOV r14, r14 >> r15
0x11: MOV r15,0x5
0x12: MOV r13, r6
0x13: MOV r13, r13 << r15
0x14: MOV r13, r13|r14
0x15: MOV r5, r5+r13
0x16: MOV r15,0x4b
0x17: UPF r4, r15
0x18: JG 0x1c
0x19: MOV r15,0x41
0x1a: MOV r15, r15*r4
0x1b: MOV r6, r6^r15
0x1c: MOV r15,0x4c
0x1d: MOV r0, r0+r15
0x1e: MOV r15, r0
0x1f: MOV r0, r1
0x20: MOV r1, r2
0x21: MOV r2, r3
0x22: MOV r3, r4
0x23: MOV r4, r5
0x24: MOV r5, r6
0x25: MOV r6, r7
0x26: MOV r7, r15
0x27: MOV r15,0x1
0x28: MOV r9, r9-r15
0x29: MOV r15,0x0
0x2a: UPF r9, r15
0x2b: JNE 0x2
0x2c: MOV r15,0xc8
0x2d: UPF r15, r0
0x2e: JNE 0x52
0x2f: MOV r15,0xb6
0x30: UPF r15, r1
0x31: JNE 0x52
0x32: MOV r15,0xf
0x33: UPF r15, r2
0x34: JNE 0x52
0x35: MOV r15,0xec
0x36: UPF r15, r3
0x37: JNE 0x52
0x38: MOV r15,0x6c
0x39: UPF r15, r4
0x3a: JNE 0x52
0x3b: MOV r15,0x94
0x3c: UPF r15, r5
0x3d: JNE 0x52
0x3e: MOV r15,0xad
0x3f: UPF r15, r6
0x40: JNE 0x52
0x41: MOV r15,0x5d
0x42: UPF r15, r7
0x43: JNE 0x52
0x44: OUT r8^0x3a
0x45: OUT r8^0x1c
0x46: OUT r8^0xa
0x47: OUT r8^0xa
0x48: OUT r8^0xc
0x49: OUT r8^0x1a
0x4a: OUT r8^0x1a
0x4b: OUT r8^0x48
0x4c: OUT r8^0x49
0x4d: OUT r8^0x53
0x4e: OUT r8^0x44
0x4f: OUT r8^0x2d
0x50: OUT r8^0x63
0x51: HALT
0x52: MOV r15,0xa9
0x53: OUT r15^0xef
0x54: OUT r15^0xc8
0x55: OUT r15^0xc0
0x56: OUT r15^0xc5
0x57: OUT r15^0xdc
0x58: OUT r15^0xdb
0x59: OUT r15^0xcc
0x5a: OUT r15^0x89
0x5b: OUT r15^0x93
0x5c: OUT r15^0x84
0x5d: OUT r15^0xf9
0x5e: OUT r15^0xa3
0x5f: HALT
Strings
From that point, it’s not hard to determine that the last string is ‘Failure!’ and the first before is ‘Success !’.
In order to find ‘Success’, we need to bruteforce all the 256 possibles values for r8.
Correct one is 105.
Reversing the algorithm
After reading a bit more, we can annotate the file as follow:
0x0: MOV r8, r2 //r2=105 (bc r8 should contains 105)
0x1: MOV r9,0x45 //init round number
0x2: MOV r15,0x55
0x3: MOV r0, r0^r15
0x4: MOV r15, r7
0x5: MOV r15, r15&r2
0x6: MOV r15, r15|r3
0x7: MOV r15, r15+r5
0x8: MOV r1, r1^r15 //r1=((r7&r2)|r3)+r5
0x9: MOV r15,0x53
0xa: MOV r4, r4*r15 //r4=r4*0x53
0xb: MOV r2, ~r2 //r2=~r2
0xc: MOV r3, r3-r1 //r3=r3-r1
0xd: MOV r7, -r7 //r7=-r7
0xe: MOV r15,0x3
0xf: MOV r14, r7
0x10: MOV r14, r14>>r15
0x11: MOV r15,0x5
0x12: MOV r13, r6
0x13: MOV r13, r13<<r15 //r13=r13<<5
0x14: MOV r13, r13|r14 // r13=r13|r14
0x15: MOV r5, r5+r13 //r5=r5+(r6<<5|r7>>3)
//if r4 > 0x4b
0x16: MOV r15,0x4b
0x17: UPF r4, r15
0x18: JG 0x1c
//{
0x19: MOV r15,0x41
0x1a: MOV r15, r15*r4
0x1b: MOV r6, r6^r15 //r6=r6^(r4*0x41)
//}
//r15=r0+0x4c
0x1c: MOV r15,0x4c
0x1d: MOV r0, r0+r15
0x1e: MOV r15, r0
//shift r1->r7 to r0->r6 r7=r0+0x4c value=(value >> 1) + (value[0]+0x4c) << 7
0x1f: MOV r0, r1
0x20: MOV r1, r2
0x21: MOV r2, r3
0x22: MOV r3, r4
0x23: MOV r4, r5
0x24: MOV r5, r6
0x25: MOV r6, r7
0x26: MOV r7, r15
//45 rounds
0x27: MOV r15,0x1
0x28: MOV r9, r9-r15
0x29: MOV r15,0x0
0x2a: UPF r9, r15
0x2b: JNE 0x2
0x2c: MOV r15,0xc8
0x2d: UPF r15, r0
0x2e: JNE 0x52
0x2f: MOV r15,0xb6
0x30: UPF r15, r1
0x31: JNE 0x52
0x32: MOV r15,0xf
0x33: UPF r15, r2
0x34: JNE 0x52
0x35: MOV r15,0xec
0x36: UPF r15, r3
0x37: JNE 0x52
0x38: MOV r15,0x6c
0x39: UPF r15, r4
0x3a: JNE 0x52
0x3b: MOV r15,0x94
0x3c: UPF r15, r5
0x3d: JNE 0x52
0x3e: MOV r15,0xad
0x3f: UPF r15, r6
0x40: JNE 0x52
0x41: MOV r15,0x5d
0x42: UPF r15, r7
0x43: JNE 0x52
0x44: OUT r8^0x3a
0x45: OUT r8^0x1c
0x46: OUT r8^0xa
0x47: OUT r8^0xa
0x48: OUT r8^0xc
0x49: OUT r8^0x1a
0x4a: OUT r8^0x1a
0x4b: OUT r8^0x48
0x4c: OUT r8^0x49
0x4d: OUT r8^0x53
0x4e: OUT r8^0x44
0x4f: OUT r8^0x2d
0x50: OUT r8^0x63
0x51: HALT
0x52: MOV r15,0xa9
0x53: OUT r15^0xef
0x54: OUT r15^0xc8
0x55: OUT r15^0xc0
0x56: OUT r15^0xc5
0x57: OUT r15^0xdc
0x58: OUT r15^0xdb
0x59: OUT r15^0xcc
0x5a: OUT r15^0x89
0x5b: OUT r15^0x93
0x5c: OUT r15^0x84
0x5d: OUT r15^0xf9
0x5e: OUT r15^0xa3
0x5f: HALT
The final test is:
r0==0xc8 &&
r1==0xb6 &&
r2==0x0f &&
r3==0xec &&
r4==0x6c &&
r5==0x94 &&
r6==0xad &&
r7==0x5d
We also have to include the correct value of r8. We can see that r10, r11, etc. are not used.
Reversing
At that point, we think we have to reverse 45 rounds of mangling of the input.
One round looks like this (after simplification):
r0=r0^0x55
r1=r1^(((r7&r2)|r3)+r5)
r4=r4*0x53
r2=~r2
r3=r3-r1
r7=-r7
r5=r5+(r6<<5|r7>>3)
if r4 <= 0x4b:
r6=r6^(r4*0x41)
r0, r1, r2, r3, r4, r5, r6, r7 = r1, r2, r3, r4, r5, r6, r7, r0+0x4c
We thus write the following python program:
forward='''
r0=r0^0x55
r1=r1^(((r7&r2)|r3)+r5)
r4=r4*0x53
r2=~r2
r3=r3-r1
r7=-r7
r5=r5+(r6<<5|r7>>3)
if r4 <= 0x4b:
r6=r6^(r4*0x41)
r0, r1, r2, r3, r4, r5, r6, r7 = r1, r2, r3, r4, r5, r6, r7, r0+0x4c
'''
def div8(r, d):
for i in range(256):
if (i*d)&0xff == r:
return i
raise Expection('Invalid div')
def onestep(r):
r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7] = r[7] - 0x04c, r[0], r[1], r[2], r[3], r[4], r[5], r[6]
if (r[4] <= 0x4b):
r[6] = (r[6]^((r[4]*0x41)&0xff))&0xff
r[5]=(256+r[5]-(((r[6]<<5)&0xff)|((r[7]>>3)&0xff)))&0xff
r[7]=256-r[7]
r[3]=(r[3]+r[1])&0xff
r[2]=(~r[2])&0xff
r[4]=div8(r[4],0x53)
r[1]=r[1]^((((r[7]&r[2])|r[3])+r[5])&0xff)
r[0]=(r[0]^0x55)&0xff
return r
r=[0xc8,0xb6,0x0f,0xec,0x6c,0x94,0xad,0x5d]
for i in range(0x45):
r=onestep(r)
for i in range(8):
print('r[{}] = {};'.format(i, r[i]))
print(''.join([chr(x) for x in r]))
It worth noting that it is easy to ensure the onestep() is correct: by changing the value 0x1945 to 0x1901 for example, only one round will be executed.
After that, it’s simply a matter of fixing up r8 and we can check if the program outputs ‘Success’.
Solution
Doing the full 45 rounds gives the following ouput:
r[0] = 56;
r[1] = 66;
r[2] = 105;
r[3] = 116;
r[4] = 70;
r[5] = 84;
r[6] = 87;
r[7] = 33;
8BitFTW!
We know we have the correct solution since r2 has a value of 105 and the password makes sense :-).