[암호학 개념]

 

 

 

암호 알고리즘은 크게 3가지로 이루어져 있다.

 

1. 비밀키 알고리즘 -> 암복호화에 같은 비밀키 사용, 대칭키 알고리즘이라고도 불림

2. 공개키 알고리즘 -> 암호화는 공개키로, 복호화는 개인키로 동작, 비대칭키 알고리즘

3. 해시 알고리즘 -> 위 2개의 알고리즘과는 성격이 다른 암호 알고리즘

 

 

합동식

 

합동식은 두 정수 a, b 를 각각 정수 m으로 나눴을 때 나머지가 같은지를 판별하는 식입니다. a와 b 각각을 m으로 나눈 나머지가 같을 때, 수학적으로 a와 b가 mod m에 대해 합동(congruent)이라고 표현합니다.

예를 들어, 7과 17은 10으로 나눈 나머지가 같기 때문에 7과 17은 mod 10에 대해 합동이며 기호로는 

7 ≡ 17 (mod 10)로 나타냅니다.

 

a, b 가 mod m에 대해 합동일 경우 a, b 각각에 정수 x를 더하거나 빼거나 곱해도 여전히 합동입니다.

 

a ≡ b(mod m)

=> a+x ≡ b+x (mod m)

=> a - x ≡ b-x(mod m)

=> ax ≡ bx (mod m)​

​

그러나 나눗셈에 대해서는 성립하지 않습니다.

 

 

 

 

합동식에서 곱셈의 역원

정수 a, m에 대해 a x b ≡ 1(mod m)을 만족하는 b를 mod m에 대한 a의 곱의 역원이라고 부르며, a^(−1)로 표기합니다.

 

예를 들어 2 x 4 = 8 ≡ 1(mod 7)이므로 mod 7에서 2에 대한 역원은 4입니다.

역원은 a와 m이 서로소일 때에만 존재합니다.

 

 

 

 

 

---

비밀키 알고리즘

 

다른 알고리즘에 비해 역사가 가장 오래되었다. 암호의 역사는 기원전 1900년 까지 거슬러 올라가는데 세계 2차 대전 때 컴퓨터 발명되고 애니그마가 해독된 시점을 기준으로 고전암호와 현대암호가 나뉜다.

 

 

 

 

 

고전암호

 

치환암호(Substitution Cipher) -> 평문 상에 알파벳을 다른 알파벳으로 치환하는 암호

ex) 카이사르 사이퍼

 

단점 -> 빈도 분석으로 쉽게 해독 가능

 

 

다중 문자 치환 암호(Polyalphabetic Substitution Cipher) -> 평문의 한 문자가 암호문에서 여러 종류의 문자로 치환될수 있습니다.

ex) 비제네르 암호(Vigenere Cipher)

 

 

전치암호(Transposition Cipher) -> 평문을 구성하는 문자들의 순서를 재배열하여 암호문을 만듭니다.

ex) 스키테일 암호(Scytale Cipher))

 

 

 

공격방법 -> 전수 키 탐색 공격(Exhaustive Key Search Attack)과 빈도수 분석(Frequency Analysis)이 있습니다.

 

 

 

 

 

 

---

현대암호

 

1945년에 암호학자 Claude Shannon은 안전한 암호 시스템은 혼돈(Confusion)과 확산(Diffusion)의 성질을 만족해야한다고 발표했습니다. 현대의 많은 암호 시스템이 두 성질을 따르고 있습니다.

 

 

혼돈

혼돈은 암호문에서 평문의 특성을 알아내기 힘든 성질을 말합니다. 단일 치환 암호를 사용하여 같은 평문을 두 번 암호화하면 출력된 두 암호문은 서로 같습니다. 공격자는 암호문을 보고 평문이 무엇인지 유추하지는 못하더라도 암호문을 생성한 두 평문이 같다는 사실은 알 수 있습니다. 따라서 단일 치환 암호는 혼돈 성질을 만족하지 못하는 암호입니다.

 

 

확산

확산은 평문의 작은 변화가 암호문의 큰 변화로 이어지는 성질입니다. 이 성질은 대부분의 고전 암호에서 찾아보기 힘든 성질입니다.

 

 

 

 

 

 

---

대칭키 암호 시스템

 

블록 암호

블록 암호(Block Cipher)는 평문을 정해진 크기의 블록 단위로 암호화하는 암호입니다. 예를 들어 블록의 크기가 4바이트라면 평문을 4바이트의 블록으로 쪼개어 각 블록마다 암호화를 진행합니다.

 

