난독화 이야기 (1) 에서 가상 블랙박스 난독화, 즉 임의의 프로그램을 인풋-아웃풋만 알 수 있도록 일종의 “프로그램을 암호화”하는 난독화 기술이 불가능함을 설명했다. 그렇다면 자연스러운 질문은 얼마나 강력한 난독화가 가능한지, 가장 좋은 난독화가 무엇인지에 관한 것이다. 한참 쉬었는데, 난독화에 관한 콴타매거진 기사가 올라와서 다시 돌아와서 조금 더 써봄ㅋ

---

사실 2001년의 가상 블랙박스 난독화 불가능성 논문에서 이미 제시한 개념이 있다. 바로 구별불가능성 난독화, indistinguishability obfuscation, 소위 “IO”라고 불리는 난독화이다. 구별불가능성 난독화는 두 동등한 프로그램, 즉 크기가 같고 입출력이 같은 프로그램 A와 B를 난독화한 결과 O(A)와 O(B)가 구별 불가능하게 만들어준다.

[정의]구별불가능성 난독화 O는 프로그램 P를 인풋으로 받아 다른 프로그램 O(P)를 아웃풋으로 내는 효율적인 컴파일러로써 다음을 만족한다.

1. (정확성) P의 입출력을 그대로 보존하여 O(P)(x)=P(x)를 만족한다
2. (안전성) 크기가 같고 입출력이 같은 프로그램 A,B에 대해 O(A)와 O(B)가 구별 불가능하다.

여기서 구별불가능하다는 것은 임의의 효율적인 알고리즘을 들고와도, X=A 또는 B에 대해 O(X)에서 X가 A인지 B인지 결정할 확률이 맞출 확률이 1/2, 즉 찍는 것에 가깝다는 것.처음 보면 이게 뭔 의미인가 싶다. 나도 그랬다 -_- 하지만 이 정의만으로도 꽤 많은 프로그램의 정보를 숨길 수 있다. 다음 예시를 보자.

은행 등의 앱을 편리하게 이용하기 위해서는 일부 개인정보, 예를 들어 계좌번호와 비밀번호 등을 앱에 저장해놓는 것이 편리하다. 이를 가장 효율적으로 구현하는 방식은 그냥 비밀번호와 계좌번호를 그대로 앱에 저장해놓는 것. 근데 이건 앱을 뜯어볼 수 있으면 비밀번호와 계좌번호를 그대로 볼 수 있고, 바로 개인정보의 유출로 이어진다.

그렇지만 만약 발전한 암호기술을 바탕으로 계좌번호와 비밀번호를 암호화한 상태로 똑같은 태스크를 할 수 있다면? 이 경우에는 앱을 뜯어도 얻을 수 있는 정보가 없다. 바로 IO가 말하는 것은, 이 두 프로그램을 IO로 난독화 한 경우 구별이 불가능하고, 따라서 단순히 구현한 프로그램을 난독화하는 것만으로 프로그램을 뜯어보는 것에 대한 강력한 보안을 얻을 수 있다는 것.

---

잠깐, 우리는 난독화된 프로그램의 안전성을 논하기 위해 다른 안전한 프로그램을 들고왔다. 이 생각을 천천히 살펴보면 다음과 같은 직관을 얻을 수 있다.

IO를 이용해 난독화한 프로그램은 모든 입출력이 같은 프로그램 중 가장 안전하다!

이런 직관에 착안하여 2007년 골드와서 교수님과 그 제자였던 Guy Rothblum이 Best-possible obfuscation이라는 개념을 제안했다. 즉 난독화된 프로그램이 동등한 프로그램 중 가장 안전해지는 난독화 기술이 무엇인지에 대해 질문을 제시한 것.

저자들의 대답은 다음과 같다.

[정리] 컴파일러 O가 효율적인 IO 방법인 것과 효율적인 Best-possible 난독화인 것은 동치이다.

아주 간단하고 깔끔하다. 이 정리를 조금 더 엄밀하게 말하기 위해 Best-possible obfuscation (BPO)의 정의를 다음과 같이 살짝 정의하자.

[정의] Best-possible 난독화 O는 프로그램 P를 인풋으로 받아 다른 프로그램 O(P)를 아웃풋으로 내는 효율적인 컴파일러로써 다음을 만족한다.

1. (정확성) P의 입출력을 그대로 보존하여 O(P)(x)=P(x)를 만족한다
2. (안전성) 임의의 알고리즘 L에 대해서, 그리고 임의의 크기가 같고 입출력이 같은 프로그램 A,B에 대해 다음을 만족하는 효율적인 알고리즘 S가 존재한다:

