올릴려 그러니까 네임드같은 고닉이 동형암호 올렸네.. 괜히 좀 그러네. 여튼.


0. 인트로


지난 글에서는 어려운 문제가 뭔지 알아봤다. (무시할만한것 도 알아봤지.)

이제 소인수분해가 어렵다는 말은 무슨말인지 알겠는데, 그거랑 암호가 안전하다라는 말이랑 무슨 상관일까?

눈치가 빠르다면 암호가 안전하다는게 암호를 깨는 문제가 어렵다는 말로 바꾸면 되지 않나, 싶을꺼다. 그래, 근데 암호를 깬다는게 뭘까?

사실 이게 굉장히 모호한 말이다. 암호를 공격할때 [암호에 대해서 뭘 할수있는데] [암호를 깨는 문제]를 풀기 어려운걸까?

이번 글에서는 이 두개를 개략적으로 이해해보는게 목표다. 특히 뒤에꺼.

물론 새로 읽는사람을 위해서 이전글 없이도 이해할수있게 적을거임.


이 글에서는


1) 구체적인 암호(OTP)의 안전성이 어떻게 정의되는가,

2) 왜 그렇게 정의되는게 "옳은"가,

3) 그걸로 충분한가?

4) 현실에서는 어떤가?


를 다룰거임.

내 생각에는 특히 2번이 흥미로움.

Shafi Goldwasser랑 Silvio Micali가 (대학원생때!) 정의한건데, 이거랑 interactive proof에 관한 공로로 튜링어워드를 받음.

(이전에 암호들이 발전은 했지만, "안전성"이 formal하게 정의된건 아마 저게 처음일거임)



1. One-time pad의 안전성 정의


우리가 다룰 암호는 [메세지공간, (암호화)키공간, 암호문공간, 암호화알고리즘, 복호화알고리즘]의 쌍으로 이루어진다. (사실 키생성알고리즘도 있어야하는데 걍 넘어가자)

구체적인 예시로 시작하자. 굉장히 초창기 암호(사실 현대암호의 시초이기도 함)인 One-time pad라는 엄청 간단한 암호를 볼꺼다.

간단하긴 하지만, 우리가 원하는 논의를 다루기에는 충분함.



이 암호에서는 메세지, 키, 암호문 모두 Z mod 2^n의 원소로 생각할거다.

우리는 암호화,복호화 알고리즘만 알면 된다.


[One-time pad=OTP]

-암호화알고리즘: 메세지 m과 키 k에 대해 암호문 c=m+k mod 2^n을 만든다.

-복호화알고리즘: 암호문 c와 키 k에 대해 메세지 m'=c-k mod 2^n을 만든다.


이 알고리즘은 암호화, 복호화에 같은 키 k를 쓰면 복호화된 메세지 m'과 암호화할때 쓴 메세지 m이 같은건 명백하다. (correctness)

근데 이게 암호라고 하면... 어떤 센스에서 안전할까? 바로 다음과 같은 조건 하에서다.


[공격문제 1 (search 문제)] 주어진 암호문 c에 대응되는 메세지 m을 찾아라.


[공격자의능력 A] 주어진 암호문 c로 어떻게든 공격을 해본다.


두번째껄 뭔가 잘 적기가 어려운데, 말하고자 하는 바는 능력 A를 가진 공격자는 주어진 암호문 말고는 아무것도 모르고 공격을 하겠다는거다.

공격 알고리즘은 다항식시간 알고리즘 아무거나가 될거임.




근데, c를 보고 (k를 모르면서) m을 복구한다는게 가능하냐? c는 k에 따라 Z mod 2^n의 아무 원소나 될 수 있는거잖아.

이런 생각을 엄밀하게 적어보면 다음과 같다.


[팩트 1] 임의로 고정된 m에 대해 다음이 성립한다.

{c:k를 랜덤으로 뽑고, c:=m+k mod 2^n} = {r: r을 Z mod 2^n에서 아무거나 뽑음}


