아인스트라세의 SW 블로그

CTF에서 크립토계열 문제들을 보면 이따금씩 등장하는 공격기법이다.

딱히 어려운 공격법은 아니니 곧바로 예시를 들면서 설명을 들어가자.

HMAC(Hash-based Message Authentication Code)

HMAC이 뭐냐면 Hash 기반의 MAC이다. 여기서 MAC은 Message Authentication Code인데, 일종의 전자서명이라고 보면 된다.

만약 A라는 사람이 B에게 "마트에서 계란 5개 사와"라는 메시지를 보낸다고 치자. 그런데 이 메시지가 B에게 도착했는데, A가 보낸게 맞고 다른 공격자가 임의로 변조시킨 메시지가 아니라는것을 알고 싶다고 하자.

이때 쓰이는 것이 MAC이다. A와 B가 공통적으로 공유하는 키 값이 있다고 하고, 공격자는 이 키를 모른다고 하자.

그러면 A는 메시지를 보내면서 key 값 뒤에 메시지를 붙인 뒤 해쉬를 취한 값으로 서명값을 만든다.

다음과 같은 모양이 나오게 된다.

signature = sha256( key + message )

만약 공유하는 비밀 키의 내용이 "CarpeDiem"이라고 하자.

그러면 서명값은 sha256("CarpeDiem마트에서 계란 5개 사와") 의 값이되게 된다.

그리고 이 서명값을 메시지와 같이 보낸다고 하자.

그러면 B는 메시지와 서명값을 받고, 본인이 가지고 있는 키를 기반으로 서명값을 만들었을때 이 서명값이 전달된 서명값과 일치하면 이 메시지는 A가 만든것이 맞다는 것을 알 수 있다.

공격자는 A와 B가 공유하고 있는 키 값을 알 수 없으므로 정당한 서명값을 만들 수 없다.

Hash Length extension attack

이러한 HMAC을 쓰는 경우 특정 조건이 맞으면 이 해쉬 길이 확장공격을 사용할 수 있다.

이 공격으로 공유되는 비밀 키 값은 알수가 없지만, 어떤 메시지와 서명값의 쌍을 안다면 메시지 뒤에 다른 문자열이 추가된 메시지와 그에 맞는 정당한 서명값을 만들 수 있다.

사전 조건

공격을 하기 위해 필요한 조건들은 몇 가지 정보들이다. 다음 내용들을 알면 공격이 가능하다.

1. 키의 길이

2. message의 내용

3. message에 대한 정당한 서명값

4. 해시 알고리즘의 종류가 Merkle-Damgard construction에 기반한 것들(MD5, SHA-1, SHA-2)

만약 아까 이야기한 예시를 계속해서 들면 키의 길이가 CarpeDiem인 것은 모르더라도 9글자인 것을 알고, "마트에서 계란 5개 사와"가 메시지인 것을 알고, 이 메시지에 대한 서명 값이 0xdeadbeef라는 것을 안다고 가정하자.

그러면 이 정보를 바탕으로 공격자는 뒤에 공격자가 원하는 메시지가 추가된 메시지와 서명값을 만들어낼 수 있다.

가령 공격자가 "그리고 고기도 2kg 사와"라는 메시지를 뒤에 추가하려고 한다고 하자.

그러면 이 공격을 통해서 공격자는 "마트에서 계란 5개 사와 그리고 고기도 2kg 사와"라는 메시지에 대한 정당한 서명값을 알아낼 수 있다.

실제로는 기존 문장과 추가 된 문장 사이에 Null byte 값들이 여러개 추가될 수 있다.

공격 예시

여기서 설명하는 내용은 위키 백과와 같은 예시이다.

원래 데이터가 아래와 같다고 하자

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo

Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

여기에 공격자는 마지막에 파라메터를 추가하고자 한다.

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

그러면 공격이 이루어진 데이터는 다음과 같은 형태를 띄게 된다.

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x02\x28&waffle=liege

New Signature: 0e41270260895979317fff3898ab85668953aaa2

사이에 Null byte들이 많이 들어가게 되는데, 저 Null byte로 해시함수를 계산할때 내부 구조를 적절히 바꾸어서 하는 방식이라고 한다.

