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

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:

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}

print ("p =", t, "#", len(p.bits()), "bits")