이게 뭔말이냐면, 공격자의 능력이랑 별개로 암호문 c랑, 그냥 랜덤으로 주어진 수 r이랑 구별 자체를 못한다는거임.

이런애가 m을 찾을수는 없지. 공격자가 답을 뭐로 내든 답이 맞을 확률이 (k를 랜덤으로 뽑혔다고 생각하면) 1/2^n=무시할만큼 작은거고, 그래서 다음이 성립함.


[정리 1] OTP에 대한 공격문제 1은 능력 A로 풀기 어려운 문제다.





근데 [팩트 1]을 잘 보면, 공격문제를 좀 더 어렵게 생각해도 되는걸 알수있음.



[공격문제 2 (decision 문제)] 정해진 메세지 m0, m1과 랜덤으로 골라진 b=0 or 1에 대해 mb를 암호화해서 c를 만들었다고 생각하자.

c,m0,m1을 가진 상태로 b를 결정하여라.



이게 왜 성립하냐면, [팩트 1]에 대해


{c:k를 랜덤으로 뽑고, c:=m0+k mod 2^n} = {r: r을 Z mod 2^n에서 아무거나 뽑음}={c:k를 랜덤으로 뽑고, c:=m1+k mod 2^n}


이 성립하기때문이지. 그래서 다음과 같은 OTP의 안전성도 말할수 있겠지.


[정리 2] OTP에 대한 공격문제 2는 능력 A로 풀기 어려운 문제다.



정리 1,2를 간단하게 "OTP는 1-A 안전하다, 2-A 안전하다" 라고 함.


------Remark, 안읽어도 됨------

눈치빠른 사람은 이 암호문에서 공격자가 다항식시간 알고리즘일 필요가 없다는걸 알수있을거임.

이 암호는 공격자가 얼마든지 강해도 (예를 들어 NP문제를 1초만에 푸는 애라도) 능력 A를 이용해서는 문제 1,2를 그냥 찍는거보다 좋은 확률로 풀수가 없다.

이런거를 Perfect security라고 함.

근데 여기서 다항식시간 알고리즘만 다루는척 하는 이유는, 사실 그래야만 하는 예시도 다루려고 적다가 너무 귀찮아져서 이거만 남았기때문임.

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



이제 [OTP가 안전하다]라는 말이 뭔지는 알겠지? 이걸로 이 글의 목표는 대충은 말했는데, 너무 별거 안한거같다.

"공격문제의 정의"와 "능력의 종류"에 대해 조금 더 얘기하겠음.




2. 공격문제 2의 의미: 의미론적 안전성 (semantic security)


위에서는 공격문제 2를 그냥 이렇게 정의하는게 자연스러운척 슬쩍 넘어갔는데, 사실 저렇게 정의하는데 다 이유가 있다.


공격문제 1은 뭐 별 할말 없지? 암호문을 보고 메세지를 알면 안되잖아.

근데 이게 불충분하다는걸 어느순간 사람들이 알아챘다. 다음과 같은 시나리오를 생각하자.


[시나리오]

메세지 "엄준식은 살아있다"를 암호화해서 c를 만들었다고 치자. 공격문제 1이 어려우니까 메세지 자체는 알 수 없지.

근데 암호문을 보고 메세지의 반정도를 알수 있다면? 예컨대, "엄??은 살아??"를 복구했다고 치자.

롤방송을 맨날 보는놈들이라면 이정도 부분 메세지를 보고 충분히 복구 가능하지 않을까? 이거 문제있다.



뭐 이런 시나리오 말고도 암호화 키의 반정도를 복구했는데, 그게 어떤 문장처럼 보인다 이런거도 엄청 큰 힌트가 되겠지.


그럼 어떻게해야 암호가 "안전"하다고 할까?

시작에도 말했지만 이거에 답한사람이 Shafi Goldwasser랑 Silvio Micali임.

