▣ 해시 알고리즘, 해시 함수, SHA(Secure Hash Algorithm), DES, AES, 블록체인
■ 해시 알고리즘(Hash Algorithm)
- 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
- 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array
- 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠름
■ 해시함수를 활용하여 제공하는 대표적인 서비스
해시기반 메시지 인증 코드 (HMAC)구현
무결성 검증을 통해 데이터 변경/변조 여부 검출(MIC)
단방향 암호화 알고리즘을 통한 패스워드 암호화(MD5, SHA256 등)
■ 해시 함수 특징
| 메시지의 압축(Message Digest) | 가변길이 원본 메시지에 대해 고정 길이 해시값을 생성 |
| 계산의 용이성 | x가 주어지면 H(x)는 계산적으로 용이해야 함 |
| 일방향성 | H(x)=y를 만족하는 x를 찾는 것은 계산적으로 불가능해야 함 - 역상 저항성(Pre-image resistance) 최초, 해시값(y)이 확인된 상태
입력값(x)을 찾는 것은 계산적으로 불가능 |
| 약한 충돌 회피성 | x가 주어졌을 때 H(x) = H(x')인 x(≠x')을 찾는 것은 계산적으로 불가능 함 - 제2 역상 저항성(Second Pre-image Resistance) h(x) = y 일때, x와 y를 알고 있는 경우, h(x') = y 인 x'을 찾는 것은 불가능해야 함 최초, 입력값(x)이 확인된 상태
동일한 해시값(y)이 나오는 다른 입력값(x')을 찾는 것은 계산적으로 불가능 |
| 강한 충돌 회피성 | H(x) = H(x')인 서로 다른 임의의 두 입력 x와 x'을 찾는 것은 계산적으로 불가능 - 충돌 저항성(Collision Resistance) 최초, 확인된 정보가 없는 상태
동일한 해시 값(y)의 서로 다른 입력 값(x, x')을 찾는 것은 계산적으로 불가능 |
임의의 길이 이진 수열을 입력 받아 고정된 길이의 이진 수열을 출력
압축( Compression ) -> h:D→R, |D|>|R| many to one => Collision
계산 용이성 h(x)
■ 해쉬함수의 분류
■ 해쉬 함수의 특성
* MDC( Modification Detection Code )의 성질
- Preimage resistance (one-way)
주어진 y에 대하여 h(x) = y가 되는 x를 찾는 것이 어렵다.
- 2nd preimage resistance (weak collision resistance)
주어진 x에 대하여 h(x) = h(x')가 되는 x'≠x 를 찾는 것이 어렵다.
- Collision resistance (strong collision resistance)
h(x) = h(x')이 되는 x≠x'의 쌍을 찾는 것이 어렵다.
OWHF : preimage resistance, 2nd preimage resistance
CRHF : 2nd preimage resistance, collision resistance
* MAC( Message Authentication Code )의 성질
- 계산 저항성 (computation resistance)
(xi, hk(xi)) 쌍이 주어지든, 주어지지 않았든 간에
∀x≠xi 에 대하여 MAC 값 hk(x)를 계산하기 어렵다.
■ MDC(메시지 변경 감지 코드) - 무결성
- 메시지의 무결성(메시지가 변하지 않았다는 것.) 보장하는 메시지 다이제스트.
- 수신한 메시지의 MDC를 계산하고 송신측이 보내준 MDC와 비교하여 동일한지 비교함.
- 과정
① 메시지의 무결성을 제공하기 위해서 송신자 A는 송신할 메시지를 이용하여 메시지 다이제스트(암호학적 해시함수를 이용한 해시값)를 만듦.
이때 생성된 메시지 다이제스트를 일반적으로 MDC라고 부름.
② 송신자 A가 메시지와 MDC를 수신자 B에게 보냄.
③ 수신자 B는 받은 메시지로 MDC를 만들고, 송신자 A가 보낸 MDC와 비교하여 메시지의 무결성을 확인함.
- 문제: 무결성은 인증가능 하지만 누가 보냈는지에 대한 메시지 출원인증이 안됨. → 즉, 메시지의 위조같은 적극적 공격은 메시지 인증으로 검출해야 함.
위의 그림을 보면 MDC는 신뢰성있는 채널을 통해 MDC가 전송된다는 가정을 한다.
따라서 MDC를 위해서는 신뢰성있는 채널이 있어야 만된다는 제약이 있으며, 그렇지 않으면 제 3자가 메시지를 위조해도 알아차리지 못하게 된다.
- 해결: MAC
■ MAC(메시지 인증코드, Message Authentication Code)의 개념
- MAC은 해시함수 + 대칭키로 메시지 무결성을 인증하고 거짓행세(메시지 인증으로 검출)를 검출.(메시지 인증: 올바른 송신자에게 온것을 인증하는 것)
- 무결성을 확인하고 메시지에 대한 인증을 하는 기술. -> 도청(소극적 공격) 방어, 변경과 거짓행세 검출 가능
- 임의 길이의 메시지와 송신자 및 수신자가 공유하는 키. 두 개를 입력으로 하여 고정 비트길이의 출력을 만드는 함수. 이 출력값을 MAC이라고 함.
- 적극적 공격인 데이터 위조 같은 것을 방어하는데 사용.
- 키 K는 오직 송,수신자만 알고 있음.
- 아래 그림에서 해시 함수 H에는 H(K||M) 처럼 두 개의 값이 입력되고 해시값 MAC이 생성됨.
- H(K||M) 에서 K+M의 순서로 입력이 되었는데, 순서는 바뀌어도 됨. H(M||K)도 되고,
H(K||M||K') 같이 다른 키를 붙여도 됨. (단, 이 경우에도 송수신자가 K, K'를 알고 있어야함.)
■ 충돌 해결
- Chaining
충돌이 일어날 경우 데이터들을 포인터를 이용해 서로 링크드 리스트(체인)형태로 연결하는 것
key값을 포인터로 이어서 연결
최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐
JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있음
- Open Addressing
모든 데이터를 테이블에 저장하는 방법
사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용
포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높음 하지만 테이블의 크기가 커질수록 장점이 사라짐
- Linear Probing
충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음인덱스에 저장
- Quadratic Probing
충돌시 i^2 만큼씩 이동
■ 해시 알고리즘 SHA(Secure Hash Algorithm)
SHA(Secure Hash Algorithm)은 해시함수를 이용해서 만든 해시 암호화 알고리즘의 모음임
미국 국가보안국(NSA)에서 1993년 처음으로 설계했고 미국 국가표준으로 지정됨
SHA종류로는 SHA-0, SHA-1, SHA-2, SHA-3 이런식으로 나타내는데, 실제 많이 사용되고 있는 함수 SHA-2임
digest 의 길이에 따라 SHA-224, SHA-256, SHA-384, SHA-512 나눌 수 있음
TLS, SSL, PGP, SSH, IPSec등 많은 보안 프로토콜과 프로그램에서 사용되고 있음
DES와 AES는 기밀성(노출방지)을 목적으로 사용하는 반면, SHA는 무결성을 보증
비트코인이나 이더리움에서 사용되는 SHA는 블록헤더, 전자서명, 공개키등 위변조 방지임
■ DES, AES 비교
| 비교의 근거 |
DES 데이터 암호화 표준 (Data Encryption Standard) |
AES 고급 암호화 표준 (Advanced Encryption Standard) |
| 기본 | DES에서 데이터 블록은 두 개의 절반으로 나뉨 | AES에서 전체 데이터 블록은 단일 행렬로 처리 |
| 원리 | DES는 Feistel Cipher 구조체에서 작동 | AES는 대체 및 치환 원리에 대해 연구함 non-Feistel 알고리즘, SPN 알고리즘 |
| 일반 텍스트 | 평문은 64 비트 DES의 키는 실제 64 비트지만, 7 비트마다 오류검출에 사용되는 Parity Bit가 1 비트씩 들어가기 때문에 실질적인 키의 비트를 56 비트 |
일반 텍스트는 128, 192 또는 256 비트 일 수 있음 |
| 키 크기 | DES는 AES와 비교하여 키 크기가 작음 | AES는 DES에 비해 키 크기가 큼 |
| 라운드 | 16 라운드 | 128 비트의 비밀키에 대해 10 라운드 192 비트의 비밀키에 대해 12 라운드 256 비트의 비밀키에 대해 14 라운드 |
| 반올림 이름 | 확장 순열, Xor, S-box, P-box, Xor 및 Swap. | Subbytes, Shiftrows, 믹스 열, Addroundkeys. |
| 보안 | DES에는 덜 안전한 키가 있음 | AES는 비교적 큰 비밀 키를 가지고 있기 때문에보다 안전 |
| 속도 | DES는 비교적 느림 | AES가 빠름 |
2019년 119번
정답 : 3번
블록체인에서는 각 개별 트랜잭션의 무결성 검증을 위해 해시트리(Hash tree, Merkle Tree)라는 자료구조를 이용하며, 암호화 기술로 단방향 암호화 알고리즘을 사용함
2020년 116번
정답 : 2번
1) 메시지의 압축(Message Digest) : 가변길이 원본 메시지에 대해 고정 길이 해시값을 생성
2) 맞음
3) 일방향성 : H(x')=y를 만족하는 x를 찾는 것은 계산적으로 불가능해야 함
4) 약한 충돌 회피성 : x가 주어졌을 때 H(x') = H(x)인 x'(≠x)을 찾는 것은 계산적으로 불가능 함
2018년 107번
정답 : 1번
- 해시함수를 활용하여 제공하는 대표적인 서비스
해시기반 메시지 인증 코드 (HMAC)구현
무결성 검증을 통해 데이터 변경/변조 여부 검출(MIC)
단방향 암호화 알고리즘을 통한 패스워드 암호화(MD5, SHA256 등)
- 재전송 공격 방지를 위해 주로 사용되는 기법
Timestamp, Sequence Number등이 활용됨
2021년 106번
정답 : 1번
SHA-3이 입력되는 데이터의 크기는 2의 128승-1로 제한되지 않음.
SHA-3는 SHA-2를 대체하기 위한 해시 암호 알고리즘임
미국 국립표준기술연구소(NIST)에서 공모를 통해 KECCAK 알고리즘을 SHA-3로 최종 선정하고 2015년에 발표
SHA-3는 SHA3-224, SHA3-256, SHA3-384, SHA3-512 4개의 해시함수와 SHAKE128, SHAKE256 6개의 확장 가능한 출력함수(Extendable-output functions, XOF)로 구성되어 있음
SHA-3는 스펀지 구조를 통해 입력된 메시지는 정해진 bitrate에 따라 f함수 출력과 XOR 연산 과정을 통해 흡수(absorbing)과정을 거치게 되고 마지막 압착(squeezing)과정을 통해 최종 해시값을 출력함
| 종류 | 출력 크기 | 블록크기 |
| SHA3-224(M) | 224 | 1152 |
| SHA3-256(M) | 256 | 1088 |
| SHA3-384(M) | 384 | 832 |
2021년 112번
정답 : 3번
블록체인에 기록된 정보는 공개 원장이기 때문에 누구나 접근이 가능하며, 한번 기록된 트랜잭션 정보는 위 변조 방지를 위해 수정이 불가능함
단, 일반적인 public blockchain이 아닌 private blockchain이나 consortium blockchain을 운영하는 경우 인가된 사용자만 블록체인 네트워크에 접속하도록 제한 할 수 있음
2021년 118번
정답 : 3번
주민등록번호와 바이오정보는 양방향 암호화, 비밀번호는 단방향 암호화를 적용해야 함
AES-256은 양방향 암호화 알고리즘이고, SHA-256은 단방향 암호화 알고리즘이므로, 주민등록번호와 바이오정보는 AES-256, 비밀번호는 SHA-256으로 암호화하는 것이 적절함
2011년 118번
정답 : 4번
■ 해시 함수 특징
- 메시지의 압축(Message Digest) : 가변길이 원본 메시지에 대해 고정 길이 해시값을 생성
- 계산의 용이성 : x가 주어지면 H(x)는 계산적으로 용이해야 함
- 일방향성 : H(x')=y를 만족하는 x를 찾는 것은 계산적으로 불가능해야 함
- 약한 충돌 회피성 : x가 주어졌을 때 H(x') = H(x)인 x'(≠x)을 찾는 것은 계산적으로 불가능 함
- 강한 충돌 회피성 : H(x') = H(x)인 서로 다른 임의의 두 입력 x와 x'을 찾는 것은 계산적으로 불가능
2012년 106번
정답 : 3번
2012년 112번
정답 : 3번
■ 해시 함수 특징
- 메시지의 압축(Message Digest) : 가변길이 원본 메시지에 대해 고정 길이 해시값을 생성
- 계산의 용이성 : x가 주어지면 H(x)는 계산적으로 용이해야 함
- 일방향성 : H(x')=y를 만족하는 x를 찾는 것은 계산적으로 불가능해야 함
- 약한 충돌 회피성 : x가 주어졌을 때 H(x') = H(x)인 x'(≠x)을 찾는 것은 계산적으로 불가능 함
- 강한 충돌 회피성 : H(x') = H(x)인 서로 다른 임의의 두 입력 x와 x'을 찾는 것은 계산적으로 불가능
2012년 118번
정답 : 2번
| 비교의 근거 |
DES 데이터 암호화 표준 (Data Encryption Standard) |
AES 고급 암호화 표준 (Advanced Encryption Standard) |
| 기본 | DES에서 데이터 블록은 두 개의 절반으로 나뉨 | AES에서 전체 데이터 블록은 단일 행렬로 처리 |
| 원리 | DES는 Feistel Cipher 구조체에서 작동 | AES는 대체 및 치환 원리에 대해 연구함 non-Feistel 알고리즘, SPN 알고리즘 |
| 일반 텍스트 | 평문은 64 비트 DES의 키는 실제 64 비트지만, 7 비트마다 오류검출에 사용되는 Parity Bit가 1 비트씩 들어가기 때문에 실질적인 키의 비트를 56 비트 |
일반 텍스트는 128, 192 또는 256 비트 일 수 있음 |
| 키 크기 | DES는 AES와 비교하여 키 크기가 작음 | AES는 DES에 비해 키 크기가 큼 |
| 라운드 | 16 라운드 | 128 비트의 비밀키에 대해 10 라운드 192 비트의 비밀키에 대해 12 라운드 256 비트의 비밀키에 대해 14 라운드 |
| 반올림 이름 | 확장 순열, Xor, S-box, P-box, Xor 및 Swap. | Subbytes, Shiftrows, 믹스 열, Addroundkeys. |
| 보안 | DES에는 덜 안전한 키가 있음 | AES는 비교적 큰 비밀 키를 가지고 있기 때문에보다 안전 |
| 속도 | DES는 비교적 느림 | AES가 빠름 |
2015년 107번
정답 : 3번
3)번은 일방향성 특징임
| 메시지의 압축(Message Digest) | 가변길이 원본 메시지에 대해 고정 길이 해시값을 생성 |
| 계산의 용이성 | x가 주어지면 H(x)는 계산적으로 용이해야 함 |
| 일방향성 | H(x')=y를 만족하는 x를 찾는 것은 계산적으로 불가능해야 함 |
| 약한 충돌 회피성 | x가 주어졌을 때 H(x') = H(x)인 x'(≠x)을 찾는 것은 계산적으로 불가능 함 |
| 강한 충돌 회피성 | H(x') = H(x)인 서로 다른 임의의 두 입력 x와 x'을 찾는 것은 계산적으로 불가능 |
2015년 115번
정답 : 2번
일방향 해시 함수는 무결성 검증은 가능하지만 별도의 인증 기능은 지원하지 않음
공개키 암호 : 공개키 암호의 인증모드(송신자의 개인키로 암호화) 사용 / 인증 송개송공
메시지 인증코드 : MAC, 인증과 무결성을 제공
디지털 서명 : 서명자의 개인키로 데이터 암호화 통한 인증