출처 : 후니의 쉽게 쓴 네트워크 + 정보통신기술용어해설 

라우팅과 라우티드 프로토콜

라우티드 프로토콜(Routed Protocol)

• 정보통신기술용어해설 정의 : 라우팅 프로토콜이 라우팅하는 프로토콜
• 다른 네트워크로 가기 위해 사용되는 프로토콜
• 말 그대로, 라우팅을 당하는, 즉 라우터가 라우팅을 해주는 고객을 뜻한다.
• 즉, 라우터는 자동차를 타고 여행을 떠나는 승객이라고 생각하면 된다.
• 라우티드 프로토콜은 고객으로서 라우터라는 자동차를 타고 다른 네트워크로 여행을 떠나는 것이다.
• 종류
  • TCP/IP
  • IPX
  • Appletalk

라우팅 프로토콜(Routing Protocol)

• 정보통신기술용어해설 정의 : 라우터간에 라우팅 정보의 교환 및 라우팅 테이블의 유지관리를 동적으로 수행하는 프로토콜
• 후니 책에 나와 있는 것처럼 쉽게 얘기하면, 라우터라는 자동차를 안전하고 빠르게 운전하는 운전 기사라고 볼 수 있다. 즉, 라우터에 살면서 라우티드 프로토콜에게 목적지까지 가장 좋은 길을 갈 수 있게 해주는 역할이다.
• 라우팅 알고리즘 이라고도 한다. 라우팅 알고리즘은 자신의 라우팅 테이블을 가지고 있으면서 자기가 찾아갈 경로에 대한 정보를 이곳에 기억한다.

• 종류

  • RIP(Routing Information Protocol)
  • IGRP(Interior Gateway Routing Protocol)
  • OSPF(Open Shotest Path First)
  • EIGRP(Enhanced Interior Gateway Routing Protocol)

• 필수 기능 및 요소

  • 라우팅 수행 프로세스
    • 라우팅 정보를 주고받기 위한 프로세스
    • 최적 경로 계산 및 이를 라우팅 테이블에 기록하는 프로세스
    • 토폴로지 변화를 감지하고 이를 자동으로 학습 반영하는 프로세스
  • 라우팅 테이블의 갱신 관리
    • 최적 경로 결정을 위한 알고리즘 및 프로세스를 적용
  • 라우팅 알고리즘
    • 최적 경로 산출을 하여가며 라우팅 테이블의 갱신, 유지관리
  • 라우팅 프로토콜 메세지
    • 라우팅 정보를 라우터들 간에 운반, 전달, 교환 등

서비스 거부 공격 관련 용어 정리

DoS(Denial of Service; 서비스 거부 공격)

개요

• 서비스 거부 공격은 공격 대상 시스템(Target)이 정상적인 서비스를 할 수 없도록 만드는 공격을 말한다. 따라서 서비스 거부 공격은 가용성(Availability)을 떨어트리는 것이 공격의 목적이다.
• 서비스 거부 공격은 두가지로 구분할 수 있다.
  • 서버 시스템 자원 소진 공격 : CPU, 메모리, 디스크 등의 자원에 과도한 부하를 발생 시키는 유형
  • 네트워크 대역폭 소진 공격 : 과도한 트래픽으로 네트워크 대역폴을 소진시키는 유형
• DoS 공격은 공격자가 단일 컴퓨터를 통해 공격을 하는 경우를 말한다. (DDoS와의 차이점)
• 용어의 모호성 : 서버는 서비스를 거부하지 않는다. 공격자의 방해로 인해 서비스를 제공할 수 없을 뿐이다. 따라서 서비스 거부 공격이라는 영어 그대로의 직역보다 서비스 방해 공격이 더 나은 표현일 수 있다.

공격의 유형

• Ping Of Death Attack : 아주 작은 ICMP 패킷으로 다수의 IP 단편화를 발생하게 하여 수신측에서 재조합 하는 과정에서 과부하 발생
• Land Attack : src ip와 dest ip가 같은 패킷을 만들어 공격
• Teardrop Attack : IP패킷의 재조합 과정에서 잘못된 fragment offset 정보로 인해 수신측이 문제를 발생하도록 만다는 공격

DDos(Distributed DoS; 분산 서비스 거부 공격)

개요

