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 🙂

Project Tuffe

This is a post somewhat out of the ordinary. If you have no interest in boats, then read no further 😉

Background

I have a boat, an Adec 530, equipped with an old Volvo Penta MB10A (15 HP) from 1976. The motor runs fairly well; it is not consuming a lot of gas and there is really no big fault with it, except that it occasionally leaks cooling water. It has the characteristic sound a two-cylinder inboard boat engine. But I do not expect this engine to run forever, without having to spend a lot of money on a slowly diminishing supply of parts. Also, I am not fond of the the gasoline fumes which are emitted from the engine. The idea of having a clean, near-silently running engine has is alluring.

So, I started to to look at various options. Obviously, electric drive is the conclusion most people would arrive at. The biggest problem with electric drive is the reach of the boat. We need to store energy. The amount of energy contained in one litre of gas and diesel is about 10 kWh. It is a very efficient way to storing energy. The efficiency of a gas motor is ideally 30 %, while on a diesel engine it can be as high as 50 %.

Storing charge

Today, a lot of electric cars are equipped with lithium-ion batteries and an electric motor for propulsion. While the lithium-ion is a good technology, it is not very safe. There are several incidents where people have gotten injured from exploding electronical devices such as phones. This is not something I would like to happen, especially not when you are on a boat.

Acid batteries are also an option, but those are heavy and are sensitive to deep discharge. For instance, a battery of with a charge capacity of 100 Ah should ideally not be discharged below 50 Ah. There are acid-battery technology such as AGM, which address this problem by using thicker lead electrodes and storing the electrolyte (sulfuric acid) embedded in fiberglass mats. However, these batteries are quite expensive and weight about the same as normal acid-based batteries. These are indeed a competetive option. There are other types of acid-based batteries as well, but AGM seems to be the best option.

Lastly, we have LiFePO4 batteries, a more recent type of lithium-based batteries. This, reportedly much safer technology in comparison to regular lithium-ion technology, is the most expensive option. However, the life expectancy of a LiFePO4 cell is much longer than the alternatives, making it less expensive than the above in the long run.

Propulsion

For the engine, I took some inspiration from electric cars. While 230 VAC electric motors are cheap, you need to convert the stored energy into alternating current and raise the voltage. This is not necessarily bad, but it increases the complexity of the solution and there will be a loss of energy in the conversion. Therefore, I decided that a 48 VDC engine would be a suitable option.

There are a few types of electric motors for DC. Brushed motors are cheap but the brushes have a limited life and that would require continuous maintenance, which I like to avoid. Brushless motors (based on Hall effect), have for a long time been expensive, but in recent years they have gotten much cheaper.

The effect required to match the current engine would be around 10 kW. However, I decided to go with a slightly weaker engine. The HPM-5000 from Golden Motor delivers 5 kW of continuous power, which is with my estimates enough for a small boat as mine.

Initial schematic

The following is an initial schematic for how the engine and powerbank will be connected:

schematic

During this weekend I will hopefully order the parts.

Edit: I have ordered the motor and controller now, which hopefully arives next week.

Edit2: Messy desk

photo_2018-07-05_22-22-42

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

Now we are ready to build Google Authenticator.

$ ./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.

Adding some notifications

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.

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

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?}

Google CTF Crypto Backdoor

crypto-backdoor

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()

grocid.net

scribbles from past, present and possibly future

Author: Carl Löndahl