Samsung Software Membership

blisstoner

June 19, 2022

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...

cryptography

blisstoner

May 15, 2022

Large S-box의 암호학적 성질 및 대수적 공격

1. Introduction 대칭키 암호화 시스템은 선형 연산과 비선형 연산을 반복적으로 적용해 키와 암호문 혹은 평문과 암호문의 관계를 가립니다. 이 때 S-box는 비선형 성질을 제공하는 중요한 역할을 합니다. DES에서는 6비트의 입력을 받아 4비트를 출력하는 S-box가 사용되었고 AES에서는 8비트의 입력을 받아 8비트를 출력하는 S-box가 사용되었습니다. 암호가 안전하기 위해서는 S-box가 편향되지 않고 잘 정의되어야 합니다. 예를 들어 S-box의 차분 성질이나 선형 성질의 편향이 클 경우 이를 이용한 차분 공격 혹은 선형 공격이 가능할 수 있습니다. 직관적으로 생각했을 때...

cryptography

blisstoner

April 17, 2022

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...

cryptography

blisstoner

March 20, 2022

암호학의 안전성 증명 테크닉

1. Introduction 안녕하세요, 이번 글에서는 암호학에서 특정 구조에 대한 안전성을 증명하는 테크닉을 알아보겠습니다. 이 테크닉을 통해 실제 Feistel cipher의 안전성을 증명해볼 것입니다. 2. 암호학의 안전성 암호학의 안전성에 대해서는 지금으로부터 대략 1년 전에 이미 포스팅을 한 적이 있습니다. Indistinguishability(구분 불가능성)이라는 용어를 처음 들어보신다면 해당 포스팅을 먼저 확인해보시는걸 추천드립니다. 이전 글에서도 언급했듯 Indistinguishability는 달성이 굉장히 어려운 성질입니다. 또한 만약 어떤 암호 체계가 랜덤한 메시지와 구분 불가능하다는건 공격자의 입장에서 그 어떤 방법으로 공격을 시도하더라도 아무런 의미있는 정보를 얻을...

cryptography

blisstoner

February 15, 2022

Intel Intrinsics(SIMD) 가이드

1. Introduction 우리가 주로 사용하는 Intel(AMD) 아키텍쳐에서는 SIMD(Single Instruction Multiple Data)를 이용할 수 있습니다. SIMD는 말 뜻 그대로 하나의 명령을 통해 여러 값의 연산을 동시에 처리하는 명령어 셋으로, 단순 덧셈/비교/뺄셈과 같은 작업을 병렬화해서 실행 시간을 줄일 수 있습니다. 영상 처리, 머신러닝 분야에서 SIMD는 빼놓을 수 없는 존재이고, 암호 모듈 구현에서도 SIMD를 통해 성능을 극한으로 끌어올려 벤치마크를 확인합니다. 저는 처음 SIMD를 건드려본게 암호 모듈 구현체를 수정해야 할 일이 있어서였습니다. 아무래도 처음 쓰는거라 낯설다보니 이런저런 자료를 찾아가며...

blisstoner

January 15, 2022

GNN을 이용한 컴파일러 기원 문제 해결 방법

1. Introduction 프로그래머가 작성한 코드는 컴파일 과정을 거쳐 기계가 해석 가능한 코드로 변환됩니다. 이 때 동일한 소스 코드임에도 불구하고 컴파일러의 종류에 따라 최종 결과물인 실행 파일에는 차이가 있을 수 있습니다. 하지만 일반적으로 실행 파일로부터 컴파일러의 종류와 버전, 최적화 옵션 등을 알아맞추는 것은 다소 난이도가 있는 작업이고 특히 디버깅 심볼을 포함한 여러 메타 데이터가 제거된 실행 파일에서는 파일에 포함된 문자열 등을 활용할 수 없이 오로지 데이터 영역의 값만을 통해 컴파일러를 유추해야 합니다. 한편, 실행 파일로부터 컴파일러의...

machine-learning GNN

