icchy/attack.cpp

## attack.cpp
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <vector>
#include <thread>
#include <mutex>
#include "md5.cpp"

using namespace std;

using ll=long long;
using ull=unsigned long long;
using uint=unsigned int;
using uchar=unsigned char;

mutex M;
mutex out_M;
bool found = false;
uint found_A = 0;

size_t get_paddlen(int msglen) {
	uint bitlen = msglen*8;
	size_t paddlen = (448 - bitlen%512)%512;

	// padding
	assert(paddlen % 8 == 0);
	paddlen = (paddlen==0?512:paddlen)/8;
	paddlen += 8;
	return paddlen;
}

void get_padding(int msglen, char *padd) {
	ull bitlen = msglen*8;
	int paddlen = (448 - bitlen%512)%512;
	char size[8];

	// padding
	assert(paddlen % 8 == 0);
	paddlen = (paddlen==0?512:paddlen)/8;
	padd[0] = '\x80';
	for(int i = 0; i < paddlen - 1; i++) padd[i+1] = '\x00';
	memcpy(size, (uchar *)&bitlen, 8);
	memcpy((padd+paddlen), size, 8);
	paddlen += 8;
}

void lengthextension(uint A, uint B, uint C, uint D, int msglen, string appendix, uint &rA, uint &rB, uint &rC, uint &rD) {
	// uint A, B, C, D;
	// memcpy(&A, hash, 4);
	// memcpy(&B, hash+4, 4);
	// memcpy(&C, hash+8, 4);
	// memcpy(&D, hash+12, 4);

	int T[65];
	for(int i = 0; i < 65; i++) T[i] = uint(((ulong)1<<32)*abs(sin(i)))&0xffffffff;

	size_t tmpmsg_size = msglen+get_paddlen(msglen);
	size_t msg_size = tmpmsg_size + appendix.size() + get_paddlen(tmpmsg_size+appendix.size());

	char *amsg = (char *)malloc(msg_size-tmpmsg_size);
	size_t paddlen = get_paddlen(tmpmsg_size+appendix.size());
	char *padd = (char *)malloc(paddlen);
	get_padding(tmpmsg_size+appendix.size(), padd);
	memcpy(amsg, appendix.c_str(), appendix.size());
	memcpy(amsg+appendix.size(), padd, paddlen);

	for(int i = 0; i < msg_size - tmpmsg_size; i+=16*4) {
		int X[16];
		for(int j = 0; j < 16; j++) {
			memcpy(&X[j], amsg+(i+4*j), 4);
		}

		uint AA, BB, CC, DD;
		AA = A, BB = B, CC = C, DD = D;

		for(int n = 0; n < 4; n++) {
			for(int idx = 0; idx < 16; idx+=4) {
				int _k[4], _s[4], _i[4];
				for(int j = 0; j < 4; j++) {
					_k[j] = MD5_table[n][idx+j][0];
					_s[j] = MD5_table[n][idx+j][1];
					_i[j] = MD5_table[n][idx+j][2];
				}

				A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]));
				D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]));
				C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]));
				B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]));
			}
		}

		A += AA, B += BB, C += CC, D += DD;
	}


	rA = A, rB = B, rC = C, rD = D;
}

string ABCD2hash(uint A, uint B, uint C, uint D) {
	uchar res[16];
	memcpy(res, &A, 4);
	memcpy(res+4, &B, 4);
	memcpy(res+8, &C, 4);
	memcpy(res+12, &D, 4);
	return tohex(16, res);
}

void hash2ABCD(string hash, uint &A, uint &B, uint &C, uint D) {
	assert(hash.size() == 32);
}

void searchA(
		uint A1, uint B1, uint C1, uint D1,
		int msglen, string appendix,
		uint A2, uint B2, uint C2, uint D2,
		uint offset, uint count) {

	thread_local uint rA, rB, rC, rD;
	for(thread_local uint i = offset; i < offset+count; ++i) {
		if(((A1>>(6*4))&0xf) ^ ((i>>(6*4))&0xf)) continue;

		M.lock();
		if(found) return;
		M.unlock();

		cerr << ABCD2hash(i, B1, C1, D1) << "\r";

		lengthextension(i, B1, C1, D1, msglen, appendix, rA, rB, rC, rD);

		if (rB == B2 && rC == C2 && rD == D2) {
			M.lock();
			found = true;
			found_A = i;
			M.unlock();
			cout << endl << ABCD2hash(i, B1, C1, D1) << endl;
			return ;
		}
	}
}

