[Crypto][CTF]Bigger is Better - RSA Wiener Attack

Description

I heard choosing a small value for e when creating an RSA key pair is a bad idea. So I switched it up!

 

- dist.txt

N = 0xa0d9f425fe1246c25b8c3708b9f6d7747dd5b5e7f79719831c5cbe19fb7bab66ed62719b3fc6090120d2cfe1410583190cd650c32a4151550732b0fc97130e5f02aa26cb829600b6ab452b5b11373ec69d4eaae6c392d92da8bcbea85344af9d4699e36fdca075d33f58049fd0a9f6919f3003512a261a00985dc3d9843a822974df30b81732a91ce706c44bde5ff48491a45a5fa8d5d73bba5022af803ab7bd85250e71fc0254fcf078d21eaa5d38724014a85f679e8a7a1aad6ed22602465f90e6dd8ef95df287628832850af7e3628ad09ff90a6dbdf7a0e6d74f508d2a6235d4eae5a828ac95558bbdf72f39af5641dfe3edb0cdaab362805d926106e2af
e = 0x5af5dbe4af4005564908a094e0eabb0a921b7482483a753e2a4d560700cb2b2dc9399b608334e05140f54d90fcbef70cec097e3f75395d0c4799d9ec3e670aca41da0892a7b3d038acb7a518be1ced8d5224354ce39e465450c12be653639a8215afb1ba70b1f8f71fc1a0549853998e2337604fca7edac67dd1e7ddeb897308ebf26ade781710e6a2fe4c533a584566ea42068d0452c1b1ecef00a781b6d31fbab893de0c9e46fce69c71cefad3119e8ceebdab25726a96aaf02a7c4a6a38d2f75f413f89064fef14fbd5762599ca8eb3737122374c5e34a7422ea1b3d7c43a110d3209e1c5e23e4eece9e964da2c447c9e5e1c8a6038dc52d699f9324fd6b9
c = 0x731ceb0ac8f10c8ff82450b61b414c4f7265ccf9f73b8e238cc7265f83c635575a9381aa625044bde7b34ad7cce901fe7512c934b7f6729584d2a77c47e8422c8c0fe2d3dd12aceda8ef904ad5896b971f8b79048e3e2f99f600bf6bac6cad32f922899c00fdc2d21fcf3d0093216bfc5829f02c08ba5e534379cc9118c347763567251c0fe57c92efe0a96c8595bac2c759837211aac914ea3b62aae096ebb8cb384c481b086e660f0c6249c9574289fe91b683609154c066de7a94eafa749c9e92d83a9d473cc88accd9d4c5754ccdbc5aa77ba9a790bc512404a81fc566df42b652a55b9b8ffb189f734d1c007b6cbdb67e14399182016843e27e6d4e5fca

 

 

 

• 올해 Patriot CTF에서 출제된 문제다.
• RSA에 대한 기본 개념은 다른 곳에서도 많이 나와 있으니, Wiener Attack에만 집중해보자.
• 이와 유사한 문제가 드림핵에도 나와있었다. 이 문제를 먼저 살펴보면서 Crypto CTF를 푸는 여러 툴들에 대해서도 정리해보자
• https://dreamhack.io/wargame/challenges/177

---

RSA-wiener

 

Description

- 암호 학자 Michael J. Wiener의 이름을 딴 Wiener의 공격은 RSA에 대한 일종의 암호화 공격입니다.해당 공격을 이용하여 플래그를 제출하세요!

 

- flag.txt

0x2393118ecdee71b12de76cb3bc14dd5dd10e5807e06593d3e2e96b1e53d48592d15da092377299bc66290c661ad0c29c8d12354da0c188c799ae21a29f8062487e0543a2a714d68a37f0f98e102ea0bd5df186c2c2f8fbf277329b8e017e6898d19ad707ccd3b75c1af4bda00ac9cb9710cb7e37bedd7b71d92c000c00b867e8

 

- public_key.pem.txt

