'md5'에 해당되는 글 2건

  1. 2010.07.06 [ CodeGate 2010 ] Challlenge 15 풀이
  2. 2010.06.16 Cryptography!

2010.07.06 18:59 WarGame

이 분야 문제는 바이너리로 남아있는 것도 아니고 삽질하면서 풀어보기도 불가능하네요

혼자 삽질해도 풀수 있을지 없을지도 의문이지만..

대회 끝나고 문제소스 등을 공개해주신다면 공부하는데 한결 수월할 것 같은데 말이죠

이번 문제 또한 자력으로 푼게 아니라 , 다른 사이트에 올라온 풀이를 보고 

제가  나름대로 정리하여 올렸음을 알립니다

갈수록 주인장의 잉여력이 묻어나는 군요

또한, 그림은 Wiki 와

http://netifera.com/research/flickr_api_signature_forgery.pdf

 에서 퍼왔음을 명시합니다

이러한 문제를 풀때마다 느끼는 거지만 정말 보안 분야는 넓네요

너무나 다양한 방법이 있고, 그 방법 마저 지속적으로 갱신되고 있으니까요


각설하고, 문제 풀이 들어갑니다

이번 문제는 8번 문제와 비슷합니다

input 값을 주면 그에 해당하는 Cookie 가 생성되고

이 Cookie 를 토대로 웹페이지에서 복호화하여 답인지 아닌지 체크 하는 형식이죠

input 에 aaaa를 넣는다면 다음과 같은 Cookie 가 생성됩니다

web1_auth = YWFhYXwx|8f5c14cc7c1cd461f35b190af57927d1c377997e


그리고 “Welcome back, aaaa! You are not the administrator.”

와 같은 메시지가 출력되죠

Cookie 는 | 를 기준으로 두 파트로 나눌수 있는데

첫번째 파트는 aaaa|1의 Base64 encoding 결과 입니다

두번째는 input 값에 길이가 달라지지도 않고

구성 문자 형식으로 볼때 hash 값이라는 것을 예측할 수 있습니다

길이가 40 이라는 것으로 sha1 으로 좁힐 수 있습니다

sha1 이나 md5 모두 Padding Attack  다른 용어로 length-extention Attack 에 취약합니다

이를 설명하자면.. Key 값인 m\, 자체를 몰라도   h(m)\, 과  len(m)\,  이 주어진다면

h (m||m')\,  을 알아낼 수 있다는 것입니다
 
|| 는 그냥 문자열의 연속이라고 보시면 되구요

이때 padding , extention 은 이 암호화 연산이 Block 단위로 이루어지기 때문에 마지막 Block 을 채워 넣는다고 하는데서

유래된걸로 보입니다

이를 나타내면 다음과 같겠죠




Sha1 의 Block Size는 512bit , 그러니까 64byte가 되겠죠



이를 시험해봅시다

위 참조 사이트에 있는 소스를 긁어서 보겠습니다



이때 필요한 sha1 hash를 수행하는 파일은


수행해보시면 아실수 있겠지만

orig_msg 의 길이는 25 이고

extention 이 적용된 msg 의 길이는 55 인것을 알 수 있습니다

여기에 key 의 길이 9를 합하면 64byte죠

즉 한 Block 을 채운것을 볼 수 있습니다





즉 extension 한 뒤에

add 함수를 이용하여 update 를 호출함으로써

새로 블럭을 생성하여 완성한다는 것입니다

물론 sha1, md5 등의 함수는 길이가 고정되어 있기 때문에

단순히 생성된 블럭을 이어 붙인다는게 아니라

완전히 다른 값이 생성되게 됩니다

아무튼 이렇게 생성을 하게 되면

key값을 모르더라도 key+orig_msg+padding+new_msg 의 Hash 함수를 구할 수 있게 되죠

인증 방식이 <name> | <role> 이기 때문에 가능한 방식입니다

만약 <role> | <name> 이었다면 이 공격 방식은 성공하지 않았겠죠


입력값으로 aaaa를  넣은 cookie 를 이용한다고 했을때

여기서 우리가 입력할 name 은  'aaaa|1'+<paddingggggggg>+'|0' 인 것입니다

|0 까지를 입력한 name 으로 인식하게 하려는 것이죠

실제로 나온 base64 Encoding 값인

YWFhYXwxgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD4fDA= 

을 decoding 시켜보면  

 aaaa|1€                               ?0

가 나오게 됩니다

이렇게 나온 Signal 값인  70f8bf57aa6d7faaa70ef17e763ef2578cb8d839 을 넣으면

인증을 통과하게 됩니다

재밌지 않나요? :D

'WarGame' 카테고리의 다른 글

ISEC 2009 Challenge 12 Solution  (0) 2010.08.23
ISEC 2009 Challenge6 with GOT OverWrite  (0) 2010.08.22
[ 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
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.

공지사항

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    

최근에 받은 트랙백

글 보관함


. .