int main() {
	string nonce; cin >> nonce;
	uint A1, B1, C1, D1, A2, B2, C2, D2;
	cin >> A1 >> B1 >> C1 >> D1;
	string appendix; cin >> appendix;
	cin >> A2 >> B2 >> C2 >> D2;

	// vector<thread> threads;
	//
	// const uint N = 0x1;
	// uint block = ((uint)1<<31)/N;
	// for(uint i = 0; i < N; ++i) {
	// 	threads.push_back(thread(searchA,
	// 				A1, B1, C1, D1, 16+nonce.size(), appendix,
	// 				A2, B2, C2, D2, block*i, block));
	// }
	// for(thread &t: threads) t.join();

	uint rA, rB, rC, rD;
	for(uint i = 0; i < (1<<31)+1; ++i) {
		if(found) break;
		if(((A1>>(6*4))&0xf) ^ ((i>>(6*4))&0xf)) continue;
		// int maskA = (A1>>(6*4))&0xf;
		// int maski = (i>>(6*4))&0xf;
		// if(maskA != maski) continue;

		// cerr << ABCD2hash(i, B1, C1, D1) << "\r";

		lengthextension(i, B1, C1, D1, 16+nonce.size(), appendix,
				rA, rB, rC, rD);
		if (rB == B2 && rC == C2 && rD == D2) {
			found = true;
			cout << endl << ABCD2hash(i, B1, C1, D1) << endl;
			break;
		}
	}

	// uint A, B, C, D;
	// // lengthextension(0x7a3e70ea, 0x00daefa1, 0x07a5ea64, 0x7eabe8d9, 4, "yo", A, B, C, D);
	// lengthextension(0x855b0432, 0x1a976eae, 0x6edcae2e, 0x4d6f0272, 16+4, "fuga", A, B, C, D);
	// cout << ABCD2hash(A, B, C, D) << endl;
	// cout << A << " " << B << " " << C << " " << D;

	return 0;
}

## md5.cpp
#include <iostream>
#include <cassert>
#include <cstring>
#include <cmath>
#include <sstream>
#include <iomanip>

using namespace std;
using ull=unsigned long long;
using uint=unsigned int;
using uchar=unsigned char;

const int MD5_table[4][16][3] = {
		{
				{ 0, 7, 1}, { 1,12, 2}, { 2,17, 3}, { 3,22, 4},
				{ 4, 7, 5}, { 5,12, 6}, { 6,17, 7}, { 7,22, 8},
				{ 8, 7, 9}, { 9,12,10}, {10,17,11}, {11,22,12},
				{12, 7,13}, {13,12,14}, {14,17,15}, {15,22,16}
		},
		{
				{ 1, 5,17}, { 6, 9,18}, {11,14,19}, { 0,20,20},
				{ 5, 5,21}, {10, 9,22}, {15,14,23}, { 4,20,24},
				{ 9, 5,25}, {14, 9,26}, { 3,14,27}, { 8,20,28},
				{13, 5,29}, { 2, 9,30}, { 7,14,31}, {12,20,32}
		},
		{
				{ 5, 4,33}, { 8,11,34}, {11,16,35}, {14,23,36},
				{ 1, 4,37}, { 4,11,38}, { 7,16,39}, {10,23,40},
				{13, 4,41}, { 0,11,42}, { 3,16,43}, { 6,23,44},
				{ 9, 4,45}, {12,11,46}, {15,16,47}, { 2,23,48}
		},
		{
				{ 0, 6,49}, { 7,10,50}, {14,15,51}, { 5,21,52},
				{12, 6,53}, { 3,10,54}, {10,15,55}, { 1,21,56},
				{ 8, 6,57}, {15,10,58}, { 6,15,59}, {13,21,60},
				{ 4, 6,61}, {11,10,62}, { 2,15,63}, { 9,21,64}
		}
};

uint ROL(uint a, uint b) {
	return (a<<b|a>>(32-b))&0xffffffff;
}

uint F1(uint x, uint y, uint z) {
	return ((x&y)|(~x&z)) & 0xffffffff;
}
uint F2(uint x, uint y, uint z) {
	return ((x&z)|(y&~z)) & 0xffffffff;
}
uint F3(uint x, uint y, uint z) {
	return (x^y^z) & 0xffffffff;
}
uint F4(uint x, uint y, uint z) {
	return (y^(x|~z)) & 0xffffffff;
}

uint (*F[4])(uint, uint, uint) = {F1, F2, F3, F4};

string tohex(int len, uchar *s){
	stringstream ss;
	for(int i = 0; i < len; i++) {
		ss << hex << setfill('0') << setw(2) << (int)s[i];
	}
	return ss.str();
}

