Writeup for Snurre128

The intended solution for Snurre128 is as follows. We note that the non-linear function is almost linear, the higher-order terms have degree 5.

return v[0] ^ v[1] ^ v[2] ^ v[31] ^ \
v[1]&v[2]&v[3]&v[64]&v[123] ^ \
v[25]&v[31]&v[32]&v[126]


Whenever a higher-order term becomes non-zero, we will get non-linear behaviour. Also note that since there are two of these terms, they will cancel out with some small probability. We write $f = L(x) + P(x) + Q(x)$. Because all indices in the non-linear terms ($\{1,2,3,64,123\} \cap \{25,31,32,126\} = \emptyset$) are disjoint, we get

$\begin{array}{rcl}\mathbb{P}(P(x) + Q(x) = 1) &=& \mathbb{P}(P(x) \neq Q(x))\\ &=& \mathbb{P}(P(x) = 1) + \mathbb{P}(Q(x) = 1) - 2\cdot \mathbb{P}(P(x) = 1 \land Q(x) = 1)\\ &=& 2 \cdot 2^{-5} - 2 \cdot 2^{-10}\\& =& \frac{31}{512} \end{array}$

Let $k$ be the dimension of the state and $n$ be the length of the keystream. Note that there exists a big-ass matrix $\mathbf{G} \in \mathbb{F}_2^{k\times n}$ such that

$x\mathbf{G} + e = v \in \mathbb{F}_2^n,$

where $e$ is governed by the non-linearity of $f$. The expected Hamming weight of $e$ is

$n \cdot \mathbb{P}(P(x) + Q(x) = 1).$

It is possible to solve this using a Walsh transform, but it is rather expensive requiring $\mathcal{O}(k \cdot 2^k)$ computation. Employing BKW will significantly reduce the complexity, by transforming the problem into a problem of smaller dimension at the expense of higher error rate.

Another solution is to treat this as a decoding problem over a random code. There is support for so-called information-set decoding in sage.

from sage.coding.information_set_decoder import LeeBrickellISDAlgorithm


First we generate the generator matrix from the cipher, according to the above.

# define a code from big-ass matrix
C = codes.LinearCode(G.transpose())


The keystream is a vector $\mathbb{F}_2^n$:

v = vector(GF(2), [0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1])


Using Lee-Brickell’s algorithm (a rather simple and not the most efficient algorithm of today), we can now decode:

num_errors = 118
A = LeeBrickellISDAlgorithm(C, (num_errors, num_errors))
A.calibrate()
x = A.decode(v)
# for the record, this is the error vector
e = v + A*x


Once this is complete, we can solve a set of linear equations to unravel the state.

Also consider to read this writeup by @hellman 🙂

Solving snurre80 @ MidnightsunCTF

Note: I was the author of this challenge. This is my intended solution. Some details have been left out.

Two teams solved this one: TokyoWesterns and LC↯BC, in that chronological order.

class Snurre80:

