6 분 소요

강의를 듣고 정리한 것이 아닌 ppt만 참고하여 내용을 정리한 것입니다.
SnP 연구실 김지혜 교수님의 도움을 받아 작성되었습니다.

Lecture 1 : Definitions

이번 포스팅은 1장에 대해서 설명하려고 한다.

스크린샷 2022-09-26 오후 8 48 06

Outline은 아래와 같다.

스크린샷 2022-09-26 오후 8 52 23

1. Classical Cryptography vs Modern Cryptography

■ Classical Cryptography vs Modern Cryptography

스크린샷 2022-09-26 오후 8 56 18

Classical cryptography는 20th 이전에는 art으로 불렸는데, 20th 이후로는 science와 Modern Cryptography로 불렸다.

Modern Crpytography는 기본적으로 define할 것이고, model을 만들고 proof하는 과정을 하는 것에서 classical cryptography랑 구별된다.

  • [definitions]Definitions of algorithms->input/output만 가지고 정의(알고리즘의 흐름을 이야기X), hard assumptions, advantage
  • [model] Computational model, security model
  • [proof] Security reduction, game-hopping proof -> reduction을 이용해서 증명할 것이다.

Reduction이란?

Scheme이 안전하다는 것을 보이기 위해 보이는 것으로, Scheme을 깨는 attacker가 존재한다면 가정을 깨는 attacker가 존재하게 된다.

그런데 가정은 computationally 풀기 어렵다는 가정이 있기 때문에 모순이 되고, 결국 scheme이 안전함을 증명하게 되는 증명 기법입니다.

■ Clarified Concepts

스크린샷 2022-09-27 오후 12 35 04

Cryptography는 security mechanism으로, authentication, confidentiality, integrity 등을 제공한다.

Cryptanalysis는 cryptography를 분석하는 것이다.

Cryptosystem은 Cryptography보다 더 구체화된 것으로, security service를 제공한다.

Scheme은 하나의 Cryptosystem에 대한 구체적인 하나의 construction을 의미한다.

도식화하여 살표보면 아래와 같다.

스크린샷 2022-09-27 오후 12 42 22

스크린샷 2022-09-27 오후 12 42 49

2. How to Define Algorithms

■ How to Define Algorithms for a Cryptosystem?

스크린샷 2022-09-27 오후 12 45 10

여기서는 Cryptosystem에서 알고리즘을 어떻게 정의할 것인가에 대한 이야기를 한다.

**참고! 앞으로의 설명을 위해 사용하는 예시는 Digital Signature이다.**

일단 가장 먼저, security service를 완전히 이해해야 한다. 예를 들어서 Digital Signature라면 authentication를 제공하는데, 왜 authentication이 필요한지, 어떤 역할을 하는지 정확히 이해해야 한다.

그 다음으로 어떤 entity가 결합되어 있는지 생각해야 한다. 계속 Digital Signature로 본다면, 메시지에 대한 서명을 하는 Signer와 해당 메시지에 대한 서명에 대해 검증하는 Verifier가 있을 것이다.

그리고 얼마나 많은 알고리즘이 관련이 있는지 알아야 한다. 메시지에 대한 서명을 하는 Sign algs만 있으면 되나? 서명을 위한 Key 생성은 어떻게 할 것인가?에 대해서 생각해보면 서명을 위한 Sign, 검증을 위한 Vfy, 키 생성을 위한 KeyGen 알고리즘이 필요하다는 것을 알 수 있다.

각 알고리즘의 이름을 위와 같이 설정할 수 있고, 각각의 알고리즘을 누가 실행하는지도 이해해야 한다. 또한 각 알고리즘의 이름과 기능을 생각했으면 해당 알고리즘이 가져야 하는 input과 output이 무엇인지 설정해야 한다.

마지막으로 알고리즘이 충족해야 하는 correctness는 무엇인지 생각해야 한다. 알고리즘을 만들었다면 그 알고리즘이 정확한지에 대한 믿음이 필요하기 때문에 correctness를 반드시 알아야 한다.

이렇게 위에서 살펴본 것들을 Algorithm Definition에 다 넣어야 한다.

■ How to Define Algorithms for Digital Signatures?

스크린샷 2022-09-27 오후 12 56 28

위에서 간단하게 이야기했지만, 여기서 Digital Signature에 대한 알고리즘을 어떻게 정의하는지 살펴본다.

Motivation 아래에 대한 것은, 이 Digital Signature라는게 어떤 식으로 쓰이느냐에 대해서 설명한 것이다.

Alice는 “내가 만든 메시지야!” 라고 다른 사람들한테 설득하고 싶은 상황이다. 그래서 Alice는 key pair를 생성하고 PK(Public Key)를 공개한다.

