[제로의 암호이야기06] 해시 공격 - 비둘기는 약하고, 생일빵은 강하게..-_-;;!

[그래할수있을거야]

안녕하세요. 제로입니다.

본격적으로 시작하기 전에 유머(?) 하나...ㅎㅎ

옛날에 책에서 본 얘기입니다만...

재치있는 아인슈타인 운전기사 얘기입니다.

========================================================================================

아인슈타인이 여기저기 초청강의를 많이 다닐때 얘기입니다.

서당개 삼년이면 풍월을 읊고, 식당개 3년이면 라면을 끓이고...

당구장개 3년이면 맛세이를 찍는다는 말이 있듯이..-_-;;

어느날 이런 얘기를 합니다.

기사:  제가 선생님을 모시고 돌아댕기면서 강의를 하두 많이 들어서 제가 강의 내용을 다 외웠슴다.

아인: 구래서 ?

기사: 다음번 강의는 제가 해도 되겠습니까/

아인: 오홋.. 구래? 구럼 한번 해보셔~!

기사: 넹.. 감솨~!

이렇게 하고.. 서로 옷을 바꿔입고.. 기사가 강의를 성공적으로 마쳤습니다.

그런데 성공적으로 강의를 마치고 내려올라고 하는데 누군가 질문을 합니다.

누군가: 선생님~! 어쩌구 저쩌구 거시기에 대해서 잘 이해가 안됩니다. 설명좀 부탁해도 될까요?

(당황하지 않고 재치있는 기사는 이렇게 답변을 했습니다.)

기사: 당신의 질문 수준이 너무 낮군요... 그 정도 문제는 제차에 있는 운전기사도 답변해줄수 있습니다. ㅎㅎㅎ

========================================================================================

오늘은 해시 알고리즘을 공격하는 두가지 방법에 대해 살펴보겠습니다.

해시를 깨기위한 공격은 크게 2가지로 나눌수 있습니다.

바로 약한 충돌내성을 깨기위한 공격과 강한충돌내성을 깨기위한 공격입니다.

"이게 먼소리여?" 하시는 분들이 있겠죠...ㅎㅎ

해시값이 같게 나오는 것을 충돌이라고 지난번에 말씀드렸죠..^^;

첫째, 약한 충돌내성

말 그대로 충돌이 일어날 확률이 약한것입니다. 즉, 충돌이 일어날 확률이 거의 없다는 것이죠...

예를 들어서 어떤 평문의 해시값이 "1818181811818181811818188.." 이라고 합시다.

위와 같은 해시값을 가진 평문을 구할라면 어떻게 해야 될까요?

가장 무식한 방법인 전수 공격입니다.

경우의 수가 100개 라면 100번 시도하면 되고... 100만개라면 100만번 시도하면 되겠죠..

해시값이 3자리라면... 2의 3승 = 8번을 시도하면 되겠죠..

만약 128bit라면.. 2의 128승 <--- 요건 도대체 값이 얼만지 모르겠네요..ㅎㅎ

이만큼 시도하는 것은 거의 미친짓이라고 하죠...^^;

따라서 약한 충돌내성을 이용하는 공격은 실제로 바보가 아니면 이런 공격을 하지않습니다.

약한 충돌내성 공격에 대하여 나오는 얘기중에 비둘기집원리라는 것이 있습니다.

머.. 알고보면 개뿔도 아닌뎅...

처음 공부할때는 약하니까.. 비둘기가 어쩌구 하니.. 이렇게 걍 외웠는뎅... 참 답답하더군요..ㅎㅎ

[비둘기 집원리]

비둘기집이 10개고 비둘기가 11마리라면...

최소한 비둘기집 하나에 두마리가 들어간 비둘기집이 있다는 얘기입니다.

패스워드가 2비트라면 경우의수는 4이고..

4번 이상을 집어넣으면 패스워드를 뚫을수 있다는 남들 다아는 얘기입니다.

즉, 암호를 뚫을때 모든 경우의 수를 전부다 집어넣는 가장 무식한 전수공격과 비슷한 이야기...

둘째, 강한 충돌내성

약한 충돌 내성은 해시값을 정해놓고... 그 해시값과 똑같은 평문을 찾는 방법을 말합니다.

즉, 모든 경우의 수를 이용하는 가장 무식한 전수공격이라고 할수 있습니다.

그러나 강한 충돌내성이라는 말에서 보듯이...

