RuCTF Quals 2013 write-up

Hint: flag is not a frag: once you've got it, you can get one more...

Crypto 200

See the task source code in attachment. Here're the main procedures:
Код:
def generate_public_key(private_key):	
	n = 199285318978668966527551342512997250816637709274749259983292077699440369
	t = 32416190071
	return list(map(lambda x: (t * x) % n, private_key))

def crypt(open_text, public_key):
	bts = []
	[bts.extend([int(b) for b in '00000000'[len(bin(ord(c))[2:]):] + bin(ord(c))[2:]]) for c in open_text]
	return [sum(map(lambda x: x[0] * x[1] ,zip(blk, public_key))) for blk in [bts[i * 128:(i+1) * 128] for i in range(len(open_text) // 16)]]
I took the values of public_key and plugged some of them into the equation ( t * x ) % n = K, which has been easily solved by Wolfram Alpha.
It has become obvious from the obtained values of private_key (x in the equation) that it had been generated like this:
Код:
private_key = [ t ] + [ t * 2 * 3 ** i for i in xrange( 0, 127 ) ]
Encryption method crypt() just takes the binary representation of the plain-text block and multiplies each bit with the corresponding value of public key.
Now we can see that public_key[ 0 ] = t*t, and each further value of public_key has the form 2*(t**2)*(3**i).
So, we should find the coefficients b_i in the sum b_0*t*t+b_1*2*(t**2)+b_2*2*(t**2)*3+...
It could be done straightforward unless we worked in the finite group (ring) Z_n.
But since we know an exact form of the sum we can just calculate the inverse of t*t and multiply each ciphered block with its value.
So:
Код:
inv(t**t) * cipher_text[ 0 ] = b_0+b_1*2+b_2*2*3+...
Such the sum is much smaller than n, so we can easily find all the coefficients by computing cipher_text[ 0 ] % 3**i / 3**(i-1).
The inverse element of t**2 has been computed at Wolfram Alpha. Final method:
Код:
t2inv = 113733348753781020783170490400630827179237386517084745662682984487937812

def dec( block ):
    r = ''
    ohlol = t2inv * block % n
    if ohlol % 2 == 1:
        r += '1'
        ohlol -= 1
    ohlol /= 2
    for i in xrange( 1, 128 ):
        r += '%s' % (ohlol % 3 ** i / 3 ** (i - 1))
    return hex( int( r, 2 ) )[ 2: ].rstrip( 'L' ).decode( 'hex' )

for c in cipher_text:
    try:
        sys.stdout.write( dec( c ) )
    except:
        print 'FAIL'
Evaluation:
Цитата:
$ python solution.py
bf145f32d9637c37de3cb5b470b2c44f8e466bc26e06725ac1 517006ab70eac23907a37da8715981c7de813dc03f8104381e adf57d50dc4841d7956fffcd22eefe8ec62e9dea680f78d183 52b4bb3ec2
P.S. As usual, after posting the flag I found out that this algorithm has been already described at wikipedia. See http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
Crypto 300

See the task source code in attachment. Here's the key part of encryption:
Код:
for i in range((len(data) + BLOCK_SIZE - 1) // BLOCK_SIZE):
  block = data[BLOCK_SIZE * i:BLOCK_SIZE * (i + 1)]
  d = 0
  for byte in block:
    d *= 256
    d += byte
  for el in key:
    encoded_file.write(pack('H', d % el))
We're given an encoded PDF-file and encryption algorithm. For each plain-text block it first calculates the sum (c**i)*(256**(15-i)) and then takes the remainders of this sum modulo the key elements.
Thus, each cipher-text element is not greater than the corresponding key element. It can help us to narrow the brute force.
After looking through the bunch of PDF-documents one can notice that their header is pretty changeable, but it's footer is long enough (more than 16 bytes) and rather uniform. It's like:
Код:
startxref
123123
%%EOF
But there're variations with "\n" and "\r" bytes. So, we can launch the brute force algorithm, that will take the last block of cipher-text (10 bytes in unpacked form) and will try to find the plain-text block of variable size and the key such that for each key elements there exists a solution (sum((c**i)*(256**(15-i))) % K = C).
First, we can search through the whole cipher-text for the maximal elements at each position of the block:

Код:
key_maxis = [ max( [ data[ i ] for i in xrange( j, len( data ), 10 ) ] ) for j in xrange( 0, 10 ) ]
Afterwards, this will reduce our brute force to the interval (key_maxis[i],65536).

Obviously, when the key is found, we can decrypt the cipher text using Chinese Remainder Theorem. I used the functions solve_crt(), invmod(), xgcd() from hellman's libnumpy to solve it.

The key parts of solution:
Код:
...................................

data = [ unpack( 'H', data[ i : i + 2 ] )[ 0 ] for i in xrange( 0, len( data ), 2 ) ]
pdf_footers = [ 'startxref\n%s\n%%%%EOF', 'startxref\n%s\r\n%%%%EOF', 'startxref\n%s\r\n%%%%EOF\r\n', 'startxref\n%s\n%%%%EOF\n' ]
c = data[ -10 : ]
key_maxis = [ max( [ data[ i ] for i in xrange( j, len( data ), 10 ) ] ) for j in xrange( 0, 10 ) ]

........................................

def decrypt( str, key ):
    r = ''
    for x in [ str[ 10 * i : 10 * i + 10 ] for i in xrange( (len( str ) + 9) / 10 ) ]:
        d = solve_crt( x, key )
        c = ''
        for i in xrange( 1, 17 ):
            c += chr( d % 256 ** i / 256 ** (i - 1) )
        r += c[ :: -1 ]
    return r

def getsols( n ):
    k = []
    i = 0
    for x in c:
        f = False
        for y in xrange( key_maxis[ i ] + 1, key_maxis[ i ] + 20 ): #It has initially been xrange( key_maxis[ i ] + 1, 65536 ), was optimised later, after observing that the dispersion of keys is small
            if n % y == x:
                k.append( y )
                f = True
                break
        if f is False:
            return None
        i += 1
    return k

def getd( str ):
    d = 0
    for byte in str:
        d *= 256
        d += ord( byte )
    return d

def checkit( len ):
    for x in xrange( 100, 1000 ):
        for foot in pdf_footers:
            foot = foot % x
            foot = foot[ -len : ]
            k = getsols( getd( foot ) )
            if k is not None:
                print 'KEY!!!! %s\nFooter: %r\nCheck olol.pdf' % (k, foot)
                f = open( 'olol.pdf', 'wb' )
                f.write( decrypt( data, k ) )
                quit()

for l in xrange( 1, 17 ):
    checkit( l )
Now, let's see:
Цитата:
$ python solution.py
KEY!!!! [47599, 54979, 18893, 28304, 49643, 35407, 27039, 46051, 45905, 12319]
Footer: '747\n%%EOF\n'
Check olol.pdf
The flag is in olol.pdf: 89d33e0d4aca0d571863d952abf8ce5d

P.S. There was no flag in the first pdf file, but it made the challenge easier, 'cause it was easier to brute force the key with that first corrupted pdf file =)
Random 300

We're given the source code in Rust language. It takes an input string and compares each char of the input with some chars. Straightforward solution is:
Код:
$r=array();
preg_replace( '/h\[(\d+)\] as char == \'(.)\'/iuse', '$r[$1]=\'$2\'', $s );
ksort($r);
echo implode( '', $r ); // 7b5f5c3b813e0df171aa51cc55e7ca4ce0dc6ad8
But the flag is not accepted. Now let's investigate the source code deeper. There's a suspicious line:
Код:
	let a9 = check({h[5] as char == 'c' && h[11] as char == 'e'}.to_str());
	let a10 = check({h[6] as char == '3' && h[9] as char == '1';}.to_str()); //Wut? Semi-colon?
	let a11 = check({h[26] as char == 'e' && h[28] as char == 'c'}.to_str());
So, let's do a bit of debugging. I use liveworkspace.org to compile this code.
The line 'io::println({h[6] as char == '3' && h[9] as char == '1';}.to_str());' implied an output '()'. It's shorter than 5, and it does not depend on input. So, the 2 bytes of our string can be arbitrary.
But the rest of symbols are hex-digits, and the length of input is 40. It can be SHA1.
Let's generate all possible SHA1-hashes which will satisfy the conditions:

Код:
$h = '7b5f5cXb8Y3e0df171aa51cc55e7ca4ce0dc6ad8';
$c = str_split( '0123456789abcdef' );
for( $i = 0; $i < 16; ++$i )
    for( $j = 0; $j < 16; ++$j )
        echo str_replace( array( 'X', 'Y' ), array( $c[ $i ], $c[ $j ] ), $h ) . "\n";
cmd5.ru service helped me to find the plain-text for one of the hashes:
Цитата:
sha1('semicolon')='7b5f5c2b8d3e0df171aa51cc55e7ca4ce0dc6ad8'
It's the flag.