[블록체인] 03. Cryptography for Blockchains

728x90

What is Crypto?

암호학의 역사
대칭 암호화와와 비대칭 암호화 비교
대칭 키 암호 방식이란
공개 키 암호 방식이란

What is Crypto's Goal?

* Cryptography, where security meets mathematics
- Cryptography : the science and art of designing ciphers (making ‘secret codes’)
- Cryptanalysis : the science and art of breaking them (breaking ‘secret codes’)
- Cryptology : the study of both
- Crypto : all of the above (context-aware)

Basic Definitions

- cipher(암호), cryptosystem : pliantext(평문)를 encrypt(암호화)하는 데 사용됨.
- encrypt(암호화) : plaintext(평문) -> cipher text(암호문)
- decrypt(복호화) : cipher text(암호문) -> plaintext(평문)

- key : cryptosystem 환경 설정에 사용됨.
- key-based classifications : key 개수에 따라 분류하기도 함.
ex) attack -> dwwdfn (key=3)
- symmetric key(대칭 키) : 하나의 키로 암호화 및 복호화 ex) 현관문을 열쇠로 열던 시절

- public key(asymmetric key) : public key로 암호화, private key로 복호화 (쌍으로 동작함)

Crypto

- 시스템/알고리즘은 전부 다 알려져있음. (비밀은 언젠가 들통나기 마련이고 노출에 취약하므로)
- key가 비밀임.

Types of cipher

① Random functions (Hash functions)
: 사이즈 제한 없는 input -> 고정된 크기의 무작위로 보이는 output (256~512bits)

사이즈 제한 없은 input이 h(x)후에 사이즈가 2^N으로 고정된 output과 mapping되므로
여러 input들이 하나의 output에 mapping되는 충돌이 발생할 수 있음.

② Random generators (Stream ciphers) ; symetric key crypto
: short input(seed)을 랜덤으로 주면 pseudo random input stream이 생성됨.
그걸 가변 길이인 평문(plain text)과 동일한 길이로 잘라서
random sequence를 stream(강물)처럼 generate함 .

plain text와 random pad를 bitwise XOR하면 cipher text가 만들어짐.
반대로 상대방은 cipher text와 random pad를 bitwise XOR하면 plain text가 만들어짐.

* seed value(입력) -> pseudo random number(출력)
: seed값 넣으면 s/w로 얻은 다량의 랜덤넘버가 생성됨.
동일한 seed를 넣으면 동일한 출력이 나오므로 pseudo라는 단어가 붙음.
하지만 상대방은 잘 모를것이기때문에 random numbeer역할은 함.

③ Random permutations (Block ciphers) ; symetric key crypto
: keyed-intertible function(역함수)를 이용하여 block 단위로 암호화/복호화가 일어남.
* permutatin : 순열 ,뒤섞기
* block : 고정된 크기의 암호화/복호화 단위(128~256bit) 여기선 블록체인 block과 다른 의미임.

④ Public key encryption (special kind of block cipher) ; Asymetric key crypto
: public key로 누구나 암호화 가능, private key로 복호화(key owner만 열어볼 수 있음)
private key로 서명하면 public key로 검증함. private key는 유출되면 안됨.

⑤ Digital signature
: key owner에 의해 디지털 서명됨, 누구나 check 가능

① Hash Function (해시 함수)

input(크기 제한 없음) -> output(고정된 크기의 해시 결과 값)

* 충돌(collision)
: 서로 다른 input -> 동일한 hash id
충돌을 완전히 피할 방법은 없음. 최대한 줄이는 게 목표임.(충돌 찾기 어렵게)

Cryptographic Hash Function

* SHA256 : 비트코인이 사용중인 crypto hash function
* 334d016f... : output의 0과 1의 sequance 256bits를 인코딩 한 것
cryptographic hash function은 충돌을 최대한 피하도록 설계되어 있음.
누군가가 채굴한 것과 똑같은 결과를 내는 것을 찾을 수 있다면
block 바꿔치기가 가능해져서 신뢰성이 떨어지기 때문.

Cryptographic Hash Function h(x) must provide...