• 분산 서비스 거부 공격은 분산된 다수의 좀비 PC에 의해 공격대상 시스템의 서비스를 마비시키는 공격 형태를 의미한다.
• 공격의 구조를 살펴보면 다음과 같이 크게 4가지 구성요소로 이루어져 있다.
  • 공격자 : C&C 서버에 공격 명령을 전달하는 해커의 컴퓨터라고 한다.
  • 명령제어(C&C, Command & Control) 서버 : 공격자로부터 직접 공격 명령을 전달받는 시스템을 말하며 전달받은 명령은 관리ㅏ는 다수의 좀비 PC에게 전달한다.
  • 공격대상 : 공격의 대상이 되는 피해 시스템

공격의 절차

• 공격자는 좀비 PC를 관리하고 명령을 내리는 C&C 서버를 구축한다.
• Sphere Phising이나 악의적인 웹 사이트 등을 통해 불특정 다수의 PC에 악성코드를 배포해 감염을 시도한다.
• 사용자가 악성 코드를 다운로드해 실행하면 좀비 PC가 된다.
• 공격자가 C&C 서버에 명령을 내리면 C&C 서버는 좀비 PC에 명령을 전달한다.
• 좀비 PC는 명령에 따라 다양한 공격을 수행하며 스스로 다른 PC로 악성코드 전파를 시도하기도 한다.

공격의 대표적 유형

• 대역폭 소진 공격
  • UDP/ICMP Flooding, SYN Flooding 등
• 시스템 자원 소진 공격
  • HTTP GET Flooding 등
• 외에 더 많은 공격 유형은 따로 공부할 것!! 

IoT를 이용한 DDoS

• 작은 단말에도 인터넷이 들어가는 IoT 장비가 많아져서 이를 이용한 공격이 증가하고 있다.
• 주로 CCTV(카메라+dvr/mvr)나 IP공유기가 해당된다.
• IoT 단말들은 주로 임베디드 리눅스가 설치되어 있으며, 백신이 없는 리눅스 환경은 악성코드에 취약해서 좀비 단말이 될 확률이 높다.
• 또한 이러한 단말들은 현재 있는 IP 대역을 스캔한 뒤 악성코드를 배포하여 더 많은 좀비 IoT 단말을 만들 수 있다.

싱크홀(Sink Hole) 서비스

• 악성 코드에 감염된 좀비 PC가 해커의 명령을 받기 위해 C&C 서버로 연결을 시도할 때 C&C 서버 대신 싱크홀 서버로 우회시켜 더 이상 해커로부터 조종 명령을 받지 않도록 해주는 시스템/서비스를 말한다.
• KISA에서 국내 주요 ISP업체(KT) 등과 협력을 통해 운영중이다.
• 싱크홀 동작 과정
  • 사전 단계로 KISA에서 배포한 C&C 목록을 ISP 등 DNS 싱크홀 적용기관의 DNS 서버에 주기적으로 업데이트한다.
  • 좀비 PC가 싱크홀이 적용된 DNS에 C&C 서버에 대한 질의를 보낸다.
  • DNS는 좀비 PC에 싱크홀 서버 IP주소를 반환한다.
  • 이를 통해 악성 봇 PC는 C&C 서버가 아닌 싱크홀 서버로 접속하여 공격자의 명령으로부터의 피해를 방지할 수 있다.

DrDos(Distributed reflection DoS)

개요

• 공격자는 src IP를 희생자의 IP로 위조(IP spoofing)하여 다수의 반사 서버로 요청정보를 전송하고, 희생자는 반사 서버로 부터 다수의 응답(대량의 트래픽)을 받아 서비스 거부 상태가 되는 공격 유형을 말한다.
• 크게 반사와 증폭으로 이루어져 있다.

DrDoS 공격의 형태

• 주로 UDP를 사용한다. 주로 DNS(53), NTP(123), SNMP, CHARGEN 등의 서비스를 이용한다.
• TCP도 가능하다. 3 way handshake를 이용하여 위조된 ip의 syn 요청을 반사서버로 전달하여 syn+ack 응답이 희생자로 향하도록 한다.
• 외에도 (Smurf Attack) ICMP 프로토콜의 echo request와 echo response를 이용하여, 위조된 주소의 echo request를 반사서버로 전달하여 echo response가 희생자로 향하도록 하는 공격이 있다.