blisstoner

November 21, 2021

Cryptanalytic Extraction of Neural Network Models

1. Introduction 이번 글에서는 암호학 분야에서 탑 티어 컨퍼런스 중 하나인 CRYPTO 2020에 통과된 Cryptanalytic Extraction of Neural Network Models 논문에 대해 알아보고자 합니다. 보통 암호학에서 인공지능을 활용할 때나 반대로 인공지능에서 암호학을 활용할 때에는 해당 기술을 마치 블랙박스와 같이 두고 결과를 가져다 쓰는 방식으로 진행되기 마련인데 이 논문에서는 그게 아니고 Neural Network Model의 Extraction을 하는 상황이 곧 암호학에서 아주 유명한 공격인 차분 공격을 하는 상황과 유사하다는 것을 이용해 Neural Network Model에 대한 Extraction을 기존의 방법들보다...

Cryptography

blisstoner

October 14, 2021

키보드 음성 키로거

1. Introduction 최근에 참가한 PBCTF 2021에서 Ghost Writers라는 이름의 문제를 보다가 굉장히 흥미로운 주제를 알게 되어 소개해드립니다. 특히 음성 인식과 머신 러닝에 관심이 많은 분이라면 좋은 연구 주제가 될 수 있다고 생각합니다. 트위치나 아프리카와 같은 플랫폼에서 여러 스트리머의 방송을 보다보면 마이크를 꺼두지 않는 한 방송 중에 기계식 키보드의 타이핑 소리가 그대로 송출이 되는 경우가 거의 대다수입니다. 이 타이핑 소리로부터 무언가 의미있는 정보를 얻기는 어려울 것 같지만, 혹시 지금 주변에 기계식 키보드가 있다면 여러 키를 눌러보았을...

blisstoner

September 19, 2021

WYSINWYX: What You See Is Not What You eXecute

1. Introduction 글을 시작하기에 앞서, 이 글에서 다루는 논문 WYSINWYX: What You See Is Not What You eXecute 는 카이스트 차상길 교수님의 IS-561: Binary Code Analysis and Secure Software Systems 과목에서 읽어보면 좋은 논문으로 소개된 논문입니다. 과목 링크에 들어가보시면 이외에도 정보 보안의 근간을 이해하는데에 있어서 도움이 될 여러 논문들을 소개하고 있으니 확인해보시는 것을 추천드립니다. WISINWYX는 WISIWYG이라는 표현으로부터 따온 재치있는 표현입니다. 저는 WISIWYG를 아주 먼 옛날 워드프로세서 필기를 공부하며 들어본 것 같은데, WISIWYG는 What You See...

security

blisstoner

August 21, 2021

TLS 1.3 프로토콜

1. Introduction 8월 16일 오후 3시부터 24시간동안 삼성에서 열린 SCTF에 DecryptTLS라는 이름의 TLS 관련 문제가 출제되었습니다. 해당 문제에서는 구글 웹사이트와 통신한 TLS 패킷파일이 제공되어서 해당 파일로부터 플래그를 알아내야 했습니다. 문제에 들어있던 암호학적 취약점 자체는 그렇게 복잡하지는 않았지만 정작 프로토콜의 Specification을 보고 데이터를 추출하는데에 rkm0959님과 같이 아주 긴 시간동안 고통을 받았습니다. 그래도 그 과정에서 TLS 1.3 버전에 대한 공부를 할 수 있었어서 TLS 1.3에 대한 포스팅을 작성하고자 합니다. 2. TLS 옛날 옛적에는 웹서버와 통신을 할 때...

Cryptography

blisstoner

July 18, 2021

Zero Knowledge Proof using AES

