ASIS 2022 - Mariana

Find 40 discrete logarithm fixed points to solve the challenge. The range check allows to solve the equation with the Chinese remainder theorem with a negative value.

Description

Mariana works in the areas of cryptography and security. But some flaws exists in her work!

nc 65.21.255.31 32066

Details

Points: 107

Category: Cryptography

Validations: 41

Solution

The script is asking 40 times for a discrete logarithm fixed point:

\[g^x = x \mod p\]

With $p$ being from 32 to 1280 bit long and $x$ being less than $p$. For the latest steps a solution involving the computation of a discrete logartihm will not be feasible. The title would indicate to look at the work of Mariana Levin et. al about discrete logarithm fixed point. However the paper proves that the solution exists but without any construction method. However in the paper there is a note saying: “Note that if x is not restricted to the interval [1, p − 1] it is easy to find fixed points. In our challenge, $x$ is limited to $p-1$ but in the code there is not limit to have a negative value.

The idea is the following, we are looking for a value of $x$ such that:

\[x \equiv 1 \mod p-1\] \[x \equiv g \mod p\]

If so, we have the correct relation: $g^x = x \mod p$ and we must have $x < p$. The chinese remainder theorem (CRT) would give us a positive solution for the previous system modulo $p(p-1)$. It would be rejected by the server. But if we substract $p(p-1)$ to the result of the CRT it would give a negative value still correct.

The final script to automatized the 40 answers is the following:

from sage.all import crt

import telnetlib

HOST = "65.21.255.31"

tn = telnetlib.Telnet(HOST, 32066)

# header
rsp = tn.read_until(b"for x.   |")
print(rsp.decode())

rsp = tn.read_until(b"\n")
print(rsp.decode())

while True:
    # p
    rsp = tn.read_until(b"\n")
    print(rsp.decode())
    exec(rsp.decode()[2:])

    # q 
    rsp = tn.read_until(b"\n")
    print(rsp.decode())
    exec(rsp.decode()[2:])

    rsp = tn.read_until(b"\n")
    print(rsp.decode())

    # CRT computation
    c = crt(1, g, p-1 , p) - p*(p-1)
    cmd = c.str().encode() + b"\n"

    tn.write(cmd)
    rsp = tn.read_until(b"\n")
    print(rsp.decode())

Which outputs the flag at the end:

$ solve.py
...
| Send the solution x = 
| Good job, try to solve the next level!
| p = 20060495634641923934290910042037415012965887049052082629378025578414094494317215752767229350560283637103129215245317866638158420602603765621357973975183610617486899951596907899625713829777825949642703336180486781294253558726793130837911364800464374046475660950482374585595881510361204635257734100278453594013796369208483140492740252211847837041081103872047376210156835506562419282005437
| g = 17128259023814750660220796259279795284170791486181711721648128733352156118458053198349603022545160428373749952344831733972901484222895150307930656564833027330762184748955605601775393310165180985683423720111484225049593443086585390492386320039883895157118956582795555111005609439268957878324133121128287666829754348637646678267889542533643145760727682471761594848292230791667831264374169
| Send the solution x = 
| Congratz! the flag is: ASIS{fiX3d_pOIn7s_f0r_d!5Cret3_l0g4riThmS!}

Written on October 1, 2022