"""
Snurre80 is a proprietary stream cipher designed for
low-power devices, i.e., in Internet of Things contexts.
More importantly, it offers an incredibly high security
level of 2^80 (who would need more?).

It has the following structure:

+--------+----+------+
|        |    |      |
+---+---+-   -+---+    |
|   |   | ... |   |  c
+-----------------+

Snurre80 is resistant to distinguishing attacks, since
it uses a non-linear(tm) boolean function f as filtering
output function.

Snurre80 is quantum resistant and blockchain ready. It
is the stream cipher of the future. It is 100 % cyber.
We charge a reasonble fee of $0.00001 / encrypted bit. -- The Designers """ def __init__(self, key): self.state = key self.mask = 1284576224436276739441733 self.nbits = self.mask.bit_length()-1 def output(self): var = bin(self.state)[2:].zfill(self.nbits) v = [int(v) for v in var] return v[0] ^ v[1] ^ v[2] ^ v[31] ^ \ v[1]&v[2]&v[3] ^ \ v[25]&v[31]&v[32]&v[33]&v[34] def __str__(self): j = 0 poly = [] x = self.mask while x > 0: if x & 1: poly = ["x^{}".format(j)] + poly x >>= 1 j += 1 return " + ".join(poly) def keystream(self, n): for _ in xrange(n): self.state = (self.state self.nbits if xor != 0: self.state ^= self.mask yield self.output() # Generate a sequence of 800 bits, with a random key. key = int(os.urandom(10).encode('hex'), 16) cipher = Snurre80(key) z = [c for c in cipher.keystream(800)] # Additionally, this may help you solve the CAPTCHA. def solve_proof_of_work(prefix): i = 0 while True: if sha256(prefix+str(i)).digest()[:3] == "\x00\x00\x00": return str(i) i += 1  The feedback polynomial of the stream cipher is $\begin{array}{rcl} P(x) & = & x^{80} + x^{76} + x^{66} + x^{64} + x^{58} + x^{54} + x^{50} + x^{42} \\ & + & x^{38} + x^{34} + x^{24} + x^{22} + x^{18} + x^{10} + x^6 + x^2 + 1 \end{array}$ To create a distinguisher, we may use the feedback polynomial as parity check. Unfortunately, the output is not linear, but we can approximate it as a linear function. However, by the piling-up lemma, the bias quickly becomes small since there are many terms. So, we need to find a low-weight polynomial multiple to avoid getting too small bias: there exists $q(x)$ such that $q(x) P(x) = u(x)$, where $u(x)$ is of low weight. But wait. Every power is even, so it means it is a square $P(x) = p^2(x)$. Turns out we can easily find the square root of it; by simply dividing every power with $2$, we can find $p(x)$ from $P(x)$. $\begin{array}{rcl} p(x) & = & x^{40} + x^{38} + x^{33} + x^{32} + x^{29} + x^{27} + x^{25} + x^{21} \\ & + & x^{19} + x^{17} + x^{12} + x^{11} + x^{9} + x^{5} + x^3 + x + 1 \end{array}$ Now, we can solve the problem of finding a low-weight multiple in a smaller dimension. This can be done in a couple of seconds. In fact, if you stalked my Github repos you will find that I have written code for this exact problem. The idea behind it is to generate a long list of powers $x^i \bmod P(x)$ and use a generalized birthday attack to find $x^{i_1} + x^{i_2} + x^{i_3} + x^{i_4} = 0 \bmod P(x)$. There are several papers on it. This is not as difficult as it may be time consuming to write functional code. Nonethless, one suitable parity check is $x^{17399} + x^{13567} + x^{4098} + 1$ But it will not work for the polynomial $P(x)$? Well, that if no concern. If $q(x) p(x) = u(x)$, then $q^2(x) p^2(x) = q^2(x) P(x) = u^2(x)$. Since $u(x)$ has weight $w$, $u^2(x)$ will have weight $w$.  p = [17399, 13567, 4098] S = sum( z[i + 2*p[0]] ^ z[i + 2*p[1]] ^ z[i + 2*p[2]] ^ z[i] for i in range(0, 1000)) return S < 430 # appropriate magic constant  Running it for every sequence, we can efficiently decide the source. This gives the flag midnight{1z_3z_2_BR34K_W1D_L0W_w31gHTz!!!} Setting up Google authenticator along SSH auth in macOS This is a guide on how to setup the use of Google Authenticator along with public-key authentication. First, we clone the Google Authenticator PAM module from Github: $ git clone https://github.com/google/google-authenticator-libpam.git

To build it, we need a few packages which are not included by default in macOS.

$brew install autoconf automake libtool To be able to get QR codes without revealing secrets to Google, you can install libqrencode: $ brew install libqrencode

$./bootstrap$ ./configure
$make$ sudo make install

To install the PAM module, invoke

$sudo cp /usr/local/lib/security/pam_google_authenticator.so /usr/lib/pam/ Then, we add the line auth required pam_google_authenticator.so to the configuration file /etc/pam.d/sshd. It will look something like this: # sshd: auth account password session # Not used by me! # auth optional pam_krb5.so use_kcminit # auth optional pam_ntlm.so try_first_pass # auth optional pam_mount.so try_first_pass # auth required pam_opendirectory.so try_first_pass # Relevant methods of authentication: auth required pam_google_authenticator.so account required pam_nologin.so account required pam_sacl.so sacl_service=ssh account required pam_opendirectory.so password required pam_opendirectory.so session required pam_launchd.so session optional pam_mount.so  I have removed the alternative methods of authentication. In /etc/ssh/sshd_config, we set PubkeyAuthentication yes ChallengeResponseAuthentication yes UsePAM yes AuthenticationMethods publickey,keyboard-interactive:pam  This will force the user to prove ownership of a valid SSH-key and along with a verification code from Google Authenticator. Now we are ready to setup the two-factor authentication. Running $ /usr/local/bin/google-authenticator


generate a shared secret and provide you with a QR code to be used with your phone. You can use TOTP or OTP verification codes. I suggest going with TOTP and small time windows.

Another good thing is to add some notifications to your ~/.ssh/rc file (also — if you are in the US, there are a lot of services available for sending SMS, which can be handy, but remember not to send any sensitive data through third parties). For instance:

# Get and sanitize sender address, probably not needed...
ip=echo $SSH_CONNECTION | cut -d " " -f 1 ip=${ip//[^a-zA-Z0-9:.]/}

# Sanitize user, probably not needed...
user=whoami
user=${user//[^a-zA-Z0-9_]/} # Show notification osascript -e 'display notification "SSH connection as '$user' from '$ip'" with title "SSH"' # Send email echo "SSH connection as '$user' from '$ip'" | sendmail me@mydomain.com  This will give a notification to you directly if you are at the computer being connected to. Additionally, it will send an email to you just in case you are AFK. The regexp are there to mitigate possible command injection, though I doubt it is possible unless there is severe bug in SSHD and the script above is running as a user with higher privileges. On the other hand, santitation is never bad if it negligible in terms of computations and you are doing it right 🙂 Another way of sending notifications is to use a Telegram bot. See below for an example output. For this purpose, one might use e.g. telegram-send. Finding close-prime factorizations This is a proposal for a simple factoring algorithm which actually performs better than regular attacks based on lattice-type algorithms. Although more efficient algorithms exists, this one is very simple to implement, while the more efficient ones are not. Do not quote me on this, though ;-D Finding a good approximation The first step is to compute an good approximation of $\phi(n)$. Denote this $\phi'$. One such good approximation is $\phi' = n - 2\sqrt{n} + 1$. Let us see why. First, assuming that $n = pq$, note that $\phi(n) = (p-1)(q-1) = n - (p+q) + 1$ Let us assume there exists a small $\gamma$ such that $p = a + \gamma$ and $q = a - \gamma$. So, we have that $\delta := \phi' - \phi(n) = 2\sqrt{a^2 - \gamma^2} - 2a = 2a\sqrt{(1 - \gamma^2/a^2)} - 2a.$ Now, let $\beta = \gamma^2/a^2$. Then, $\delta =2a\left(\sqrt{1 - \beta} - 1\right) = 2a \cdot \left[\beta/2 + \mathcal{O}(\beta^2)\right]$. Since $\beta$ is assumed to be small ($a >> \gamma$), we can approximate it as $\delta \approx \gamma^2/a.$ Great! So the running time is bounded by $\mathcal{O}( \gamma^2/a)$ if we use pure brute force. Now, we are going to be just a little more clever than that, aren’t we? Searching efficiently We will now show how to search for a solution faster than brute force. First, we pick an arbitrary invertible element $y$ and compute all powers of $y \bmod n$ up to a certain parameter $b$, i.e., $\mathcal B := \{y^0 \bmod n, y^1 \bmod n, \dots , y^b \bmod n\}$ Obviously, this requires $\mathcal O(b)$ time and memory. A reference implementation in Python (with $y = 2$) would look something like. # create a look-up table look_up = {} z = 1 for i in range(0, b + 1): look_up[z] = i z = (z * 2) % n  Now, compute $\mu := (y^{\phi'})^{-1} \bmod n.$ Note that the exponent of $\mu$ is $-\phi' \bmod \phi(n)$. We now do a BSGS-type of algorithm (as noted by hellman in the comments, we can use Pollard’s kangaroo algorithm to avoid exhausting precious memory without sacrificing computational effort, up to polynomial factors). Generate all powers $y^{bi} \bmod n$ for $0 \leq i \leq b$ and multiply with $\mu$ forming $c:= y^{bi} \cdot \mu$. Again, we get an exponent which is $-\phi' + bi \bmod \phi(n).$ For each such computed, check against $\mathcal{B}$ is it exists. If so, we have found $\phi(n)$. # check the table mu = gmpy.invert(pow(2, phi_approx, n), n) fac = pow(2, b, n) j = 0 while True: mu = (mu * fac) % n j += b if mu in look_up: phi = phi_approx + (look_up[mu] - j) break if j > b * b: return  This is $\mathcal O(b)$ in time. Once $\phi(n)$ has been found, we can trivially compute the factors in negligible time as # compute roots m = n - phi + 1 roots = (m - gmpy.sqrt(m ** 2 - 4 * n)) / 2, \ (m + gmpy.sqrt(m ** 2 - 4 * n)) / 2  Cool! Since we require that $\gamma^2/a \leq b^2$ for a solution to be found, the running time is $\mathcal O(\gamma/a^{1/2})$ and with equal amount of memory required. Note that $n = (a + \gamma)(a - \gamma) = a^2 - \gamma^2$. Note that we further reduce the space required by a factor two. Since we know that $\phi(n) = (p-1)(q-1) = 4k$, we can do increments skipping even values. # check the table mu = gmpy.invert(pow(2, phi_approx // 2 * 2, n), n) fac = pow(4, b, n) j = 0 while True: mu = (mu * fac) % n j += 2 * b if mu in look_up: phi = phi_approx + (look_up[mu] - j) break if j > b * b: return  A real-world example (sort of) This little finding inspired me to create a CTF challenge. During the SEC-T CTF 2017, one of the challenges (qproximity) could be solved using this method. Description We are given a public key and an encrypted message. The key is -----BEGIN PUBLIC KEY----- MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgAOBxiQviVpL4G5d0TmVmjDn51zu iravDlD4vUlVk9XK79/fwptVzYsjimO42+ZW5VmHF2AUXaPhDC3jBaoNIoa78CXO ft030bR1S0hGcffcDFMm/tZxwu2/AAXCHoLdjHSwL7gxtXulFxbWoWOdSq+qxtak zBSZ7R1QlDmbnpwdAgMDEzc= -----END PUBLIC KEY-----  Extracting the modulus, we find that $\begin{array}{rl} n = &246264974647736414345408205036830544055349190030438864689361084738619 \\ &430136992438500973098730365134506003143847829773369403632725772343146 \\ &864922044439763512753030199250563829152109289871491767838931495698391 \\ &860322173235862868025625353744920431228772475066920885663471105686331 \\ &5465220853759428826555838536733 \end{array}$ The factors are found as follows def close_factor(n, b): # approximate phi phi_approx = n - 2 * gmpy.sqrt(n) + 1 # create a look-up table look_up = {} z = 1 for i in range(0, b + 1): look_up[z] = i z = (z * 2) % n # check the table mu = gmpy.invert(pow(2, phi_approx, n), n) fac = pow(2, b, n) j = 0 while True: mu = (mu * fac) % n j += b if mu in look_up: phi = phi_approx + (look_up[mu] - j) break if j > b * b: return m = n - phi + 1 roots = (m - gmpy.sqrt(m ** 2 - 4 * n)) / 2, \ (m + gmpy.sqrt(m ** 2 - 4 * n)) / 2 return roots n = 2462649746477364143454082050368305440553491900304388646893610847386194301369924385009730987303651345060031438478297733694036327257723431468649220444397635127530301992505638291521092898714917678389314956983918603221732358628680256253537449204312287724750669208856634711056863315465220853759428826555838536733 b = 10000000 close_factor(n, b)  The code runs in matter of seconds and gives the factors $\begin{array}{rl} p = &156928319511723700336966188419841178779822856669047426731288203806365 \\ &781043486977181195772183437407585036370841822568787188893070958887580 \\ &0968904667752571 \end{array}$ and $\begin{array}{rl} q = &156928319511723700336966188419841178779822856669047426731288203806365 \\ &838576177312234882203162849666809217683250766146317773098495921211843 \\ &5829588059735623 \end{array}$ Using these, we construct the flag SECT{w3ll_th4t_wasnt_2_h4rd?} Edit: I needed a threaded memory-less implementation. It can be found here. Polictf 2017 – Lucky Consecutive Guessing This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem $aX_i + b = X_{i+1} \bmod M$ to $aX_i = X_{i+1} \bmod M$. This problem is quite easy to solve. The basic idea is to view the problem as the latter and correct the discrepancies ($\delta = (b, ab, a^2b,\dots)$). So, for instance, if we sample $V = \texttt{1310585136, 1634517111, 2548394614, 745784911},$ then these values contain the implicit discrepancies. By performing correction of the values (subtracting $\sum_k^i \delta_k$ from the corresponding $V_i$ we obtain a corrected value). So, now we can use LLL to solve the simpler problem. Once a solution is found, we use the discrepancies to correct it to the case $aX_i + b = X_{i+1} \bmod M$. import random class LinearCongruentialGenerator: def __init__(self, a, b, nbits): self.a = a self.b = b self.nbits = nbits self.state = random.randint(0, 1 << nbits) def nextint(self): self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) return self.state >> (self.nbits - 32) def break_lcg(a,b,p,i,j,outputs): deltas = [b % p, (a*b + b) % p, (a^2*b + a*b + b) % p, (a^3*b + a^2*b + a*b + b) % p] Y = [((val << (i - j)) ) for val, delta in zip(outputs, deltas)] L = matrix([ [p, 0, 0, 0 ], [a^1, -1, 0, 0 ], [a^2, 0, -1, 0 ], [a^3, 0, 0, -1] ]) B = L.LLL() Y = vector([x - y for x, y in zip(Y, deltas)]) target = vector([ round(RR(w) / p) * p - w for w in B * vector(Y) ]) states = list(B.solve_right(target)) return [x + y + z for x, y, z in zip(Y, states, deltas)] # parameters p = 2^85 a = 0x66e158441b6995 b = 0xb n = 85 r = 32 sequence = [1310585136, 1634517111, 2548394614, 745784911] # break the LCG start_seed = break_lcg(a,b,p,n,r,sequence) # run it to sample required values lcg = LinearCongruentialGenerator(a, b, n) lcg.state = start_seed[0] for i in range(0, 104): print lcg.nextint()  Generating wallpaper-consistent terminal colors with K-means++ K-means algorithm Assume that we have to following image: We can represent the image in 3D-space as follows: Suppose that we want to find eight dominant colors in the image. We could create a histogram and take the eight most common values. This would be fine, but often, very similar colors would repeat. Instead, we can try to find eight centroids in the image and find clusters of points beloning to each centroid (say, a point $p$ belongs to a centroid $p_{\text{centroid}}$ if $\|p - p_{\text{centroid}}\|_2 < R$ for some radius $R$). All points not belonging to a centroid will be penalized using some heuristic. This is basically the K-means clustering algorithm. Usage The algorithm can be used to generate set of dominant colors to be used for instance in the terminal. Running the above algorithm on the image, we get or as list ['#321331', '#e1a070', '#621d39', '#e05a40', '#9ed8aa', '#8b3860', '#f7d188', '#ab3031'] with some minor adjustment { "color": [ "#ab3031","#621d39","#e05a40","#e1a070","#9ed8aa","#521f50","#8b3860","#f7d188","#ab5a5b","#623b4b","#e08c7b","#e1b99c","#c4d8c8","#715171","#8b5770","#f7e4c0" ], "foreground": "#c5c8c6", "background": "#282a2e" }  In iTerm, it might look like this This can be achieved using the following code: #!/usr/bin/env python import sys, os from sklearn.cluster import KMeans from PIL import Image nbrcentroids = 10 # Constant increase in colors beta = 10 # Multplicative factor in background gamma = 0.4 rgb2hex = lambda rgb: '#%s' % ''.join(('%02x' % min(p + beta, 255) for p in rgb)) darken = lambda rgb : (p * gamma for p in rgb) def getcentroids(filename, n=8): img = Image.open(filename) img.thumbnail((100, 100)) # Run K-means algorithm on image kmeans = KMeans(init='k-means++', n_clusters=n) kmeans.fit(list(img.getdata())) # Get centroids from solution rgbs = [map(int, c) for c in kmeans.cluster_centers_] return rgbs def set_colors_gnome(centroids): centroids = sorted(centroids, key=lambda rgb: sum(c**2 for c in rgb)) prefix = 'gsettings set org.pantheon.terminal.settings ' # Set background and foreground os.system(prefix + 'background \"%s\"' % rgb2hex(darken(centroids[0]))) os.system(prefix + 'foreground \"%s\"' % rgb2hex(centroids[-1])) # Set ANSI colors colors = ':'.join(rgb2hex(centroid) for centroid in centroids[1:-1]) os.system(prefix + 'palette \"' + colors + ':' + colors + '\"') def bar(mode): write = sys.stdout.write for i in range(0, nbrcentroids): write('\033[0;3%dmBAR ' % i) write('\n') centroids = getcentroids(sys.argv[1], n=nbrcentroids) set_colors_gnome(centroids) bar(0);  It is on Github too! PlaidCTF’17 – Multicast We are given a challenge which contains a Sage script, which holds the following lines of code nbits = 1024 e = 5 flag = open("flag.txt").read().strip() assert len(flag) <= 64 m = Integer(int(flag.encode('hex'),16)) out = open("data.txt","w") for i in range(e): while True: p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False) q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False) ni = p*q phi = (p-1)*(q-1) if gcd(phi, e) == 1: break while True: ai = randint(1,ni-1) if gcd(ai, ni) == 1: break bi = randint(1,ni-1) mi = ai*m + bi ci = pow(mi, e, ni) out.write(str(ai)+'\n') out.write(str(bi)+'\n') out.write(str(ci)+'\n') out.write(str(ni)+'\n')  …along with a text file containing the encrypted flag. Let us first parse the file and put in a JSON structure data = {'n' : [n0, n1, ...], 'a' : [a0, a1, ...], ...} We see that the flag is encrypted several times, up to affine transformation. If we define a polynomial $g_i(x) = (a_ix + b_i)^5 - c_i \mod N_i$, this has a root $g_i(m) = 0 \mod N_i$. We could try to find this root using Coppersmith, but it turns out it not possible since the size of $(am + b)^5$ is larger than $N_i$. However, due to a publication by Håstad, we can construct the following: $g(x) = \sum \phi_i(N_i) g_i(x)$ where $\phi_i \mod N_j = \begin{cases}0 & \quad \text{if } i \neq j\\1 & \quad \text{when } i = j\\\end{cases}$ It is easy to construct $\phi_i$ as $\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}$ using the Chinese Remainder Theorem. Clearly, $g(x)$ also has a root $g(m) = 0 \mod (\prod N_i)$ (this is easy to check!). Since $m^5$ is strictly smaller than $\prod_k N_k$, the polynomial roots of $g(x)$ can be found using Coppersmith! p = data['n'][0] * data['n'][1] * data['n'][2] * data['n'][3] * data['n'][4] PR. = PolynomialRing(Zmod(p)) f = 0 # compute the target polynomial for i in range(0, 5): q = p / data['n'][i] qinv = inverse_mod(q, data['n'][i]) f = f + q * qinv * ((data['a'][i]*x + data['b'][i])^5 - data['c'][i]) # make f monic f = f * inverse_mod(f[5], p) print f.small_roots(X=2^512, beta=1)[0]  The code outputs the long integer representation of PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!} ASIS CTF’17 F4 Phantom With F-4 Phantom II, we want to break the encryption! Please help us!! ‍‍‍nc 66.172.27.77 54979 We get a key-generation function, as seen below. def gen_pubkey(e, p): assert gmpy.is_prime(p) != 0 B = bin(p).strip('0b') k = random.randrange(len(B)) k, l = min(k, len(B) - k), max(k, len(B) - k) assert k != l BB = B[:k] + str(int(B[k]) ^ 1) + B[k+1:l] + str(int(B[l]) ^ 1) + B[l+1:] q = gmpy.next_prime(int(BB, 2)) assert p != q n = p*q key = RSA.construct((long(n), long(e))) pubkey = key.publickey().exportKey("PEM") return n, p, q, pubkey  So, $pq = p \cdot (p \pm 2^k \pm 2^l + \Delta)$, where $\Delta = \texttt{next\_prime}(p \pm 2^k \pm 2^l) - (p \pm 2^k \pm 2^l)$. The density of primes (well, asymptotically) is $\pi(n) \sim \frac{x}{log x}$, so we expect $\Delta$ to be quite small. We define $a := p \pm 2^k \pm 2^l$. Now, we solve the following equation $x \cdot (x \pm 2^k \pm 2^l + \Delta) = N \iff x \cdot (x + a) - N = 0 \iff x = \frac{a}{2} \pm \sqrt{\frac{a^2}{4} + N}$ Now, we know that the roots should be numerically close to $p$ and $q$. So, we may simply call $\texttt{next\_prime}$ on them and check if they divide $N$. Note that we need to do this for different hypotheses (different $k$). import gmpy, base64 from Crypto.PublicKey import RSA def solve(a): a2 = a ** 2/4 L = gmpy.sqrt(a2 + N) # L > a/2 C_1 = gmpy.next_prime(-a/2 + L) if N % C_1 == 0: return C_1 C_2 = gmpy.next_prime(a/2 + L) if N % C_2 == 0: return C_2 return False # just some public key pem_data1 = ''' MIGmMA0GCSqGSIb3DQEBAQUAA4GUADCBkAKBhyW0uQDhy7/eShVn6VQWQisC8sda zl8xJmCe8eEPGNfDVMFgN7Ll4WdRLYE4T8dOvoMb99Cmjhym7Orb/qfP5q/BpTQy 5hr1w5RZVtYMqQ5I+M4qg7E8kkVhGJh/13bNwqEYvV6VNSCK+bgFWVGMelTQam31 Fiq6wsTLbIBCrLie52Cil1584QIEC8rPFw== ''' pub = RSA.importKey(base64.b64decode(pem_data1)) N = pub.n m = (len(bin(N))+1)/2-2 print '[ ] Solving equations...' for mm in range(m, m+3): for j in range(2, m/2+1): k = mm - j l = j retval = solve(2**(k-1) + 2**(l-1)) if retval: q = retval break retval = solve(2**(k-1) - 2**(l-1)) if retval: q = retval break p = N / q print '[+] Found p = {}... and q = {}...'.format(str(p)[:40], str(q)[:40])  λ python solve.py [ ] Solving equations... [+] Found p = 1381282812140256921334162381757305071089... and q = 1381282811302268925712750063033928508701...  Now, it turns out that $\text{gcd}(e, (p-1)(q-1)) \neq 1$. We cannot decrypt the message! If we look closely, we see that $\text{gcd}(e, (p-1)) = 1$. Hmm… so, we can decrypt the message $c^d = m \mod p$. And the message is the flag, which is constant. What if we sample two ciphertexts encrypting the same message but under different keys? Yes… so, basically, we have $m \mod p_1$ and $m \mod p_2$. Then, we can combine it using CRT! This is easy! import gmpy from Crypto.Util.number import long_to_bytes enc1 = 63188108518214820361083256140053967663112132356420859206347143811869148973386950682507343981284848159232100220605963292020722612854139075311063776086523677522160515093598202087755508512714885329251980275085813640578839753523295579661559881983237388178475574713319340090857313275483787001349560782781513895950569634984688753665 q1 = 33452043035349425454164058954054458228134102234436666511159820871022348004023966976017694615018111901825497223286811050478588079083387098695346723120647425399335947 p1 = 33452043035349425454164058954054813129854949698738692548175391185736387867969615080539316436404430573352896343366560167202569408949342999951142479436993639588965567 e1 = 3562731839 enc2 = 162331112890791758781057932826106636167735138703054666826574266304486608255768782351247144197937186145526374008317633308191215438756014724244242639042178681790803086016105986729819920057318114565244866632716401408212076926367974085730803964312385570202673351687846963322223962280999264618753873289802828995706526584379102468 q2 = 1381282812140256921334162381757305071089685391539884775199049048751523002134390007428038278188586333291047282664366863789424963612326970767160301759006158962675449 p2 = 1381282811302268925712750063033928508701820008572424411412024462643800411901779755548441592138469189655615818433739872652769585433967353091413641137354055362924329 e2 = 197840663 d1 = gmpy.invert(e1, p1-1) d2 = gmpy.invert(e2, p2-1) assert(gmpy.gcd(e1, p1-1) == 1) assert(gmpy.gcd(e2, p2-1) == 1) m = (pow(enc1, d1, p1) * p2 * gmpy.invert(p2, p1) + pow(enc2, d2, p2) * p1 * gmpy.invert(p1, p2)) % (p1*p2) print long_to_bytes(m)  …prints: ********** great job! the flag is: ASIS{Still____We_Can_Solve_Bad_F4!} Alright! A fine OTP server Connect to OTP generator server, and try to find one OTP. nc 66.172.27.77 35156 We get the code for generating OTPs: def gen_otps(): template_phrase = 'Welcome, dear customer, the secret passphrase for today is: ' OTP_1 = template_phrase + gen_passphrase(18) OTP_2 = template_phrase + gen_passphrase(18) otp_1 = bytes_to_long(OTP_1) otp_2 = bytes_to_long(OTP_2) nbit, e = 2048, 3 privkey = RSA.generate(nbit, e = e) pubkey = privkey.publickey().exportKey() n = getattr(privkey.key, 'n') r = otp_2 - otp_1 if r < 0: r = -r IMP = n - r**(e**2) if IMP > 0: c_1 = pow(otp_1, e, n) c_2 = pow(otp_2, e, n) return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2  We note that $\texttt{otp\_1}^3 < N$. Because of this, the task is really trivial. We can simply compute the cubic root without taking any modulus into consideration. $\texttt{gmpy2.iroot(arg, 3)}$ can solve this efficiently! This gives us: ASIS{0f4ae19fefbb44b37f9012b561698d19} Secured OTP server Connect to OTP generator server, and try to find one OTP. This is secure than first server 🙂 nc 66.172.33.77 12431 This is almost identical to the previous, but the OTP is chosen such that it will overflow the modulus when cubed.  template_phrase = '*************** Welcome, dear customer, the secret passphrase for today is: ' A = bytes_to_long(template_phrase + '00' * 18)  Note that we can write an OTP as $m = A \cdot 2^k + B$, where $B < 2^k$. So, we have $m^3 = A^3 + 3A^2D + 3AD^2 + D^3$. The observant reader have noticed that if we remove $A^3$, it will not wrap around $N$. Now, we can mod out the terms containing $A$, i.e., find $m - A^3 \mod A$. Now we are back in the scenario of previous challenge… so, we can use the method from before! Hence, $(m - A^3 \bmod A)^{1/3}$. Finally, we get ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter’s_attack_CongratZ_ZZzZ!_!!!}  DLP You should solve a DLP challenge, but how? Of course , you don’t expect us to give you a regular and boring DLP problem! nc 146.185.143.84 28416 The ciphertext is generated using the following function: def encrypt(nbit, msg): msg = bytes_to_long(msg) p = getPrime(nbit) q = getPrime(nbit) n = p*q s = getPrime(4) enc = pow(n+1, msg, n**(s+1)) return n, enc  We have that $e = (n+1)^m \mod n^s = n^m + {m \choose {m-1}}n^{m-1} + \cdots + + {m \choose 2}n^2 + {m \choose 1}n + 1$. We can write this as ${m \choose 1}n + 1 + \mathcal{O}(n^2)$. Now, we can eliminate the ordo term by taking $e \mod n^2 = {m \choose 1}n + 1 \iff e - 1 \mod n^2 = mn$. Assuming that $m < n$, we can determine $m$ by simple division. So, $\frac{e - 1 \mod n^2}{n} = m$. In Python, we have that Turns out this is the case, and, hence, we obtain ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!} unsecure ASIS sub-d ASIS has many insecure sub-domains, but we think they are over HTTPS and attackers can’t leak the private data, what do you think? So, we get a PCAP. The first thing we do is to extract data binwalk -e a.pcap. This generates a folder with all the certificates used. Then, we look at the moduli. #!/bin/bash FILES=*.crt for f in$FILES
do
openssl x509 -inform der -in \$f -noout -text -modulus
done


This generates a file with all moduli. Let us try something simple! Common moduli! For each pair, we check if $\text{gcd}(N_i, N_j) \neq 1$. If so, we have found a factor. Turns out two moduli have a common factor, so we can factor each of them and decrypt their traffic:

p1 = 146249784329547545035308340930254364245288876297216562424333141770088412298746469906286182066615379476873056564980833858661100965014105001127214232254190717336849507023311015581633824409415804327604469563409224081177802788427063672849867055266789932844073948974256061777120104371422363305077674127139401263621
q1 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791

p2 = 159072931658024851342797833315280546154939430450467231353206540935062751955081790412036356161220775514065486129401808837362613958280183385111112210138741783544387138997362535026057272682680165251507521692992632284864412443528183142162915484975972665950649788745756668511286191684172614506875951907023988325767
q2 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791


We can now generate two PEM-keys

d1 = gmpy.invert(e, (p1 - 1)*(q1 - 1))
key = RSA.construct((long(p1*q1), long(e), long(d1)))
f = open('privkey.pem','w')
f.write(key.exportKey('PEM'))
f.close()


Putting it into Wireshark, we obtain two images:

I totally agree.

Alice, Bob and Rob

We have developed a miniature of a crypto-system. Can you break it?
We only want to break it, don’t get so hard on our system!

This is McElice PKC. The ciphertexts are generated by splitting each byte in blocks of four bits. The following matrix is used as public key:

$G = \begin{pmatrix}1& 1& 0& 0& 0& 1& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 1& 0& 1& 1& 0& 0 \\ 0& 1& 1& 1& 0& 0& 1& 0 \end{pmatrix}$

The ciphertext is generated as $\mathbf{m}G + \mathbf{e}$, which is a function from 4 bits to a byte. $\mathbf{e}$ is an error (or pertubation) vector with only one bit set. This defines a map $f: \mathbb{F}_4 \rightarrow \mathbb{F}_8$. So, each plaintext byte is two ciphertext bytes.

We can first create a set of codewords

P = numpy.matrix([[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 0, 1, 1, 0, 0],[0, 1, 1, 1, 0, 0, 1, 0]])
image = {} # set of codewords
for i in range(0, 2**4):
C = (numpy.array([int(b) for b in (bin(i))[2:].zfill(4)]) * P % 2).tolist()[0]
image[int(''.join([str(c) for c in C]), 2)] = i


Then, go through each symbol in the ciphertext, flip all possible bits (corresponding to zeroing out $\mathbf{e}$) and perform lookup in the set of codewords $P$ (compute the intersection between the Hamming ball of the ciperhext block and $P$).

f = open('flag.enc','r')
out = ''
for i in xrange(18730/2):
j = ord(blocks[0])
C1 = 0
C2 = 0
for i in range(0, 8):
if j ^ 2**i in image:
C1 = image[j ^ 2**i] << 4
j = ord(blocks[1])
for i in range(0, 8):
if j ^ 2**i in image:
C2 = image[j ^ 2**i]
out += chr(C1+C2)
f=open('decrypted','w')
f.write(out)


Turns out it is a PNG:

Confidence DS CTF ’17 – Public Key Infrastructure

nc pki.hackable.software 1337

This was a fun challenge, because it required many steps to complete. The first thing we notice is that MD5 is being used:

def h(x):
return int(hashlib.md5(x).hexdigest(), 16)

def makeMsg(name, n):
return 'MSG = {n: ' + n + ', name: ' + name + '}'

def makeK(name, n):
return 'K = {n: ' + n + ', name: ' + name + ', secret: ' + SECRET + '}'

def sign(name, n):
k = h(makeK(name, n))
r = pow(G, k, P) % Q
s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q
return (r*Q + s)


Naturally, we cannot register as $\texttt{admin}$. An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the $\texttt{admin}$ account. What if we can create a collision in $r$ while keeping $s$ distinct?

from coll import Collider, md5pad, filter_disallow_binstrings
import os

random_string = os.urandom(64)

# nullpad the prefix so that it does not interfere
# with the two collision blocks
prefix = nullpad(b'K = {n: ')
suffix = b', name: groci, secret:'

collider = Collider()
collider.bincat(prefix)
collider.safe_diverge()
c1, c2 = collider.get_last_coll()
collider.bincat(suffix)
cols = collider.get_collisions()

# here are our collisions!
A = next(cols)
B = next(cols)


The above code creates a collision such that k = h(makeK(name, n)) generates the same value. The problem is that the server does not return the signature, but str(pow(sign(name, n), 65537, int(n.encode('hex'), 16))).

To get the signature, which is computed as $Z = (r \cdot Q + s)^{65537} \mod M$, we need to perform some additional computations. Obviously, we could factor the modulus $M$ and compute $\phi(M)$ and then obtain the signature as easy as $Z^{65537^{-1} \mod \phi(M)}$… but factoring…

The probability that it is smooth enough is not very high. Also, the number is around $300$ digits so not a good candidate for msieve or other factoring software… so what then?

Well… what if $2^{96} \cdot A + c$ and $2^{96} \cdot B + c$ both are prime? Then, we can easily recover the signature as $Z^{65537^{-1} \mod (M-1)}$! No need for time-consuming factoring! Embodied in Python, it could look like this:

import hashlib
from Crypto.Util.number import isPrime

def num2b(i):
c = hex(i).strip('L')
c = (len(c) % 2) * '0' + c[2:]
return c.decode('hex')

A = int(A[64:64*3].encode('hex'), 16)
B = int(B[64:64*3].encode('hex'), 16)

# PURE BRUTEFORCE, NOTHING FANCY HERE!
# append the same data to both payload until
# they resulting numbers are BOTH prime
mul = 2 ** 96
for i in range(1, 2**20, 2):
if isPrime(AA + i) and isPrime(BB + i):
print AA+i
print BB+i
break


As an example, we obtain

$\begin{array}{rcl} n_1 &= & 105830311539247723296176540884596952305269885491629657210626981367998\\ &&347855559972583535368860650411949121405830046936667132754993342040282\\ &&396579458814796410615711380733886667185822027819749278255976029130752\\ &&166929087394904457033345839480235723175883533744993499706397792250975\\ &&3538392909994754306314762383722990106537161406818023\\ \end{array}$

and

$\begin{array}{rcl} n_2 &=& 105830311539247723296176540884596952305269885520672956204333681813273\\ &&006022550217898599044674310459977554450027911751595002340337873829980\\ &&015343362188266640170082456168713800027076364038815247707214102650115\\ &&472228269311796278082939271876115926467296299772272093195558205398667\\ &&4873073960726016011965433749481512129478713571026663\\ \end{array}$

Putting this into action, we might do something like:

def connect(name, n):
name_encoded = base64.b64encode(name)
n_encoded = base64.b64encode(n)
server = remote('pki.hackable.software', 1337)
payload = 'register:' + name_encoded + ',' + n_encoded
return pow(int(server.recvline()), modinv(65537, n1-1), n1)

name = 'groci'
PORT = 1331

# Get first signature
r1, s1 = sig / Q, sig % Q

# Get second signature
sig = pow(int(server.recvline()), modinv(65537, n2-1), n2)
r2, s2 = sig / Q, sig % Q

# Make sure we got a nonce re-use
assert(r1 == r2)

# OK, use standard nonce re-use technique...
delta = modinv(((s1 - s2) % Q), Q)
k = ( ((z1 - z2) % Q) * delta) % Q
r_inv = modinv(r1, Q)
PRIVATE = (((((s1 * k) % Q) - z1) % Q) * r_inv) % Q

# Now that we know the private key,
# lets forge/sign the admin account!
n = 'snelhest'
k = h(makeK(name, n))

r = pow(G, k, P) % Q
s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q
sig = r*Q + s

name_encoded = base64.b64encode(name)
n_encoded = base64.b64encode(n)
server = remote('pki.hackable.software', 1337)
payload = 'login:' + name_encoded + ',' + n_encoded + ',' + base64.b64encode(num2b(sig))

$r_1 = 455070882754437660339639715779025537190883529105$ $s_1 = 719850042802710537609987071764516609303635832220$
$r_2 = 455070882754437660339639715779025537190883529105$ $s_2 = 584220801769294572739392594733340817152152143208$
Now, with our forced nonce re-use, we can use standard techniques to obtain the private key and sign our $\texttt{admin}$ account, which gives the flag
DrgnS{ThisFlagIsNotInterestingJustPasteItIntoTheScoreboard}!