Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
TWCTF 2017 - BabyPinhole
#-*- coding:utf-8 -*-
"""
In this challenge we have a Paillier cryptosystem.
We are given a decryption oracle, which leaks only one bit in the middle of the plaintext.
Due to homomorphic properties of the Paillier cryptosystem, we can recover the full decryption using such an oracle.
1. First, we recover the lower half of the message bit-by-bit.
This can be done by manipulating and observing the carry bit going through the pinhole,
by exploiting the homomorphic addition:
leaked guess
| |
| |
v [ known ] v [ unknown ]
@ 0 0 1 0 1 X ? ? ? ? ? ?
| +
|  1 1 0 1 0 1 0 0 0 0 0 0
v =
(+0)<1 1 1 1 1 1 (if X = 0)
(+1)<0 0 0 0 0 0 (if X = 1)
2. Once we know the lower half, we can easily learn the higher half.
First, we zeroize the lower half by adding its complement.
Then, we can simply shift the message right and leak each bit,
by homomorphically multiplying the message by the inverse of 2.
The flag: TWCTF{ccb71c01f350cf0bc844e87d161f84b9b479b439}
"""
from sock import Sock
from libnum import invmod, gcd
from random import randint
n = 0xadd142708d464b5c50b936f2dc3a0419842a06741761e160d31d6c0330f2c515b91479f37502a0e9ddf30f7a18c71ef1eba993bdc368f7e90b58fb9fdbfc0d9ee0776dc629c8893a118e0ad8fc05633f0b9b4ab20f7c6363c4625dbaedf5a8d8799abc8353cb54bbfeab829792eb57837030900d73a06c4e87172599338fd5b1
n2 = n **2
g = 0x676ae3e2f70e9a5e35b007a70f4e7e113a77f0dbe462d867b19a67839f41b6e66940c02936bb73839d98966fc01f81b2b79c834347e71de6d754b038cb83f27bac6b33bf7ebd25de75a625ea6dd78fb973ed8637d32d2eaf5ae412b5222c8efea99b183ac823ab04219f1b700b207614df11f1f3759dea6d722635f45e453f6eae4d597dcb741d996ec72fe3e54075f6211056769056c5ad949c8becec7e179da3514c1f110ce65dc39300dfdce1170893c44f334a1b7260c51fb71b2d4dc6032e907bbaeebff763665e38cdfe418039dc782ae46f80e835bfd1ef94aeaba3ab086e61dab2ff99f600eb8d1cd3cf3fc952b56b561adc2de2097e7d04cb7c556
CT = 0x2ab54e5c3bde8614bd0e98bf838eb998d071ead770577333cf472fb54bdc72833c3daa76a07a4fee8738e75eb3403c6bcbd24293dc2b661ab1462d6d6ac19188879f3b1c51e5094eb66e61763df22c0654174032f15613a53c0bed24920fd8601d0ac42465267b7eba01a6df3ab14dd039a32432003fd8c3db0501ae2046a76a8b1e56f456a2d40e2dd6e2e1ab77a8d96318778e8a61fe32d03407fc6a7429ec1fb66fc68c92e33310b3a574bde7818eb7089d392a30d07c85032a3d34fd589889ff6053fb19592dbb647a38063c5b403d64ee94859d9cf9b746041e5494ab7413f508d814c4b3bba29bca41d4464e1feb2bce27b3b081c85b455e035a138747
assert gcd(g-1, n2) == n
mbits = 1024
b = mbits//2
f = None
nref = 999999999
def refresh():
global f, nref
nref += 1
if nref >= 100:
f = Sock("ppc2.chal.ctf.westerns.tokyo 38264", timeout=1000)
def oracle(add, aftermul=1):
refresh()
c = CT * pow(g, add, n2) % n2
c = pow(c, aftermul, n2)
f.send_line("%x" % c)
res = f.read_line().strip()
assert res in "01"
return int(res)
base = oracle(0)
known = 0
for pos in reversed(range(b)):
k = b - 1 - pos # number of already known bits
add = (2**k - 1 - known) * 2 + 1
newbit = oracle(add << pos) ^ base
known = (known << 1) + newbit
print "new low", pos, bin(known)[2:].rstrip("L").rjust(b-pos+1, "0")
low = known
assert low < 2**b
add = 2**b - low
known = low
for i in xrange(1, b):
new = oracle(add=add, aftermul=invmod(2**i, n))
known |= new << (b + i)
print "new high", b - i, bin(known)[2:].rstrip("L").rjust(b+i+1, "0")
# correct the zeroizing addition
known -= 1<<b
from hashlib import sha1
print "TWCTF{" + sha1(str(known)).hexdigest() + "}"
# verify
for i in xrange(100):
a = randint(0, n-1)
m = randint(1, n-1)
expected = (known + a) * m % n
expected >>= b
expected &= 1
real = oracle(a, m)
print expected, real
assert expected == real
# Python 3
from Crypto.Util.number import *
from hashlib import sha1
bits = 1024
def LCM(x, y):
return x * y // GCD(x, y)
def L(x, n):
return (x - 1) // n
p = getStrongPrime(bits/2)
q = getStrongPrime(bits/2)
n = p*q
n2 = n*n
k = getRandomRange(0, n)
g = (1 + k*n) % n2
sk1 = LCM(p - 1, q - 1)
sk2 = inverse(L(pow(g, sk1, n2), n), n)
message = getRandomInteger(bits - 1)
with open("message", "w") as f:
f.write(hex(message))
with open("flag", "w") as f:
f.write("TWCTF{" + sha1(str(message).encode("ascii")).hexdigest() + "}\n")
with open("secretkey", "w") as f:
f.write(hex(sk1) + "\n")
f.write(hex(sk2) + "\n")
with open("publickey", "w") as f:
f.write(hex(n) + "\n")
f.write(hex(n2) + "\n")
f.write(hex(g) + "\n")
def encrypt(m):
r = getRandomRange(1, n2)
c = pow(g, m, n2) * pow(r, n, n2) % n2
return c
ciphertext = encrypt(message)
with open("ciphertext", "w") as f:
f.write(hex(ciphertext) + "\n")
# Python 3
from signal import alarm
from Crypto.Util.number import *
import Crypto.Random as Random
with open("secretkey", "r") as f:
sk1 = int(f.readline(), 16)
sk2 = int(f.readline(), 16)
with open("publickey", "r") as f:
n = int(f.readline(), 16)
n2 = int(f.readline(), 16)
g = int(f.readline(), 16)
cbits = size(n2)
mbits = size(n)
b = mbits//2
def L(x, n):
return (x - 1) // n
def decrypt(c, sk1, sk2, n, n2):
return L(pow(c, sk1, n2), n) * sk2 % n
def run(fin, fout):
alarm(1200)
try:
while True:
line = fin.readline()[:4+cbits//4]
ciphertext = int(line, 16) # Note: input is HEX
m = decrypt(ciphertext, sk1, sk2, n, n2)
fout.write(str((m >> b) & 1) + "\n")
fout.flush()
except:
pass
if __name__ == "__main__":
run(sys.stdin, sys.stdout)
0xadd142708d464b5c50b936f2dc3a0419842a06741761e160d31d6c0330f2c515b91479f37502a0e9ddf30f7a18c71ef1eba993bdc368f7e90b58fb9fdbfc0d9ee0776dc629c8893a118e0ad8fc05633f0b9b4ab20f7c6363c4625dbaedf5a8d8799abc8353cb54bbfeab829792eb57837030900d73a06c4e87172599338fd5b1
0x76047ed9abf5e8f5fc2a2f67162eb2bc0359c3ffa3585ba846de7181d815dba75738c65f79d8923c061b55933fbd391e48da3cd94ab6c5b09f7c9e80dea0b5848a8cf74cd27e429ca3d4647d81d4deae1ec76ffd732124c0e31fe6fbed1103135f19f3fcc2ec04a9f694c4468597b12e1c0020d478b82a21ca899e76f6f28d32cef1eea558fd8fddf1a870ceae356809cf567c1627fdcbb967e4c5996cf15119ab5c058d8bf4280efc5eff7659d717ccfa08169681a2445a17874099e448278fdf7e99b7df1a2e309592e2dc3c6a762a97d46e4b8a5e2824e52e30a241bdce7aa67f788866e41b2a2282f7d2c5fa606ad4541a5e46a22bab53e33786f41e0461
0x676ae3e2f70e9a5e35b007a70f4e7e113a77f0dbe462d867b19a67839f41b6e66940c02936bb73839d98966fc01f81b2b79c834347e71de6d754b038cb83f27bac6b33bf7ebd25de75a625ea6dd78fb973ed8637d32d2eaf5ae412b5222c8efea99b183ac823ab04219f1b700b207614df11f1f3759dea6d722635f45e453f6eae4d597dcb741d996ec72fe3e54075f6211056769056c5ad949c8becec7e179da3514c1f110ce65dc39300dfdce1170893c44f334a1b7260c51fb71b2d4dc6032e907bbaeebff763665e38cdfe418039dc782ae46f80e835bfd1ef94aeaba3ab086e61dab2ff99f600eb8d1cd3cf3fc952b56b561adc2de2097e7d04cb7c556
0x2ab54e5c3bde8614bd0e98bf838eb998d071ead770577333cf472fb54bdc72833c3daa76a07a4fee8738e75eb3403c6bcbd24293dc2b661ab1462d6d6ac19188879f3b1c51e5094eb66e61763df22c0654174032f15613a53c0bed24920fd8601d0ac42465267b7eba01a6df3ab14dd039a32432003fd8c3db0501ae2046a76a8b1e56f456a2d40e2dd6e2e1ab77a8d96318778e8a61fe32d03407fc6a7429ec1fb66fc68c92e33310b3a574bde7818eb7089d392a30d07c85032a3d34fd589889ff6053fb19592dbb647a38063c5b403d64ee94859d9cf9b746041e5494ab7413f508d814c4b3bba29bca41d4464e1feb2bce27b3b081c85b455e035a138747
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment