Weak RSA
First crypto challenges, it was a pem file which can be opened with a python module or online pem parsers, We used the latter first just for a quick look, We noticed how big the e value is and we can safely conclude that: $$ d<\frac{N^{\frac14}}{3} $$ We can use the Wiener’s attack to calculate the private exponent.
There is a python implementation of this attack that is already written, so just if you haven’t, paste this on a package manager:
pip3 install owiener
Then you can write a python script to find d and open the flag file in python and rest is textbook RSA, here’s the code:
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
import owiener
key = RSA.importKey(open('pubkey.pem', 'r').read())
N=key.n
e=key.e
d = owiener.attack(e, N)
c= open("flag.enc","rb").read()
c = bytes_to_long(c)
print(long_to_bytes(pow(c, d, key.n)))
Flag:
Signal From outer Space
Downloading the files, we see there is a pdf, encrypted flag and source code.
We noticed the pdf had an equation of sorts, it is in the form of an Elliptical curve equation.
We are given a, b, and the modular prime p. Also, there are two point which are given, one of them has the heading Point of reference which we can assume to be the generator point.
We can plug in those in the empty variables that is supposed to be filled in the code for now:
p = 19930885203825540108513916323464619607890520613882110268999315402502483992713624056070847778485065788387695567162120805830837964237496163664777233360835853
a = 16964108867870875431022511847406074513505438269132199629926447105117327702973321429130078673611996313382775579316996202239740533714013559789369433905598853
b = 2557269903904682970099236538031735218462780844817175317697385659377007186785050969676938059088155922328011075081606354569621958862612850816694647002380820
g_x = 11612316038801479962400723698427883310130163176291338759911281034170556609743457773032375965620429931675410389220512342834663089126659445523701533922313238
g_y = 14492470559976609909614920150302533890662281539874542639808213982956316710837667114681496336361906718748053884513468343236055545337522055713141076615967243
Next, we figure out what the error point is supposed to mean, we notice the way the file using elliptical curve to find a multiple of a Generator then using that point to generate shared secret as key for encryption.
There is also the info that is given in the question which says that the error point is a multiple of the generator.
We looked at the code again and noticed that the shared secret is generated by doing the point multiplication again.
We can assume the error point is value that was multiplied once, i.e. the variable public in which multiplication was done once. We can write this down as maths values to make it clearer. $$ \begin{aligned} Public = n\ *\ G \newline Key = n\ *\ Public \end{aligned} $$ Where the Key only uses, the x point for the encryption
Now the next question is how do we find n? Elliptical curves are very hard to solve, so calculation of n should be almost impossible… unless the curve is anomalous.
We went through the list of all the attacks that was possible for a simple anomalous curve. All the values are too big for Pohlig-Hellman Attack (which uses discrete logarithm). But there was one thing we noticed and that was the order of curve is the same as that of modular prime p. We checked this in sage by writing it in the form of elliptical curve equation:
p = 19930885203825540108513916323464619607890520613882110268999315402502483992713624056070847778485065788387695567162120805830837964237496163664777233360835853
a = 16964108867870875431022511847406074513505438269132199629926447105117327702973321429130078673611996313382775579316996202239740533714013559789369433905598853
b = 2557269903904682970099236538031735218462780844817175317697385659377007186785050969676938059088155922328011075081606354569621958862612850816694647002380820
g_x = 11612316038801479962400723698427883310130163176291338759911281034170556609743457773032375965620429931675410389220512342834663089126659445523701533922313238
g_y = 14492470559976609909614920150302533890662281539874542639808213982956316710837667114681496336361906718748053884513468343236055545337522055713141076615967243
E = EllipticCurve(GF(p), [a,b])
G = E(g_x,g_y)
print(order(E)==p)
Which returns True
This makes it prone to something called a smart attack and can be solved very easily with some algorithms. I don’t want to touch on the maths behind a smart attack as it is long winded, the jist of it the is we move the discrete logarithm problem from Elliptic curve to an integer mod p,but I shall link my point of reference which I used to implement the algorithm.
https://wstein.org/edu/2010/414/projects/novotney.pdf
So, we can essentially calculate n this way, here’s my code for algorithm which was implemented in sage:
p = 19930885203825540108513916323464619607890520613882110268999315402502483992713624056070847778485065788387695567162120805830837964237496163664777233360835853
A = 16964108867870875431022511847406074513505438269132199629926447105117327702973321429130078673611996313382775579316996202239740533714013559789369433905598853
B = 2557269903904682970099236538031735218462780844817175317697385659377007186785050969676938059088155922328011075081606354569621958862612850816694647002380820
xP = 11612316038801479962400723698427883310130163176291338759911281034170556609743457773032375965620429931675410389220512342834663089126659445523701533922313238
yP = 14492470559976609909614920150302533890662281539874542639808213982956316710837667114681496336361906718748053884513468343236055545337522055713141076615967243
xQ = 2609506039090139098835068603396546214836589143940493046
yQ = 8637771092812212464887027788957801177574860926032421582
xQ =716447455218443211337138354910360820310039222467099750548875601978669948877653369670984450493776038314939273990792875030477209738905138162016103972822887
yQ= 2577636835404844606086593513656242872409629115084680797009677298030035019056074660428408865132307063442440986937998752115629728860272800311376841076830297
E = EllipticCurve(GF(p), [0, 0, 0, A, B])
Qp = Qp(p, 2)
Ep = EllipticCurve(Qp, [0, 0, 0, A, B])
yPp = sqrt(Qp(xP) ** 3 + Qp(A) * Qp(xP) + Qp(B))
Pp = Ep(Qp(xP), (-yPp, yPp)[yPp[0] == yP])
yQp = sqrt(Qp(xQ) ** 3 + Qp(A) * Qp(xQ) + Qp(B))
Qp = Ep(Qp(xQ), (-yQp, yQp)[yQp[0] == yQ])
lQ = Ep.formal_group().log()(- (p * Qp)[0] // (p * Qp)[1]) / p
lP = Ep.formal_group().log()(- (p * Pp)[0] // (p * Pp)[1]) / p
e = lQ / lP
print('\n--> n: {:d}\n'.format(e[0]))
Where, P here is the Generator G , Q here is the Error point
As we have n, we can use n once more to calculate shared secret and use it as a key to decrypt the flag, one thing we noticed was the flag was in mp3 format before it was encrypted so we decrypt to an mp3 file.
Finally, the last part decryption which was done in python where we change up the encrypt script just a bit:
from Crypto.Cipher import AES
from Crypto.Util.number import inverse,bytes_to_long
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os
# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")
# The point at infinity (origin for the group law).
O = (0,0)
def decrypt(secret):
sha1 = hashlib.sha1()
sha1.update(str(secret).encode('ascii'))
key = sha1.digest()[:16]
dt = open('flag.enc','rb').read()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.decrypt(pad(dt, 16))
open('flag1.mp3','wb').write(ciphertext)
return ciphertext
def check_point(P: tuple):
if P == O:
return True
else:
return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p
def point_inverse(P: tuple):
if P == O:
return P
return Point(P.x, -P.y % p)
def point_addition(P: tuple, Q: tuple):
if P == O:
return Q
elif Q == O:
return P
elif Q == point_inverse(P):
return O
else:
if P == Q:
lam = (3*P.x**2 + a)*inverse(2*P.y, p)
lam %= p
else:
lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
lam %= p
Rx = (lam**2 - P.x - Q.x) % p
Ry = (lam*(P.x - Rx) - P.y) % p
R = Point(Rx, Ry)
assert check_point(R)
return R
def double_and_add(P: tuple, n: int):
Q = P
R = O
while n > 0:
if n % 2 == 1:
R = point_addition(R, Q)
Q = point_addition(Q, Q)
n = n // 2
assert check_point(R)
return R
def gen_shared_secret(Q: tuple, n: int):
S = double_and_add(Q, n)
return S.x
p = 19930885203825540108513916323464619607890520613882110268999315402502483992713624056070847778485065788387695567162120805830837964237496163664777233360835853
a = 16964108867870875431022511847406074513505438269132199629926447105117327702973321429130078673611996313382775579316996202239740533714013559789369433905598853
b = 2557269903904682970099236538031735218462780844817175317697385659377007186785050969676938059088155922328011075081606354569621958862612850816694647002380820
g_x = 11612316038801479962400723698427883310130163176291338759911281034170556609743457773032375965620429931675410389220512342834663089126659445523701533922313238
g_y = 14492470559976609909614920150302533890662281539874542639808213982956316710837667114681496336361906718748053884513468343236055545337522055713141076615967243
G = Point(g_x, g_y)
n = 11568228948033756316880439309350939673466728751800247616290793327983726097204440941777542891811676682980936787973145438110219254450479902147897654728360094
P = double_and_add(G, n)
key = gen_shared_secret(P, n)
decrypt(key)
This gives us a mp3 file which is a monotonous narration of the flag :V:
Flag:
HTB{37_c0m3_h0m3_d1nn3r_15_r34dy}
Nuclear Disaster
4th Crypto Challenge, to get the files for this one you have to ssh into the server, !
there you file with parameters but there is no scripts to know what the implementation of these strange numbers are:
n: 0x690ee43793bc1f34b9e44f7aeb91063d92292be0884816718ed836efeec60744d68f73c0dcebe42837a7d316dd0ab8589b461d034b0e6468e734b2b741c2ce7d50ca0e619114d758ff1973e57f843f22b0cb14af7694763a774f306c4f106616f173e2b4bdb49ef1cc2553c9dd3dc1877f7f87f106d01052faae22acfd6f3fbbfdb41be6192a0e49810a7c0874d634bcd07627e2a64f596e4356212f38628bb5416a6008e2ef0763a0da97475d7d5a1ee15842a4db54987b776f36120bf851b70c7edd197857297193c39c69d3cefe330029e57baae71f57a8fa3ffe3392855d7eca3861aa60eaabf93244b6659c9838680829eeba788dba871eedaf1f48e6ed00c1d5c12ace91edfab730d88180f2cab20beca486f73bb39ff73120a7d80c1a4bdfea3507009737977262a534a6513f4fb2db9a626f33d50a16f11098ada1d8f73043e616c298ce5bcc657120b83daa7e35263d0ff9dae602df9e00b1da0b0beacb00ee680ca890f8949f9ebd723c81eb789309a007301e6a621d431d367577
e: 0x257ae0a7b65e25b4e6de59c94259c86238666858419de8565c6bfc5ce2c7964bf013918b888341361ab61143a3848e34c8609b8eed9f44bbad6ec5c2e9c5d1fdcf79038a1fcb87aad9cae2cd885e2f42758b3ccc1efd37ebddc4462f86af68c199ae6015600077ddf6b8e2dfa5ce5b9701aebbd2d1385171c300a2823d72511f5663692b0c33c7d5ccdc9acd255a0ef7d644d94670a7af40a6829494e8a8371657b8b96618b4323030713b32c29b159ebddd7a0af42c64c63b5d92a8b8ff493b0418828206fbb5663d35d7d42d03e54b37e08f858296234d85d1eb72ad6fdff7115799c4901635cfd2ac83dda30b69fd9fbb9d1bddf38fd9c62e01776ab3c155d0e3fecefb7b9801e0cbc477b10dcd25f872c0f3172cdf05f27a17ea6d418f77bec591e1828b3830d35a3217cf59c7c384eee460579fff5d61f368bf453b142952456db7934d0063c0f46d9b5a8b35a7e7a4b211c532b7ce7ca5c09e45e241f87eaf63e0ecd35ece6275509c999415138daa6530297564e32b298ddaf62d87bf
a: 0xd05e30b62b9c8a473b7513ac2c8b372d58092733a463458f749b2db4544a868344f79312dd03c366f6855f12db68881d3c57ba857c8c4927a93e8e59569ba1c8eada720adcc818b8fb92c3e0b23ab26704d7859c16ef09c9d2692f0132295fa8a67e7936d1a7d53872c3a51e7115cb952c3ccbbfeb8d29c2f5b58ecdb799b423ebeca3725ff317682750610e5986b9c0fb385feacdbfda4082b8e820a7651e9569642d598c50050176019ade5ef446b5165b8280cf0c3f33efed0d13298aa6ab628669493d12bbbb6e80bc220b303874f0b4acd8a61319215fb44decae0c2f116e0710d3b022baeb6ee294206310e42dd51c1de91de872f1adf5c395a674cf05
g: 0x23e774b678534aca7671d71a4f87dca2274e161b1f8561ab2ad51d12333d901f054759281a8bc1f9686184b5487e8353813dc0938e1570aed83f34857744fbc5ea856687dcac06c53e3f9fc7e973cc94efb17ba85ecc00109e289b157172a0cad89ef4b6d795271e4e42aca26f0a0ee3cd71e2f561657fca7ddcb0fb45bb4d0491dca103cb5a4bfbbbf086bb58f73ae4f0fbd5fd8b2baf3606aca6937f0cd4a764be6ab44a014c6be5d2614a9de6c6548ce86588b7a3cff8e326429c9c2dcdd8595d9c5703f91c07b835721d5b59d9ba26e3f4d34f7e38a2d39602259cb024da307715f61a0c07ea4ce47eb19356109e4335820faa5b6e1f68fdcd4780c92a1c
c1: 0x48eeea8b6d8ee7b7264115858c883005b93a515db96c33329f22153b5646d771aee09fd5e34338640ddd3bb933e1eda111625f527725d3e3b8a7990560a4a50271fce090fcd1f525a9ddb5ceac20646afa5d383a84eab00c88fb6041899ebc1a6ce0b10a2fe00a7b6f7c0a23d6bb4c02237a4eaf7a8b8a748e1273a873d8b0b48526a6b96675163bd20d452050d530bd2cad6849a7087663a3aa3d11a2063716e4bd0279f1c369538d491b891301126310abb5b3b2ed1c2d4547fecd0feba29fa1a14b641e2cb5669cc6225a0f9c573ef3dd2a4b8f820afe63a639538d4dc52c1b76380ed3f6e9507c40f1a68412585acea0e5a8b5f00bfb15187ed84a65db1dba5e2c2a8234cc3acb15b354c3072e5f9e330f12aa6a323e4f98185050a161621fcaa6a0067697420c5a9509ed35724a623e36963fa80a5831d6925b2a89be18935147cfc2d390cbe39f3e44a4951f3a6c078c10d2c241c6e9a1e84188b36abee3c045d61325ba73b12c54844a2debf93d2d5374679f9aaa668278893e0ef65c
c2: 0xb9aa388ec95aa402d590ffd57ccb8cc1c741060cf4a33147ff5b030b8ab160d7475befb59a5221ab48a4567977f40ce5a60ec32ed35d21f05f3d9a3c4f0cc129f8bb71193cd14752e9b446132fca31402fc38d32b41b5cd98b8d56b03e360ab778158f2b529b95adcef7014fb7914958f73eb866232d58c06034c9050e94dd47bca4b43b7d3c9990171b68fced26ec22779a229cbd5d89b46110bfb17efcd68a6f786502a3e3e94dfac11b30108109ed331d2b3d69a70716d48420f0c1b43e954a09d1bf8a47f73360db789df6fdfc5ae360fc6d2d5952e41f1ce4def3ce2454007711c7c0fd4359c30fea7357e6ec1c5e61a42e908c0d01cb145795b44bf505
DROP US some ETH and you may prevent a nuclear disaster:
0x7b1cA37A0ad47B14e55a1E0d9d882999c0DF1Ee0
We can’t proceed forward with these numbers alone, We can’t access root as we don’t have the password, there was an hidden folder in the directory that we can access by:
cd .secrets/
There we get a script which contained the files for the source code.
The source code was a very strange implementation of RSA combined with some generator-mod a prime.
The message was implemented through a random value K which you get from g,k and n. We write out what each of these values do for a better understanding of the how they all come into play. $$ \begin{aligned} k = rand(2,a) \newline K \equiv g^k \mod a \newline c_1 \equiv k^e \mod n \newline c_2 \equiv m*K \mod a \end{aligned} $$ Now as you can see the only way to calculate K is to determine k, and the only way to get k is by using c1. We could try other methods of finding K like brute force the set if g is a small cyclic group, but as we see one of the lines prevent generation of such small groups.
As we know from number theory, $$ \begin{aligned} d \equiv e^{-1} \mod \phi \newline So, we\ can\ write, \newline k \equiv c_1^{d} \mod n \end{aligned} $$ Now, all we need to do is to find d, we can see in the code that it is generated in a strange way… and also that the e is still huge but not huge in the form of the wiener attack but something along those lines.
We quickly googled and found other big public exponent attack, notably the Variant of the wiener attack, which we found, we used this implementation to calculate d in sage:
This returns d,
d = 98099084361187641892367838720535907642384507854400227061381270492608084322671
As we have d we can calculate k with c1 equation as noted before and calculate K, then all we have to do to calculate the message: $$ m \equiv c2*K^{-1} \mod n $$ and we get the message, here’s the python script for the rest:
from Crypto.Util.number import long_to_bytes
n= 0x690ee43793bc1f34b9e44f7aeb91063d92292be0884816718ed836efeec60744d68f73c0dcebe42837a7d316dd0ab8589b461d034b0e6468e734b2b741c2ce7d50ca0e619114d758ff1973e57f843f22b0cb14af7694763a774f306c4f106616f173e2b4bdb49ef1cc2553c9dd3dc1877f7f87f106d01052faae22acfd6f3fbbfdb41be6192a0e49810a7c0874d634bcd07627e2a64f596e4356212f38628bb5416a6008e2ef0763a0da97475d7d5a1ee15842a4db54987b776f36120bf851b70c7edd197857297193c39c69d3cefe330029e57baae71f57a8fa3ffe3392855d7eca3861aa60eaabf93244b6659c9838680829eeba788dba871eedaf1f48e6ed00c1d5c12ace91edfab730d88180f2cab20beca486f73bb39ff73120a7d80c1a4bdfea3507009737977262a534a6513f4fb2db9a626f33d50a16f11098ada1d8f73043e616c298ce5bcc657120b83daa7e35263d0ff9dae602df9e00b1da0b0beacb00ee680ca890f8949f9ebd723c81eb789309a007301e6a621d431d367577
e= 0x257ae0a7b65e25b4e6de59c94259c86238666858419de8565c6bfc5ce2c7964bf013918b888341361ab61143a3848e34c8609b8eed9f44bbad6ec5c2e9c5d1fdcf79038a1fcb87aad9cae2cd885e2f42758b3ccc1efd37ebddc4462f86af68c199ae6015600077ddf6b8e2dfa5ce5b9701aebbd2d1385171c300a2823d72511f5663692b0c33c7d5ccdc9acd255a0ef7d644d94670a7af40a6829494e8a8371657b8b96618b4323030713b32c29b159ebddd7a0af42c64c63b5d92a8b8ff493b0418828206fbb5663d35d7d42d03e54b37e08f858296234d85d1eb72ad6fdff7115799c4901635cfd2ac83dda30b69fd9fbb9d1bddf38fd9c62e01776ab3c155d0e3fecefb7b9801e0cbc477b10dcd25f872c0f3172cdf05f27a17ea6d418f77bec591e1828b3830d35a3217cf59c7c384eee460579fff5d61f368bf453b142952456db7934d0063c0f46d9b5a8b35a7e7a4b211c532b7ce7ca5c09e45e241f87eaf63e0ecd35ece6275509c999415138daa6530297564e32b298ddaf62d87bf
a= 0xd05e30b62b9c8a473b7513ac2c8b372d58092733a463458f749b2db4544a868344f79312dd03c366f6855f12db68881d3c57ba857c8c4927a93e8e59569ba1c8eada720adcc818b8fb92c3e0b23ab26704d7859c16ef09c9d2692f0132295fa8a67e7936d1a7d53872c3a51e7115cb952c3ccbbfeb8d29c2f5b58ecdb799b423ebeca3725ff317682750610e5986b9c0fb385feacdbfda4082b8e820a7651e9569642d598c50050176019ade5ef446b5165b8280cf0c3f33efed0d13298aa6ab628669493d12bbbb6e80bc220b303874f0b4acd8a61319215fb44decae0c2f116e0710d3b022baeb6ee294206310e42dd51c1de91de872f1adf5c395a674cf05
g= 0x23e774b678534aca7671d71a4f87dca2274e161b1f8561ab2ad51d12333d901f054759281a8bc1f9686184b5487e8353813dc0938e1570aed83f34857744fbc5ea856687dcac06c53e3f9fc7e973cc94efb17ba85ecc00109e289b157172a0cad89ef4b6d795271e4e42aca26f0a0ee3cd71e2f561657fca7ddcb0fb45bb4d0491dca103cb5a4bfbbbf086bb58f73ae4f0fbd5fd8b2baf3606aca6937f0cd4a764be6ab44a014c6be5d2614a9de6c6548ce86588b7a3cff8e326429c9c2dcdd8595d9c5703f91c07b835721d5b59d9ba26e3f4d34f7e38a2d39602259cb024da307715f61a0c07ea4ce47eb19356109e4335820faa5b6e1f68fdcd4780c92a1c
c1= 0x48eeea8b6d8ee7b7264115858c883005b93a515db96c33329f22153b5646d771aee09fd5e34338640ddd3bb933e1eda111625f527725d3e3b8a7990560a4a50271fce090fcd1f525a9ddb5ceac20646afa5d383a84eab00c88fb6041899ebc1a6ce0b10a2fe00a7b6f7c0a23d6bb4c02237a4eaf7a8b8a748e1273a873d8b0b48526a6b96675163bd20d452050d530bd2cad6849a7087663a3aa3d11a2063716e4bd0279f1c369538d491b891301126310abb5b3b2ed1c2d4547fecd0feba29fa1a14b641e2cb5669cc6225a0f9c573ef3dd2a4b8f820afe63a639538d4dc52c1b76380ed3f6e9507c40f1a68412585acea0e5a8b5f00bfb15187ed84a65db1dba5e2c2a8234cc3acb15b354c3072e5f9e330f12aa6a323e4f98185050a161621fcaa6a0067697420c5a9509ed35724a623e36963fa80a5831d6925b2a89be18935147cfc2d390cbe39f3e44a4951f3a6c078c10d2c241c6e9a1e84188b36abee3c045d61325ba73b12c54844a2debf93d2d5374679f9aaa668278893e0ef65c
c2= 0xb9aa388ec95aa402d590ffd57ccb8cc1c741060cf4a33147ff5b030b8ab160d7475befb59a5221ab48a4567977f40ce5a60ec32ed35d21f05f3d9a3c4f0cc129f8bb71193cd14752e9b446132fca31402fc38d32b41b5cd98b8d56b03e360ab778158f2b529b95adcef7014fb7914958f73eb866232d58c06034c9050e94dd47bca4b43b7d3c9990171b68fced26ec22779a229cbd5d89b46110bfb17efcd68a6f786502a3e3e94dfac11b30108109ed331d2b3d69a70716d48420f0c1b43e954a09d1bf8a47f73360db789df6fdfc5ae360fc6d2d5952e41f1ce4def3ce2454007711c7c0fd4359c30fea7357e6ec1c5e61a42e908c0d01cb145795b44bf505
d = 98099084361187641892367838720535907642384507854400227061381270492608084322671
k = pow(c1,d,n)
K = pow(g,k,a)
Ki = pow(K,-1,a)
m = pow(c2*Ki,1,a)
print(long_to_bytes(m))
This prints :
which we assume is root password, paste that in ssh root and we get the flag.
Flag:
Buggy Time Machine
Looking at the code, it looks like a PRNG (Psuedo Random Number Generator), this type has been seen before and can be broke with Linear Congruential Equations.
This challenge is pretty straightforward compared to other crypto challenges, only slight difference being the hops, which can be solved with some basic number theory.
Regardless, we will go over it. The goal of this challenge is to enter seed in predict_year function to 2020 to get the flag.
Looking at the source, we are not given any of the values n, m, and c , the seed seems to be random, we can write it down as a congruential equation to make sense of it: $$ year_{\mathrm{n}}\equiv (year_{\mathrm{n-1}}*m+c) \mod n $$ As they are 3 unknown variables, the way to solve this would with 6 equations which we can get from the function next_year, to solve and get all the variables in the equations.
Now we can calculate the next_year if we have the initial seed or any of the other year from the function, but to get the flag we need to calculate enter a seed such that after a certain number of hops we get end up with the year 2020. We are given the number the number of hops when you net-cat to the server, and it seemed constant, so all there is left is to find a seed that will end at 2020 after several hops.
We know the equation has to end up at 2020, we can calculate the seed backwards through this method, we write this down mathematically to be clearer: $$ (year_1-c)*m^{-1}\equiv (year_{\mathrm{0}}) \mod n $$
$$ (year_2-c)*m^{-1}\equiv (year_{\mathrm{1}}) \mod n $$
$$ (year_3-c)*m^{-1}\equiv (year_{\mathrm{2}}) \mod n $$
$$ . $$
$$ . $$
$$ (2020-c)*m^{-1}\equiv (year_{\mathrm{hops}}) \mod n $$
Finally, we can code all this up this python and here’s the script:
from math import gcd
from functools import reduce
import json
import requests
states = []
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * pow(states[1] - states[0], -1,modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)
for _ in range(7):
r = requests.get("http://docker.hackthebox.eu:31044/next_year")
j = json.loads(r.text)
states.append(int(j['year']))
n, m, c = crack_unknown_modulus(states)
print(n,m,c)
s7 = (states[6]*m + c) % n
r = requests.post("http://docker.hackthebox.eu:31044/predict_year", json={'year': s7})
print(r.text)
hops = 876578
year = 2020
# inverse = modinv(m, n)
inverse = pow(m, -1, n)
for _ in range(hops):
year = (year * inverse) % n
r = requests.post("http://docker.hackthebox.eu:31044/travelTo2020", json={'seed': year})
print(r.text)
And we get the Flag
Baby Rebellion
Last Crypto Challenge, we are given 3 certificates and a challenge file. We can open the challenge file in txt and get text about the challenge:
To: "Andromeda" <andromeda@cyb.org>, "Mechi" <mechi@cyb.org>, "Corius" <corius@cyb.org>
From: "Dr Greez" <dr.greez@cyb.org>
Subject: Request for supplies
MIME-Version: 1.0
Content-Type: application/pkcs7-mime; smime-type=enveloped-data; name=smime.p7m
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename=smime.p7m
MIIFkQYJKoZIhvcNAQcDoIIFgjCCBX4CAQAxggSXMIIBggIBADBsMF8xCzAJBgNV
BAYTAlVTMQ8wDQYDVQQIDAZOZXZhZGExEDAOBgNVBAcMB1Vua25vd24xDzANBgNV
BAoMBkN5Ym9yZzEcMBoGCSqGSIb3DQEJARYNbWVjaGlAY3liLm9yZwIJAKDnC94/
ymViMAsGCSqGSIb3DQEBAQSCAQC1joK+oOelZiSpjRKr4rbcNsZ3qC0prjukGj6m
DXHjAS67O3fJNOfd7xt3Pq1/a7MVHfeIykVtiWvMo4tlD5SlrBdTo2w4ihDfXo44
J9aVufhK5RKlzuQ8eK8WNT9ODZC54vxKvSANWQ9s5THR18+y93TK6+RCyi4opCxU
w+k4O2zbxcF68lNK7DkhMxrsbukp5juwjLEFYDmo9fbjCnUbDsPcZmepU1CLr62r
6gbEHdULUFb6r0mqXN24On462glsaNIK128cKZmHRWlzceP3Fc0zv+4E767ZNhSP
nHC2ANL4DfRZ62eFhQmmzELvIkadMMnGKe+oJ8w83wvq6s9qMIIBgwIBADBtMGAx
CzAJBgNVBAYTAlVTMQ8wDQYDVQQIDAZOZXZhZGExEDAOBgNVBAcMB1Vua25vd24x
DzANBgNVBAoMBkN5Ym9yZzEdMBsGCSqGSIb3DQEJARYOY29yaXVzQGN5Yi5vcmcC
CQCp7SgGzZFINTALBgkqhkiG9w0BAQEEggEAGhBZcEHeCmYfGb4zXjip5/pEM/pf
0eyjLwXPh9fMrA6wcf7zgHhoDjevcAgmHnhSUiEEdvQNR3h7/W5Ifl2fErx6wJn4
5/G/9Zy9uqib6d9mmJs6hAMbCqPKD+tR0gncN+nsFLVHWdB1SHDb8Gys5zIY8+/V
PVg3CR7EPV8ILsp3DSa6HOoC6EU5/sD0TOaNIr3aX96CdeWC7VzAReU+3fZAxSzF
cVzWA+8yteREADjtn/+aZm/E+3xM9ElwodcdinVb0WtDqm14SzUe3Quhq6xECUH3
1q08rfLe0C/DtioBemnxFXIIGK5LuPyVjwZV4SXHZpTZ2LGHipemxMPBWDCCAYYC
AQAwcDBjMQswCQYDVQQGEwJVUzEPMA0GA1UECAwGTmV2YWRhMRAwDgYDVQQHDAdV
bmtub3duMQ8wDQYDVQQKDAZDeWJvcmcxIDAeBgkqhkiG9w0BCQEWEWFuZHJvbWVk
YUBjeWIub3JnAgkA8kWOkc0932UwCwYJKoZIhvcNAQEBBIIBAF+LTGJtPYgS30J3
UBb7XY+i+FSaA3HPeew/VzY6IyZF8l656jAOkwY/IYNeEmX0mTjAvSOIyO9JpPVr
JVNfOBZfwZ1At+WSseMRYpJzrxoOkxqhUAF4E9jRL/ON1WPr94SCg3x049zkZ2fB
ZeFJZ9njqV4AKGl23NyViW6Hi/CLuKinZ0Lu4DGEy1txpc+XBD57+2Aa/TAJJwJ8
kmRkSmrrKV24kvXS5Ns4c8OgiMPnWtGVqkWM6SZJS0EfPDZiZScGmLuMkDddgRS4
Czb5fzUnK7Vzgn6DthSKSakgqnchMOC67ikETgvX2JGjERpqy5RG+IJlkTL2Va8d
7wlJbqkwgd0GCSqGSIb3DQEHATAdBglghkgBZQMEASoEEF94VSuj0vFWgwmVP3Np
QwWAgbBJf9OIynRQt6XAKq4lCjvmCzZ7QTKBnxOc+L/GxYlUK4CqLFfQyMDV2kZL
6UGShVipeLJA8vGy9rCX+LWkpP1RKqis5SuEWixTLProB8yBgYr/apINIY8Zn/Al
uY/nvjemCyInvc7ekqs1Sl3UmsFV3Un1DGm5WvF9QKeGf2gmt9/BdTMn9FjL9kHK
CAqmVoYWiZMxBjNeUro8S2f8pyUiR5Wqfp2o8F87WSkD4HD6mQ==
As we can see, the mail seem to addressed to the three recipients and there seem to be a common message that is sent to all three of them.
We can open the three .cert files in online parser or with python modules, we used the former again for less clutter in the code and get the n and e values of the respective recipients.
We notice that the mail is in the form .p7m which is a encrypted email, and we can open the base64 encoding in an ASN.1 parser which we used again online. We used https://lapo.it/asn1js/ to parse that base64.
There seems to be an rsa ciphertext addressed to each recipient in the certificate and a AES-256 IV and data which we assume is the flag.
Calculating the common message is quite easy, we use C.R.T (Chinese Remainder Theorem) these 3 ciphertexts as they have the same message, we will write it down for clarity: $$ \begin{aligned} m\equiv c_1 \mod n_1 \\ m\equiv c_2 \mod n_2 \\ m\equiv c_3 \mod n_3 \end{aligned} $$ As they have the same message, we can use Hastad’s Brodcast Attack to calculate the message m with crt, here’s my implementation of that in sage:
This gives us the common message m that was sent to the recipients, which is just garbage bytes of data but we can use this as an AES key to get the flag, and use the last part of the ASN parser as IV and data respectively, here’s the code for the rest in python:
Which gives us a message and a flag..
Flag:
Plug
We are given a pcap file which we can look through in wireshark.
After snooping around a big you find a packet with PNG header which can be found easily by arranging the packets by length.
We copy the hex stream and write it to a png file, here’s the script for that in python:
p = '89504e470d0a1a0a0000000d49484452000000c8000000c80806000000ad58ae9e0000078d49444154789ced9941922c290cc5fafe979e59f78f804cdcd8298314c1d2f0ecb436553fff89c8909faf038890511091090a2232414144262888c804051199a02022131444648282884c501091090a22326159909f9f9ff6273cac843babb364d47539a1392f17001a5510055110d8a09e7aaf4641140435a8a7deab511005410deaa9f76a14444150837aeabd1a055110d4a09e7aaf46411a0a42a27a1132eeecd2030905794997e522bd9731cf6a14e4255d968bf45ec63cab51909774592ed27b19f3ac46415ed265b948ef65ccb31a05794997e522bd9731cf6a14e4255d968bf45ec63cab692b086949a254f740ca72eb7757904dbd2b48ef9cc3fb960b2e1dd4173d90b2dcfadd156453ef0ad23be7f0bee5824b07f5450fa42cb77e7705d9d4bb82f4ce39bc6fb9e0d2417dd10329cbaddf5d4136e5acce72420fa49cc3fb960b0e1f54972c27f440ca39bc6fb9e0f04175c972420fa49cc3fb960b0e1f54972c27f440ca39bc6fb9e0f04175c972420fa49cc3fb960b0e1f54972c27f440ca39bc6fb9e0f04175c972420fa49cc3fb960b2e1dd413a4b990e6d925e7f0bee5824b07f504692ea47976c939bc6fb9e0d2413d419a0b699e5d720eef5b2eb874504f90e6429a67979cc3fb960b2e1dd413a4b990e6d925e7f0bee5824b07f504692ea47976c939bc6fb9e0d2413d419a0b699e5d720eef5b2e285ebc28a445a8a6c3e265a1202f5110055190090aa2200a3241411444412628888228c8040551100599a0200a8213a4cbc918f0cd755d4e040559e8cfbade2782822cf4675def13414116fab3aef789a0200bfd59d7fb44509085feaceb7d2228c8427fd6f53e11583f625fc8ee0f4a7baf3b4ee56314848d53f9180561e3543e4641d838958f5110364ee56314848d53f9180561d3fa7f90d37356d791b264d445501070ceea3a52968cba080a02ce595d47ca9251174141c039abeb485932ea2228083867751d294b465d040501e7acae2365c9a88ba020e09cd575a42c197511b60a12adeb32e0ca0ff3f41e49f28cfe28772a888228c8ecbeaa000ab2ced752288882288882ccefab0aa020eb7c2d858228888228c8fcbeaa000ab2ced7522848409028d51fad8b90a4737aef1114e4b225b9b9f7080a72d992dcdc7b0405b96c496eee3d82825cb62437f71e41412e5b929b7b8fa020972dc9cdbd47d82ac8ee705fbcd7e1a3fda5f7ea9cd52848f27b0aa220bfee2387fbe23d0551905ff791c37df19e8228c8affbc8e1be784f4114e4d77de4705fbca7200af2eb3e72b82fde531005f9755f5580ea0f4a5aa06ae94839a350b228c8a6f7aa7be892330a258b826c7aafba872e39a350b228c8a6f7aa7be892330a258b826c7aafba872e39a350b228c8a6f7aa7be892330a258b826c7aafba872e39a350b2e0052165a95eca8c2cd587d443040551100599655c2e501005519058531975a42c0aa220cf050aa2200a126b2aa38e94454114e4b94041144441624d55d7913e6806a49ca4592bc8cb3ad247cb809493346b05795947fa681990729266ad202feb481f2d03524ed2ac15e4651de9a36540ca499ab582bcac237db40c483949b356909775a48f9601292769d6470a12bdb37a29bbe4ac5ebc2e2888823c66e9d243060aa2208f59baf490818228c863962e3d64a0200af298a54b0f192888823c66e9d243060aa2208f59baf490c191826490b140a767211d0a0ab2a9ee842ca443414136d59d9085742828c8a6ba13b2900e0505d954774216d2a1a0209bea4ec8423a14146453dd09594887022709848c0fda65d133a8ceb9bb3f05f9870e1fed2f391564317fa8ea603a7cb4bfe45490c5fca1aa83e9f0d1fe92534116f387aa0ea6c347fb4b4e0559cc1faa3a980e1fed2f391564317fa8ea603a7cb4bfe45490c5fc8486ab4f467f51be9e45f6e29166167aab2a1ce950864f9b673467465dc6cc426f5585231dcaf069f38ce6cca8cb9859e8adaa70a443193e6d9ed19c197519330bbd55158e7428c3a7cd339a33a32e6366a1b7aac2910e65f8b479467366d465cc2cf4565538d2a10c9f36cf68ce8cba8c9985deda198e44754e92581975d539292848c17b0ac2df97110a52f09e82f0f765848214bca720fc7d19a12005ef29087f5f462848c17b0ac2df97110a52f09e82f0f765449920d105aa5e849b73920e05053127f250501073220f05053127f250501073220f05053127f250501073220f0505f9b8bf28d5cb45fa7e95b356908ffb8ba2200aa220093933de539097c1490d93ea1484bf2fc31c3b07456a9854a720fc7d19e6d8392852c3a43a05e1efcb30c7ce41911a26d529087f5f8639760e8ad4f0cd7594e57a82f4dd87f7ed6c2a5a471ad409750aa220ad16b6ba4e4114a4d5c256d7298882b45ad8ea3a055190560b5b5da7200ad26a61abeb14a4a120d59cbe78d5394f984be8beaf0364a120bd4fc65c42f77d1d200b05e97d32e612baefeb00592848ef933197d07d5f07c842417a9f8cb984eefb3a40160ad2fb64cc2574dfd701b25090de27632ea1fb7606e87232fa8b9291f3f42c95df484136f517a5cb5292b2288882e096929445411404b794a42c0aa220b8a52465511005c12d25298b8228086e294959d08288dc8482884c501091090a2232414144262888c804051199a02022131444648282884c501091090a223241414426fc0ff1b2c0879d39a3b20000000049454e44ae42608200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
p = bytes.fromhex(p)
open('flag1.png','wb').write(p)
Which turns out to be a QR code. We then use QR code scanner to get the flag.
Flag:
HTB FINALS writeups
Locked Out
We are given encryption.py , new_password and leaks. Where, new_password is the cipher-text and leaks is the public-exponents also some additional information. Let’s look at the python source :
from Crypto.Util.number import *
from random import getrandbits
import random
import gmpy2
bits=1024
def generate_prime(bits):
m = 2
while True:
a= getrandbits(bits)
a = a**m
prime = None
r = None
for i in range(2*a):
if gmpy2.is_prime(a +i):
prime = a +i
r = i
break
if prime is None: continue
return prime, r
p, rp = generate_prime(512)
q, rq = generate_prime(512)
n = p * q
e = 65537
msg = sys.argv[1].encode()
msg = bytes_to_long(msg)
ct = hex(pow(msg, e,n))
f = open('new_password', 'w')
f.write(ct)
f.close()
f = open('leaks', 'w')
f.write(str({'n':n, 'rp':rp, 'rq':rq}))
f.close()
We see that generate_prime(bits) is a prime number generator, but it is quite evident that the method is weak from the way it is generated, let’s look at the function closely..
We see that some random 512 bits number was generated which is squared and is added to some number. This addition is done until a prime is found. After which, the prime and number added to it is returned, lets write this down mathematically. $$ \begin{aligned} p = a^{2}+r_p \newline q=b^{2}+r_q \end{aligned} $$ These primes are then multiplied then the rest is standard RSA procedure.. But lets look at the primes once again, my first thought looking at this was writing N as product in that form, I shall write it out
$$ N=p*q $$
$$ N=(a^{2}+r_p)*(b^{2}+r_q) $$
this implies
$$ \text{N}=a^{2}\times b^{2}+a^{2}*r _ q+b^{2}\times r _ p+r _ p\times r _ q $$
$$ \text{N}-r _ p\times r _ q=a^{2}\times b^{2}+a^{2}\times r _ q+b^{2}\times r _ p $$
My intuition here was was solving this in form of a polynomial and taking the roots, but the a^2*b^2 was the annoying part, which got me stumped, but i googled for something similar perhaps to find prime generators that can be solved this way, which got me a hit for this https://einspem.upm.edu.my/journal/fullpaper/vol13saugust/8.pdf . This paper essentially solves these sort of prime generators but i would like to discuss more maths of this paper as i previously stated my intuition for this challenge was somewhere on the right track…
What the next step after subtracting it from big N was taking the modulus so that a^2*b^2 gets removed, as we then would be able to solve for equation and get the roots for it. Let’s write this out
$$ (N-rp\times rq)\equiv(a^{2}\times r_q+b^{2}\times r_p)\mod{a^{2}\times b^{2}} $$
We know,
$$ x^{2}+(a+b)x+ab=0$$
$$ x^{2}+(a+b)x+ab=0 $$
$$ Similarly,\ we \ write \ down, $$
$$ x^{2}+(a^{2}\times r _ q+b^{2}*r _ p)*x+a^{2}\times r _ p\times b^{2}\times r _ q=0\ $$
$$roots\ of \ this \ equation \ are,$$
$$ (x+a^{2}\times r_q)\times (x+b^{2}\times r_p)=0 $$
$$ i.e, $$
$$ x_1=a^{2}\times r_q \ \ and\ \ x_2=b^{2}\times r_p $$
$$ p=\frac{x_1}{r_q}+r_p $$
$$ q=\frac{x_2}{r_p}+r_q $$
Which gives us the prime factors of N, depending on the roots of the equation, these roots if they are an integer will be a factor of N, But this question is how do we take modulus a^2*b^2 if we don’t know a and b, the answer to this is BRUTE-FORCE, yes, as explained by the paper we take the square root of N and rp*rq, then iterate till the only factor that is left is a^2*b^2, let’s write this down again:
$$(\sqrt N-x)^2=a^2*b^2$$
$$ where,\ x \simeq \sqrt{(rp\times rq)}-\sqrt{(a^{2}\times rq+b^{2} \times rp)} $$
This is my understanding of the maths behind the algorithm, we can just refer to page 7 of the above paper and look for factors in the similar way, here is my implementation of the algorithm in sage:
rp = 228
rq = 75
N = 18627060853366003817633498319725128072935605420672144028180887821598995058566763870406708181052681986936527075954895204088200290386963730876047423903233595643471077586653831691013827267874620159258094222853259785361633293190228850242828942973252729075142510154777682987087560910570468443515976133521357279350135180187709921165306439775516983770374718903851808402718506713073936579721447055524042778187890314247383276126544626388594005451861656297486009721524593236438272682590796161812616558556489424502887789415628561091674949871825109470840186278129161368348123380425008804948098905894644488816022732318170994842927
i = floor(sqrt(rp*rq))
while i<floor(rq/2+rp+1):
sig = (ceil(sqrt(N))-i)**2
z = (N - rp*rq)%sig
i+=1
R = PolynomialRing( ZZ,'x')
x = R.gen()
f = x^2 - z * x + rp*rq*sig
a = f.roots()
if a ==[]:
continue
else:
x1 = f.roots()[0][0]
x2 = f.roots()[0][1]
if (gcd(N,x1/rp+rq)!=1 or gcd(N,x2/rq+rp)!=1) and ((x1/rp+rq) in ZZ or (x2/rq+rp) in ZZ) :
print(gcd(N,x1/rp+rq)) #123880731118078606990137525967538331116275498654165135288667481763468359990787854975994876893087359471477116036463781441086420155388498641200190619570949282848164235074476184966442200869534040008670271367209107524675332904145907801965290873060668160752216813566725872730131480362642158718779920761925401528651
print(gcd(N,x2/rq+rp)) # 1/75
break
else:
continue
Rest is pretty much textbook RSA using the ciphertext from new_password, I shall leave my code for that and the output for it
from Crypto.Util.number import long_to_bytes
N = 18627060853366003817633498319725128072935605420672144028180887821598995058566763870406708181052681986936527075954895204088200290386963730876047423903233595643471077586653831691013827267874620159258094222853259785361633293190228850242828942973252729075142510154777682987087560910570468443515976133521357279350135180187709921165306439775516983770374718903851808402718506713073936579721447055524042778187890314247383276126544626388594005451861656297486009721524593236438272682590796161812616558556489424502887789415628561091674949871825109470840186278129161368348123380425008804948098905894644488816022732318170994842927
p = 123880731118078606990137525967538331116275498654165135288667481763468359990787854975994876893087359471477116036463781441086420155388498641200190619570949282848164235074476184966442200869534040008670271367209107524675332904145907801965290873060668160752216813566725872730131480362642158718779920761925401528651
q = N//p
c = 0x15f8468e603cfe7eca368ebf666b98d918686148336e2ffae048dc7dc7d4a399b1c6bff22140a79628c6a66e8d85fcc2d39505f15ec77295d373091c56a57de9472adf673d56307fa7fd2c7a3e2dc2d57c9380a5d332aa4c3592c08da22aa82667ebe7536a104e814c3f06dff9632f26fff3e52c711416abded102fa5377fce6dadcad3ac4d6197da69002817d00d3f765e71d73070fe1d5b1d8f1bf9a148ea026371c2d19debe317d96e9f1911f07286f90b8d9f9ff35d6b886f2f9b171b112f27e96c199e6f70501b282475c5ade73abe1c6bf39aada6507ab080aeccd11942171d83a28fb9c5aaeb7b40cf0a628946d6d46c40534e2fd3d65bf6e718435ce
e = 65537
d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))
which prints, b'The password is 4p7gr0p0w3ndU'
Right, so the challenge description had a docker link, which takes us to a website, where you can login, we can assume this is the password for admin, let’s this out
Entering that as the password, we get the flag:
