PlaidCTF 2016 crypto 175: rabit Writeup

params.py

n = 81546073902331759271984999004451939555402085006705656828495536906802924215055062358675944026785619015267809774867163668490714884157533291262435378747443005227619394842923633601610550982321457446416213545088054898767148483676379966942027388615616321652290989027944696127478611206798587697949222663092494873481
c = 16155172062598073107968676378352115117161436172814227581212799030353856989153650114500204987192715640325805773228721292633844470727274927681444727510153616642152298025005171599963912929571282929138074246451372957668797897908285264033088572552509959195673435645475880129067211859038705979011490574216118690919

solve.py

from scryptos import *
from params import *
import itertools
import hashlib
import string
import sys

p = Tube(host="rabit.pwning.xxx", port=7763)

def search(s):
  for x in itertools.permutations(string.printable, 5):
    r = s + "".join(x)
    h = hashlib.sha1(r).hexdigest()
    if h[-6:] == "ffffff":
      print h, r
      return r

def oracle(c, p):
  p.writeline(str(c))
  p.read_until("lsb is ")
  return int(p.read(1))

p.read_until("with ")
start = p.read_until(", ")[:-2]
d = search(start)
p.writeline(d)
p.read(1024)

k = 1

lb = 0
ub = n

while True:
  o = oracle((pow(pow(2, k, n), 2, n) * c) % n, p)
  if o == 1:
    lb = (ub + lb) / 2
  else:
    ub = (ub + lb) / 2
  print repr(long_to_bytes(lb))
  if lb == ub:
    break
  k += 1
print repr(long_to_bytes(lb))

solve_log

Mon Apr 18 04:57:33 JST 2016 ~/ctf/plaidctf-2016/crypto175 Battery 0: Full, 100%
> pypy solve.py 
[+] Connected: rabit.pwning.xxx:7763
0543a69b4fcaa0e6f8aea904ae0fbcc3d1ffffff TuKN8sCQuU05$M?
'\x00'
'\x00'
'\x00'
'\x00'
'\x00'
'\x00'
'\x00'
'\x00'
':\x10\x0f3B\xffa\xb2\x86_\xb0\x8d\x87\xad\xdddQ3\x0cU\xc1\xad>\xe1A\x94\xdb\x03OTD\x9e\xe4.h\x0f\xc0h\xa1\xa8\xedd\\\xef+%^\xf3\xb0\xf0\xa5g\x11\xfa\xcduU\xf1\x98\xcbR\xccl\xd0_\x1e\x80\xfd[Y\x91\xe4\xf1q^\xef\xde\xd2\x1e\xa6d\xe3 \x0e\x1b&\x0f\xff\x80\x07\x1a\x967 \xfb\xc7\x7f1 \xaf\x05JYV-;\x94v\xd0#/\xa2\xa2\x17\x96|\x01\xa4\xe2\xa4q\x0b\xcf\x0bS\x89\x99'
':\x10\x0f3B\xffa\xb2\x86_\xb0\x8d\x87\xad\xdddQ3\x0cU\xc1\xad>\xe1A\x94\xdb\x03OTD\x9e\xe4.h\x0f\xc0h\xa1\xa8\xedd\\\xef+%^\xf3\xb0\xf0\xa5g\x11\xfa\xcduU\xf1\x98\xcbR\xccl\xd0_\x1e\x80\xfd[Y\x91\xe4\xf1q^\xef\xde\xd2\x1e\xa6d\xe3 \x0e\x1b&\x0f\xff\x80\x07\x1a\x967 \xfb\xc7\x7f1 \xaf\x05JYV-;\x94v\xd0#/\xa2\xa2\x17\x96|\x01\xa4\xe2\xa4q\x0b\xcf\x0bS\x89\x99'
"H\x94\x13\x00\x13\xbf:\x1f'\xf7\x9c\xb0\xe9\x99T\xbde\x7f\xcfk2\x18\x8e\x99\x91\xfa\x11\xc4#)U\xc6\x9d:\x02\x13\xb0\x82\xca\x13(\xbdt*\xf5\xee\xb6\xb0\x9d,\xce\xc0\xd6y\x80\xd2\xabm\xfe\xfe'\x7f\x88\x04v\xe6!<\xb2/\xf6^-\xcd\xb6\xab\xd6\x86\xa6O\xfe\x1b\xe8\x11\xa1\xef\x93\xff`\x08\xe1;\xc4\xe9:\xb9^\xfdh\xda\xc6\x9c\xef\xab\xb8\x8ay\x94\x84+\xfb\x8bJ\x9d|\x1b\x02\x0e\x1bM\x8dN\xc2\xce(k\xff"
(snip)
"PCTF{LSB_is_4ll_y0u_ne3d}\xf2\xf2\x14R\xcb&C\x8d\xfd\r\xa6\x8bq\x80t\x19\xbauCI\xb6\xafN\xc3\xfa\xb1&\x19\x10\xab\x0c,\x14\xb3\x91\xd2\xad\xf5=\xb6\x8d\xa868c\xecAxy\xedly\xd9\x97/\xa8 +X\xb5\xb5I!\xfd\xcc\x99\xc1\x8d\n\xb3\x85O\x91|\x1dF\xe8\xa28(\x8d\x8d'\x84\x80\xec/\xb3\x964\xa7\x89\xdbM@\xfd6\x9e,\x89\xfd\xcb"
^C

Writeup:
rabit is Rabin + Bit. and I can access to decryption oracle, but oracle gives only LSB of plaintext!

In RSA, If I can access to lsb Oracle, decrypt any ciphertext. but, This is Rabin...

I perceived 2 is Quadratic Residue absolutely, so, 2^k is Quadratic Residue (by Jacobi Symbol (2^k/n) = (2^{k-1}/n)(2/n) ).
well, I can apply LSB Attack.

Flag: PCTF{LSB_is_4ll_y0u_ne3d}

Reference:
RSA least significant bit oracle attack - Cryptography Stack Exchange : http://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack

o = oracle((pow(pow(2, k, n), 2, n) * c) % n, p)

In this line, c is not previously defined.

@x62275: oh, sorry
c and n is defined at params.py. c is encrypted flag, n is parameter.

update gist