Initial attempts#

On first sight, there isn’t a good algo to handle this other than factorization. Because the product is very large, if we go for the bruteforce approach it would take ages (there should be at least 2^30 40-bit prime and each time we need to do a gigantic division). Throwing it in cado-nfs or yafu is also a bit problematic because the number is really large and my terminal can’t handle it. (Perhaps there’s a way but I couldn’t get it work zzz)

Utaha mentioned that Alpertron could factor fast for 40 bit * 960 bit numbers, and since Alpertron uses ECM, the challenge intended should be something related with ECM tuning and smart factorizations. It turns out fine-tune ECM is indeed intended, but he spent a while during the competition and couldn’t get this to work.

At this point the challenge is still 0 solved, then I was told Neobeo blooded it in 5-10 minutes:

This made me wonder if there’s some cheesy solution to the challenge, rather than normally solving it, because even with ECM factorization it wouldn’t be that fast…

Cheese#

Ok, so now I had the (wrong) impression this challenge could be solved with unintendeds. The first idea came to my mind is some gcd related cheese, because if key repeats we can directly use gcd to find the value. I tried to do it locally, and found that the script should be extremely slow in generating and multiplying the primes. However, their server response was instant, this made me suspect the 1024-bit primes were not generated on-the-fly. Instead, there is probably a list of pre-generated primes, and the server just picks a subset of them and multiplies together.

Now let’s verify this, first by getting a few haystacks:

1
from pwn import *
2
from math import gcd
3
import sys
4
from Crypto.Util.number import isPrime
5

6
sys.set_int_max_str_digits(0)
7
haystacks = []
8

9
for _ in range(100):
10
    io = remote("key-in-a-haystack.chal.uiuc.tf", 1337, ssl=True)
11
    enc = io.recvline().strip().decode().split(": ")[1]
12
    haystack = io.recvline().strip().decode().split(": ")[1]
13
    haystacks.append(int(haystack))
14
    io.close()

After this, we can try gcd some of haystack values, and not surprisingly, their gcd are large, and we see they are pre-calculated primes.

Now that we know it, we can just repeatedly gcd the original haystack with the remaining haystacks by keep connecting to remote and get the 40-bit key in the end.

1
context.log_level = 'error'
2
target = # the original haystack
3
while True:
4
    io = remote("key-in-a-haystack.chal.uiuc.tf", 1337, ssl=True)
5
    io.recvline()
6
    haystack = int(io.recvline().strip().decode().split(": ")[1])
7
    curr = gcd(target, haystack)
8
    if curr > 1:
9
        print("oops")
10
        target //= curr
11
        print(target)
12
    io.close()

We could just check if final value is 40-bits but I just wanted to print the values to see if there’s progress. We got the prime in the end:

1
...
2
oops
3
112688939659913406629490487167845386067751231399315913109849555229115292487855950959927027176650843915352473623487892707210009856646885955117602455611720842709305117773571460983279240682765546633507425483859031587490016626471928168564375982601715768031888038723968927176515979535143327347455189285294611760810392555698351
4
oops
5
769433032933

And the flag:

1
from Crypto.Cipher import AES
2
from hashlib import md5
3

4
AES.new(
5
  key = md5(b"769433032933").digest(),
6
  mode = AES.MODE_ECB
7
).decrypt(enc_flag)
8

9
# b'uiuctf{Finding_Key_Via_Small_Subgroups}\t\t\t\t\t\t\t\t\t'

To summarize, the cheese is funny and apparently Neobeo solved it intended but fast.