Skip to content

Instantly share code, notes, and snippets.

@icchy

icchy/attack.cpp

Created July 20, 2016 04:36
Show Gist options
  • Save icchy/e07035fd52289ab491dbd71910af1467 to your computer and use it in GitHub Desktop.
Save icchy/e07035fd52289ab491dbd71910af1467 to your computer and use it in GitHub Desktop.
Download ZIP
katagaitai #5 関東med crypt.3 parlor
Raw
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;
}
Raw
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;
// }
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment