Старый 17.02.2013, 21:17   #1
Beched
 
Регистрация: 06.07.2010
Сообщений: 375
Репутация: 117
По умолчанию GitS 2013 write-ups

At these weekend we've participated in the Ghost in the Shellcode CTF event.
As usual, there were few of us, and nobody has been solving tasks constantly.
Actually, there were NO reverse-engineers among us, and tasks were full of binary stuff.
Nevertheless, as usual, again, we've managed to get some points and finished 16-th.
Thanks to ont, overxor, blackfan.

Here's a write-up on the task I liked ('cause I like Web, PPC and Crypto categories, and there was only Crypto out of them):

Crypto 250

We're given:
Цитата:
Question 12 - RabinsBitch
Points: 250

Extract the key! Answers in sha256("p=0x...,q=0x...".lower()) (File running at rabinsbitch.2013.ghostintheshellcode.com)
You can find the source code in the attachment.

At first, the service asks to solve a SHA-1 puzzle:
Код:
...
		req.sendall("You must first solve a puzzle, a sha1 sum ending in 26 bit's set to 1, it must be of length %s bytes, starting with %s"%(len(proof)+5,proof))
		test=req.recv(21)
		ha=hashlib.sha1()
		ha.update(test)
		if (test[0:16]!=proof or ord(ha.digest()[-1])!=0xff or 
            ord(ha.digest()[-2])!=0xff or
			ord(ha.digest()[-3])!=0xff or
			ord(ha.digest()[-4])&3!=3 
			):
			req.sendall("NOPE")
...
Such puzzle can be solved by the brute force. I used itertools.combinations for this purpose.
Also, there's implemented a ciphering algorithm:
Код:
...
def encrypt(m,n):
    c=pow(m,2,n)
    return c
...
The decryption is not fully correct, though it does return the correct answers (due to the Fermat's little theorem):
Код:
...
def decrypt(c,p,q):
    mp=pow(c,(p+1)/4,p)
    mq=pow(c,(q+1)/4,q)
    r1 = pow(c, (p+1)/4, p)
    r2 = pow(c, (q+1)/4, q)

    return (reste_chinois([r1, r2], [p, q]), \
                reste_chinois([-r1, r2], [p, q]), \
                reste_chinois([r1, -r2], [p, q]), \
                reste_chinois([-r1, -r2], [p, q]))
...
decrypt() returns a tuple of 4 solutions of Chinese Remainder Theorem.

So, we should obtain and factorize the modulo. First, I've used an obvious solution -- took the received tuple decrypt( 1, p, q ), say, (a,b,c,d).
Square of each of these numbers is congruent to 1 modulo n. Thus, we can obtain the modulo itself by computing the GCD of all the numbers:

Код:
...
norm = lambda x: pow( x, 2 ) - 1
r = [ norm( int( x ) ) for x in r ] #r = (a,b,c,d)
print 'GCD of the tuple is %s' % gcd( gcd( gcd( r[ 0 ], r[ 1 ] ), r[ 2 ] ), r[ 3 ] )
FactorDB.com didn't know the factors of the obtained modulo at that moment, so, I decided to perfom these actions on the decrypt( 2, p, q ).
The GCD of the new tuple turned out to be exactly p. So, the challenge was solved.

But after I've passed this task, hellman from MoreSmokedLeetChicken told me about the right way to solve this task.
Since the decrypt() functions returns the following tuple:

Код:
(reste_chinois([r1, r2], [p, q]), reste_chinois([-r1, r2], [p, q]), reste_chinois([r1, -r2], [p, q]), reste_chinois([-r1, -r2], [p, q])),
the modulo n can be computed as follows:

Код:
decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 3 ] = decrypt( 1, p, q )[ 1 ] + decrypt( 1, p, q )[ 2 ] = 
reste_chinois([r1, r2], [p, q]) + reste_chinois([-r1, -r2], [p, q]) = reste_chinois([-r1, r2], [p, q]) + reste_chinois([r1, -r2], [p, q]) = n
Than, the factors can be computing by taking GCD:

Код:
p = GCD( decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 1 ], n)
q = GCD( decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 3 ], n) = n / p
So, the final exploit looks like this (my initial solution is commented):

Код:
import hashlib, socket, re, itertools, struct
from fractions import gcd

s = socket.socket()
s.connect( ('54.235.155.218', 9955) )
tmp = s.recv( 256 )
proof = re.search( 'with (\S+)', tmp ).group( 1 )

print 'Ok, got salt: %s\nStarting brute force' % proof
charset = ''.join( [ chr( x ) for x in xrange( 0, 128 ) ] )
found = False

for comb in itertools.combinations( charset, 5 ):
    test = proof + ''.join( comb )
    ha=hashlib.sha1()
    ha.update( test )
    if ( ord( ha.digest()[ -1 ] ) == 0xff and
            ord( ha.digest()[ -2 ] ) == 0xff and
			ord( ha.digest()[ -3 ] ) == 0xff and
			ord( ha.digest()[ -4 ] ) & 3 == 3 
			):
        print 'Found %s' % test
        found = True
        break

if not found:
    print 'Could not find string =('
    quit()

s.send( test )
s.send( struct.pack( 'H', 1 ) )
s.send( chr( 1 ) )
r = ''
while 1:
    t = s.recv( 256 )
    if t == '':
        break
    r += t

#print 'Ok, decrypt( 1, p, q ) == (%s)' % r
#norm = lambda x: pow( x, 2 ) - 1
r = r.split( ',' )
#r = [ norm( int( x ) ) for x in r ]
r = [ int( x ) for x in r ]
#print 'GCD of the tuple is %s' % gcd( gcd( gcd( r[ 0 ], r[ 1 ] ), r[ 2 ] ), r[ 3 ] )
n = r[ 0 ] + r[ 3 ]
p = gcd( r[ 0 ] + r[ 1 ], n )
q = n / p
ans = 'p=%s,q=%s' % (hex( p ).rstrip( 'L' ), hex( q ).rstrip( 'L' ))
print 'W00t, the flag is %s' % hashlib.sha256( ans ).hexdigest()

