[UIUCTF 2018] Hastad

Hastad ● Crypto ● 200 Points

sorry wrong chat라고 하고..

ciphertexts.txt 와 moduli.txt가 주어진다.

일단 한번 보자.

이게 ciphertexts.txt이고 아래가 moduli.txt이다.

RSA암호화로 ciphertexts.txt를 보낸것이라 생각한다. 여기서 e=3이라고 하는데...

e값이 매우 작고 평문이 길이가 짧을 경우, n(=p*q)값이 매우 크기때문에.. 암호화된 평문 C=P^e(% n) 에서 n이 너무커서 C가 모듈러 연산에 몇번 걸리지 않는 경우가 있다. 이 경우 C값을 그냥 e 거듭제곱근을 구해서 평문을 복호화해 낼 수가 있다고 한다. 그래서 일단 e제곱근한 값이 나오나 보기로 했다.

c_list = [0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65]
 
 
e = 3.00
 
for idx, c in enumerate(c_list):
    c_list[idx]=c**(1.00/e)
    print("%x " % c_list[idx])
 
 
for c in c_list:
    #c = c**(1.00/e)
    c=format(int(c), 'x')
    print("%s " % (c.decode("hex")))
 

이런 파이썬 코드를 짜서... 출력해보았다.

코드는 해당 ciphertexts.txt의 값들을 각각 세제곱근한 값을 hex값으로 두고, 이를 decode해 평문으로 출력하는 것이다.

