Tags: polynomial cryptography-rsa

Rating:

# Inctfi 2020 Writeups

- Crypto
- [PolyRSA](#polyrsa)
- [DLPoly](#dlpoly)
- [bakflip&sons](#bakflip)
- [EaCy](#Eacy)

---

# PolyRSA Challenge Writeup [Crypto]

For this challenge we were given a single file [out.txt](/Inctfi-2020/PolyRSA/out.txt) which contains commands used in sage interactive shell and there output.

In the out.txt file we have, three values

- p = 2470567871 (a prime number)
- n = ... (a 255 degree polynomial)
- c = m ^ 65537 (also a polynomial)

These parameters constitute the RSA Encryption but instead of Group of numbers modulo n, this
uses univariate polynomials over the finite field Zp.

[Polynomial based RSA](http://www.diva-portal.se/smash/get/diva2:823505/FULLTEXT01.pdf)

As in integer group, we have to find the multiplicative order of the group formed by residue polynomials of given n.

Above resource specifies the formula in page 14 as

s = (p**d1 - 1) * (p**d2 - 1) where d1 and d2 are the degrees of irreducible polynomials constituing the given modulus(n).

After obtaining s (multiplicative order), finding the inverse of e = 65537 and raising the ct polynomial to the inverse gives the message polynomial.

Converting the coefficients of message polynomial gives us the flag.

python
q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]
s = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, s) == 1
d = inverse_mod(e, s)
m = pow(c, d, n)
flag = bytes(m.coefficients())

solution code :: [solve.sage](/Inctfi-2020/PolyRSA/solve.sage)

Flag :: inctf{and_i_4m_ir0n_m4n}

---

# DLPoly challenge writeup [Crypto]

Got second blood for this challenge.
This challenge is similar to above challenge. we were given [out.txt](/Inctfi-2020/DLPoly/out.txt) file which contains the commands and output in sage interactive shell.

In the out.txt file we have,
- p = 35201
- n (a 256 degree polynomial with coefficients in Zmod(p))
- len(flag) = 14
- g = x (a 1 degree polynomial)
- X = int.from_bytes(flag.strip(b'inctf{').strip(b'}') , 'big')
- g ^ X

In order to get the flag, we have to solve the discrete logarithm in the groupof residues(polynomial) modulo n with coefficients in Zmod(p)(Zp[x]).

Use the resource mentioned in [PolyRSA](#polyrsa) writeup for a better understanding.

factoring n and finding the order
python
nfactors = n.factor()
s = 1
for i in nfactors:
s *= p**(i[0].degree()) - 1

factoring the order(s) shows that s has many small factors.
python
2^208 * 3^27 * 5^77 * 7^2 * 11^26 * 13 * 31^25 * 41^25 * 241 * 271 * 1291^25 * 5867^26 * 6781^25 * 18973 * 648391 * 62904731^25 * 595306331^25 * 1131568001^25


As the order contains small factors, we can use pohlig hellman algorithm to find discrete logarithm.

we have to select the factors carefully as raising base element (g) to many of the factors gives the identity element (1) which we cannot use.

So, taking the following factors
python
[7^2, 13, 241, 271, 18973, 648391]

we can calculate the value of flag(X) modulo prod([7^2, 13, 241, 271, 18973, 648391]) using CRT.

Value obtained is the correct value of the flag as the X is less than 2**(7*8) i.e X is 7 bytes long.

quick and ugly implementation of pohlig hellman ::
python
def brute_dlp(gi, ci, n, lim):
bi = gi
for i in range(1, lim+1):
if bi == ci:
return i
bi = (bi * gi) % n
print("[-] NOT in the range")
print("[-] Something's Wrong, you gotta check the range", lim)

def pohlig_hellman(g, c, s, n, factors):
res = []
modulus = []
for q, e in factors:
assert pow(g, s//(q**e), n) != 1
gi = pow(g, s//(q**e), n)
ci = pow(c, s//(q**e), n)
dlogi = brute_dlp(gi, ci, n, q**e)
print("[+] dlog modulo {0} == {1}".format(q**e, dlogi))
res.append(dlogi)
modulus.append(q**e)
print("\n[*] res = ", res)
print("[*] modulus = ", modulus)
dlog = CRT(res, modulus)
print("\n[+] dlog modulo {0} == {1}".format(prod(modulus), dlog))
return dlog


solution code :: [solve.sage](Inctfi-2020/DLPoly/solve.sage)

Flag :: inctf{bingo!}

---

# Bakflip&sons challenge Writeup [Crypto]

This challenge runs the [challenge.py](/Inctfi-2020/Bakflip_n_sons/challenge.py) on the server.

It provides two functionalities signMessage and getFlag.

signMessage signs the given message using thenecdsa with NIST198p elliptic curve.

getFlag gives us the flag if we can provide the ecdsa signature of message please_give_me_the_flag.

python
def signMessage():
print("""
Sign Message Service - courtsy of bakflip&sons
""")
message = input("Enter a message to sign: ").encode()
print("\n\t:Coughs: This ain't that easy as Verifier1")
sys.exit()
secret_mask = int(input("Now insert a really stupid value here: "))
signingKey = SigningKey.from_secret_exponent(secret)
signature = signingKey.sign(message)
print("Signature: ", hexlify(signature).decode())

def getFlag():
print("""
BeetleBountyProgram - by bakflip&sons

Wanted! Patched or Alive- \$200,000
Submit a valid signature for 'please_give_me_the_flag' and claim the flag
""")
signingKey = SigningKey.from_secret_exponent(secret_multiplier)
verifyingKey = signingKey.verifying_key
try:
signature = unhexlify(input("Forged Signature: "))
print(flag)
except:
print("Phew! that was close")


As we can see in the signMessage function declaration, it doesn't allow us to obtain signature of our target message.

At the start of execution, challenge.py generates secret key with 101 bit_length
python
secret_multiplier = random.getrandbits(101)

In order to forge the signature, we have to calculate the secret key, we won't be able to solve the
ecdlp but we can use the additional secret mask requested in signMessage function.
python
secret_mask = int(input("Now insert a really stupid value here: "))

so, we can modify the secret key used for signing.
we can use this to completely obtain the secret key in a few iterations.

Let G be the generator
s1 is the secret_key
s2 is the secret_key ^ mask (^ --> xor operation)
P = s1 * G
Q = s2 * G
suppose if the mask is 1
s2 = s1 ^ 1 , (xor with 1 flips the lsb)
if lsb of s1 is 0 then s2 = s1 + 1 => Q = s2 * G = (s1 + 1) * G = P + G
else if lsb of s1 is 1 then s2 = s1 - 1 => Q = s2 * G = (s1 - 1) * G = P - G

Given the points P, Q we can obtain the lsb of secret_key s1
by checking
if Q == P + G then lsb of secret key is 0
else Q == P - G then lsb of secret key is 1

similarly we can set the nth(lsb is 0 bit) lower bit in the mask i.e mask = (1 << n)
flipping the nth lower bit,
decreases or increases the secret_key(s1) by 2**n based on whether nth bit in secret_key is set or not
so, checking if Q == P + (2**n) * G or Q == P - (2**n) * G gives the nth bit


Using the above method recursively gives the complete secret key and we can use that to forge the
required signature.

There are small hurdles in the challenge
1. Only signature is given, we have to calculate the Public Key (P).
2. We have only 73 iterations, we have to calculate the 101 bit key using less than 72 iterations.

For the first problem, we can use the signature (r,s) to obtain the Public Key, two valid Public Keys are possible for a given signature pair (r, s).

we have to use other Public Keys to identify the correct key.

For the second problem, we can extend the same theory for any number of bits with bruteforceable number of cases.

example of 2 bits.
python
secret_key_lsb =>
00 --> Q = P + 3*G
01 --> Q = P + G
10 --> Q = P - G
11 --> Q = P - 3*G

Using the above approach with 2 bits, we can calculate secret_key using less than 72 iterations and get the flag.

There are a lot of small implementation details, check out my solution code :: [solve.sage](/Inctfi-2020/Bakflip_n_sons/solve.sage)

FLAG :: inctf{i_see_bitflip_i_see_family}

---

# EaCy challenge writeup [Crypto]

Luckily I got First Blood for this challenge.

we were given four files
1. [ecc.py](/Inctfi-2020/EaCy/ecc.py) contains classes to work with elliptic curves
2. [ansi931.py](/Inctfi-2020/EaCy/ansi931.py) contains classes to generate random data using ANSI X9.31 with AES 128
3. [prng.py](/Inctfi-2020/EaCy/prng.py) contains implementation of dual_ec_drbg random generator along with prng using ANSI X9.31
4. [encrypt.py](/Inctfi-2020/EaCy/encrypt.py)

The basic flow of service is as follows
- Generates a random number e using the prng defined in prng.py.
- Asks to choose between [1] Asynchronous SchnorrID and [2] Synchronous SchnorrID.
- Asks the user for two Points Q, R.
- Gives the value of e to the user if 1 is selected (Asynchronous SchnorrID)
- User has to provide value of s such that s*P == e*Q + R, P is an hard coded point
- if the above condition fails then it closes the connection
- if we can provide the correct s without the e value i.e in Synchronous SchnorrID, we can request the flag

service repeats the above process for 10 times.

if we have e value, we can pass the condition by sending point P for both Q and R values and (e + 1) value.

s*P = (e + 1) * P = e*P + P = e*Q + R

so, if we know the value of e we can easily pass the condition, in order to get the flag we have to
calculate the s value without taking e from the service.

Only way is to crack the prng used
python
def prng_reseed(self):
self.prng_temporary = long_to_bytes(self.ecprng_obj.ec_generate())
assert len(self.prng_temporary) == 32
self.prng_seed = self.prng_temporary[:8]
prng.prng_output_index = 8
self.prng_key = self.prng_temporary[8:]
prng.prng_output_index = 32
return bytes_to_long(self.prng_temporary)

def prng_generate(self):
_time = time.time()
prng.prng_output_index = 0
if not self.one_state_rng:
print("prng_reseed ", self.prng_reseed())

ansi_obj = ANSI(self.prng_seed + self.prng_key + long_to_bytes(_time).rjust(16, "\x00"))
while prng.prng_output_index <= 0x1f:
self.prng_temporary += ANSI.get(8)
prng.prng_output_index += 8
print("prng generate = ", bytes_to_long(self.prng_temporary))
return bytes_to_long(self.prng_temporary)

At the first glance, it may seem like the prng is using ANSI class to generate random data but in the settings used by the challenge, prng directly gives the random_data generated by dual_ec_drbg.
python
class ecprng:
# Curve P-256; source: https://safecurves.cr.yp.to/
p = 2**256 - 2**224 + 2**192 + 2**96 - 1
a = p-3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
ec = ecc.CurveFp(p, a, b)

_Px = 115113149114637566422228202471255745041343462839792246702200996638778690567225
_Py = 88701990415124583444630570378020746694390711248186320283617457322869078545663
Point_P = ecc.Point(ec, _Px, _Py)

_Qx = 75498749949015782244392151836890161743686522667385613237212787867797557116642
_Qy = 19586975827802643945708711597046872561784179836880328844627665993398229124361
Point_Q = ecc.Point(ec, _Qx, _Qy)

def __init__(self, seed):
self.seed = seed
if self.seed:
assert len(long_to_bytes(self.seed)) == 32

def update_seed(self, intermediate_state_S_1):
self.seed = (intermediate_state_S_1 * ecprng.Point_P).x()
assert len(long_to_bytes(self.seed)) == 32

def ec_generate(self):
intermediate_state_S_1 = (self.seed * ecprng.Point_P).x()
self.update_seed(intermediate_state_S_1)
r_1 = long_to_bytes((intermediate_state_S_1 * ecprng.Point_Q).x())[-30:]
r_2 = long_to_bytes((self.seed * ecprng.Point_Q).x())[-30:][:2]
assert len(r_1 + r_2) == 32
print("seed == ", self.seed)
return bytes_to_long(r_1 + r_2)

so, random_number e is generated using dual_ec_drbg with P-256 curve.

we can predict the next state of the generator if author has inserted a backdoor into the generator.

See the video from David Wong for an excellent explanation about the backdoor [link](https://www.youtube.com/watch?v=OkiVN6z60lg).

so, generator state consists of two points and seed.

To generate a random number
- s1 = (seed * P).x()
- random_number = (s1 * Q).x() & ((1 << 240) - 1) ; (lower 240 bits)
- seed = (s1 * P).x()

generator follows this above procedure to calculate a single random number.

One who decides the points P and Q has the ability to insert a backdoor into the generator which will allow him to predict the future states of generator given a single random number
generated and little other information.

The way one can do it is,


if Q = c * P (c can be any number)
given random_number = (s1 * Q).x()
lifting the random_number gives the value of (s1 * Q)
multiplying the value of (s1 * Q) with the inverse(c, order) and take the x co-ordinate of the result gives the seed.


cinv * (s1 * Q) = cinv * s1 * c * P = s1 * P = seed

After obtaining the seed, one can generate all the future states.

There are little changes in the implementation of dual_ec_drbg in this challenge.

For the points used in this challenge, Q = 1735 * P.

backdoor exists in this generator.

Normally, top 16 bits of the random number i.e (s1 * Q).x() are removed, we have to use another random number to filter out the wrong ones but in this challenge we are given with additional information in the form of r2, we can use that to filter.

So, we only need single e, after that we can predict all the future states.

Final solution is
- obtain a value of e by selecting the 1 option(Asynchronous SchnorrID)
- bruteforce the top 16 bits and find the seed
- select option 2, predict the value of e, pass the check using above mentioned method
- get the flag

solution code :: [solve.sage](/Inctfi-2020/EaCy/solve.sage)

FLAG :: inctf{Ev3ry_wa11_1s_4_d00r_but_7his_1s_4_D0ubl3_d0or}

Original writeup (https://github.com/S3v3ru5/CTF-writeups/tree/master/Inctfi-2020#polyrsa).