URL: http://score.quals.seccon.jp/question/
Type: crypto
Solution: SECCON{Ra_b1_N}
Description
crypt1.zip http://files.quals.seccon.jp/crypt1.zip
First part – decoding encrypted file
The given archive contains a binary, an encrypted file and a readme:
$ unzip crypt1.zip Archive: crypt1.zip inflating: ecrypt1.bin inflating: rnd inflating: readme.txt $ file rnd rnd: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, stripped
readme.txt gives us usefull information: ecrypt1.bin is an encrypted PNG file.
$ ./rnd crypt1.png ecrypt1.bin
Let’s have a look at the binary encoder assembly code:
08048514: push %ebp ... 0804852d: movl $0x0,(%esp) ; /t = NULL 08048534: call 80483e0 <time@plt> ; \=> time(t) 08048539: mov %eax,(%esp) ; /seed = time(NULL) 0804853c: call 8048420 <srand@plt> ; \=> srand(seed) 08048541: mov $0x80486f0,%edx ; "rb" 08048546: mov 0xc(%ebp),%eax 08048549: add $0x4,%eax 0804854c: mov (%eax),%eax 0804854e: mov %edx,0x4(%esp) ; /mode = "rb" 08048552: mov %eax,(%esp) ; |path = argv[1] 08048555: call 8048440 <fopen@plt> ; \=> fopen(path, mode) 0804855a: mov %eax,0x10(%esp) ; fi = fopen(argv[1], "rb") 0804855e: mov $0x80486f3,%edx ; "wb" 08048563: mov 0xc(%ebp),%eax 08048566: add $0x8,%eax 08048569: mov (%eax),%eax 0804856b: mov %edx,0x4(%esp) ; /mode = "wb" 0804856f: mov %eax,(%esp) ; |path = argv[2] 08048572: call 8048440 <fopen@plt> ; \=> fopen(path, mode) 08048577: mov %eax,0x14(%esp) ; fo = fopen(argv[2], "wb") 0804857b: lea 0x1f(%esp),%eax 0804857f: mov 0x10(%esp),%edx 08048583: mov %edx,0xc(%esp) ; /stream = fi 08048587: movl $0x1,0x8(%esp) ; |nmemb = 1 0804858f: movl $0x1,0x4(%esp) ; |size = 1 08048597: mov %eax,(%esp) ; |ptr = buffer 0804859a: call 8048400 <fread@plt> ; \=> fread(ptr, size, nmemb, stream) 0804859f: mov %eax,0x18(%esp) 080485a3: cmpl $0x1,0x18(%esp) 080485a8: jne 80485f3 080485aa: call 8048450 <rand@plt> ; => rand() 080485af: mov %eax,%edx ; i = x = rand() 080485b1: sar $0x1f,%edx ; i >>= 0x1f 080485b4: shr $0x18,%edx ; i <<= 0x18 080485b7: add %edx,%eax ; x += i 080485b9: and $0xff,%eax ; x &= 0xff 080485be: sub %edx,%eax ; x -= i 080485c0: mov %eax,%edx 080485c2: movzbl 0x1f(%esp),%eax ; buffer 080485c7: xor %edx,%eax ; buffer ^= x 080485c9: mov %al,0x1f(%esp) 080485cd: lea 0x1f(%esp),%eax 080485d1: mov 0x14(%esp),%edx 080485d5: mov %edx,0xc(%esp) ; /stream = fo 080485d9: movl $0x1,0x8(%esp) ; |nmemb = 1 080485e1: movl $0x1,0x4(%esp) ; |size = 1 080485e9: mov %eax,(%esp) ; |ptr = buffer 080485ec: call 80483f0 <fwrite@plt> ; \=> fwrite(ptr, size, nmemb, stream) 080485f1: jmp 804857b 080485f3: nop 080485f4: mov 0x10(%esp),%eax 080485f8: mov %eax,(%esp) ; /fp = fi 080485fb: call 80483d0 <fclose@plt> ; \=> fclose(fp) 08048600: mov 0x14(%esp),%eax 08048604: mov %eax,(%esp) ; /fp = fo 08048607: call 80483d0 <fclose@plt> ; \=> fclose(fp) 0804860c: mov $0x0,%eax 08048611: leave 08048612: ret
So the encryption scheme is a simple XOR with a sequence of random numbers. The trick is that the pseudo-random number generator is seeded with the system time, and we can easily retrieve this time using the creation timestamp of the ecrypt1.bin file. As stated in the srand man page:
The srand() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by rand(). These sequences are repeatable by calling srand() with the same seed value.
So let’s have a look at the « times » of the ecrypt1.bin file, and more specifically at its modify time:
$ stat ecrypt1.bin File: « ecrypt1.bin » Size: 45989 Blocks: 96 IO Block: 4096 fichier Device: 801h/2049d Inode: 49544 Links: 1 Access: (0664/-rw-rw-r--) Uid: ( 1000/ phoenix) Gid: ( 1000/ phoenix) Access: 2014-11-22 15:46:36.000000000 +0100 Modify: 2014-11-22 15:46:30.000000000 +0100 Change: 2014-12-07 00:53:58.000000000 +0100 $ stat --printf=%Y ecrypt1.bin 1416667590
Knowing the algorithm used, we can easily write a decoder:
#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { FILE *cipher = fopen(argv[1], "rb"); FILE *plain = fopen(argv[2], "wb"); unsigned int seed = atoi(argv[3]); int c; srand(seed); c = (fgetc(cipher) & 0xff) ^ (rand() & 0xff); while (!feof(cipher)) { fputc(c, plain); c = (fgetc(cipher) & 0xff) ^ (rand() & 0xff); } fclose(plain); fclose(cipher); }
… and, knowing the seed, decode the encrypted file ecrypt1.bin:
$ ./decode ecrypt1.bin crypt1.png 1416667590 $ file crypt1.png crypt1.png: PNG image data, 676 x 517, 8-bit/color RGB, non-interlaced
Second part – asymmetric cryptosystem
The decoded image shows what seems to be an asymmetric cryptosystem like Rabin‘s one :
N = pq C = M(M + B) mod N N = B8AE199365 B = FFEEE C = 8D5051562B N = B86E78C811 B = FFFEE C = 5FFA0AC1A2 N = 7BD4071E55 B = FEFEF C = 6008DDF867
The way of the ugly
The numbers are not so big so they can be bruteforced with some optimizations. We know that flag strings always look like SECCON{...}. Let’s check with the first encoding:
N, B, FLAG = 0xB8AE199365, 0xFFEEE, 'SECCON{' for i in range(1, len(FLAG)+1): M = int(FLAG[0:i].encode('hex'), 16) print FLAG[0:i]+'\t'+hex(M * (M + B) % N)
S 0x52fc213
SE 0x54f0cb0bf
SEC 0x8c0ad9b877
SECC 0x704d68c1fb
SECCO 0x8d5051562bL <== we retrieve the C value provided
SECCON 0x2339eed575L
SECCON{ 0x1bce931b16L
So message M is 5 chars length. Let's bruteforce the 5 nexts chars knowing that it starts with N{:
N, B = 0xB86E78C811, 0xFFFEE for i in range(32, 127): for j in range(32, 127): for k in range(32, 127): M = int(('N{' + chr(i) + chr(j) + chr(k)).encode('hex'), 16) if ((M * (M + B) % N) == 0x5FFA0AC1A2): print 'N{' + chr(i) + chr(j) + chr(k)
N{Ra_
And finally, let's bruteforce the last 5 chars knowing that it ends with }:
N, B = 0x7BD4071E55, 0xFEFEF for i in range(32, 127): for j in range(32, 127): for k in range(32, 127): for l in range(32, 127): M = int((chr(i) + chr(j) + chr(k) + chr(l) + '}').encode('hex'), 16) if ((M * (M + B) % N) == 0x6008DDF867): print chr(i) + chr(j) + chr(k) + chr(l) + '}'
b1_N}
The concatenation of these 3 strings gives us the final flag SECCON{Ra_b1_N}
The way of the samurai
As N is the product of two prime numbers p & q, then C = M(M + B) mod N can be expressed as:
Mp * (Mp + B) ≡ C mod p Mq * (Mq + B) ≡ C mod q
The Chinese remainder theorem can then be applied to solve M. The following code will do the job for us:
def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: q = a / b a, b = b, a%b x0, x1 = x1 - q * x0, x0 if x1 < 0: x1 += b0 return x1 def chinese_remainder(n, a, lena): p = i = prod = 1; sm = 0 for i in range(lena): prod *= n[i] for i in range(lena): p = prod / n[i] sm += a[i] * mul_inv(p, n[i]) * p return sm % prod def bruteforce(p, q, C, B): for Mp in [m for m in xrange(p) if (C % p) == (m * (m + B) % p)]: for Mq in [m for m in xrange(q) if (C % q) == (m * (m + B) % q)]: print ('%x' % chinese_remainder([p, q], [Mp, Mq], 2)).decode('hex')
(Chinese remainder parts taken from Rosetta Code)
Let's bruteforce each values:
>>> bruteforce(868019, 913799, 0x8d5051562b, 0xffeee)
eh?Q(
aN?q?
W_V"?
SECCO
>>> bruteforce(875543, 904727, 0x5ffa0ac1a2, 0xfffee)
?V ??
N{Ra_
i?f?
2_5
>>> bruteforce(597263, 890459, 0x6008ddf867, 0xfefef)
????
U?ԕ4
%?"?2
b1_N}
We then easily recover the correct parts among the solutions...