일반 DoS 공격과의 차이점

• 공격 근원지를 파악하기 어렵다! src IP를 변조하고 공격 트래픽이 수많은 반사 서버를 경유하므로 공격의 근원지를 파악하는 것이 매우 어렵다.
• 좀비 PC의 공격 트래픽 효율이 증가한다. DrDoS에 사용되는 반사 서버는 syn+ack 패킷에 대한 응답이 없을 경우 일정 횟수 재전송을 수행하기 때문에 공격자가 전송하는 syn 패킷보다 몇 배 많은 syn+ack 패킷이 공격대상서버에 전송된다. (비용 절감 측면)

대응방법

• DrDoS 공격은 src IP를 위조하는 공격이므로 IP 주소가 위조된 패킷이 인터넷 망에 유입되지 않도록 ISP 단에서 직접 차단할 수 있다. (Ingress Filtering)
• 반사 서버에서는 ICMP 등 필요없는 프로토콜을 사전에 차단한다.
• DNS 서버
  • 내부 사용자 주소만 Recursive query 제한
  • 특정 바이트 이상의 query 차단, 동일 ip에 대해 초당 요청 개수 제한
• NTP 서버
  • monlist 명령 비활성화 (/etc/ntp.conf -> disable monlist)
  • monlist : 최근에 NTP에 접속한 클라이언트 정보를 전송해주는 명령

인터넷 일반 기술에 관한 문서부터 개인정보 관련 문서까지 넓은 범위의 기술안내 가이드를 배포중이다.

공개 sw를 활용한 소프트웨어 개발 보안 가이드나 소프트웨어 보안 약점 진단 가이드 등 보안에 관련된 가이드도 많이 있다.

http://www.kisa.or.kr/public/laws/laws3.jsp

“해커는 컴퓨터 팬이 회전할 때 발생하는 작음을 통해 데이터를 절취할 수 있다. 회전속도의 차이로 잡음이 발생하며 관련 잡음을 녹음장비에 녹취 후 데이터 절취가 가능하다. 이 과정은 네트워크 연결이 차단된 상황에서도 실현이 가능하다.”

자세한 내용은 아래 기사 참고.

http://dailysecu.com/news_view.php?article_id=14901

CCTV가 DDoS 공격에 활용되고 있다고 한다.

일반적으로 좀비 네트워크가 오프라인 상황일 때 공격이 약화되는 현상이 발생하게 되는데,

이번 공격에 이용된 좀비 PC는 항상 온라인 상태로 유지되었다고 한다.

CCTV는 항상 켜져있으므로....

자세한 내용은 아래 기사를 참조하기 바람.

http://www.dailysecu.com/news_view.php?article_id=14918

샤오미 폰의 커스텀 빌드 안드로이드에 있는 앱에서 중간자(main in the middel) 공격을 통해 패키지 내에 원격 코드 실행 취약점을 지닌 많은 앱들을 발견했다고 한다.

자세한 내용은 아래 기사 참조

http://dailysecu.com/news_view.php?article_id=14934

헷갈릴 여지가 많은 게이트 웨이와 라우터의 차이점에 대하여 알아보자.

위키에서 정의를 보면 다음과 같다.

##게이트웨이

