이 글은 메아리 저널에 쓸 목적으로 한동안 작업하던 글입니다. 메아리 특유의 디자인(...)이 싫다면 여기로 링크하셔도 됩니다. 어느 쪽이든간에 의견은 이 아래의 코멘트 란 또는 메아리에 기재되어 있는 메일 주소를 써 주시면 감사하겠습니다. --lifthrasiir
암호학을 사용하는 많은 시스템은 세부적으로 무슨 알고리즘을 쓰는지보다는 그 알고리즘들이 어떻게 연결되어 있는지, 즉 구조가 실제 안전성에 더 큰 영향을 미친다. 따라서 구조와 그 구조를 이루는 빌딩 블럭을 아는 것이 중요한데, 여기에서는 이러한 암호학적 빌딩 블럭과 함께 블럭들이 어떻게 쓰여서 더 큰 구조를 만드는지를 알아 본다.
키 교환. 두 사람만이 알 수 있는 새로운 키를 만든다. 이 과정이 끝나도 상대방이 내가 아는 사람인진 알 수 없지만 적어도 상대방과 내가 같은 키를 가지고 있다는 건 확신할 수 있다.
- Diffie-Hellman 계열 알고리즘이 대표적. 온갖 종류의 변종들이 있다.
- 기술적으로는 키 교환 후 만들어진 키를 그대로 써도 되긴 하는데, 보통 암호화 등에서 쓰는 키 포맷과 안 맞기 때문에(정수 비트로 안 떨어진다거나...) 키 유도를 통해 새 키를 만들어 쓴다.
- 키 교환을 쌩으로 쓰면 중간에 있는 사람(man-in-the-middle)이 상대인 척 하고 끼어들 수 있다. 서로에 대해 어느 정도 정보를 알고 있다면 인증된 키 교환을 써야 한다.
키 유도. 다른 키에서 새로운 키 여러 벌을 만든다. 입력이나 출력이나 암호화 등등에 사용할 수 있어야 하는 키여야 하고, 새로운 키에서 원래 키를 알아낼 방법은 없어야 한다.
- 당연히 같은 입력에 같은 방법이면 같은 키가 나온다. 그래서 키 유도 함수(KDF)라고 부른다.
- 키는 한 개만 나올 수 있는 게 아니다. 고로 키 유도 함수에는 입력과 함께 임의의 문자열을 넣을 수 있다. 물론 어느 한 쪽이라도 바뀌면 결과는 확 바뀌어야 한다.
- 크게 두 가지 용도로 쓰이는데, 이전 키를 쓰는 암호화와 이후 키를 쓰는 암호화를 분리시켜서 이후 키가 노출되어도 이전 데이터를 보호하기 위함이 하나고, 서로 키 크키가 다른 알고리즘에 쓸 목적으로 새 키를 만드는 것이 하나이다.
- 키 유도 함수를 후술할 해싱으로 구현하는 경우도 있으며(keyed hash function) 가능한 방법이다. 그런데 좀 더 나아가서 사용자로부터 받은 암호에도 키 유도 함수나 해시를 쓰는 경우가 많은데 이것은 권장되지 않는다. 아래의 키 스트레칭을 참고할 것.
암호학적 해시. 어쩌면 엄청 길 수 있는 데이터에서 고정된 길이로 데이터의 요약(digest)을 끄집어 낸다. 요약만 가지고 데이터에 대한 어떤 정보도 알 수는 없어야 한다(즉, 완전 랜덤한 데이터처럼 보여야 한다). 임의의 두 데이터를 줬을 때 같은 해시가 나오는 가능성이 "거의" 없어야 한다.
- 데이터는 무한히 많은데 요약은 유한하니 당연히 완벽한 건 아니다. 위에서 "거의"라고 말한 게 그 이유. 어떤 알고리즘이라도 생일 역설(birthday paradox)에 따라 n비트 해시에서 대강 n/2비트 정도를 무작위로 대입(brute force attack)하면 높은 확률로 충돌이 나오는데, 이게 최선의 공격이 되도록 하는 게 목표가 된다.
- 요즘은 컴퓨터가 좋기 때문에 해시가 너무 짧으면 무작위 대입이 먹히는 경우도 종종 있다. 너무 길 필요는 없지만 128비트나 그 이하는 너무 짧다고 생각하는 게 좋다.
- 좋은 암호학적 해시는 빨라야 한다. 빠르면 빠를 수록 좋고, 요즘 시대에서는 병렬화도 되면 좋다.
- 흔히 역변환이 불가능해야 한다(first pre-image attack)는 것만 생각하는데, 이미 있는 데이터를 줬을 때 그거랑 같은 해시를 가지는 쪼금 다른 데이터를 만드는 것도 불가능해야 한다(second pre-image attack). 이거랑 해시 충돌이랑 합쳐서 세 가지가 암호학적 해시의 최소 조건.
- 해시를 쓰면 안 되는 곳에 해시를 쓰는 것은 피해야 한다. 예를 들어서 메시지 인증에는 거기에 맞게 만들어진 알고리즘을 써야 한다. (메시지 인증 전에 해시를 써서 요약을 인증시키는 건 가능하다. 사실 원래 그렇게 쓰는 거다.)
키 스트레칭. 암호 같이 암호화 등에 쓰이기 어려운 입력에서 새로운 키를 만든다. 암호학적 해시의 기본적인 조건과 더불어, 느린 정도를 조정할 수 있어서 무작위 대입을 하는 것도 비싸야 한다.
- 옛날에는 암호학적 해시나 키 유도 함수가 이 용도로 흔히 쓰였다. 시간이 갈수록 암호 저장용으로는 별개의 방법이 필요하다는 인식이 확산되면서 다른 분류로 분리되었다. 요즘은 bcrypt나 scrypt를 많이 쓴다.
- 키 유도 함수와 비슷하게 암호와 더불어 별도의 문자열(salt)을 넣을 수 있다. 이 문자열의 용도는 미리 계산된 데이터베이스(rainbow table)를 가지고 짧은 암호를 빠르게 역변환하는 걸 막기 위한 것으로, 사용하는 곳마다 달라야 한다.
- 컴퓨터는 시간이 지날 수록 계속 빨라질 것이기 때문에 느린 정도를 조정할 수 있어야 한다. 관심이 있다면 키 스트레칭을 할 컴퓨터에서 미리 성능을 테스트하고 적절한 파라미터를 선택해 보자. 또한 한 번 파라미터를 정하면 시간이 갈수록 빨라질텐데, 따라서 나중에 파라미터를 더 올리는 것도 가능해야 한다.
암호화. 두 사람이 상대방에 대한 적절한 정보를 가지고 있을 때 한 쪽이 암호화해서 보내면 다른 쪽이 복호화한다. 크게 두 종류가 있다.
대칭 암호화. 두 사람이 같은 키를 가지고 있을 때 한 쪽이 암호화해서 보내면 다른 쪽이 복호화한다. 키가 안 털리면 암호화된 내용을 백날 털어도 아무 정보도 알 수 없어야 한다.
- 잘 표준화되어 있다. 그리고 엄청 빠르다. 그냥 갖다 쓰면 된다. (AES 등)
- ...그러면 좋겠지만 왠진 몰라도 "운용 방식"(modes of operation)이라는 이상한 것을 선택해야 하는 경우가 있다. 이것은 대칭 암호화의 큰 갈래인 블록 암호(block cipher)의 특징 때문에 생긴 이상한 것이며, 잘못 고르면 골로 간다. 요즘은 다른 갈래인 스트림 암호(stream cipher)도 많이 발전했기 때문에 좋은 스트림 암호를 쓰는 게 더 간편하고 안전할 수 있다.
- 보통 단순하게 "암호화"라고 말할 때 이것만을 가리키는 경향이 있긴 하지만 실제 암호화를 하려면 다른 일련의 과정들을 거쳐서 공용 키를 만들어 내야만 안전하게 대칭 암호화를 쓸 수 있다. 절대로 착각하지 말자.
- 암호화와 더불어 후술할 메시지 인증을 함께 해야 한다면 마찬가지로 후술할 인증된 암호화를 쓰는 게 더 낫다.
비대칭 암호화. 한 사람이 비밀키를 가지고 있고 다른 사람이 그 비밀키에 대한 공개키를 가지고 있을 때 공개키를 가진 쪽이 그걸로 암호화해서 보내면 비밀키를 가진 쪽이 복호화한다. 비밀키에서는 공개키를 쉽게 만들 수 있지만 공개키에서는 죽었다 깨나도 비밀키를 만들 수 없다. 비밀키가 안 털리면 암호화된 내용을 백날 털어도 아무 정보도 알 수 없어야 한다.
- RSA가 대표적인 비대칭 암호화 알고리즘이지만 그거 말고도 많이 있다.
- 보통 대칭 암호화에 비해서 훨씬 비싸다. 차라리 다른 방법으로 키를 교환해서 대칭 암호화를 쓰는게 비슷하게 안전하면서 더 빠를 때가 많아서 쌩으로 쓰는 경우가 많이 줄어들었다. 다만 키 교환을 미리 하기 어려운 상황이라면 여전히 의미가 있다.
(전자)서명. 한 사람이 비밀키를 가지고 있고 다른 사람이 그 비밀키에 대한 공개키를 가지고 있을 때, 비밀키를 가진 쪽이 메시지와 더불어 비밀키를 가지고 해당 메시지에 짧은 서명을 붙이면 공개키를 가진 쪽이 해당 서명이 정말로 대응되는 비밀키로 서명한 게 맞는지를 확인한다. 비밀키/공개키의 컨셉은 비대칭 암호화와 같음. 바깥에서는 데이터는 변조시킬 수 있지만 올바른 서명은 만들 수 없어야 한다.
- 데이터가 아무리 길어도 상관 없다. 데이터를 암호학적 해시로 요약한 뒤 그 요약을 서명하면 된다. 프로토콜에 따라서는 아예 해시 알고리즘과 서명 알고리즘을 붙여서 선택하도록 하는 경우도 있다.
- 데이터 자체가 알려져서는 안 되는 상황이라면 암호화와 함께 사용해야 한다.
- 똑같이 비밀키랑 공개키 나오고 대표적인 알고리즘인 RSA가 서명에도 비대칭 암호화에서도 쓸 수 있어서 헷갈릴 수 있지만 둘은 다르다. 암호화에는 쓸 수 없지만 서명에는 쓸 수 있고 더 효율적인 알고리즘들이 여럿 있다.
메시지 인증. 두 사람이 같은 키를 가지고 있을 때, 한 쪽이 데이터와 더불어 키를 가지고 해당 데이터에 짧은 메시지 인증 코드(MAC)를 붙이면 다른 쪽이 키와 데이터와 인증 코드를 가지고 메시지가 안 바뀌었는지 확인한다. 바깥에서는 데이터는 변조시킬 수 있지만 키를 모르는 이상 올바른 인증 코드는 만들 수 없어야 한다.
- 데이터 자체가 알려져서는 안 되는 상황이라면 암호화와 함께 사용해야 한다. 일반적으로 암호화를 먼저 하고 암호문의 인증 코드를 붙이는 게 올바르다(encrypt-then-MAC)고 여겨진다. 반대(MAC-then-encrypt)로 하거나 평문의 인증 코드를 붙인다(encrypt-and-MAC)고 해서 바로 뚫린다는 건 아니지만, 둘 중 하나가 뚫렸을 때 파탄이 나기 쉬우며 구현이 틀리기도 쉽다. 성능상으로도 별 차이 없으니 더 안전한 쪽을 쓰자.
- 데이터가 무한히 길어질 수 있으므로 보통 해시를 먼저 하고 그 결과를 인증 코드 함수에 돌린다.
인증된 키 교환. "서로 아는" 두 사람만이 알 수 있는 새로운 키를 만든다. 키 교환과 비슷하지만 서로에 대한 정보를 알고 있고 그 정보를 키 교환과 함께 검증하고자 한다는 게 차이점.
- 일반적으로는 "서로 안다"는 것의 정의는 서명과 비슷하게 보내는 쪽이 공개키를, 받는 쪽이 비밀키를 가지고 있다는 것이다. 그래서 인증된 키 교환은 보통 서명 알고리즘에 의존한다.
- 좋은 인증된 키 교환 알고리즘은 중간 공격자가 상대인 척 하는 것을 막을 뿐만 아니라 중간 공격자가 의도한 상대방이 아닌 엉뚱한 제 3자를 연결시키는 것(misbinding attack)도 막아야 한다. SIGMA 등이 여기에 속한다.
인증된 암호화. 두 사람이 같은 키를 가지고 있을 때, 한 쪽이 데이터와 키를 인증된 암호화 알고리즘에 집어 넣어서 보내면 다른 쪽이 같은 키와 암호화된 데이터를 가지고 이게 해당 키로 암호화된 게 맞는지 확인하고 맞으면 복호화된 데이터를 얻는다. 메시지 인증이랑 대칭 암호화를 하나로 합쳤다고 생각하면 쉽다.
- 암호화 따로 메시지 인증 따로 쓰고 싶은 경우가 잘 없기 때문에, 이왕 자주 쓰는 거라면 둘을 합쳐서 한꺼번에 설계하는게 더 안전하다는 취지로 만들어진 방법. 신경 쓸 거리가 많이 줄어드므로 가능하면 이걸 쓰자.
- 대칭 암호화에 사용되는 블록 암호는 적절한 운용 방법을 선택하면 인증된 암호화로 변신시킬 수 있다. (GCM 등)
암호학적으로 안전한 유사난수 생성기(CSPRNG). 적절한 방법으로 예측이 불가능한(랜덤한) 난수를 생성한다.
- 레알 온갖 곳에서 쓰인다. 키 생성할 때도 쓰고, 한 번 끝났으면 재현(replay attack)이 불가능해야 하는 종류의 데이터를 주고 받을 때도 덤으로 붙이고, 아예 대칭 암호화를 이걸로 만드는 과격한 경우도 있다(one-time pad). 여튼 중요하다.
- 컴퓨터는 근본적으로는 결정론적으로 돌아가므로 이론적으로 최상의 랜덤은 불가능하다. 대신, 랜덤하다고 볼 수 있는 데이터들이 컴퓨터에 입력으로 들어 오는데(이를테면 키보드 입력이라거나...) 이런 것들을 잘 모아 적절한 방법으로 쑤셔서 박아서 난수를 만든다. 원래 데이터는 매우 민감한 정보이므로 난수에서 원래 데이터를 복구할 수는 없어야 한다.
- 데이터가 얼마나 랜덤한지를 "정보 엔트로피"라고 한다. 이를테면 10비트의 엔트로피는 모든 2^10개의 가능성이 동등한 확률로 나오는 랜덤이라는 뜻. 이상적으로 CSPRNG는 들어온 엔트로피랑 같은 엔트로피를 제공해야 한다.