만약 평문의 크기가 블록 크기의 배수가 아니어서 블록으로 균등하게 쪼갤 수 없다면, 평문뒤에 데이터를 추가하는 패딩(Padding)을 먼저 수행합니다. 패딩은 평문이 블록 크기의 배수가 될 때까지 데이터를 추가합니다. 블록 암호의 대표적인 예시로는 DES와 AES가 있습니다.

 

 

 

DES(Data Encryption Standard)은 1970년에 미국 정부가 만든 표준 암호이다. IBM에서 사용하는 암호 알고리즘을 약간 변형해서 만들었고 시기는 1970 ~ 2000년도에 사용되었다. 이후 AES라는 알고리즘으로 교체. DES는 키 길이 56비트이고 8바이트씩 잘라서 블록단위로 암호화를 진행한다,

 

 

AES(Advanced Encryption Standard)는 키 길이가 최소 128비트 이상이다. 미국 정부가 공모전을 진행해서 벨기에 수학자가 만든 암호를 채택해서 만든 알고리즘이다. 지금도 사용 중인 알고리즘으로 16바이트씩 잘라서 블록단위로 암호화를 진행한다.

 

 

 

 

 

 

 

 

 

 

---

AES 알고리즘

 

AES 알고리즘은 표준으로 선정된 이후부터 지금까지, AES에는 기밀성을 위협하는 치명적인 취약점이 발견되지 않았습니다. 또한 CPU 제조사들이 AES 연산을 위한 명령어를 따로 정의해 주어서 암호화, 복호화의 성능도 뛰어납니다. 이런 이유로 현대에는 대칭키 암호 알고리즘을 사용할 때, 일반적으로 AES가 사용됩니다.

 

 

https://lemon-soju.tistory.com/237

[AES 개념]

 

 

---

블록암호 운영모드

 

ECB(Electronic CodeBook mode)

-> 각 블록을 각각 암호화 -> 안전 X -> 블록 내용이 같으면 만들어진 암호문도 같아진다. -> 사용 X

 

P0 -> C0

P1 -> C1

P2 -> C2

 

ex) 암호화 -> openssl enc -aes-128-ecb -e -in plain.txt -out cipher.bin -K 00112233445566778899aabbccddeeff

명령어를 사용하면 12바이트 길이의 plain.txt가 암호화되고 블록단위를 맞추기위해 패딩값이 삽입되어 16바이트 크기의 암호문이 만들어진다. 암호화된 파일은 xxd cipher.bin 명령어로 내용을 볼 수 있다.

 

ex) 복호화 -> openssl enc -aes-128-ecb -d -in plain.txt -out cipher.bin -K 00112233445566778899aabbccddeeff

 

만약 이미지 파일을 ECB로 암호화하면 헤더 부분만 수정하면 이전의 그림의 형태가 보이기 때문에 안전하지않다.

CBC(Cipher Block Chaining mode)

-> 이전 암호문 블록을 현재 plain 블록과 xor연산해서 계산하므로 블록 내용이 같아도 결과가 달라짐. IV(Initial Vector)이 필요함. 병렬 계산이 불가능하므로 성능이 떨어짐

 

CTR(CounTeR mode)

-> CBC와 보안 수준은 비슷하나 성능이 더 좋다.

 

 

 

 

 

 

 

 

Padding

 

만약 블록 암호에서 plain이 블록단위로 딱 맞아 떨어지지 않는다면 패딩(padding)으로 채워준다.

 

PKCS#5 -> 만약 7바이트가 남는다면 7이라는 값으로 모자란 길이 7만큼 채운다. -> 어디까지가 패딩된 부분인지 판별할 수 있어야함

 

 

 

 

보안 3대 요소(CIA)

 

Confidentiality -> 기밀성 -> 비밀키를 소유한 사람만 복호화할 수 있다.

 

Integrity -> 무결성 -> 변조를 탐지할 수 있어야한다.

 

Availability -> 가용성 -> 성능도 중요

 

 

 

 

 

위에서 설명한 ECB, CBC, CTF 같은 운영모드는 기밀성은 보장하지만 무결성을 보장하지 않는다. 무결성 속성까지 만족하는 Authenticated Encrption에 존재하는 운영모드로 GCM mode가 있다. 

 

 

 

 

 

 

---

스트림 암호

스트림 암호(Stream Cipher)는 송신자와 수신자가 공유하는 데이터 스트림을 생성하고 이를 평문에 XOR하는 암호입니다. 평문을 P, 암호문을 C, 스트림을 X라고 할 때, 암호문 C는 C = P ⊕ X로 생성됩니다. X ⊕ X=0이므로 수신자는 C ⊕ X = P ⊕ X ⊕ X = P로 암호문을 복호화할 수 있습니다. 만약 송신자와 수신자가 평문 길이 만큼의 스트림을 매번 공유할 수 있다면, 스트림을 모르는 공격자는 암호문을 복호화할 수 없습니다. 하지만 평문과 같은 길이의 스트림을 안전하게 공유할 수 있다면, 스트림을 공유하는 채널로 평문을 공유하면 되므로 암호화가 필요하지 않은 환경임을 의미합니다.

그래서 일반적으로 송신자와 수신자는 스트림을 공유하는 대신, 시드(Seed)라 불리는 작은 값을 공유하고, 이를 사전에 합의된 함수의 인자로 넣어 스트림을 각자 생성합니다. 스트림 암호는 단순한 연산으로만 구현되므로 속도가 매우 빠릅니다. 그러나 블록암호보다는 안전하지 못하다고 알려져서 연산 능력이 부족한 임베디드 기기나 속도가 중요한 환경에서만 제한적으로 사용됩니다.

 

 

대칭키 암호 시스템의 장점과 단점

대칭키 암호 시스템은 일반적으로 공개키 암호 시스템에 비해 속도가 빠릅니다. 그러나 송신자와 수신자가 사전에 키를 교환해야 한다는 제약이 있습니다. 또한 대칭키 암호 시스템에서는 그룹 내에 여러 명이 있을 경우 두 사람마다 서로 다른 키를 생성해서 사용해야 합니다. 즉, N명의 사람이 있을 때 총 N(N−1)/2개의 키가 필요합니다. 이후에도 새로운 상대와 통신할 때마다 계속 키를 생성해야 합니다. 공개키 암호 시스템에는 이와 같은 키 생성의 불편함이 없습니다.

 

 

 

 

 

---

공개키 암호 시스템(비대칭키)

 

공개키 암호 시스템의 장점과 단점

 

공개키 암호 시스템에서는 그룹 내의 사람들이 각자의 공개키와 비밀키를 만든 후 공개키만 공개하면 되므로 N명의 사람이 있을 때 2N개의 키만 필요합니다. 이는 N(N-1)/2개의 키가 필요했던 대칭키 암호 시스템보다 훨씬 적습니다. 또한 한 번 키를 생성하고 나면, 새로운 상대와 통신하더라도 자신이 키를 다시 만들어야할 필요가 없습니다.

반면, 공개키 암호 시스템은 일반적으로 대칭키 암호 시스템에 비해 다소 복잡한 연산이 필요하므로 속도가 느립니다. 또한 대칭키 암호와 같은 안전성을 제공하려면, 대칭키 암호보다 긴 키를 사용해야 합니다. 예를 들어 대칭키 암호 시스템인 AES는 192 비트 이상의 키를 사용하면 충분히 안전하지만, 공개키 암호 시스템인 RSA는 2048 비트 이상의 키를 사용할 것이 권장됩니다.

 

 

 

디피-헬먼 키 교환

 

엘리스와 밥은 노란색 물감통을 가지고 있다. 각자 노란색 물감통에 자신의 비밀 색상 물감을 넣은 뒤 서로에게 보낸다.

 

중간에 이브라는 악당이 전송되는 물감을 가로챈다. 하지만 일방향 함수와 같이 물감을 원래 색깔로 되돌릴 수는 없다.

 

앨리스와 밥은 수신한 물감에 자신의 물감을 섞는다. 그러면 서로 같은 색깔의 물감이 된다. 

 

 

결론 -> 공개적으로 비밀 열쇠를 정할 수 있다.

 

 

 

---

디피의 비대칭 암호

 

앨리스가 밥에게 상자를 보내고 싶다. 앨리스는 우체국에 공개되어있는 밥의 자물쇠로 상자를 잠근다. 열쇠는 밥에게만 있으므로 밥을 제외한 그 누구도 상자를 열 수 없다.

 

 

 

결론 -> 디피가 비대칭 암호 개념을 생각해냈지만 비대칭 암호를 찾지는 못했다.

 

 

 

 

 

---

One-Way 해시함수

 

 

해시 함수(Hash Function)는 임의 크기의 데이터를 입력으로 받아서, 고정된 크기의 데이터를 반환하는 함수이며, 해시 함수의 반환값은 해시 값(Hash Value)이라고 부릅니다. 암호학적 해시 함수(Cryptographic Hash Function)는 해시 함수 중에서 특정 성질을 만족하는 함수를 의미합니다.

 

 

암호학적 해시 함수의 성질

암호학적 해시 함수(Cryptographic Hash Function)는 다음 성질을 만족하는 해시 함수를 말합니다.

1. 제 1 역상 저항성(Preimage Resistance): 암호학적 해시 함수 H에 대해 y가 주어졌을 때 H(x)=y를 만족하는 x를 찾는 것이 어렵다. 이는 함수가 일방향 함수여야 함을 의미합니다.
2. 제 2 역상 저항성(Second Preimage Resistance): 암호학적 해시 함수 H에 대해 x가 주어졌을 때 x != x', H(x)=H(x′)을 만족하는 x'을 찾는 것이 어렵다.
3. 충돌 저항성(Collision Resistance): 암호학적 해시 함수 H에 대해 x != x', H(x)=H(x′)을 만족하는 x, x′을 찾는 것이 어렵다.

추가로, 현대에는 눈사태 효과(Avalanche Effect)를 이상적인 해시 함수의 조건 중 하나로 보기도 합니다. 이 성질은 대칭키 암호 시스템의 확산과 비슷하게 입력에 조그만 변화가 발생하면, 해시값에도 큰 변화가 발생하는 성질입니다.

 

 

 

 

생일 역설(Birthday Paradox)은 암호학적 해시 함수의 충돌 저항성과 관련된 이론 중 하나입니다.

 

 

생일 역설 문제

한 반에 30명의 학생이 있다. 이들 중에서 생일이 같은 학생이 있을 확률은 얼마일까? A. 2.7% B. 11.7% C. 24.6% D. 40.6% E. 70.6%

가능한 생일의 수는 365개인데 학생은 30명밖에 없으니 생일이 같은 학생이 있을 확률은 낮을 것으로 예상됩니다. 하지만 정답은 무려 70.6%인 E입니다. 이처럼 일반적인 직관과 다르게 전체 인원이 적어도, 그 안에 생일이 같은 학생이 높은 확률로 존재하는 현상을 생일 역설이라고 합니다.

 

위 문제의 결과는 공역의 크기가 365인 해시 함수 H가 있을 때, H에 대해 무작위로 30개의 해시값을 생성하면 충돌이 발생할 확률이 70%이상인 것으로 재해석될 수 있습니다.

이 문제를 조금 더 일반화해서 계산한 결과, 공역의 크기가 A인 해시 함수 H가 있을 때, H에 대해 무작위로 A^(1/2)​개의 해시 값만 생성하면 그 안에 충돌이 발생할 확률이 유의미하게 높다고 알려져있습니다.

다시말해, 아무리 정교한 해시 함수를 만들더라도, 공역의 크기가 작으면 해시 함수는 충돌 저항성을 만족하기 어렵습니다.

암호학적 해시 함수를 만들 땐 이를 고려하여 공역의 크기를 크게 만들어야 합니다. 어떤 해시 함수의 입력이 256비트의 출력에 대응될 때, 이 함수의 공역의 크기는 2^256이며, 대략 2^128 ≃ 10^36번 이상의 연산을 해야 충돌 쌍을 찾을 수 있다고 기대할 수 있습니다. 이 정도 연산은 현실적으로 불가능하므로, 이 해시 함수는 충돌 저항성을 만족합니다.

 

 

 

---

MD series -> MD5는 Ronald Lorin Rivest가 1991년에 만들어낸 해시 함수입니다. 이 코스를 작성하는 2020년 기준으로는 다양한 취약점이 발견되어 더는 안전한 해시 함수로 여겨지지 않지만, 몇몇 구형의 시스템에는 아직 MD5가 사용되고 있습니다.

 

SHA series -> SHA256은 미국 표준 기술 연구소(NIST)에서 만들어낸 해시 함수입니다. 현재까지 취약점이 발견되지 않아 해시가 필요한 대부분의 곳에서 사용되고 있습니다. SHA256 이전에 SHA0, SHA1가 있었으나 모두 취약점이 발견되어 현재는 사용하지 않을 것이 권장됩니다.

 

 

 

 