s.close()
Now it's time to launch it:

Цитата:
$ python crypto250.py
Ok, got salt: U/0VkklASh1aiZsd
Starting brute force
Found U/0VkklASh1aiZsd(H`|
W00t, the flag is 98ebb2bffe5b0eb2872e395f7b504162a7c2a6fda6820c0e03 9d85ebece7bde2

P.S. Some guy (ius) in the IRC pointed that all this staff is described at wikipedia: https://en.wikipedia.org/wiki/Rabin_cryptosystem#Decryption
I just haven't thought about the name of the task and treated it as some unknown cipher algorithm.
Вложения
Тип файла: txt rabinsbitch.txt (3.0 Кб, 240 просмотров)

Последний раз редактировалось Beched; 19.02.2013 в 18:23..
Beched вне форума   Ответить с цитированием
Старый 18.02.2013, 00:32   #2
chupakabra
 
Аватар для chupakabra
 
Регистрация: 09.12.2011
Сообщений: 47
Репутация: 5
По умолчанию

staff - переводится как работники, персонал. Наверное имелось ввиду stuff.
chupakabra вне форума   Ответить с цитированием
Старый 18.02.2013, 09:12   #3
Beched
 
Регистрация: 06.07.2010
Сообщений: 375
Репутация: 117
По умолчанию

Цитата:
Сообщение от chupakabra Посмотреть сообщение
staff - переводится как работники, персонал. Наверное имелось ввиду stuff.
Спасибо, опечатка =)
Beched вне форума   Ответить с цитированием
Старый 18.02.2013, 18:30   #4
ont
 
Аватар для ont
 
Регистрация: 16.12.2010
Сообщений: 57
Репутация: 92
По умолчанию

RE 100 (slowpoke edition)
Sometimes not so hard task can be solved for the big time and with not so fast semi-manual solution :)
Warn: this writeup can be sooooooooo interesting for skilled reverse engineers...

Task consists of two files:
Код:
rtfm-67cc5dcb69df4244bcf2d573481e6d6a06b861a3  -- ELF, 32-bit, dyn-linked, stripped
rtfm-e24f03bb1204f8e3d40fae8ac135187a11b0ba5c  -- bin data, starting with RTFM bytes
Actually reversing already done when you hit f5 key in IDA in sub_80485F0. Hexrays do all hard job for us.
Pseudo code:
PHP код:
int mainint argcchar *argv[] )
{
    
/* ... file reading part ... */
    
for( int i 0file_lengthi++ )
        if( 
file_bytes] < )   // yeah, treat them as signed chars
            
exit( );              // ... only 0-127 (ASCII range) are allowed
    
    
rtfm sub_8048910file_bytesfile_length, ... );   // most funny part

    /* ... outputting rtfm to original.file.name + .rtfm ... */

Now most funny part. Hexrays decompile it to very funny variant, so i decide transform it
to python-ish equivalent:
Код:
bytes_8048CA2 = "\x0a\x00\xdb\x02\x0a\x00\xed\x02..."  ## many bytes
bytes_8048CA0 = "\xab\x02" + bytes_8048CA2

def sub_804910( bytes ):
    out = [ 0 ] * 10000   ## our empty crypto stripe
    pos = 0               ## current position in stripe
    ttt = 0               ## count of 'touches'

    for c in bytes:
        ## take secret char and word based on 'c'
        s_c = ord( bytes_8048CA2[ 4 * c ] )
        s_w = struct.unpack( 'h', bytes_8048CA0[ 4*c: 4*c+2 ] )[ 0 ]

        cnt = s_c + 2               ## calculate count of actions for byte 'c'
        xxx = s_w << ( 16 - s_c )   ## starting value for crypto-stamp

        while cnt:
            out[ pos ] *= 2         ## multiply byte!
            out[ pos ] &= 0xff      ## for python int -> byte conversion

            xxx_ = ( xxx & 0xffff ) >> 15  ## change crypto-stamp (word size)
            xxx *= 2                       ## ...
            out[ pos ] |= xxx_         ## apply crypto-stamp to stripe
            ttt += 1                   ## we touched stripe one time!

            if ttt > 7:                ## byte on stripe touched 8-times! 
                ttt, pos = 0, pos + 1  ## ... move cursor to next position

            cnt -= 1

    return 'RTFM' + out
So one byte == couple of actions on crypto-stripe. Sometimes cnt < 8, so in one byte of crypto stripe
can be stored two chars from original message.

Our goal is to recover bytes from crypted output stored in rtfm-e24f03bb1204f8e3d40fae8ac135187a11b0ba5c.

Here goes pokiest part -- I don't understand how to recover fast. =)
Idea of my algo:
Код:
1. append byte from 0-127 range to our answer
2. encrypt answer
3. if count of wrong output bytes in encrypted message less than 2 then 
   call recursion for bruting next byte
Schematic view of recursion calls:
Код:
              .
          .  /__.    .
         /  /       /
(start)-+--+-------+--------(finish)
            \ _.    \_. 
             |        
             `
Recursion finds most deepest way from start character. But it has many wrong short branches on the way.
Finally after some hours of recursion bruting and 'max recursion limit' we got a flag in mess of rtf tags.

Flag: Did I have Vari-good-code?

My slow solution with some optimizations: http://pastebin.com/Fs6eTLyh

Последний раз редактировалось ont; 18.02.2013 в 18:33..
ont вне форума   Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход



Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd. Перевод: zCarot