Request for a writeup - CTF HXP 2019 - nacht

[IamLupo]

Hello sir,

Could you make a writeup about the "nacht" CTF? I saw you solved it at "2019-12-29 18:00". Congrats

I manage get myself to get the X, A, R, S.

But my problem was getting the C1 and C2 in the formula:

X + S mod 2^128 = A
(C1 * R) + (C2 * R * R) mod (2^130 - 5) = X

I Re-arrange the formula:

R(C1 + C2 * R) = R * Y
R * Y * X mod (2^130 - 5) = 1

Then us modulo multiple inverse to find Y. But the Y i found is not the correct one.

If i could find the corrrect Y for two tag (A) cases i could find C1 and C2:

C2 = abs(Y1 - Y2) / abs(R1 - R2)
C1 = Y1 - (C2 * R1)

Happy 2020!

CTF: https://2019.ctf.link/internal/challenge/5af3da6e-8187-43cf-bd40-5f553e1a7a58

[chia-an]

Hi,

Here is the long-awaited reply. Sorry for being so late.

First of all, you noticed that we have R, S instead of C1, C2. This is good because that is one of the key observations in this task.

Your plan of solving C1, C2 looks reasonable, and it is hard to know which part went wrong without code and data. However, I'd like to point out some details you may have missed, and hopefully that will help you solve the challenge.

1. Make sure you encode / decode numbers correctly. The algorithm flips some bits before doing maths and encode numbers in an unintuitive way. You can check the code or the documents for this.

2. Following your notation, if you set Y = C1 + C2 * R, then the equation you get should be R * Y mod (2^130-5) = X. So you should be able to get Y using something like Y = R^(-1) * X mod (2^130-5).

3. You don't need abs() to solve C2. The formula is simply C2 = (Y1 - Y2) / (R1 - R2).

I hope this is useful to you. There are also some writeups from other teams on CTFtime.

[IamLupo]

thx for your respons, I realized on one of the solutions i had to use the ideal of a PolynomialRing to find the correct C1 and C2. In my case i dont have any experience with this and thats why i kept stuck.
This writeup helped me in the end: https://cr0wn.uk/2019/36c3/

Your insight on step 2 was a good one, i didnt knew i could transform it like that.