이거가지고 튜링상 받았으니까 어렵게 들리는데, 사실 그렇게 어렵지 않음. "공격자가 뭘 배울수 있는가"를 생각하는거임.

이상적으로는 공격자가 "아무런 정보도 얻지 못해야한다". 이걸 어떻게 엄밀하게 말할수 있을까? 바로 다음과 같은 문장임.


[암호문을 이용해서 할수 있는 모든것은 암호문 없이도 모두 할수있다.]


혹은 약간 더 엄밀하게, "시뮬레이션"을 통해 정의할수 있음.

무슨말이냐면, 우리는 다음과 비슷한 의미를 가지는 정의를 만들거임.


[임의의 암호문을 갖고 공격하는 공격자가 얻을수 있는 정보를,

"!!암호문이 없는!!" 시뮬레이터가 똑같이 따라할수 있다.]


이걸 포말하게 적으면 다음이 됨.


[OTP의 능력 A에 대한 의미론적 안전성]

임의의 (능력 A를 가진) 다항식시간 공격알고리즘 X에 대해서, 다항식시간 시뮬레이터 S가 존재해서 모든 다항식시간에 계산되는 "정보함수 f"에 대해

Pr[X(c)->f(m)] 와 Pr[S()->f(m)]의 차이가 무시할만큼 작을 때 OTP가 semantically A-안전하다고 말함.


여기서 f는 메세지에 대한 아무 새어나갈수 있는 정보인거임.



뭐 그럴듯한 정의인데, 이걸가지고 대체 뭘 할수 있을까? 임의의 f,h를 들고와야하고, 임의의 공격을 들고와야하구.. 어쩌구저쩌구...

말 그대로 "의미론적"으로는 의미가 있어보이는데, 우리가 저 정의를 만족하는걸 보이는건 쉽지않아보임.

그래서 Goldwasser랑 Micali가 보인게 바로 다음 정리(의 필요한 부분)임.

(일반적으로 공개키암호에 대해 증명했는데, 우리한테 필요한 형태로 적을거임 그리고 반대방향 (의미론적안전->문제2 안전)은 나중에 증명됐는데, 별로 중요하지 않지.)


[정리] OTP가 2-A 안전한거랑, semantically A-안전한거랑 동치이다.


와, 우리가 위에서 봤듯이 2-A 안전한걸 보이는건 엄청 쉽잖아? 그리고 complexity theory에서 맨날 다루는거도 decision 문제고.

그니까 우리가 잘 아는 정의 (2-A 안전)가 "의미론적"으로 안전한거랑 동치라는거임.

엄청 좋잖아? 게다가 2-안전 계열이 더 많은 좋은 성질을 갖는게 나중에 증명이 됨.

이건 기회가 되면 다루도록 할게 (아마 안다룰듯..)



증명은 여기서 자세히 하지는 않을건데, 2-A 안전 => semantically A-안전의 아웃라인은 대충 다음과 같음:

S는 다음과 같이 함

1. 스스로 메세지 0에 대한 암호문c'을 하나 만들고, 키를 잊어버림.

2. 그리고 c'에 대해 X를 돌리는거임.

근데 위에서 말했듯이 다항식공격자는 c랑 c'을 구별 못하잖아?

그래서 공격자 X가 c에대해 f(m)을 낼 확률이나 c'에 대해 f(m)을 낼 확률이나 비슷비슷하고 (그렇지 않으면 c랑 c'을 구별할수 있겠지?) 그래서 끝남.



--------Remark, 안읽어도 됨--------

사실 원래 명제는 non-uniform algorithm등도 고려하고, 뭐 이것저것 다양하게 복잡하게 고려해야할게 많음.

그래서 귀류법으로 증명해야만 하고. 근데 아웃라인은 결국 똑같음

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



엄청 간단하지? 이런 관점으로 2-안전한게 엄청 중요하고, 이런 정의는 후에 다양한 암호의 formalism의 기초가 됨.

그래서 튜링상도 받은거고.