1. Introduction 이전에 썼던 글들을 통해 MPC를 이용해 Zero-Knowledge Proof를 만들 수 있다 Fiat-Shamir Transform을 이용해 Zero-Knowledge Proof을 Non-Interactive로 변경할 수 있다 NIZK를 통해 전자 서명을 만들 수 있다 는 것을 알게 되었습니다. 이미 RSA 혹은 ECC 등을 이용한 전자서명이 존재하지만 RSA 혹은 ECC 등은 아직 증명되지 않은 정수론/대수학적 안전성을 가정해야 하는 반면, MPC를 이용한 전자서명은 오로지 해시 함수의 안전성에만 의존한다는 장점이 있습니다. 더 나아가 양자컴퓨터가 개발된 이후에도 안전한 양자 내성 성질을 가지고 있습니다. 전자서명을...

Cryptography

blisstoner

June 20, 2021

Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures

1. Introduction 저번 글에서는 MPC를 이용한 Zero-Knowledge Proof에 대해 다루었습니다. 쉽게 요약을 해보자면 MPC-in-the-head를 이용해 증명자는 SHA256(x) = y를 만족하는 y를 알고 있다는 사실을 x를 공개하지 않고 검증자에게 납득시킬 수 있습니다. 더 나아가 원래의 증명은 검증자의 질의에 대해 증명자가 대답하는 방식으로 진행되나 Fiat-Shamir Transform을 사용하면 Non-Interactive로 증명을 만들 수 있습니다. 이렇게 Ishai et al.이 MPC-in-the-head를 제안한 후 Giacomelli et al.은 실제로 MPC를 수행하는 ZKBoo 프로토콜을 만들어냈습니다. 한편, Zero-Knowledge Proof로부터 전자서명을 만들 수 있습니다. 이건 사실...

Cryptography

blisstoner

May 17, 2021

Zero-Knowledge from MPC

1. Introduction 드디어 Zero-Knowledge에 도달했습니다. 암호학에 그다지 관심이 없었다고 하더라도 최근 Zero-Knowledge가 모네로, 지캐시와 같은 프라이버시 코인에 쓰임으로 인해 Zero-Knowledge라는 단어 혹은 간단한 개념 정도는 익숙한 분이 그럭저럭 있을 것으로 보입니다. 맨 처음에는 게시글 하나를 할애해 Zero-Knowledge에 대한 설명을 하려고 했으나 evenharder님이 작성하신 대화형 증명 시스템과 영지식 증명에 설명이 잘 되어있어서 자세한 설명은 저 글로 대신하고 간단한 요약만 작성하겠습니다. 먼저 $\text{SHA256}(x) = 0^{256}$을 만족하는 $x$를 증명자가 알고 있고, 알고 있다는 사실을 검증자에게 증명하면서도 $x$ 자체는...

Cryptography

blisstoner

April 18, 2021

Ciphers for MPC and FHE

1. Introduction 최근의 두 포스트에서 Multi-party computation에 대해 다루었습니다. Garbled circuit의 발전사와 최종적인 형태를 보면 결론적으로 AND 연산의 수가 적으면 적을수록 MPC의 성능이 올라감을 알 수 있습니다. 또한 ZK(Zeroknowlege Proof, prover가 verfier에게 어떤 문장이 참임을 증명할 때 그 문장이 참이라는 것을 제외하면 그 어떤 정보도 prover에게 노출하지 않는 프로토콜),FHE(Fully Homomorphic Encryption, 데이터를 암호화한 상태로 연산할 수 있는 암호화 방법) 등에서도 AND 연산이 XOR 연산에 비해 훨씬 큰 비중을 차지합니다. 기존에 널리 쓰이는 암호화 알고리즘으로는 AES가...

Cryptography

blisstoner

March 21, 2021

Multi-Party Computation 2

1. Introduction 저번 시간에 이어서 Multi-Party Computation을 살펴보겠습니다. 저번 시간에는 MPC를 할 수 있는 Garbled Circuit을 만드는 방법을 알아보고 Garbled Circuit이 처음 등장한 1982년부터 Half-gates technique이 발표된 2015년까지 어떠한 흐름을 통해 발전해왔는지 확인했습니다. 이번 시간에는 실제 Garbled Circuit을 구현할 때에는 어떤 방법을 이용하는지, 그리고 그와 관련한 안전성과 공격을 살펴보겠습니다. 2. Half-gates technique 저번 글에서는 이 Half-gates technique에 관해 아주 간략하게 설명을 하고 넘어갔습니다. 그러나 이번 글에서 본격적으로 안전성에 대해 논의를 하다보면 Half-gates technique의 동작에 대해...