void *md5(int msglen, const char *_msg, uchar *res) {
	ull bitlen = msglen*8;
	int paddlen = (448 - bitlen%512)%512;
	char *padd;
	uchar size[8];

	// padding
	assert(paddlen % 8 == 0);
	paddlen = (paddlen==0?512:paddlen)/8;
	padd = (char *)malloc(paddlen+8);
	padd[0] = '\x80';
	for(int i = 1; i < paddlen; i++) padd[i] = '\x00';

	memcpy(size, (uchar *)&bitlen, 8);
	memcpy((padd+paddlen), size, 8);
	paddlen += 8;

	char *msg = (char *)malloc(msglen+paddlen);
	memcpy(msg, _msg, msglen);
	memcpy(msg+msglen, padd, paddlen);
	free(padd);

	// calc
	uint A, B, C, D;
	int T[65];

	A = 0x67452301;
	B = 0xefcdab89;
	C = 0x98badcfe;
	D = 0x10325476;

	for(int i = 0; i < 65; i++) T[i] = uint(((ulong)1<<32)*abs(sin(i)))&0xffffffff;

	for(int i = 0; i < msglen+paddlen; i+=16*4) {
		uint X[16];
		for(int j = 0; j < 16; j++) {
			memcpy(&(X[j]), msg+(i+(4*j)), 4);
		}

		uint AA, BB, CC, DD;
		AA = A, BB = B, CC = C, DD = D;

		for(int n = 0; n < 4; n++) {
			for(int idx = 0; idx < 16; idx+=4) {
				int _k[4], _s[4], _i[4];
				for(int j = 0; j < 4; j++) {
					_k[j] = MD5_table[n][idx+j][0];
					_s[j] = MD5_table[n][idx+j][1];
					_i[j] = MD5_table[n][idx+j][2];
				}

				A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]));
				D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]));
				C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]));
				B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]));
			}
		}

		// A += AA, B += BB, C += CC, D += DD;
		A = (A+AA)&0xffffffff;
		B = (B+BB)&0xffffffff;
		C = (C+CC)&0xffffffff;
		D = (D+DD)&0xffffffff;
	}

	free(msg);

	// res = (uchar *)malloc(16);
	memcpy(res, (uchar *)&A, 4);
	memcpy(res+4, (uchar *)&B, 4);
	memcpy(res+8, (uchar *)&C, 4);
	memcpy(res+12, (uchar *)&D, 4);
}

// int main() {
// 	string s; cin >> s;
// 	uchar *res = (uchar *)malloc(16);
// 	md5(s, res);
// 	cout << tohex(16, res) << endl;
// 	return 0;
// }

## solve.py
from pwn import *
import commands

# context.log_level = 'debug'

HOST = 'katagaitai.orz.hm'
PORT = 4321


def set_odds(n):
    conn.sendline("1")
    conn.recvuntil("): ")
    conn.sendline(str(n))
    conn.recvuntil('\n====================')

def set_bet(n):
    conn.sendline("2")
    conn.recvuntil("): ")
    conn.sendline(str(n))
    conn.recvuntil('\n====================')

def play(nonce):
    conn.sendline("3")
    conn.recvuntil("round!\n")
    conn.send(nonce)
    recv = conn.recvuntil('\n====================')
    conn.recvuntil('\n====================')
    print recv
    if 'Wow' in recv:
        return 0
    else:
        l = filter(lambda x:'generated' in x, recv.split('\n'))[0]
        import re
        res = re.match('.* generated (.*), .*', l).groups()[0]
        return res

def get_secret():
    import re
    conn.sendline('5')
    recv = conn.recvuntil('\n====================')
    l = filter(lambda x:'What' in x, recv.split('\n'))[0]
    res = re.match('.* has been (.*)', l).groups()[0]
    return res

def md5(s):
    from math import sin
    import struct
    # s: bytes

    bitlen = len(s)*8
    paddlen = (448 - bitlen%512)%512
    assert paddlen % 8 == 0
    paddlen = 512 if paddlen == 0 else paddlen
    padd = chr(int("10000000", 2)) + (paddlen/8 - 1)*'\x00'
    padd += struct.pack('<Q', bitlen&0xffffffffffffffff)
    msg = s + padd
    assert len(msg)*8 % 512 == 0

    A = 0x67452301
    B = 0xefcdab89
    C = 0x98badcfe
    D = 0x10325476
    T = [int((1<<32) * abs(sin(i)))&0xffffffff for i in xrange(65)]

    MD5_table = [
        [
            [ 0, 7, 1], [ 1,12, 2], [ 2,17, 3], [ 3,22, 4],
            [ 4, 7, 5], [ 5,12, 6], [ 6,17, 7], [ 7,22, 8],
            [ 8, 7, 9], [ 9,12,10], [10,17,11], [11,22,12],
            [12, 7,13], [13,12,14], [14,17,15], [15,22,16]
        ],
        [
            [ 1, 5,17], [ 6, 9,18], [11,14,19], [ 0,20,20],
            [ 5, 5,21], [10, 9,22], [15,14,23], [ 4,20,24],
            [ 9, 5,25], [14, 9,26], [ 3,14,27], [ 8,20,28],
            [13, 5,29], [ 2, 9,30], [ 7,14,31], [12,20,32]
        ],
        [
            [ 5, 4,33], [ 8,11,34], [11,16,35], [14,23,36],
            [ 1, 4,37], [ 4,11,38], [ 7,16,39], [10,23,40],
            [13, 4,41], [ 0,11,42], [ 3,16,43], [ 6,23,44],
            [ 9, 4,45], [12,11,46], [15,16,47], [ 2,23,48]
        ],
        [
            [ 0, 6,49], [ 7,10,50], [14,15,51], [ 5,21,52],
            [12, 6,53], [ 3,10,54], [10,15,55], [ 1,21,56],
            [ 8, 6,57], [15,10,58], [ 6,15,59], [13,21,60],
            [ 4, 6,61], [11,10,62], [ 2,15,63], [ 9,21,64]
        ]
    ]

    F = [
        lambda x,y,z: ((x&y)|(~x&z)) & 0xffffffff,
        lambda x,y,z: ((x&z)|(y&~z)) & 0xffffffff,
        lambda x,y,z: (x^y^z)&0xffffffff,
        lambda x,y,z: (y^(x|~z))&0xffffffff
    ]
    ROL = lambda x,y: (x<<y|x>>(32-y))&0xffffffff

    for i in xrange(0, len(msg), 16*4):
        X = struct.unpack('<16I', msg[i:i+16*4])

        AA = A
        BB = B
        CC = C
        DD = D

        for n in xrange(4):
            for idx in xrange(0, len(MD5_table[n]), 4):
                _k, _s, _i = zip(*MD5_table[n][idx:idx+4])
                A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]))
                D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]))
                C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]))
                B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]))

        A = (A + AA)&0xffffffff
        B = (B + BB)&0xffffffff
        C = (C + CC)&0xffffffff
        D = (D + DD)&0xffffffff


    return ''.join(map(lambda x: hex(x)[2:].zfill(8).decode('hex')[::-1].encode('hex'), [A, B, C, D]))