해시함수 사용용도

 

1. Intergrity 증명 -> 데이터가 변조되지 않았는가? -> 해시 함수는 웹, 네트워크, 블록 체인 등 컴퓨터와 연관된 여러 분야에서 무결성을 입증하는 수단으로 사용되고 있습니다. 송신자가 데이터와 함께 데이터의 해시 값을 보내면, 수신자는 받은 데이터로부터 해시값을 생성하고, 이를 송신자가 보낸 해시값과 비교하여 받은 데이터가 변조되지 않았는지 확인할 수 있습니다.

 

2. 비밀번호 저장 -> 리눅스에서 shadow 파일에 평문으로 사용자들의 비밀번호를 저장할 수 없으므로 해시로 저장 -> 암호학적 해시 함수는 일방향 함수이므로 비밀번호를 해시 값으로 저장하면 데이터베이스가 유출돼도 비밀번호의 원본이 알려질 가능성이 거의 없습니다.

 

사전공격에 취약? -> salt를 추가하면 같은 입력이라도 해시값이 다르게 나오므로 안전

 

 

 

 

 

해시함수 취약점

 

 

1. 해시 충돌 -> 만약 공격자 증명서가 다른 사람과 겹친다면 다른 사람 신분을 악용할 수 있음 

2. 다른 파일이 같은 MD5 hash를 가짐 -> 파일의 Intergrity를 증명할 수 없음

 

 

 

 

 

---

메세지 인증 코드(Message Authentication Code, MAC)

 

MAC은 데이터와 함께 보내는 추가적인 정보로, MAC을 통해 데이터의 무결성을 보장할 수 있고 또 현재 통신 중인 상대방이 위장한 공격자가 아니라는 사실 또한 알아낼 수 있습니다.

 

MAC을 만들어내기 위해서는 메시지와 키가 필요합니다. 이때 키는 송신자와 수신자 사이에서 사전에 공유되어있어야 합니다. 송신자는 수신자에게 메시지를 보낼 때, 메시지와 키를 이용해 계산된 MAC 값을 같이 보냅니다. 수신자는 기존에 알고 있던 키를 이용해 수신한 메세지의 MAC을 계산하고, 이를 전송받은 MAC과 일치하는지 비교합니다. 공격자가 메시지를 위조하고 싶으면 위조된 메시지에 대한 올바른 MAC값을 알아야 하는데 키를 모르는 공격자로서는 MAC을 계산할 수 없습니다.

 

 

 

HMAC

MAC을 만드는 방법은 크게 암호학적 해시 함수를 이용하는 방법과 블록 암호를 이용하는 방법으로 나눌 수 있습니다. 그중에서 HMAC은 해시 함수를 기반으로 하는 MAC입니다. 실제 표준으로 정의된 HMAC은 키의 길이, 블록의 길이를 인자로 하는 복잡한 함수입니다. 여기서는 이를 다소 간소화하여 다음과 같은 HMAC함수가 있다고 하겠습니다.

 

HMAC(K, M) = H(K ∣∣ M)

 

∣∣는 비트 배열을 연결하는 연산자입니다. 예를 들어 01 || 110 = 0111001입니다. 즉 이 함수는 키와 메시지를 붙인 것의 해시 값으로 HMAC을 생성합니다. HMAC을 사용하면, 메세지를 도청당해도 역상 저항성으로 인해 공격자가 HMAC에 사용된 키를 알아낼 수 없으며, 메세지를 위조하면 위조한 메세지에 대한 올바른 HMAC을 생성할 수 없습니다.

 

 

 

 

 

---

RSA

 

RSA 암호 알고리즘은 공개키 암호시스템의 하나로, 전자 거래, 금융 거래, 인증서 등 다양한 분야에서 가장 보편적으로 사용되는 암호 및 인증 알고리즘입니다. RSA는 암복호화 과정에서 AES를 비롯한 대칭키 암호 알고리즘보다 훨씬 많은 연산을 필요로 합니다. 따라서 많은 데이터를 여러 번 암호화해야 하는 네트워크 통신에서는 잘 사용되지 않습니다. RSA는 알고리즘을 창시한 Rivert, Shamir, Adleman 3명의 이름을 따서 만들어졌습니다.

 

https://lemon-soju.tistory.com/236

[RSA 개념]

 

---