L(O(A))와 S(B)의 결과 분포가 구별 불가능하다.

정확성은 IO와 정확히 같고, 안전성은 언뜻 봐서는 무슨 뜻인지 꽤 헷갈린다. 대충 그 뜻을 해석해보자면, 난독화 결과 O(A)에서 얻을수 있는 결과는 사실 임의의 다른 동등한 프로그램 B에서 얻을수 있었다는 뜻. 다시 말하면 O(A)에서 유출되는 정보는 다른 모든 동등한 프로그램에서 이미 유출되고 있다는 것.

이제 위 정리는 다음과 같이 증명할 수 있다.

[BPO=>IO] O가 BPO라고 하자. L을 identity, 즉 O(A)의 결과를 그대로 내는 알고리즘이라고 하면 임의의 동등한 두 프로그램 A,B에 대해 (O(A), S(A)), (S(A),O(B))가 각각 구별 불가능하고, 따라서 O(A)와 O(B)도 구별 불가능하다.
[IO=>BPO] O가 IO라고 하자. 임의의 L에 대해 S를 잡아줘야 한다. S(*)=L(O(*))로 정의하면 O(A)와 O(B)가 구별 불가능한 것에서 L(O(A))와 L(O(B))도 구별 불가능.

아주 간단하고 쉽다. 이 논문 이후 난독화의 이론적 연구는 IO가 옳은 목표라는 것에 많이들 동의하게 되었고, 이후 수년간 정체되어 있다가 2013년에 처음으로 그럴듯한 일반적인 난독화 기술이 나온다. 이는 다음 글에서 다룰 예정.

마지막으로 이 논문의 독특한 결과는 다음과 같다.

[정리] P=NP라면 BPO가 존재한다.

암호학적으로는 굉장히 어이없는 결과인게, 암호 시스템이 안전하다는 것은 보통 P≠NP보다도 강력한 결과이다. (즉, 암호가 (다른 가정 없이) 안전하면 P≠NP가 성립한다.) 증명은 자세히는 조금 복잡하고, 대충 아래와 같다.

P=NP라면 임의의 프로그램에 대해 동등한 프로그램 중 "가장 짧은" 프로그램을 효율적으로 찾을 수 있다. 그리고 이 가장 짧은 프로그램은 동등한 두 프로그램 A,B에 대해 같으므로, 이 과정은 IO이고 따라서 BPO이다.

한동안 연구 주제로 잡았던 것 중 프로그램을 “읽기 어렵게 만드는” 난독화라는 기술이 있다. 프로그램 난독화 기술은 여러가지 이유로 2013년 정도부터 (이론적) 암호학에서 현재 가장 중요한 주제로 떠올랐다.

특히 구별불가능성 난독화(Indistinguishability Obfuscation)의 존재성이 그 핵심 문제인데, 이를 가장 활발히 풀던 연구자들이 해당 기술이 가능하다고 주장하는 논문을 최근 포스팅했다.

따라서 이를 기념(?)하기 위해 이 방향의 연구의 큰 이야기들을 몇 개의 글로 정리해보고자 한다. 다만 의욕이 항상 없어 다음 이야기가 언제 나올지는 의문 ㅋ

이번 글에서는 프로그램 난독화의 초창기 결과인 2001년의 보아즈 바락(Boaz Barak)등이 증명한 가상 블랙박스 난독화(Virtual Black-box Obfuscation)이 불가능하다는 논문에 대한 이야기를 하고자 한다. 증명이 아주 간단하다!

계속 읽기 →

얼마전 Crypto 2020에 발표될 논문들이 공개되었다. 이중에 재밌을만한걸 소개해보려 했는데, 딱히 비-암호학자에게 흥미로운 내용은 안보이는듯 -_- 대신 작년 Crypto 2019에서 발표되고 Best paper award를 받은 결과인 OCB2 인증암호에 대한 공격에 대해 살짝 소개해보려 한다.

OCB2는 필립 로가웨이(Phillip Rogaway)가 2004년 Aisacrypt에서 소개한 블럭암호(의 Mode of operation)를 이용한 인증방식으로, 2001년 로가웨이가 미히르 벨라르(Mihir Bellare)와 존 블랙(John Black)과 함께 만들었던 OCB1의 변형이다. 이후 OCB3도 제안되었는데, OCB1,2,3 모두 ISO/IEC 19772:2009로 아예 스탠다드로 정해진 방식이다. 또한 이전의 많은 연구에서 그 이론적 안전성이 다양하게 증명되고 뒷받침 되었다.

