MD5

MD5(message digest 5)는 입력 데이터로부터 128 비트 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 알고리즘이다. 프로그램이 수정되었는지, 원본과 같은지를 확인하는 무결성 검사에 사용된다. 입력받은 메시지를 128비트로 압축하는 방식이며, 이전 버전으로는 MD2, MD4가 있다. 현재에는 1996년에 보안상의 결함이 발견되어 보안용으로 쓰는 것은 권장하지 않는다.

개요

MD5는 미국 MIT의 교수 로날드 리베스트(Ronald Rivest)가 개발한 전자서명, 응용 프로그램 등 정보보호를 목적으로 개발한 해시 알고리즘이다. 큰 파일들은 RSA와 같은 공개키 암호 사용법하에서 개인키와 함께 암호화되기 전에 안전한 방법으로 압축되어야만 한다. MD5 규격은 현재 IETF RFC 1321에 명시되어 있다. MD5 규격에 따르면, MD5 알고리즘에 입력된 어떤 두 개의 메시지가 동일한 메시지 축약을 결과로 내거나, 또는 어떤 메시지 축약을 통해 엉뚱한 메시지가 만들어지는 것은 "계산적으로 불가능"하다고 한다.

등장배경

1991년 미국 MIT의 교수 로날드 리베스트가 이전 버전인 MD4의 결함을 보안하기 위해 개발했다.

특징

• 임의의 길이로 입력받은 메시지를 512비트 단위로 처리해 128비트로 암호화한다.
• 입력 메시지의 길이 제한이 없다.
• 해시값 길이 : 128 비트
• 패딩 처리 : 메시지 길이를 512 비트 정수배로 만든다
• 해싱 충돌 방지 확률 : 약 2^64

비교

MD2

미국 MIT의 교수 로날드 리베스트가 만든 MD2는 8비트 컴퓨터에 최적화되어있는 반면 MD5는 32비트 컴퓨터에 최적화되어있다.

MD4

MD4는 3라운드에 걸쳐 처리하지만 MD5는 4라운드에 걸쳐 처리한다. MD4보다 MD5가 더 느리지만 더 안정적이다.

SHA-1

SHA-1은 로널드 리베스트가 개발한 MD 해시 함수와 비슷한 방법을 사용하지만 SHA-1이 MD5보다 속도가 더 빠르며 더 안정적이다.

알고리즘 구현

• Step1 : Append Padding Bits

입력받은 메시지의 길이가 512비트의 배수가 되게 패딩해야 하지만 첫 번째 단계에서는 512비트의 배수보다 64비트 모자라게(-64bit) 패딩해야 한다. 이때 마이너스 해 준 64비트는 패딩 전의 원래의 서명문 길이를 의미한다.

• Step2 : Append Length

Step1에서 제외시켰던 64비트를 채워준다. 패딩 전의 원래의 서명문 길이를 64비트로 표시하여 붙여준다. 이때 메시지의 길이가 2^64보다 클 경우, 낮은 64비트만 사용된다. 패딩이 완료되었다면 완료된 메시지를 16word단위로 M[0,,,,,,N-1]에 할당시킨다. 이때 M은 워드 단위를 의미하고, N은 16의 배수가 된다.

• Step3 : Initialize MD Buffer

MD 버퍼를 초기화한다. 128비트 버퍼는 해시 함수의 중간 값 그리고 최종 값을 저장할 때 쓰여지는데, 32비트의 레지스터 A, B, C, D로 표시한다. 메모리에 저장 시 MD5는 Little-endian 방식을 사용하길 규정하기 때문에 low order bytes를 먼저 저장해야 한다.

초기화한 형태는 이러하다.

word A: 01 23 45 67
word B: 89 AB CD EF
word C: FE DC BA 98
word D: 76 54 32 10

• Step4 : Process Message in 16-Word Blocks===

16 word(512bit) block 단위로 Message Disgest를 수행한다.

4라운드에 걸쳐 작업하는데

1Round F(x,y,z) == (x∧y)∨(~x∧z)
2Round F(x,y,z) == (x∧z)∨(y∧~z)
3Round F(x,y,z) == x⊕y⊕z
4Round F(x,y,z) == y⊕(x∧~z)
(∧,∨,~,⊕는 논리 연산자이다. )

이러한 형태의 함수로 3개의 32비트 워드(x, y, z)를 입력하여 32비트 워드의 출력을 생성하도록 정의한다. 각각의 라운드마다 16단계의 처리를 하는데, 4번의 라운드의 구조는 비슷하나 서로 다른 논리 함수로 구성된다. 각 라운드는 현재의 512비트 블록과 128비트 버퍼값인 A, B, C, D, 입력 메시지의 i번째의 32비트 내용의 입력으로 처리되는데 입력 메시지의 i번째의 32비트 내용은 총 64개로 1/4씩 각각의 라운드마다 입력된다.

• Step5 : Output

4번의 과정을 통해 나온 A, B, C, D의 값을 연결해 준다. 이때 A, B, C, D는 word이며 결과적으로 출력은 128bit(16byte)가 된다.

앞서 말했듯 Little-endian방식의 사용을 규정하기 때문에 low order bytes 순서대로 저장되어야 하며 ABCD의 순서 역시 어긋나면 안 된다.

문제점

MD5는 원래 공인인증서, MySQL, DB Password 알고리즘 등 다방면에서 사용됐으나 암호화의 방식이 MD5라는 것을 안다면 복호화가 쉽다는 문제점이 있다. 2008년 독일 베를린에서 개최된 해커 컨퍼런스 Chaos communication Congress에서 국제 보안 연구팀이 MD5를 이용한 피싱 공격 기술에 관해 발표했으며 SSL의 인증서 변조가 가능한 것이 발표되었다.

참고자료

• Margaret Rouse, 〈MD5〉, 《TechTarget》, 2017-07
• 〈제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
• 〈MD5, MD-5, MD4, MD-4 Message Digest 5, Message Digest 4〉, 《정보통신기술용어해설》, 2016-04-04

같이 보기

• 암호 알고리즘
• 합의 알고리즘
• 체인 알고리즘
• 블록체인
• 해시그래프
• 암호화폐

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반