Cryptography

blisstoner

February 20, 2021

Multi-Party Computation 1

1. Introduction 두 부자 Alice와 Bob이 있다. 두 명은 상대방에게 자신의 재산이 얼마인지 공개하지 않고 누구의 재산이 더 많은지 비교하고 싶다. 라는 문제를 생각해봅시다. 사실 이 문제를 해결하는 방법은 굉장히 간단합니다. Alice와 Bob이 모두 신뢰할 수 있는 Charlie가 있다면 Alice와 Bob이 Charlie에게 자신의 재산을 알려주고 Charlie가 비교를 한 후 누가 더 재산이 많은지를 두 사람에게 알려주면 됩니다. 하지만 두 사람이 모두 신뢰할 수 있는 제 3자가 없다면 상황이 많이 복잡해집니다. 결국 대소를 비교하려면 양쪽의 값을...

Cryptography

blisstoner

January 24, 2021

Indistinguishability in Cryptography

1. Introduction 주어진 암호를 키에 대한 정보 없이 전수 조사보다 더 효율적으로 완전히 해독할 수 있다면 더할 나위 없이 강력한 공격입니다. 특히 현재 널리 쓰이고 있는 암호 시스템에 대해 이러한 공격을 찾았다면 정말 큰 업적을 세웠다고 할 수 있습니다. 그러나 수명, 많게는 수십명이 협력해 만들고 긴 시간을 걸쳐 검증을 받아온 암호 시스템에서 이러한 공격이 발견되기란 굉장히 어려운 일입니다. 이렇게 암호문을 완전히 해독하는건 매우 힘들지만 학계에서는 꼭 암호문을 완전 해독해내는 것이 아닌 더 느슨한 환경에서의 조그만...

Cryptography

blisstoner

December 20, 2020

SABER: Mod-LWR based KEM

1. Introduction 저번 글에서는 양자 컴퓨터와 Post Quantum Cryptography에 대해 다루었습니다. 이번 포스팅에서는 어떤 암호 시스템을 다루어볼까 고민하다가 NIST에서 진행하는 PQC contest의 3라운드 7개의 후보 중에서 5개가 Lattice-based인 만큼 Lattice를 기반 문제로 사용하는 SABER 암호의 동작 원리, 장단점을 소개해보려고 합니다. 저도 불과 한달 전까지만 해도 PQC에서 사용하는 Lattice에 대해 아주 얕은 지식만을 가지고 있었기 때문에 Lattice를 잘 모르더라도 글을 이해하는데 큰 어려움은 없습니다. 다만 Group Theory가 많이 쓰이기 때문에 Group Theory에 대한 이해가 약하시면 내용을...

quantum Cryptography

blisstoner

November 22, 2020

Post-Quantum Cryptography

1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...

quantum cryptography

blisstoner

October 25, 2020

블루투스의 취약점들

1. Introduction 블루투스는 수많은 기기들이 근거리 통신을 위해 사용하는 프로토콜입니다. 컴퓨터와 연관이 있는 키보드, 마우스, 스피커 등의 입출력장치는 물론이고 심장박동수 측정 기기와 같은 의료기기들도 무선으로 정보를 송/수신해야할 필요가 있을 경우 블루투스를 사용합니다. 블루투스 통신에서 오가는 정보는 반드시 기밀이 유지되어야 하고 송/수신자가 아닌 외부의 공격자가 내용을 감청하거나 변조하는 일이 없어야 합니다. 그렇기 때문에 블루투스의 통신 규약을 보면 내용은 암호화가 되고 다양한 공격들에 대한 대비책을 미리 마련해두고 있습니다. 그러나 현존하는 모든 시스템이 그러하듯 블루투스 프로토콜도 다양한 취약점이...