def padding(s):
    bitlen = len(s)*8
    paddlen = (448 - bitlen%512)%512
    assert paddlen % 8 == 0
    paddlen = 512 if paddlen == 0 else paddlen
    padd = chr(int("10000000", 2)) + (paddlen/8 - 1)*'\x00'
    padd += struct.pack('<Q', bitlen&0xffffffffffffffff)
    msg = s + padd
    assert len(msg)*8 % 512 == 0
    return padd

def lengthextension(myhash, msglen, appendix):
    from math import sin
    A = int(myhash[:8].decode('hex')[::-1].encode('hex'), 16)
    B = int(myhash[8:16].decode('hex')[::-1].encode('hex'), 16)
    C = int(myhash[16:24].decode('hex')[::-1].encode('hex'), 16)
    D = int(myhash[24:].decode('hex')[::-1].encode('hex'), 16)

    T = [int((1<<32) * abs(sin(i)))&0xffffffff for i in xrange(65)]

    MD5_table = [
        [
            [ 0, 7, 1], [ 1,12, 2], [ 2,17, 3], [ 3,22, 4],
            [ 4, 7, 5], [ 5,12, 6], [ 6,17, 7], [ 7,22, 8],
            [ 8, 7, 9], [ 9,12,10], [10,17,11], [11,22,12],
            [12, 7,13], [13,12,14], [14,17,15], [15,22,16]
        ],
        [
            [ 1, 5,17], [ 6, 9,18], [11,14,19], [ 0,20,20],
            [ 5, 5,21], [10, 9,22], [15,14,23], [ 4,20,24],
            [ 9, 5,25], [14, 9,26], [ 3,14,27], [ 8,20,28],
            [13, 5,29], [ 2, 9,30], [ 7,14,31], [12,20,32]
        ],
        [
            [ 5, 4,33], [ 8,11,34], [11,16,35], [14,23,36],
            [ 1, 4,37], [ 4,11,38], [ 7,16,39], [10,23,40],
            [13, 4,41], [ 0,11,42], [ 3,16,43], [ 6,23,44],
            [ 9, 4,45], [12,11,46], [15,16,47], [ 2,23,48]
        ],
        [
            [ 0, 6,49], [ 7,10,50], [14,15,51], [ 5,21,52],
            [12, 6,53], [ 3,10,54], [10,15,55], [ 1,21,56],
            [ 8, 6,57], [15,10,58], [ 6,15,59], [13,21,60],
            [ 4, 6,61], [11,10,62], [ 2,15,63], [ 9,21,64]
        ]
    ]

    F = [
        lambda x,y,z: ((x&y)|(~x&z)) & 0xffffffff,
        lambda x,y,z: ((x&z)|(y&~z)) & 0xffffffff,
        lambda x,y,z: (x^y^z)&0xffffffff,
        lambda x,y,z: (y^(x|~z))&0xffffffff
    ]
    ROL = lambda x,y: (x<<y|x>>(32-y))&0xffffffff

    extended = msglen*'A'
    extended += padding(extended)
    pmsglen = len(extended)
    extended += appendix
    extended += padding(extended)
    extended = extended[pmsglen:]
    for i in xrange(0, len(extended), 16*4):
        X = struct.unpack('<16I', extended[i:i+16*4])

        AA = A
        BB = B
        CC = C
        DD = D

        for n in xrange(4):
            for idx in xrange(0, len(MD5_table[n]), 4):
                _k, _s, _i = zip(*MD5_table[n][idx:idx+4])
                A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]))
                D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]))
                C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]))
                B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]))

        A = (A + AA)&0xffffffff
        B = (B + BB)&0xffffffff
        C = (C + CC)&0xffffffff
        D = (D + DD)&0xffffffff
    return ''.join(map(lambda x: hex(x)[2:].zfill(8).decode('hex')[::-1].encode('hex'), [A, B, C, D]))


