Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/1_solution.py

Last active Oct 4, 2019
Embed
What would you like to do?
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
You can’t perform that action at this time.