Skip to content

Instantly share code, notes, and snippets.

@aJchemist aJchemist/crypto.md forked from lifthrasiir/crypto.md
Last active Jul 20, 2019

Embed
What would you like to do?
고수준에서 암호학 이해하기

고수준에서 암호학 이해하기

이 글은 메아리 저널에 쓸 목적으로 한동안 작업하던 글입니다. 메아리 특유의 디자인(...)이 싫다면 여기로 링크하셔도 됩니다. 어느 쪽이든간에 의견은 이 아래의 코멘트 란 또는 메아리에 기재되어 있는 메일 주소를 써 주시면 감사하겠습니다. --lifthrasiir

암호학을 사용하는 많은 시스템은 세부적으로 무슨 알고리즘을 쓰는지보다는 그 알고리즘들이 어떻게 연결되어 있는지, 즉 구조가 실제 안전성에 더 큰 영향을 미친다. 따라서 구조와 그 구조를 이루는 빌딩 블럭을 아는 것이 중요한데, 여기에서는 이러한 암호학적 빌딩 블럭과 함께 블럭들이 어떻게 쓰여서 더 큰 구조를 만드는지를 알아 본다.

Key Exchange

키 교환. 두 사람만이 알 수 있는 새로운 키를 만든다. 이 과정이 끝나도 상대방이 내가 아는 사람인진 알 수 없지만 적어도 상대방과 내가 같은 키를 가지고 있다는 건 확신할 수 있다.

  • Diffie-Hellman 계열 알고리즘이 대표적. 온갖 종류의 변종들이 있다.
  • 기술적으로는 키 교환 후 만들어진 키를 그대로 써도 되긴 하는데, 보통 암호화 등에서 쓰는 키 포맷과 안 맞기 때문에(정수 비트로 안 떨어진다거나...) 키 유도를 통해 새 키를 만들어 쓴다.
  • 키 교환을 쌩으로 쓰면 중간에 있는 사람(man-in-the-middle)이 상대인 척 하고 끼어들 수 있다. 서로에 대해 어느 정도 정보를 알고 있다면 인증된 키 교환을 써야 한다.

Key Derivation

키 유도. 다른 키에서 새로운 키 여러 벌을 만든다. 입력이나 출력이나 암호화 등등에 사용할 수 있어야 하는 키여야 하고, 새로운 키에서 원래 키를 알아낼 방법은 없어야 한다.

  • 당연히 같은 입력에 같은 방법이면 같은 키가 나온다. 그래서 키 유도 함수(KDF)라고 부른다.
  • 키는 한 개만 나올 수 있는 게 아니다. 고로 키 유도 함수에는 입력과 함께 임의의 문자열을 넣을 수 있다. 물론 어느 한 쪽이라도 바뀌면 결과는 확 바뀌어야 한다.
  • 크게 두 가지 용도로 쓰이는데, 이전 키를 쓰는 암호화와 이후 키를 쓰는 암호화를 분리시켜서 이후 키가 노출되어도 이전 데이터를 보호하기 위함이 하나고, 서로 키 크키가 다른 알고리즘에 쓸 목적으로 새 키를 만드는 것이 하나이다.
  • 키 유도 함수를 후술할 해싱으로 구현하는 경우도 있으며(keyed hash function) 가능한 방법이다. 그런데 좀 더 나아가서 사용자로부터 받은 암호에도 키 유도 함수나 해시를 쓰는 경우가 많은데 이것은 권장되지 않는다. 아래의 키 스트레칭을 참고할 것.

Cryptographic Hashing

