Hash Function & MAC
해시 함수는 데이터를 고정 사이즈 해시값으로 변환하는 함수이다.
해시 함수가 다음 조건을 만족하면 cryptographic hash function이 된다.
- one way property
현실적인 컴퓨팅 환경에서 해시값을 만들어내는 data object를 찾기 어려워야 한다.
입력값으로 출력을 만들어내는 것은 쉽지만, 반대로 출력이 주어졌을 때 이에 따른 입력을 찾기 어려워야 한다. - collision-free property
임의의 데이터를 고정된 데이터로 변환하는 만큼, 출력의 사이즈가 충분히 크지 않으면 서로 다른 입력값이 동일한 출력을 만들어낼 수 있다. 이런 현상을collision이라고 부른다.
해시 함수는 출력값의 길이를 조절해서collision이 거의 발생하지 않게 해야 한다.
secret key 를 입력값으로 받는 MAC Function 과 달리 Hash Function 은 키 없이 메시지를 바로 해시로 변환한다.
MAC
메시지 변환과 authentication을 겸하는 함수이다.
해시 함수 활용
- one-way password 제작
비밀번호를 해시 값으로 저장해서 유저와 주고받는다. 서버 상에도 원본 비밀번호는 저장되어있지 않다. - 보안
악성 코드나 악성 트래픽을 수집했을 때 해당 값을 해시로 저장해두고 나중에 위험 요소가 있는 데이터를 다운로드할 때 기존 해시와 비교하여 안전성을 검증한다.
collision-free property와 관련 있는 기능이다. - PRF, PRNG
랜덤 값을 제작할 때 해시 함수를 기반으로 할 수 있다.
cryptographic 해시 함수의 의미
Preimage
해시 함수의 입력값이다.
해시의 길이가 제한적인 만큼 해시 함수는 many to one 매핑 방식이기 때문에, 여러 개의 입력값을 쓰면 그 중에 몇 개 정도는 동일한 입력값을 가질 수밖에 없다.
Collision
x ≠ y 이고 H(x) = H(y) 인 상황을 말한다.
해시 함수는 collision을 최대한 줄이면서도 출력값 크기는 작아야 효율적이다.
요구사항
- preimage resistant(one-way property)
출력이 주어진다고 하더라도 대응하는 입력을 얻어내기 어려워야 한다. (결과와 관련된 조건) - second preimage resistant
입력 x가 주어질 때, x와 동일한 해시값을 만드는 또다른 입력값 y를 찾기 어려워야 한다. (결과가 아니라 입력과 관련된 조건) - collision resistant
collision을 최대한 줄여야 한다.
Birthday problems
cryptographic 해시 함수의 요구사항을 강의실에 존재하는 학생의 생일에 빗대는 문제이다.
collision이 발생하지 않게 하는 입력값의 최소치를 찾는 것이 목적이다.
preimage resistant - 한 반에 오늘 생일인 학생이 있을 확률은 학생 수가 많을수록 커진다. 이 확률이 1/2을 넘어서는 최소 학생 수를 구하는 문제이다.
n = 253
second preimage resistant - 학생 하나를 골랐을 때, 해당 학생과 같은 생일인 학생이 존재할 확률이 1/2을 넘어서는 최소 학생 수를 구하는 문제이다.
n = 254
collision resistant - 생일이 같은 사람 두 명이 존재할 확률이 1/2을 넘어서는 최소 학생 수를 구하는 문제이다.
n = 23
이 때 두 번째, 세 번째 해시 함수의 출력값이 비슷하다.
출력 space가 충분히 크면 출력값의 다양성을 보장할 수 있다.
현재 안전하다고 판단되는 알고리즘은 출력값이 2^454인 SHA-2이다.
colision resistant attacks
이런 공격 방식은 같은 해시값을 만들어내는 두 개의 메시지(혹은 데이터 블록)를 찾기 위해 전개되는데, 120비트 해시 함수를 1GHz 컴퓨터로 해석한다고 가정할 시 이론 상 35년이 걸린다.
Merkle-Damgard 방식
패딩으로 정렬한 메시지를 Compression function 을 이용해서 압축하는 방식이다. 데이터 입력이 들어올 때마다 하나의 블럭으로 압축한다.
여러 번 압축 함수를 이용한 후 마지막에 압축된 블럭을 해시의 결과로 출력한다.
SHA(secure hash algorithm)
SHA 는 NIST에서 제안한 해시 함수이다.
SHA-1 -> SHA-2 -> SHA-3 순서로 발전하였다.
이 중 SHA-3는 기존의 merkle-damgard 방식을 사용하지 않고 개발된 알고리즘이다.
SHA-3
SHA-1를 아직 사용하던 시절에 SHA-2는 이전 방식과 구조 등을 공유하는 부분이 많아서 위험 요소가 있었다. 때문에 2007년에 만들어진 것이 SHA-3이다.
SHA-3는 스펀지 구조를 사용한다(absorbing - squezzing pase로 나뉜다.)
하드웨어적으로는 구현이 빠르지만 소프트웨어적으로는 overhead가 많이 발생한다.
MAC
일반적인 cryptographic 해시 함수만 사용해서 권한을 검증하기에는 부족하기 때문에 비밀 키를 활용하는 MAC 검증이 필요하다.
공격자가 비밀 키를 모르면 관련된 MAC을 절대 만들어낼 수 없다.
해시 기반 MAC을 HMAC 이라고 부른다.
전자서명과 다른 점
MAC은 비밀 키 하나만으로 암호화, 복호화를 모두 진행하는 대칭 키 알고리즘이고 전자서명은 암호화 시 비밀 키, 검증 시 공개 키를 활용하는 비대칭 키 알고리즘이다.
Digital signature
MAC처럼 암호화 시 비밀 키, 검증 시 공개 키를 활용한다.
해시 값을 만들어내는 과정에서 비밀 키가 필요하고, 유저의 공개 키를 아는 누구나 메시지의 무결성을 검증할 수 있다.
Encryption scheme과 차이점
공개 키를 검증에 사용하는지 복호화에 사용하는지에 따라 다르다.
- 공개 키를 알고 있는 누구나 쉽게 전자서명을 검증할 수 있다.
- 방향성이 존재하는 인증 방식이다. 서명을 만든 사람은 서명에 대응하는 비밀 키를, 서명을 받은 사람은 검증하기 위한 공개 키를 가진다.
- 데이터를 받은 사람은 서명을 통해서 데이터를 보낸 사람이 신뢰 가능한지 판단한다.
- Non-repudiation(부인 방지) : MAC이나 Hash와 달리 권한을 가진 사람이 서명했다는 사실을 증명할 수 있다.
forgery
서명은 원래 키가 있어야 만들 수 있다. 정당한 비밀 키 없이 유효한 서명을 만들어내는 것을 signature forgery 라고 한다. 이 경우 해당 서명을 위조되었다고 한다.
Attacks in digital signature
key-only attack
공격자가 공개 키를 알고 있는 경우이다.
known message attack
공격자가 오간 메시지와 서명에 대한 정보를 가지고 있는 경우이다.
chosen message attack
공격자가 특정 메시지의 서명에 접근할 수 있을 때, 그 정보를 활용해서 다른 메시지의 서명을 위조하려는 공격이다.
generic, directed, adaptive 등 여러 가지가 있다.
generic
공격자가 공개 키를 알고 있으며 일반적인 메시지 집합의 서명에 적용해서 서명 알고리즘의 약점을 분석하거나 패턴을 얻기 위해 수행하는 공격이다.
directed
공격자가 특정 메시지의 서명을 얻는 것을 목적으로 한다.
adaptive
공격자가 서명을 요청한 결과를 바탕으로 다음 메시지의 서명을 또 요청하고, 이 과정을 반복해서 피드백을 거쳐가며 최종적으로 위조 목표를 달성하는 방식이다.
Forgeries
total break
공격자가 비밀 키를 변조한다.
universal forgery
모든 메시지에 대해 전자 서명을 위조할 수 있는 경우이다.
selective forgery
모든 메시지는 아니지만 선택한 메시지에 대해 위조할 수 있다.
existential forgery
검증 단계를 우회할 수 있는 메시지를 만들어내는 경우 존재적 위조라고 한다.
예를 들어 RSA signature를 위조하려면 아무 값을 비밀 키 S로 선정하고 메시지를 S^e로 만든다.
이후 verification 단계에서 비밀키를 지수승 하고 메시지와 비교하는데, 메시지가 S^e이기 때문에 일치해서 검증을 통과할 수 있다.
전자서명에서 값에 해시를 씌워서 전달하면 h(x) = S^e가 되는 x 값을 공격자 입장에서 찾아야 하기 때문에 위조를 방지할 수 있다.
디지털 서명 알고리즘
RSA signature
RSA 방식을 전자서명에 접목한 형태이다.
Elgamal signature
DLP에 기반하여 키값을 암호화한다.
y = g^x(mod p) 에서 pk는 y, g, p, sk는 x가 된다.
- 자체적으로 랜덤값을 만들 수 있다. 입력이 같아도 매번 랜덤 키를 이용해서 새로운 시그니처를 만들고, 시그니처를 두 개로 나눠서 전달한다.
Schnorr signature(슈노르 서명)
DLP를 적용한 암호화 방식이다.
Digital signature algorithm(DSA)
DLP를 적용한 암호화 방식. 표준으로 쓰인다.
비밀값 x값만 알고 있으면 유일한 서명을 찾아내는 것이 가능한데, 이것을 방지하기 위해 알고리즘을 추가했다.
g^e(1)과 y^e(2)를 곱한 값을 기존의 감마값과 비교하여 검증을 진행한다.
여기에서 g는 소수 q로 이루어진 집합 Z의 요소이고 감마는 서명 시 수식에 활용된 상수이다.
Elliptic curve digital signature algorithm
줄여서 ECDSA 라고 한다.
key
타원 곡선에서 제너레이터 G가 주어졌을 때 G가 몇 번 더해졌는지로 비밀 키를 만든다.
공개 키는 base point의 상수배(d배)인데, 이 d를 알아내기 어렵다는 점으로 비밀을 보장한다.
Certificate chain
인증서를 여러 개 사용하는 보안 방식이다.
단계별로 구성된 인증서가 하위 인증서를 검증할 수 있고, 최상위에 위치하는 인증서를 root CA 인증서 라고 한다. root CA는 스스로의 공개 키로 자기 자신을 인증하기 때문에 self-signed 인증서 라고도 한다.
루트 CA가 사용하는 브라우저의 트러스트 앵커에 해당한다면 사이트가 신뢰 가능하다고 볼 수 있다. 브라우저는 각 사이트의 인증서가 아니라 루트 CA를 신뢰한다.
