본문 바로가기
조회 수 1431 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print

http://celdee.tistory.com/226


만약, 한 방에서 같은 생일을 가진 사람이 존재할 확률이 50% 이상이 되려면, 몇 명의 사람이 있어야 할까? 그 답은 놀랍게도 23명이면 충분하다. 윤년을 생각하지 않더라도 1년이 365일이므로, 23명이란 표본의 수는 일반적으로 생각되는 것보다 훨씬 적은 수이다. 이것을 생일 파라독스(Birthday Paradox)라고 한다.



먼저, 이 사람들이 모두 다른 생일을 가지고 있을 확률을 알아보면, 첫 번째 사람은 365일 중 어떤 날을 선택할 수 있다. 두 번째 사람은 첫 번째 사람과 다른 날을 선택해야 하며, 이 확률은 (1 - 1 / 365)이다. 세 번째 사람은, 365일에서 선택할 수 있는 날이 2개 줄었으며, 따라서 (1 - 2 / 365)이다. 이와 같이 23명까지 전개해보면,


1 * (1 - 1 / 365) * (1 - 2 / 365) * (1 - 3 / 365) * ... (1 - 22 /365) = 0.493


따라서, 23명이 모두 다른 생일이 가질 확률이 0.493이므로, 최소한 두 명이 같은 생일 가질 확률은 1 - 0.493 = 0.507로 50%를 조금 넘는다.



이것을 일반화하여 생각해보자. 충분히 큰 수의 N개의 물건이 있다고 하고, r명의 사람들이 존재하며, 이 사람들 각각 N개의 물건 중 하나를 선택한다고 하자. 그렇다면, 이 사람들이 중복되는 물건을 선택할 확률은 얼마인가? 대략 다음과 같다.


1 - e^((-r^2) / 2N)


이것은 N이 충분히 큰 수일 경우에 해당되는 근사값이다. 여기서, 이 확률이 1 / 2이 넘기 위해서는 (r^2 / 2N) = ln2가 되어야 하며, 이것을 r에 대해서 정리하면 r = root(2ln2) * root(N)이 된다.



이것을 정리해본다면, N의 가능성이 있을 때, 최소한 root(N) 길이의 리스트를 조사하면 중복을 발견할 확률이 50% 정도 된다는 것이다. 이러한 성질은, 해시 함수를 공격하는데 좋은 근거가 된다. 즉, 64비트 해시값이 있다고 했을 때, 2^32번의 계산을 해보면 중복되는 해시값을 찾을 확률은 50%가 넘는다. 이 비트수가 낮을 수록 계산량은 급감하며, 전수공격은 해볼만한 가치가 생긴다. 중복되는 해시값을 찾았다면, 이것을 어떻게 악용할 수 있는가? 생일공격을 처음으로 제안했던 유발(Gideon Yuval)은 다음과 같이 설명한다.


1. Alice는 계약서를 두 종류로 준비한다. 하나는 Bob에게 보여줄 것이고, 다른 하나는 Bob을 속이기 위한 것이다.


2. Alice는 정당한 계약서를 눈에 띄지 않게 다양하게 변조한다. 변조하는 방법은 여러 가지가 있는데 Space 키 대신 Space - Backspace - Space를 쓰거나, 줄 바꾸기(Return) 키를 치기 전에 한 두개 정도의 Space를 넣는 방법 등이 있다. 만약 문서가 모두 32줄일 때, 각 줄마다 이런 식의 변조 방법을 쓴다면 2^32 종류의 서로 다른 문서들을 만들어 놓을 수 있다.


3. 필요하다면 가능한 변조를 계속해서 2^32 종류의 문서가 서로 다른 해시 함수값을 갖도록 한다.


4. 이번에는 Bob을 속이기 위한 부정한 문서를 역시 다양하게 변조하여 2^32 종류의 서로 다른 해시값들을 가지는 문서들을 만들어 놓는다.


5. 그런 다음 Alice는 정당한 문서들 가운데 절반인 2^32개씩 두 묶음(A, A´)으로 나눈다. 부정한 문서로 같은 방법으로 두 묶음(B, B´)으로 나눈다.


6. 가능한 해시값의 종류가 2^64이므로 대략 2^32개의 문서들의 그룹에서는 1 / 2 확률로 충돌쌍이 존재한다. 즉 (A, B), (A, B´), (A´, B), (A´, B´) 가운데 충돌쌍이 있는 그룹은 거의 항상 존재할 것이다.


7. 충돌쌍을 찾은 Alice는 Bob에게 변조되기는 했지만 겉으로는 정당한 문서에 서명해 달라고 한다.


8. Alice는 Bob이 서명한 문서를 서명하지 않았던 사기 문서로 바꾸어 놓는다. 앞으로 언젠가 Alice는 판사 앞에서, Bob이 전혀 생각하지도 않았던 문서에 서명했음을 입증할 때가 있을 것이다.



Reference

Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education


Title
List of Articles
번호 제목 글쓴이 날짜 조회 수
46 Install crunch on Mac and examples Hojung 2015.02.18 2294
45 Create Kali Live USB Persistence from Mac file Hojung 2015.02.18 2577
44 Firewall Assessment with Prometheus file Hojung 2015.02.04 1809
43 Install WebGoat 5.3 in Kali file Hojung 2015.02.02 3104
42 brute-force HTTP/S basic access authentication with hydra file Hojung 2015.01.07 2682
41 Session Cookie 세부항목에 대해 (secure, Http Only flag) Hojung 2015.01.06 4043
40 쉘코드(shell code)란 payload로 사용되는 작은 코드조각 Hojung 2014.12.23 3720
39 Netcat (nc) guide (port scan, file transfer, backdoor, reverse shell, source port/ip) Hojung 2014.12.16 1989
38 SSH Tunnels (ssh -L localport:host:hostport user@ssh_server -N) Hojung 2014.12.16 1317
37 How to install Damn Vulnerable Linux (DVL) file Hojung 2014.11.26 2723
36 Five Steps of a Hacking Attack Hojung 2014.11.24 1183
35 How to install Snorby in Kali (snort) Hojung 2014.11.19 2475
34 TightVNC on Kali Hojung 2014.11.18 1960
33 10 stage Generic attack process in a nutshell (in chronological order) Hojung 2014.11.07 1377
32 Send HEAD request with netcat (nc - banner grabbing) Hojung 2014.11.05 1516
» Birthday Attack, Birthday Paradox Hojung 2014.11.03 1431
30 Discovering rogue AP with nmap Hojung 2014.11.03 1375
29 DoS (Denial of Service) 공격에 대해 (Ping of Death, Syn Flooding 공격/탐지/대응, Tear Drop, Smurf/Fraggle, LAND Attack) file Hojung 2014.11.02 4454
28 DNS Spoofing from GUI (ip forwarding + arp spoofing + dns spoofing with ettercap) file Hojung 2014.10.06 2411
27 DNS Spoofing from CLI (ip forwarding + arp spoofing + dns spoofing with ettercap) file Hojung 2014.10.06 4053
Board Pagination ‹ Prev 1 2 ... 3 Next ›
/ 3

Designed by sketchbooks.co.kr / sketchbook5 board skin

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5