방어법

이 취약점은 Merkle–Damgård construction를 갖는 해쉬함수를 MAC에 오용해서 나타나는 취약점이라고 한다. 이 구조의 해시함수는 충돌이 잘 일어나지 않는 것그러므로 해당 구조에 해당하지 않는 해쉬함수(SHA-3)를 사용하면 된다.

공격용 툴들

이 Hash length extension attack을 직접 구현해서 써먹기에는 어려우므로 공개된 라이브러리들을 쓰면 좋다. HashPump는 커맨드라인에서 실행할 수 있는 형태의 툴이며, hlextend는 파이썬에서 사용할 수 있는 라이브러리 형태로 제공된다.

https://github.com/apoirrier/CTFs-writeups/blob/master/TAMUCTF2020/Crypto/Eternal%20Game.md

https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction

https://github.com/bwall/HashPump

https://en.wikipedia.org/wiki/Length_extension_attack

https://github.com/stephenbradshaw/hlextend

이번 포스팅에서는 인코딩과 암호화 및 해시에 대하여 설명해보고자 한다.

자주 혼동되는 개념이기도 하고 처음에 접하면서 햇갈려하는 사람들이 꽤 있어서 명확하게 구분을 지어보려고 한다.

인코딩(Encoding)과 디코딩(Decoding)이란?

일단 인코딩에 대하여 이야기해보겠다. 인코딩(encoding)은 code화 한다는 뜻이다. 무언가를 코드로 바꾼다는 뜻이다.

반대로 디코딩(decoding)은 코드에서 원래 모습으로 되돌리는 것이다.

약간 햇갈리는 개념이 될 수 있는데, 이 단락은 이해가 안되면 그냥 넘어가도 좋다.

인코딩이란 심볼을 코드로 바꾸는 것이고, 디코딩은 코드를 심볼로 다시 바꾸는 과정이다.

여기서 심볼은 뜻을 가진 무언가라고 보면 되고, 코드는 뜻을 갖지 않은 무언가이다.

즉, 인코딩은 의미(내용, 혹은 뜻)을 기호로 바꾸는 과정, 디코딩은 그 반대의 과정이다.

그렇다면 코드(code)는 무엇일까?

코드는 인코딩 방법에 따라 각자 다른데, 여기서는 무언가를 나타내는 기호라고 생각하면 되겠다.

인코딩 방법에 따라서 각각의 코드가 무엇을 나타내는지는 달라지게 된다.

사실 컴퓨팅, 계산과학 등 컴퓨터와 관련된 분야에서 심볼과 코드의 경우, 보통 사람이 읽을 수 있는 내용들(심볼)을 컴퓨터가 인식할 수 있는 데이터(이진 데이터, bit)로 변화하는 경우가 대부분이다.

따라서 심볼은 자연언어(영어, 한국어, 일본어 등등...)이거나 이미지(사람이 인식할 수 있는) 및 동영상, 소리 등이 되는 경우가 많고, 코드는 컴퓨터가 인식할 수 있는 바이너리 데이터가 되곤 한다.

모스 부호(Morse code)를 예로 들어보겠다. 모스 부호의 영어 단어도 Morse Code이다.

이 경우에는 알파뱃(A,B,C,...,Z)과 아라비안 숫자(0,1,2,3,...,9)가 심볼이 되고, 오른쪽에 점과 작대기가 코드가 된다.

점과 작대기는 사실 뜻이 없고, 알파뱃은 뜻이 있는데, 이 알파뱃들을 점과 작대기로 바꾸는 과정은 인코딩이 되고, 점과 작대기로 알파뱃으로 되돌리는 과정은 디코딩이 된다.

사실 이제 눈치채었겠지만, 인코딩과 디코딩 과정은 표현방식을 바꾸는 것 뿐이다. 그리고 그 과정에서 정보의 손실은 없다.

정보의 손실이 없다고 하는 것은 어떤 정보 A를 B로 인코딩 한 뒤, 다시 디코딩 했을 때 원래 정보 A에서 사라지는 정보가 없다는 것이다.

