PwnThyBytes 2019 CTF - LOTR
#-*- coding:utf-8 -*- | |
# python3 adaptation... | |
from __future__ import print_function, division | |
from sage.all import * | |
# begin copy paste ================ | |
import hashlib | |
f = open('gov_officials_PK.txt','r') | |
Pub_keys = [] | |
for i in f: | |
Pub_keys.append(int(i.strip(),10)) | |
f.close() | |
def sha256(my_string): | |
m = hashlib.sha256(my_string).digest() | |
return int(m.encode('hex'),16) | |
k = 1024 | |
b = 2*k + 128 | |
e = 0x10001 | |
signer_count = 243 | |
def RSA_permutation(x, e, N): | |
r = x % N | |
q = x // N | |
if (q+1)*N <= 2 ** b: | |
return q * N + pow(r,e,N) | |
else: | |
return x | |
def gen(pk): | |
sig = randint(2 ** (b-1) + 2 ** (2*k) + 1, 2 ** b - 2 ** (2 * k) - 1) | |
w = RSA_permutation(sig, e, pk) % 2**256 | |
w = tobin(w, 256) | |
w = vector(GF(2), w) | |
return sig, w | |
# end copy paste =================== | |
def tobin(x, bits): | |
return tuple(ZZ(x).digits(2, padto=bits)[::-1]) | |
mat = [] | |
sources = [] | |
# since we must take exactly one sig per member | |
# we start with a pair of random sigs per member, | |
# "assume" that we take the first ones (record xor(all w1) = target1) | |
# and make a binary variable tracking | |
# whether we switch from first sig to the second | |
# for each pair we keep the difference of respective (w) vectors | |
# as a result, we need to find an *arbitrary* subset of those differences | |
# that matches the difference (target1 xor final_target) | |
target2 = vector(GF(2), tobin(sha256("FAKE NEWS"), 256)) | |
target1 = vector(GF(2), (0,)*256) | |
for j in range(len(Pub_keys)-1): | |
sig1, w1 = gen(Pub_keys[j]) | |
sig2, w2 = gen(Pub_keys[j]) | |
target1 += w1 | |
sources.append((sig1, sig2)) | |
mat.append(vector(GF(2), w1 + w2)) | |
# note that we have 243 vectors and 256 equations | |
# we have to be lucky to get the solution | |
# but instead of generating the whole system many times, | |
# we can change only the last vector | |
# and automatically assume that we take it in the solution | |
# we need on average 2^{256-242} = 16k runs | |
# if the matrix without the last vector has full rank 242 | |
# (this check is not done here) | |
m = matrix(GF(2), mat).transpose() | |
print(m.nrows(), "x", m.ncols(), ":", m.rank()) | |
# generate parity check matrix | |
# to check for solutions quickly | |
# matrix x vector is O(n^2) | |
# vs matrix.solve_right is O(n^2.8) or whatever | |
paritycheck = m.left_kernel().matrix() | |
itr = 0 | |
while True: | |
sig, w = gen(Pub_keys[-1]) | |
target = target1 + target2 + w | |
if paritycheck * target == 0: | |
break | |
print("no sol..", itr, paritycheck * target) | |
itr += 1 | |
sol = m.solve_right(target) | |
print("sol", sol) | |
ans = [s2 if take else s1 for (s1, s2), take in zip(sources, sol)] | |
ans.append(sig) | |
w = 0 | |
for j in range(len(Pub_keys)): | |
w = w ^ RSA_permutation(ans[j], e, Pub_keys[j]) | |
assert sha256("FAKE NEWS") == w % (2 ** 256) | |
f = open("sol", "w") | |
f.write("2\n") | |
f.write("FAKE NEWS\n") | |
for v in ans: | |
f.write("%d\n" % v) | |
f.close() | |
os.system("cat sol | nc 52.142.217.130 13375") |
""" | |
Author: rtitiu | |
The file gov_officials_PK.txt contains a list of RSA public keys of some government employees. Any signer who knows the secret key d[j] corresponding to one of the public keys N[j] is able to anonymously sign any document on behalf of all the people from the list. | |
Thus, a whistleblower can anonymously leak documents whose authenticity can be publicly verified, while maintaining anonymity within that group of people. | |
The goal of the task is to produce a valid signature of a specific document/message on behalf of the entire group, even though you don't have access to any of the secret keys. Good luck! | |
nc 52.142.217.130 13375 | |
""" | |
import gmpy, signal, hashlib, sys | |
from os import urandom | |
from hashlib import * | |
from random import randint | |
k = 1024 | |
b = 2*k + 128 | |
e = 0x10001 | |
signer_count = 243 | |
def sha256(my_string): | |
m = hashlib.sha256(my_string).digest() | |
return int(m.encode('hex'),16) | |
def Sign_Keygen(no_users): | |
f = open('gov_officials_PK.txt','w') | |
g = open('gov_officials_SK.txt','w') | |
for i in range(no_users): | |
p = gmpy.next_prime(int(urandom(k / 8).encode('hex'),16)) | |
q = gmpy.next_prime(int(urandom(k / 8).encode('hex'),16)) | |
N = p * q | |
d = gmpy.invert(e, (p-1)*(q-1)) | |
f.write(str(N) + '\n') | |
g.write(str(d) + '\n') | |
f.close() | |
g.close() | |
def RSA_permutation(x,e,N): | |
r = x % N | |
q = x // N | |
if (q+1)*N <= 2 ** b: | |
return q * N + pow(r,e,N) | |
else: | |
return x | |
def Sign_Oracle(signer,message): | |
if message != 'FAKE NEWS': | |
f = open('gov_officials_PK.txt','r') | |
g = open('gov_officials_SK.txt','r') | |
Pub_keys = [] | |
d = [] | |
for i in f: | |
Pub_keys.append(int(i.strip(),10)) | |
if signer < 0 or signer >= len(Pub_keys): | |
return 'NOT allowed! ' | |
for i in g: | |
d.append(int(i.strip(),10)) | |
f.close() | |
g.close() | |
x = [0] * len(Pub_keys) | |
v = sha256(message) | |
for j in range(len(Pub_keys)): | |
if (j != signer): | |
x[j] = randint(2 ** (b-1) + 1, 2 ** b - 1) | |
v = v ^ RSA_permutation(x[j],e,Pub_keys[j]) | |
x[signer] = RSA_permutation(v,d[signer],Pub_keys[signer]) | |
return x | |
else: | |
return 'NOT allowed! ' | |
def Verify(x, message): | |
w = 0 | |
f = open('gov_officials_PK.txt','r') | |
Pub_keys = [] | |
for i in f: | |
Pub_keys.append(int(i.strip(),10)) | |
f.close() | |
if len(x) != len(Pub_keys): | |
return 'incorrect component count: %d given versus %d needed' % ( len(x), len(Pub_keys) ) | |
for j in range(len(Pub_keys)): | |
w = w ^ RSA_permutation(x[j],e,Pub_keys[j]) | |
if sha256(message) == w % (2 ** 256): | |
if message == 'FAKE NEWS': | |
flag = open("flag.txt").read() | |
return 'VALID signature, you get the FLAG: %s' % flag | |
else: | |
return 'VALID signature' | |
else: | |
return 'NOT valid' | |
def do_initial_setup(): | |
Sign_Keygen(signer_count) | |
def do_sign(): | |
print "What message do you want to sign?" | |
msg = raw_input().strip() | |
print "Who do you want to sign it?" | |
idx = raw_input().strip() | |
try: | |
idx = int(idx) | |
except: | |
return | |
signature = Sign_Oracle(idx, msg) | |
print len(signature) | |
print "Here you go:" | |
for i in signature: | |
print i | |
def do_verify(): | |
print "What message do you want to verify?" | |
msg = raw_input().strip() | |
print "What's the signature?" | |
sig_vec = [] | |
for i in range(signer_count): | |
sig = int(raw_input()) | |
if (sig < 2 ** b - 2 ** (2 * k)) and (sig > 2 ** (b-1) + 2 ** (2*k)): | |
sig_vec.append( sig ) | |
else: | |
print "Signature NOT valid!" | |
exit() | |
print Verify(sig_vec, msg) | |
def input_int(prompt): | |
sys.stdout.write(prompt) | |
try: | |
n = int(raw_input()) | |
return n | |
except ValueError: | |
return 0 | |
except: | |
exit() | |
def menu(): | |
while True: | |
print "========== LOTR ==========" | |
print "1. Sign message" | |
print "2. Verify message" | |
print "3. Exit" | |
choice = input_int("Command: ") | |
{ | |
1: do_sign, | |
2: do_verify, | |
3: exit, | |
}.get(choice, lambda *args:1)() | |
if __name__ == "__main__": | |
signal.alarm(15) | |
menu() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment