«

»

Oct
02

TUM CTF 2016 – Tacos (Crypto 400)

All my fine arts and philosophy student friends claim discrete logarithms are hard. Prove them wrong.

nc 104.198.63.175 1729

vuln_tacos.py

Summary: bypassing Fermat primality test with Carmichael numbers and solving discrete logarithm using Pohlig-Hellman algorithm.

The source code is quite simple:

def is_prime(n):
    for _ in range(42):
        if pow(random.randrange(1, n), n - 1, n) != 1:
            return False
    return True
 
q, p = int(input(), 0), int(input(), 0)
 
assert 2 ** 1024 < p < q < 2 ** 4096
assert is_prime(q)
assert not (q - 1) % p
assert is_prime(p)
 
g = random.randrange(1, q)
y = pow(g, random.randrange(q - 1), q)
print(hex(g), hex(y))
signal.alarm(60)
 
# good luck!
if pow(g, int(input(), 0), q) == y:
    print(open('flag.txt').read().strip())

We need to supply a large prime modulo $q$ with large multiplicative subgroup of order $p$. And then the server will ask us to perform a discrete logarithm in this group. There are no known algorithms for such setting. However, here we can bypass some conditions – the primality test. is_prime uses Fermat test to check for primality. It is well known that Carmichael numbers bypass such test easily. Note that Carmichael numbers do not bypass Fermat test in 100% of cases! They bypass if only when witness (base) is coprime with $p$, otherwise the base yields a divisor of $p$. Nonetheless, for non-Carmichael and non-prime numbers Fermat test declines composite numbers with much higher probability, therefore Carmichael numbers are our only hope here.

Bypassing primality test

Assume that we can generate Carmichael numbers of ~3000 bits with lots of small prime factors. There are two paths here:

  • Generate Carmichael $q$ (false prime) until we can find a large real prime factor $p$ of $q-1$. In such case we will be able to do discrete log modulo each prime factor of $q$ and then combine them using CRT.
  • Generate Carmichael $p$ (false prime) until we can find a large real prime $q$ for which $p | (q – 1)$. In this case we will have to do discrete log modulo large prime $q$, but separately for each of the small subgroups (obtained from factorization of $p$).

For both ways we would need Pohlig-Hellman method, but in the second case the arithmetic will be much heavier (since all small logs must be done modulo large $q$). Also it is easier to find small prime $p$ than large prime $q$. Therefore, the first way is preferrable.

The way we will find $p$ is simple: first we obtain some Carmichael number $q$, then we remove small factors from $q$ by let’s say trial division. Then we check if the result is prime. It should happen quite often!

Now the problem is – how to generate Carmichael numbers? One of the basic algorithms is Erdos algorithm, described for example in this paper:

Erdos algorithm

Here is my implementation of its simplest randomized version in Sage:

from sage.all import *
import operator
 
first_primes = list(primes(10**7))
 
# it is important to find good lambda
# the algorithm highly depends on it
# this one is from some paper
factors = [2**5, 3**2, 5, 7, 11, 13, 17]
lam = reduce(operator.mul, factors)
# lam = /\ = 24504480
 
P = []
for p in primes(min(10000000, lam)):
    # do not include large primes so that Fermat test
    # has higher probability to pass
    if p < 400:
        continue
    if lam % p and lam % (p - 1) == 0:
        P.append(p)
 
print "P size", len(P)
 
prodlam = reduce(lambda a, b: a * b % lam, P)
prod = reduce(lambda a, b: a * b, P)
 
# faster prime checks
proof.arithmetic(False)
 
while 1:
    numlam = 1
    num = 1
    # we are building random subset {p1,...,p20}
    # and checking the subset at each step
    for i in xrange(20):
        p = choice(P)
        numlam = numlam * p % lam
        num = num * p
        if numlam != prodlam or prod % num != 0:
            continue
        q = prod // num
        print "candidate", q
        print factor(q)
        print
        ps = [p for p, e in factor(q)]
        is_carm = ( (q - 1) % lcm([p-1 for p in ps]) == 0 )
        if not is_carm:
            continue
 
        # now check if q - 1 = small primes * large prime p
        # since we need to know such p
        # should happen by chance quite often
        t = q - 1
        for p in first_primes:
            while t % p == 0:
                t //= p
        if is_prime(t):
            print "Good!"
            print "q =", q, "#", len(q.bits()), "bits"
            print "p =", p, "#", len(p.bits()), "bits"
            print
            open("candidates", "a").write("q = %d\n" % q)
            open("candidates", "a").write("p = %d\n\n" % p)
 
