- 기밀성
- 송신자와 지정된 수신자만이 전송되는 메시지 내용을 이해할 수 있어야 한다.
- 도청자가 메시지를 가로챌 수도 있으므로 도청자가 해석할 수 없도록 메시지를 어떠한 방식으로 암호화해야한다.
- 메시지 무결성
- 통신하는 내용이 전송 도중에 변경되지 않아야 한다.
- 종단점 인증
- 통신에 참여하는 상대방이 누구인지 확인하기 위해 상대방의 신원을 확인할 수 있어야 한다.
- 운영 보안
- 오늘날 대부분 기관들의 네트워크는 공공 인터넷에 연결되어 있다.
- 따라서 외부로부터의 공격을 받을 수 있는 위험을 갖고 있고 대비하여 방화벽이나 보안 체계를 갖고 있어야 한다.
- 송신자와 수신자
- 데이터 일부 혹은 전부를 암호화하여 안전한 통신을 하려고 할 것이다.
- 침입자
- 채널상의 제어 메시지 및 데이터 메시지를 스니핑하거나 기록
- 메시지 혹은 메시지 내용의 조작, 삽입 혹은 삭제
송신자가 보내는 원래 형태의 메시지를 평문 또는 원문이라고 한다.
송신자는 평문을 암호화 알고리즘을 사용해서 암호화하며, 암호화된 메시지인 암호문은 다른 침입자가 해석할 수 없다.
이 암호화 알고리즘은 모든이에게 알려져있고, 누구나 쉽게 사용할 수 있다.
즉, 전송한 데이터를 침입자가 복원할 수 없게 해주는 비밀 정보가 필요한데 이것이 바로 키이다.
- 앨리스는 숫자나 문자의 열인 키 A를 암호화 알고리즘의 입력값으로 사용하여 암호화된 메시지 A(m)을 완성한다.
- 밥은 키 B와 암호문 A(m)을 복호화 알고리즘에 입력값으로 넣어 B(A(m)) = m 의 출력을 받는다.
앨리스와 밥의 키가 동일하며 이 키는 둘만의 비밀이다.
키 중 하나는 세상 모두에게 알려져있고 다른 키는 앨리스 밥 중 한명만 알고 있다.
영어로된 원문에 대해 평문의 각 철자를 알파벳 순서로 k번째 뒤에 오는 철자로 대치한다. (철자들의 순환을 가정. z의 1번째 뒤에 오는 철자는 a다.)
여기서는 k의 값이 암호화 키가 된다.
하지만 카이사르 암호인 것을 알고 있다면 금방 암호문을 복호화할 수 있을 것이다.
카이사르 암호처럼 일정한 규칙에 따라 대치하는 대신 아무 규칙 없이 각 철자들을 고유한 대응 글자로 변환한다.
26! 정도의 문자 대응쌍이 가능하여 더 안전하다.
그러나 e나 t가 흔하게 나타나거나 3개 혹은 3개의 특정 문자가 함께 나오거나 하는 특성 탓에 암호를 해독하기 쉬워진다.
예를들어 암호문을 사용하는 사람의 이름이 평문에 들어가있다는 것을 안다면 즉시 알파벳 중 몇쌍을 확정 지을 수 있다.
침입자가 갖고 있는 정보에 따른 시나리오
- 암호문만을 이용한 공격
- 평문 메시지에 대한 어떠한 정보도 없는 경우
- 알려진 평문 공격
- 침입자가 평문과 암호문에 나올 단어(이름 등)를 미리 알고 있는 경우 해당 단어에 대한 단어 쌍을 알 수 있다.
- 선택 평문 공격
- 침입자가 특정 평문 메시지를 선택하여 송신자에게 보내게 하고 이에 대응하는 암호문의 형태를 얻을 수 있다.
여러 개의 단일 문자 대응법을 가지고 평문 메시지에서의 위치에 따라 서로 다른 단일 문자 대응 암호법을 사용한다.
즉, 같은 문자라도 평문 메시지에서의 위치에 따라 다르게 암호화 된다.
예를 들어, 단일 문자 대응법 첫번째를 C1, 단일 문자 대응법 두번째를 C2라고 해보자.
평문의 첫번째 메시지는 C1, 두번째는 C2, 세번째는 C1 … 식으로 평문 메시지의 위치에 따라 단일 문자 대응법을 달리 한다.
현재 TLS, PGP, IPsec 등에 사용되는 암호화 기법이다.
오늘날 널리 활용되는 블록 암호화 방법에는 AES, DES, 3DES 등이 있다.
블록 암호화에서는 메시지가 k 비트의 블록 단위로 쪼개어져 암호화 된다.
k 비트의 평문은 k 비트 블록의 평문을 k비트 블록의 암호문으로 일대일 사상 시킨다.
위 표와 같이 사상한다면 010110001111은 101000111001 로 암호화 된다.
k 비트에 대해서 총 (2^k)! 로 사상의 수가 천문학적으로 커진다.
그러나 k=64라고하면 송신자와 수신자 모두 2^64개의 입력 테이블에 대한 테이블을 유지해야하는데 이는 실행이 거의 불가능 하고, 키가 바뀌면 큰 테이블을 재생성해야 하기 때문에 실제 사용은 불가능 하다.
대신 블록 암호화 기법은 입출력 블록의 순열 테이블을 임의로 모방 생성하는 함수를 사용한다.
위 그림은 k=64일 때의 예시를 나타낸다.
시나리오
- 64 비트의 블록을 8 비트씩 8개의 청크로 나눈다.
- 각 8 비트 청크는 관리 가능한 크기인 8비트 입력 블록에 대응하는 8비트 출력 블록을 가진 테이블에 의해 처리된다.
- 각 청크는 관리 가능한 크기인 8 비트 입력 블록에 대응하는 8 비트 출력 블록을 가진 테이블에 의해 처리된다.
- 암호화된 청크는 하나의 64 비트 블록으로 다시 합쳐진다.
- 각각의 위치는 뒤섞여서 합쳐진다.
- 64 비트 블록을 다시 입력부로 넣는다.
- 이 사이클을 n번 반복한다.
- 각 입력 비트가 대부분의 최종 출력 바트들에 영향을 미치게 하기 위해서이다.
- 라운드를 한번만 수행하면 하나의 입력 비트는 8개의 출력 비트에만 영향을 끼친다.
이 블록 암호화 알고리즘의 키는 블록을 뒤섞는 규칙이 알려져있다면 8개의 순열 테이블이다.
네트워크 애플리케이션에서는 일반적으로 긴 메시지를 암호화할 필요가 있는데, 블록 암호화를 이용하면 미묘하지만 중요한 문제가 발생한다.
2개 이상의 평문 블록이 동일하다면 같은 암호문을 생성해내고, 공격자는 동일한 암호문으로 원문을 추측해낼 수 있는 가능성이 생긴다.
여기에 하위 프로토콜에 대한 지식까지 활용하면 전체 메시지를 복호화할 수 있다.
이를 해결하기 위해 같은 평문 블록에 대해 다른 암호문 블록이 생성될 수 있도록 임의성을 추가할 수 있다.
시나리오
- 송신자는 i번째 평문 블록 m(i)를 위해 k비트 길이의 임의의 수 r(i)를 생성한다.
- K(r(i) xor m(i)) = c(i) 암호문을 만든다.
- r(i)로 인해 m(i)와 m(j)가 같아도 암호문은 달라지게 된다.
- 수신자는 r(i)와 c(i)를 받아서 m(i) = K(c(i)) xor r(i) 를 수행한다.
- 침입자는 암호화되지 않은 r(i)를 볼수는 있지만 키를 알지 못하므로 평문 m(i)를 복호화할 수 없다.
그러나 송신자는 2배의 비트를 더 보내야 하고 2배의 대역폭을 필요로 한다.
이 문제를 해결하기 위해 암호 블록 체이닝(Cipher Block Chaining, CBC) 기법을 사용한다.
시나리오
- 메시지를 암호화하기 전에 송신자는 초기화 벡터라 불리는 임의의 k 비트열 c(0)을 생성한다.
- 송신자는 c(0)를 수신자에게 보낸다.
- 첫번째 블록에 대해 송신자는 c(1)= K(m(1) xor c(0)) 을 계산한다.
- 암호화된 c(1)을 수신자에게 보낸다.
- 송신자는 이를 계속 c(i)= K(m(i) xor c(i-1)) 암호문 블록을 생성하고 보낸다.
- 수신자는 c(i-1)을 알고 있으므로 계속 복호화할 수 있다.
- 마찬가지로 같은 평문을 가지고 있어도 다른 암호문을 갖게 된다.
- 침입자는 암호화되지 않은 c(0)을 볼수는 있지만 키를 알지 못하므로 평문 m(i)를 복호화할 수 없다.
- 송신자는 하나의 초기화 벡터만 더 전송하면 되므로 대역폭 증가량이 미미하다.
공개키 암호화에서는 송수신자가 각각 키를 갖는다기보다 수신자가 2개의 키를 갖는다.
하나는 세상 모두에게 알려진 공개키이고, 다른 하나는 수신자만 아는 개인키이다.
시나리오
- 송신자는 수신자에게 메시지를 보내기 위해 수신자의 공개키를 확인한다.
- 수신자의 공개키로 메세지를 암호화하고 송신한다.
- 수신자는 자신의 개인키로 암호문을 복호화 알고리즘을 사용하여 복호화한다.
RSA는 모듈로 n 연산(나머지)을 많이 사용한다.
모듈로 연산의 유용한 성질
[(a mod n)+(b mod n)]mod n=(a+b)mod n
[(a mod n)−(b mod n)]mod n=(a−b)mod n
[(a mod n)⋅(b mod n)]mod n=(a⋅b)mod n
// 3번째 성질로부터 나오는 식
(a mod n)^d mod n = a^d mod n
공개키와 개인키의 선택
- 2개의 큰 소수 p와 q를 선택한다.
- 값이 클수록 RSA를 깨기가 어려워지지만 암호화 복호화를 수행하는데 시간이 더 걸린다.
- n = pq, z =(p-1)(q-1) 식을 계산한다.
- 1을 제외하고 z의 서로소 n보다 작은 e를 선택한다.
- 암호화 encryption의 e를 따왔다.
- ed-1이 z로 정확히 나누어 떨어지는 숫자 d를 찾는다.
- 복호화 decryption의 d를 따왔다.
- 이 말은 즉슨, ed mod z = 1이 성립하도록 d를 선택한다와 같다.
- 공개키는 숫자쌍 (n,e) 이다. 그의 개인키는 (n,d)이다.
큰 p와 q를 고르는 방법, 지수 연산 방법, e와 d를 고르는 방법 등은 이 책의 범위에서 벗어나므로 생략한다.
알고리즘 시나리오
- 암호화를 위해 공개키 (n,e)를 활용한다. 메세지에 e승을 하고 이를 n으로 나눈 나머지를 계산한 값이 암호문 c가 된다.
- 메세지는 k 비트열로 하나의 정수와 같아서 e의 제곱을 할 수 있다.
- c = m^e mod n
- 수신된 암호 메시지 c를 복호화 하기 위해 개인키 (n,d)를 활용한다.
- m = c^d mod n = m^ed mod n 을 수행하여 복호화한다.
e.g.
수신자가 p=5 , q=7로 선택한다.
이때 n = 35, z = 24가 된다.
5와 z가 공통인수가 없으므로 e = 5 를 선택한다.
5x29-1 (즉, ed-1) 이 24로 나누어떨어지므로 d= 29를 선택한다.
이제 공개키 (35,5)와 비밀키 (35,29)가 완성되었다.
이제 평문 m을 암호화 복호화 해보자.
m은 비트열 1100으로 숫자 12에 대응된다고 가정하자.
암호화 : m^e = 248832, 17(c) = 248832(m^e) mod 35(n)
복호화 : 12(m) = 4819685721067509150915091411825223071697(c^d) mod 68(n)
RSA에 필요한 지수 연산은 시간이 많이 필요하여 실제로 종종 대칭키 암호화와 함께 사용된다.
시나리오
- 송신자는 데이터 암호화에 사용할 세션키를 고른다.
- 세션키는 대칭키 암호화에 사용된다. 즉, 밥에게 세션키를 알려야 한다.
- 송신자는 수신자의 공개키로 세션키를 RSA 암호화한다.
- 수신자는 암호문을 받고 자신의 개인키로 복호화한다.
- 수신자는 세션키를 얻고, 송신자가 보낸 데이터를 복호화할 수 있다.
m = m mod n= m^ed mod n 임을 증명하면 된다.
정수론에 의하면 p와 q가 소수이고 n = pq, z = (p-1)(q-1)이면, x^y mod n 이 x^(y mod z) mod n과 같다.
즉, 다음과 같은 식을 얻을 수 있다.
m^ed mod n = m^(ed mod z) mod n
ed mod z = 1이 되도록 e와 d를 선택하였으므로, m = m mod n= m^ed mod n 이다.
여기서 e와 d는 단순 제곱이므로 둘을 바꿔도 정상 동작한다.
- 메시지가 정말 해당 출발지로부터 왔는가?
- 메시지가 전달되는 도중 변경되지는 않았는가?
해시 함수는 입력 m을 받아서 해시라 불리는 고정된 크기의 문자열 H(m)을 계산해낸다.
암호화 해시 함수는 H(x) = H(y)가 되는 서로 다른 두 메시지 x와 y를 찾는 일이 산술적으로 실행 불가능하다.
즉, (m, H(m))이 원래 메시지와 그 메시지에 대해 송신자가 만들어낸 해시값이라고 할 때, 침입자가 원래 메시지와 동일한 해시값을 갖는 다른 메시지 y를 위조해낼 수 없다.
인터넷 체크섬과 같은 간단한 체크섬은 같은 값을 만들기 쉬워 암호화 해시 함수로 사용하기에는 너무 허술하다.
MD5 해시 알고리즘이 오늘날 널리 쓰이고 있다.
- 덧붙이는 단계
- 하나의 1을 메시지 뒤에 붙이고 충분히 많은 0을 뒤에 덧붙여서 메시지 길이가 단위 길이 조건을 만족시킨다.
- 추가 단계
- 덧붙이기 전 메시지 길이를 64비트로 표현하여 추가
- 어큐뮬레이터 초기화
- 루프 단계
- 메시지를 16워드 길이의 단위 블록들로 나누어 4개 라운드로 처리한다.
SHA 알고리즘은 MD4에 사용된 원리와 유사한 원리를 사용하여 널리 사용된다.
- 송신자는 메시지 m을 생성하고 해시값 H(m)을 만든다.
- 이때 SHA 등이 사용된다.
- 송신자는 메시지 m에 H(m)을 첨부하여 확장 메시지 (m, H(m))을 생성한 후 수신자에게 보낸다.
(수신자의 입장에서는 (m, h)로 보임) - (m, h)를 받은 수신자는 H(m)을 계산하고 이것이 h와 같다면 문제 없이 처리되었음을 확인한다.
이때, 침입자가 (m’, H(m’))을 자신이 수신자라고 주장하며 보내면 위 단계를 통과하고 부적절한지 알 수 없다.
송신자를 확인하기 위해 송신자 수신자는 비트열 형태의 인증키인 비밀키를 공유하여야 한다.
- 송신자는 메시지 m을 생성하고 인증키 s와 합하여 m+s를 만들고, H(m+s)를 생성한다.
- H(m+s)를 메시지 인증 코드(message authentication code, MAC 이는 링크 계층의 메시지와는 다르다.)라고 부른다.
- 송신자는 (m, H(m+s))를 보낸다. (수신자의 입장에서는 (m, h)로 보임)
- 수신자는 (m, h)를 받으면 H(m+s)를 계산하고 값이 h와 같다면 문제가 없다고 결론 짓는다.
메시지 인증 코드는 복잡한 암호화 알고리즘을 필요로하지 않는다.
MD5와 SHA와 함께 사용되는 메시지 인증코드는 HMAC으로 가장 많이 사용되는 표준이다.
통신 개체들에게 인증키를 전달하는 방법은 네트워크 관리자가 각각의 라우터에 직접 접근하거나 인증키를 각 라우터의 공개키로 암호화하여 네트워크를 통해 전달할 수 있다.
디지털 세계에서 문서의 소유자를 명시하거나 어떤 사람이 문서의 내용에 동의했다는 것을 표시하길 원하고, 전자 서명은 디지털 세계에서 이러한 목적으로 사용된다.
서명 시 실제로 그 사람이 서명했다는 사실, 그리고 오직 그 사람만이 문서에 서명할 수 있었다는 사실을 증명할 수 있어야 한다.
공개키 암호화 방법은 개인키와 공개키를 따로 가지고 있어 전자 서명에 효과적이다. (다른 사람은 개인키로 서명할 수 없다.)
- 서명자는 문서 m을 서명하려한다.
- 서명자는 자신의 개인키로 K(m)을 만든다. 이것이 바로 전자 서명이다.
- 전자서명 K(m)은 서명자의 개인키로 만들어져 서명자만 만들 수 있다.
- 전자서명 K(m)을 받은 사람들은 서명자의 공개키를 사용해 원래의 m을 다시 확인할 수 있다.
- 즉, 공개키의 주인인 서명자가 쓴 서명이라는 것이 확인된다.
- 어느 한 사람이 중간에 문서를 조작해 m’을 만들었어도 m과 같지 않으므로 유효하지 않음을 알 수 있다. 즉, 메시지 무결성을 확인할 수 있다.
자신의 개인키로 먼저 암호화하고 공개키로 복호화해도 되는 이유는, m^ed mod n = m^de mod n = m mod n 이기 때문이다.
m 자체에 암호화 복호화를 하면 계산의 부하가 심하다.
이때, 해시 알고리즘을 사용하여 해결할 수 있다.
즉, m을 H(m)으로 표현되는 고정 길이의 지문을 계산해내고, K(H(m))을 계산하여 계산의 부하를 줄인다.
- 메시지 m을 해시 알고리즘을 이용하여 고정 길이로 바꿔 H(m)을 만든다.
- H(m)을 자신의 개인키로 암호화 한다.
- (m,K(H(m)))을 보낸다.
- 서명자로 부터 (m,K(h))를 받는다.
- 서명자의 공개키로 K(h)를 복호화하여 h를 알아낸다.
- m을 해시 알고리즘을 이용하여, H(m)으로 만들고 h와 일치하는지 알아낸다.
전자 서명은 인증기관과 함께 공개키 하부 구조를 요구하기 때문에 MAC에 비해 더 무거운 기술이다.
많은 프로토콜에서는 MAC이 사용된다.
전자 서명에서는 공개키가 특정 통신 개체에 속한다는 것을 보증하여야 한다. (IPsec과 TSL를 포함한 많은 보안 네트워킹 프로토콜에서 사용된다.)
중간에 침입자가 자신이 서명자라고 주장하며 메시지를 보내는데, 이때 공개키를 자신의 공개키를 담아 보낸다.
수신자는 침입자의 공개키를 사용해 메세지를 복호화 할 것이고, 수신자는 서명자가 쓴 서명임을 확신할 것이다.
즉, 공개키 암호를 사용하려면 서명자의 공개키라고 생각되는 것이 정말 서명자의 것인지 확인하여야 한다.
공개키가 어떤 통신 개체(서명자)의 것인지 보증하는 일은 일반적으로 CA(인증 기관)에서 담당한다.
CA는 신원을 확인하고 인증서를 발행한다.
- CA는 어떤 개체(사람, 라우터)가 스스로 주장하는 자신의 신분이 바로 그 개체가 맞는지 확인한다.
- 인증에 정해진 방법은 없고 CA가 적절한 방법으로 엄격하게 식별자 검증을 수행하리라는 점을 신뢰해야한다.
- 일단 CA가 신원을 확인하면, CA는 개체의 공개키와 신분 확인서를 결합한 인증서를 만든다.
- 인증서에는 CA가 서명한다.