(위키링크 : https://ko.wikipedia.org/wiki/%EA%B2%8C%EC%9D%B4%ED%8A%B8%EC%9B%A8%EC%9D%B4)

* 게이트웨이(gateway, 문화어: 망관문)는 컴퓨터 네트워크에서 서로 다른 통신망, 프로토콜을 사용하는 네트워크 간의 통신을 가능하게 하는 컴퓨터나 소프트웨어를 두루 일컫는 용어, 즉 다른 네트워크로 들어가는 입구 역할을 하는 네트워크 포인트이다. 넓은 의미로는 종류가 다른 네트워크 간의 통로의 역할을 하는 장치이다.

##라우터

(위키링크 : https://ko.wikipedia.org/wiki/%EB%9D%BC%EC%9A%B0%ED%84%B0 )

* 라우터(router, 문화어: 경로기)혹은 공유기는 패킷의 위치를 추출하여 그 위치에 대한 최상의 경로를 지정하며 이 경로를 따라 데이터 패킷을 다음 장치로 전향시키는 장치이다.

정의만 놓고 보면 완전 다른 개념이지만, 추상적으로 공부를 하다보면 헷갈린다.

둘다 외부의 네트워크와 이어주는 개념으로 이해할 수 있기 때문이다.

하지만 게이트웨이는 개념적인 용어이고 라우터는 장비이기 때문에 약간은 분류가 다르다고도 할 수 있다.

즉, 네트워크 구성환경에 따라서 라우터가 게이트웨이로 쓰일 수도 있는 것이고, 게이트웨이는 다른 장비나 소프웨어가 될 수도 있는 것이다.

## File Upload 취약점

* 일반적으로 업로드가 허용되는 이미지 파일등 외에 허용되지 않은 (웹쉘같은) 악의적인 파일을 올려서 서버를 장악할 수 있는 취약점이다.

jsp, php, asp 등의 파일을 업로드하여 악성행위를 하게 된다.

## File Upload 취약점 원인

* 해당 페이지에서 허용하는 파일만 업로드 할 수 있게 해놓아야 하는데, 업로드 파일에 대한 검증 부분이 취약하여 해커가 악성코드를 서버에 심을 수 있게 된다.

## Upload File 확장자 필터링 방식

* 클라이언트가 업로드하는 파일의 확장자를 검사하여 파일을 필터링 하게 된다. 

#### 확장자 필터링 우회 방식 예시

* 확장자의 대소문자를 바꿔가며 시도해 본다.   ex) a.php -> a.pHp

* 확장자만 바꿔서 올린다 ex) a.php -> a.jpg

* a.php -> a.php.kr

* a.php -> a.php.

* a.php -> a.php;.jpg    (세미콜론 사용)

* a.php -> a.php%00.jpg (NULL Byte 사용)

#### 파일 업로드 후 파일의 절대경로가 바로 나오는 경우도 있으나 그렇지 않을 경우 디렉토리 구조를 파악한 후 업로드 된 파일의 절대경로를 찾아야 한다.

## File Upload 취약점 대응 방식

#### 서버에서 대응 방식

* 파일이 업로드 되는 디렉토리의 실행 권한을 제거 한다.

* 업로드 된 파일의 이름을 무작위로 변경한다.

* 너무 작거나 큰 파일을 처리하는 로직을 포함해야 한다.

* 임시 디렉토리에서 업로드된 파일을 지우거나 다른곳으로 이동시킨다.

* 폼에서 어떠한 파일도 선택되지 않았다면 파일 업로드에 사용되는 변수를 초기화 시킨다.

* Content-Type 이나 File Signature를 확인하여 허용하는 파일 형식만 업로드할 수 있게끔 한다.

#### 확장자 필터링 우회 대응 방식 예시

* Server Side에서 구현한다.

* 확장자 부분의 문자를 모두 upper case로 바꾼 뒤 검사한다.

#### 아파치 서버 설정 변경

* http.conf에서 해당 디렉토리

<Directory "/usr/local/apache">

AllowOverride FileInfo

....

</Directory>

* 파일 업로드 디렉토리에 .htaccess 파일 생성한 후 Server Side 에서 Script가 실행되지 않도록 설정

<.htaccess>

<FileMatch "\.(ph|inc|lib)">

order allow,deny

deny from all

</FileMatch>

AddType text/html .html .htm .php .php3 .php4 .phtml .phps .in .cgi .pl .shtml .jsp

#### IIS 설정 

* 시작 -> 제어판 -. 관리도구 -> 인터넷 서비스 관리자

* 해당 업로드 폴더를 선택하여 실행 권한을 "없음"으로 설정한다.

## 실습

2016 암호여름학교 NIMS 
한참 재밌게 듣다가 갑자기 놓침....

Provable Security of Public-Key Cryptography

Aaram Yun, School of ECE, UNIST

Summary

• '증명가능한 안전성', 즉 provable security는 80년대 중반에 Goldwasser와 Micali가 계산복잡도 이론에 근거해서 암호화 방식의 안전성을 엄밀하게 정의하고 이를 환원 증명을 통해 증명한 이후로 암호학적 설계에서 중요한 패러다임으로 자리 잡았고, 오늘날은 사실상 공개키 암호학의 거의 전 분야에서 요구되고 있다. 본 강의에서는 구체적인 예를 통해 증명가능한 안전성에 관해 설명하고자 한다. 특히, IND-CCA 안전성을 만족하는 최초의 효율적인 암호화 방식인 Cramer-Shoup의 안전성 증명을 자세히 살펴보도록 한다.

