'확장된 유클리드 호제법'에 해당되는 글 1건

  1. 2010.06.21 [ CodeGate 2010 ] Challenge 7 풀이 (2)

2010.06.21 18:47 WarGame

http://www.vnsecurity.net/2010/03/codegate-2010-challenge7-weak-ssl-cracking/


*이 풀이는 위 두 사이트에서 참조하여 정리하였음을 알려드립니다 




문제의 패킷을 열어보면 , 192.168.100.2 와 192.168.100.4 간의 SSL 통신이 있었음을 알 수 있습니다

패킷의 상세 정보를 보면 RSA 로 암호화 되어 있는 것을 볼 수 있죠

RSA는 대표적인 공개키 알고리즘으로 공개키와 개인키가 모두 있어야만 받은 데이터를 해석 할 수 있습니다



RSA에도 여러 버전이 있는데, 그 버전을 알아야 풀이가 가능하겠죠

지난 번에 포스팅 했던 글에서 공개키의 생성 부분을 잠시 다시 살펴보겠습니다
 
[+] 키의 생성

  1. p \,와 q \, 라고 하는 두 개의 서로 다른 (p \ne q소수를 고른다.
  2. 두 수를 곱하여 N = p q \, 을 찾는다.
  3. \varphi(N) = (p-1)(q-1) \, 를 구한다.
  4. \varphi(N) 보단 작고, \varphi(N)와 서로 소인 정수 를 찾는다.
  5. 유클리드 호제법을 이용하여 d e \equiv 1 \pmod{\varphi(N)} 을 만족시키는 를 구한다.

A의 공개키는 위에서 구한 두 개의 숫자로 이루어진 <Ne>이고, 개인키는 이다. A는 <Ne>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다. 여기서 와 의 보안은 매우 중요하다. 이를 가지고 와 의 계산이 가능하기 때문이다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전하다.



p와 q의 보안은 매우 중요하다고 하였으나

상당 수의 RSA는 p와 q 값이 공개된 상태입니다. 물론 자의적으로 공개한건 아니고

타의적으로 공개되었겠죠 :D



아무튼, p와 q 값을 알기 위해서는 N 값을 알아내서 버전에 맞는 RSA 를 찾아내야 합니다

혹은 패킷에서 추출한 파일을 openssl 로 분석하는 방법이 있겠는데요

Python 코드를 통해 추출하도록 하겠습니다



도출한 N과 e 값을 통해서 p,q 값을 찾습니다

RSA-768 이군요

p , q 값에 확장된 유클리드 호제법을 적용합니다

값이 음수로 나오지만 조건

 d e \equiv 1 \pmod{\varphi(N)} 는 만족하는 것을 확인 하실수 있습니다

이를 통해서, ,개인키 정보를 담은 파일을 만들수 있는데요


이 개인키 파일을 이용해서 ssl 이 적용된 패킷의 정보를 복호화할 수 있습니다



WireShark 를 이용해서 복호화 시켜보면..



쨘-

공개키 구조를 사용한다고 무조건 안전한게 아니군요

하긴 n 값에서 p, q 값을 찾아내리라고 생각지도 못했을 것 같은데 말이죠

이렇게 값이 밝혀진 것을 factor 되었다고 표현하더라구요

RSA 768 같은 경우는 2009년 12월에 factor 되었고..

현재 뚫리지 않은 것 역시 언젠가는 factor 되겠죠

정말이지 보안 분야는 창과 방패의 끝없는 대결같군요 :D

'WarGame' 카테고리의 다른 글

[ CodeGate 2010 ] Challlenge 15 풀이  (0) 2010.07.06
[ CodeGate 2010 ] Challenge 8  (0) 2010.06.22
[ CodeGate 2010 ] Challenge 7 풀이  (2) 2010.06.21
[ Python Challenge ] level 15  (0) 2010.06.08
[ CodeEnge Malware Analysis ] level 8  (0) 2010.05.30
[ CodeEnge Malware Analysis ] level7  (0) 2010.05.30
Posted by LinkC

댓글을 달아 주세요

  1. cogch 2011.09.16 13:24  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 대회 문제풀이 항상 잘 보고있습니다. 저는 보안을 공부하고 있는 학생입니다.
    궁금한게 있는데 아무리 찾아봐도 못찾겠어서 이렇게 직접 여쭈어 봅니다. N값과 e값 도출하는 파이썬 코드에서 payload의 범위가 94:1141 인데
    그 범위를 어떻게 설정한건지 잘 모르겠습니다. 혹시 주인장님 이 문제 패킷파일있으면 보내주실수 있으신가요? cogch243@gmail.com 입니다.

    • LinkC 2011.09.18 01:39  댓글주소  수정/삭제

      안녕하세요 cogch님. 제 글이 도움이 되었다니 기쁘네요 :D

      일단 문의 주신 패킷 내용의 범위는 Header를 제외한 인증 Data를 나타냅니다.

      Packet Body 94 byte 부터 [ Header를 포함한 절대주소는 160 Byte 부터 ]

      1141 Byte 까진데 사실 1141 Byte는 의미 없다고 보시면 됩니다.

      실제로는 700 Byte 남짓 밖에 안들어가거든요.

      아무튼 인증에 필요한 Data의 범위라고 이해하시면 될 거 같네요.

      문제 파일은 메일로 보내드리도록 하겠습니다.

      열공하시고 의문점 있으면 또 문의 주세요!

이전버튼 1 이전버튼

블로그 이미지
LinkC

태그목록

Tistory Cumulus Flash tag cloud by BLUEnLIVE requires Flash Player 9 or better.

공지사항

Yesterday31
Today9
Total333,198

달력

 « |  » 2019.10
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

최근에 받은 트랙백

글 보관함


. .