conn = remote(HOST, PORT)
set_odds(100)
set_bet(0)
nonce = 'hoge'
tail1 = hex(int(play(nonce)))[2:].strip('L')

appendix = 'fuga'
set_odds(100)
set_bet(0)

msg = 'A'*16+nonce
msg += padding(msg)
msg += appendix
nonce2 = msg[16:]
tail2 = hex(int(play(nonce2)))[2:].strip('L')

# secret = get_secret()

ABCD1 = " ".join(map(lambda x: str(int(x, 16)), [tail1.zfill(32)[i:i+8].decode('hex')[::-1].encode('hex') for i in range(0, 32, 8)]))
ABCD2 = " ".join(map(lambda x: str(int(x, 16)), [tail2.zfill(32)[i:i+8].decode('hex')[::-1].encode('hex') for i in range(0, 32, 8)]))

print 'tail1', tail1
print 'tail2', tail2
# print 'secret', secret
# print 'ans1', md5(secret.decode('hex')+nonce)
# print 'ans2', md5(secret.decode('hex')+nonce2)

cmd = 'echo {nonce} {ABCD1} {appendix} {ABCD2} | ./attack'.format(**locals())
res = commands.getoutput(cmd).strip()

print 'hit', res

padd = 'A'*16+nonce
padd += padding(padd)
padd = padd[16:]