Bluetooth Security

blisstoner

September 20, 2020

Cryptographic Backdoor

안녕하세요, 최근에 연달아 다소 난이도 있고 재미 없는 내용을 올렸는데 이번 글에서는 약간의 배경 지식을 필요로 하지만 굉장히 흥미로운 주제를 가지고 왔습니다. 꼭 암호학에 관심이 없더라도 읽어보면 재밌을만한 내용이니 편하게 즐겨주세요. Introduction Privacy vs National security 디지털 시대가 도래하면서 개인의 프라이버시와 국가 안보 사이에서 딜레마를 겪는 일이 많아지고 있습니다. 2015년 샌버너디노 총기 난사 사건 당시 수사기관은 애플에게 테러리스트의 휴대폰 잠금을 풀어줄 것을 요청했지만 애플은 이를 거부했고, 2017년 웨스트민스터 테러에서도 암호화된 테러리스트의 Whatsapp 대화를 풀어내지 못했습니다....

Cryptography

blisstoner

August 19, 2020

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으로부터 도출되고...

cryptography

blisstoner

July 18, 2020

ROCA 취약점

안녕하세요, 이번 글에서는 2017년 2월에 제보된 RSA 구현에서의 취약점인 ROCA(Return Of Coppersmith Attack)에 대해 다뤄보겠습니다. RSA RSA는 별도의 설명이 필요없을 정도로 너무나 유명한 공개키 암호 시스템입니다. 암호화/복호화 과정이 헷갈리시는 분은 RSA_암호 위키를 참고하시는 것을 추천드립니다. RSA는 큰 소수 2개를 곱하는 것은 쉽지만 소인수분해하는 것은 어렵다는 사실을 이용한 암호 시스템입니다. 비록 소인수분해를 다항 시간에 처리하는 양자 알고리즘이 존재하지만 실제 양자컴퓨터가 개발되어 RSA가 무력화되기까지는 아주 긴 시간이 필요할 것으로 예상됩니다. 이외에는 RSA 암호 시스템 자체에 대한 취약점이...

cryptography

blisstoner

December 15, 2019

Rabin-Karp 해싱의 충돌쌍 찾기

안녕하세요, 이번 글에서는 Rabin-Karp 해싱의 충돌쌍을 찾는 다양한 방법에 대해 알아보겠습니다. Rabin-Karp 해싱이란? Rabin-Karp 해싱은 문자열의 해쉬함수입니다. 이 글의 내용에서 알 수 있듯이 암호학적으로 안전한 함수는 아니지만 $O(N)$의 전처리를 거치고 나면 문자열 내의 임의의 substring의 해쉬 값을 $O(1)$에 알 수 있다는 특성 덕분에 해당 특성이 필요할 때 활용하면 효과적입니다. 또한 구현이 쉬운 편이기 때문에 굳이 암호학적으로 안전한 함수가 필요없는 상황일 경우에는 Java와 기본 String hashcode를 포함한 다양한 곳에서 사용되고 있습니다. 해싱에 대한 자세한 설명은 제...

algorithm cryptography

blisstoner

November 15, 2019

2D Segment Tree

안녕하세요, 이번 글에서는 2D Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree에 관한 기초 지식 2D Segment Tree를 이해하기 위해서는 Persistent Segment Tree 포스팅 때와 비슷하게 Segment Tree에 대한 이해가 선행되어야 합니다. Segment Tree가 무엇인지, 혹은 Dynamic Segment Tree가 무엇인지 모르고 있다면 먼저 링크를 타고 그 부분을 공부한 후에 오시는 것을 추천드립니다. Bottom-Up 방식의 Segment Tree Segment Tree를 구현하는 방법으로는 Top-Down 방식과 Bottom-Up 방식이 있습니다. 이전 글에서는 Top-Down 방식만을 설명했으나 2D Segment Tree에서는 Bottom-Up 방식을...