만약 어떤 영어 문장이 있었을 때, 이 문장에서 짝수번째 자리에 있는 알파뱃만을 모스부호 인코딩을 한 경우, 이 과정에서는 정보의 손실이 나타나게 된다.

왜냐면 다시 모스부호 디코딩을 한 경우 문장의 홀수번째 자리에 있는 알파뱃만이 남아있기 때문에, 짝수번째 자리에 있던 알파뱃의 정보는 손실이 되기 때문이다.

다른 유명한 인코딩은 무엇이 있을까?

다양한 인코딩들이 있다. 사실 인코딩은 심볼을 어떻게 코드화 하는지, 그리고 되돌리는지에 대한 규칙만 있으면 쉽게 만들 수 있다. 그래서 인코딩 이름에 encoding이 들어가는 경우도 있고, 그냥 무슨 무슨 코드라고 써있는 경우도 있다.

간단하게 봐서는 심볼과 코드의 단순 1대 1 대응관계라고도 볼 수 있다.

아스키 코드(ASCII Code)

아마 컴퓨터공학을 전공하면 처음으로 배운 코드 중 하나일 것이다. 로마자 알파뱃과 아라비아숫자, 그리고 일부 특수문자들을 1byte로 표현할 수 있는 간단한 코드이다. 이 문자들은 1byte 정수로 인코딩되며, C언어에서 문자(열)을 다룬다면 매우 친숙한 코드일 것이다.

유니코드 (UTF-8 혹은 UTF-16 등)

아스키코드의 경우 로마자 알파뱃만 표현이 가능하다는 불편한점을 개선한 코드로, 전 세계 모든 글자를 다 표현할 수 있는 문자 처리 방식이다. 사실 유니코드 자체는 인코딩이 아닌, 이런 전세계 모든 문자 각각을 1바이트 이상의 크기로 표현할 수 있게하는 방식이고 이를 실제로 구현한 인코딩이 몇 가지가 있는데 그 중 가장 유명한 녀석 중 UTF-8와 UTF-16이 있다.

Base 64 인코딩

Base 2라고 하면 2진법을 뜻하고 base 10이라고 하면 10진법을 뜻한다. 따라서 base64는 직역하면 64진법이 된다.(64진법이라고 부르는 경우는 없는데 이해를 돕기 위한 내용이다.)실제로도 64개의 서로 다른 printable한 문자들을 코드로 사용하고 있으며, 심볼로는 모든 범위의 바이너리 값을 표현할 수 있도록 고안된 인코딩 방법이다.

이미지나 동영상 등 바이너리 데이터를 깨지지 않는 출력가능한 문자로 표현하기 위해 자주 사용되는 녀석 중 하나이다.

uuencoding

요녀석은 자주 나타나지는 않는데 이 녀석도 바이너리 데이터를 printable 한 값으로 변환시킬 수 있는 인코딩방법이다.

URI Encoding(% encoding)

URI에서 일부 특수문자들 등을 나타낼 때 사용하는 인코딩 방법으로, 인코딩 방식이 % 뒤에 16진수 hex 값 2글자가 들어가는 방식의 인코딩이라서 퍼센트 인코딩이라고도 부른다. 네이버 주소창에서 아무 한글로 검색한 뒤, URL창을 보면 마지막 URI 쿼리스트링 부분에 %로 인코딩 된 부분들을 쉽게 볼 수 있다.

인코딩은 왜 하는 것일까?

인코딩을 하는 이유는 상황별로 조금 다를 수 있긴 하다. 하지만 일단 컴퓨터라는 것 자체가 0과 1로 이루어진 bit들이 모여서 각종 작업을 하는데, 이때 한글이나 영어와 같은 데이터들을 처리해야하는 경우가 항상 있다. 그러면 컴퓨터는 어차피 숫자만 다루기 때문에, 한글과 영어와 같은 심볼들을 숫자 Code로 맵핑해야 한다.

이런 경우 문자열 인코딩(Character encoding)이 필연적으로 필요해진다.