그런데 놀랍게도 Inoue등에 따르면 이 인증암호가 엄청나게 간단한 공격으로 평문이 복원되는 등의 문제가 있다고 한다! 이 논문의 결과로 OCB2는 ISO/IEC 스탠다드에서 제외되었다. 어떻게 이런 일이 일어날 수 있을까?

답은 간단하다. 로가웨이가 증명에서 실수한 부분이 있기때문 -_- 엄청 자세히 본건 아닌데, 로가웨이는 OCB2의 설계의 기반이 되는 방식으로 XEX*라는 새로운 연산을 정의했다. 이는 XE와 XEX라는 간단한 연산의 혼합인데, XEX*는 인풋을 받을때 태그를 같이 받아서 XE를 적용할지, XEX를 적용할지 선택할 수 있다. 근데 XEX*는 같은 메세지에 대한 다른 태그(즉, XE와 XEX)를 적용할 수 있다면 전혀 안전하지 않다고 한다.

로가웨이도 이걸 알았는데, OCB2에서 그런 방식의 계산이 없다고 생각한 듯 했나보다. 꽤나 subtle한 문제인가봄. 그런 가정 하에서는 안전성 증명이 가능하다고 한다. 근데 사실은 가능했던것 -_- 이게 15년 넘게 간과되고 있었고, 이번에 이게 사실 문제라는게 지적되었던 것. 증명이 별로 어려운 것도 아닐텐데, 조금 어이가 없다.

다행인 점이 몇가지 있는데,

• OCB1과 OCB3는 XEX*를 쓰지 않고, 그래서 이 공격에 영향을 받지 않는다. (뿐만 아니라 증명이 아마 틀리지 않을것이라고 믿고있다.) 참고로 현재 가장 많이 쓰이는 것은 효율성 등의 이유로 OCB3. 사실은 로가웨이도 예전부터 OCB3를 쓰라고 추천했다고 한다. 그리고 OCB2도 XEX*대신 그냥 XEX를 쓰면 안전하다고 한다.
• OCB2는 특이하게 특허가 걸려있고, 그래서 OCB2를 이용하는 예시가 거의 없다! 한 트위터 타래에서는 암호 특허의 최초의 현실적 쓸모라고 비꼬았다 ㅋㅋㅋ

이 문제가 발견된 이야기도 꽤 흥미로운데, 저자 카즈히코 미네마츠(Kazuhiko Minematsu)가 대학원생인 아키코 이노우에(Akiko Inoue)에게 교육를 목적으로 OCB2의 안전성 증명을 확인했다고 한다. 근데 두 사람은 어느순간 위에 언급한 증명의 문제를 찾아내었고, 크지 않은 갭이라고 생각해서 메꾸려고 한참 노력하다가 결국 existential forgery라는 공격(인증 부분을 깨는것)을 찾았다고 한다. 그래서 이걸 ePrint아카이브에 올리고, 그 두어주 후 베르트람 포테링(Bertram Poettering)과 테츠 이와타(Tetsu Iwata)가 각각 IND-CCA, OW-CCA공격(혹은 평문 복호화)을 찾았다고 한다. 논문의 Appendix A에서 대충 확인할 수 있음 ㅋ.

사실 나는 다른 사람에게 썰을 듣고 증명과 설계가 달라서 공격이 된거로 알고 있었는데, 알고보니 증명 자체가 틀린거네 -_- 아마 그 사람이 결론의 다음 문장을 읽고 착각한것 같다.

This was possible due to the discrepancy between the proof of OCB2 and the actual construction.

실제 공격에 대한 설명은 논문이나 유튜브에 기록된 발표, 혹은 react0r 블로그글정도에 꽤 잘 정리되어 있는듯.

암호학계에서는 증명이 꽤 그럴듯하면 어느정도 대충 읽는 경향이 있는것같다. 특히 로가웨이정도면 굉장히 유명한 학자라서 더 그랬던듯. 결론부에 따르면 이거 말고도 이전에 몇몇 안전성이 증명된 스킴들이 틀린 부분이 발견된 적이 있나보다. 다행히도 듣기로는 스탠다드로 정해진것 중에서 공격이 된건 OCB2가 처음이라는듯. 정말 암호 특허의 현실적인 쓰임이다 -_-

여튼, 논문에 나온대로 결론은 안전성 증명의 퀄리티와 검증이 굉장히 중요하다는 것!