data-structure

blisstoner

October 20, 2019

떼껄룩 조각모음

이번달 초에 하웨이에서 주최한 마라톤 매치가 있었습니다. 주어진 기간은 2주였고, 1등 상금이 무려 10000달러인 것을 확인하고 눈이 돌아가 얕게 발을 담구었습니다. 이 대회에서 요구한 것은 아래와 같이 8x8조각, 16x16조각, 32x32조각으로 나누어진 고양이 사진을 재배치하는 것이었습니다. 나름대로 프로토타입을 만들고 그럭저럭 괜찮은 점수를 얻었지만 관련 논문들 좀 읽고 ICPC 준비도 하고 그러던 중에 다른 참가자들의 점수가 어떻게 비벼볼 수 없는 수준으로 높아져있는 것을 확인하고 그냥 포기했습니다. 그래도 재밌는 도전이었던 만큼 제가 공부한 기록을 남겨보고 싶어 포스팅을 작성해봅니다....

computer-vision

blisstoner

September 18, 2019

Persistent Segment Tree

안녕하세요, 이번 글에서는 Persistent Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. 이미 대다수의 독자분들이 Segment Tree에 대해 알고 있겠지만 다시 한 번 짚고 넘어가겠습니다. Segment Tree는 배열을 여러 구간으로 나누어 관리하는 구조로, $N$개의 원소가 있을 때 구현에 따라 2배에서 4배 정도의 추가 공간이 필요하지만 원소의 변경, 특정 범위 내의 원소의 연산을 $lgN$에 수행할 수 있습니다. 구체적으로 배열 1 2 3 4 3 2...

data-structure algorithm

blisstoner

August 19, 2019

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번째...

cryptography

blisstoner

July 19, 2019

Fixed-base Miller-Rabin

shjgkwo님이 작성하신 포스팅에서 Miller-Rabin Algorithm을 소개하고 있습니다. 마침 저희 팀이 WCTF에서 출제했던 문제 중에 Miller-Rabin에서 base가 고정되어있을 때 실제로는 합성수이나 소수로 판정되는 수를 쉽게 찾을 수 있다는 취약점을 이용하는 문제가 있었기에 이 부분을 설명드리려고 합니다. Miller-Rabin Algorithm shjgkwo님의 포스팅에도 정보가 있지만 다시 한 번 설명하고 가겠습니다. 독자가 기초적인 정수론에 대한 지식은 가지고 있다고 가정하고 진행하겠습니다. 보통 어떤 수 $N$이 소수인지 판별하기 위해서는 1부터 $N^{0.5}$까지의 모든 수로 나눠보는 알고리즘을 많이 사용 합니다. 이 알고리즘은 $N$이 그다지...

cryptography

blisstoner

June 17, 2019

번사이드 보조정리(Burnside Lemma)

서론 Burnside Lemma(번사이드 보조정리)는 Group action에서 나오는 정리입니다. 여기서 말하는 Group이란 대수학에서의 Group을 의미합니다. Competitive Programming에서 아주 가끔씩 경우의 수를 세는 문제에서 활용이 되나 객관적으로 나올 확률은 굉장히 낮다고 볼 수 있습니다. 이 글 자체는 Group Theory의 기초부터 차근차근 설명을 할 예정이지만 만약 Group Theory에 대해 이전에 전혀 공부를 한 적이 없다면 안타깝게도 이론적 배경을 이해하는 것이 불가능에 가까울 것입니다. 대신 이론적 배경을 이해하지 않고 하단의 실제 문제에서 Burnside Lemma를 사용하는 예시만을 익혀두어도 괜찮습니다. 배경...

competitive-programming group-theory

blisstoner

May 17, 2019

