[목차]
1. 일방향 해시 함수
2. 일방향 해시 함수의 응용
[일방향 해시 함수]
■ 파일의 진위
■ 일방향 해시 함수란?
■ 일방향 해시 함수의 성질
■ 해시 함수 관련 용어
1. 파일의 진위
어제 저장한 파일과 오늘의 파일 비교
밤새 맬로리가 파일을 변경했는지 어떤지를 조사하고 싶다.
무결성(Integrity)
파일이 변경되지 않았음
■ 파일의 지문(fingerprint)
범죄 수사에서 지문을 채취하는 것과 마찬가지로 앨리스가 만든 파일의 "지문"을 채취할 수 없을까?
파일 전체를 비교하는 대신에 작은 지문만을 비교하는 것만으로도 무결성을 확인할 수 있다면 매우 편리
# diff file1.txt file2.txt
# md5sum file1.txt; md5sum file2.txt
2. 일방향 해시 함수란?
일방향 해시 함수(One-way hash function)란?
일방향 해시 함수는 바로 파일의 지문을 재취하는 기술
일방향 해시 함수가 만들어내는 "해시 값"은 메시지의 지문에 해당
일방향 해시 함수(One-way hash function)
입력과 출력이 각각 1개씩 있다.
입력은 메시지(message)
출력은 해시값(hash value)
일방향 해시 함수는 메시지를 기초로 해서 해시 값을 계산
■ 일방향 함수의 예(단순 설명을 위한 예이다.)
입력: 임의의 숫자
처리: 입력되는 숫자를 23으로 나누는 메커니즘
출력: 그 몫을 소수로 표시했을 때 소수점 이하 7자리부터 10자리까지 4자리 숫자
입력: 345689
처리: 345689 ÷ 23
출력: 7391
몫: 15029.95652173913043... 이므로 7자리부터 10자리의 수는 7391
■ 일방향 해시 함수는 메시지를 기초로 해서 해시 값을 계산
■ 일정한 크기의 출력
해시 값의 길이는 메시지의 길이와는 관계가 없다.
메시지가 1비트라도, 1메가바이트라도, 100기가바이트라도 일방향 해시 함수는 고정된 길이의 해시 값을 출력
예: SHA-1의 출력은 항상 160비트(20바이트)
3. 일방향 해시 함수의 성질
임의의 길이 메시지로부터 고정 길이의 해시 값을 계산한다.
해시 값을 고속으로 계산 할 수 있다.
메시지가 다르면 해시 값도 다른다.
일방향성을 갖는다.
1) 고정 길이의 출력
어떠한 크기의 메시지라도 크기에 관계없이 입력으로 사용할 수 있어야 한다.
어떤 길이의 메시지를 입력으로 주더라도 일방향 해시 함수는 짧은 해시 값을 생성
2) 빠른 계산 속도
해시 값 계산은 고속이어야 한다.
메시지가 길어지면 해시값을 구하는 시간이 길어지는 것은 어쩔수 없다.
현실적인 시간 내에 계산할 수 없다면 소용이 없다.
3) 메시지가 다르면 해시 값도 다르다.
메시지가 1비트라도 변화하면 해시 값은 매운 높은 확률로 다른 값이 되어야 한다.
4) 일방향성을 갖는다.
해시 값으로부터 메시지를 역산할 수 없다는 성질
메시지로 부터 해시 값을 계산하는 것으 간단히 할 수 있다.
해시 값으로부터 메시지를 계산하는 것은 불가능해야 한다.
5) 기타
■ 해시 함수의 충돌
충돌(Collision)
2개의 다른 메시지가 같은 해시 값을 갖는 것
충돌 내성(Collision Resistance)
충돌을 발견하는 것이 어려운 성질
■ 충돌내성(Collision Resistance)
[참고] 해시 함수의 성질
* 일방향성
* 강한 충돌 내성: 2개의 해시 값이 같은, 2개의 메세지를 찾을 없게 하는 성질
* 약한 출돌 내성: 2개의 해시 값이 같을 때, 2개의 메세지가 같다는 것을 찾을수 없게 하는 성질
프리이미지 저항성(역상 저항성)
y = h(M)에 대해 메시지 M을 찾는 것이 계산적으로 불가능
어떤 해시 값에 대해서, 원래 입력 값을 찾는 어려워야 하며, 이를 일방향성(One-wayness)이라고 한다.
제2 역상 저항성(약한 충돌 내성)
h(M) = h(M'), M≠M'을 만족하는 다른 입력 값 M'을 찾는 것이 어려움
어떤 입력 값에 대하여, 그 입력값의 해시값과 같은 해시값이 갖는 또다른 입력값을 찾는 것이 어려워야 한다.
충돌저항성(강한 충돌 내성)
h(M) = h(M')과 같이 동일한 다이제스트를 가지는 2개의 메시지(M, M')를 구하는 것이 계산적으로 불가능
다른 표현: 강 일방향성 -> 서명문 M과 그 해시값 H=h(M)이 주어졌을 때 H=h(M')가 되는 M'을 찾는 것이 계산상 불가능
같은 해시값을 갖는 두 입력값을 찾는 것이 어려워야 한다.
4. 해시 함수 관련 용어
일방향 해시 함수
메시지 다이제스트 함수(Message Digest Function)
메시지 요약 함수
암호적 해시 함수
일방향 해시 함수이 입력이 되는 메시지
프리-이미지(Pre-Image)
해시 값은
메시지 다이제스트(Message Digest)
핑거프린트(Fingerprint)
해시 값(Hash Value)
무결성
완전성
보전성
[일방향 해시 함수의 응용]
■ 소프트웨어의 변경 검출
■ 패스워드를 기초로 한 암호화
■ 메시지 인증 코드
■ 디지털 서명
■ 의사난수 생성기
■ 일회용 패스워드
1. 소프트웨어의 변경 검출
자신이 입수한 소프트웨어가 변경 되었는지를 확인하기 위해 일방향 해시 함수를 사용
(예) md5sum, sha512sum, ...
(예) httpd.apache.org/download
(예) 포렌식에서 파일 무결성 확인
* 포렌식 보고서 내용 중 일부 내용(구글 검색: "포렌식 보고서")
2. 패스워드를 기초로 한 암호화
패스워드를 기초로 한 암호화(Password based Encryption, PBE)에서 사용
PBE에서는 패스워드와 솔트(salt)를 섞은 결과의 해시 값을 구해 그것을 암호화 키로 사용
패스워드 사전공격(Dictionary attack) 방어
(예) 리눅스(SHA512)/윈도우 시스템(NTLM)의 encrypted password
(예) 패스워드 크랙
* john the ripper
* 카인과 아벨
3. 메시지 인증 코드(MAC, Message Authetication Code)
"송신자와 수신자만이 공유하고 있는 키"와 "메시지"를 혼합해서 그 해시 값을 계산한 값
통신 중의 오류나 수정 그리고 "가장(spoofing)"을 검출 가능
SSL/TLS에서 이용
(예) ssh 통신 중의 MAC
(예) https 통신 중의 MAC
(예) IPsec 기반 VPN의 통신 중의 MAC
4. 디지털 서명
현실 사회의 서명(사인)이나 날인에 해당하는 온라인 상의 서명
처리시간 단축을 위해 일방향 해시 함수를 사용해서 메시지의 해시 값을 일단 구하고, 그 해시 값에 대해 디지털 서명을 수행
(예) 메일 서명(GPG 키)
(예) 패키지 서명(GPG 키)
5. 의사난수 생성기(PRNG)
암호 기술에 필요한 난수
"과거의 난수열로부터 미래의 난수열을 예측하는 것은 사실상 불가능"이라는 성질이 필요
그 예측 불가능성을 보증하기 위해 일방향 해시 함수의 일방향성을 이용
6. 일회용 패스워드
일회용 패스워드, 원타임 패스워드(One-Time Password)
정당한 클라이언트인지 아닌지를 서버가 인증할 때에 사용
일방향 해시 함수를 써서 통신 경로 상에 흐르는 패스워드를 1호(one-time)만 사용하도록 고안
패스워드가 도청되어도 악용될 위험성이 없다.
(예) 은행에서 발급하는 암호카드를 대신할 수 있는 OTP
- 금융거래(ex: 이체) => 개인 인증서(인증서암호), 암호카드(OTP)
|
일방향 해시 함수의 예 |
■ MD4, MD5
■ SHA-1, SHA-2/SHA-3(SHA-256, SHA-384, SHA-512)
■ SHA(Advanced Hash Standard), SHA-3
■ RIPEMD-160
■ LSH(Lightweight Secure Hash)
1. MD4, MD5
MD4
Rivest가 1990년에 만든 일방향 해시 함수
128비트의 해시 값
Dobbertin에 의해 충돌 발견 방법이 고안
현재는 안전하지 않다.
MD5
Rivest가 1991년에 만든 일방향 해시 함수
128비트의 해시 값
암호해독에 취약함을 보여주는 여러가지 암호 해독 방법들이 개발
MD5가 완전히 뚫린 것은 아니지만, MD5 내부 구조의 일부에 대한 공격 방법이 몇 개 발견
사용을 권장하지 않는다.
2. SHA(Secure Hash Algorithm)
미국 국가안보국(NSA)이 1993년에 처음으로 설계했으며 미국 국가 표준으로 지정되었다. SHA 함수군에 속하는 최초의 함수는 공식적으로 SHA이지만 SHA-0라고도 불린다.
SHA-0는 얼마지나지 않아 표준이 폐기되었고, 1995년에 SHA-1이 새로 출판된다. SHA-1은 SHA-0의 압축 함수에 비트 회전 연산을 추가한 것이다. NSA에 따르면, 암호학적 보안을 감소시키는 문제점을 고쳤다고 한다.(실제 문제점을 공개하진 않음)
SHA-0와 SHA-1은 최대 264비트의 메시지로부터 160비트의 해시값을 만들어 낸다. 로널드 라이베스트가 만든 MD4와 MD5 해시함수에서 사용했던 것과 비슷한 방법에 기초한다.
이후, 4종류의 변형, 즉 SHA-224, SHA-256, SHA-384, SHA-512가 더 발표되었다. 이들을 통칭해서 SHA-2라고 하기도 한다. 2002년에 SHA-1과 함께 정식표준으로 지정되었다.
SHA2부터 뒤에 비트수가 붙는데, 주로 이렇게 다양한 비트들은 암호연산의 키 길이와 비례한다.
[표] SHA 알고리즘 비교
|
알고리즘 |
해시값 크기 |
내부상태 크기 |
블록 크기 |
길이 한계 |
워드 크기 |
과정 수 |
사용되는 연산 |
충돌 |
|
SHA-0 |
160 |
160 |
512 |
64 |
32 |
80 |
+,and,or,xor,rotl |
발견됨 |
|
SHA-1 |
160 |
160 |
512 |
64 |
32 |
80 |
+,and,or,xor,rotl |
발견됨 |
|
SHA-224 /256 |
224/256 |
256 |
512 |
64 |
32 |
64 |
+,and,or,xor,shr,rotl |
|
|
SHA-384 /512 |
384/512 |
512 |
1024 |
128 |
64 |
80 |
+,and,or,xor,shr,rotl |
|
(출처) 위키백과
1) SHA-1
NIST(National Institute of Standards and Technology)에서 제작
160비트의 해시 값
SHA(Advanced Hash Standard)
1993년에 미국의 연방정보처리표준
SHA-1
1995년에 발표된 개정판
입력: 메시지 길이 상한 264bits 미만
출력: 160 bits 해시값
블록크기: 512 bits
2) SHA-2
SHA-256
입력: 메시지의 길이 상한 264 bits 미만
출력: 256 bits 해시 값(32 bytes)
SHA-384
입력: 메시지의 길이 상한 2128 bits 미만
출력: 384 bits 해시 값(48 bytes)
SHA-512
입력: 메시지의 길이 상한 2128 bits 미만
출력: 512 bits 해시 값(64 bytes)
|
[참고] 264 bits |
|
2^64 = 18,446,744,073,709,600,000: 약 천팔백경(약 18 EB)
Bytes -> KB -> MB -> GB -> TB -> PB -> EB -> ZB -> YB |
3) SHA(Advanced Hash Standard)와 SHA-3
SHA-1의 강한 충돌 내성 침해
NIST는 SHA-1을 대체하는 차세대 일방향 해시함수로 2007년에 "SHA-3" 선정 시작
AES와 같은 경쟁 방식으로 표준화
2012년 선정 완료
- KECCAK(케챡)을 표준으로 선정
- 이것이 SHA-3
3. RIPEMD-160
RIPEMD-160
1996년에 Hans Dobbertin, Antoon Bosselears, Bart Preneel이 제작
160비트의 해시 값
European Union RIPE 프로젝트로 만들어진 RIPEMD 함수의 개정판
4. LSH(Lightweight Secure Hash)
해시함수 LSH
TTA(한국정보통신기술협회)에 NSR에서 제안한 국내표준 해시함수(2015.12)
주요 특성
개발연도: 2014년
알고리즘 구분: 해시 함수
출력 길이: 224비트, 256비트, 384비트 또는 512비트
구조: Wide-pipe Merkle Damgaard 구조
성능/활용
다양한 SW 환경에서 국제 표준(SHA2/3) 대비 2배 이상 성능
메시지 인증, 사용자 인증, 전자서명 등 다양한 암호 응용 분야
|
일방향 해시 함수의 SHA-1 |
■ SHA-1
■ SHA-512
1. 일방행 해시 함수 SHA-1 개요
■ SHA-1 구조
입력: 최대 264 bits 미만 메시지
출력: 512 bits 메시지 다이제스트 => 160 bits 해시값
블록 크기 : 512 bits
■ SHA-1 처리 단계
패딩(Padding)
W0 ~ W79 계산
블록 처리
단계 1 ~ 단계 80 처리
2. 패딩(Padding)
목적: 512비트 블록 만들기(1추가 + 데이터 크기 표시)
패딩(Padding)?
메시지 뒤에 여분의 데이터를 부가하여 메시지의 길이가 512비트의 정수배가 되도록 하는 것
패딩의 예
입력: Hello. (6바이트(48비트))의 메시지
- ASCII 코드로 부호화하여 2진수로 표현하면
- 여기에 1을 붙인다.
H e l l o .
01001000 01100101 01101100 01101100 01101111 00101110
01001000 01100101 01101100 01101100 01101111 00101110 1
메시지의 길이가 512비트의 정수배가 될때까지 0이라는 1비트의 값을 부가
단, 마지막 블록의 마지막 64비트는 메시지 길이정보 영역으로서 비워둔다.
"Hello."의 경우
* 원래 메시지 길이(48비트) 정보 저장을 위해 끝의 64비트를 뺀 나머지를 0으로 채워 넣는다.
* 512 - 64 = 448 비트가 될때까지 0을 부가
길이 정보 추가
데이터 길이: 48 bits를 2진수로 표현하면
데이터 길이: 48 = 32 + 16 = 0011000
3. W0 ~ W79 계산
목적: 복잡성 구현(XOR, Rotation L)
입력 블록 512 bits마다 32 bits×80개(2560 bits)의 값(W0 ~ W79)을 계산
* W0 ~ W15 : 32 bits × 16
* W16 : 32 bits × 1
* W17 ~ W79 : 32 bits × 63
입력 블록 512 bits를 32 bits×16개로 분할하여 W0 ~ W15로 이름을 붙인다.
W16부터 W79는 아래와 같이 계산
* W16 = (W0 ㊉ W2 ㊉ W8 ㊉ W13)을 1비트 회전
* Wt = (Wt-16 ㊉ Wt-14 ㊉ Wt-8 ㊉ Wt-3)을 1비트 회전, t=17~79
1비트 회전한 모양
■ 01001000 01100101 01101100 01101100를 1비트 회전한 모양
4. 블록 처리
목적: 복잡성 구현(and, or, xor, +)
입력 블록에 대해 80 단계씩의 처리를 행한다.
입력 블록의 정보를 기초로 내부 상태(160비트)를 변화
|
일방향 해시 함수의 SHA-512 |
■ SHA-512 구조
입력: 최대 2128 bits 이하 메시지
출력: 512 bits(64 bytes) 메시지 다이제스트
입력 데이터는 길이 1024비트 블록으로 처리
■ SHA-512 처리 단계
패딩 비트 붙이기
길이 붙이기
MD 버퍼 초기화
1024-비트(128-워드)블록 메시지 처리
출력
■ SHA-512를 이용한 메시지 다이제스트 생성
■ 1024비트 한개에 대한 SHA-512 처리
■ SHA-512의 안정성
2017년까지 약점 발견된 것 없음
확률적 안정성
* 약 충돌성: 동일한 메시지 다이제스트를 갖는 두 개의 서로 다른 메시지를 찾는 난이도 연산
수행 수는 2256
* 강 충돌성: 주어진 다이제스트와 동일한 다이제스트를 갖는 메시지를 찾는 난이도 연산
수행 수는 2512
■ SHA-3란 무엇인가?
SHA-3(Secure Hash Algorithm)
이론적 공격방법이 알려져 버린 SHA-1을 대신하는 새로운 표준의 일방향 해시 알고리즘
2012년에 KECCAK(케챡)이라는 알고리즘을 SHA-3으로 선정
■ SHA-3 최종 후보와 SHA-3 결정
SHA-2와 SHA-3 공존해서 사용
KECCAK이 SHA-3로 선정된 이유
* SHA-2와 전혀 다른 구조임
* 구성이 투명하여 구조를 해석하기 쉬움
* 다양한 디바이스에서 구동되고, 조합 형태로도 양호
* 하드웨어 상에 내장시 높은 고성능
* 다른 최종 목록과 비교하여 보안성이 높음
■ KECCAK(케챡)란 무엇인가?
SHA-3으로 선정된 일방향 해시 함수 알고리즘
해시 값으로서 임의 길이의 비트열 생성
SHA-2 비트 길이에 맞춰져 있음
SHA3-224, SHA3-256, SHA3-384, SHA3-512 4종류가 SHA-3으로 규정
입력 데이터 크기에 제한 없음
SHAKE128과 SHAKE256이라는 임의 길이의 출력을 가진 함수(XOF, Extendable-Output Function)를 규정
* SHAKE = Secure Hash Algorithm + KECCAK
■ 스펀지 구조(SHA3 구조)
SHA-1, SHA-2와는 전혀 다른 스펀지 구조가 사용
입력되는 메시지에 패딩을 시행한 후 흡수 단계(absorbing phase)와 추출 단계(squeezing phase)라는 두개의 상태를 통해서 해시 값을 출력
■ KECCAK에 대한 공격
MD 변환
MD4, MD5, RIPEMD, RIPEMD-160, SHA-1, SHA-2 등, 지금까지 거의 일방향 해시 함수 알고리즘에서 이용
SHA-1에 대한 논리적인 공격 방법이 발견
SHA-2는 SHA-1과 같은 MD 구조를 사용했기 때문에 근본적으로 문제를 해결할 필요가 있음
KECCAK은
MD구조와 다른 스펀지 구조로 만들어져 있기 때문에 SHA-1을 공격하는데 사용된 방법이 KECCAK에는 통용되지 않음
현재까지 공격 방법이 알려진 것이 없음
|
일방향 해시 함수에 대한 공격 |
충돌 공격(https://ko.wikipedia.org/wiki/충돌_공격)
역상 공격(https://ko.wikipedia.org/wiki/역상_공격)
생일 공격(https://ko.wikipedia.org/wiki/생일_공격)
무차별 대입 공격(https://ko.wikipedia.org/wiki/무차별_대입_공격)
레인보우 테이블(https://ko.wikipedia.org/wiki/레인보_테이블)
부채널 공격(https://ko.wikipedia.org/wiki/부채널_공격)
|
어떤 일방향 해시 함수를 사용하면 좋은가? |
MD5는 안전하지 않으므로 사용해서는 안됨
SHA-2는 SHA-1에 대한 공격방법에 대한 대처를 하여 고안했기 때문에 안전
SHA-3은 안전
자작 알고리즘은 사용해서는 안됨
[참고] 지디넷 기사
구글, 구형 암호기술 'SHA1' 허점 입증했다
http://www.zdnet.co.kr/view/?no=20170224153403&re=R_20170227105154
|
일방향 해시 함수로 해결할 수 없는 문제 |
일방향 해시 함수는 "조작 또는 변경"을 검출할 수 있지만, "거짓 행세"(위장) 검출은 못 한다.
인증:
* 이 파일이 정말로 앨리스가 작성한 것인지를 확인하는 것
* 인증을 수행하기 위한 기술
- 메시지 인증 코드
- 디지털 서명
|
참고문헌 |
"알기 쉬운 정보보호 개론", 히로시 유키 저(이재광 외 2 공역, 인피니티북스, 2017)
"네트워크 보안 에센셜 3판", 윌리엄 스톨링스 저(전태일 등역), 교보문고
"해시 함수 LSH", 한국정보통신기술협회, 2015.12
SHA - https://ko.wikipedia.org/wiki/SHA
[참고] 전자화페(암호화페)
전자화페 및 블라인드 서명(Blind signature)
https://life-with-coding.tistory.com/21
암호화페-1(분산네트워크 및 비트코인)
https://life-with-coding.tistory.com/22?category=799521
암호화페-2(BitCoin 및 Timestamp Server)
https://life-with-coding.tistory.com/23?category=799521
암호화페-3(블록체인에 기반한 거래과정)
https://life-with-coding.tistory.com/24?category=799521
|
제 08장 요점 정리 |
|
■ 예전 해시 알고리즘 (주의) 다음 알고리즘을 사용해서는 안된다. SHA-1 MD2 MD5 PIPEMD-160 Keccak ■ 현대 해시 알고리즘(Modern Hash Algorithms) SHA-2 SHA-224, SHA-256, SHA-384 SHA-512, SHA-512/224, SHA-512/256 SHA-3 SHA-224, SHA-256, SHA-384 SHA-512 BLAKE2 BLAKE2s BLAKE2b ■ 확장 가능 출력 함수(XOF) SHAKE(SHA-3 제품군) SHAKE128 SHAKE256 ■ 메시지 인증 코드 알고리즘(Message Authentication Code Algorithms) HMAC(Hash-based MAC) CMAC(Cipher-based MAC) Poly1305 |
'정보보안공부 > 정보보안전문과정' 카테고리의 다른 글
| 정보보안 과정 Day89 : NTLM 해시 크랙 / Yum repo 서명/검증 실습 / 해시 함수 테스트 (0) | 2021.01.13 |
|---|---|
| 정보보안 과정 Day88-1 : 해시 스크립트 제작 실습 / 암호크랙 실습 (0) | 2021.01.12 |
| 정보보안 과정 Day87-1 : 하이브리드 암호 시스템 (0) | 2021.01.11 |
| 정보보안 과정 Day87 : RSA 실습 (0) | 2021.01.11 |
| 정보보안 과정 Day86-1 : 공개 키 암호 실습 (0) | 2021.01.11 |