또한 어떤 값들을 네트워크나 다른 영역으로 전송해야 하거나 전송받아야 하는 경우, 서로 다른 플랫폼이라서 데이터를 표현하는 방식이 다르더라도 서로 호환되도록 공통적인 데이터 표현방식이 필요할 수 있다. 마치 세계 공용어로 영어가 쓰이면 지구 모든 사람이 영어를 할 줄 안다면 세계 누구와도 언어가 통할 수 있듯이, 그러한 표준화된 데이터 표현 방법을 정의한다고 보면 된다.

따라서 인코딩의 목적은 정보의 호환성이 되겠다. 

암호화(encrypt)와 복호화(decrypt)란?

인코딩과 암호화를 많이 햇갈려하곤 한다. 그런데 둘은 목적 자체도 다르고 성질도 다르다. 인코딩은 표현 방법을 바꾸는 것이고, 암호화는 남이 정보를 알아보지 못하게 하는 것이다.

암호화의 목적

암호화의 목적은 남들이 정보를 알아보지 못하게 만드는 것이다. 평문(plain text)을 암호화하면 암호문(cipher text)이 되고, 암호문을 복호화하면 평문이 된다.

그리고 여기서 '남'이란 암호 키가 없는 사람이다. 암호 키가 있는 사람은 복호화를 할 수 있고, 암호키가 없는 사람은 복호화를 할 수 없다. 즉, 키가 없으면 원래 평문이 어떤 값인지 알 수 없다는 것이다.

여기서 인코딩과 암호화의 첫번째 차이가 나왔다. 바로 '키'의 존재 유무이다.

암호의 종류

암호 부분은 자세히 들어가면 굉장히 복잡하다. 보통 암호를 금고에 많이 비유를 하는데, 일단 암호 시스템의 구성요소는 4가지라고 보면 된다.

평문과 암호 알고리즘 그리고 키와 암호문이 된다.

평문을 암호 알고리즘과 키를 통해서 암호화를 하면 암호문이 된다.

평문은 중요 정보라고 보면 되고, 암호 알고리즘은 금고이다. 그리고 키는 금고의 패스워드가 된다.

금고안에 들어간 중요 정보는 암호문이라고 보면 된다.

암호는 키의 형태에 따라 대칭키, 비밀키 암호가 있고, 대칭키는 암호화에 쓰이는 키가 복호화에도 쓰이는 것이다.

비밀키는 키가 비밀키 및 공개키로 한 쌍이 있고, 비밀키로 암호화하면 공개키로 복호화가 되고, 공개키로 암호화를 하면 비밀키로 복호화가 되는 특이한 방식의 암호이다.

암호 알고리즘의 종류

암호 알고리즘도 다양한 종류가 있는데, 유명한 몇 가지를 알아보도록 하겠다.

DES(Data Encryption Standard)

매우 오래된 대칭키 암호 알고리즘이다. 취약성하다고 알려져서 요즘은 그냥은 사용하지 않는다.

AES(Advanced Encryption Standard)

DES가 취약하다고 알려져서 이를 대체하기 위해 새로이 만들어진 대칭키 암호 알고리즘이다.

RSA(Rivest Shamir Adelman)

암호 알고리즘을 만든 3명의 이름을 본 따서 이름을 지은 공개키 암호 알고리즘이다. 지금까지도 널리 잘 쓰이고 있는 암호 알고리즘이며, 공개키 암호 알고리즘의 대표격이다.

암호화와 정보의 손실

아까 인코딩은 정보의 손실이 없다고 했는데, 그렇다면 암호화는 정보의 손실이 있을까?

답은 구현에 따라 다르다이다. 단방향 해시함수를 이용해서 암호화를 하는 경우가 있는데, 이 경우는 해시함수의 특성상 정보 손실이 일어나고 복호화가 불가능하다.

 이는 조금 특별한 경우인데, 보통 계정 정보의 패스워드를 이 방식을 통해서 암호화하여 저장한다.

패스워드가 동일한지는 입력한 패스워드를 단방향 해시함수로 암호화 한 뒤, 기존에 저장된 암호문과 일치하는지를 확인한다.

-------------------------------------------------------------------

https://ko.wikipedia.org/wiki/%EB%AA%A8%EC%8A%A4_%EB%B6%80%ED%98%B8