reality

Attachmentscrypto - 27924 solves

Shamir did the job for you, just connect to the challenge and get the flag.

Time

8 hours

Actually, it only tooks me 1.5 hour to solve it after getting into the right direction.
I wasted a lot of time guessing the code and poking its PRNG 😡.

Behavior

Here's a base32-encoded and encrypted flag: DUHUKDEVNOPMLPYNJGHSAFJECOSJPUNENVP5J2NCJGADRLT7CRZQ====
To decrypt it you need 5 coefficients. I'll only give you 3
coefficients 1: 1.0922~[491 more digits]~5705, 717~[33 more digits]~542.4453~[453 more digits]~0219
coefficients 2: 1.1527~[491 more digits]~1035, 808~[33 more digits]~638.0541~[453 more digits]~6787
coefficients 3: 1.9277~[491 more digits]~3298, 345~[33 more digits]~353.7075~[453 more digits]~1995

We don't have any source code in this challenge. According to the description, it may uses shamir secret sharing to split the key into 5 pieces. However, we only have 3 of them.

Solution

TL;DR

  1. Guess what the service does
  2. Multiply 1045010^{450} to each number and truncate the fraction to integer
  3. Build the lattice
  4. Run LLL to find the shortest integer solution
  5. Decrypt the flag with AES-CBC

Shamir Secret Sharing

Shamir secret sharing is used to split a secret into multiple pieces. It has two parameters, nn and kk. The secret will be split into nn pieces, and you'll need kk pieces to reconstruct the secret. Furthermore, you won't gain any knowledge of the secret with less than kk pieces (when implemented correctly).

Technically, it defines a polynomial of degree k1k - 1:

f(x)=i=0k1sixif(x) = \sum_{i=0}^{k-1} s_i x^i

where s0s_0 is the secret and all other coefficients are randomly generated. Those split secret pieces are the points on this curve. We'll need at least kk points to reconstruct the curve, and it can be done using lagrange polynomial.

Typically, the shamir secret sharing works in a finite field instead of the reals. The precision in this task is pretty high, which gives us excessive information about the secret.

To solve this task, you have to guess that the coefficients are positive integers and they're quite small (~40 digits compares to 500 digits fraction).

I'll talk about the analysis before I came up with this guess. You can jump to the last section about LLL if you aren't interesting on the reason.

Random numbers

Without any knowledge about the service, I start from dumping 3000 pairs from the server and analyze how they are generated.

I dump with 16 threads in parallel, and I found that some output are the same. The collision probability is about 0.03, and all collisions only happened in succesive runs. It means the server may use a time-seeded PRNG (possible milliseconds).

Next I trying to figure out how they generate x, Here's the distribution of x I got from the server.

x_dist

Most of the x are closed to 1, and all of them are bigger than 1. The distribution of 1/x seems to be uniform distribution.

Moreover, the number of 1/x looks like:

0.5372495835723414270290732019930146634578704833984375
0.1468025157144856596147519667283631861209869384765625
0.39606395612572253828176371825975365936756134033203125

They are actually generated by rangrange(2^53) / 2^53.

Now we know how x are generated, how about the coefficients?

Random Coefficients

According to the polynomial of Shamir secret sharing, the expected value of these cofficients will be f(x)/ixif(x) / \sum_i x^i, which is about 225568696201524096821742572483714374706.

However, the real random number generator they choice can't generate such large number. I also tested that whether the result is dominated by one of the coefficients (i.e. the secret), and it's not correct.

Also, the order of three x are always same as tho order of y, which means all coefficients are positive.

Based on these result, I guess the coefficients are positive integers. (Another reason is that I have totally no idea how to convert a fraction to a encryption key. LOL)

Underconstrained System of Linear Equations

Now, we have a linear system Xs=yXs = y where XX is the Vandermonde matrix of those three x. the system is Underconstrained because we have only 3 equations.

Compare to the coefficients, those yy are much longer. For such problem, we can solve it with some lattice magic.

However, lattice methods only works with integers. To convert these fractions to integer, I scale up both XX and yy with 1045010^{450}, and the equations still hold.

Next, I truncate those fractions to integer and concatenate an identity matrix to XX. One of the solution becomes X[a0,,a4,e0,e1,e2]=yX' [a_0, \cdots, a_4, e_0, e_1, e_2] = y' where eie_i is the error introduced by truncating. Those error would be smaller than sum of those coefficients because the truncated fractions are smaller than 1.

Finally, I concatenate yy' to XX' as a column vector, and one of the solution becomes A[a0,,a4,e0,e1,e2,1]=0A [a_0, \cdots, a_4, e_0, e_1, e_2, -1] = 0

The lattice of solutions is {sAs=0}\{s | As = 0\} which can be defined by the right kernel of AA.

Alse, the solution we want is quite "short". It's absolute value is about 104010^{40} compared to others which is about 1050010^{500}.

Finding such vector is hard in general, but we have suboptimal algorithms like LLL. And it guarantees to find the shortest one if it is short enough.

We can solve it with sagemath easily:

A = Matrix([
#  Vandemonde              Identity matrix                    y
    x.list() + [1 if i == j else 0 for j in range(len(y))] + [yi]
    for i, (x, yi) in enumerate(zip(X, y))
    ])
B = A.right_kernel_matrix()
print(-B.LLL()[0])

You can find the full code at here.

The result looks like

a_0: 285450566584795714324161453455178970870,
a_1: 128443615496666315668191505779431802508,
a_2: 120171678482189002974121031567641762737,
a_3: 29169727575576393604385364950262505188,
a_4: 191216618537187805549913252159424580933,
y_s: -1,
e_0: 138021328216454971007230221028671168120,
e_1: 48993614216086579566584094608235291082,
e_2: -85525054552282748747414766196213187078

The last thing is to guess the encryption algorithm, it turns out to be AES CBC with null IV.