생일 역설이라고 파티에 n 명의 사람이 모였을 때
서로 생일이 같은 사람이 나올 확률이 50% 이상이 되려면
최소 몇 명의 사람이 모여야 하는가? 인데
n이 23명만 돼도 50% 확률이 넘으니 역설적이라고 하는 건데,
Conficker.C 웜 바이러스라고 이 생일 역설을 재미있게 응용한 사례가 있음.
Conficker 웜 바이러스가 시리즈가 Conficker.A부터 Conficker.E까지 있는데,
공격자가 새로운 버전을 만들었을 때 이걸 단 한 대의 컴퓨터라도 유포시키고 싶단 말이야?
그래서 자동 업데이트(self update) 기능을 넣어야 하는데, 이 자동 업데이트 기능이 매우 독특하면서 재미있음.
날짜에 근거해서 매일 고유한 50,000개의 도메인 주소를 생성해서 그 중 500개를 랜덤하게 뽑아서 거기에 접속한 뒤
접속이 성공하면 최신 버전의 바이러스를 다운 받음. 이제 공격자가 몇 개의 도메인을 미리 등록해 놓느냐가 관건인데,
100개만 등록해도 63.43%의 확률로 1대 이상의 컴퓨터가 업데이트에 성공하고,
500개를 등록할 경우 99.359%의 확률로 성공한다고 함.
반대로 방어하는 입장에서 보면 날짜를 이용해서 매일 고유하게 생성되는 50,000개 도메인 중에서 어떤 것이 바이러스 유포 도메인인지
알기가 매우 까다롭고 알았다고 하더라도 차단하기가 곤란함. 매일 도메인이 달라지니깐. 그리고 50,000개 도메인을 하나라도 막지 못하면
확률이 1%가 되어서 50,000개 도메인을 모두 막아야 함.
사스가... 머리 너무 좋은 거 아니냐 ㅋㅋㅋ
그랬군요
얘는 재미있는걸 정말 많이 알고있네
난 각자가 알아서 행동하는데 전체적으로 어떤 효과가 발생하는 그런게 너무 좋음
이게 그런 현상에 해당되는지는 모르겠지만
생일 역설 자체는 컴퓨터 보안 과목 들으면 해쉬 충돌 공격하는 파트에서 꼭 다루게 되는 부분이지만 해쉬 충돌 이외의 의미있는 활용은 저게 거의 유일할 듯 ㅋㅋㅋ
진짜 윈도우 웜 바이러스 중에서 Conficker 웜 바이러스 엄청 잘 만들었음. MS가 제작자 정보 제보하면 현상금까지 주겠다고 내걸 정도였음.
공격보다 방어가 어려운 케이스라 끌리는 것 같기도 함
ㅇㅇ 나도 저거 봤을 때 불알을 탁 쳤음. 세상에 저런 웜 전파 방법도 가능했구나 라며... ㅋㅋㅋ
구체적인 부분은 아직 이해가 안가서 약간 의문스럽지만 상당히 매력적인 방법을 사용하는듯
꼭 웜 배포가 아니더라도 어딘가에 응용 방안이 있을 것 같은 방법
http://blogs.technet.com/b/mmpc/archive/2009/04/06/birthday-problem-and-conficker.aspx
가 분석 글 원문인데 한번 읽어봐. 진짜 대단함.
500개 등록해놓고 500개 뽑아내면 99% 확률로 히트한다는 말이구나.. 차단 대상이 되는 url을 100배로 부풀리는거네
그중에 단 하나만 성공해도 받아지는 거니까
날짜에 근거해서 생성되는 50,000개 도메인은 컴퓨터마다 같음. 그러나 하루가 지나면 50,000개는 새로운 도메인이 생성됨(랜덤 알고리즘 사용하되 시드 값이 날짜로 고정된 셈). 50,000개 중에서 뽑는 500개는 컴퓨터마다 다름(랜덤 알고리즘 사용). 도메인을 차단하는 입장에서는 50,000개를 다 차단하지 않고 예를 들어 49,999개만 차단할 경우 1% 확률로 적어도 1대 이상의 컴퓨터가 업데이트됨. 그래서 50,000개를 다 차단해야 하고, 또 매일 새로운 50,000개 도메인을 차단해야 됨. 엄청난 거죠.
근데 이걸 거꾸로 분석하는 입장에서도 좋은 의미로 이용할 수 있는데, 분석하는 사람도 도메인 몇 개 미리 등록해서 바이러스 최신 버전을 검사하는 트래픽을 보내는 컴퓨터 IP 개수를 카운트함으로써 전세계적으로 이 웜 바이러스가 몇 대가 감염되었는지 추산해 볼 수 있게 돼죠.
url 5만개가 날짜 시드로 생성되니까 뭔지 예측 가능하고 그 50000개중 500개만 웜 배포 url로 등록해도 모든 컴퓨터가 99%확률로 감염되는데다가 49999개를 차단해도 컴퓨터 1대 기준으로 1% 확률로 감염되는데 감염된 컴퓨터의 수가 많으면 그 감염 확률도 올라가고 이게 매일 반복된다는 의미인듯
맞게 이해한건지 모르겠네
birthday paradox는 익숙하다고 생각했는데 5만개중 500개만 등록해도 1개 이상 히트할 확률이 99%가 넘게 나온다는게 신기하게 느껴짐
ㅇㅇ 공격자 입장에서는 개꿀인데 방어하는 입장에서는 50,000개를 다 막을 수도 없는 노릇이고 또 어느 날에 어느 도메인을 공격자가 등록할지 전혀 예측이 불가능해서. 진짜 대박임. 난 이거 보고 지렸는데 넌 안 지림? ㅋㅋㅋ
내 컴퓨터가 hit할 확률이 아니라 전체 중에 한 컴퓨터 이상이 히트할 확률임.
수학적으론 당연한 건데 역시 "생일 역설"이라는 이름대로 쉽사리 이해는 안 가지.
500 ... 50000이 히트할 확률이 99%인건 컴퓨터 1대 기준이고 49999개 차단했을때 히트할 확률이 1%인것도 컴퓨터 1대 기준이지 않음?
간단하게 생각해도 접속 시도를 하는 컴퓨터가 수십만대라면 그중 한 컴퓨터가 히트할 확률은 99%에 가까워질 거 같은데.. 서버쪽 관점에서 얘기하는 건가
발상은 정말 쩌는듯
에이. 500개만 등록했을 때 감염된 컴퓨터 자기 자신이 감염될 확률은 500/50000 = 1%지. ㅋㅋ 생일 역설, 그리고 Conficker.C 바이러스에서 나오는 확률은 전체를 놓고 볼 때의 확률이야.
야 잠깐만. 99%가 맞다. 50000개 중에 500개를 뽑으니깐... 와 시발 소름돋네.
나도 제대로 이해 못하고 있었다 ㅡㅡ;
아 아니구나. 후자는 내가 잘못 이해한듯
그럼 공격자가 500개만 등록해도 전체 감염 컴퓨터의 99% 이상이 최신으로 업데이트된다는 말이네? 개발자 진짜 천재인듯.
전자는 내가 생각한게 맞는듯. 본문에 그렇게 쓰여있으니깐
ㅇㅇ 전체 감염 컴퓨터의 99%가 전부 업데이트 될듯
생일 역설에 따라서 50,000개 중에 하나만 못 막아도 1%의 컴퓨터가 업데이트되니... ㅎㄷㄷ. 즉, 생일 역설은 50,000개에서 500개를 뽑는 과정에서 일어나는 거라 봐야겠네. 근데 쉽사리 이해가 잘 안되지? 나도 그런데 ㅋㅋㅋ
음.. 50000개중 500개 뽑는 경우의 수라는거 자체가 머리속에 아예 그려지지가 않음. 이 경우의 수의 99%에는 무조건 원소 500개짜리 특정 집합의 원소가 적어도 하나씩 포함되어 있다는 말인데..
문제 사이즈를 줄여서 테스트 해봐야겠음. 지금은 생각을 하기가 힘들어서 ㅠ
ㅋㅋㅋ 아무튼 역시 디씨에 올리길 잘했네. 나도 오해하고 있었음. 생일 역설 자체는 "내가 생일이 같을 확률"이 아닌게 분명하지만 Conficker.C에서 확률 이야기하는 건 1대 PC 내에서 이야기하는 거였어 ㄷㄷ 진짜 지리는 듯.
이 시스템은 분명히 어딘가에 응용 방안이 있을듯
그러게. 예를 들어서 네트워크 같은 데서 서버 검색할 때도 유용할 듯. A.B.C.D 이렇게 IP가 있을 때 A 값은 특정 값, D 값은 예를 들어 D=20로 고정시켜 놓고 B,C를 random하게 256개를 뽑아서 A.B.C.20로 connect하는 거지. 그러면 server를 만드는 입장에서는 A.B.0~255.20 만이라도 서버를 만들 수 있으면 99%의 확률로 서치가 가능.
궁극적으로는 Serverless Service 구현하는 데 부분적으로 쓰일 수 있을 거 같아. 진짜 쩌는 듯.
나도 그 생각 하고 있었는데. 500개씩이나 다 테스트 해봐야 되는게 퍼포먼스가 문제가 될수 있긴 한데.. 이미 이런 발상을 어디선가 쓰고 있을꺼 같은 느낌
아니면 키 분배같은거 할때도 모래속에 바늘 숨기기 같은 작전으로 쓸수 있지 않을려나..? 이건 잘 모르겠음
영지식 증명으로도 써먹을 수 있을 듯. 예를 들어 DB 서버에 패스워드 정보는 해쉬 알고리즘을 MD5로 쓴다고 가정했을 때 MD5(hash + password)로 돌리는데 이 때 salt 값은 50000개의 salt table에서 500개를 랜덤하게 선택해서 해쉬를 생성한 다음 패스워드를 500개 DB에 저장하는 거지. 이후 사용자가 로그인을 시도하면 서버 내부적으로 salt table에서 salt를 500개 랜덤하게 선택해서 해쉬 돌려서 비교하는 식.
와, 상당히 괜찮은 방법인듯. 비교하는데 시간 복잡도가 엄청 많이 들긴 하겠지만 역으로 말하면 그만큼 보안성이 향상된다고 볼 수도 있으니까
단순 로그인에 적용하기는 무리가 있겠지만 방법 자체는 어딘가에 쓰일수 있을듯
아 위에 MD5 인자에서 hash + password가 아니라 salt + password. ㅋ. ㅇㅇ 저렇게 하면 서버 DB가 통째로 털려도 해커는 50,000개 salt에 대해서 rainbow table을 생성하거나 할튼 어떤 attack을 50,000배를 해야 된다는 얘기니깐. 엄청 힘들어지지. 게다가 salt table을 아이디마다 고유하게 생성한다고 하면 더 힘들걸.
근데 비밀번호를 제대로 넣어도 1%정도 확률로는 로그인이 실패하겠네
그러면 두번하면 되겠지 뭐. 1% 제곱하면 거의 0에 수렴하니까
근데 일반 로그인에 이걸 적용하면 서버에 대한 DoS 공격이 너무 쉬워질듯. 뭔가 상당한 보안성이 요구되고 많은 로그인 요청이 있지 않은 대상에 사용하면 좋을듯. 아니면 parameter를 좀 조절해서 부하를 줄이거나
독립 시행일 경우 3번 연속으로 틀릴 확률은 0.0001%일테니 틀릴 경우 retry를 2번 더 해서 내부적으로 3번까지 하게하면 괜찮지 않을까? 그리고 해쉬 알고리즘을 MD5 같은 느린 거 대신에 빠른 걸 쓰면 좀 나을 듯.
DoS를 생각 못했네. 근데 서버가 아니라 로컬 서비스(예: OS 로그인)이면 어떨까? 괜찮아 보이지 않아?
사실 암호화 쪽에선 계산량을 늘리려면 얼마든지 늘릴수 있어서 더 좋은 방법이 많으니까 실제로 적용하긴 힘들듯. 그래도 활용 가능성은 좀 있어보임
로컬이라면 쓸만할듯
근데 이거 활용 방안 생각해 보니까 나쁜 쪽으로 밖에 안 떠오름 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그래도 비밀번호 하나를 다른 salt값으로 해쉬한 결과가 공격당할 가능성도 있어서 속단은 하기 힘들듯
ㅋㅋㅋㅋㅋ 웜 배포할때랑 정보를 외부로 보낼때 어디로 보내는지 모르게 할때랑... 아까 네가 말한대로 serverless에는 꽤 쓸만할지도
나무를 숲에 숨기려고 한다면 거의 항상 적용 가능할듯
예를 들어 전체가 50,000칸인 맵에 크기가 500짜리인 object가 있다. object가 존재하는 칸은 2차원 배열에 색칠이 되어 있다. 이 object의 존재 유무를 파악하기 위해서는 50,000칸을 다 돌 필요 없이 500칸만 랜덤으로 골라서 조사해 보면 99%의 확률로 알아낼 수 있을 듯. 근데 이게 어느 짝에 쓸모가 있는진...
근데 저 경우 linear search하면 문제가 되는 게 object는 칸이 서로 인접한 게 보장이 되니까 linear search가 random search보다 효율이 훨씬 떨어질 수 밖에 없음.
즉 단순히 linear search할 게 아니라 랜덤하게 500칸을 뽑은 뒤 500칸을 뒤지고 거기에도 없으면 다시 나머지 45,000칸에서 500칸을 뽑고... 식으로 여분의 칸이 없을 때까지 진행. 하면 될 듯.
히트율 99%를 유지하기 위해 적어도 500개는 유지해야 한다는 비용이 만만치 않은듯. 파라메터를 조정해서 확률이랑 유지비용 사이의 타협을 봐야 할듯
ㅇㅇ 그런듯. 이거 고찰하면서 한 가지 깨달은 게, 뭐 당연하지만 2차원 공간에서 연속된 데이터 뭉치의 존재 여부를 알아차릴 때는 linear search보다 random search가 효율적이라는 거네. 위의 예에서도 500개씩 뽑을 게 아니라 걍 random한 순서대로 50,000개를 search하면 됨. 그게 결국 500개 뽑고 거기서 보고 또 뽑고 하는 거나 마찬가지일테니.
2차원이 아니라 1차원이어도 마찬가지고.
전체적으로 고르게 분포되어있다고 가정하면 리니어하게 100칸 정도 갈때마다 object가 발견되는 정도 수준일듯. 뭐 500개라는건 그중 99%를 보장해주는 N이라고 보면 되니까..
random으로 500개 뽑는거나 linear로 500개 뽑는거나 비슷하지 않을려나. 중요한건 몇퍼센트까지 보장되느냐인것 같은데
음.. 데이터가 뭉쳐져 있을땐 확실히 다를 수도 있을듯
그러네
야 그러네. 50,000개 중에 공격자가 등록한 500개 도메인에 대해서 500개가 인접하도록 array를 정렬한 상태를 가정하면(정렬하나 안하나 랜덤하면 고르게 나올테니) 랜덤하게 500개 뽑았을 때 그 500개 도메인 중에 하나가 안 나오는 게 이상해 보인다.
한번 생각해 봐. [0]~[499]까지 1이고 [500]~[49999]가 0인 배열을 가정해서 거기서 index를 0~49999 사이에 랜덤한 500개를 최대한 고르게 뽑았다고 하면(랜덤에서 추구하는 성질이기도 하잖아) [0]~[499] 중에 하나는 왠지 높은 확률로 뽑힐 거 같지 않냐.
ㅇㅇ. 그렇게 생각하니까 좀 더 와닿는듯
뭐 수학적으로 엄밀하게 쓸 능력은 안되지만 100개 정도마다 하나 뽑히는 느낌인데 500개를 뽑았으니 왠만하면 하나는 뽑히지 않을까
수학적으론 (50000C500 - 49500C500) / 50000C500일 거고 Wolfram Alpha 돌리니까 0.9935941...나온다.
= (50000개 중에 500개를 뽑을 경우 - 49500개 중에 500개를 뽑을 경우) / (50000개 중에 500개를 뽑을 경우)
그러네. 내가 얘기하려던건 100개중 하나정도 뽑는 느낌에 대한 거였긴 하지만
즉 분모는 50000개 중에 500개를 뽑는 경우이고 분자는 50000개 중의 49500개 중에 500개를 뽑을 여사건이기 때문에 500개 중에 적어도 하나 이상은 뽑을 경우의 수가 됨.
이게 랜덤 알고리즘(Randomized Algorithm)의 매력인 듯. ㅋㅋㅋ
음.. 이런걸 monte carlo method라고 하는건가. 흥미가 생기는듯
뭐 이건 아주 간단한 경우긴 하지만..
이거 제 하드에 영구보존허고싶은데 글 지우지마세욧!!>_<
해시공부할때 생일공격나왔는데 그때는 같은해시값을같은 두메세지를찾는거라고나왔는데 어려웅개념이구나