해시함수
해시함수 (Hash function) : 데이터 입력보다 작은 형태의 고정된 값으로 출력값을 생성하는 함수
- 해시 함수의 출력값은 입력 데이터의 디지털 지문 역할을 한다.
해시함수 성질
- 고정 길이의 출력
- 빠른 계산 속도
- 메시지가 다르면 해시 값도 다르다.
즉, 해시함수는 출력값을 통해 입력값을 찾는 것은 쉽지 않다.
왜 해시함수를 사용하는가?
- 메시지 무결성(integrity)제공한다. (원본 메시지가 변조되지 않음을 보장해주는 성질)
- 암호학적으로 원본 메시지에 대응하는 메시지 변조 감지 코드를 생성하기위해 사용한다.
암호학적 해시함수 (Cryptographic hash function) : 특정한 보안 성질들을 추가적으로 제공하는 해시함수
1. 역상 저항성(Preimage resistance)
중간에 가로채도 알 수 없어야한다.
파란색 네모칸 = Digest(Hash함수를 통과 하기전의 원본 데이터를 메시지 라고 부르고 통과된 이후의 데이터를 다이제스트라고 부른다.
2. 제2 역상 저항성
(보통 h()와 메시지M이 주어지고 h(M')을 알 수 없어야하는 특징)
3. 충돌 저항성
위의 3가지를 지키지 못할경우 공격자는 어떠한 메시지에 대해서 위조된 메시지를 생성하는등 여러가지 취약점이 발생한다.
해시함수 공격
제2 역상 저항성에 대한 공격: x에 대해 h(x)=h(x')를 만족하는 x'이 반드시 존재한다.
즉, 무제한 영역에서의 입력값들이 해시함수를 거쳐 정해진 한정된 영역의 출력값으로 맵핑이 되면 어쩔 수 없이 제2 역상이 존재할수밖에 없다.
제2 역상을 어떻게찾나?
- 전수 조사 공격: 무작위로 x'를 선택하여 h(x)=h(x')를 만족하는지 확인 => DES나AES의 대칭키 찾는것과 동일
ex) 현재 컴퓨팅 능력에서의 출력 길이가 n-bit 이면 공격자는 2^n번 정도의 계산을 수행해야함 -> 현실적으로 불가 따라서 n은 224 이상 권장한다.
-왼쪽 문장을 오른쪽 문장으로 위조하고 싶은상황-
왼쪽 문장이 해시함수를 거쳐 나온 출력값 x와 동일한 출력값을 갖는 y를 (이때 y는 오른쪽 문장이 해시함수를 거쳐 나온 출력값) 바꿔치기 하는 것이다. 하지만 오른쪽 문장을 해시 함수에 넣었을때 x와 동일한 y가 나올 확률은 매우 적다.
- "Alice의 월급은 일억원(一億원) 으로 한다"
- "Alice의 월급은 일억원(壹億원) 으로 한다"
- "Alice의 월급은 100,000,000원 으로 한다"
- "Alice의 월급은 100000000원으로 한다"
- "Alice의 월급은, 100,000,000원으로 한다"
- "Alice가 받을 월급은 100,000,000원이다" 등등
- 충돌 저항성에 대한 공격: h(x)=h(x')를 만족하는 서로 다른 x,x'를 찾는것
동일한 의미의 다양한 문장을 생성하여 hash값을 계산한다 => 오리지널 hash값과 동일한 값이 나올때까지
이를 행할 수 있는 근거: 해시함수의 특징인 '한비트만 바뀌어도 출력은 다르다' 라는 성질을 이용하여 계속 전수조사 해보는것
- 충돌쌍을 찾는 문제는 생일 문제와 동일
만약 해시함수의 출력 길이가 n비트라면 2^n/2번의 입력값을 무작위로 뽑아서 해시값을 계산하면 충돌쌍을 찾을 수 있다.
해시함수 응용
암호학적해시함수의 단방향성과 충돌 저항성이 충분히 보장된다면 온라인 입찰에서도 사용이 가능
메시지 인증 코드
vs 메시지 변조 감지 코드(MDC)
- 해시함수를 이용한 메시지 변조 감지 코드는 -> 메시지 무결성보장
메시지 인증
메시지 인증 코드(MAC)
- 송신자와 수신자가 공유한 키를 사용 -> 메시지 인증보장
- MDC vs MAC*
즉, MAC의 데이터 출원 인증은 'Bob이 생성한거다','Alice가 생성한거다'가 아닌 'Bob과Alice 둘중 하나가 생성한거다' 이기때문에 데이터 출원 인증은 할 수 있으나 부인방지가 안되는 기법이다.
메시지 인증 코드(MAC)에 대한 공격
- 재전송 공격(Replay attack): 저장해둔 정당한 MAC값을 반복해서 전송하는 방법
)))
)))
재전송 공격 방어 방법
-
- 순서 번호(sequence number): 송신 메시지에 매회 1씩 증가하는 번호를 붙인다.
- 타임 스탬프(timestamp): 송신 메시지에 현재 시각을 넣는다. (송수신자 사이의 동기화 필요)
- 비표(nonce): 송신자에게 일회용의 랜덤한 값을 전송, 메시지와 비표를 합해 MAC값 계산, 비표 값은 통신 때마다 교체한다.
메시지 인증 코드(MAC)로 해결할 수 없는 문제
- 제 3자에 대한 메시지 인증 불가 -> 키를 공유한 사람들만 메시지를 인증할 수 있으며, 제 3자는 검증 불가 => 제 3자가 인증하기 위해서는 송수신자 간에 공유된 키를 "안전하게" 알려줘야 한다.
- 부인 방지 불가
)
Java 실습
)
댓글