-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKBgQFSOuj6SExa7VtHUvbbnY57
aGVM9brzp5p/Iq4O4CcLaa4Ssj6lc2AY6iAHIgciWDwrYVrnmKyEXaFVZvjvsh9N
snuDq5RpIe3X9GAnvH6BWROxpPwmyPtULcyCFfkx5kR2sjQSVTbRXoste6xNzm63
524mnnhJ2FhXPMLzg/vSmQKBgQEKnblIfuXfwtCild+olEsxXmNu5c/RGi4AOWmm
jMqvGoXYNKW5UvJJwIhjnAkU5JiMWTAjndXZGCZ7xWgZsJ/iziDVVsa3WzFEh494
3TQva3LG9hwOXRYD2BYsSajZ7RWz/yLqKRAmBE5Si2dTxUhmwHgScSKDsSzqKBhc
YFQd2Q==
-----END PUBLIC KEY-----

 

• 이 문제는 암호화된 flag값과 RSA의 public key값을 제공한다. 여기서 PEM 파일이란 Privacy Enhanced Mail의 줄임말로, 각종 인증 및 비대칭키 암호화 알고리즘에서 사용되는 비밀키, 인증서 등을 텍스트 형식으로 직렬화하여 저장하기 위한 파일을 말한다.
• PEM 파이일을 통해 public key의 N과 e값을 얻어낼 수 있다. PEM parser 온라인 사이트에 해당 파일을 넣어주면 N(modulus)과 e(public exponent)를 얻어낼 수 있다. 
• https://8gwifi.org/PemParserFunctions.jsp#google_vignette

• 결과는 다음과 같이 나온다.

Algo RSA
Format X.509
 ASN1 Dump
RSA Public Key [b5:ea:05:7f:46:9f:66:39:5f:09:6b:0e:d0:75:65:9a:f3:36:ab:20]
            modulus: 1523ae8fa484c5aed5b4752f6db9d8e7b68654cf5baf3a79a7f22ae0ee0270b69ae12b23ea5736018ea2007220722583c2b615ae798ac845da15566f8efb21f4db27b83ab946921edd7f46027bc7e815913b1a4fc26c8fb542dcc8215f931e64476b234125536d15e8b2d7bac4dce6eb7e76e269e7849d858573cc2f383fbd299
    public exponent: 10a9db9487ee5dfc2d0a295dfa8944b315e636ee5cfd11a2e003969a68ccaaf1a85d834a5b952f249c088639c0914e4988c5930239dd5d918267bc56819b09fe2ce20d556c6b75b3144878f78dd342f6b72c6f61c0e5d1603d8162c49a8d9ed15b3ff22ea291026044e528b6753c54866c07812712283b12cea28185c60541dd9

 

• 출력된 N과 e값이 모두 hex값이므로 10진수로 바꿔준다. 바꿔주는 사이트는 검색하면 많이 나오니 생략한다

N : 237513265686025789186562608732400008100581870458434017952788114554225756652162413702306473956172406315118900180084859436965775540087331299252158189935099309726131944473377703166550089276072127708850460299073570538050902891628197488607150799868080449908160852741234270848472245085906293581136277333188361835161
e : 187224198358976786579749067995497890905799822947128651088251530361387419780131539700347226362649795586438751501544451473659148049507814353125472665954342709257182749776947194758327083239358991106508477303866175029695125086636425667367941964361682844471490598884007406957886946810963902666192471332550759161305

 

