この大会は2022/6/4 9:00(JST)～2022/6/6 9:00(JST)に開催されました。
今回もチームで参戦。結果は100点で140チーム中114位でした。
自分で解けた問題をWriteupとして書いておきます。
rsalab - Beginner (Crypto)
$ nc rsalab-a75d5c9a.challenges.bsidessf.net 6537 _____ _____ _____ /\ \ /\ \ /\ \ /::\ \ /::\ \ /::\ \ /::::\ \ /::::\ \ /::::\ \ /::::::\ \ /::::::\ \ /::::::\ \ /:::/\:::\ \ /:::/\:::\ \ /:::/\:::\ \ /:::/__\:::\ \ /:::/__\:::\ \ /:::/__\:::\ \ /::::\ \:::\ \ \:::\ \:::\ \ /::::\ \:::\ \ /::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \:::\ \ /:::/\:::\ \:::\____\ /\ \:::\ \:::\ \ /:::/\:::\ \:::\ \ /:::/ \:::\ \:::| |/::\ \:::\ \:::\____\/:::/ \:::\ \:::\____\ \::/ |::::\ /:::|____|\:::\ \:::\ \::/ /\::/ \:::\ /:::/ / \/____|:::::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / |:::::::::/ / \:::\ \:::\ \ \::::::/ / |::|\::::/ / \:::\ \:::\____\ \::::/ / |::| \::/____/ \:::\ /:::/ / /:::/ / |::| ~| \:::\/:::/ / /:::/ / |::| | \::::::/ / /:::/ / \::| | \::::/ / /:::/ / \:| | \::/ / \::/ / \|___| \/____/ \/____/ __ __ __ / / ____ _/ /_ ____ _________ _/ /_____ _______ __ / / / __ `/ __ \/ __ \/ ___/ __ `/ __/ __ \/ ___/ / / / / /___/ /_/ / /_/ / /_/ / / / /_/ / /_/ /_/ / / / /_/ / /_____/\__,_/_.___/\____/_/ \__,_/\__/\____/_/ \__, / /____/ Welcome to the RSA Laboratory! We hope you learn and have fun! Try "help" for a list of commands RSA Laboratory> help RSA Laboratory help: Commands: help // Prints this help help first // Read this first help conventions // Describe the conventions used by this challenge lab help rsa // Explanation of RSA help mod // Explanation of modular arithmetic help code // Dump sample code to help with some challenges help challenge <n> // Get help on a specific challenge status // Print the challenge statuses challenge <n> // Complete the nth challenge getflag beginner // Flag for completing challenges 1-3 getflag intermediate // Flag for completing challenges 4-6 getflag advanced // Flag for completing challenges 7-8 exit // Exit the lab ^d // Same as exit but 100% more Unix-points RSA Laboratory> status Challenge Statuses ================== beginner: 1 - Getting Started: RSA Encryption 2 - Modular Inverse 3 - Choose-Your-Own-Key! intermediate: 4 - Break RSA! 5 - Fermat's Big Factorization 6 - Weak Entropy: Weak Keys advanced: 7 - Exponent Size Matters 8 - Signing Fault RSA Laboratory> challenge 1 Challenge 1: Before your start on attacking RSA, it's important to first understand basic RSA operations like encryption and decryption. For this challenge, we have generated a public key. Your job is to encrypt the provided message with that public key to get the ciphertext. RSA encryption uses the encrypting exponent, e. Decryption is the same mathematical operation except that it uses the decrypting exponent, d. If you can encrypt with the provided e then you could decrypt (if you had d) just as easily. == Generated Public Key == Public Modulus (n): 86828730984014867052517824177477883975814629207826179470445671208095424758859 Encrypting Exponent (e): 65537 Message to encrypt (m): 1234567890 What is the ciphertext (c) for the message (m) using the public key?
Challenge 1 は c = pow(m, e, n) を求めればよい。
RSA Laboratory> challenge 2 Challenge 2: One of the most intimidating things about RSA when you first read about it is the notion of a "modular inverse". In our everyday lives we're pretty familiar with the idea that (1/3) * 3 = 1 or that (5/7) * (7/5) = 1. That is, 1/3 is the inverse of 3 and 5/7 is the inverse of 7/5. What happens though when the numbers "wrap around" because of a modulus? As one example, you can verify easily that the inverse of 2 mod 5 is 3 mod 5 because 2 * 3 = 6 and 6 mod 5 = 1. The idea that 2 and 3 are inverses mod 5 is not at all obvious. Or, even if mod 5 is obvious, in the general case where the modulus is large inverses are not obvious. In this challenge you are given e and n (as well as the factors of n, p and q)and you need to find the modular inverse of e mod phi(n). Recall that when n has two factors phi(n) is (p - 1) * (q - 1). == Generated Public Key == Public Modulus (n): 105991610937793432511512769183140925792599561981875711633528491974096472851013 Encrypting Exponent (e): 65537 == Secret Primes == Prime p: 329304195514613069521087428978491862187 Prime q: 321865352405113805300386876581403323599 What is secret decrypting exponent (d) that is the couterpart of e?
Challenge 2 は d = inverse(e, (p - 1) * (q - 1))を求めればよい。
RSA Laboratory> challenge 3 Challenge 3: RSA is an "asymmetric" encryption algorithm because the key used to decrypt (d) is not the same key that is used to encrypt (e). This challenge will let you experience that first-hand. You provide your public key (n) and (e) and this challenge will encrypt a secret message (m) and provide you the ciphertext (c). Then using your decrypting exponent (d) you can decrypt the ciphertext back to the secret message. You are highly encouraged to generate your own key here instead of finding RSA keys somewhere. To pass this challenge the n value you provide must be at least 512 bits, not be prime and the e value you choose must be at least 100. 65537 is a good choice for e. What is n for your public key?
Challenge 3 は条件を満たすn, eを指定すると、cが提示される。p, qから構成していけば秘密鍵もわかっているので、それを使って復号すればよい。
#!/usr/bin/env python3 import socket from Crypto.Util.number import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('rsalab-a75d5c9a.challenges.bsidessf.net', 6537)) #### Challenge 1 #### cmd = 'challenge 1' data = recvuntil(s, b'> ') print(data + cmd) s.sendall(cmd.encode() + b'\n') data = recvuntil(s, b'==\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) n = int(data.split(' ')[-1]) data = recvuntil(s, b'\n').rstrip() print(data) e = int(data.split(' ')[-1]) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) m = int(data.split(' ')[-1]) c = pow(m, e, n) data = recvuntil(s, b'? ') print(data + str(c)) s.sendall(str(c).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) #### Challenge 2 #### cmd = 'challenge 2' data = recvuntil(s, b'> ') print(data + cmd) s.sendall(cmd.encode() + b'\n') data = recvuntil(s, b'==\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) e = int(data.split(' ')[-1]) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) p = int(data.split(' ')[-1]) data = recvuntil(s, b'\n').rstrip() print(data) q = int(data.split(' ')[-1]) d = inverse(e, (p - 1) * (q - 1)) data = recvuntil(s, b'? ') print(data + str(d)) s.sendall(str(d).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) #### Challenge 3 #### cmd = 'challenge 3' data = recvuntil(s, b'> ') print(data + cmd) s.sendall(cmd.encode() + b'\n') p = getPrime(257) q = getPrime(257) n = p * q e = 65537 data = recvuntil(s, b'? ') print(data + str(n)) s.sendall(str(n).encode() + b'\n') data = recvuntil(s, b'? ') print(data + str(e)) s.sendall(str(e).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) c = int(data.split(' ')[-1]) d = inverse(e, (p - 1) * (q - 1)) m = pow(c, d, n) data = recvuntil(s, b'? ') print(data + str(m)) s.sendall(str(m).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) #### Getflag Beginner #### cmd = 'getflag beginner' data = recvuntil(s, b'> ') print(data + cmd) s.sendall(cmd.encode() + b'\n') for _ in range(9): data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
_____ _____ _____
/\ \ /\ \ /\ \
/::\ \ /::\ \ /::\ \
/::::\ \ /::::\ \ /::::\ \
/::::::\ \ /::::::\ \ /::::::\ \
/:::/\:::\ \ /:::/\:::\ \ /:::/\:::\ \
/:::/__\:::\ \ /:::/__\:::\ \ /:::/__\:::\ \
/::::\ \:::\ \ \:::\ \:::\ \ /::::\ \:::\ \
/::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \:::\ \
/:::/\:::\ \:::\____\ /\ \:::\ \:::\ \ /:::/\:::\ \:::\ \
/:::/ \:::\ \:::| |/::\ \:::\ \:::\____\/:::/ \:::\ \:::\____\
\::/ |::::\ /:::|____|\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /
\/____|:::::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ /
|:::::::::/ / \:::\ \:::\ \ \::::::/ /
|::|\::::/ / \:::\ \:::\____\ \::::/ /
|::| \::/____/ \:::\ /:::/ / /:::/ /
|::| ~| \:::\/:::/ / /:::/ /
|::| | \::::::/ / /:::/ /
\::| | \::::/ / /:::/ /
\:| | \::/ / \::/ /
\|___| \/____/ \/____/
__ __ __
/ / ____ _/ /_ ____ _________ _/ /_____ _______ __
/ / / __ `/ __ \/ __ \/ ___/ __ `/ __/ __ \/ ___/ / / /
/ /___/ /_/ / /_/ / /_/ / / / /_/ / /_/ /_/ / / / /_/ /
/_____/\__,_/_.___/\____/_/ \__,_/\__/\____/_/ \__, /
/____/
Welcome to the RSA Laboratory! We hope you learn and have fun!
Try "help" for a list of commands
RSA Laboratory> challenge 1
Challenge 1:
Before your start on attacking RSA, it's important to first understand
basic RSA operations like encryption and decryption. For this
challenge, we have generated a public key. Your job is to encrypt the
provided message with that public key to get the ciphertext.
RSA encryption uses the encrypting exponent, e. Decryption is the same
mathematical operation except that it uses the decrypting exponent, d.
If you can encrypt with the provided e then you could decrypt (if you
had d) just as easily.
== Generated Public Key ==
Public Modulus (n): 94899042868431872284171148580816489604348651419541351335361638942477157443523
Encrypting Exponent (e): 65537
Message to encrypt (m): 1234567890
What is the ciphertext (c) for the message (m) using the public key? 5175736424660611339210306216866106341740037819925937670054602090316107149899
Correct!
RSA Laboratory> challenge 2
Challenge 2:
One of the most intimidating things about RSA when you first read
about it is the notion of a "modular inverse". In our everyday lives
we're pretty familiar with the idea that (1/3) * 3 = 1 or that (5/7) *
(7/5) = 1. That is, 1/3 is the inverse of 3 and 5/7 is the inverse of
7/5. What happens though when the numbers "wrap around" because of a
modulus? As one example, you can verify easily that the inverse of 2
mod 5 is 3 mod 5 because 2 * 3 = 6 and 6 mod 5 = 1. The idea that 2
and 3 are inverses mod 5 is not at all obvious. Or, even if mod 5 is
obvious, in the general case where the modulus is large inverses are
not obvious.
In this challenge you are given e and n (as well as the factors of n,
p and q)and you need to find the modular inverse of e mod
phi(n). Recall that when n has two factors phi(n) is (p - 1) * (q - 1).
== Generated Public Key ==
Public Modulus (n): 77737640655685619042190856102034492401638770090359667823273091502941643328193
Encrypting Exponent (e): 65537
== Secret Primes ==
Prime p: 262774966468132123848805601629169939609
Prime q: 295833509944004520302962453816556828777
What is secret decrypting exponent (d) that is the couterpart of e? 42519240535021540506681316322589200216810648537674339726364999317926341227137
Correct!
RSA Laboratory> challenge 3
Challenge 3:
RSA is an "asymmetric" encryption algorithm because the key used to
decrypt (d) is not the same key that is used to encrypt (e). This
challenge will let you experience that first-hand. You provide your
public key (n) and (e) and this challenge will encrypt a secret
message (m) and provide you the ciphertext (c). Then using your
decrypting exponent (d) you can decrypt the ciphertext back to the
secret message.
You are highly encouraged to generate your own key here instead of
finding RSA keys somewhere.
To pass this challenge the n value you provide must be at least 512
bits, not be prime and the e value you choose must be at least
100. 65537 is a good choice for e.
What is n for your public key? 32936175784346413076050285555296382882862624662924010552735293363201385082027351059649815528062802037831311998896470714825457700020287844724202098121055689
What is e for your public key? 65537
The ciphertext you must decrypt is 20955722228915016420051912936865907667987279932758663828266102238501457306403281935518169479932696502650057964525931025217270845550543851633330971357972987
What was m (decrypt with the d you've made for your key!)? 134944442607317421674829361658617047088
Correct!
RSA Laboratory> getflag beginner
Challenge 1, Getting Started: RSA Encryption, complete!
Challenge 2, Modular Inverse, complete!
Challenge 3, Choose-Your-Own-Key!, complete!
beginner set complete!
CTF{right_so_awesome!}
CTF{right_so_awesome!}
