Bro do you even Lift - Teaser CONFidence CTF 2019

tl;dr

1. Find roots in a polynomial ring over $ mod;p $
2. Use Hensel’s Lifting lemma to find roots over $ mod;p^k $

Challenge Points: 85
Challenge Solves:
Solved by: v4d3r, s0rc3r3r, v3ct0r, 4lph4

Preliminary Analysis

This challenge was based on a 4th degree Univariate Polynomial Ring. We are provided with lift.sage and
outputs.txt. In lift.sage we have:

flag = int(open('flag.txt','r').read().encode("hex"),16)
ranges = int(log(flag,2))
p = next_prime(ZZ.random_element(2^15, 2^16))
k = 100
N = p^k
d = 5
P. = PolynomialRing(Zmod(N), implementation='NTL')
pol = 0
for c in range(d):
    pol += ZZ.random_element(2^ranges, 2^(ranges+1))*x^c
remainder = pol(flag)
pol = pol - remainder
assert pol(flag) == 0

print(p)
print(pol)

Contents of outputs.txt are:

35671

12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

It is clear from the above snippet that the flag is a root of the following polynomial:
$ ax^4 + bx^3 + cx^2 + dx + e = 0;(mod;N) $
where $ N = p^{100} $; $ p = 35671 $

Thus, the challenge was to find the root of this polynomial!

To solve this challenge, we can first find a solution for the given polynomial over $ mod;p $ and then use
Hensel’s lifting lemma to find a solution for the given polynomial over $ mod;p^k = mod; N $. Hensel’s lifting
lemma states that:

If a polynomial equation has a simple root modulo a prime number p, then this root corresponds to a unique root of the same equation modulo any higher power of p, which can be found by iteratively “lifting” the solution modulo successive powers of p.

Step-1: Finding roots over $ mod;p $

p = 35671
k = 100
P. = PolynomialRing(Zmod(p), implementation='NTL')
f = 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
print f.monic().roots()

Cool! This python/sagemath script returned the base solutions as [27020, 25020]

Step-2: Use Hensel’s lifting to find roots over $ mod;N $

We primarily used p4’s Hensel’s lifting implementation in their library crypto-commons. v4d3r tweaked it to
make it compatible with sagemath.

from sage.all import *
from Crypto.Util.number import *

def lift(f, p, k, previous):
    result = []
    df = diff(f)
    for lower_solution in previous:
        dfr = Integer(df(lower_solution))
        fr = Integer(f(lower_solution))
        if dfr % p != 0:
            t = (-(xgcd(dfr, p)[1]) * int(fr / p ** (k - 1))) % p
            result.append(lower_solution + t * p ** (k - 1))
        if dfr % p == 0:
            if fr % p ** k == 0:
                for t in range(0, p):
                    result.append(lower_solution + t * p ** (k - 1))
    return result

def hensel_lifting(f, p, k, base_solution):
    solution = base_solution
    for i in range(2, k + 1):
        solution = lift(f, p, i, solution)
    return solution

if __name__=="__main__":
    #base = [27020,25020]
    base = [27020]
    p = 35671
    k = 100
    N = p^k
    P. = PolynomialRing(Zmod(N), implementation='NTL')
    f = 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
    solutions = hensel_lifting(f,p,k,base)
    for solution in solutions:
        print long_to_bytes(solution)

Running the above script gave the flag as:
p4{Th4t5_50m3_h34vy_l1ft1n9}