Provable Security?

A bit of History...

• 1976 : Diffie & Hellman, "New direction in cryptography"
• 1982 : Goldwasser & Micali, "Probabilistic encryption and how to play mental poker, keeping secret all partial information", STOC 1982
  • Turing award for 2012

Provable security

Goldwasser & Micali

Why proof?

• Else, how can we be sure nobody learned anyting from what they have eavesdropped?
• or, how do you know that nothing happened?

Unconditionally?

• Bad new: currently, we don't know how to design a cryptosystem with proven security
• Because, if P=NP, then you can break

P and NP

Class P

• A problem is in class P: if it can be solved efficiently(in polynomial time)
• EX : Eulerian path problem
• "Given a graph G, is there an Eulerian path in this graph?"
• Eulerian path itself is the witness

Class NP

• A problem is in class NP : if given an answer, checking it can be done efficiently
• EX : Hamiltonian path problem
• "Given a graph G, is there a Hamiltonian path in this graph?"
• Hamiltonian path itself is the witness
• 정답을 확인하는 것은 쉽지만 정답을 찾는 건 어렵다.
• Another Example : "Given a bitstring c and a public key pk, is this c an encryption of some message with respect to the public key pk?"
• That is, do we have c = Encpk(m) for some message m?
• what can be the witness?

P vs NP Problem

• We have P =< NP. Do we have NP = P? or is there some problem in NP which is outside of P?
• Most people believe P != NP, but very hard to prove
• If NP = P, you can solve any NP problems efficiently
• You can answer questions like "Do we have c Encpk(m) for some messages m?"
• Big Deal?

Unconditional security

• So, P = NP --> such cryptosystem will not be secure
• Then, provably secure cryptosystem -> prrof of P = NP
• This is far beyond cryptography

Reduction

Use reduction between problems

• Given algorithm A for solving problem a, design algorithm B for solving b, which uses A as a subroutine
• Later, solving a -> solving b
• On the other hand, infeasible to solve b -> infeasible to solve a

Reductions everywhere

Reduction became the core methodology in complexity theory

• In a sense, bypassing P vs NP problem
• classifying between problems

Reduction and P.S.

• X : difficult mathematical problem
• E : cryptosystem
• R : polytime reduction for solving X, using an
• E can be attacked efficiently -> X can be solved efficiently
• Contrapositive : X cannot be solved efficiently -> E cannot be attacked efficienty
• The trust in the hardness of X is transferred into the trust in the security of E

More History

• Middle 80s - Early 90s : ad-hoc crypto & provable security went in parallel
• Random Oracle Model : to design practical & somewhat provable schemes
• Bellare & Rogaway : "Random Oracles are Practicals", 1993
• 2000 - : trying to do things in the Standard model

Case study : Cramer-Shoup encryption

Notion of PKE

Provable security of PKE

• 3-step recipe for provable security
• Step 1 : you need to define what you are making
  • Step 1-1 : you need to describe its syntax, or, correctness
  • Step 1-2 : you need to describe its security properties
• Step 2 : describe a concrete scheme realizing above notion
• Step 3 : give a reduction proof

Public-key encryption

Consists of 3 Polynomial algorithms( Gen, Enc, Dec)

• (pk, sk) <- Gen(1^lambda) : given security para lambda, Gen outputs public key & security key pair (pk, sk)
• c <- Encpk(m) : given a public key pk and a plaintext m, Enc outputs corresopnding ciphertext c
• Decsk(c) outputs a message, or it may fail to decrypt

Syntax of PKE

• The algorithm should satisfy the following:
• for any lambda, if key pair (pk, sk) is generated by (pk, sk) <- Gen(1^lambda), then for any plaintext

IND-CCA encryption

• Cramer-Shoup "First practical IND-CCA public key encryption scheme in the standard model"

Semantic Security

Intuitive security we want for an encryption

• "Even if you happen to know c, it won't help you at all in learning anything more about the plaintext m"
• c doesn't leak even one bit of information about m
• This is called semantic security
• Satisfying definition, but hard to use

Indistinguishability

