-
New Updates on Proximity Testing with Logarithmic Randomness
소개 이전 글에서, “Proximity Testing with Logarithmic Randomness”라는 논문을 소개했습니다. 이 논문을 읽은 당시에 제가 논문에 있었던 증명의 작은 오류를 찾아 이를 수정하는데 기여하기도 했으며, 그 내용도 이전 글에 소개되어 있습니다. 1월 이후, 해당 논문과 관련된 여러 새로운 발견이 이루어졌습니다. 이 글에서는 1월 이후 Proximity Testing에 대한 추가적인 발전에 대해서 다룹니다. 복습 이전 논문에서 다룬 핵심적인 정리는 다음과 같습니다. For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots,...
-
Polymath: Groth16 is Not The Limit
소개 ZKP의 성능을 측정하는 요소에는 여러 가지가 있습니다. Prover와 Verifier의 입장에서 생각해보면, 가장 중요한 것은 아무래도 Prover가 proof를 생성하는데 걸리는 시간 및 리소스 Verifier가 proof를 검증하는데 걸리는 시간 및 리소스 입니다. 하지만, Recursive ZKP나 최종적으로 Verifier가 위치하는 곳이 어디인지 등을 생각해보면, 시간 및 리소스만큼이나 중요한 것이 바로 Proof의 크기, 즉 proof size임을 알 수 있습니다. Proof의 크기 자체가 크면 blockchain 위에 올리는 데 비용이 커지며, 동시에 Recursive ZKP를 하는 overhead도 커지기 때문입니다. 특히, blockchain 위에...
-
STIR: Reed-Solomon Proximity Testing with Fewer Queries
소개 이 글은 https://eprint.iacr.org/2024/390.pdf에 대해서 설명합니다. STIR의 목표는, Reed-Solomon Code와의 Proximity Testing을 최소한의 query로 하는 것입니다. 동일한 문제를 푸는 알고리즘 중 가장 잘 알려진 FRI는, degree $d$ 문제를 $\lambda$-bit security를 갖게 해결하기 위하여 query를 $\mathcal{O}(\lambda \log d)$개 사용합니다. STIR는, 그에 비해 $\mathcal{O}(\log d + \lambda \cdot \log \log d)$만큼의 query를 사용하여, 더 적은 query를 사용하게 됩니다. query의 개수는 STARK proof의 크기와 연결되어 있기 때문에, FRI를 STIR로 대체하여 STARK의 proof size 및 verifier time을 줄일 수...
-
Anatomy of a zkVM: Looking at SP1
소개 최근 Succinct Labs의 zkVM인 SP1을 자세히 볼 기회가 생겼습니다. zkVM은 ZKP를 통해서 하나의 프로그램 자체의 execution을 통째로 증명하는 것을 목표로 하고 있습니다. SP1의 경우에서는 RISC-V 프로그램을 대상으로 하고 있어, Rust을 구현한 후 컴파일하면 SP1이 바로 증명을 할 수 있게 됩니다. 이를 통해서, 복잡한 ZKP 서킷을 직접 작성하는 대신 Rust로 코드를 짜고, 이를 SP1으로 덮어서 ZKP를 사용할 수 있게 됩니다. 즉, zkEVM을 구현하기 위해서 EVM의 Rust 구현체를 가져다 쓰기만 하면 됩니다. 이 글에서는 SP1의 구조에...
-
Minimizing Foreign Arithmetic in ZKP Circuits
https://eprint.iacr.org/2024/265.pdf 논문에 대해 다룹니다. 소개 ZKP를 사용하는 과정에서 가장 핵심적인 부분은 결국 $\mathbb{F}_p$ 위의 기본적인 연산들을 통해서 프로젝트 스펙에서 필요로 하는 constraint들을 표현하는 것에 있습니다. 하지만 $\mathbb{F}_p$ 위에서 모든 것을 표현하는 것이 쉽지만은 않습니다. 대표적인 사례는 바로 foreign field arithmetic인데, 이는 $\mathbb{F}_p$를 표현할 수 있는 ZKP system 위에서 $\mathbb{F}_q$의 연산을 증명하는 것을 의미합니다. 예를 들어, BN254 위의 PLONK를 하고 있다고 치면 BN254의 scalar field가 ZKP 상으로 native 하게 지원되지만, 여기서 SECP256K1 ECDSA verification을 하고 싶다면...
-
Insights from and on Taxonomy of ZKP Vulnerabilities
올해 4월 초, ZKP 관련 최대 컨퍼런스 중 하나인 zkSummit11에서 ZKP 보안과 관련된 발표를 진행할 수 있었습니다. 이번 글에서는 발표 내용에 대한 간략한 설명을 합니다. ZKP 보안에 대한 업계의 이해도는 2022년부터 꾸준히 증가해왔지만, 아직도 ZKP 보안 판에는 여러 문제가 있습니다. 가장 큰 문제 중 하나는 사람이 부족하다는 것인데, 이에 대한 해답으로는 크게 두 가지를 생각할 수 있습니다. 암호를 잘 하는 사람에게 보안의 컨텍스트를 가르쳐 ZKP 보안을 소개하는 것 블록체인 보안을 하는 사람에게 암호의 컨텍스트를 가르쳐...
-
PIOP Improvements for ZeroCheck
Circle STARK Part 2를 하기 이전에, 최근 읽은 논문 중 간단하면서도 강력한 게 하나 있어서 이를 공유합니다. 이번 글에서는 https://eprint.iacr.org/2024/108 의 내용을 정리합니다. Zero Check Multivariate Polynomial을 기반으로 한 proof system들은, 일반적으로 boolean hypercube $H_n$ 위에서 어떤 함수 $C(x)$가 전부 0으로 계산됨을 증명하는 것으로 문제를 환원시킵니다. 결국 최종적으로 \[C(x) = 0 \quad \forall x \in H_n\] 를 보여야 하는데, 이를 위해서 verifier는 랜덤한 $\alpha$를 정한다음 \[\sum_{x \in H_n} \tilde{eq}(x, \alpha) \cdot C(x) = 0\] 을...
-
Circle STARK Part 1: Circle FFT
ZKP를 위한 Underlying Field $\mathbb{F}_p$ ZKP의 패러다임을 다루거나, ZKP를 본격적으로 분류를 하게 되면 그에 대한 가능한 기준으로는 여러가지가 있습니다. 하지만 요즘 대부분이 생각하는 방식은 (수학적으로 엄밀하거나 완전하지는 않아도) $\mathbb{F}_p$ 위에서 ZKP가 작동을 할 때 $p$가 어떤 값을 가지냐를 가지고 많이 논의를 합니다. $p$가 256 bit 정도를 가지는 경우 $p$가 64 bit 정도거나 32 bit 정도로 작은 경우 $p$가 소수가 아니라 256 bit 정도의 2의 거듭제곱인 경우 여기에 추가적으로 $p$가 NTT를 지원한다던가, 타원곡선의 크기여야 한다던가 하는...
-
Garbled Circuit and Functional Encryption
Introduction 이 글에서는 Multi-party computation(MPC)에서 사용되는 Garbled Circuit과 Oblivious Transfer에 대해 알아볼 것입니다. 그 뒤에는 public key encryption을 확장한 개념인 Functional Encryption이라는 개념을 소개할 것입니다. 배경지식이 크게 필요하지 않도록 작성했기 때문에, 암호학에 관심이 있는 독자들에게 흥미를 줄 수 있기를 바랍니다. Garbled Circuit Garbled Circuit(GC) 는 두 사람 $Alice$와 $Bob$이 각각 input $x$와 $y$를 갖고 있을 때, 서로에게 자신의 input을 노출하지 않고 $f(x,y)$를 계산하는 two-party computation을 위해 고안되었습니다. 이는 필자의 직전 포스트인 two-party communication 모델과 동일하지만,...
-
Proximity Testing with Logarithmic Randomness
Code-Based PCS의 복습 Linear code $V$에 대하여, 벡터 $x$와 $V$의 거리를 \[d(x, V) = \lVert x - V \rVert_0 = \min_{y \in V} (\lVert x - y \rVert_0)\] 또, 행렬 $X$와 $V$의 거리를 각 column이 전부 $V$의 원소인 행렬 $Y$에 대하여, $X - Y$가 갖는 non-zero row의 최소 개수라고 정의한다. 이 거리의 정의를 기반으로, $q$-close와 $q$-far를 정의할 수 있다. 이때, code-based PCS의 안정성을 증명하는 가장 핵심적인 결과는 \[\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le...
-
HE Sanitization - Washing Machine
Introduction 지금까지는 주로 동형암호(Homomorphic Encryption)의 scheme들에 관해 글을 써왔는데, 이번 글에서는 동형암호와 관련돼 있는 연구 분야 중 하나인 Circuit Privacy에 관련된 Sanitization에 관련된 글을 써보려고 합니다. 이 글에서는 Ducas - Stehlé Washing machine에 대해서 중점적으로 설명하도록 하겠습니다. 원 논문은 이 링크에서 확인하실 수 있습니다. Backgrounds Homomorphic Encryption 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 지금까지 쓴 글들에 설명이 자세하게 나와 있으니, 자세한 설명은 생략하겠습니다. Bootstrapping 동형암호들의 경우 error를 필수적으로 가지게...
-
Secure Matrix Multiplication with Homomorphic Encryption - 1
Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...
-
Folding Part 2: HyperNova
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 HyperNova에 대해서 다룬다. https://eprint.iacr.org/2023/573.pdf Preliminaries Incremental Verifiable Computation Incrementally Verifiable Computation은 Generator $\mathcal{G}(1^\lambda) \rightarrow pp$: security parameter $\lambda$를 받고 public parameter $pp$를 만든다 Encoder $\mathcal{K}(pp, F) \rightarrow (pk, vk)$: public parameter $pp$와 반복할 함수 $F$를 받고, prover key 및 verifier key $pk, vk$를 만든다 Prover $\mathcal{P}(pk, (i, z_0, z_i), \omega_i, \Pi_i) \rightarrow \Pi_{i+1}$은 결과 $z_i$와 이에 대한 IVC proof $\Pi_i$를 받고, $z_{i+1} =...
-
Folding Part 1: ProtoStar
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 ProtoStar에 대해서 다룹니다. https://eprint.iacr.org/2023/620.pdf Folding이란 무엇이며, ProtoStar의 목표는 무엇인가 Folding은, input 자체만 제외하면 증명하고자 하는 연산의 형태는 동일한 두 ZKP instance를 하나의 instance로 fold 하는 테크닉으로, 올해 초부터 더욱 본격적인 관심을 받게된 테크닉입니다. 기존에 IVC를 (Incrementally Verifiable Computation) 얻으려면 recursive SNARKs, 즉 이전 SNARK의 verification 과정을 다시 SNARK로 올려 계산하는 방식으로 구현했다면, 이제는 SNARK를 accumulate 하여 접어가면서 쌓아올린 후 최종 accumulator를 가지고 전체...
-
Multi Key Homomorphic Encryption - 3
Introduction 저번 글에서, 이어서, MKHE에 대한 설명을 하겠습니다. 저번 글을 읽고 오시는 것이 이해하기 편할 것 같습니다. Notation의 경우 저번 글에서 사용한 것을 그대로 가져다가 사용하겠습니다. 이 글에서는 저번 글에서 설명을 다 하지 못한 Multiplication에 대한 설명을 하도록 하겠습니다. Backgrounds MKHE의 경우 저번 글에서 기준으로 한 논문에 이어서 추가 연구가 진행됐습니다. 다른 연산의 경우 거의 바뀐 것이 없습니다. 다만, Multiplication의 경우, 현재는 저 논문보다 더 개선된 방식으로 key를 생성해서 evaluation을 수행합니다. 새로 사용하는 방식이 이해도...
-
Multilinear PCS from Univariate PCS
저번 포스팅에서는 Multilinear Polynomial에 대한 linear-time commitment 중 하나인 Brakedown에 대해서 알아보았습니다. Sumcheck 관련 기법들이 떠오르면서, Multilinear Polynomial의 commitment에 대한 기법들이 더욱 중요해졌습니다. 그 방법에는 Brakedown 및 이를 강화하는 Orion, Orion+ 뿐만 아니라 Dory, Hyrax 등 다른 기법도 존재합니다. 특히, Univariate Polynomial에 대한 Commitment를 기반으로 Multilinear Polynomial에 대한 Commitment 기법을 유도하는 기법들도 여러 가지 존재합니다. 여기서는 그 방법인 Gemini와 Zeromorph에 대해서 알아보도록 하겠습니다. 이 포스팅에 대응되는 논문은 아래와 같습니다. https://eprint.iacr.org/2022/420.pdf Section 5 https://eprint.iacr.org/2023/917 KZG +...
-
Multi Key Homomorphic Encryption - 2
Introduction 저번 글에서, 이어서, 이 논문의 내용을 기준으로 하여, MKHE에 대한 설명을 이어서 진행합니다. 따라서, 저번 글을 읽고 오시는 것이 여러 면에서 도움이 됩니다. 아래에 정리해둔 Notation에 잘 모르겠다는 부분이 있다면, 저번 글과 BFV를 설명한 글들을 읽고 오시는 것을 추천드립니다. Backgrounds Notation 이 글에서는 논문에서 사용한 Notation을 거의 따릅니다. 저번 글에도 썼지만, 다시 정리하면 다음과 같습니다. 먼저, $\textbf{u}, \textbf{v}$처럼 굵은 소문자들은 vector를 나타냅니다. 그리고, $\langle \textbf{u} , \textbf{v} \rangle$는 vector의 innner product를 나타냅니다. real number...
-
Brakedown Overview
이 내용은 https://eprint.iacr.org/2021/1043 의 요약입니다. 이 논문의 목표는 Linear Code를 기반으로 한 Linear-Time PCS를 준비하고 이를 Spartan에 적용하여 Linear-Time Field-Agnostic SNARK를 얻는 것입니다. Spartan 계열 테크닉이 주목을 받는 시점에서 읽기 좋은 논문이라고 생각됩니다. 다만, 길이의 문제로 각종 증명들은 생략하도록 하겠습니다. Linear Time Polynomial Commitment Multilinear polynomial을 기준으로 생각하면, $g$의 Lagrange basis에서 coefficient를 $u$라고 했을 때 \[g(r) = \sum_i u_i \cdot \left(\prod_{k} (r_k i_k + (1 - r_k)(1 - i_k)) \right)\] 라고 쓸 수 있고, 대괄호...
-
Multi Key Homomorphic Encryption - 1
Introduction 저번 글에서, Multi Party HE에 대해 간단하게 설명을 했습니다. 이번 글에서는 Multi Key HE에 대해서 간단히 설명하는 글을 쓰려고 합니다. 이번에 기준으로 한 논문은 여기에서 보실 수 있으며, 저자들의 이름을 따서 CDKS scheme이라고도 불립니다. 논문에서는 기본적인 Multi Key HE에 대한 설계를 바탕으로, BFV, CKKS에 적용시켜 Multi Key BFV, Multi Key CKKS 역시 설명하고 있으나, 이번 글에서는 아직 CKKS를 자세히 설명한 적도 없고, 적용도 그렇게 어렵지 않으므로, Multi Key HE의 구조에 대해서만 설명하려고 합니다. 저번...
-
Multi Party Homomorphic Encryption
Introduction Homomorphic Encryption (HE)는 secret key 가 없어도, ciphertext끼리의 evaluation이 가능한 scheme들으로, cloud computing등에 적합한 model이기 때문에 많은 관심을 받고 있습니다. Gentry가 처음으로 BGV를 제안안 이후, BFV, CKKS, TFHE 등의 scheme들이 제안됐습니다. 하지만 지금까지 제안되고, 널리 사용되는 scheme들에는 한 가지 공통점이 있는데, 그것은 하나의 고정된 secret key를 가진다는 것입니다. 얼핏 보면 당연할 수 있는 말이지만, 이는 HE scheme들이 가진 단점이기도 합니다. cloud computing 같은 걸 하면 여러 개의 party에 대해 data를 주고 받고, 해야 하는데,...
-
Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
이 내용은 https://eprint.iacr.org/2023/1025.pdf 의 요약입니다. ZK Friendly Hash Function의 필요성 해시함수는 굉장히 많은 곳에서 사용되고 있습니다. 그런만큼 ZKP 상에서도 해시함수의 계산에 대한 증명을 하게 될 필요가 상당히 많습니다. 그런데 일반적인 해시함수는 일반적인 컴퓨팅 환경에서 빠르게 작동하는 것을 목표로 하기 때문에, 비트 연산 등을 많이 활용합니다. 이는 비트 연산을 다루는 비용이 큰 ZKP 상에서는 큰 문제로 작용합니다. 이에 따라, ZKP 상에서 비용이 적은, 즉 적은 constraint로 증명을 할 수 있는 해시함수를 만드는 것이 필요해졌습니다. 또한, ZKP...
-
BFV scheme에 대한 소개 - 5
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV Multiplication을 어떻게 처리하는지에 대해서 설명을 했습니다. 이번 글에서는 저번 글에서 다 하지 못한 설명을 마무리하도록 하겠습니다. Backgrounds 이번 글은 기본적으로 저번 글에서 설명한 내용을 이어서 하는 것이기 때문에, 따로 Background는 필요하지 않으나, 저번 글의 내용을 이해하는 것이 중요합니다. 특히 FastBConv 함수의 정의에 대해서 잘 기억해 주세요. Step 4. 앞의 step 3의 결과를 다시 불러와 봅시다. \[FastRNSFloor_q(t \cdot ct[j], B_{sk})...
-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
BFV scheme에 대한 소개 - 4
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV decryption을 어떻게 처리하는지에 대해서 설명했습니다. 이번 글에서는 multiplication을 어떻게 처리하는지에 대해서 설명하도록 하겠습니다. Backgrounds 이번에 설명할 연산은 RNS module의 BFV scheme에서 multiplication 입니다. 얼핏 생각했을 때, decryption에서 rounding을 correction하는 법도 이미 구했고, Multiplication 역시 비슷하게 하면 되지 않을까? 라는 생각을 할 수 있습니다. NTT등을 사용하면 속도도 빠르게 나올 것입니다. 하지만, 그냥 곱하는 방법을 쓰면 문제가 있는데, 바로 Noise Growth가...
-
ZKP and Block Hash Oracles
이 내용은 ZK-School에서 멘토링한 자료에 기반합니다. ZKP의 목표 영지식 증명, Zero Knowledge Proof는 기본적으로 일련의 계산이 제대로 되었음을 간단하게 증명하는 것을 목표로 하고 있습니다. Zero Knowledge라는 부분도 중요하지만, 가장 핵심은 보통 Proof에 있습니다. 일단 Proof가 되어야지 Zero Knowledge를 이야기를 하겠죠? 그래서 대강 압축을 하자면, Alice가 $f(x)$라는 값을 알고 싶은데 이를 직접 계산하기에는 컴퓨팅 파워가 부족하다면, 그 컴퓨팅 파워가 있는 Bob이 $f(x)$를 직접 계산해서 $y = f(x)$라는 사실을 알아내고, Alice에게 단순히 $y$의 값을 넘기는 것이 아니라,...
-
GKR protocol and Linear Prover
Preliminaries Multilinear Extension $f(x_1, \cdots ,x_v) = \lbrace 0,1 \rbrace^v \rightarrow \mathbb{F}$ 에 대해, $f$의 domain $\lbrace 0,1 \rbrace^v$ 내에서 $f(x_1, \cdots ,x_v) = g(x_1, \cdots ,x_v)$가 성립하는 multivariable polynomial $\overline{f}$가 각각의 variable $x_1, \cdots, x_v$에 대해 linear일 때 $\overline{f}$를 $f$의 multilinear extension이라 합니다. How to build Multilinear Extension \[\overline{f}(x_1, \cdots, x_v) = \sum_{(a_1, \cdots, a_v) \in \{0,1\}^v} f(a_1, \cdots, a_v) \prod_{i=1}^v (a_ix_i + (1-a_i)(1-x_i))\] 위 식에서 $x_1, \cdots, x_v \in {0,1}^v$ 인 경우 모든...
-
BFV scheme에 대한 소개 - 3
Introduction 지금까지 BFV Scheme에 관한 설명글과, BFV scheme의 practical한 구현을 위해서 RNS module이라는 걸 사용한다는 것 그리고, RNS module에서 operations들이 기본적으로 어떻게 돌아가는지에 대해 설명하는 글을 썼습니다. 이번 글에서는 RNS module에서 구현하기 까다로운 연산들을 어떻게 처리하는지에 대해 설명하겠습니다. Backgrounds 저번 글에 좀 더 자세히 설명하고 있지만, Background를 한 번 더 짚고 넘어가겠습니다. RNS module은 널리 알려진 CRT(Chinese Remainder Theorem)에 기반하여 큰 범위의 수를 작은 수 여러 개로 표현하는 방식입니다. Homomorphic Encryption은 보안상의 이유 때문에 대부분...
-
BFV scheme에 대한 소개 - 2
Introduction 저번 글에서 BFV scheme에 대해서 소개하는 글을 썼습니다. 이 글에선 저번 글에서 사용한 notation들을 따와서 설명을 할 것이기 때문에, 이전 글을 다시 한번 읽고 오시면 이해가 더 쉬울 것입니다. 이번 글에서는 BFV scheme의 실제적인 구현을 위한 알고리즘들을 좀 더 설명하는 글을 쓰도록 하겠습니다. 이 글에서 사용한 Microsoft SEAL의 코드 구현은 이 글이 쓰여진 시점에서 최신 version의 SEAL(206648d)의 구현을 따릅니다. RNS representation Definition 본격적으로 설명하기에 앞서, RNS representation에 대해 먼저 설명을 하도록 하겠습니다. RNS(Residue Number...
-
BFV scheme에 대한 소개 - 1
Introduction 저번 글에서 Homomorphic Encryption, 동형암호에 대해서 소개하는 글을 썼습니다. 이번 글부터는 저번 글에서 소개한 여러가지 FHE scheme 중에서, BFV scheme에 대해 설명하는 글을 쓰려고 합니다. 저번 글에 Homomorphic Encryption에 대한 간단한 설명과 특징을 설명했습니다. 이 글에서는 Homomorphic Encryption에 기본 개념에 대해서 알고 있다고 생각하고 설명할 것이기 때문에, 이번 글을 읽기 전에 저번 글을 읽고 오시는 것을 추천드립니다. 이번 글에서는 BFV scheme의 다양한 연산들에 대해서 설명하도록 하겠습니다. Key Generation BFV scheme에서 key 생성을 어떻게 하는지...
-
Isogeny-based cryptography
Introduction 현재 사용되고있는 공개키 암호 시스템은 많은 수가 기본적인 RSA의 변형으로 discrete logarithm problem(이산로그) 또는 integer factorization problem 문제의 어려움을 기반으로 하고 있으며, 타원곡선 상에서의 연산에 기반한 시스템 역시 elliptic-curve discrete logarithm problem(ECDLP)을 기반으로 합니다. 이 3가지 문제들은 모두 양자컴퓨터상에서 Shor’s algorithm으로 빠른 시간에 풀 수 있음이 알려져있기 때문에, 양자컴퓨터가 등장하더라도 그 안전성을 보장할 수 있는 post-quantum cryptography algorithm이 필요하게 되었습니다. NIST(미국 국립표준기술연구소) 에서는 양자컴퓨터의 출현에도 안전한 Post-Quantum Cryptography의 표준화를 위해 여러 알고리즘들을 제출받아서 보안성과...
-
Optimal Ate Pairings, BLS12-381, BN254 알아보기
이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q) = f_{r, P}(Q)^{(q^k - 1) / r}\] 를 얻을 수 있었습니다. 이제 이를 최적화하는 Ate Pairing을 알아봅시다. Lemma \[f_{ab, Q} = f_{a, Q}^b \cdot f_{b, [a]Q}\] 증명: 단순 계산. 어렵지 않습니다. 그러면 특히 $[r]Q = \mathcal{O}$인 경우에는 \[f_{mr, Q} = f_{r, Q}^m\] 가...
-
Homomorphic Encryption에 대한 소개
Introduction 올 한해 크립토랩이라는 스타트업에서 근무할 기회가 있었습니다. 크립토랩은 Homomorphic Encryption, 즉 동형암호 scheme 중 CKKS를 바탕으로 창업한 스타트업입니다. (CKKS scheme을 제안하신 천정희 교수님이 대표입니다.) 회사에서 근무하며 그동안 잘 몰랐던 동형암호에 대해서 배울 기회가 있었습니다. 현재 국내에는 동형암호에 대해 서술하는 자료가 그리 많지 않은 것으로 보여, 동형암호에 대한 소개글을 작성하기로 했습니다. What is Homomophic Encryption? 먼저 동형암호가 무엇인지 간단하게 설명하도록 하겠습니다. 우선 보통의 암호 scheme의 경우 평문(plaintext)와 암호문(ciphertext)의 관계를 최대한 random하게 만드려고 합니다. 평문과 암호문...
-
Pairing 제대로 알아보기
자료: Pairings For Beginners Introduction 이 글에서는 여러 암호학의 분야에서 자주 등장하는 Elliptic Curve Pairing에 대해서 자세하게 알아보겠습니다. 독자 대상은 현대대수학 기본 Elliptic Curve 연산에 대한 기초지식 Elliptic Curve를 기반으로 한 Cryptography에 대한 기초지식 Pairing을 기반으로 한 Cryptography에 대한 기초지식 이 있는 분들입니다. 즉, 이 글에서는 Pairing이 왜 쓸모있는지, 어떻게 사용되는지는 다루지 않고, Pairing이란 무엇이며 어떻게 효율적으로 계산되는지 다룹니다. 최대한 증명을 포함하려고 하나, 지나치게 증명이 어려운 경우에는 따로 알아두면 좋은 사실로 빼겠습니다. A Look at...
-
Sum-Check Protocol and Applications
Introduction 최근 개인적인 사정으로 공부를 제대로 못하다가 정신을 차리고 Thaler의 책을 읽고 있습니다. 그 내용 중 일부분인 Sum-Check Protocol과 이를 활용한 application들에 대해서 짚고 넘어가고자 합니다. 이번 글에서는 다루지 않으나, 최근 등장한 HyperPLONK도 역시 Sum-Check Protocol에 기반하고 있으니, 이를 공부하기 위해서라도 Sum-Check에 대해서 제대로 공부해놓는 것이 좋아보입니다. The Sum-Check Protocol $v$-variate polynomial $g$가 유한체 $\mathbb{F}$ 위에서 정의되었다고 합시다. 목표는 \[H = \sum_{(b_1, \cdots, b_v) \in \{0,1\}^v} g(b_1, \cdots , b_v)\] 가 성립함을 증명하는 것인데, 특히...
-
Polynomial Commitment Scheme from DARK
논문: https://eprint.iacr.org/2019/1229.pdf Introduction 수많은 zkSNARK 체계들은 하나의 커다란 연산 과정을 간단한 게이트들로 구성된 Arithmetic Circuit으로 변환하고, 이에 대한 증명을 다항식들에 대한 항등식을 증명하는 것으로 전환합니다. 결과적으로 다루는 대상들이 다항식이므로, 자연스럽게 Polynomial Commitment라는 암호학 기술이 사용되게 됩니다. 보통 Commitment라고 하면, 값 $x$에 대한 commitment $C$를 계산하는 commit 함수가 있고, 다시 $C$를 알때 이것이 $x$의 commitment임을 증명하는 open 과정이 있습니다. $C$를 다른 값 $y$의 commitment로 open 하지 못하도록 하는 특성을 binding이라 하고, $C$만 봐서는 이것이 $x$의 commitment임을...
-
Isochronous Gaussian Sampling of [HPRR20]
논문은 https://eprint.iacr.org/2019/1411.pdf 입니다. Post Quantum Cryptography and Lattices 지금 사용되고 있는 많은 암호화 체계, 예를 들면 블록체인에서 많이 사용되고 있는 ECDSA/EDDSA나 공개키 암호화를 위해 사용되는 RSA 등은 전부 충분히 강력한 양자컴퓨터가 나오면 더 이상 안전하지 않게 됩니다. 양자컴퓨터가 나오는 미래에 대비하기 위해 NIST는 2010년대 후반부터 양자컴퓨터가 나오더라도 안전한, Post Quantum Cryptography에 (이하 PQC) 대한 표준을 정하기 위한 과정을 밟기 시작했습니다. 여러 과정을 거쳐서 매우 최근 Round 4 발표 및 첫 표준이 등장하게 되었는데, PQC 암호체계를...
-
On the insecurity of ROS
논문은 https://eprint.iacr.org/2020/945.pdf 입니다. 이번 논문을 읽기 위해서는 사전지식이 거의 필요하지 않습니다. What is ROS? ROS란, 다음의 약자를 따서 만든 이름입니다. Random inhomogeneities in a Overdetermined Solvable system of linear equations ROS는 다음과 같이 정의되는 문제입니다. 소수 $p$와 임의의 input을 $\mathbb{F_p}$로 보내는 random oracle $H_{ros}$가 있다고 합시다. 이때, dimension $l$의 ROS 문제는 서로 다른 $\hat{\rho}_i \in \mathbb{F}_p^l$을 각 $1 \le i \le l+1$에 대하여 찾되, $c \in \mathbb{F}_p^l$이 존재하여 \[H_{ros}(\hat{\rho}_i) = \langle \hat{\rho}_i, c \rangle\] 이...
-
Triple DES의 안전성
1. Introduction Triple DES는 DES를 3번 진행하는 암호이고, DES가 낮은 키의 엔트로피(56비트)로 인해 컴퓨터 성능이 발전함에 따라 점차 충분한 안전성을 제공할 수 없게 되자 다음 암호인 AES가 등장하기 전까지 임시로 사용되었습니다. Triple DES는 DES를 서로 다른 키 $K_1, K_2, K_3$에 대해 3번 적용합니다. 즉 키의 길이는 168비트입니다. 이 때 Single DES와의 호환성을 위해 처음 두 번의 DES는 암호화, 세 번째의 DES는 복호화로 둡니다. 또한 경우에 따라 $K_1 = K_3$으로 두어 112비트의 키를 사용하기도 합니다. Triple...
-
Bitslice을 활용한 암호 구현
들어가며 이번 글에서는 1997년 Eli Biham의 “A Fast New DES implementation in Software”에서 다시 환기된 Bitslice 기법에 대해서 작성해보려고 합니다. 이전 1970년대에 사용되던 Bitslice는 워드의 길이를 늘리기 위해서 더 작은 bit 너비에서 구성하는 것이었습니다. 현대에 들어서는 거의 사용되지 않았지만, Eli Biham이 평문을 병렬화하여 DES의 고속구현을 하며 소프트웨어단에서 재사용되기 시작했습니다. 현대의 Bitslice기법은 각 단어를 Bit별로 잘라, 여러 단어의 특정 bit들을 묶어 재지정한 다음 연산을 하는 과정을 의미합니다. 그렇게되면, 재지정된 한 단어는 기존 여러 단어들의 동일한 위치의...
-
Caulk : Lookup Arguments in Sublinear Time
논문은 https://eprint.iacr.org/2022/621 입니다. 선행지식 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf https://www.secmem.org/blog/2022/05/15/KZG-ASVC/ 정확히는, Powers of Tau 및 KZG Commitment 계열 이론, ZK 계열 이론 기초 Membership Proofs in Zero Knowledge 우리의 목표는 집합 $S$가 있을 때, 어떤 $v$가 $v \in S$를 만족한다는 사실을 영지식으로 증명하는 겁니다. 이를 위해서 사용된 대표적인 방법이 두 가지가 있는데, 하나는 Tornado Cash에서 사용하고 있는 것과 같은 Merkle Tree + zkSNARKS입니다. 적당한 hash function을 기반으로 한 Merkle Tree를 만들고, 자신이 갖고 있는 원소가 leaf 중 하나임을 Merkle...
-
Large S-box의 암호학적 성질 및 대수적 공격
1. Introduction 대칭키 암호화 시스템은 선형 연산과 비선형 연산을 반복적으로 적용해 키와 암호문 혹은 평문과 암호문의 관계를 가립니다. 이 때 S-box는 비선형 성질을 제공하는 중요한 역할을 합니다. DES에서는 6비트의 입력을 받아 4비트를 출력하는 S-box가 사용되었고 AES에서는 8비트의 입력을 받아 8비트를 출력하는 S-box가 사용되었습니다. 암호가 안전하기 위해서는 S-box가 편향되지 않고 잘 정의되어야 합니다. 예를 들어 S-box의 차분 성질이나 선형 성질의 편향이 클 경우 이를 이용한 차분 공격 혹은 선형 공격이 가능할 수 있습니다. 직관적으로 생각했을 때...
-
KZG Commitment, Aggregatable Subvector Commitments, Stateless Cryptocurrencies
들어가기 전에 논문 https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf (KZG Commitment, Asiacrypt 2010) https://eprint.iacr.org/2020/527.pdf (eprint) 이 논문의 저자에는 Vitalik Buterin도 있습니다. 선행지식 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 정확히는, Powers of Tau와 Pairing에 대한 기본적인 이해 다항식의 연산에 관한 알고리즘 (FFT 계열) 이 글에서 Security에 대한 부분은 생략하도록 하겠습니다. 필요한 가정과 실제 scheme의 security 증명 사이의 gap이 그렇게 크지 않고, 글에서 다루는 내용이 이미 많기 때문입니다. 이 부분에 대해 궁금한 점이 있는 독자들은 KZG Commitment 논문의 Section 2에 있는 Assumption들과 Appendix C를 참고하시기 바랍니다. 서론...
-
Tweakable block ciphers
1. Introduction 안녕하세요, 이번 글에서는 Moses Liskov, Ronald L. Rivest and David Wagner가 작성한 Tweakable Block Ciphers(링크) 논문을 주제로 정했습니다. 참고로 저자중 2번째에 위치한 Ronald L. Rivest는 RSA의 R입니다. 이 논문에서 최초로 Tweakable Block Ciphers라는 개념을 제안했고 이후 Tweak이라는 개념은 대칭키 분야에서 중요하게 쓰이고 있고 최근까지도 관련된 논문이 계속 제시되고 있습니다. 진정한 대가들은 학문에서 새로운 방향성을 제시한다고 하는데 이 논문이 딱 그런 상황에 걸맞는 논문이 맞지 않나 하는 생각이 듭니다. 이번 글을 통해 Tweakable block...
-
암호학의 안전성 증명 테크닉
1. Introduction 안녕하세요, 이번 글에서는 암호학에서 특정 구조에 대한 안전성을 증명하는 테크닉을 알아보겠습니다. 이 테크닉을 통해 실제 Feistel cipher의 안전성을 증명해볼 것입니다. 2. 암호학의 안전성 암호학의 안전성에 대해서는 지금으로부터 대략 1년 전에 이미 포스팅을 한 적이 있습니다. Indistinguishability(구분 불가능성)이라는 용어를 처음 들어보신다면 해당 포스팅을 먼저 확인해보시는걸 추천드립니다. 이전 글에서도 언급했듯 Indistinguishability는 달성이 굉장히 어려운 성질입니다. 또한 만약 어떤 암호 체계가 랜덤한 메시지와 구분 불가능하다는건 공격자의 입장에서 그 어떤 방법으로 공격을 시도하더라도 아무런 의미있는 정보를 얻을...
-
Zero Knowledge and Groth16 Protocol
서론 최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다. 이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다. 세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다. Zero Knowledge Proof (ZKP) Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다. 예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의...
-
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1)
1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수...
-
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}$를 하나 뽑읍시다....
-
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}...
-
Differential Cryptanalysis on 4-round DES
서론 이번 글에서는 차분 분석 (Differential cryptanalysis)가 무엇인지 간략하게 살펴보고, 4-round DES에 대한 차분 공격을 예시로 알아보고자 합니다. 본론 차분 분석 차분 분석을 간단하게 말하자면, 어떤 함수 $f$가 주어져있을 때 $x, y$ 에 대해서 $(y - x, f(y) - f(x))$ 가 일정 확률로 특정 관계성을 만족하는 것을 이용하는 분석 방법 중 하나입니다. 이렇게만 이야기하면 쉽게 와닿지 않을 것 같아서 예시를 준비해봤습니다. S-box DES, AES와 같은 암호들을 살펴보면, 대부분의 연산이 선형 계산으로 이루어져 있습니다. 즉, 어떤...
-
The Attacks on GEA-1 and GEA-2
Introduction 최근 한 논문이 암호학계에서 크게 주목을 받고 있습니다. 최고의 컨퍼런스 중 하나인 EUROCRYPT 2021에 수록된 논문인 “Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2”라는 논문입니다. 이 내용은 GEA-1, GEA-2라는 암호체계를 공격하는 알고리즘을 제시하는 논문입니다. 암호를 공격하는 논문은 많은데, 왜 하필 이 논문은 이렇게 주목을 많이 받고 있는 걸까요? 그 이유는 공격 과정에서 GEA-1에 백도어가 있다는 것이 사실상 확정적으로 밝혀졌기 때문입니다. 암호학적 백도어가 무엇인지는 barkingdong님의 http://www.secmem.org/blog/2020/09/20/Cryptographic-Backdoor/ 라는 글을 참고하시길 바랍니다. 이번 글에서는 GEA-1, GEA-2...
-
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)을...
-
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,...
-
Inequality Solving with CVP
서론 이 글은 제가 CTF 대회에서 자주 사용하는 toolkit인 github.com/rkm0959/Inequality_Solving_with_CVP의 설명서입니다. 이미 README에 많은 설명이 있지만, 설명서라기에는 부실한 점이 많아 이를 보강합니다. 제가 이 글을 작성하는 목적은 이 repository의 존재를 더 많은 사람들에게 홍보하기 위해서 이 repository의 기본적인 아이디어를 CTF를 하지 않는 사람들에게도 알리기 위해서 이 repository가 더 많은 사람들에게 사용되기를 바라기 때문 이 repository의 부족한 점을 보충하기 위해서 입니다. 이 점을 참고하시고 글을 읽어주시면 감사하겠습니다. 이 글에서 모든 나눗셈은 floor function을 거친 결과로 생각하시기...
-
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$...
-
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가 끝난 뒤 알게 되었습니다....
-
대화형 증명 시스템과 영지식 증명
이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성zero-knowledgeness을 다루고자 합니다. 대화형 증명 시스템 NP Revisited Arthur-Merlin Protocol IP 영지식 알리바바와 동굴 Indistinguishability Revisited Fiat-Shamir Protocol Hamiltonian Cycle 마무리 각주 대화형 증명 시스템 대화형 증명 시스템interactive proof system은 두 개체 증명자prover와 검증자verifier로 이루어져...
-
Post-Quantum Cryptography
1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...
-
공개 키 암호화 시스템과 수학적 안전성
이 글에서는 공개 키 암호화 시스템이 발전해나가면서 같이 논의된 수학적 개념을 살펴보고자 합니다. 특히, 암호문으로부터 평문을 알아낼 수 없다는 막연한 속성을 수학적으로 어떻게 표현하는지 알아보고자 합니다. 목차는 다음과 같습니다. 공개 키 암호화 시스템 배경 지식 공개 키 암호화 시스템의 정의 Diffie-Hellman Key Exchange RSA 암호 One-wayness CPA Semantic Security and Indistinguishability Chosen Ciphertext Attack Random Oracle Model Malleability RSA-OAEP 마무리 각주 공개 키 암호화 시스템 공개 키 암호화 시스템Public Key Cryptosystem, PKC은 W. Diffie와 M....
-
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}$이 있을 때 다음과 같은 집합을 의미합니다....
-
포카전/카포전 2020 해킹 문제 출제
서론 올해 정식 명칭은 포카전이기 때문에, 중립성을 위해 포카전/카포전으로 쓰겠습니다. 근 몇 년 간 포카전/카포전 해킹을 LeaveCat이라는 팀에서 출제하고 있습니다. 개인적으로 포항공대 PLUS의 후배들이 제 문제를 푸는 모습을 한 번 쯤 구경해보고 싶었기 때문에 이번에 LeaveCat의 일종의 멤버가 되어 처음으로 포카전/카포전 해킹 출제를 하게 되었습니다. 본래 과제로 최근에 개발하고 있던 웹사이트의 이야기를 이번 글에서 하려고 했지만, 출제진이 된 것이 일주일 전이었는데도 짧은 기간 동안 꽤 많은 시간을 투자해서 나름의 좋은 문제를 만들었다는 소기의 성과(?)를 얻었기...
-
A Generalized Birthday Problem
안녕하세요, 이번 글에서는 CRYPTO 2002에 소개된 David Wagner - A Generalized Birthday Problem 논문의 내용을 따라가며 논문에서 소개하는 Birthday Problem의 확장을 알아보겠습니다. Introduction Classic Birthday Problem Birthday Problem은 직관과 다르게 23명 이상만 있어도 그 중 두 명의 생일이 같을 확률이 1/2를 넘는다는 내용의 문제이고 별도의 설명이 필요한가 싶을 정도로 너무나 유명한 내용입니다. 암호학에서는 대표적으로 해쉬 함수가 N-bit이라고 할 때 해쉬값이 같은 두 입력을 찾기 위해서 $O(2^{N/2})$개의 입력에 대한 차분을 보면 된다는 정리가 Birthday Problem으로부터 도출되고...
-
RSA Puzzles
서론 RSA는 공개키 암호의 일종으로, 공개키를 통해 평문을 암호화할 수 있으며 비밀키를 통해 암호문을 복호화할 수 있습니다. 이 때 비밀키로부터 공개키를 구할 수는 있지만, 공개키로부터 비밀키를 구하기는 어렵다는 비대칭적 특징을 지닙니다. 일반적으로 RSA에 대한 공격이라고 한다면 공개키만을 갖고 있는 상황에서 비밀키를 구할 수 있는 방법을 의미하곤 합니다. 예를 들어 RSA는 공개키 $(e, N)$과 비밀키 $(d, N)$으로 구성되는데, $N$를 소인수분해해 $N$을 이루는 두 소수 $p, q\ (N = pq)$를 구하거나 암호문으로부터 비밀키의 값을 모르는 상태로 평문...
-
ROCA 취약점
안녕하세요, 이번 글에서는 2017년 2월에 제보된 RSA 구현에서의 취약점인 ROCA(Return Of Coppersmith Attack)에 대해 다뤄보겠습니다. RSA RSA는 별도의 설명이 필요없을 정도로 너무나 유명한 공개키 암호 시스템입니다. 암호화/복호화 과정이 헷갈리시는 분은 RSA_암호 위키를 참고하시는 것을 추천드립니다. RSA는 큰 소수 2개를 곱하는 것은 쉽지만 소인수분해하는 것은 어렵다는 사실을 이용한 암호 시스템입니다. 비록 소인수분해를 다항 시간에 처리하는 양자 알고리즘이 존재하지만 실제 양자컴퓨터가 개발되어 RSA가 무력화되기까지는 아주 긴 시간이 필요할 것으로 예상됩니다. 이외에는 RSA 암호 시스템 자체에 대한 취약점이...
-
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$ 인 곡선을 의미합니다. 타원 곡선을 정의를 하게 되면 그 곡선 상에 존재할 수 있는 점의 개수가 정해지는데,...
-
Singular Elliptic Curves
서론 최근 타원 곡선에 대해서 공부하면서 피상적으로 이해하던 부분을 좀 더 깊이 이해하는 단계에 들어서고 있습니다. 특히 수학에 대해서 배우는 것은 좋아하지만 고등 수학 위로 배운 것이 없어, 많은 재미를 느끼고 있습니다. 그러면서 해소된 궁금점은 바로 “Discriminant가 왜 0이면 안 되는 것일까?” 였습니다. 타원 곡선에 대한 Wikipedia article 을 살펴보면, $y^2 = x^3 + ax + b$ 꼴의 short Weierstrass equation에 대해서 Discriminant $\Delta = -16(4a^3 + 27b^2)$ 가 0이 아니여야 한다는 조건을 달고 있습니다....
-
Rabin-Karp 해싱의 충돌쌍 찾기
안녕하세요, 이번 글에서는 Rabin-Karp 해싱의 충돌쌍을 찾는 다양한 방법에 대해 알아보겠습니다. Rabin-Karp 해싱이란? Rabin-Karp 해싱은 문자열의 해쉬함수입니다. 이 글의 내용에서 알 수 있듯이 암호학적으로 안전한 함수는 아니지만 $O(N)$의 전처리를 거치고 나면 문자열 내의 임의의 substring의 해쉬 값을 $O(1)$에 알 수 있다는 특성 덕분에 해당 특성이 필요할 때 활용하면 효과적입니다. 또한 구현이 쉬운 편이기 때문에 굳이 암호학적으로 안전한 함수가 필요없는 상황일 경우에는 Java와 기본 String hashcode를 포함한 다양한 곳에서 사용되고 있습니다. 해싱에 대한 자세한 설명은 제...
-
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라고 불리는...
-
On Factoring Given Any Bits
서론 이번에 Belluminar 라고 하는 대회에 참가했습니다. 해당 대회는 각 팀마다 문제를 두 개 씩 출제하고, 대회 시간 동안 문제를 풀면서 점수를 겨루는 방식으로 구성되어 있습니다. 저는 이번에 공부했던 테크닉을 문제로 내기로 결심해서 작성을 했는데, 생각보다 만족스러운 퀄리티로 문제가 나오지 않아 아쉬웠습니다. 본래라면 공부한 내용을 포스트로 바로 쓰겠지만, 제 이름이나 아이디를 검색해 그대로 솔버에 사용하는 것을 원치 않았기 때문에 이러한 소셜 해킹을 방지하기 위해서 이제서야 포스팅을 하게 되었습니다. 이번 포스트는 제가 냈던 문제의 근간이 되는...
-
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)$로...
-
Linear Feedback Shift Register
안녕하세요, 이번 글에서는 Linear Feedback Shift Register에 대해 알아보도록 하겠습니다. Linear Feedback Shift Register Linear Feedback Shift Register(a.k.a LFSR)는 현재 상태에서의 선형 연산을 통해 다음 상태를 생성하는 레지스터입니다. 예를 들어 상태는 4비트이고 다음 입력값은 1-indexed 기준 4번째 비트와 3번째 비트의 XOR으로 생성된다고 해봅시다. 만약 현재 상태가 1011일 경우 $1 \oplus 1 = 0$이기에 다음 입력값은 0이고, 다음 상태는 0101이 됩니다. 그 다음 입력값은 $0 \oplus 1 = 1$이고, 다음 상태는 1010입니다. 아래의 그림을 참고해보세요. 4번째...
-
Fixed-base Miller-Rabin
shjgkwo님이 작성하신 포스팅에서 Miller-Rabin Algorithm을 소개하고 있습니다. 마침 저희 팀이 WCTF에서 출제했던 문제 중에 Miller-Rabin에서 base가 고정되어있을 때 실제로는 합성수이나 소수로 판정되는 수를 쉽게 찾을 수 있다는 취약점을 이용하는 문제가 있었기에 이 부분을 설명드리려고 합니다. Miller-Rabin Algorithm shjgkwo님의 포스팅에도 정보가 있지만 다시 한 번 설명하고 가겠습니다. 독자가 기초적인 정수론에 대한 지식은 가지고 있다고 가정하고 진행하겠습니다. 보통 어떤 수 $N$이 소수인지 판별하기 위해서는 1부터 $N^{0.5}$까지의 모든 수로 나눠보는 알고리즘을 많이 사용 합니다. 이 알고리즘은 $N$이 그다지...
-
이산 로그(Dicrete Logarithm)
이산 로그란? 수학에서의 로그는 모두 익숙할 것입니다. $a^x = b$일 때 $x = log_a b$입니다. 실수에서는 $a, b$가 주어졌을 때 $a^x = b$를 만족하는 $x$, 즉 $log_a b$를 아주 간단하게 계산할 수 있습니다. 그러나 $Z_p$에서는 이를 계산하는 것이 간단하지 않습니다. 이와 같이 $Z_p$에서 주어진 $a, b$에 대해 $a^x = b$를 만족하는 $x$를 찾는 문제가 바로 이산 로그(Discrete Logarithm) 문제입니다. 이산 로그 문제에서 $p$는 소수, $a$는 $p$의 원시근인 것이 좋습니다. $a$가 $p$의 원시근이라면 $a^0, a^1, a^2,...
-
차분 공격의 이해
개요 차분 공격(Differential Cryptanalysis, 줄여서 DC라고 부르기도 함)는 선형 공격(Linear Cryptanalysis)와 더불어 블럭 암호를 공격하는 아주 강력한 공격 기법으로, 1991년 Eli Biham과 Adi Shamir(RSA을 만드신 그 분입니다!)에 의해 처음 논문으로 제시되었습니다. NSA는 차분 공격을 1974년부터 인지하고 있었고 DES를 설계할 때 차분 공격으로부터 최대한 안전하게끔 만들었다고 추후에 밝혔습니다. DES의 예시와 같이 비록 현대에 들어서는 블럭 암호를 설계할 때 차분 공격에 안전하게끔 설계를 하지만, Higher-order differential cryptanalysis, Truncated differential cryptanalysis, Impossible differential cryptanalysis, Boomerang attack과 같이 다양한...
-
현대 암호 1 : 블록 암호
저번 포스팅에서는 고전 암호를 다루었습니다. 이번 포스팅에서는 현대 암호 중에서도 DES, AES와 같은 블록 암호를 다루도록 하겠습니다. 블록 암호란? 블록 암호(Block Cipher)란 평문을 블록 단위로 암호화하는 대칭키 암호 시스템입니다. 대칭키 암호 시스템은 암호화와 복호화를 할 때 동일한 키가 사용되는 암호 시스템입니다. 반대로 암호화와 복호화를 할 때 동일하지 않은 키가 사용되지 않는 공개키 암호 시스템도 존재하는데, 공개키 암호 시스템 보다는 대칭키 암호 시스템이 우리의 직관과 조금 더 맞는 시스템일 것입니다. 참고로 저번 포스팅에서 다룬 고전 암호는...
-
고전 암호의 공격 기법
암호학에 대해 잘 알고 있나요? 암호학과 관련해 깊은 지식을 가지고 있지는 않더라도 분명 역사 속에서, 문학 속에서, 혹은 일상생활 속에서라도 암호학을 접해본 적이 있을 것입니다. 현대에는 컴퓨터의 성능이 비약적으로 발전했고 다양한 암호 분석 기법이 나왔기 때문에 단순히 각 알파벳을 다른 알파벳으로 치환하는 치환 암호 혹은 평문 내에서 글자의 순서를 바꾸는 전치 암호와 같은 고전 암호는 더 이상 사용되고 있지 않습니다. 그러나 실제로 개인이 고전 암호로 암호화된 메시지를 해독하려고 시도를 해본다면 설령 암호화 방식이 공개된 상태라고...