TWCTF 2017 - Palindrome Pairs - Challenge Phase
#include <iostream> | |
#include <stdlib.h> | |
using namespace std; | |
#define REP(i,x) for(int i = 0; i < (int)x; i++) | |
#define M 8 | |
int N; | |
string s[1000]; | |
long q[M], p[M], hs[M][1000], hr[M][1000]; | |
long mp(long a, long b, long c){ | |
long r=1; | |
for(;b;b>>=1){ | |
if(b&1) r=r*a%c; | |
a=a*a%c; | |
} | |
return r; | |
} | |
int main() { | |
std::ios_base::sync_with_stdio(false); | |
REP(i, M) { | |
q[i]=rand(); | |
p[i]=rand(); | |
} | |
cin>>N; | |
REP(i,N) cin>>s[i]; | |
REP(i,N){ | |
REP(j,M){ | |
REP(k,s[i].size())hs[j][i]=(hs[j][i]*q[j]+s[i][k])%p[j]; | |
REP(k,s[i].size())hr[j][i]=(hr[j][i]*q[j]+s[i][s[i].size()-k-1])%p[j]; | |
} | |
} | |
long ans=0; | |
REP(i,N){ | |
REP(j,N){ | |
bool o=true; | |
REP(k,M){ | |
if( | |
(hs[k][i]*mp(q[k],s[j].size(),p[k])+hs[k][j] | |
-hr[k][j]*mp(q[k],s[i].size(),p[k])-hr[k][i])%p[k]){ | |
o=false;break; | |
} | |
} | |
if (o) ans++; | |
} | |
} | |
cout<<ans<<endl; | |
} |
''' | |
In this challenge we are given a C code computing a number of palindromic pairs in the input. | |
We need to find an input on which the program is wrong or crashes. | |
The program uses Rabin-Karp rolling hash modulo 8 different random primes to check for palindromes. | |
Notable, it uses rand() function without seeding. Therefore the primes are actually fixed! | |
This is what we are going to exploit! | |
We will build a string such that its hash is equal to the hash of its reverse. | |
Consider even-length string s of length L. | |
Consider pairs of chars (s[i], s[-1-i]). | |
Each such pair contributes | |
(s[i] - s[-1-i]) * (q**i - q**(L-1-i)) | |
to the hash difference H(s) - H(rev(s)), which we want to be zero. | |
That is, only the difference (s[i] - s[-1-i]) is important. | |
Due to the charset requirement, we can get difference between -25 and 25 only. | |
Therefore, we need to find a linear combination of the terms (q**i - q**(L-1-i)) | |
with small coefficients and which sums to zero. | |
LLL is good for this! | |
We build a matrix (rows are the basis of the lattice): | |
(8 terms for i=0) | 1 0 0 ... 0 | |
(8 terms for i=1) | 0 1 0 ... 0 | |
... | |
(8 terms for i=L/2-1) | 0 1 0 ... 0 | |
p0 | 0 ... 0 | |
p1 | 0 ... 0 | |
... | 0 ... 0 | |
p8 | 0 ... 0 | |
We want a vector in this lattice with first 8 zero values (hash difference is zero), | |
and the rest of the values being small (between -25 and 25). | |
Since the hash difference must be exactly zero (small difference would not fit us), | |
we should switch to orthogonal lattice. However, we can use a small trick to go without this. | |
We can multiply the left half of the matrix by a large number, | |
thus telling the LLL algorithm that minimizing the hash differences is priority. | |
This works and for L=100 we can already find lots of solutions! | |
Pseudo-palindrome: | |
aalnjdcagaabafaasaaahiaaaaabaaaeaoeaaajnkjacfbjfaajnaaaaaaaaaadkfaaeahgiapdccoaaifcahgarafkamaaaaaaa | |
To make a challenge input we just split it in a random place: | |
$ cat >hack.in | |
2 | |
aal njdcagaabafaasaaahiaaaaabaaaeaoeaaajnkjacfbjfaajnaaaaaaaaaadkfaaeahgiapdccoaaifcahgarafkamaaaaaaa | |
The challenge program returns 2, while the answer is 0! | |
The flags: | |
TWCTF{Simple_Rolling_Hash_is_not_suitable_to_principal_part} | |
TWCTF{Sorry_for_participants-rolling_hash_is_weak} | |
(the challenge was fixed and another flag was added) | |
''' | |
from sage.all import * | |
qps = [ | |
(0x6b8b4567, 0x327b23c6), | |
(0x643c9869, 0x66334873), | |
(0x74b0dc51, 0x19495cff), | |
(0x2ae8944a, 0x625558ec), | |
(0x238e1f29, 0x46e87ccd), | |
(0x3d1b58ba, 0x507ed7ab), | |
(0x2eb141f2, 0x41b71efb), | |
(0x79e2a9e3, 0x7545e146), | |
] | |
qs = [q for q, p in qps] | |
ps = [p for q, p in qps] | |
M = len(qps) | |
def h(s): | |
"""polynomial hash modulo 8 primes""" | |
v = [0] * 8 | |
for c in s: | |
v = [x * q + ord(c) for x, q in zip(v, qs)] | |
return tuple(v % p for v, p in zip(v, ps)) | |
L = 100 | |
N = L / 2 | |
MULTIPLIER = 100 | |
mv = matrix(ZZ, N, N) | |
for y in xrange(N): | |
for x, q, p in zip(range(8), qs, ps): | |
mv[y,x] = (pow(q, y, p) - pow(q, L-1-y, p)) % p | |
m = matrix(ZZ, N + 8, N + 8) | |
# submatrix with terms | |
m.set_block(0, 0, MULTIPLIER * mv) | |
# modulo reductions | |
m.set_block(N, 0, MULTIPLIER * diagonal_matrix(ps)) | |
# term coefficients | |
m.set_block(0, 8, identity_matrix(N)) | |
# 4th submiatrix is zero | |
for row in m.LLL(): | |
print row[:8], min(row[8:]), "~", max(row[8:]) | |
delta = max(abs(v) for v in row[8:]) | |
if set(row[:8]) == {0} and delta <= 25: | |
print "Good!" | |
s = [None] * L | |
for i, v in enumerate(row[8:]): | |
a = ord('a') | |
b = a + abs(v) | |
if v > 0: | |
a, b = b, a | |
s[i] = a | |
s[-1-i] = b | |
s = "".join(map(chr, s)) | |
print s | |
print h(s) | |
print h(s[::-1]) | |
assert h(s) == h(s[::-1]) | |
break |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment