Suggestion for proof of retrievability

(Originally posted here)

Scenario

In this scenario, $A$ and $B$ wants to distribute segments of their data (preferably encrypted). We do not care about coverage, we are trying to maximize the amount of remotely stored data. The game is essentially that any peer, will try to minimize their own storage requirements and thus maximize other peers’.

Protocol

Two peers $A$ and $B$ will repeatedly negotiate upon storage space according to the follwing protocol, where $A$ is prover and $B$ verifier. Let $S(B,A)$ be the set of segments owned by $B$ and stored by $A$ . Moreover, let $s \in S(B,A)$ be an abritrary segment and let $\text{sig}(s)$ denote the signature of $s$ .

1. $B$ picks a random string $r$ of length $n$ bits (equal to the length of the signature)
2. $B$ asks $A$ to send the closests segment from $S(B,A)$ , i.e., such that $\| r - \text{sig}(s) \|_1$ is minimized.
3. $B$ verifies the segment $s$ via the signature. Then, using the distance $\| r - \text{sig}(s) \|_1$ , $B$ can estimate the number of segments stored by $A$ .

Repeat until the variance is low enough. The procedure is performed both ways.

Approximating $\delta$

Intuitively, we can think of $S(B,A)$ as a random (non-linear) code $\mathcal{C}$ over $\mathbb{F}_2^n$ and the task is to find a minimum-weight codeword in $\mathcal{C} + r = \{ c + r | c \in \mathcal C\}$ . Then $N$ corresponds to the number of codewords in $\mathcal{C}$ .

Assume that A has stored $N$ segments. Without loss of generality, we can assume that $r$ is the all-zero string, hence transforming the problem to finding the minimum weight of $n$ binomial variables. Let $X_1, X_2, \dots, X_N \in \textsf{Bin}(n, \frac12)$ and $Z := \min(X_1, X_2, \dots, X_n)$ . Then with high probability and for larger values of $N$ ,

$\frac n2 - \sqrt{\frac n3 \log N} \geq E(Z) \geq \frac n2 - \sqrt{\frac n2 \log N}.$

The above can be obtained by Gaussian approximation and the conventional expectation of the minimum of Gaussian random variables. We omit the proof here. Of course, this can be pre-computed for reasonable values of $N$ .

Assume there exists a peer $A$ with infinite computing power that tries to minimize its required storage for a given minimum distance $d$ . Done in an optimal manner, $A$ will pick equidistant points in the space $\mathbb{F}_2^n$ . This corresponds to a perfect error-correcting code with minimum distance $d$. The covering-coding bound states that $d\leq n-k$ . For a perfect code, which has minimal size, we have $d = n-k$ . Therefore, the size of the code is $|\mathcal C| = 2^{n-d}$ , which is also the number of elements $A$ needs to store.

A glaring problem is that $A$ cannot arbitrarily pick points (since points must be valid signatures). The best $A$ can do is to decide upon a perfect code $\mathcal{C}$ (or pick one that is closest to the current set of points — which is a very hard problem). Then, $A$ will look for points $v$ and $v'$ that map to the same codeword $c \in \mathcal{C}$ and discard the point that is the farthest away from $c$ . For larger $n$ and smaller $d$ , it is not realistic to achieve the covering-coding bound since there in reality are not that many shared segments. So, even given infinite computation, $A$ will not be able to sample points until a perfect code is achieved.

The covering-coding bound serves as a crude estimation on how to set the parameters.

Simulating

In Figure $1$ , we see that the upper bound for expected minimum distance approximates $N$ for values larger than $2^7$ and $n = 256$ .

rZ9aT

Assume that $A$ send a signature $s$ along with the segment. Let

$\delta(r,s) = \|r - \text{sig}(s)\|_1 - \frac n2.$

$B$ can now use different bounds at its own choice. Assume that $\delta(r,s) = 100 - \frac{256}{2}.$ Then, using the expression

$N \approx \exp\left(-\frac 2n \cdot \delta(r,s) \cdot \text{abs}\left(\delta(r,s)\right) \right)$

$B$ determines that $A$ most likely has at least $458$ segments with high probability. Using the lower bound, $A$ has at least $9775$ segments.

So, what is all this?

The intention is to create a simplistic protocol for asserting that shared data actually is retrievable, based on a probabilistic model. This could serve as basis for shared storage, in which segments are distributed. Even if the storer does not have access to the segments it has distributed, it can use the protocol to verify that it can retrieve them without actually doing so.

Project Tuffe Part 3

Throttle design

The paradigm is minimalistic design. No unnecessary parts, it is just a handle which goes in two directions. Forward (left) is 5V, up is neutral (2.4 – 2.6 V) and back is 0V. The lever controls the 5 kΩ potentiometer via a 2:1 cog gear. The intention is to be able to control the force needed to change the thrust, but also move the applied force from the mechanical parts in the potentiometer to the handle.

throttle

Concept with power indicator

thr_pwr

Base mount

The mount is being made from thick stainless steel and is designed to allow for a few degrees of freedom. An elastic axial connection is used to reduce vibration. It is modular and contains three plates that are movable. One for the axis, one for the motor mount and one for the electronics mount.

base1

Electrical parts

Electronics and wiring that are complete:

Battery monitor
Key switch
High-voltage circuit with contactor

Electronics that remain:

Speedometer
Temperature control
RPM monitor

arduino

Components for this have been ordered on eBay. I will be using a GPS u-blox module to get the position, from which speed can be derived. Temperature is read from motor via analog interface (KTY84-130). The RPM is read from 12V Hall-effect sensor (this will be scaled down to 5V with a resistor bridge and a Schottky diode).

bridge

Everything will be presented on an OLED display, which I need to protect from moisture somehow. Suggestions are welcome. My initial idea is to use plexiglass on the front and backfill with epoxi.

Meter concept arts

meter2

pwrmeter

Project Tuffe Part 2

I have now received all components (except contactor and belt-drive wheels). In the below video, you can see the motor in action.

The battery is an eBike battery with 2.4 kWh of charge. At 4 knots, this would ideally drive the boat for roughly 4 hours.

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.

grocid.net

scribbles from past, present and possibly future

Author: Carl Löndahl