그리고 Alice는 “내가 만든 메시지야~”라는 것을 보장해주기 위해 메시지에 대한 서명을 자신의 SK(Secret Key)로 만든다. Alice가 서명을 만들었으면 메시지와 메시지에 대한 서명을 다른 사람들한테 수신하고, 수신자는 서명을 확인하여 메시지의 출처가 Alice가 맞음을 알 수 있다.

이런 Motivatioin을 보고 어떤 entity가 있고 어떤 알고리즘이 있는지 도출해낼 수 있어야 한다.

  • Which entities (not names) are involved.
    Signer, Verifier

  • How many algorithms are involved
    1 (system paremeter generation) + 3

  • What is the name of each algorithm
    SysGen, KeyGen, Sign, Verify

    -> 여기서 SysGen은 first step으로, 전체 system의 public parameter를 생성하는 알고리즘으로 이해하면 된다.

  • Who runs each algorithm
    SysGen(Authority), KeyGen(Signer), Sign(Signer), Verify(Verifier)

    -> 누가 각각의 알고리즘을 run할 것인지에 대한 것인데, 이건 관점에 따라 다르다. 하지만 여기서는 KeyGen을 trusted third party가 생성하는 것이 아닌 Signer가 직접 생성한다. 본인이 생성하면 더 Security하다. 왜냐하면 본인이 생성하는 것이니까 그 어떠한 사람도 Key를 알 수 없다.

스크린샷 2022-09-27 오후 1 12 57위에서 entity와 알고리즘 등 다 정의했으니 이제 I/O를 만들면 된다.

\[SysGen(\lambda) \rightarrow SP.\]

SP는 system의 public parameter 생성된 것이라고 생각하면 된다. SP로 security level을 결정한다.

이런식으로 알고리즘을 정의했다.

여기까지 했으면 scheme을 만들었다고 생각할 수있는데 그렇지 않다. 적어도 이 알고리즘이 어떻게 된다라는 것만 확인한 것이다.

여기서 이제 더 나아가서 corectness를 말해야 한다.

스크린샷 2022-09-27 오후 1 26 03

이 페이지에서는 조금 더 기능적인 이야기, 조금 더 자세하게 이야기한 것이다. 보통 논문에서 이 Level로 작성한다.

Note부분을 보면, 보통 deterministic이 아니라 probabilistic polynomial time algorithms으로 구성된다고 보면 된다. 줄여서 PPT라고 말한다.

스크린샷 2022-09-27 오후 1 27 52

이제 다시 돌아와서, 알고리즘을 정의했으면 그 정의는 correctness를 만족해야 한다.

예를 들어서 그냥 알고리즘이 있다고 해서, signer가 알맞게 서명을 했는데 verifier가 검증하는 알고리즘을 reject하면 안된다. 그렇게 될 경우 알고리즘의 의미가 없다. 따라서 guarantee 해야되는 correctness가 필요하다.

\[Verify(SP,PK, m, Sign(SP, SK, m)) = 1\]

위와 같은 식으로 correctness를 명확하게 이야기해야 한다.


이렇게 다 알고리즘의 Definition과 Correctness를 말했으면 이제는! CryptoSystem을 만들었다!라고 말할 수 있다. :)

스크린샷 2022-09-29 오후 8 46 48

3. How to Define Security Models

이렇게 우리는 알고리즘을 정의했습니다. 그런데 여기서 더 나아가 우리는,,

“공격자가 sk 없이도 서명을 만들어서 verify를 할 수 없게 해야 한다.” 라는 이야기, 즉 조작할 수 없는 공격자 이야기까지 포함이 되어야 한다.

그래서 이런것들을 만족해야 하는 Security Model도 필요하다. 쉽게 말해서 공격자에 대한 내용도 필요하다.

■ Questions Before Security Model

스크린샷 2022-09-29 오후 8 59 34

그러면 Security model을 보기 전에 몇 가지 질문을 해본다. scheme의 security를 어떻게 분석해야 하고, scheme은 다 방어를 할 수 있어야 하는지, scheme에 대해서 security model이 정의되어 있는지?

공격자가 어떤 알고리즘을 쓰는지는 모른다. 그렇기 때문에 어떻게 공격햇는지 focus를 두는 것이 아니라, 우리의 focus는 최종적으로 공격자가 어떤 정보(hint)를 얻는지에 대한 것이다.

■ What is Security Model?

스크린샷 2022-09-29 오후 9 03 43

다시 이야기하면! 공격자가 어떻게 공격하는지는 궁금하지 않고 어떤 정보를 얻을 수 있는지에 대해서 궁금한 것이다.

우리는 cryptosystem에서 scheme을 제안할 때, replay attack or collusion attack같은 security는 분석하지 않는다. Security model은 list of attack을 추상적으로 표현한 것이다. Security model은 scheme이 아닌 cryptosystem에 대해 정의된다.

■ How to Define a Security Model?

스크린샷 2022-09-29 오후 9 13 49