• 보다시피 e값이 굉장히 큰 수임을 알 수 있다. 원래 RSA에서 e값으로 가장 적절한 값은 3, 17, 65537을 권장하고 있다. 이 값이 아닌 작은 e값을 설정해도 RSA 암호는 굉장히 취약해지지만, 반대로 e값이 너무 큰 경우에도 RSA 암호가 취약해질 수 있음을 나타내는 공격이 Wiener Attack이다. Wiener Attack이 가능한 이유에 대한 수학적 증명은 나중에 적을 수 있으면 적어보도록 하겠다
• Wiener Attack을 실제로 할 수 있는 방법 중 하나는 RSA 암호와 관련된 여러 가지 공격을 실행할 수 있는 툴인 RSHack을 이용하면 된다. 사실 현재 다양한 Crypto 관련 툴들이 많이 있지만 대부분 윈도우 아키텍처(amd64)에서만 사용이 가능하다. 본인은 맥북이라 RSHack을 실행하는데 많은 어려움이 있었다. 결론은 맥북에서 파이썬 idle에서 실행하면 정상적으로 툴 실행이 가능하다.
• https://github.com/zweisamkeit/RSHack

GitHub - zweisamkeit/RSHack: RSHack - Tool for RSA CTF's challenges

 

RSHack 실행 화면이다. RSA와 관련된 다양한 공격들이나 RSA 암.복호화 기능을 수행할 수 있게 해준다

 

 

• 이제 Wiener Attack 옵션을 선택하고 우리가 구한 N과 e값을 구하면 d(private exponent)를 구할 수 있다.

==================== RESTART: /Users/jhkmac/RSHack/rshack.py ===================


		#########################
		#      RSHack v2.1      #
		#      Zweisamkeit      #
		#      GNU GPL v3       #
		#########################



	List of the available attacks:

		1. Wiener Attack
		2. Hastad Attack
		3. Fermat Attack
		4. Bleichenbacher Attack
		5. Common Modulus Attack
		6. Chosen Plaintext Attack

	List of the available tools:

		a. RSA Public Key parameters extraction
		b. RSA Private Key parameters extraction
		c. RSA Private Key construction (PEM)
		d. RSA Public Key construction (PEM)
		e. RSA Ciphertext Decipher
		f. RSA Ciphertext Encipher

	[*] What attack or tool do you want to carry out? 1(input)

			 ***** Wiener Attack *****

		[*] Arguments ([-h] -n modulus -e exponent):

			-n 237513265686025789186562608732400008100581870458434017952788114554225756652162413702306473956172406315118900180084859436965775540087331299252158189935099309726131944473377703166550089276072127708850460299073570538050902891628197488607150799868080449908160852741234270848472245085906293581136277333188361835161 -e 187224198358976786579749067995497890905799822947128651088251530361387419780131539700347226362649795586438751501544451473659148049507814353125472665954342709257182749776947194758327083239358991106508477303866175029695125086636425667367941964361682844471490598884007406957886946810963902666192471332550759161305
			(input)

	~~~~~~~~~~~~~~~~~~~~~~~~~
	      Wiener Attack      
	       Zweisamkeit       
	    GNU GPL v3 License   
	~~~~~~~~~~~~~~~~~~~~~~~~~


	[+] Private exponent: 48912004092406924024000584172054565936474738596922505659344766088380906257001

 

• 이제 우리가 flag를 복호화하는데 필요한 모든 값을 다 얻었으니, flag도 10진수로 변환해주고 $C^d (mod N)$ 값을 계산하면 flag값이 나온다. 이때 복호화된 값은 10진수이므로 우리가 원하는 flag를 구하려면 long_to_bytes()함수를 이용해 바이트값으로 변환해주어야 한다.

from Crypto.Util.number import *
from pwn import *

C = 24981254080909219230265206235193414028780554719956568981014479247148185251168118446607184006846379494138286369937332491801314184196030148052351232512282822191418093014429056913869049243299733179602660079651535369672864881677595298490260859831553321356068082173796345881132554132547112018880976416128995190760
N = 237513265686025789186562608732400008100581870458434017952788114554225756652162413702306473956172406315118900180084859436965775540087331299252158189935099309726131944473377703166550089276072127708850460299073570538050902891628197488607150799868080449908160852741234270848472245085906293581136277333188361835161
d = 48912004092406924024000584172054565936474738596922505659344766088380906257001

str = pow(C, d, N)
print(long_to_bytes(str)) #KCTF{We1l_kn0wn_rSa_ATTAcK}

 