• I'll give you a ciphertext c. This is either encryption of m0, or m1. Guess which is the case
• By default, you can win this game with probability 1/2$12$

Similar to semantic security, or, a special case of semantic security

• You already know that the plaintext is m0, or, m1

Semantic security VS IND

• Clearly, if your encryption scheme satisfies semantic security, then it also satifies IND
• Importantly, the other direction is also true
• 그래서 보편적으로 IND를 암호화 다룰 때 더 많이 씀

IND game

• A : polytime adverary
• IND GAME
• (pk, sk) <- Gen(1^lambda)
• (m0', m1', state) <- A('find', pk)
• b <- {0, 1}; c' <- Encpk(mb')
• b' <- A('guess', c', state) (not allowed to query c')
• A wins IND game if b = b'

Chosen ciphertext attack

Chosen plaintext attack

• The attacker's ability to create a ciphertext for any plaintext chosen by the attacker
• Obvious in PKE

Chosen ciphertext attack

• The attacker's ability to obtain decryption of any ciphertext chosen by the attacker
• IND-CCA : even against such powerful attacker, any ciphertext which is untouched by the attacker is still IND-secure

IND-CCA Justification?

Security assumption

Diffie-Hellman

• G : a group of prime order p
• g (- G : uniform random
• Assume discrete logarithm is hard on G : given g^a
• If you know g, g^a, and b (- Zp, then easy to compute gab=(ga)b$g^{ab}{g}^a{}^b$

Decisioin Diffie-Hellman

DDH Problem

DDH assumption : alternatively

DDH game

• b <- {0, 1}
• If b = 0, sample (g1, g2, u1, u2) <- D
• Else, sample (g1, g2, u1, u2) <- R
• b' <- A(g1, g2, u1, u2)
• b = b'

Collision-resistant hashing

• one more ingredient : hash function
• A hash function H maps elements in a large domain to a small, fixed size codomain
• Naturally, there should be lots of collisions : a pair (x, y) where H(x) = H(y) but x!=y$xy$
• H is collision-resistent, if it is computationally hard to actually find a collision
• 계산 자원에 제약이 주어지는 상황에서는 찾아내는 것이 불가능

Key generation

• Choose G with prime order p according to security parameter
• Choose g1,g2<−G$g_1{g}_{2}G$ : uniform random
• Choose x1,x2,y1,y2,z<−Zp$x1x_2{y}_1{y}_{2}z{Z}_p$: uniform random
• c=g1x1g2x2,d=g1y1g2y2,h=g1z$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}h{g_1}^z$

Encryption & Decryption

• (사정상 생략)

IND-CPA security of Cramer-Shoup

IND-CAP security

• Cramer-Shoup is IND-CPA, if DDH assumption holds

IND-CPA reduction proof

Basic idea

• B is DDH solver, so it receives a tuple t=(g1,g2,u1,u2)$t{g}_1{g}_2{u}_1{u}_2$
• B wants to find out if this tuple is a DDH tuple(from D), or a random tuple (from R)
• B simulates the IND-CPA game environment of A

How to determine t using A?

• B's simulation should at
• B will use this tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^z$
• If t is from D, then c∗$c^{}$ is the same as correctly created
• On the other hand, if t is from R, then c∗$c^{}$ is a fake encryption for mb∗${m_b}^{}$
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• claim : from A' is point of view, u1z${u_1}^z$ is uniform random
• If so, u1zmb${u_1}^z{m}_b$ is also uniform random : it can be anything in G equally likely : no matter what b is
• In that case, A can win the fake IND-CPA game with prob. 1/2
• c∗=(u1=g1r,u2=g2r′,v=u1x1+y1au2x1+y1a)$c^{}{u}_1{g_1}^r{u}_2{g_2}^{r^{}}v{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• (이하 생략. PPT 참조 바람.)

Bypassing the problem

• B will simulate IND-CPA game, but generating a fake pk
• Choose x1,x2,y1,y2,z1,z2<−Zp$x_1{x}_2{y}_1{y}_2{z}_1{z}_2{Z}_p$ : uniform random

• compute c=g1x1g2x2,d=g1y1g2y2$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}$

• Claim : this modification is completely invisible to A

Reassessing the situation

• B will use tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1z1u2z2mb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z1u2z2)$c^{}{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}$

Uniform randomness

Going to IND-CCA