참고로 1=One-way=OW, 2=indistinguishability=IND 라고 많이 씀.




3.능력 A가 끝인가?


사실 위로 끝내는게 글은 깔끔한거같은데, 아직 얘기를 한번도 안한게 있지. 왜 능력을 A만 줬을까?

왜냐면 OTP는 이거에만 안전해서 안쓰는 스킴이기때문임. 능력 A는 현실적으로는 별 의미가 없는 능력이거든.

다음과 같은 다양한 다른 공격능력의 예시를 볼게 (능력이라는 단어가 선택이 별로 안좋아서 문맥상 이상할수 있는데, 그냥 대충 이해해라)



[여러 암호문 능력(multiple message)]

예를 들어, 하나의 키로 두개의 메세지를 암호화하면,

c1=m1+k, c2=m2+k

에서 두 암호문을 빼면 두 메세지의 차를 알 수 있잖아? 이건 충분히 위험할수 있는 정보임.


[알려진 메세지 능력]

아니면 이미 암호키를 한번 써서, (메세지,암호문) 쌍 (m0,c0=m0+k)가 알려져있는 상황은 어떨까?

이 경우에는 k를 바로 알 수 있어서 전혀 안전하지 않겠지? 이런 종류의 공격을 알려진 메세지 공격이라고 부름.

(위 글에서 "공격" 대신 "능력"이란 단어를 쓴건 이 공격이 공격의 class인데, 그냥 하나의 공격이랑 모호하니까 그렇게 쓴거임)



다른 어떤 공격들이 있을까?

실제 많은 상황에서 [공개키암호]를 다루는데, 얘는 암호 키가 공개키와 비밀키로 나뉘지.

암호화하는데는 공개키로 암호화하고, 그래서 아무나=공격자도 할 수 있어.

복호화는 비밀키로 하니까 아무나 못하는거고.

그래서 공격자에게 "암호화하는 능력"을 주는 [메세지 고르는 능력], 혹은 chosen plaintext attack (CPA)이 가능함.


이거 말고도 "암호문을 몇개 골라서 복호화하는 능력"같은걸 주기도 함. 이건 chosen ciphertext attack=CCA라고 부르고.


이거랑 OW, IND를 합쳐서 많이 부르지. 이론적으로 보통 원하는건 IND-CCA security로 꽤나 강력한 조건임.



(살짝 IND의 힘을 보면, IND-CPA security가 한 암호문에 대해 성립하면, 여러 암호문에 대해서도 똑같이 성립함! 어떻게 증명할까?)




4.그러면 IND-CCA secure한 암호는 안전할까?


사실 현실적으로는 아닐수 있음. 왜냐면, 위 시나리오에서는 암호화, 복호화 알고리즘을 [블랙박스]로 쓰거든.

무슨말이냐면, 얘네의 구현 과정은 전혀 고려하지 않고, 그냥 인풋 넣으면 아웃풋 주는 새까만 박스로 생각한다는거임.

근데 현실적으로는 그렇지 않거든? 예를 들어서 0을 암호화할때는 계산을 할게 별로 없어서 0.01초가 걸리고, 다른 메세지를 암호화할때는 0.02초가 걸리는 경우가 있을수있어.

이럴때 암호화하는데 걸리는 시간을 측정해서 메세지를 복호화하기도 함. 이런거를 "부채널어택 = side channel attack"이라고 한다.

그래서 실제로 구현하는데에도 엄청 이슈가 많은거지. 심지어 코드에는 아무런 문제가 없는데, 컴파일러가 최적화하는 과정에서 저런 현상을 만들어내기도 함. 효율적이기 위해 한 최적화가 현실적으로 암호학에서 위협이 되는거지.

효율과 안전성이 싸우는게 이론이나 현실이나 꽤나 비슷함.


나는 사실 이런쪽은 잘 모름. 이건 공대쪽에서 하는거임.


그럼 안녕. 다음에 더 적을지는 잘 모르겠네.