암호학적 해시. 어쩌면 엄청 길 수 있는 데이터에서 고정된 길이로 데이터의 요약(digest)을 끄집어 낸다. 요약만 가지고 데이터에 대한 어떤 정보도 알 수는 없어야 한다(즉, 완전 랜덤한 데이터처럼 보여야 한다). 임의의 두 데이터를 줬을 때 같은 해시가 나오는 가능성이 "거의" 없어야 한다.

  • 데이터는 무한히 많은데 요약은 유한하니 당연히 완벽한 건 아니다. 위에서 "거의"라고 말한 게 그 이유. 어떤 알고리즘이라도 생일 역설(birthday paradox)에 따라 n비트 해시에서 대강 n/2비트 정도를 무작위로 대입(brute force attack)하면 높은 확률로 충돌이 나오는데, 이게 최선의 공격이 되도록 하는 게 목표가 된다.
  • 요즘은 컴퓨터가 좋기 때문에 해시가 너무 짧으면 무작위 대입이 먹히는 경우도 종종 있다. 너무 길 필요는 없지만 128비트나 그 이하는 너무 짧다고 생각하는 게 좋다.
  • 좋은 암호학적 해시는 빨라야 한다. 빠르면 빠를 수록 좋고, 요즘 시대에서는 병렬화도 되면 좋다.
  • 흔히 역변환이 불가능해야 한다(first pre-image attack)는 것만 생각하는데, 이미 있는 데이터를 줬을 때 그거랑 같은 해시를 가지는 쪼금 다른 데이터를 만드는 것도 불가능해야 한다(second pre-image attack). 이거랑 해시 충돌이랑 합쳐서 세 가지가 암호학적 해시의 최소 조건.
  • 해시를 쓰면 안 되는 곳에 해시를 쓰는 것은 피해야 한다. 예를 들어서 메시지 인증에는 거기에 맞게 만들어진 알고리즘을 써야 한다. (메시지 인증 전에 해시를 써서 요약을 인증시키는 건 가능하다. 사실 원래 그렇게 쓰는 거다.)

Key Stretching

키 스트레칭. 암호 같이 암호화 등에 쓰이기 어려운 입력에서 새로운 키를 만든다. 암호학적 해시의 기본적인 조건과 더불어, 느린 정도를 조정할 수 있어서 무작위 대입을 하는 것도 비싸야 한다.

  • 옛날에는 암호학적 해시키 유도 함수가 이 용도로 흔히 쓰였다. 시간이 갈수록 암호 저장용으로는 별개의 방법이 필요하다는 인식이 확산되면서 다른 분류로 분리되었다. 요즘은 bcrypt나 scrypt를 많이 쓴다.
  • 키 유도 함수와 비슷하게 암호와 더불어 별도의 문자열(salt)을 넣을 수 있다. 이 문자열의 용도는 미리 계산된 데이터베이스(rainbow table)를 가지고 짧은 암호를 빠르게 역변환하는 걸 막기 위한 것으로, 사용하는 곳마다 달라야 한다.
  • 컴퓨터는 시간이 지날 수록 계속 빨라질 것이기 때문에 느린 정도를 조정할 수 있어야 한다. 관심이 있다면 키 스트레칭을 할 컴퓨터에서 미리 성능을 테스트하고 적절한 파라미터를 선택해 보자. 또한 한 번 파라미터를 정하면 시간이 갈수록 빨라질텐데, 따라서 나중에 파라미터를 더 올리는 것도 가능해야 한다.

Encryption

암호화. 두 사람이 상대방에 대한 적절한 정보를 가지고 있을 때 한 쪽이 암호화해서 보내면 다른 쪽이 복호화한다. 크게 두 종류가 있다.

Symmetric Encryption

