Tags: polynomial discrete-log crypto
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`.
Use the following resource to understand about this
[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 `group`of `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 then`ecdsa` 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()
if message == b'please_give_me_the_flag':
print("\n\t:Coughs: This ain't that easy as Verifier1")
sys.exit()
secret_mask = int(input("Now insert a really stupid value here: "))
secret = secret_multiplier ^ secret_mask
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: "))
if verifyingKey.verify(signature, b'please_give_me_the_flag'):
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: "))
secret = secret_multiplier ^ secret_mask
```
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}
