Instantly share code, notes, and snippets.

# hellman/1_solution.py

Last active October 4, 2019 08:37
Show Gist options
• Save hellman/4881ca802deca1c7fc582015fff41402 to your computer and use it in GitHub Desktop.
PwnThyBytes 2019 CTF - LOTR
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #-*- 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")
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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()