대칭 암호화. 두 사람이 같은 키를 가지고 있을 때 한 쪽이 암호화해서 보내면 다른 쪽이 복호화한다. 키가 안 털리면 암호화된 내용을 백날 털어도 아무 정보도 알 수 없어야 한다.

  • 잘 표준화되어 있다. 그리고 엄청 빠르다. 그냥 갖다 쓰면 된다. (AES 등)
  • ...그러면 좋겠지만 왠진 몰라도 "운용 방식"(modes of operation)이라는 이상한 것을 선택해야 하는 경우가 있다. 이것은 대칭 암호화의 큰 갈래인 블록 암호(block cipher)의 특징 때문에 생긴 이상한 것이며, 잘못 고르면 골로 간다. 요즘은 다른 갈래인 스트림 암호(stream cipher)도 많이 발전했기 때문에 좋은 스트림 암호를 쓰는 게 더 간편하고 안전할 수 있다.
  • 보통 단순하게 "암호화"라고 말할 때 이것만을 가리키는 경향이 있긴 하지만 실제 암호화를 하려면 다른 일련의 과정들을 거쳐서 공용 키를 만들어 내야만 안전하게 대칭 암호화를 쓸 수 있다. 절대로 착각하지 말자.
  • 암호화와 더불어 후술할 메시지 인증을 함께 해야 한다면 마찬가지로 후술할 인증된 암호화를 쓰는 게 더 낫다.

Asymmetric Encryption

비대칭 암호화. 한 사람이 비밀키를 가지고 있고 다른 사람이 그 비밀키에 대한 공개키를 가지고 있을 때 공개키를 가진 쪽이 그걸로 암호화해서 보내면 비밀키를 가진 쪽이 복호화한다. 비밀키에서는 공개키를 쉽게 만들 수 있지만 공개키에서는 죽었다 깨나도 비밀키를 만들 수 없다. 비밀키가 안 털리면 암호화된 내용을 백날 털어도 아무 정보도 알 수 없어야 한다.

  • RSA가 대표적인 비대칭 암호화 알고리즘이지만 그거 말고도 많이 있다.
  • 보통 대칭 암호화에 비해서 훨씬 비싸다. 차라리 다른 방법으로 키를 교환해서 대칭 암호화를 쓰는게 비슷하게 안전하면서 더 빠를 때가 많아서 쌩으로 쓰는 경우가 많이 줄어들었다. 다만 키 교환을 미리 하기 어려운 상황이라면 여전히 의미가 있다.

Signing

(전자)서명. 한 사람이 비밀키를 가지고 있고 다른 사람이 그 비밀키에 대한 공개키를 가지고 있을 때, 비밀키를 가진 쪽이 메시지와 더불어 비밀키를 가지고 해당 메시지에 짧은 서명을 붙이면 공개키를 가진 쪽이 해당 서명이 정말로 대응되는 비밀키로 서명한 게 맞는지를 확인한다. 비밀키/공개키의 컨셉은 비대칭 암호화와 같음. 바깥에서는 데이터는 변조시킬 수 있지만 올바른 서명은 만들 수 없어야 한다.

  • 데이터가 아무리 길어도 상관 없다. 데이터를 암호학적 해시로 요약한 뒤 그 요약을 서명하면 된다. 프로토콜에 따라서는 아예 해시 알고리즘과 서명 알고리즘을 붙여서 선택하도록 하는 경우도 있다.
  • 데이터 자체가 알려져서는 안 되는 상황이라면 암호화와 함께 사용해야 한다.
  • 똑같이 비밀키랑 공개키 나오고 대표적인 알고리즘인 RSA가 서명에도 비대칭 암호화에서도 쓸 수 있어서 헷갈릴 수 있지만 둘은 다르다. 암호화에는 쓸 수 없지만 서명에는 쓸 수 있고 더 효율적인 알고리즘들이 여럿 있다.

Message Authentication

메시지 인증. 두 사람이 같은 키를 가지고 있을 때, 한 쪽이 데이터와 더불어 키를 가지고 해당 데이터에 짧은 메시지 인증 코드(MAC)를 붙이면 다른 쪽이 키와 데이터와 인증 코드를 가지고 메시지가 안 바뀌었는지 확인한다. 바깥에서는 데이터는 변조시킬 수 있지만 키를 모르는 이상 올바른 인증 코드는 만들 수 없어야 한다.

  • 데이터 자체가 알려져서는 안 되는 상황이라면 암호화와 함께 사용해야 한다. 일반적으로 암호화를 먼저 하고 암호문의 인증 코드를 붙이는 게 올바르다(encrypt-then-MAC)고 여겨진다. 반대(MAC-then-encrypt)로 하거나 평문의 인증 코드를 붙인다(encrypt-and-MAC)고 해서 바로 뚫린다는 건 아니지만, 둘 중 하나가 뚫렸을 때 파탄이 나기 쉬우며 구현이 틀리기도 쉽다. 성능상으로도 별 차이 없으니 더 안전한 쪽을 쓰자.
  • 데이터가 무한히 길어질 수 있으므로 보통 해시를 먼저 하고 그 결과를 인증 코드 함수에 돌린다.

