search

l0vey0u / ToDo

2 stars 1 forks source link

RSA LLL Attack 조사하기 #126

Closed l0vey0u closed 3 years ago

l0vey0u commented 4 years ago

할 말은 나의 CLog로 대체 한다.

CLog

" CTF Log likes VLog"

Crypto

Double Message (201pt, 67solves)

( RSA, Block Chipher )

제일 시간을 많이 투자했고, 그만큼 제일 근접했으며, 제일 알아간게 많았던 문제

So long time used to solve this prob, thus very-similar to intended solution but can't understand that technique

BTW During read Many blog posts, CTF Writeups, papers I got many technique existence

일단 double.sage부터 보자

아니 일단 sage에서 Crypto 문제구나 느껴진다.

Crypto 문제를 쉽게 풀려면 sage 환경과 sage 문법에 대해 익숙해져야 할 것 같다.

First, I saw that is sage extension that is popular in crypto prob

open Double.sage

from Crypto.PublicKey import RSA
from hashlib import md5
import binascii

nBitSize = 2048
e = 3
Flag = b'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'   # censored

key = RSA.generate(nBitSize)

M1 = Flag + md5(Flag).digest()
M2 = Flag + md5(b'One more time!' + Flag).digest()

M1 = int(binascii.hexlify(M1),16)
M2 = int(binascii.hexlify(M2),16)

C1 = Integer(pow(M1,e,key.n))
C2 = Integer(pow(M2,e,key.n))

with open('out.txt','w') as f:
    f.write('n = ' + hex(key.n)+'\n')
    f.write('C1 = '+ hex(C1)+'\n')
    f.write('C2 = ' + hex(C2)+'\n')

len(n) = 2^2048, e = 3, M1, M2가 비슷한 상황이다.

젤 처음 시도한 것은 e가 3으로 매우 낮기 때문에 C = P^3 mod N 에서 P^3 < 2^2048일 가능성을 두고 C^1/3 계산을 해보았다. 아쉽게 그렇게 쉬운 문제는 아니였다. 또 보면 Flag = 하고 써논 x의 개수가 67개다. 저 개수가 의도된 것이라면 len(p) = 2^ (536 + 128) 로 2^1992 < 2^2048 뭐야 되겠네 하고 gmpy2 모듈로 열심히 해봤지만 저건 걍 x 대충 많이 누른거였다.

실제 플래그 길이가 104자로 (1048+128)3 > 2048 ...

I tried to simply 3th root, when P < N^1/e <=> C^1/e = P, but that was fail... after ctf I knew that P len is 104byte!

그 후에 무한한 구글링의 시작이 시작됬다.

구글링 중 처음 발견한 공격기법은 ( 물론 이 문제와 완벽히 동일한 해법이 있는 글을 더 빨리 봤지만 이해를 못해서 넘겼다. ) Stereotyped message attack 이다.

After failure, I started infinite googling, and finally I found some attack technique that named Stereotyped message attack

( I passed solution post that very very similar to that prob cuz I don't understand that solution at that time )

https://gsdt.github.io/blog/2018/07/20/stereotyped-message-attack/

M1 = F + H(F), M2 = F + H(c+F) 에서 F부분이 동일하므로 저 공격이 먹히지 않을 까 생각했다.

I Guessed that will be work this prob cuz F is same.

저 공격의 원리는 아직 제대로 이해하지는 못했지만 P^e mod N을 (KnownString+x)^e mod N으로 하여 bf범위를 축소시키는 것이다.

That Attack's principle maybe is shortening Brute-Force range ( P^e to (KnownString+x)^e )

저 공격 기법의 다른 이름은 Coppersmith's small public RSA exponent attack with partially known message 이다.

근데 지금와서 보니 결국 내가 알아봤던 것들이 다 동일 기법상에 있다. LLL이라는... 진짜 진득히 LLL을 알아봤어야 했다...

일단 LLL 조사하면 이 글 마무리를 못할 것 같으니 그냥 그 당시 상황만 써야겠다 : )

"Defenit{xxxxxxxxxx}xxxxxxxxxxxxxxxx"이 M의 형태라고 생각하고 코드를 짰다.

저 포스트를 보면 조건이 x < N^1/e 라 되있는데 그땐 정직하게 67자라고 믿었으니까 ((58+16)*24)< 2048 이니 만족했다.

하지만 현실은 111*24 > 2048...

하지만 당연하게 잘 안되니 또 구글링을 시작하고 또 하나의 기법을 찾았다. Franklin-Reiter related message attack , 사실 이걸 보기 전 까지 유용한 글들을 많이 봤다. Crypto CTF 고인물의 포스트나 여러 RSA 공격 기법을 소개한 중국인 포스트나 hash값을 계산할 수 있다는 사실 빼고 제일 비슷했던 문제 라이트업이나 지금보니 거의 답이였던 small e 문제의 라이트업이나 출제자의 RSA 공격법 모음 포스트나 년도별 Crypto CTF 라이트업 모음을 보았다.

지금 느끼는 건데 내 원칙대로 코드 한줄 한줄 놓치지 않고 조사했다면 Small E 문제를 봤을 때 이 문제를 풀었을 것 같다... ( 완전 수학적이였던 이 포스트를 이해 할 정도로 했다면?)

저 문제에 대해 검색하니 출제자가 유심히 봤을 것 같은 블로그 글도 있었다.

하지만 그냥 스크립트 내 n, c1, c2 바꾸는 것으론 절대 해결되지 않자, 역시 hash에 무엇인가가 있구나 생각이 들었다. md5에 대해 열심히 조사해보니 512bit => 128bit 가 되는 Block Cipher 였다. 정직하게 67글자였어도 Padding이 적용됬어야 하는 것이다.

근데 어정쩡하게 여기서 마무리 지어야 할 것 같은게 .... 패딩 포스트가 안보인다 ㅠ...

어서 LLL에 대해 자세히 알아봐야겠다. 폴리노미어 링 나오는걸로 보아 정수론을 좀 더 이해해야겠다.

l0vey0u commented 4 years ago

이 문제의 출처는 Defenit팀의 2020 Defenit CTF - Crypto [ Double Message ] 이다.

l0vey0u commented 4 years ago

핵심과는 별개지만 참고할만한 사이트

l0vey0u commented 3 years ago

머야 출제자님 언제 like 해주셨지 ㅠㅠㅠㅠㅠㅠ todo 양식에 맞지 않아 내리겠지만 LLL 제대로 알아보고 싶어서 선형대수학 교양 신청 했으며 블로그 논문 읽어보기 컨텐츠 진행하면서 해볼 계획이다.