Attacker가 정보를 얻는걸로 표현한다고 했는데, Attacker가 최대한 얻을 수 있는 정보를 interactive하게 표현할 것이다.
앞에서 Security model은 추상적으로 표현한 것이라고 이야기 했는데, 보통 game model로 적는다.

Game에서는 adversary, challenger 주체가 있다. challenger는 adversary한테 정보를 주는 존재이다. 그래서 challenger는 sk를 가지고 있지만 adversary한테 sk를 주지는 않고 adversary가 질문하는 것에 대한 올바른 대답만 해준다.(sk가 안전하게 되어있다고 가정함). Adversary는 challenger한테 받은 정보들을 가지고 Cryptosystem을 깨는 시도를 한다. 이런식으로 Adversary와 Challenger의 interaction을 Game으로 표현한 것이다.

그래서 Security model을 정의해보면 크게 2개를 정의한다.

  1. The adversary’s capabilities:

    • What information the adversary can query
    • When the adversary can query information

    -> 공격자가 정보를 얻는것을 어느정도까지 허용할 것인가에 대한 내용이다. 예를 들어서 몇개의 서명만, 어떤 유저의 메시지의 서명만 접근하게 할 것인지, 공격자가 선택한 메시지에 대해서만 서명을 얻을 수 있는 것인지 등등..

  2. The adversary’s security goal:

    • How the adversary wins the game (breaks the scheme).

    -> Digital Signature에서의 high level로 말하면, 공격자가 원하는 메시지에 대해서 유효한 서명을 만드는 것이 공격자의 security goal이된다. Game에서 interaction을 통해 최종적으로 sk없이도 유효한 서명을 만들었다! 가 되면 security goal을 성공한 것이다.

스크린샷 2022-09-29 오후 9 25 53

Security model의 definition은 4개의 파트로 구성된다.

  1. Setup : adversary와 challenger 초기화
  2. Capabilities : 이것에 대해서는 interaction으로 이야기할 것이다. 어떤 Information에 대해서 query하고 받는지, 언제 가능하게 할건지에 대한 이야기이다.
  3. Security Goal : adversary가 game을 이길 확률을 advantage라고 한다.
  4. Advantage : 만약에 parameter가 negligible(ex. $1/2^{10}$ 정도의 아주 작은 값)이면, cryptosystem은 secure하다라고 한다. 그렇지 않은 경우 non-neg이면 insecure하다고 한다.

■ When Defining a Security Model

스크린샷 2022-09-29 오후 9 34 42

앞에서 계속 언급했듯이 Security model을 정의할 때, 공격자가 어떤 input(query)를 던지고 어떤 답을 받는지에 대한 input/output만 focus로 둔다.

예를 들어서, 공격자가 메시지 m에 대해서 서명을 쿼리했을 때, challenger는 쿼리에 대한 응답을 해야 한다. 여기서 우리는 서명을 어떻게 생성하는지, 서명이 어떻게 생겼는지 신경쓰지 않고 공격자가 무엇을 쿼리했는지(예. 메시지 m)에만 관심이 있다.

스크린샷 2022-09-29 오후 9 47 16

security model을 define할 때 우리가 고려하지 않는 것들이 있다. 첫 번째는 trivial attack은 고려하지 않는다. 예를 들어서 sk값을 얻게 한다면 당연히 공격자가 깰 수 있으니까 고려하지 않는다. 두 번째는 공격자가 어떻게 이겼는지 고려하지 않는다. 앞에서 계속 이야기했던 부분이다. Input/ouput만 고려하는 것이고, 쉽게 생각해서 공격자도 알고리즘인데 블랙박스같은 존재로 생각하면 된다.

이렇게! Security model에서 최종적으로 무엇을 증명하냐면 the advantage is negligible이다! 이것이 cryptosystem의 끝이다.

풀어서 이야기하면 어떤 cryptosystem(알고리즘, security model ->adversary와 challenger가 interaction이 존재할 때)이 있는데 이 adversary가 이길 확률이 negligible이다!라면 scure한 cryptosystem이다!라고 하겠다는 것이다.

■ Security Model for Digital Signatures

IMG_D10F71B53A20-1

이 페이지에서는 ppt 안에 적힌 필기를 참고하며 넘어가겠다.

스크린샷 2022-09-30 오전 11 08 16

이 부분도 위에 내용을 논문 버전으로 작성하게 되면 이런 느낌이다.

■ Remarks on Security Model

스크린샷 2022-09-30 오전 11 11 51

Security model은 여러 define을 가질 수 있습니다.

  • Standard security model

    대부분 이 버전으로 한다. (꽤 쎄~~)

  • Strong security model

    attacker가 더 많은 정보를 얻을 수 있다.

  • Weak security model

    attacker가 더 적은 정보를 얻는다. 그렇게 때문에 더 강한 security goal를 갖는다.

이런식으로 특정 응용에 맞게 security model을 만들어야 한다.

댓글남기기

참고