# solution:
q = 59857999685097510058704903303340275550835640940514904342609260821117098340506319476802302889863926430165796687108736694628663794024203081690831548926936527743286188479060985861546093711311571900661759884274719541236402441770905441176260283697893506556009435089259190308034118717196693029323272007089714272903225216389846915864612112381878100108428287917605430965442572234711074146363466926780699151173555904751392997928289187479977403795442182731620805949932616667193358004913424246140299423521
p = 62524500763431441748481642690708441489776386892126187254070724779722504054292898512943722029745633023670685560530873804922086432332770562190282869379418979194485569141426416326281184435782910942683630763055432514713734358605440032411156894024431274583468338817956399407807741136790938228633811230955007519469063632837378284757301519562677312080310137628454021752642170957113443979650111115572728879157653822412120689975685302219422272533094042684647476957834486986793341

It takes around 30-60 minutes to find a solution, for example:

q = 409 * 421 * 443 * 463 * 521 * 613 * 617 * 631 * 661 * 673 * 859 * 881 * 911 * 937 * 953 * 991 * 1021 * 1123 * 1171 * 1249 * 1321 * 1327 * 1361 * 1429 * 1531 * 1871 * 1873 * 2003 * 2081 * 2143 * 2311 * 2381 * 2731 * 2857 * 2861 * 3061 * 3169 * 3361 * 3433 * 3571 * 3697 * 4421 * 4621 * 5237 * 5281 * 6007 * 6121 * 6553 * 6733 * 7481 * 8009 * 8191 * 8581 * 8737 * 9241 * 9283 * 10711 * 12377 * 13729 * 14281 * 16831 * 17137 * 17681 * 18481 * 19891 * 20021 * 20593 * 21841 * 23563 * 24481 * 25741 * 26209 * 27847 * 29173 * 29921 * 30941 * 34273 * 36037 * 42841 * 43759 * 46411 * 48049 * 52361 * 53857 * 55441 * 63649 * 65521 * 72073 * 72931 * 74257 * 78541 * 79561 * 87517 * 92821 * 96097 * 97241 * 110881 * 116689 * 117811 * 131041 * 145861 * 148513 * 157081 * 180181 * 185641 * 209441 * 235621 * 269281 * 291721 * 314161 * 371281 * 388961 * 445537 * 471241 * 680681 * 700129 * 816817 * 1633633 * 8168161.

Solving the discrete log

After finding good $p$ and $q$, it is easy to solve the rest of the problem. First, since we can’t bypass the test in 100% of the times, we have to do a few iterations. Then, if the tests pass, we need to solve the discrete logarithm problem. Luckily, Sage automatically factors the modulus (and all the group orders) and applies Pohlig-Hellman method. Since the factors are small, we don’t need to supply our factorization to Sage, it finds it quickly automatically. We only have to ask Sage to compute $discrete\_log(v, g)$!

from sage.all import *
from sock import *
 
q = 59857999685097510058704903303340275550835640940514904342609260821117098340506319476802302889863926430165796687108736694628663794024203081690831548926936527743286188479060985861546093711311571900661759884274719541236402441770905441176260283697893506556009435089259190308034118717196693029323272007089714272903225216389846915864612112381878100108428287917605430965442572234711074146363466926780699151173555904751392997928289187479977403795442182731620805949932616667193358004913424246140299423521
p = 62524500763431441748481642690708441489776386892126187254070724779722504054292898512943722029745633023670685560530873804922086432332770562190282869379418979194485569141426416326281184435782910942683630763055432514713734358605440032411156894024431274583468338817956399407807741136790938228633811230955007519469063632837378284757301519562677312080310137628454021752642170957113443979650111115572728879157653822412120689975685302219422272533094042684647476957834486986793341
 
itr = 0
while 1:
    itr += 1
    print "Try #%d" % itr
    f = Sock("104.198.63.175 1729")
    f.send_line(str(q))
    f.send_line(str(p))
    ans = f.read_line()
    print `ans`
    if "Traceback" in ans:
        print ans
        print f.read_all()
        continue
 
    print "Primes are accepted! Getting discrete log"
    g, y = [int(ss[2:], 16) for ss in ans.split()]
    R = IntegerModRing(q)
    x = discrete_log(R(y), R(g))
    print "x", x
    print "y", y
    print "correct ?", pow(g, x, q) == y
    f.send_line(str(x))
 
    print f.read_all()
    break

After a few iterations, we get the flag: hxp{5cHr0eD1n9eR’s_Pr1m3z}

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>