Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/0ctf-arsenal.cpp

Last active Oct 10, 2016
Embed
What would you like to do?
0CTF 2016 Quals - Arsenal
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef pair<int, int> PII;
#define MAX_INT (int)0x7fffffff
#define MIN_INT (int)0x80000000
#define MAX_UINT (uint)0xffffffff
#define TTi template<typename T> inline
TTi T SQR(T x) { return x * x; }
#define CONCAT3_NX(x, y, z) x ## y ## z
#define CONCAT3(x, y, z) CONCAT3_NX(x, y, z)
#define VAR(name) CONCAT3(__tmpvar__, name, __LINE__)
#define TYPE(x) __typeof(x)
#define FOR(i, s, n) for (TYPE(n) i=(s), VAR(end)=(n); i < VAR(end); i++)
#define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s); i >= VAR(end); i--)
#define FORN(i, n) FOR(i, 0, n)
#define RFORN(i, n) RFOR(i, 0, n)
#define FOREACH(i, v) for (auto& i: v)
#define SC() scanf("\n")
#define SC1(fmt, a) scanf(fmt, &a)
#define SC2(fmt, a, b) scanf(fmt, &a, &b)
#define SC3(fmt, a, b, c) scanf(fmt, &a, &b, &c)
#define SCi(a) scanf("%d", &a)
#define SCii(a,b) scanf("%d%d", &a, &b)
#define SCiii(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define fLL "%lld"
#define SCl(a) scanf(fLL, &a)
#define SCll(a,b) scanf(fLL fLL, &a, &b)
#define SClll(a,b,c) scanf(fLL fLL fLL, &a, &b, &c)
#define SCs(s, n) {scanf("%s", s); n = strlen(s);}
#define SCc(s) scanf("%c", s)
#define MP make_pair
#define PB push_back
#define WHOLE(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define POPST(stack) (stack).top();(stack).pop();
#define POPQ(queue) (queue).front();(queue).pop();
#define CONTAINS(v, x) (find(WHOLE(v), (x)) != v.end())
#define SORT(v) (sort(WHOLE(v)))
#define LIMIT(x, lim) {if (x > lim) x = lim;}
TTi T MIN(T x, T y) { return (x < y) ? x : y; }
TTi T MAX(T x, T y) { return (x > y) ? x : y; }
TTi T ABS(T x) { return (x > 0) ? x : -x; }
TTi void UPDATE_MIN(T &x, T y) {if (y < x) {x = y;}}
TTi void UPDATE_MAX(T &x, T y) {if (x < y) {x = y;}}
TTi int ARGMAX(T cont) { return max_element(cont.begin(), cont.end()) - cont.begin(); }
TTi int ARGMIN(T cont) { return min_element(cont.begin(), cont.end()) - cont.begin(); }
vector<string> split(const string& s, char c) {
vector<string> v; stringstream ss(s); string x;
while (getline(ss, x, c)) v.emplace_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
stringstream s;
s << "[";
FORN(i, n - 1) s << arr[i] << ",";
s << arr[n - 1] << "]";
return s.str();
}
#ifdef JUDGE_LOCAL
#define EPR(args...) if (DEBUG) {fprintf(stderr, args);}
#define EARR(arr, n) if (DEBUG) {FORN(i, n) fprintf(stderr, "%d, ", arr[i]);}
#define EVEC(arr) if (DEBUG) {FORN(i, arr.size()) fprintf(stderr, "%d, ", arr[i]);}
#define EVARS(args...) if (DEBUG) { __evars_begin(__LINE__); __evars(split(#args, ',').begin(), args);}
inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
inline void __evars(vector<string>::iterator it) {cerr << endl;}
TTi void __evars_out_var(vector<T> val) {
cerr << arrStr(val, val.size());
}
TTi void __evars_out_var(T* val) {
cerr << arrStr(val, 10);
}
TTi void __evars_out_var(T val) {
cerr << val;
}
template<typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
__evars_out_var(a);
cerr << "; ";
__evars(++it, args...);
}
#else
#define EPR(args...) 1
#define EARR(args...) 1
#define EVEC(args...) 1
#define EVARS(args...) 1
#endif
// -----------------------------------------------------------------
// CODE
// -----------------------------------------------------------------
#define DEBUG 1
uint8_t rsbox[256] =
{ 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d };
static uint8_t xtime(uint8_t x)
{
return ((x<<1) ^ (((x>>7) & 1) * 0x1b));
}
#define Multiply(x, y) \
( ((y & 1) * x) ^ \
((y>>1 & 1) * xtime(x)) ^ \
((y>>2 & 1) * xtime(xtime(x))) ^ \
((y>>3 & 1) * xtime(xtime(xtime(x)))) ^ \
((y>>4 & 1) * xtime(xtime(xtime(xtime(x)))))) \
// task
uint8_t blocks[4][63][4] =
{
{ {165, 1, 71, 238} , {230, 53, 57, 172} , {106, 12, 252, 139} , {238, 191, 8, 109} , {62, 222, 219, 17} , {64, 76, 133, 114} , {252, 182, 107, 122} , {198, 39, 253, 201} , {205, 3, 113, 63} , {32, 199, 67, 221} , {25, 0, 98, 137} , {176, 183, 31, 238} , {217, 133, 166, 27} , {93, 98, 198, 56} , {120, 40, 73, 88} , {240, 17, 129, 22} , {36, 12, 153, 171} , {215, 190, 243, 33} , {225, 90, 11, 227} , {75, 29, 73, 248} , {21, 199, 4, 110} , {223, 75, 10, 198} , {196, 150, 123, 101} , {12, 137, 8, 195} , {26, 29, 123, 65} , {144, 187, 9, 43} , {28, 142, 221, 147} , {236, 230, 108, 76} , {33, 177, 49, 182} , {26, 229, 79, 151} , {3, 252, 221, 208} , {189, 221, 161, 20} , {229, 109, 32, 60} , {60, 59, 254, 235} , {211, 30, 2, 27} , {90, 234, 192, 53} , {11, 144, 181, 129} , {84, 117, 4, 10} , {33, 112, 102, 231} , {36, 63, 89, 239} , {254, 128, 99, 73} , {160, 27, 167, 78} , {227, 172, 167, 216} , {208, 52, 2, 180} , {123, 116, 252, 105} , {175, 175, 48, 134} , {2, 121, 20, 238} , {230, 97, 58, 126} , {10, 132, 227, 70} , {191, 165, 49, 110} , {120, 36, 124, 47} , {136, 204, 146, 100} , {40, 69, 177, 61} , {75, 166, 88, 71} , {199, 211, 151, 24} , {155, 102, 230, 214} , {122, 13, 102, 193} , {155, 198, 128, 155} , {140, 91, 58, 120} , {238, 148, 189, 88} , {18, 85, 47, 209} , {148, 69, 69, 107} , {125, 166, 222, 122} }, // x = 0
{ {113, 166, 230, 170} , {241, 60, 121, 22} , {205, 177, 45, 136} , {52, 75, 140, 177} , {29, 22, 109, 118} , {237, 29, 108, 226} , {237, 134, 147, 228} , {15, 29, 61, 181} , {95, 243, 9, 184} , {47, 72, 76, 93} , {141, 200, 15, 1} , {126, 65, 171, 205} , {22, 119, 9, 205} , {139, 25, 213, 54} , {15, 205, 11, 84} , {35, 17, 51, 35} , {242, 237, 46, 85} , {218, 217, 192, 139} , {62, 129, 35, 214} , {183, 191, 51, 97} , {133, 176, 173, 194} , {172, 19, 86, 140} , {59, 101, 53, 108} , {253, 240, 219, 28} , {184, 50, 166, 241} , {63, 192, 252, 54} , {67, 194, 252, 50} , {232, 155, 136, 59} , {214, 119, 145, 145} , {138, 188, 215, 198} , {25, 21, 118, 95} , {92, 32, 52, 114} , {52, 218, 198, 212} , {222, 195, 137, 161} , {87, 131, 218, 80} , {28, 151, 93, 116} , {250, 141, 166, 33} , {48, 171, 190, 177} , {215, 94, 105, 34} , {181, 183, 249, 178} , {144, 163, 48, 64} , {96, 58, 188, 112} , {22, 146, 156, 55} , {100, 232, 48, 10} , {198, 24, 198, 177} , {73, 193, 6, 162} , {21, 120, 160, 254} , {67, 117, 59, 54} , {23, 105, 197, 21} , {128, 96, 20, 39} , {155, 186, 57, 102} , {207, 203, 53, 196} , {148, 169, 8, 230} , {238, 189, 201, 70} , {139, 48, 110, 151} , {62, 39, 236, 200} , {101, 246, 135, 55} , {208, 58, 240, 0} , {98, 60, 101, 19} , {228, 115, 171, 51} , {80, 118, 13, 124} , {149, 248, 182, 165} , {178, 24, 72, 45} }, // x = 1
{ {111, 196, 48, 212} , {104, 178, 191, 149} , {53, 221, 16, 111} , {120, 216, 3, 242} , {120, 60, 166, 146} , {143, 57, 242, 97} , {110, 220, 87, 40} , {170, 200, 157, 101} , {237, 38, 226, 215} , {197, 193, 149, 163} , {57, 207, 163, 0} , {188, 248, 85, 98} , {48, 100, 251, 234} , {21, 62, 238, 197} , {26, 13, 214, 132} , {68, 6, 223, 107} , {62, 8, 68, 174} , {38, 38, 135, 173} , {60, 119, 45, 46} , {212, 247, 185, 57} , {134, 17, 198, 103} , {153, 40, 88, 171} , {136, 29, 195, 144} , {23, 0, 183, 75} , {179, 157, 137, 127} , {61, 228, 56, 77} , {34, 163, 240, 252} , {68, 102, 38, 124} , {203, 248, 71, 237} , {132, 67, 44, 236} , {115, 247, 114, 202} , {255, 73, 112, 167} , {173, 121, 219, 91} , {150, 22, 239, 25} , {42, 126, 75, 0} , {145, 122, 62, 187} , {172, 44, 156, 45} , {0, 155, 19, 68} , {102, 68, 38, 0} , {17, 144, 99, 139} , {215, 59, 35, 206} , {38, 157, 28, 54} , {59, 87, 214, 232} , {43, 41, 0, 16} , {64, 247, 222, 163} , {135, 119, 84, 247} , {112, 247, 209, 130} , {196, 75, 90, 131} , {141, 148, 134, 206} , {240, 116, 50, 119} , {58, 247, 2, 215} , {65, 182, 242, 105} , {82, 156, 119, 214} , {119, 95, 119, 149} , {55, 37, 101, 160} , {9, 126, 108, 224} , {34, 54, 155, 70} , {117, 128, 240, 134} , {16, 117, 30, 206} , {211, 15, 128, 160} , {246, 148, 73, 72} , {162, 135, 131, 26} , {94, 69, 245, 117} }, // x = 2
{ {231, 10, 118, 221} , {105, 31, 200, 41} , {224, 28, 127, 42} , {97, 203, 57, 53} , {226, 65, 135, 37} , {11, 85, 6, 64} , {203, 55, 157, 17} , {218, 241, 201, 23} , {218, 35, 175, 158} , {134, 62, 79, 171} , {68, 143, 222, 122} , {179, 4, 189, 189} , {155, 7, 48, 203} , {16, 46, 67, 219} , {171, 121, 83, 116} , {123, 124, 58, 129} , {183, 100, 187, 145} , {107, 13, 39, 80} , {60, 199, 160, 252} , {94, 176, 218, 211} , {138, 18, 101, 33} , {236, 195, 253, 235} , {108, 34, 189, 18} , {11, 127, 221, 16} , {92, 100, 84, 62} , {118, 219, 59, 50} , {237, 239, 63, 253} , {214, 169, 28, 53} , {115, 190, 2, 235} , {30, 141, 226, 98} , {235, 52, 143, 223} , {57, 230, 58, 71} , {89, 17, 20, 124} , {159, 96, 0, 134} , {57, 192, 132, 25} , {50, 16, 45, 75} , {83, 248, 106, 171} , {62, 119, 47, 178} , {162, 191, 123, 96} , {109, 202, 126, 103} , {1, 104, 238, 248} , {213, 170, 196, 165} , {146, 38, 239, 252} , {171, 202, 156, 245} , {149, 222, 25, 148} , {121, 39, 95, 100} , {135, 212, 136, 198} , {126, 106, 167, 196} , {56, 251, 28, 188} , {150, 92, 5, 94} , {85, 213, 121, 230} , {220, 59, 245, 196} , {190, 186, 37, 131} , {139, 33, 118, 233} , {29, 29, 22, 255} , {138, 215, 4, 179} , {79, 33, 127, 250} , {193, 197, 129, 234} , {10, 226, 134, 243} , {199, 188, 147, 237} , {244, 93, 127, 197} , {95, 254, 13, 128} , {58, 111, 32, 97} } // x = 3
};
uint8_t multable[256][256] = {};
void inv_mix_column(uint8_t *column) {
uint8_t a,b,c,d;
a = column[0];
b = column[1];
c = column[2];
d = column[3];
column[0] = multable[a][0x0e] ^ multable[b][0x0b] ^ multable[c][0x0d] ^ multable[d][0x09];
column[1] = multable[a][0x09] ^ multable[b][0x0e] ^ multable[c][0x0b] ^ multable[d][0x0d];
column[2] = multable[a][0x0d] ^ multable[b][0x09] ^ multable[c][0x0e] ^ multable[d][0x0b];
column[3] = multable[a][0x0b] ^ multable[b][0x0d] ^ multable[c][0x09] ^ multable[d][0x0e];
}
#define N 63
int main(int argc, char *argv[]) {
int curx = atoi(argv[1]);
int start_key = atoi(argv[2]);
EVARS(curx, start_key);
uint8_t curblockset[128][4];
FORN(a, 256) {
FORN(b, 256) {
multable[a][b] = Multiply(a, b);
}}
char values[4][256] = {};
int keys[4];
for(keys[0] = start_key; keys[0] < 256; keys[0]++) {
EVARS(keys[0]);
for(keys[1] = 0; keys[1] < 256; keys[1]++) {
for(keys[2] = 0; keys[2] < 256; keys[2]++) {
for(keys[3] = 0; keys[3] < 256; keys[3]++) {
// xor key, invert sboxes, invert MC
memset(values, 0, 4*256);
int good = 1;
FORN(iblock, N) {
uint8_t *block = curblockset[iblock];
FORN(y, 4) {
block[y] = blocks[curx][iblock][y];
block[y] ^= keys[y];
block[y] = rsbox[block[y]];
}
inv_mix_column(block);
FORN(y, 4) {
if (values[y][block[y]]) {
good = 0;
break;
}
values[y][block[y]] = 1;
}
if (!good) break;
}
// return 0;
if (good) {
printf("Good key: %d, %d, %d, %d <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n", keys[0], keys[1], keys[2], keys[3]);
}
}}}}
return 0;
}
/*
g++ 0ctf-arsenal.cpp -o arsenal -O3 -std=c++11 -DJUDGE_LOCAL && time ./arsenal 0 0
g++ 0ctf-arsenal.cpp -o arsenal -O3 -std=c++11 -DJUDGE_LOCAL && time ./arsenal 1 0
g++ 0ctf-arsenal.cpp -o arsenal -O3 -std=c++11 -DJUDGE_LOCAL && time ./arsenal 2 0
g++ 0ctf-arsenal.cpp -o arsenal -O3 -std=c++11 -DJUDGE_LOCAL && time ./arsenal 3 0
each run takes around 11 minutes
rkey4 = [None] * 16
#Good key: 143 4 231 110 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
rkey4[0:0+16:4] = 143, 4, 231, 110
#Good key: 46 18 215 37 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
rkey4[1:1+16:4] = 46, 18, 215, 37
#Good key: 84 173 237 139 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
rkey4[2:2+16:4] = 84, 173, 237, 139
# Good key: 243 148 36 112 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
rkey4[3:3+16:4] = 243, 148, 36, 112
get master key from rkey4 using z3:
69 65 57 150 81 48 39 93 235 157 218 184 155 0 51 215
decrypt:
0CTF{~~1MP0SS1BLE_1S_N0TH1NG!~~}
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.