코딩, 해킹
[HITCON CTF 2019 Quals] Very Simple Haskell


import Data.Char
import System.IO

n :: Integer
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667

k :: Int
k = 131

primes :: [Integer]
primes = take k $ sieve (2 : [3, 5..])
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

stringToInteger :: String -> Integer
stringToInteger str = foldl (\x y -> (toInteger $ ord y) + x*256) 0 str

integerToString :: Integer -> String
integerToString num = f num ""
        f 0 str = str
        f num str = f (div num 256) $ (:) (chr $ fromIntegral $ num `mod` 256) str

numToBits :: Integer -> [Int]
numToBits num = f num []
        f 0 arr = arr
        f x arr = f (div x 2) ((fromInteger $ x `mod` 2) : arr)

extendBits :: Int -> [Int] -> [Int]
extendBits blockLen arr
    | len == 0 = arr
    | len > 0 = (replicate (blockLen-len) 0) ++ arr
    where len = (length arr) `mod` blockLen

calc :: Integer -> [Int] -> Integer
calc num [] = num
calc num arr = calc result restArr
        num2 = num*num `mod` n
        (block, restArr) = splitAt k arr
        zipped = zipWith (\x y -> ((fromIntegral x)*y) `mod` n) block primes  
        mul = product $ filter (/=0) zipped
        result = num2*mul `mod` n

magic :: String -> String
magic input = result
        num = stringToInteger input
        bits = numToBits num
        extended = reverse $ extendBits 8 bits
        oriLen = length extended
        extendedBits = extendBits k extended
        oriLenBits = numToBits $ fromIntegral oriLen
        extendedOriLenBits = extendBits k oriLenBits
        finalBits = extendedOriLenBits ++ extendedBits
        result = show $ calc 1 (reverse finalBits)

main = do
    flag <- readFile "flag" $ length flag
    putStrLn $ magic ("the flag is hitcon{" ++ flag ++ "}") 



Since I'm not that familiar with haskell, I waste a lot of time to understand the logic. The logic is not that hard. It is a Naccache-Stern Knapsack Cryptosystem. Some wise guy in GoN ports haskell code to python, so if you are interested, you can check it.


The candidates of flag are total $10^{12}$. But using Meet-In-The-Middle, You can solve it in $O(10^6log(10^6))$.

from Crypto.Util.number import *
import string
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
k = 131
enc = 84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
prlist = []
for i in range(2,1000000):
  if isPrime(i): prlist.append(i)
  if len(prlist) == k: break

def calc1(L1, L2):
  val = 1
  for i in range(0, len(L1), k):
    val = val*val%n
    for j in range(0,k):
      if L1[i+j] == 1: val = val * prlist[j] % n
  for i in range(0, len(L2), k):
    val = val*val%n
    for j in range(0,k):
      if L2[i+j] == 1: val = val * prlist[j] % n
  return val

base = 129105988525739869308153101831605950072860268575706582195774923614094296354415364173823406181109200888049609207238266506466864447780824680862439187440797565555486108716502098901182492654356397840996322893263870349262138909453630565384869193972124927953237311411285678188486737576555535085444384901167109670365

target = enc * inverse(base, n)
D = dict()
for a1 in string.printable:
  for a2 in string.printable:
    for a3 in string.printable:
      i = bytes_to_long((a1+a2+a3).encode())
      s = bin(i)[2:].zfill(24)
      val = 1
      for j in range(24):
        if s[j]=='1':
          val = val * prlist[j+21] * prlist[j+21] % n
      D[val] = a1+a2+a3

for a1 in string.printable:
  print("now2 ", a1)
  for a2 in string.printable:
    for a3 in string.printable:
      i = bytes_to_long((a1+a2+a3).encode())
      s = bin(i)[2:].zfill(24)
      val = 1
      for j in range(24):
        if s[j]=='1':
          val = val * prlist[j+45] * prlist[j+45] % n
      tt = target * inverse(val, n) % n
      if tt in D:
        print("flag : hitcon{"+D[tt]+a1+a2+a3+"}")

'CTF > Crypto' 카테고리의 다른 글