충돌이 일어날 확률이 강하다는 것입니다.

즉, 해시값이 같은 두개의 평문을 찾는 공격을 뜻합니다.

이것에 대해 주사위 확률이라는 것이 있습니다.

(이것은 이해를 쉽게하기 위해서 그냥 제가 생각나는 대로 쓴것이라서 맞지않을 있습니다. -_-;;)

[주사위 확률]

 - 주사위를 n번 던질때 모두 서로 다른 수가 나올확률을 구해보겠습니다.

"확률 = 나오는 경우의 수 / 모든 경우의 수" 공식이 있죠..

(1) 1번 던질때 모두 다른 수가 나올 확률

     6/6 이죠... 당근히 100%죠..ㅎㅎ

(2) 2번 던질때 모두 다른 수가 나올 확률 

   6/6 * 5/6 = (6*5)/(6*6) = 5/6

(3) 3번 던질때 모두 다른 수가 나올 확률 

 6/6 * 5/6 * 4/6 = (6*5*4)/(6*6*6) = 20/36

....

....

(4) n번 던질때 모두 다른 수가 나올 확률 = (6Pn)/6^n  

자.. 그럼 n번중에서 한번이라도 같은 숫자가 나올 확률은 아래와 같습니다.

  = 1 - (n번 모두 다른 숫자가 나올 확률)

 = 1- 6Pn/6^n 

[생일빵(birthday attack) 공격]

n명의 사람들이 모여있습니다. 이때 생일이 같은 사람이 있을 확률이 50%이상이 되려면

최소한 몇명이 필요할까요?

여기서 말을 잘 이해해야 됩니다. 생일이 특정일로 정해졌다면... 365/2 명이 필요하겠죠...

그런데 생일이 특정일로 정해지지 않았죠...^^;

위의 주사위와 비슷한 개념입니다.

즉, 1에서 n명이 모두 다른 숫자가 나올 확류을 빼면 됩니다.

따라서 이번에는 6대신 365로 교체하고...

n번중에서 한번이라도 같은 숫자가 나올 확률

  = 1 - (n번 모두 다른 숫자가 나올 확률)

  = 1- 365Pn / 365^n

따라서 n = 23일때

 = 1 - 365P23 /365^23 = 1 - 0.4927...

즉, n=23일때 약 50%가 됩니다.

즉, 생일이 정해졌다면.. 365/2 = 183명이 필요합니다.

그렇치만 생일이 정해지지 않았다면 23명이면 되죠..

생일빵 공격을 어떨때 써먹을수 있을까요?

예를들어서 제로뱅크가 돈없어회사에 돈 1억을 빌려주고 차용증을 써줄 계획이라고 합시다.

물론, 여기서 차용증은 디지털문서입니다. (종이로 쓰는거 말고..^^)

해시값은 글자의 1bit가 바뀌더라도 바뀌죠..

따라서 아래처럼 여러개의 문서를 만듭니다.

돈1억을 빌려준당

돈1억을 빌려준당께

돈1억을 빌려주겠당.

.....

.....

그리고 이번에는 돈10억으로 바꿔서 만듭니다.

돈10억을 빌려준당

돈10억을 빌려준당께

돈10억을 빌려주겠당.

.....

.....

이렇게 2가지 종류의 것을 많이 만들다보면 해시값이 같은 것이 나올수 있습니다.

경우의 수는 전수공격의 갯수가 아닌... 생일빵 공격의 경우의 수만큼입니다.

해시값이 160비트일 경우

전수공격은 2의 160승을 시도해야 되지만...

생일빵 공격은 약 2의 80승 정도만 시도하면 됩니다.

이렇게 해서 해시값이 같은 넘을 찾은 다음에

처음에는 1억짜리를 주고... 나중에 10억짜리로 바꾸어 놓고..

나중에 10억 내놓으라고 할수 있습니다. 

생일빵은 참 무서운 공격이죠.. ^^

아래는 우리모두의 백과사전 위키입니다.~! ^^;

=====================================================================================

비둘기집 원리

위키백과, 우리 모두의 백과사전.

 

비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 '서랍 원칙' 또는 '디리클레의 방 나누기 원칙'이라고 부르기도 한다.

이 증명은 대표적인 존재 증명이다. 즉, 비둘기가 두 마리 이상 존재하는 집이 정확히 어떤 집인지는 이 증명으로 알아낼 수 없다.

용례[편집]