- Collision resistance (=Strong Collision resistance)
: 충돌 저항성
충돌 발생 자체를 막을 수는 없지만, 공격자가 충돌을 찾는 게 매우 어려워지도록 만들자.
x가 주어지지 않았을 때, 공격자가 동일한 hash값으로 mapping되는 임의의 값 두개를 찾는 게
매우 어렵다면 string collision resistance가 성립하는 것임.
즉, x!=y인데 h(x)==h(y)인 x와 y 찾기

- Preimage resistance (=Oneway Property)
: image로 부터 preimage를 찾는 게 매우 어렵다면 preimage resistance가 존재하는 거임.
x로 h(x)를 구하는 건 빠르지만 h(x)=y값으로 x를 찾아내는 것은 어려움.

- 2nd-preimage resistance (=Weak Collision resistance)
: x와 h(x)가 주어졌을 때, y!=x이고 h(y)==h(x)인 y를 찾는 것이 매우 어렵다면
weak collision resistance가 성립하는 것임.

- Compression
: output size는 고정된 작은 size임.

- Efficiency
: x로 h(x)를 계산하는 것은 쉽고 빠름.

매우 유사한 2개의 input에 대하여 거의 똑같은 output을 낸다면 위험함.
10G input 2개가 서로 딱 1bit만 다르더라도,
제대로 된 crypto hash function은 완전히 다른 2개의 output을 만듦.

* cryptographic hash function 사용 예시

: 비밀번호를 암호화해서 DB에 저장. 공격자가 DB해킹해도 비번 모름.

Pre-Birthday Problem

Q1. 방에 N명 있음. 그중에 나랑 생일이 같은 사람이 있을 확률이 1/2이 되려면 N은 몇명일까?
A1. 1/2 = 1-(나랑 생일이 다를 확률)^N = 1-(364/365)^N
∴ N = 253 (182보다 크고 365보다 작음)

Q2. 방에 K명 있음. 이중에 생일이 같은 두 사람이 있을 확률이 1/2이 되려면 K은 몇명일까?
A2. (B가 A와 생일 다를 확률) = 364/365, (C가 A,B와 생일 다를 확률) = 353/365 ...

k가 루트N보다 살짝 크면 해당 확률은 1/2보다 작아짐. 즉 정답은 루트365인 23명.
∴ K = 23 * K는 사람 수, N은 생일 수

==> h(x)의 output 길이가 Nbits일 때,
2^N의 서로다른 해시값이 가능함.(위의 예시에서 2^N은 365일에 해당)

따라서 SHA256의 hash를 break하려면 2^(n/2) = 2^(256/2) = 2^128의 hash계산이 가능해야함.

* hash를 break하는 데 드는 노력
- Crypto hash function
: output size N일 때, 루트(2^N) = 2^(N/2)번의 hash 계산 필요
- Symmetric cipher key
: key size Nbit일때, (2^N)/2 = 2^(N-1)번의 시도 필요.
Nbit의 key -> 서로다른 2^N개의 key 이므로, 암호문에서 평문을 얻으려면
symmetric cipher 시도를 하나하나씩 해봤을 때 평균적으로 절반정도는 해봐야 성공함.

② Stream Ciphers (Random generators)

seed value로 pseudo random number를 generate함.
=> random bit generator의 source of randomness가 무엇일까?
: 하드웨어 장치(diode의 noise 등), 사용자의 행동(키보드 누르는 시간 간격, 마우스 움직이는 궤적 등)

③ Block Ciphers (Random permutations)

block 단위로 암호화 및 복호화.
block size가 128bits라면 서로다른 block 2^128개.

서로 일대일 대응이어야 뒤집을 수 있음(암호화<->복호화)
keyed-invertible(key로 역함수 계산). key가 permutation을 결정함.

Confusion과 Diffusion을 적절히 활용함.

* Confusion : key와 ciphertext의 관계를 최대한 복잡하게 만들기
* Diffusion : plaintext와 ciphertext의 관계를 최대한 모호하게 하기(없애기)

AES (Advanced Encryption Standard)

