-
RBTree's profile image
RBTree
November 21, 2021
Attacking a Variant of the RSA Cryptosystem
서론 이번 글은 저번 달의 글에 이어서 pbctf 2021를 출제하면서 사용한 논문 하나를 리뷰하려고 합니다. 이 논문은 Yet Another RSA라는 문제로 작성하게 되었습니다. 해당 논문의 제목은 Classical Attacks on a Variant of the RSA Cryptosystem인데요, RSA의 변종에 대해 $d$가 작을 경우의 공격법을 다루는 논문입니다. 본론 RSA Variant 이 논문에서 소개하는 RSA의 변종은 정수가 아닌 group 위에서 정의됩니다. 해당 그룹에 대해서 정의하자면 다음과 같습니다. Field $(\mathbb{F}, +, \cdot)$에 대해서 non-cubic integer $r \in \mathbb{F}$를 하나 뽑읍시다....
-
RBTree's profile image
RBTree
October 24, 2021
Breaking Combined Multiple Recursive Generators
서론 10월 중에 제가 속한 CTF 팀 perfect blue에서 pbctf 2021을 주최했습니다. CTF를 준비하면서 다양한 암호학 논문들을 읽어보았는데, 그 중에서도 참고할만한 흥미로운 공격이 있어서 Yet Another PRNG라는 문제로 작성하게 되었습니다. 해당 문제는 CMRG(Combined Multiple Recursive Generator)라는 PRNG의 선형성을 공격하는 문제로, 이 논문의 5절에서 공격의 원형을 살펴볼 수 있습니다. 본론 CMRG CMRG는 2개의 LCG를 혼합한 형태입니다. 서로소인 $m1, m2$가 존재할 때, $x_i = a_{11} x_{i-1} + a_{12}x_{i-2} + a_{13} x_{i-3} \mod m_1$ $y_i = a_{21} y_{i-1}...
-
RBTree's profile image
RBTree
July 16, 2021
Differential Cryptanalysis on 4-round DES
서론 이번 글에서는 차분 분석 (Differential cryptanalysis)가 무엇인지 간략하게 살펴보고, 4-round DES에 대한 차분 공격을 예시로 알아보고자 합니다. 본론 차분 분석 차분 분석을 간단하게 말하자면, 어떤 함수 $f$가 주어져있을 때 $x, y$ 에 대해서 $(y - x, f(y) - f(x))$ 가 일정 확률로 특정 관계성을 만족하는 것을 이용하는 분석 방법 중 하나입니다. 이렇게만 이야기하면 쉽게 와닿지 않을 것 같아서 예시를 준비해봤습니다. S-box DES, AES와 같은 암호들을 살펴보면, 대부분의 연산이 선형 계산으로 이루어져 있습니다. 즉, 어떤...
-
RBTree's profile image
RBTree
May 18, 2021
Breaking Python random module
서론 PlaidCTF 2021에서 Fake Medallion 이라는 문제가 나왔습니다. 문제를 푸는 과정은 다음과 같았습니다. Qubit 30개가 |0>, |1>, |+>, |-> 4개 중 하나의 state로 존재합니다. 각 qubit마다 여분의 빈 2개의 qubit이 주어지는데, quantum teleportation과 probabilistic quantum cloning을 통해서 이 stage를 통과할 수 있었습니다. (자세한 설명은 이 글의 주제가 아니라서 생략하겠습니다.) Qubit 30개를 초기화할 때 Python random 모듈의 random.getrandbits(30)을 사용합니다. 한 번 1번 stage를 성공하면 이 값들을 수많이 받아올 수 있습니다. 이 값들을 모은 뒤 다음 random.getrandbits(30)을...
-
RBTree's profile image
RBTree
March 21, 2021
Solving Univariate Polynomial over Finite Field
서론 최근 finite field 위에서는 univariate polynomial을 빠르게 풀 수 있다는 소프트웨어 멤버십 노규민 님의 말씀을 들었습니다. 일반적인 합성수 modulus 위에서 Coppersmith method 등을 통해서 작은 값을 가지는 해를 구하는 방법에 대해서만 접해보았기 때문에, 이 방법에 흥미를 느끼고 한 번 정리해보게 되었습니다. 본론 찾아보니 해를 구하는 것은 Polynomial factorization과 밀접한 관련이 있어서, 유명한 Polynomial factorization 알고리즘인 Cantor–Zassenhaus algorithm을 알아보고, 이를 바탕으로 해를 구하는 방법에 대해서 알아보려고 합니다. Cantor–Zassenhaus algorithm Cantor–Zassenhaus algorithm의 메인 아이디어는 equal-degree factorization,...
-
RBTree's profile image
RBTree
February 20, 2021
Gröbner basis
서론 최근 다변수 Coppersmith Method와 관련해 살펴보면서 Gröbner basis, 한국어로는 그뢰브너 기저에 대해서 접하게 되었습니다. 다변수 Coppersmith Method의 과정을 간략하게 설명하자면 다음과 같습니다. 변수 $x_1, x_2, \dots, x_k$에 대한 어떤 modular equation $f(x_1, x_2, \dots, x_k) \equiv 0 \pmod n$을 풀고 싶다. 단, $x_1, x_2, \dots, x_k$는 $n$에 비해서 매우 작다. Howgrave-Graham Theorem과 LLL algorithm을 적용해 $g_1(x_1, x_2, \dots, x_k) = 0, g_2(x_1, x_2, \dots, x_k) = 0, \cdots, g_l(x_1, x_2, \dots, x_k) = 0$...
-
RBTree's profile image
RBTree
January 22, 2021
rth Root Extraction
서론 이번에 CTF 문제를 풀면서 한 가지 특이한 문제를 보게 되었습니다. 문제의 핵심 부분은 다음과 같았습니다. 소수 $p$와 $\gcd(p-1,r)\neq1$인 $r$에 대해서 $m^r\text{mod}\ p$가 있을 때 $m$을 구할 수 있는가? 일반적으로 $\gcd(p-1,r)=1$이라면 $p-1$에 대한 $r$의 역수 $r^{-1}$을 구한 뒤 $(m^r)^{r^{-1}}$을 계산하면 $m$을 구할 수 있습니다. 하지만 그렇지 않은 경우에 대해서는 본 적이 없었기 때문에 검색하는데 시간을 꽤 들이게 되었습니다. 저는 한 논문을 보고 구현했지만, 일반적으로 Adleman-Manders-Miller Root Extraction이라는 Method를 사용한다는 것을 CTF가 끝난 뒤 알게 되었습니다....
-
RBTree's profile image
RBTree
November 22, 2020
Sudoku and Nonogram with z3
서론 이전에 z3와 Boolector를 비교하는 글을 올린 적이 있습니다. (Link) 그런데 정작 z3에 대해서 글이 잘 없어서, 이번에 z3로 퍼즐을 푸는 글을 작성해보게 되었습니다. 스도쿠는 이미 충분히 유명하고, 노노그램은 네모네모 로직이나 피크로스 등을 통해서 많은 분들이 알고 계신 퍼즐이기 때문에 고르게 되었습니다. 이번 글에서는 스도쿠랑 노노그램의 솔버를 하나씩 설명해가면서 작성해보려고 합니다. 본론 Sudoku 스도쿠는 9x9개의 정수를 맞추는 퍼즐 게임입니다. 정수는 모두 1부터 9로 구성되며, 9x9개의 정수 중 몇 개의 값이 고정되어 있습니다. Wikipedia에 있는 sudoku...
-
RBTree's profile image
RBTree
October 23, 2020
SVP and CVP
서론 이번에 N1CTF에 Super Guesser 팀으로 참전해서 4등을 차지했습니다. (ctftime) 한국의 강력한 crypto hacker rkm0959님과 함께 할 수 있는 좋은 자리였는데요, N1CTF에 나온 한 문제가 SVP(Shortest Vector Problem)과 CVP(Closest Vector Problem)에 대해서 다루기 좋아서 이번에 이렇게 글을 작성하게 되었습니다. 본론 Lattice 우선 SVP와 CVP에 대해서 살펴보기 전에 Lattice에 대해서 알아봐야 합니다. Lattice는 이름에서 알 수 있듯이 격자 형태를 나타내는 수학적 개념입니다. Lattice는 서로 independent한 vector ${v_1, v_2, \ldots v_n}$이 있을 때 다음과 같은 집합을 의미합니다....
-
RBTree's profile image
RBTree
September 20, 2020
포카전/카포전 2020 해킹 문제 출제
서론 올해 정식 명칭은 포카전이기 때문에, 중립성을 위해 포카전/카포전으로 쓰겠습니다. 근 몇 년 간 포카전/카포전 해킹을 LeaveCat이라는 팀에서 출제하고 있습니다. 개인적으로 포항공대 PLUS의 후배들이 제 문제를 푸는 모습을 한 번 쯤 구경해보고 싶었기 때문에 이번에 LeaveCat의 일종의 멤버가 되어 처음으로 포카전/카포전 해킹 출제를 하게 되었습니다. 본래 과제로 최근에 개발하고 있던 웹사이트의 이야기를 이번 글에서 하려고 했지만, 출제진이 된 것이 일주일 전이었는데도 짧은 기간 동안 꽤 많은 시간을 투자해서 나름의 좋은 문제를 만들었다는 소기의 성과(?)를 얻었기...
-
RBTree's profile image
RBTree
August 19, 2020
Understanding CRC
서론 작년 중순, 한 CTF에서 CRC와 관련된 문제가 하나 나왔습니다. 문제의 요지인 즉슨, flag{x}의 CRC 값이 다시 x가 나오게 하는 x를 구하는 것이었습니다. 이 과정에서 CRC의 특성에 대해서 이해하고 있는 사람이 별로 없다는 것을 알게 되었습니다. 또한 네트워크 수업에서도 Error code를 소개하는 자리에서 CRC가 나왔지만, CRC를 구하는 방법에 대해서만 알려줄 뿐 CRC가 어떠한 특성을 가지고 있는지는 알려주지 않았습니다. 최근에도 CRC에 대한 CTF 문제가 나오고 있고, 저도 CRC에 대해서 헷갈리던 부분이 있어서 이번에 한 번 정리하게...
-
RBTree's profile image
RBTree
July 19, 2020
RSA Puzzles
서론 RSA는 공개키 암호의 일종으로, 공개키를 통해 평문을 암호화할 수 있으며 비밀키를 통해 암호문을 복호화할 수 있습니다. 이 때 비밀키로부터 공개키를 구할 수는 있지만, 공개키로부터 비밀키를 구하기는 어렵다는 비대칭적 특징을 지닙니다. 일반적으로 RSA에 대한 공격이라고 한다면 공개키만을 갖고 있는 상황에서 비밀키를 구할 수 있는 방법을 의미하곤 합니다. 예를 들어 RSA는 공개키 $(e, N)$과 비밀키 $(d, N)$으로 구성되는데, $N$를 소인수분해해 $N$을 이루는 두 소수 $p, q\ (N = pq)$를 구하거나 암호문으로부터 비밀키의 값을 모르는 상태로 평문...
-
RBTree's profile image
RBTree
June 19, 2020
SMT Solver in CTF - z3 vs Boolector
서론 SMT (Satisfiability modulo theories) Solver는 CTF에서 빠질 수 없는 존재입니다. SMT Solver가 무엇인지 구체적으로 설명하기 보다는, 다음 z3py 예시를 보는 것이 더 직관적일 것입니다. (Link) x = Int('x') y = Int('y') s = Solver() print s s.add(x > 10, y == x + 2) print s print "Solving constraints in the solver s ..." print s.check() print "Create a new scope..." s.push() s.add(y < 11) print s print "Solving updated set of constraints..." print...
-
RBTree's profile image
RBTree
May 19, 2020
Anomalous Elliptic Curves
서론 저번 글에 이어서 이번에는 데프콘 CTF의 예선을 진행하면서 anomalous elliptic curve에 대해서 공부하게 되었습니다. 본래 CryptoHack[1] 에서 anomalous elliptic curve와 그 취약점에 공부한 바가 있지만, 예선에 나온 문제는 CryptoHack에서 공부했던 공격에 취약하지 않은 anomalous elliptic curve를 구하는 문제였습니다. 어떤 문제가 나왔었는지 하나씩 살펴봅시다. 본론 Anomalous Elliptic Curve Anomalous elliptic curve는 곡선이 $F_p$ 위에서 정의될 때 order가 $p$ 인 곡선을 의미합니다. 타원 곡선을 정의를 하게 되면 그 곡선 상에 존재할 수 있는 점의 개수가 정해지는데,...
-
RBTree's profile image
RBTree
April 18, 2020
Singular Elliptic Curves
서론 최근 타원 곡선에 대해서 공부하면서 피상적으로 이해하던 부분을 좀 더 깊이 이해하는 단계에 들어서고 있습니다. 특히 수학에 대해서 배우는 것은 좋아하지만 고등 수학 위로 배운 것이 없어, 많은 재미를 느끼고 있습니다. 그러면서 해소된 궁금점은 바로 “Discriminant가 왜 0이면 안 되는 것일까?” 였습니다. 타원 곡선에 대한 Wikipedia article 을 살펴보면, $y^2 = x^3 + ax + b$ 꼴의 short Weierstrass equation에 대해서 Discriminant $\Delta = -16(4a^3 + 27b^2)$ 가 0이 아니여야 한다는 조건을 달고 있습니다....
-
RBTree's profile image
RBTree
March 19, 2020
AntiVirus Oracle
서론 CONFidence CTF 2020 Teaser라는 대회에서 Angry Defender라는 문제가 나왔습니다. 해당 문제는 Windows Defender의 특성을 이용해서 문제의 답에 해당하는 Flag를 얻어내는 문제었는데, 이 방법이 흥미로워서 이번에 공유하게 되었습니다. 본론 AV Oracle이란? 일반적으로 보안에서 Oracle이라는 이름이 붙은 공격들은 서버가 원하는 정보를 알고 있고 서버와 Interactive하게 통신이 가능할 때 해당 정보의 일부를 유출시킬 수 있는 공격들입니다. 대표적으로 Padding oracle attack과 RSA LSB oracle attack이 있습니다. (공교롭게도 둘은 모두 암호학적 공격이네요.) AV Oracle은 일반적인 컴퓨터 환경에서 사용되는 Antivirus의...
-
RBTree's profile image
RBTree
February 19, 2020
How to build WebAssembly app with Rust
서론 작년에 마작에서 현재 들고 있는 패의 점수 기대치를 계산하는 웹 사이트를 제작을 하려고 하고 있었는데, 다음과 같은 문제에 부딪혔습니다. 가능하면 클라이언트 사이드에서 패의 정보를 입력하고, 해당 패의 점수 기대치를 클라이언트에서 계산하게 하고 싶다. 하지만 웹에서 클라이언트 사이드에서 계산하는 선택지는 거의 JavaScript 뿐이다. JavaScript를 사용할 줄은 알지만, 굳이 개발하면서 JS를 쓰고 싶지는 않다. 대안으로 TypeScript가 있지만, 그리고 JS보다 훨씬 낫지만, 역시 마음에 들지는 않는다. 그래서 더 생각해본 결과, 클라이언트 사이드에서 계산하는 것을 포기하고 Python +...
-
RBTree's profile image
RBTree
December 15, 2019
Forgery Attack on ElGamal Signatures
서론 최근에 한 문제에 대한 질문을 받았습니다. FuzzyLand라는 사이트의 WebShop 2.0 이라는 문제로, ElGamal signature 에 대한 공격을 요구하는 문제였습니다. 문제를 풀다보니 아이디어가 흥미로워서 공유하게 되었습니다. 본론 ElGamal Signatures ElGamal signature는 RSA signature와 비슷하게 discrete logarithm의 어려움에 바탕을 둔 signature scheme입니다. ElGamal signature는 다음과 같은 방식으로 돌아갑니다. 파라미터 및 생성 어떤 $N$-bit 소수 $p$를 고릅니다. 그리고 Hash function $H$를 고릅니다. 2부터 $p-1$ 사이의 어떤 수 $g$를 고릅니다. 이 수를 generator라고 부릅니다. 이 때 generator라고 불리는...
-
RBTree's profile image
RBTree
November 15, 2019
On Factoring Given Any Bits
서론 이번에 Belluminar 라고 하는 대회에 참가했습니다. 해당 대회는 각 팀마다 문제를 두 개 씩 출제하고, 대회 시간 동안 문제를 풀면서 점수를 겨루는 방식으로 구성되어 있습니다. 저는 이번에 공부했던 테크닉을 문제로 내기로 결심해서 작성을 했는데, 생각보다 만족스러운 퀄리티로 문제가 나오지 않아 아쉬웠습니다. 본래라면 공부한 내용을 포스트로 바로 쓰겠지만, 제 이름이나 아이디를 검색해 그대로 솔버에 사용하는 것을 원치 않았기 때문에 이러한 소셜 해킹을 방지하기 위해서 이제서야 포스팅을 하게 되었습니다. 이번 포스트는 제가 냈던 문제의 근간이 되는...
-
RBTree's profile image
RBTree
October 20, 2019
Smooth number and Factorization
서론 이번 HITCON CTF 2019 Quals에서 안타깝게 14등으로 본선을 진출하지 못하게 되었습니다. 결과 링크 아쉬운 부분은 푼 팀이 적은 암호학 문제들을 풀지 못했다는 건데, 그 중 한 문제가 소인수분해와 관련이 있어 이번 포스팅을 작성하게 되었습니다. RSA 위에서 말한 문제는 Lost Key Again이라는, RSA와 관련된 문제입니다. RSA에 대해서 간편하게 살펴보자면, $a \equiv b (\mathbb{mod}\ c)$는 $a$를 $c$로 나눈 나머지와 $b$를 $c$로 나눈 나머지가 같다는 뜻으로 이해할 수 있습니다. 편의상 $a$를 $b$로 나눈 나머지를 $a (\mathbb{mod}\ b)$로...
-
RBTree's profile image
RBTree
August 19, 2019
Shellcoding and Bitflip Conjecture
서론 이번에 DEF CON CTF 2019에 팀 SeoulPlusBadass로 다녀왔습니다. 결과 링크 대회의 대부분의 문제가 프로그램의 취약점을 찾아서 익스플로잇하는 Pwnable 문제였는데, 그렇지 않은 문제는 ropship, DOOOM, bitflip conjecture 세 문제였습니다. 그 중에서도 Bitflip Conjecture는 흥미로운 Shellcoding 문제여서 이번에 공유하고자 합니다. Bitflip Conjecture Bitflip Conjecture는 X64 Assembly로 작성된 Binary를 전송하는 문제입니다. 자세한 것은 문제에 접속하면 나오는 메시지를 살펴봅시다: =============================================================================== Definition: A snippet of assembly code is `N-Flip Resistant` if its output remains constant (i.e., it produces the...
-
RBTree's profile image
RBTree
July 21, 2019
Digital Signature and Nonce Reuse
서론 Digital signature, 혹은 디지털 서명은 컴퓨터 네트워크에서 빠져서는 안 될 중요한 요소 중 하나이다. 수신자는 발신자로부터 메시지를 수신한 뒤, 메시지에 같이 붙어 온 digital signature를 검증해 해당 메시지가 정말로 발신자로부터 온 것인지 확인할 수 있다. 이를 보장할 수 있는 근간에는 다양한 수학 이론이 깔려있고, 이 중 중심이 되는 것은 정수론과 타원 곡선이라고 할 수 있다. 오늘 이 포스트에서는 이 중에서도 가장 쉽게 이해할 수 있고 널리 쓰이고 있는 DSA에 대해서 알아보고, nonce reuse가 왜...