이산 로그(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,...

cryptography

blisstoner

April 8, 2019

차분 공격의 이해

개요 차분 공격(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과 같이 다양한...

cryptography

blisstoner

March 7, 2019

코딩테스트 대비 특강

이 포스트는 3월 1일과 2일에 걸쳐 진행한 코딩테스트 특강의 내용을 기술한 포스트입니다. BFS/DFS, 백트래킹, 시뮬레이션 개념을 알고 있고 기출 문제에 손을 댈 수는 있는데 100% 푼다는 확신은 없어서 개념을 다시 정리하고 모의고사를 쳐보고 싶은 분이 이 포스트를 보신다면 많은 도움이 될 것입니다. 특강의 슬라이드는 여기에서 확인할 수 있습니다. 이 특강은 개인이 준비한 특강이고, 특히 특정 기업의 채용절차와 아무런 관련이 없습니다. 무엇보다 먼저 기초 지식과 자주 실수하는 점을 짚고 넘어가겠습니다. 함수의 인자로 구조체/pair/tuple/vector를 넘길 때 어떤...

BFS-DFS backtracking

blisstoner

February 6, 2019

현대 암호 1 : 블록 암호

저번 포스팅에서는 고전 암호를 다루었습니다. 이번 포스팅에서는 현대 암호 중에서도 DES, AES와 같은 블록 암호를 다루도록 하겠습니다. 블록 암호란? 블록 암호(Block Cipher)란 평문을 블록 단위로 암호화하는 대칭키 암호 시스템입니다. 대칭키 암호 시스템은 암호화와 복호화를 할 때 동일한 키가 사용되는 암호 시스템입니다. 반대로 암호화와 복호화를 할 때 동일하지 않은 키가 사용되지 않는 공개키 암호 시스템도 존재하는데, 공개키 암호 시스템 보다는 대칭키 암호 시스템이 우리의 직관과 조금 더 맞는 시스템일 것입니다. 참고로 저번 포스팅에서 다룬 고전 암호는...

cryptography

blisstoner

January 7, 2019

고전 암호의 공격 기법

암호학에 대해 잘 알고 있나요? 암호학과 관련해 깊은 지식을 가지고 있지는 않더라도 분명 역사 속에서, 문학 속에서, 혹은 일상생활 속에서라도 암호학을 접해본 적이 있을 것입니다. 현대에는 컴퓨터의 성능이 비약적으로 발전했고 다양한 암호 분석 기법이 나왔기 때문에 단순히 각 알파벳을 다른 알파벳으로 치환하는 치환 암호 혹은 평문 내에서 글자의 순서를 바꾸는 전치 암호와 같은 고전 암호는 더 이상 사용되고 있지 않습니다. 그러나 실제로 개인이 고전 암호로 암호화된 메시지를 해독하려고 시도를 해본다면 설령 암호화 방식이 공개된 상태라고...

cryptography

Blisstoner

Triple DES의 안전성

Large S-box의 암호학적 성질 및 대수적 공격

Tweakable block ciphers

암호학의 안전성 증명 테크닉

Intel Intrinsics(SIMD) 가이드

GNN을 이용한 컴파일러 기원 문제 해결 방법

Cryptanalytic Extraction of Neural Network Models

키보드 음성 키로거

WYSINWYX: What You See Is Not What You eXecute

TLS 1.3 프로토콜

Zero Knowledge Proof using AES

Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures

Zero-Knowledge from MPC

Ciphers for MPC and FHE

Multi-Party Computation 2

Multi-Party Computation 1

Indistinguishability in Cryptography

SABER: Mod-LWR based KEM

Post-Quantum Cryptography

블루투스의 취약점들

Cryptographic Backdoor

A Generalized Birthday Problem

ROCA 취약점

Rabin-Karp 해싱의 충돌쌍 찾기

2D Segment Tree

떼껄룩 조각모음

Persistent Segment Tree

Linear Feedback Shift Register

Fixed-base Miller-Rabin

번사이드 보조정리(Burnside Lemma)

이산 로그(Dicrete Logarithm)

차분 공격의 이해

코딩테스트 대비 특강

현대 암호 1 : 블록 암호

고전 암호의 공격 기법