for i in xrange(0x100000000):
    import struct
    appendix = struct.pack('<I', i)
    cur = lengthextension(res, 16+len('hoge'), appendix)
    for _i in range(16, 2, -1):
        if cur.endswith('0'*_i):
            print _i, cur
            set_odds(_i*4)
            set_bet(1000)
            assert play(padd+appendix) == 0
            break
	#include <iostream>
	#include <sstream>
	#include <iomanip>
	#include <algorithm>
	#include <cstring>
	#include <cassert>
	#include <vector>
	#include <thread>
	#include <mutex>
	#include "md5.cpp"

	using namespace std;

	using ll=long long;
	using ull=unsigned long long;
	using uint=unsigned int;
	using uchar=unsigned char;

	mutex M;
	mutex out_M;
	bool found = false;
	uint found_A = 0;

	size_t get_paddlen(int msglen) {
	uint bitlen = msglen*8;
	size_t paddlen = (448 - bitlen%512)%512;

	// padding
	assert(paddlen % 8 == 0);
	paddlen = (paddlen==0?512:paddlen)/8;
	paddlen += 8;
	return paddlen;
	}

	void get_padding(int msglen, char *padd) {
	ull bitlen = msglen*8;
	int paddlen = (448 - bitlen%512)%512;
	char size[8];

	// padding
	assert(paddlen % 8 == 0);
	paddlen = (paddlen==0?512:paddlen)/8;
	padd[0] = '\x80';
	for(int i = 0; i < paddlen - 1; i++) padd[i+1] = '\x00';
	memcpy(size, (uchar *)&bitlen, 8);
	memcpy((padd+paddlen), size, 8);
	paddlen += 8;
	}

	void lengthextension(uint A, uint B, uint C, uint D, int msglen, string appendix, uint &rA, uint &rB, uint &rC, uint &rD) {
	// uint A, B, C, D;
	// memcpy(&A, hash, 4);
	// memcpy(&B, hash+4, 4);
	// memcpy(&C, hash+8, 4);
	// memcpy(&D, hash+12, 4);

	int T[65];
	for(int i = 0; i < 65; i++) T[i] = uint(((ulong)1<<32)*abs(sin(i)))&0xffffffff;

	size_t tmpmsg_size = msglen+get_paddlen(msglen);
	size_t msg_size = tmpmsg_size + appendix.size() + get_paddlen(tmpmsg_size+appendix.size());

	char amsg = (char )malloc(msg_size-tmpmsg_size);
	size_t paddlen = get_paddlen(tmpmsg_size+appendix.size());
	char padd = (char )malloc(paddlen);
	get_padding(tmpmsg_size+appendix.size(), padd);
	memcpy(amsg, appendix.c_str(), appendix.size());
	memcpy(amsg+appendix.size(), padd, paddlen);

	for(int i = 0; i < msg_size - tmpmsg_size; i+=16*4) {
	int X[16];
	for(int j = 0; j < 16; j++) {
	memcpy(&X[j], amsg+(i+4*j), 4);
	}

	uint AA, BB, CC, DD;
	AA = A, BB = B, CC = C, DD = D;

	for(int n = 0; n < 4; n++) {
	for(int idx = 0; idx < 16; idx+=4) {
	int _k[4], _s[4], _i[4];
	for(int j = 0; j < 4; j++) {
	_k[j] = MD5_table[n][idx+j][0];
	_s[j] = MD5_table[n][idx+j][1];
	_i[j] = MD5_table[n][idx+j][2];
	}

	A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]));
	D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]));
	C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]));
	B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]));
	}
	}

	A += AA, B += BB, C += CC, D += DD;
	}


	rA = A, rB = B, rC = C, rD = D;
	}

	string ABCD2hash(uint A, uint B, uint C, uint D) {
	uchar res[16];
	memcpy(res, &A, 4);
	memcpy(res+4, &B, 4);
	memcpy(res+8, &C, 4);
	memcpy(res+12, &D, 4);
	return tohex(16, res);
	}

	void hash2ABCD(string hash, uint &A, uint &B, uint &C, uint D) {
	assert(hash.size() == 32);
	}

	void searchA(
	uint A1, uint B1, uint C1, uint D1,
	int msglen, string appendix,
	uint A2, uint B2, uint C2, uint D2,
	uint offset, uint count) {

	thread_local uint rA, rB, rC, rD;
	for(thread_local uint i = offset; i < offset+count; ++i) {
	if(((A1>>(64))&0xf) ^ ((i>>(64))&0xf)) continue;

	M.lock();
	if(found) return;
	M.unlock();

	cerr << ABCD2hash(i, B1, C1, D1) << "\r";

	lengthextension(i, B1, C1, D1, msglen, appendix, rA, rB, rC, rD);

	if (rB == B2 && rC == C2 && rD == D2) {
	M.lock();
	found = true;
	found_A = i;
	M.unlock();
	cout << endl << ABCD2hash(i, B1, C1, D1) << endl;
	return ;
	}
	}
	}

	int main() {
	string nonce; cin >> nonce;
	uint A1, B1, C1, D1, A2, B2, C2, D2;
	cin >> A1 >> B1 >> C1 >> D1;
	string appendix; cin >> appendix;
	cin >> A2 >> B2 >> C2 >> D2;

	// vector<thread> threads;
	//
	// const uint N = 0x1;
	// uint block = ((uint)1<<31)/N;
	// for(uint i = 0; i < N; ++i) {
	// threads.push_back(thread(searchA,
	// A1, B1, C1, D1, 16+nonce.size(), appendix,
	// A2, B2, C2, D2, block*i, block));
	// }
	// for(thread &t: threads) t.join();

	uint rA, rB, rC, rD;
	for(uint i = 0; i < (1<<31)+1; ++i) {
	if(found) break;
	if(((A1>>(64))&0xf) ^ ((i>>(64))&0xf)) continue;
	// int maskA = (A1>>(6*4))&0xf;
	// int maski = (i>>(6*4))&0xf;
	// if(maskA != maski) continue;

	// cerr << ABCD2hash(i, B1, C1, D1) << "\r";

	lengthextension(i, B1, C1, D1, 16+nonce.size(), appendix,
	rA, rB, rC, rD);
	if (rB == B2 && rC == C2 && rD == D2) {
	found = true;
	cout << endl << ABCD2hash(i, B1, C1, D1) << endl;
	break;
	}
	}

	// uint A, B, C, D;
	// // lengthextension(0x7a3e70ea, 0x00daefa1, 0x07a5ea64, 0x7eabe8d9, 4, "yo", A, B, C, D);
	// lengthextension(0x855b0432, 0x1a976eae, 0x6edcae2e, 0x4d6f0272, 16+4, "fuga", A, B, C, D);
	// cout << ABCD2hash(A, B, C, D) << endl;
	// cout << A << " " << B << " " << C << " " << D;

	return 0;
	}
	from pwn import *
	import commands

	# context.log_level = 'debug'

	HOST = 'katagaitai.orz.hm'
	PORT = 4321


	def set_odds(n):
	conn.sendline("1")
	conn.recvuntil("): ")
	conn.sendline(str(n))
	conn.recvuntil('\n====================')

	def set_bet(n):
	conn.sendline("2")
	conn.recvuntil("): ")
	conn.sendline(str(n))
	conn.recvuntil('\n====================')

	def play(nonce):
	conn.sendline("3")
	conn.recvuntil("round!\n")
	conn.send(nonce)
	recv = conn.recvuntil('\n====================')
	conn.recvuntil('\n====================')
	print recv
	if 'Wow' in recv:
	return 0
	else:
	l = filter(lambda x:'generated' in x, recv.split('\n'))[0]
	import re
	res = re.match('.* generated (.), .', l).groups()[0]
	return res

	def get_secret():
	import re
	conn.sendline('5')
	recv = conn.recvuntil('\n====================')
	l = filter(lambda x:'What' in x, recv.split('\n'))[0]
	res = re.match('.* has been (.*)', l).groups()[0]
	return res

	def md5(s):
	from math import sin
	import struct
	# s: bytes

	bitlen = len(s)*8
	paddlen = (448 - bitlen%512)%512
	assert paddlen % 8 == 0
	paddlen = 512 if paddlen == 0 else paddlen
	padd = chr(int("10000000", 2)) + (paddlen/8 - 1)*'\x00'
	padd += struct.pack('<Q', bitlen&0xffffffffffffffff)
	msg = s + padd
	assert len(msg)*8 % 512 == 0

	A = 0x67452301
	B = 0xefcdab89
	C = 0x98badcfe
	D = 0x10325476
	T = [int((1<<32) * abs(sin(i)))&0xffffffff for i in xrange(65)]

	MD5_table = [
	[
	[ 0, 7, 1], [ 1,12, 2], [ 2,17, 3], [ 3,22, 4],
	[ 4, 7, 5], [ 5,12, 6], [ 6,17, 7], [ 7,22, 8],
	[ 8, 7, 9], [ 9,12,10], [10,17,11], [11,22,12],
	[12, 7,13], [13,12,14], [14,17,15], [15,22,16]
	],
	[
	[ 1, 5,17], [ 6, 9,18], [11,14,19], [ 0,20,20],
	[ 5, 5,21], [10, 9,22], [15,14,23], [ 4,20,24],
	[ 9, 5,25], [14, 9,26], [ 3,14,27], [ 8,20,28],
	[13, 5,29], [ 2, 9,30], [ 7,14,31], [12,20,32]
	],
	[
	[ 5, 4,33], [ 8,11,34], [11,16,35], [14,23,36],
	[ 1, 4,37], [ 4,11,38], [ 7,16,39], [10,23,40],
	[13, 4,41], [ 0,11,42], [ 3,16,43], [ 6,23,44],
	[ 9, 4,45], [12,11,46], [15,16,47], [ 2,23,48]
	],
	[
	[ 0, 6,49], [ 7,10,50], [14,15,51], [ 5,21,52],
	[12, 6,53], [ 3,10,54], [10,15,55], [ 1,21,56],
	[ 8, 6,57], [15,10,58], [ 6,15,59], [13,21,60],
	[ 4, 6,61], [11,10,62], [ 2,15,63], [ 9,21,64]
	]
	]

	F = [
	lambda x,y,z: ((x&y)\|(~x&z)) & 0xffffffff,
	lambda x,y,z: ((x&z)\|(y&~z)) & 0xffffffff,
	lambda x,y,z: (x^y^z)&0xffffffff,
	lambda x,y,z: (y^(x\|~z))&0xffffffff
	]
	ROL = lambda x,y: (x<<y\|x>>(32-y))&0xffffffff

	for i in xrange(0, len(msg), 16*4):
	X = struct.unpack('<16I', msg[i:i+16*4])

	AA = A
	BB = B
	CC = C
	DD = D

	for n in xrange(4):
	for idx in xrange(0, len(MD5_table[n]), 4):
	_k, _s, _i = zip(*MD5_table[n][idx:idx+4])
	A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]))
	D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]))
	C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]))
	B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]))

	A = (A + AA)&0xffffffff
	B = (B + BB)&0xffffffff
	C = (C + CC)&0xffffffff
	D = (D + DD)&0xffffffff


	return ''.join(map(lambda x: hex(x)[2:].zfill(8).decode('hex')[::-1].encode('hex'), [A, B, C, D]))

	def padding(s):
	bitlen = len(s)*8
	paddlen = (448 - bitlen%512)%512
	assert paddlen % 8 == 0
	paddlen = 512 if paddlen == 0 else paddlen
	padd = chr(int("10000000", 2)) + (paddlen/8 - 1)*'\x00'
	padd += struct.pack('<Q', bitlen&0xffffffffffffffff)
	msg = s + padd
	assert len(msg)*8 % 512 == 0
	return padd

	def lengthextension(myhash, msglen, appendix):
	from math import sin
	A = int(myhash[:8].decode('hex')[::-1].encode('hex'), 16)
	B = int(myhash[8:16].decode('hex')[::-1].encode('hex'), 16)
	C = int(myhash[16:24].decode('hex')[::-1].encode('hex'), 16)
	D = int(myhash[24:].decode('hex')[::-1].encode('hex'), 16)

	T = [int((1<<32) * abs(sin(i)))&0xffffffff for i in xrange(65)]

	MD5_table = [
	[
	[ 0, 7, 1], [ 1,12, 2], [ 2,17, 3], [ 3,22, 4],
	[ 4, 7, 5], [ 5,12, 6], [ 6,17, 7], [ 7,22, 8],
	[ 8, 7, 9], [ 9,12,10], [10,17,11], [11,22,12],
	[12, 7,13], [13,12,14], [14,17,15], [15,22,16]
	],
	[
	[ 1, 5,17], [ 6, 9,18], [11,14,19], [ 0,20,20],
	[ 5, 5,21], [10, 9,22], [15,14,23], [ 4,20,24],
	[ 9, 5,25], [14, 9,26], [ 3,14,27], [ 8,20,28],
	[13, 5,29], [ 2, 9,30], [ 7,14,31], [12,20,32]
	],
	[
	[ 5, 4,33], [ 8,11,34], [11,16,35], [14,23,36],
	[ 1, 4,37], [ 4,11,38], [ 7,16,39], [10,23,40],
	[13, 4,41], [ 0,11,42], [ 3,16,43], [ 6,23,44],
	[ 9, 4,45], [12,11,46], [15,16,47], [ 2,23,48]
	],
	[
	[ 0, 6,49], [ 7,10,50], [14,15,51], [ 5,21,52],
	[12, 6,53], [ 3,10,54], [10,15,55], [ 1,21,56],
	[ 8, 6,57], [15,10,58], [ 6,15,59], [13,21,60],
	[ 4, 6,61], [11,10,62], [ 2,15,63], [ 9,21,64]
	]
	]

	F = [
	lambda x,y,z: ((x&y)\|(~x&z)) & 0xffffffff,
	lambda x,y,z: ((x&z)\|(y&~z)) & 0xffffffff,
	lambda x,y,z: (x^y^z)&0xffffffff,
	lambda x,y,z: (y^(x\|~z))&0xffffffff
	]
	ROL = lambda x,y: (x<<y\|x>>(32-y))&0xffffffff

	extended = msglen*'A'
	extended += padding(extended)
	pmsglen = len(extended)
	extended += appendix
	extended += padding(extended)
	extended = extended[pmsglen:]
	for i in xrange(0, len(extended), 16*4):
	X = struct.unpack('<16I', extended[i:i+16*4])

	AA = A
	BB = B
	CC = C
	DD = D

	for n in xrange(4):
	for idx in xrange(0, len(MD5_table[n]), 4):
	_k, _s, _i = zip(*MD5_table[n][idx:idx+4])
	A = (B + ROL((A + F[n](B, C, D) + X[_k[0]] + T[_i[0]])&0xffffffff, _s[0]))
	D = (A + ROL((D + F[n](A, B, C) + X[_k[1]] + T[_i[1]])&0xffffffff, _s[1]))
	C = (D + ROL((C + F[n](D, A, B) + X[_k[2]] + T[_i[2]])&0xffffffff, _s[2]))
	B = (C + ROL((B + F[n](C, D, A) + X[_k[3]] + T[_i[3]])&0xffffffff, _s[3]))

	A = (A + AA)&0xffffffff
	B = (B + BB)&0xffffffff
	C = (C + CC)&0xffffffff
	D = (D + DD)&0xffffffff
	return ''.join(map(lambda x: hex(x)[2:].zfill(8).decode('hex')[::-1].encode('hex'), [A, B, C, D]))


	conn = remote(HOST, PORT)
	set_odds(100)
	set_bet(0)
	nonce = 'hoge'
	tail1 = hex(int(play(nonce)))[2:].strip('L')

	appendix = 'fuga'
	set_odds(100)
	set_bet(0)

	msg = 'A'*16+nonce
	msg += padding(msg)
	msg += appendix
	nonce2 = msg[16:]
	tail2 = hex(int(play(nonce2)))[2:].strip('L')

	# secret = get_secret()

	ABCD1 = " ".join(map(lambda x: str(int(x, 16)), [tail1.zfill(32)[i:i+8].decode('hex')[::-1].encode('hex') for i in range(0, 32, 8)]))
	ABCD2 = " ".join(map(lambda x: str(int(x, 16)), [tail2.zfill(32)[i:i+8].decode('hex')[::-1].encode('hex') for i in range(0, 32, 8)]))

	print 'tail1', tail1
	print 'tail2', tail2
	# print 'secret', secret
	# print 'ans1', md5(secret.decode('hex')+nonce)
	# print 'ans2', md5(secret.decode('hex')+nonce2)

	cmd = 'echo {nonce} {ABCD1} {appendix} {ABCD2} \| ./attack'.format(**locals())
	res = commands.getoutput(cmd).strip()

	print 'hit', res

	padd = 'A'*16+nonce
	padd += padding(padd)
	padd = padd[16:]

	for i in xrange(0x100000000):
	import struct
	appendix = struct.pack('<I', i)
	cur = lengthextension(res, 16+len('hoge'), appendix)
	for _i in range(16, 2, -1):
	if cur.endswith('0'*_i):
	print _i, cur
	set_odds(_i*4)
	set_bet(1000)
	assert play(padd+appendix) == 0
	break