<?php
include('config.php');
session_start();
if($_SESSION['time'] && time() - $_SESSION['time'] > 60) {
session_destroy();
die('timeout');
} else {
$_SESSION['time'] = time();
}
echo rand();
if (isset($_GET['go'])) {
$_SESSION['rand'] = array();
$i = 5;
$d = '';
while($i--){
$r = (string)rand();
$_SESSION['rand'][] = $r;
$d .= $r;
}
echo md5($d);
} else if (isset($_GET['check'])) {
if ($_GET['check'] === $_SESSION['rand']) {
echo $flag;
} else {
echo 'die';
session_destroy();
}
} else {
show_source(__FILE__);
}
?>
One more PRNG problem. PHP normally use glibc’s random function as its underlying implementation, which is x[n]=(x[n-3]+x[n-31])>>1. My solution was generating all 2^32 possible cases and confirm with the md5 value. First part of the solution was the cache generator:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
namespace vhrand {
static long randtbl[DEG_3 + 1] = {
TYPE_3,
0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05,
0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454,
0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471,
0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
0xf3bec5da
};
static long *fptr = &randtbl[SEP_3 + 1];
static long *rptr = &randtbl[1];
static long *state = &randtbl[1];
static long rand_type = TYPE_3;
static long rand_deg = DEG_3;
static long rand_sep = SEP_3;
static long *end_ptr = &randtbl[DEG_3 + 1];
long random();
//
// Compute x = (7^5 * x) mod (2^31 - 1)
// wihout overflowing 31 bits:
// (2^31 - 1) = 127773 * (7^5) + 2836
// From "Random number generators: good ones are hard to find",
// Park and Miller, Communications of the ACM, vol. 31, no. 10,
// October 1988, p. 1195.
//
__inline long good_rand(long x) {
long hi, lo;
// Can't be initialized with 0, so use another value.
if (x == 0) x = 123459876;
hi = x / 127773;
lo = x % 127773;
x = 16807 * lo - 2836 * hi;
if (x < 0) x += 0x7fffffff;
return x;
}
void srandom(unsigned long x) {
long i, lim;
state[0] = x;
if (rand_type == TYPE_0) {
lim = NSHUFF;
} else {
for (i = 1; i < rand_deg; i++) state[i] = good_rand(state[i - 1]);
fptr = &state[rand_sep];
rptr = &state[0];
lim = 10 * rand_deg;
}
for (i = 0; i < lim; i++) random();
}
long random() {
long i;
long *f, *r;
if (rand_type == TYPE_0) {
i = state[0];
state[0] = i = (good_rand(i)) & 0x7fffffff;
} else {
f = fptr; r = rptr;
*f += *r;
i = (*f >> 1) & 0x7fffffff; // Chucking least random bit
if (++f >= end_ptr) {
f = state;
++r;
} else if (++r >= end_ptr) {
r = state;
}
fptr = f; rptr = r;
}
return i;
}
};
int ctop[2148];
int cnext[10000000];
long pendingValues[10000000][2];
long pendingCount = 0;
void processPending(){
printf("Flushing %ld\n",pendingCount);
char filename[100];
for(int i=0;i<=2147;i++){
FILE* h = NULL;
for(int j=ctop[i];j>=0;j=cnext[j]){
if(pendingValues[j][1]/1000000==i){
sprintf(filename, "caches/%d.txt", i);
if(h==NULL){
h = fopen(filename, "a");
}
fprintf(h, "%ld %ld\n", pendingValues[j][1], pendingValues[j][0]);
}else{
printf("ERRROR!!!!!");
exit(-1);
}
}
if(h!=NULL) fclose(h);
}
memset(ctop, -1, sizeof(ctop));
pendingCount = 0;
}
int main(int argc, char *argv[]) {
//max=2147483647
pendingCount = 0;
memset(ctop, -1, sizeof(ctop));
for(long i=0;i<2147483647l;i++){
if(i%1000000==0)
fprintf(stderr,"Generated up to %ld\n",i);
vhrand::srandom(i);
long val = vhrand::random();
long bucket = val/1000000;
pendingValues[pendingCount][0]=i;
pendingValues[pendingCount][1]=val;
cnext[pendingCount]=ctop[bucket];
ctop[bucket]=pendingCount;
pendingCount++;
if(pendingCount==10000000) processPending();
}
processPending();
return 0;
}
While the cache was generating, i ran a script to solve the problem and just left it running tothether with above C++ script:
<?php
for(;;){
$s=N("http://202.120.7.202:8888/?go=1");
preg_match('@Set-Cookie: (.*?); path=\/@', $s, $m);
$cookie = $m[1];
$param = end((explode("\n", $s)));
$md5 = substr($param, -32);
$param = intval(substr($param, 0, -32));
$bucket = floor($param/1000000);
echo "Param: $param ($bucket) | MD5 : $md5\n";
if(file_exists($fn = "caches/$bucket.txt")){
$h = fopen($fn, "r");
while(!feof($h)){
fscanf($h, "%d%d", $n, $seed);
if($n==$param){
srand($seed);
$rr = rand();
echo "Trying seed=$seed : $rr\n";
$url = "http://202.120.7.202:8888/?_=1";
$d = "";
$i=5;
while($i--){
$r = (string)rand();
$url.="&check[]=$r";
$d.=$r;
}
if($md5 == md5($d)){
echo "Finally... ".$url."\n";
echo N($url,$cookie);
exit;
} else {
echo "MD5 must be $md5 -- ".md5($d)."\n";
}
}
}
}
N("http://202.120.7.202:8888/?check=1");
}
function N($url,$cookie=""){
$ch = curl_init();
curl_setopt_array($ch, [
CURLOPT_URL => $url,
CURLOPT_SSL_VERIFYPEER => 0,
CURLOPT_SSL_VERIFYHOST => 0,
CURLOPT_RETURNTRANSFER => 1,
CURLOPT_POST => 0,
CURLOPT_HEADER => 1,
CURLOPT_COOKIE => $cookie,
]);
$s = curl_exec($ch);
curl_close($ch);
return $s;
}
?>
The flag printed out after the cache had generated about 500mils items. After sometime i noticed how stupid i was when forgot the Keep-Alive header, yes it has been a long time…
$ cat public.pem -----BEGIN PUBLIC KEY----- MEEwDQYJKoZIhvcNAQEBBQADMAAwLQIoAsqpwJ3BBh5Qflt/Od3jRV/P4Seixpti HIP9nT0+qjqsQhR81xiMUwIBAw== -----END PUBLIC KEY----- $ hexdump -C flag.enc 00000000 00 4c 41 62 a0 7a 01 11 b8 34 4c 68 b1 18 bd 05 |.LAb.z...4Lh....| 00000010 4a cb c3 8c 31 31 b6 a8 99 9c 91 d1 b3 e2 d8 2d |J...11.........-| 00000020 c7 c3 a1 e1 03 4f d6 04 |.....O..| 00000028
The pem file give us n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067, e=3. Msieve reported 3 factors of n after about 2 hours:
a = 26440615366395242196516853423447 b = 27038194053540661979045656526063 c = 32581479300404876772405716877547
It was not that easy, (a-1)*(b-1)*(c-1) is divisible by e, so d does not exists in this system. In this problem we can calculate d’ which’s
cipher^d' = (plain^e)^d' = plain^27 (mod n)
Then find all 27th-root of n and check one by one. Final solution’s below:
from sage.all import *
n = 23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
a = 26440615366395242196516853423447
b = 27038194053540661979045656526063
c = 32581479300404876772405716877547
e = 3
phi = (a-1)*(b-1)*(c-1)
ne = 0
while phi % (e**(ne+1)) == 0:
ne += 1
print "ne = ", ne
d = long(1/Mod(e,phi/e**ne))
print "d = ", d
with open("flag.enc","rb") as f:
cipher = f.read(100)
cipher = int(cipher.encode("hex"),16)
plain_pow_ene = pow(cipher,d*e**ne,n)
print plain_pow_ene
cases = []
for p in [a,b,c]:
cases.append(Mod(plain_pow_ene%p,p).nth_root(e**ne,all=True))
print "Start solving"
for ar in map(long,Mod(plain_pow_ene%a,a).nth_root(e**ne,all=True)):
for br in map(long,Mod(plain_pow_ene%b,b).nth_root(e**ne,all=True)):
for cr in map(long,Mod(plain_pow_ene%c,c).nth_root(e**ne,all=True)):
x = crt([ar,br,cr],[a,b,c])
print hex(x)
s = hex(x)
if len(s)%2==1:
s = "0" + s
print s.decode("hex")
The flag is:
0ctf{HahA!Thi5_1s_n0T_rSa~}
Yes yes, i know, it was not RSA, of cause…
People’s Square (A.K.A. shenmhin guangshan in Shanghai Dialect) is a large public square in the Huangpu District of Shanghai, China.
We know Talent Yang is the king of People's Square. Now he provides you a strange guessing game, and he also demonstrates his talent by giving you the result of how he tackles this task. Can you show your talent to decrypt the secret?
After a while reading the binaries with IDA, it’s confirmed that this’s a problem about recovering a cipher text with known plain-cipher pairs on reduced version of AES (4 rounds). The given binary’s decompiled code looks like below:
int __fastcall load_flag(void *a1)
{
FILE *v1; // ST10_8@1
v1 = fopen("flag.txt", "r");
fread(a1, 1uLL, 0x20uLL, v1);
return fclose(v1);
}
int __fastcall load_key(void *a1)
{
FILE *v1; // ST10_8@1
v1 = fopen("key.txt", "rb");
fread(a1, 1uLL, 0x10uLL, v1);
return fclose(v1);
}
__m128i *__fastcall GenerateSamples(__int64 a1, __int64 a2, __int64 a3, int a4, int a5)
{
__int64 v5; // ST28_8@1
int v6; // ST20_4@1
int v7; // ST18_4@1
v5 = a3;
v6 = a4;
v7 = a5;
memset((void *)a2, 0, 0x10uLL);
memset((void *)v5, 1, 0x10uLL);
*(_DWORD *)(a2 + 8) = v6;
*(_DWORD *)(v5 + 8) = v6;
*(_DWORD *)(a2 + 12) = v7;
*(_DWORD *)(v5 + 12) = v7;
AESEncrypt(a2, a1);
return AESEncrypt(v5, a1);
}
__int64 main()
{
unsigned __int8 v0; // ST3B_1@6
__int64 result; // rax@12
int v2; // [sp+3Ch] [bp-174h]@3
unsigned __int64 i; // [sp+40h] [bp-170h]@1
int v4; // [sp+48h] [bp-168h]@1
__int64 v5; // [sp+50h] [bp-160h]@1
char sample_1; // [sp+60h] [bp-150h]@3
char sample_0; // [sp+70h] [bp-140h]@3
char aes_key; // [sp+80h] [bp-130h]@1
char key_str; // [sp+170h] [bp-40h]@1
char v10; // [sp+180h] [bp-30h]@1
__int64 v11; // [sp+190h] [bp-20h]@11
__int64 v12; // [sp+1A8h] [bp-8h]@1
v12 = *__stack_chk_guard_ptr;
memset(&v10, 0, 0x20uLL);
load_flag(&v10);
memset(&key_str, 0, 0x10uLL);
load_key(&key_str);
AESKeyExpand((__int64)&key_str, (__int64)&aes_key);
v5 = 0LL;
v4 = time(0LL);
for ( i = 0LL; i < 0x400; ++i )
{
GenerateSamples((__int64)&aes_key, (__int64)&sample_0, (__int64)&sample_1, i, v4);
v2 = rand() % 2;
if ( v2 )
print_hex(&sample_1, 16LL);
else
print_hex(&sample_0, 16LL);
puts("0 or 1?");
v0 = getchar() - 48;
puts("ciphertext for 0 is: ");
print_hex(&sample_0, 16LL);
puts("ciphertext for 1 is: ");
print_hex(&sample_1, 16LL);
if ( v0 == v2 )
{
++v5;
puts("Correct!");
}
else
{
puts("Incorrect!");
}
}
if ( 1024 == v5 )
{
puts("Now I will give you the flag:");
AESEncrypt((__int64)&v10, (__int64)&aes_key);
AESEncrypt((__int64)&v11, (__int64)&aes_key);
print_hex(&v10, 32LL);
}
result = *__stack_chk_guard_ptr;
if ( *__stack_chk_guard_ptr == v12 )
result = 0LL;
return result;
}
output.txt from problem statement also gave a session that we need to decrypt to obtain flag:
4d 7c 5d b0 80 45 a2 13 f6 61 0d ca e2 c1 75 9f 0 or 1? ciphertext for 0 is: d2 e2 57 9e ee 1f e0 dd 39 45 8d 5a 3f 4e 97 65 ciphertext for 1 is: 4d 7c 5d b0 80 45 a2 13 f6 61 0d ca e2 c1 75 9f Correct! 1d dc d4 fb e0 4a 33 c2 a8 3f 24 a6 d2 6d 86 39 0 or 1? ciphertext for 0 is: bb a3 80 8c 66 94 c5 b9 c7 2b 18 ad 8d 9a 1f 78 ciphertext for 1 is: 1d dc d4 fb e0 4a 33 c2 a8 3f 24 a6 d2 6d 86 39 Correct! .... Now I will give you the flag: af 93 ce ae 1f 1e 7a 13 26 d6 05 51 97 3c 46 1b c9 b1 56 9c 2c df d5 5a c6 ca 33 46 31 fb 19 73
So we have 1024 known cipher texts, in which there is 512 plain text in the format of 00 00 00 00 00 00 00 00 xx xx xx xx yy yy yy yy where xxxxxxxx is an integer from with values in range [0, 1024) and yyyyyyyy is a unix timestamp, and the rest is in the format of 01 01 01 01 01 01 01 01 xx xx xx xx yy yy yy yy.
After some time spending for research on AES, i found an interesting slide here: http://www.di.ens.fr/~fouque/pub/fse13b.pdf.
So the final solution is solving the 4-th subkey of given AES session byte by byte, trying all 256 values for each byte of the subkey, perform a single aes decryption step each and xor all the values, the corresponding bytes in the received values will have xor-sum of zero with wrong probality of 2-8. The implementation for subkey recovery looks like below:
def recover_subkey():
messages = open("output.txt").read(10*1024*1024).split("\r\n")[:-2]
key0 = messages[3::7]
key1 = messages[5::7]
print len(messages), len(key0), len(key1)
key0 = map(parse_hex, key0)
key1 = map(parse_hex, key1)
sol = [0]*16
for ci in range(16):
found = False
for c in range(256):
sol[ci]=c
valid = True
for i in range(4):
sxor3 = "\x00"*16
for j in range(256):
sxor3 = str_xor(sxor3, decryptOneRound(key0[256*i+j], "".join(map(chr,sol))))
if sxor3[ci]!="\x00":
valid = False
break
if valid:
print "Found byte ", c
found = True
break
assert found
print "Subkey = ", "".join(map(chr,sol)).encode("hex")
for i in range(4):
sxor3 = "\x00"*16
for j in range(256):
sxor3 = str_xor(sxor3, backround(key0[256*i+j], "".join(map(chr,sol))))
print "Test = ", sxor3.encode("hex")
f6f601bb7b6adf60d366c0a78724a66b
Now we can recover the original key:
def unexpandKey(self, size, expandedKeySize, finalBlock):
expandedKey = [0] * expandedKeySize
for j in range(1,1+size):
expandedKey[-j] = finalBlock[-j]
currentSize = expandedKeySize - 4
rconIteration = expandedKeySize/size
rdi = 0
while currentSize >= size:
t = expandedKey[currentSize-4:currentSize]
special = False
if (currentSize-rdi) % size == 0:
rconIteration -= 1
t = self.core(t, rconIteration)
for m in range(4):
expandedKey[currentSize-size+m] = expandedKey[currentSize+m] ^ t[m]
currentSize -= 4
return expandedKey[:size]
174a221440356475dce3a037a317ed4b
Finally it’s so easily to decrypt the flag:
0CTF{~R0MAN_l0VES_B10CK_C1PHER~}
There is a rumor that Arsenal F.C., Talent Yang’s favourite team, always likes to set some “mission impossible” tasks for themselves.
For instance, with a 0-2 home defeat against FC Barcelona they must play a great game in Camp Nou to get to the next round of UEFA Champions League. Can they fulfil this task? Decrypt the provided ciphertext to help them!
(The executable of this challenge is similar to that of People's Square , check the slight difference and enjoy solving it)
Hint: You should perform 2^32 single round decryption first
This’s the same as people_square, but with only 126 known plain texts, with 63 in each group. The zero sumed xor trick cannot be used anymore…
I did not have enough time to solve this problem within the context, i was only 2 hours left and i was so tired due to almost 40 hours playing on both 0ctf and codegate.
The idea is that the internal state of aes before MixColumn step of 3rd round will have unique values when plain text has exactly 1 active byte. We can find out the final subkey by groups of 4 bytes each, confirm the validity of that group with that statement with wrong probability of 256!/[(256-63)! * 256^63] which is almost zero – more than good enough for us to confirm the validity of specified group.
Problem is that pure-python implement cant work anymore 😀 The implement i made for people_square require about 5 mins to check 10000 cases of a group, that will result in about 1491.30808889 days running (lol), so i decided to try out the AES Instruction Set (which’s used in the problem statement too), and surprisingly, the problem is solved after 20 mins running time!!!
int ntest=0;
__m128i test[2][100];
union{
__m128i i128;
uint8_t i8[16];
} key, state;
void solveRound(int a0, int a1, int a2, int a3, int b0, int b1, int b2, int b3){
int check[4][256], checkid[4]={7,7,7,7};
#define INC(a,b,c,d) ++key.i8[a]==0x00 && ++key.i8[b]==0x00 && ++key.i8[c]==0x00 && ++key.i8[d]==0x00
#define TES(a,b) if(check[a][state.i8[b]]!=checkid[a]) check[a][state.i8[b]]=checkid[a]; else {valid=false;break;}
memset(check, 0, sizeof(check));
for(int i=0;i<4;i++) checkid[i]=1;
for(long long i=0;;i++){
if(i%100000000==0){
printf("%lld / %lld\n",i,(1ll<<32));
}
bool valid = true;
for(int j=0;j<4;j++) checkid[j]++;
for(int j=0;j<ntest;j++){
state.i128 = _mm_aesdec_si128(_mm_xor_si128(test[0][j],key.i128), _mm_setzero_si128());
TES(0,a0);TES(1,a1);TES(2,a2);TES(3,a3);
}
if(valid){
printf("Found!\n");
print128_num(key.i128);
break;
}
if(INC(b0, b1, b2, b3)) break;
}
}
void solve(){
FILE* h = fopen("output.txt", "r");
char s[1000];
while(!feof(h)){
fgets(s, 1000, h); // guess line
fgets(s, 1000, h); // 0 or 1?
fgets(s, 1000, h); // ciphertext for 0 is:
if(feof_unlocked(h)) break;
fgets(s, 1000, h);
fromHex((uint8_t*)&test[0][ntest],s);
fgets(s, 1000, h); // ciphertext for 1 is:
fgets(s, 1000, h);
fromHex((uint8_t*)&test[1][ntest],s);
fgets(s, 1000, h); //Correct!
ntest++;
}
fclose(h);
printf("Total samples = %d\n",ntest);
key.i128 = _mm_setzero_si128();
solveRound(0,1,2,3, 0,7,10,13);
solveRound(4,5,6,7, 1,4,11,14);
solveRound(8,9,10,11, 2,5,8,15);
solveRound(12,13,14,15, 3,6,9,12);
}
The final flag is:
0CTF{~~1MP0SS1BLE_1S_N0TH1NG!~~}