[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
[TWCTF 2019] M-Poly-Cipher  (0) 2019.09.02
[TWCTF 2019] Simple Logic  (0) 2019.09.02
[TWCTF 2019] real-baby-rsa  (0) 2019.09.02
[Plaid CTF 2019] R u SAd?  (0) 2019.04.16
[0CTF/TCTF 2019] babyrsa  (0) 2019.03.28
댓글 쓰기
[HITCON CTF 2019 Quals] Lost Modulus Again

from Crypto.Util.number import *

class Key:
    def __init__(self, bits):
        assert bits >= 512
        self.p = getPrime(bits)
        self.q = getPrime(bits)
        self.n = self.p * self.q
        self.e = 0x100007
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
        self.dmp1 = self.d%(self.p-1)
        self.dmq1 = self.d%(self.q-1)
        self.iqmp = inverse(self.q, self.p)
        self.ipmq = inverse(self.p, self.q)

    def encrypt(self, data):
        num = bytes_to_long(data)
        result = pow(num, self.e, self.n)
        return long_to_bytes(result)

    def decrypt(self, data):
        num = bytes_to_long(data)
        v1 = pow(num, self.dmp1, self.p)
        v2 = pow(num, self.dmq1, self.q)
        result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
        return long_to_bytes(result)

    def __str__(self):
        return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)

def main():
    key = Key(1024)
    flag = open('flag').read()
    encrypt_flag = key.encrypt(flag)
    assert key.decrypt(encrypt_flag) == flag
    print key
    print encrypt_flag.encode('hex')

if __name__ == '__main__':



In this problem, $e, d, iqmp, ipmq$ is given. To recover flag from encrypt_flag, it is enough to find $n$.


Let's consider below three equations.


$ed-1= k\phi(n) \; (Equation 1)$

$\phi(n) = n - p - q + 1 \; (Equation 2)$

$p \times ipmq + q \times iqmp = n + 1 \; (Equation 3)$


Using this equation, we can get a diophantine equation $(ipmq-1) \times p + (iqmp - 1) \times q = (ed-1)/k$.


Since $k < e$, it is enough to check few kinds of $k$.

from Crypto.Util.number import *

def gcd(a, b):
    a,b = b, a % b 
  return a 

def mysqrt(d):
  st = 1
  en = 10**1300
  while st<=en:
    mid = (st+en)//2
    if mid*mid == d: return mid
    if mid*mid < d: st=mid+1
    else: en=mid-1
  return -1

def egcd(a1, a2):
    x1, x2 = 1, 0
    y1, y2 = 0, 1
    while a2:
        q = a1 // a2
        a1, a2 = a2, a1 - q * a2
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2
    return (x1, y1, a1)

e =   1048583
d =   20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
enc = 6315517144108346181816723099897023675574911374735398936591833706590364258184564710827234427731055048559822607765825888615252018165526396090041236515481884097316115657845863616027191241546872931338194871262588098949428397377758354022592306745947669728354322461011070818767686781572984901259034033895184947744496886943392083163678583781999851929812332715335746883110069495497948728241194518127509291959160766882315610259762352662845983222877441386838765184047248466927144181212035420321292287216414973587365695429489044345623525454703093721722072717560946535366845119502057231317372617085049803374310078177219696035587
xx=  e*d-1

#iqmp bit_length : 1022
iqmp = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
#ipmq bit_length : 1024
ipmq = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331

gg = gcd(iqmp-1,ipmq-1)

for k in range(1,e):
  if (e*d-1) % k == 0:
    phi_n = (e*d-1)//k
    if not (1<<2046) < phi_n < (1<<2048) : continue
    if phi_n % gg != 0: continue
    c = phi_n // gg
    a = (ipmq-1)//gg
    b = (iqmp-1)//gg
    # p*a + q*b = c
    pmod = inverse(a, b)*c%b
    for j in range(100000):
      p = pmod + j*b
      if p > (1<<1024): break
      if not isPrime(p): continue
      q = (c-p*a)//b
      if (iqmp*q-1)%p == 0 and (ipmq*p-1)%q == 0:
        M = pow(enc,d,p*q)

#p = 135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477
#q = 166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929
#M = pow(enc,d,p*q)

# hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}

'CTF > Crypto' 카테고리의 다른 글