AES 알고리즘이란?
block size : 128bits
key length : 128bits, 192bits, 256bits(안전!)

Block Operation Modes

암호화하려는 message가 굉장히 크다면 block(대부분 128bits) 여러개가 필요함.
암호화하려는 message가 block size의 정수배가 아닐 수도 있음.

- CBC (Cipher Block Chaining) mode
: 평문을 조각(block)단위로 나눠서, 현재 block을 암호화 한 내용을 다음 block을 암호화할 때 사용
- GCM (Galois Counter mode)
: 최근엔 이거 사용중. 그냥 이런게 있다는 정도만 알면 됨.

④ Public key encryption

key가 항상 쌍으로 존재함. {public key, private key}

A와 B가 통신을 하는 상황. B가 보낸 메세지를 A만 열어봤으면 좋겠음.
B의 메세지를 중간에 누가 가로채더라도 그 내용을 알아보지 못하게 하고싶음.
-> 이 기능을 public key crypto로 제공할 수 있음.

근데 symmetric key crypto로도 제공할 수 있는거 아닌가요?
-> 맞음. 근데 A와 B가 이미 key를 안전하게 공유하고있고
제3자(공격자)는 key를 알 지 못해야한다는 전제가 필요함. 이게 쉽지 않음.
A와 B가 멀리 떨어져있고 직접 만날 수 없는 상황이라면
전화 등으로 key(128or256bits)를 전달 할 때 도청 등의 문제가 발생할 수 있기 때문.

따라서 public key crypto가 등장하였음!

A가 B에게 public key를 알려줌(공개적으로 알려줘도 상관 없음)
-> B가 A에게 받은 public key를 이용해서 메세지를 암호화해서 보냄.
-> 해당 메세지를 열어볼 수 있는 유일한 사람은 private key를 알고있는 A뿐임.

Asymmetric crypto primitives

- Crypto based on factoring

: RSA (메세지 암호화/복호화)
Rivest, Shamir, Adleman
35를 5*7로 소인수분해하는 것은 어렵지않지만 큰 수의 소인수분해는 어렵다는 것을 이용.

ex) p=3, q=5, N=15
(p-1)(q-1)과 서로소인 e 선택.
ed를 (p-1)(q-1)로 나눈 나머지가 1이 되도록 d 설정.

만약 N으로 p와 q를 알아내기 쉽다면(d를 알아낼 수 있으므로) RSA가 깨짐.
N으로 p,q를 알아내는 short cut이 없긴 하지만, RSA를 계속 안전하게 쓰려면
key size가 길어질 수 밖에 없음.

- Crypto based on discrete logarithms

: Diffie-Hellman key establishment (키 교환 목적)
A와 B가 인터넷 상에서 교환하는 메세지를 누가 보더라도 상관없도록 하고싶음.
즉, 안전하게 서로 공유하는 키를 만들고싶음. -> 디피헬만 공식에 따라 각자 비밀값을 선정함
-> 그 비밀값으로 계산한 어떤 값을 상대방에게 보냄.
-> 본인의 비밀값과 상대방에게 받은 공개값으로 계산함.(계산 결과 동일하다는 보장이 있음)
이때, A나 B가 보낸 공개값을 전부 공격자가 가로채더라도 A나 B가 계산한 값을 계산할 수 없음.

discrete logarithms (이산 로그) 개념을 활용하였음.

- Elliptic curve cryptography

: ECC 타원 곡선 암호화 (서명/서명 검증, 암호화/복호화)
elliptic curve 개념 활용.
RSA보다 key size가 짧음, 서명/서명 검증 속도 빠름.

* Elliptic Curve란?

암호학에 갖다쓰기 위해 타원 곡선 상의 점을 정의하였음.
암튼 더하기를 저렇게 정의하니까 안전성 보장됨.(계산 과정 식은 암기할 필요x)

* ECC Diffie-Hellman
: ecc 응용. 안전하게 키 공유하기

- Certification authorities(CAs)

: PKI
public key 기반 시스템을 위한 모든 요소.