• 서울에는 머리카락의 수가 같은 사람이 최소한 두 명 존재한다. : 일반적인 사람의 머리카락 수는 15만 개이다. 그러므로 100만 개 이상 머리카락을 가진 사람은 없다고 가정해도 무리가 없다. 서울에는 1000만 명 가량의 사람이 있으므로, 서로 다른 머리카락의 개수를 서로 다른 비둘기집으로 보고, 서울에 사는 사람 각각을 머리카락의 개수에 따라 서로 다른 비둘기집에 할당하면, 같은 머리카락 개수를 가진 사람이 반드시 존재한다는 것을 알 수 있다.
• 소프트볼을 하고 싶어하는 5명의 사람 있다고 할 때, 서로 같은 팀에서 경기를 하고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한 명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.
• 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 알고리즘도 충돌을 피할 수는 없다.
• 모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.
• 어느 그룹에 생일이 같은 사람이 반드시 1쌍 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다. 생일의 경우의 수는 2월29일을 포함하여 366가지 이기 때문이다.
• 앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.

비둘기집 원리의 일반화[편집]

일반화 된 비둘기집 원리는 다음과 같다.

개의 별개의 사물을 개의 용기에 나누어 담으면 적어도 한 개의 용기는 이상의 사물을 담고 있어야 한다.(여기서, 는 올림 함수를 의미한다.)

확률론적으로 일반화 된 비둘기집 원리는 다음과 같다.

의 균일한 확률로 개의 비둘기를 무작위로 개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.

인 경우와, 인 경우(단, )에 확률은 0인데, 달리 말하면 비둘기가 한마리 밖에 없다고 하면, 충돌(한 비둘기집에 두 마리 이상의 비둘기가 들어가는 일)이 일어날 수 없다는 것이다. (비둘기가 비둘기집보다 많다)이라면 확률은 1이 되고 이런 경우에는 보통의 비둘기집 원리와 같은 일이 일어난다. 그러나 비둘기의 수가 비둘기집의 수를 초과하지 않는다 하더라도 (), 비둘기 분배의 무작위적인 성질에 의하여 종종 상당한 확률로 충돌이 일어난다. 예를 들어, 2마리의 비둘기가 무작위로 4개의 비둘기집에 분배된다면, 25%의 확률로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 될 것이며, 5마리의 비둘기를 10개의 비둘기집에 분배한다면 확률은 69.76%가 되고, 10마리의 비둘기를 20개의 비둘기집에 분배하면 그 확률은 약 93.45%가 된다.

<noscript></noscript>

원본 주소 "http://ko.wikipedia.org/w/index.php?title=비둘기집_원리&oldid=11287860"

생일 문제

위키백과, 우리 모두의 백과사전.

이동: 둘러보기, 찾기

모인 사람 수에 따라 생일이 같은 두 사람이 있을 확률이 얼마나 되는지를 보이는 그래프. 가로축이 사람 수,그리고 세로축이 확률을 나타낸다. 23명이 모였을 때 확률이 0.5를 넘어감을 보여 준다.

생일 문제(生日問題)란 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.

생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.

확률 계산[편집]

만약 366명 이상의 사람이 있다면 비둘기집 원리에 따라 생일이 같은 두 사람이 존재해야 한다. 365명 이하의 사람이 있을 경우를 계산한다. 명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 이라고 한다면, 반대로 모든 사람의 생일이 다를 확률 은 이 된다. 먼저 을 구해보면, 두 번째 사람의 생일은 첫 번째 사람과 다르고, 세 번째 사람의 생일은 첫 번째와 두 번째 모두와 달라야 하므로 다음과 같은 식을 얻을 수 있다.

가 되고, 최종적으로 구하고자하는 생일이 같은 사람이 둘 이상 있을 확률 은

가 된다. 여기서, n≤365 인 자연수이고, !는 계승을 의미한다.

이 값을 특정 n 값에 대해 계산하면 다음과 같다.

n	p(n)
10	12%
20	41%
30	70%
50	97%
100	99.99996%

즉, 50명만 모이면 그 가운데 2명 이상의 생일이 같을 확률이 97%이고, 100명이 모이면 거의 1에 가까워진다는 것을 알 수 있다.

 

카페 소개 : 정보보안기사 카페(다음 정보보안기사 대표 카페)

카페 주소 :http://cafe.daum.net/Security-no1클릭

교재 소개 : 알·기·사(알기쉬운 정보보안기사.산업기사(필기편,실기편))