'공개키'에 해당되는 글 2건

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

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

2010.06.16 00:53 Etc../Encryption

대칭키 & 비밀키 (Symmetric-key cryptography &  private key)

대칭키 OR 비밀키로 불리는 암호화는 송,수신자가 같은 키를 사용하여 부호화, 복호화 하는 것을 말합니다




[+]블록 암호화

 정해진 비트 길이의 정보를 암호화하는 암호 방식으로, 이때의 정보 단위를 블록이라고 부릅니다. 만약 암호화하려는 정보가 블록 길이보다 길 경우에는 블록 암호를 바로 이용할 수 없기 때문에, 특정한 운영 모드가 사용됩니다

이 운영 모드는 각 블록들간의 연관성 또는 의존성을 주는 방식이라고 보면 되죠

-운영모드

Ex) ECB, CBC, PCBC, CFB, OFB, CTR








DES (Data Encryption Standard) ; 데이터 암호 표준


블록 암호의 일종으로, 미국 NBS (National Bureau of Standards, 현재 NIST)에서 국가 표준으로 정한 암호.

일반적인 DES는 현재 취약한 것으로 알려져 있습니다




Key Sizes : 56bits

Block Sizes : 64 bits

Rounds : 16

많은 회사들이 세개의 키가 잇달아 적용되는 'Triple DES' 사용


http://en.wikipedia.org/wiki/Data_Encryption_Standard































AES (advanced encryption standard) ; 고급 암호 표준

DES를 대체하기 위한 목적으로 등장.  미국정보 표준으로 지정된 암호 형식


Key Sizes  : 128, 192 or 256  bits

Block Sizes : 128 bits

Rounds : 10, 12 or 14 [ depending on key size ]

http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

High-level description of the algorithm

  1. AddRoundKey—each byte of the state is combined with the round key using bitwise xor
  • Rounds
  1. SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
  2. ShiftRows—a transposition step where each row of the state is shifted cyclically a certain number of steps.
  3. MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
  4. AddRoundKey
  • Final Round (no MixColumns)
  1. SubBytes
  2. ShiftRows
  3. AddRoundKey



Blowfish

마찬가지로 DES를 대체하는데 사용될 수 있는 암호화 알고리즘. 32~ 488 비트까지 가변적인 길이의 키를 사용하는 대칭 블록.

미국 내 뿐만 아니라 수출용으로도 이상적으로 사용될 수 있다는군요.


http://en.wikipedia.org/wiki/Blowfish_(cipher)






[+]스트림 암호화

 스트림 암호에서는 연속적인 데이터 입력을 하나씩 받으면서 암호화한다. 하지만 블록 암호에서도 OFB나 OTR 등의 운영 모드를 사용할 경우 스트림 암호처럼 사용할 수 있는 등, 두 암호 사이의 구분이 확실한 것은 아님.

http://en.wikipedia.org/wiki/Stream_cipher

Ex) A5/1, A5/2, RC4, SEAL,

HASH

모든 해시 함수의 가장 기본적인 성질은 두 해시 값이 다르다면 원래의 데이터도 어딘가 다르다는 것.

같은 해시 값을 가진다면, 원래의 입력값이 같다는 것을 시사하지만 보장해주지는 않음.

원래 입력의 한 비트만 바뀌더라도 해시 함수의 성질로 인해 해시 값은 크게 달라집니다.

Ex) MD5, SHA

http://en.wikipedia.org/wiki/Hash_function


A hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".








공개 키 암호화(Public-key cryptography)


신뢰할 수 있는 기관에서 부여된 한쌍의 공개키와 개인키를 사용함으로써, 안전하고 은밀하게 데이터나 자금을 교환 할 수 있게 함.

대칭키 암호화의 경우 여러 사용자가 사용하려면 (n*(n-1)/2)  대칭키가 필요하게 되고 이러한 생성과 분배는

유지, 관리를 어렵게 하는 문제점이 있을 뿐더러, 인터넷과 같은 개방형 시스템에서 동일한 대칭키를 가지는 것은

위험하기 때문에 공개키 암호화 방식이 등장하게 되었습니다


[+]PKI 구성 요소

1. 디질털 인증서를 발급하고 검증하는 인증기관

2. 공개키 또는 공개키에 관한 정보를 포함하고 있는 인증서

3. 디지털 인증서가 신청자에게 발급되기 전에 인증기관의 입증을 대행하는 등록기관

4. 공개키를 가진 인증서들이 보관되고 있는 하나 이상의 디렉토리

5. 인증서 관리 시스템



[+] 동작 원리


다음의 일을 하기 위해 ...
누구 것을 사용?
어떤 키를 사용?
암호화된 메시지를 송신
수신자의
공개키
암호화된 서명을 송신
송신자의
개인키
암호화된 메시지의 해독
수신자의
개인키
암호화된 서명의 해독 (그리고 송신자의 인증)
송신자의
공개키





[+] 키의 생성

  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는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다. 여기서 와 의 보안은 매우 중요하다. 이를 가지고 와 의 계산이 가능하기 때문이다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전하다.




- 유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘의 하나

문제) 1071과 1029의 최대공약수를 구하라.
  • 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
  • 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21
  • 42은 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.





- 확장된 유클리드 호제법

정수 m, n 의 최대공약수(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때,

확장된 유클리드 호제법을 이용하여,

am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. 위에서 든 예의 경우,

1071 = 1 * 1029 + 42 
1029 = 24 * 42 + 21 
42 = 2 * 21 

이므로

21 = 1029 - 24 * 42 = 1029 - 24 * (1071 - 1 * 1029) = -24 * 1071 + 25 * 1029 

가 된다.

특히, m, n이 서로소(최대공약수가 1)인 경우, am + bn = c는 임의의 정수 c에 대해서 정수해 (a,b)가 존재한다.


'Etc.. > Encryption' 카테고리의 다른 글

Cryptography!  (0) 2010.06.16
What is CRC?  (0) 2009.11.06
What is Padding?  (0) 2009.10.31
Posted by LinkC
이전버튼 1 이전버튼

블로그 이미지
LinkC

태그목록

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

공지사항

Yesterday30
Today3
Total328,675

달력

 « |  » 2019.5
      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  

최근에 받은 트랙백

글 보관함


. .