* 인증서
: PKI중에 가장 핵심적인 요소.
어떤 대상에게 발급된 인증서인지와 그 대상에게 발급된 public key가 인증서에 담겨있음.

1) 인증서가 valid한지 확인해야함(폐기여부, 유효기간)
- certificate revocation list (폐기된 인증서 리스트) 확인
- OSCP(Online Certificate Status Protocol): 인증서 폐기여부(유효한지)알려줌
(OSCP 방식을 더 많이 씀)

2) 인증서 조작 여부 확인

3) CA 서명 검증도 해야함
- CA의 public key가 필요함(priv로 서명하면 pub로 검증)

==> 전부 통과하면 인증서를 받아들임

Public key crypto 정리

RSA
- (pubA, privA)쌍. pubA로 암호화, privA로 복호화
- (pubA', privA')쌍. privA'로 서명(signing), pubA'으로 검증(verification)
Diffie-Hellman
: 안전한 key exchange가 목적. descript log에 기반함.
ECC
- 암호화/복호화(가능하지만 RSA보다 속도가 느려서 거의 사용 안함)
- 서명/서명검증
- ECC Diffie-Hellman (key exchange)

Public key crypto 활용

Confidentiality
메세지를 수신자의 public key로 암호화해서 보내면,
그 메세지는 오직 그 public key와 쌍이되는 private key를 알고있는 상대방만 열어볼 수 있음.

다만, ①hash > ②,③ symmetric > ④public 순서로 빠르기때문에
④(public key crypto)를 꼭 써야하는 경우가 아니라면 안쓰는 게 좋음(성능 구림)
Authentication
private key로 인증
디지털서명은 integrity(진실성) & non-repudation(부인 방지)을 제공함

* non-repudaton
: A(고객)가 B(증권사)에게 [삼성전자, 100주, 55000, 매수]라는 M(메세지) 보냄.
이때 h(M)을 같이 보내면 공격자가 hash function을 아므로 안전하지 않음.
따라서 h(keyA-B, M)을 같이 보내자! (=MAC)

-> 주가가 떨어져서 A가 매수 취소하고싶어짐. 매수한 적 없다고 발뺌함.
-> B가 A고소. 근데 A의 승소가능성 있음.
왜냐면 keyA-B를 B도 알고있기 때문.(B도 주문내역 조작 가능)

==> 그래서 등장한 게 '서명'임.

A가 B에게 M과 서명을 같이 보냄.
-> 이번에는 B가 승소할 가능성이 훨씬 큼. 서명 만들 때 사용한 private key는 A만 알기 때문!
누군가 private key를 해킹했다고 하더라도 그건 A의 관리 소홀 잘못임.

* MAC (message authentication code)
: h(keyA-B, M)와같은 keyed-hash. 이때 괄호 안의 콤마는 단순히 이어붙인 걸 의미함.
Hybrid Encryption (Digital Envelope)
①hash > ②,③ symmetric > ④public key 순서로 빠르기때문에
public key crypto는 이왕이면 안쓰는 게 좋음.
근데 AES(③)같은거는 A와 B사이에 이미 key가 안전하게 공유되어있어야 하는데
그거를 ④로 하기도 함.

⑤ Digital signatures (전자 서명)

Data integrity + Message authentication + Non-repudation

A('나')가 B에게 보내는 내용이 A가 확인한 내용이 맞다라는 것을 B에게 알려주고 싶음.
-> A가 어떤 문서에 private key를 이용해서 서명을 함. -> 서명을 문서와 같이 보냄.
-> B는 A의 서명이 문서에 대한 서명이 맞다는 것을 public key로 검증 함.
(ex 돈을 지불 받을 수 있다는 보장이 되었으므로, 판매자B가 안심하고 A에게 물건을 보냄)

전자서명 동작 원리

- Public Key : 자물쇠(Encryption)-열쇠없어도 잠글 수 있음, 검증(Verification)
- Private Key : 열쇠(Decryption)-열려면 열쇠 필요, 서명(Signing)

* 비트코인에서는 서명/서명검증을 ECC(ECDSA)로 함.
근데 RSA방식으로 서명/검증하는것도 많이 쓰임.