SECCON 2014 quals # Crypto – Decrypt it (Easy)

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

 
crypt1
 

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...
 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *


*

Captcha loading...