위와 같이 출력되었고... 666c61677b757000000000000000000000000000000000000000000000 와 flag{up 를 볼때...

모듈러연산에 걸려 평문값이 짤려 손실된것으로 보인다.

....

아닛.... 엄청난걸 찾았다. 위키백과 굿

https://en.wikipedia.org/wiki/Coppersmith%27s_attack#RSA_basics

위 url을 통해 들어가보면 Håstad's broadcast attack라고 있다.

한번 자세히 알아보자. 

(번역 : https://translate.google.co.kr/translate?hl=ko&sl=en&u=https://en.wikipedia.org/wiki/Coppersmith%2527s_attack&prev=search)

Hastad's Broadcast Attack 

Coppersmith 정리를 이용한 첫 번째 응용으로써, Hastad가 제안했던 알고리즘을 개선한 내용을 알아본다. Bob은 평문 M을 암호화해서 P1,P2,…,Pk 라고 하는 여러 group에게 동시 에 전송하려 한다고 가정하자. 각 group은 각기 RSA 공개키 를 갖고 있다. 그리고 평문M이 모든 Ni보다 작다고 하자. 이런 상황에서 Oscar는 Bob이 모르게 이들의 통신을 도청할 수 있고, k개의 암호문을 가로 챌 수 있다. 편의상, 모든 공개키 ei가 3이라고 하자. 이 경우, k≥3이면, 0scar는 암호문으로부터 평문 M을 복호화 할 수 있다. 즉, Oscar가 세 개의 암호문 C1,C2,C3를 얻었다고 하자. 여기서, C1=M3 modN1, C2=M3 modN2, C3=M3 modN3 이다. 그리고, Oscar가 Ni를 소인수 분해하지 못하게 하기 위해, 서로 다른 i, j 에 대해 gcd(Ni,Nj)=1라고 가정할 수 있다. 그러면, CRT을 이용해, C'=M3 modN1N2N3을 만족하는 Z N1N2N3의 원소 C'를 구할 수 있다. 가정에서 M이 모든 Ni보다 작다고 했기 때문에 M3 < N1N2N3이고 따라서 C'=M3 이 성립한다. 따라서, Oscar는 C'의 삼제곱근을 실수에서 연산하 면, M을 얻을 수 있다. 일반적으로, 모든 공개키(public exponent) ei가 같다고 하고 "k≥ei" 이기만 하면 Oscar는 평문 M을 복호화할 수 있다. 이 공격법은 공개키 e가 작은 경우에 한한다. 하지만, 이 공격법에 미미하게 대응해선 안 된다. 예를 들어, Bob이 평문 M을 암호 화하기 전에, "덧붙이기" 과정을 취할 수 있다. 즉, |M|=m 이라 하면, Bob은 Pi에게 Mi=i2m +M을 암호화해서 전달한다. 그러면, Oscar는 서로 다른 평문에 대안 암호문을 얻기 때문에, 위에서 살펴본 공격법을 취할 수가 없을 것 같다. 하지만, 위와 같은 선형 덧붙이기 과정이 안전하지 못함을 Hastad는 보였다. 더욱이, 그는 덧붙이기 과정으로서, 평문을 입력 으로 하는 고정된 다항식 연산을 취하는 것도 위의 공격방법을 막을 수 없음을 증명했다. 다음은 Hastad의 결과보다 강한 내용(stronger version)이다.

여기서 CRT는  Chinese Remainder Theorem, 로 중국인의 나머지 정리이다.

요약하자면 동일한 메세지를 여러 명에게 동시에 전송할때, 평문 M이 모든 Ni보다 작고, ei가 충분히 작고 알고있는 암호문 k가 k>=ei이면 중국인의 나머지정리(CRT)를 이용해 C를 구할수 있고 이 C의 e제곱근이 바로 평문이다.

먼저 이 문제가 hastad's Broadcast Attack으로 공격할수 있는지 살펴보자.

먼저 e=3으로 작은 값이고, ciphertexts.txt에 같은 flag를 암호화한 암호문 여려개와 moduli.txt에 N이 3개가 주어졌다. (이 3개의 N은 서로 서로수일것이다.)

암호문을 3개 이상얻었으므로 중국인의 나머지 정리를 이용해서 C = M^3 mod N1N2N3을 만족하는 C를 구해보자.

.................

이거 가지고 7시간 삽질을 했는데... 결국 안됐다 ㅡㅡ;; 아나

가장 큰 문제는  C = M^3 mod N1N2N3을 만족하는 C를 구햇는데 이 C의 세제곱근을 못구해서 엄청 헤매다가;;

import gmpy를 통해 해결하였다. 그런데 이게 안구해져서 ㅁㄴㅇㄹ 화가 나려하는데;; 아래와 같은 문제점을 발견해서 풀었다.

------------------------------------------------------------------------------------------------------------------------------

세제곱근을 구할때 보통 r = (c **(1.0/3.0)) 과 같이 구한다. 하지만 큰 수 c를 여기에 쓸 경우 이렇게 쓰면 정확하지 않다...

그래서  flag가  666c61677b757000000000000000000000000000000000000000000000 와 flag{up  이렇게 짤려나오는거였다.

문제에서 일부러 저렇게 준게 아니고 python에서 계산을 못해서 짤려나온거다 ㅡㅡ;;

해결법은 gmpy 모듈을 쓰는것이다.

import gmpy를 하면 result, bool = gmpy.root( num, k)를 쓸수가 있는데; 

이게 num를 k제곱근한 값을 result에 저장하고 bool에 성공여부를 0과 1로 저장한다.

이걸 이용해서 위 코드를 다시 짜면...

import gmpy
 
c_list = [0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65]
 
 
e = 3.00
 
for idx, c in enumerate(c_list):
    c_list[idx], perfect = gmpy.root(c, 3)
    print("%x %d " % (c_list[idx], perfect))
 
 
for c in c_list:
    #c = c**(1.00/e)
    c=format(int(c), 'x')
    print("%s " % (c.decode("hex")))
 
 

이렇게 되고 결과는 아래와 같다.

하... 이렇게 잘나오는걸 삽질을 그렇게 하다니 ㅡㅡ;

다른사람들의 Writeup - 추가

이분들은 그냥 정석대로 Hastad Broadcast Attack을 하셨다. 

암호문이 15개주어졌으니 15개를 3개씩 가능한 모든 조합으로 브루트포싱으로 공격을 시도하면 그 중 계산이 맞아 떨어지는것이 있고, 이것으로 플래그가 구해진다. (물론 나도 가능한 모든 조합으로 공격해보았다. 하지만 실패 ㅡㅡ; 분명 어딘가 실수가 있었겠지...)

이때 사용한 파이썬 모듈이 itertools인데 알아두면 좋을 것 같다. (참고사이트: http://hamait.tistory.com/803)

itertools이 가지고있는 함수들의 목록 및 기능은 여기서 보면 좋다.(https://docs.python.org/2/library/itertools.html)

Iterator	Arguments	Results
product()	p, q, … [repeat=1]	cartesian product, equivalent to a nested for-loop
permutations()	p[, r]	r-length tuples, all possible orderings, no repeated elements

 

특히 이 permutations()라는 것이 좋다.. 가능한 모든 순열을 구해준다.

Other WriteUP

- https://github.com/VoidHack/write-ups/tree/master/UIUCTF%202018/crypto/Hastad

- https://advancedpersistentjest.com/2018/04/09/writeups-hastad-triptych-uiuctf/