[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
[TWCTF 2019] M-Poly-Cipher  (0) 2019.09.02
[TWCTF 2019] Simple Logic  (0) 2019.09.02
[TWCTF 2019] real-baby-rsa  (0) 2019.09.02
[Plaid CTF 2019] R u SAd?  (0) 2019.04.16
[0CTF/TCTF 2019] babyrsa  (0) 2019.03.28
DEF CON CTF 2019 후기

데프콘에 갔다 온 지 벌써 두 달이나 됐네요. 후기를 진작에 썼어야 하는데 저번 달에 글을 날려먹고 미루다가 지금에야 씁니다. 이번에는 임시저장을 꼬박꼬박 하면서 작성하고 있습니다.


저희 팀은 CodeRed, GYG와 연합을 해서 팀 CGC로 예선을 치렀고 예선 때 암호 문제를 붙잡긴 했지만 썩 문제를 잘 해결하지는 못했습니다. 역시 잠을 잘 자는 게 중요한 것 같아요. 본선은 Attack & Defense 형식이고 지금까지의 경향을 볼 때 딱히 저의 지식이 도움이 될 것 같지는 않아 본선에 참여할지 말지 고민을 좀 많이 했습니다. ICPC 준비를 하는 게 마음에 좀 걸리기도 했고요.


결론적으로 보험용으로 생각하자고, 혹시 암호 관련 문제가 조금이라도 나오면 좋은 거고 아니면 어쩔 수 없는 것으로 마음을 제 마음대로 편하게 먹고 본선에 참여하기로 마음을 먹었습니다.


항공권은 BOB에서, 숙박비의 대부분은 학과에서 지원해주었습니다. 덕분에 금전적인 부담을 많이 덜고 대회에 참여할 수 있었습니다. 감사합니다.


아마 기억상으로 전날 UCPC를 치고 바로 다음 날 출국이었던 것 같습니다. ICPC의 부담감이 좀 커서 머릿속은 복잡했지만 그래도 막상 공항에 도착하니 여행이 기대됐습니다.


고2 때 고등학교에서 단체로 여행을 갈 때 처음으로 미국에 갔고 그 당시 추가적인 인터뷰를 받았습니다. 그리고 이번에도 맥캐런 공항에 도착한 후 일행 중에서 저만 인터뷰를 받았습니다.


첫 질문은 "예전에 미국에 올 당시 어떤 종류의 비자를 발급받아 왔나?"였고 저는 질문을 이해하지 못했습니다,,, 제가 어버버하고 있으니 한국인 통역가를 불러서 질문을 주고받았습니다. 질답은 아래와 같았습니다.


Q. 예전에 미국에 올 당시 어떤 종류의 비자를 발급받아 왔나?

A. 4-5년 전에 학교에서 단체로 온 기억은 있는데 학교에서 단체로 처리를 해서 기억이 잘 나지 않는다.


Q. 이번에 어떤 목적으로 온 것인가?

A. 여행


Q. 돈 얼마나 가지고 왔는가?

A. 현금 300달러에 한도가 1000달러 정도인 신용카드 및 체크카드


Q. 최근에 중국을 왜 2번 방문했는가?

A. 대회에 참여하기 위해서였다.


Q. 어떤 대회인가?

A. 해킹대회이다.


Q. 당신은 해커인가?

A. 그렇다.


Q. 혹시 이번에 블랙햇에 참석하는가?

A. 데프콘이라고 비슷한 정보보안 쪽 콘퍼런스에 참석한다.


Q. 당신은 화이트 해커인가?

A. 그렇다.


Q. 혹시 내 와이프의 휴대폰을 해킹해줄 수 있는가?

A. 그건 불법이다ㅋㅋㅋ..


마지막에 드립을 치시고 입국 허가를 해주셨습니다. 다음번에 미국을 갈 때에도 인터뷰에 걸린다면 뭔가 제가 미국에 밉보인 게 있나 봐요ㅜㅜ


아무튼 입국에 성공했습니다!! 


여름의 라스베이거스는 정말 건조하고 또 정말 더웠습니다. 일단 우버를 타고 숙소에 도착한 다음 인근 식당에서 저녁을 먹었습니다. 제가 사진에는 소질이 없지만 아무튼 맛있었습니다 ㅎㅅㅎ


저희가 지낼 숙소는 에어비엔비였고 슈퍼마켓에 가서 술과 음식을 풀매수했습니다. 풀매수 가즈아

바로 다음날 새벽 6시에 그랜드캐니언 1박 2일 투어 픽업이 숙소 앞에 오기로 예정되어있었기 때문에 일찍 자려고 했지만 시차 때문에 그게 잘 안됐고 새벽 4시쯤 깼습니다. 집에서는 요리를 해 먹는 게 그렇게 귀찮더니 밖에 나오니 갑자기 요리가 하고 싶어 져 계란 프라이와 컵라면 하나로 가볍게 아침을 해결했습니다.



이후 1박 2일간 봉고차에 타서 열심히 그랜드캐니언을 돌아다녔고 자연경관이 정말 멋있었습니다. 사진도 많이 찍었습니다ㅎㅎ


그랜드캐니언 투어를 마치고 돌아온 후에는 시차 적응 + 오래 걸은 것의 여파로 정말 피곤해서 바로 뻗어 잤습니다.


다음 날 점심에는 삼성 리서치 시큐리티 랩(2018년 초에 인턴을 했던 거기입니다!)에서 저희와 SeoulPlusbadass팀 참가자들을 불러 모아 라스베이거스 메인 스트립에 있는 Hot N Juicy Crawfish를 사주었습니다. 머 기업의 자본력을 느끼며 감사히 얻어먹었습니다ㅜㅜ SSTF에 갔어야 했는데 ICPC를 준비하느라ㅜ.. 내년에 꼭 가겠습니다!!


점심을 먹은 후 스트립을 돌아다니면서 시간을 때웠고 저녁에는 BOB에서 Ginseng Korean BBQ를 사주었습니다. 진정한 의미로 하루 종일 놀고먹었네요ㅎㅎ


다음 날이 바로 데프콘 전날이었고, 운영진 측에서 각 팀에게 호텔방 4개를 주고 BOB에서 스위트룸 1개를 줘서 매우 매우 매우 편안한 환경 속에서 대회를 치를 수 있었습니다. 다시 한번 감사합니다!!!


저희가 받은 Planet Hollywood 호텔에서는 데프콘 참가자들을 위해 따로 카드키를 만들어두어서 아주 예쁜 카드키를 받았습니다.


그날 밤 CGC 팀원들끼리 모여 스위트룸에 모여 간단하게 논의를 하고 헤어졌습니다. 저는 살짝 어부지리로 스위트룸에서 잤습니다. 개꿀이었습니다 ㄹㅇ



드디어 대회날이 되었고 저는 온 테이블은 하지 않은 채 스위트룸에서 문제를 봤습니다. 대회는 총 52시간 동안 진행되었고 1, 2일 차에는 8시간, 3일 차에는 4시간 동안 공방이 진행되었습니다.


이전에 데프콘을 참석해보지 않아 현재의 Organizer인 OOO(Order Of Overflow)가 맡기 전에는 어떤 식으로 대회 환경이 구축되어있었는지 모르겠지만 , OOO가 진행하는 데프콘에서는 실행파일을 패치해서 직접 공방전이 진행되는 서버에 올리는 것이 아니라, 일단 패치된 실행파일을 보내면 그쪽에서 (아마 자동화되어있을) SLA(Service Level Agreement, 서비스가 정상적으로 작동하는지 확인하는 작업)를 거쳐 해당 패치를 반영할지 말지를 결정합니다. 문제에 따라 패치할 수 있는 바이트 수가 정해져 있는 경우도 있었습니다.


Attack & Defense 형식의 문제는 위와 같이 진행이 되었고 King Of The Hill 형식의 문제는 주어진 문제에서 요구하는 바를 달성해 점수를 얻는 문제였습니다. 이번에는 ROP를 이용해 비행기 게임을 하는 문제(ROPShip), Xbox를 리버 싱하는 문제(Dooom), 1-bit를 flip해도 정상적으로 동작하는 쉘 코드를 만드는 문제(bitflip conjecture) 이 3문제가 있었습니다.


역시 예상했던 대로 제가 도움이 될만한 문제는 딱히 없었고 굳이 따지자면 Attack & Defense에 출제되었던, Deep Learning과 관련이 있는 ai-han-solo라는 문제와 bitflip conjecture 정도에 아주 미약하게나마 기여를 할 수 있었지만 객관적으로 딱히 가서 제가 한 게 없었습니다. 비록 보험용으로 스스로를 생각하긴 했지만 막상 가서 앉아는 있는데 할게 없으니 참 슬픈 일이었습니다. 더군다나 팀이 총 13명 정도로 인원수가 많이 부족했어서 더 미안했습니다.


아쉽게도 대회 성적은 좋지 않았습니다. 간신히 갓등만 면했습니다ㅎㅎ... 저는 한게 없었지만 다른 분들 모두 대단하신 분들이고 또 대회 내내 정말 고생 많았는데 아쉬웠어요. 아쉽지만 다음에 더 잘하면 되겠죠.


끝나고 대회장에서 동아리원들끼리 기념사진을 찍었습니다.


굉장히 피곤해서 금방 잘 줄 알았는데 막상 잠이 그렇게 많이 오지는 않아서 호텔 방에서 동아리원들이랑 SeoulPlusBadass 팀원 두 분과 맥주나 마시면서 놀았습니다. 이쪽 분야가 그다지 넓지 않아서 대회들을 돌아다니다 보면 이런 식으로 금세 zl젼해커들을 많이 알게 됩니다.


다음날 체크아웃을 하고 출국은 거의 자정쯤이었기 때문에 무엇을 하면서 시간을 때울까 고민하다가 스트라토스피어에서 스카이점프도 하고 놀이기구도 탔습니다. 딴 것보다 놀이기구를 거의 기다림 없이 바로 탈 수 있다는 게 너무 좋았습니다.


스카이점프는 대충 이런 식으로 250m를 하강합니다. 처음 해봤는데 정말 재밌었습니다. 신나게 놀다가 노스 아웃렛으로 쇼핑하러 갔는데 생각보다 딱 끌리는 게 없어서 그냥 구경만 하다가 다시 돌아왔습니다.


이후 라스베이거스를 뒤로한 채 한국으로 돌아왔습니다 ^__^

아직 부족한 게 많은데 이런 경험을 할 수 있어서 좋았고 또 데려가 준 팀원들도 고마웠습니다. 제 능력을 써먹을 수 있는 문제가 나왔다면 참 좋았을 텐데 그건 다음 기회에ㅎㅎ..


아쉽지만 다음에는 굳이 라스베이거스까지 와서 본선에 참여할 필요는 없겠다는 생각이 들었습니다. 제가 좋아하는 암호학/PPC 분야의 문제는 비중이 매우 낮거나 출제가 되지 않을 테니 그냥 한국에서 해도 될 것 같아서요.


그렇지만 이번 대회를 포함한 여행은 정말 즐거웠고 또 데프콘 빌리지에서 발표를 할 것이라는 목표를 가지게 되는 계기가 되었습니다.


ICPC 월파도 가고 싶고 코드 포스 레드도 달고 싶고 CTF도 정말 잘하고 싶고 CVE도 하나 가지고 싶고 데프콘에서 발표도 해보고 싶고 하고 싶은 건 많지만 아직 부족하네요. 현실적으로 어느 하나라도 이루려면 정말 오랜 시간이 필요하거나, 어쩌면 불가능할 수도 있겠지만 상상하면서 뭔가 기분이 좋아지는 목표를 품고 있는 것도 나쁘지 않다고 생각합니다 :p


이상으로 후기를 마치겠습니다!!

'대회 > 각종 대회 후기' 카테고리의 다른 글

2019 ACM-ICPC Seoul Regional 후기  (0) 2019.11.14
DEF CON CTF 2019 후기  (2) 2019.10.14
SCPC 2019, UCPC 2019 후기  (0) 2019.08.08
WCTF 2019 후기  (2) 2019.07.12
0CTF/TCTF 2019 후기  (0) 2019.06.19
Codegate 2019 본선 후기  (0) 2019.03.30
Google Hash Code 2019 후기  (3) 2019.03.05
댓글 쓰기