• 파이썬에서 pow함수는 일반적으로 pow(a, b)를 하면 $a^b$값을 출력해주는 것으로만 알고 있지만, pow(a, b, N)으로 세번째 인자를 넣었을 경우 $a^b$의 $mod N$에서의 값을 반환한다. 

---

 

• 이제 Patriot CTF에서 출제한 문제를 보면, 드림핵 문제보다 주어진 값이 더 flag를 구하기 편하게 주어진 것을 알 수 있다. PEM parser 없이도 RSHack 툴만을 사용하면 쉽게 d값이 주어지고, 위의 방법과 동일하게 pow( C, d, N )을 해주면 flag값을 구할 수 있다.
• 이와 다른 방법으로 파이썬에서는 owiener 패키지가 따로 만들어져있다. 
• https://github.com/orisano/owiener

GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSA

 

• owiener.attack( e, N ) 함수를 이용하면 쉽게 d값을 구할 수 있다. 다음은 owiener 패키지를 이용하여 해결한 솔브 코드이다

import owiener

def decrypt_rsa(N, e, c, d):
    m = pow(c, d, N)
    print(f"Decrypted message (integer): {m}")
    
    try:
        m_bytes = m.to_bytes((m.bit_length() + 7) // 8, byteorder='big')
        print(f"Decrypted message (hex): {m_bytes.hex()}")
    except OverflowError:
        print("Failed to convert decrypted message to bytes.")
        return None
    
    try:
        plaintext = m_bytes.decode('utf-8', errors='ignore')
        print(f"Decrypted message (ASCII): {plaintext}")
        return plaintext
    except UnicodeDecodeError:
        print("Failed to decode decrypted message to ASCII.")
        return None

def main():
    N = 20305605772088142254079724960884486005748847015497427301575410293505817279910746556529376931600618579467120276350191887301067237559338164615341364063895698445198450602100622547416422520569435203138576780851363672762744455872440594076326813879006337922017621673305730465334708327073147244529163919113400850500409784670385009784210553996344093407282702258367726551292949276478302283365758654388095557202147107693063638232912598498439805960866571776128157562869249540687561326901969851229705248157494412716795536617485874928328884253043159166953971992309846319441730059436713807550503780907287938041242764808454486287023
    e = 11482685017819657772146196533057795733473449629855289693100164822097723844966138177362511509772380353831218660693991845555704097147035306958570110974439828105301049643719991559075905686792619567403740919201379127416674307003242767236082047328240271052874236417166735391996411110944467555336448767975263755538261304581405836813138939268114431131030122076716110715178499142704121740475206968272546304252509000120167141777229963404829961350506433927568085505890377296146907922613025051900945495785850823000233847703348763563935446095561235796206511113603398775388472794084369294787467785140078624603886943660133858662073
    c = 14531665134114167100979837826752342028891450735196995677636357769295865614666559933494564785156988282683425867538070343091701676024659802732068652721583634562927719841530261965002797455986557324485535150988712817607148213596012867495441913039874954586582711201328787601881545464712275113969203389652205083501245059792154793119468153650644663596094313386931963669611066891546631181901326785976138953854826637304180664070190483908587086086528278431012978756396240661945644492612350098787059899072364888105545382998691878881197718078741483487137826986723167593340766546454020829394951911243295040065262047943870970224586

    print("Attempting to perform Wiener's attack using owiener module to find the private exponent d...")
    d = owiener.attack(e, N)
    
    if d is None:
        print("Failed to find the private exponent d using Wiener's attack.")
    else:
        print(f"Private exponent d found: {d}")
        print("\nDecrypting the ciphertext...")
        plaintext = decrypt_rsa(N, e, c, d)
        if plaintext:
            print("\nDecryption successful!")
            print(f"Plaintext: {plaintext}")
        else:
            print("\nDecryption completed, but failed to interpret the plaintext.")

if __name__ == "__main__":
    main()