Authenticated Key Exchange

인증된 키 교환. "서로 아는" 두 사람만이 알 수 있는 새로운 키를 만든다. 키 교환과 비슷하지만 서로에 대한 정보를 알고 있고 그 정보를 키 교환과 함께 검증하고자 한다는 게 차이점.

  • 일반적으로는 "서로 안다"는 것의 정의는 서명과 비슷하게 보내는 쪽이 공개키를, 받는 쪽이 비밀키를 가지고 있다는 것이다. 그래서 인증된 키 교환은 보통 서명 알고리즘에 의존한다.
  • 좋은 인증된 키 교환 알고리즘은 중간 공격자가 상대인 척 하는 것을 막을 뿐만 아니라 중간 공격자가 의도한 상대방이 아닌 엉뚱한 제 3자를 연결시키는 것(misbinding attack)도 막아야 한다. SIGMA 등이 여기에 속한다.

Authenticated Encryption

인증된 암호화. 두 사람이 같은 키를 가지고 있을 때, 한 쪽이 데이터와 키를 인증된 암호화 알고리즘에 집어 넣어서 보내면 다른 쪽이 같은 키와 암호화된 데이터를 가지고 이게 해당 키로 암호화된 게 맞는지 확인하고 맞으면 복호화된 데이터를 얻는다. 메시지 인증이랑 대칭 암호화를 하나로 합쳤다고 생각하면 쉽다.

  • 암호화 따로 메시지 인증 따로 쓰고 싶은 경우가 잘 없기 때문에, 이왕 자주 쓰는 거라면 둘을 합쳐서 한꺼번에 설계하는게 더 안전하다는 취지로 만들어진 방법. 신경 쓸 거리가 많이 줄어드므로 가능하면 이걸 쓰자.
  • 대칭 암호화에 사용되는 블록 암호는 적절한 운용 방법을 선택하면 인증된 암호화로 변신시킬 수 있다. (GCM 등)

Cryptographically Secure Pseudorandom Number Generator

암호학적으로 안전한 유사난수 생성기(CSPRNG). 적절한 방법으로 예측이 불가능한(랜덤한) 난수를 생성한다.

  • 레알 온갖 곳에서 쓰인다. 키 생성할 때도 쓰고, 한 번 끝났으면 재현(replay attack)이 불가능해야 하는 종류의 데이터를 주고 받을 때도 덤으로 붙이고, 아예 대칭 암호화를 이걸로 만드는 과격한 경우도 있다(one-time pad). 여튼 중요하다.
  • 컴퓨터는 근본적으로는 결정론적으로 돌아가므로 이론적으로 최상의 랜덤은 불가능하다. 대신, 랜덤하다고 볼 수 있는 데이터들이 컴퓨터에 입력으로 들어 오는데(이를테면 키보드 입력이라거나...) 이런 것들을 잘 모아 적절한 방법으로 쑤셔서 박아서 난수를 만든다. 원래 데이터는 매우 민감한 정보이므로 난수에서 원래 데이터를 복구할 수는 없어야 한다.
  • 데이터가 얼마나 랜덤한지를 "정보 엔트로피"라고 한다. 이를테면 10비트의 엔트로피는 모든 2^10개의 가능성이 동등한 확률로 나오는 랜덤이라는 뜻. 이상적으로 CSPRNG는 들어온 엔트로피랑 같은 엔트로피를 제공해야 한다.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.