Implementing Turing machine using iptables...

Ok, today I decided that I'm going to try to implement Turing machine using iptables. From the start it was obvious to me that I'll use stream of IP packets as a tape. So, after reading a bit and thinking, I decided to implement this Turing machine. The reason I selected that particular one is because tape always moves to the right, and that simplifies things a lot. More precisely, I decided to implement example given in the linked Wikipedia article.

Now, next problem, after deciding which Turing machine to implement, was where to keep internal state of a Turing machine. For that part I found that I can have mark value (32bit number, i.e. state) per connection. In other words, this means that testing current state is performed with the following test:

-m conntrack --mark <desiredstate>

and to set new state I have to use:

-j CONNTRACK --set-mark <newstate>

It also means that packets that belong to a tape should belong to a single connection, i.e. TCP connection.

Also, I had to decide where to keep content of a cell. There are different possibilities, but for now the simplest one is to use MARK target. So, to test a value of the cell I use:

--mark <cellvalue>

and to set it, I use

-j MARK --set-mark <cellvalue>

The last bit is initialization, i.e. to set initial state, and halting. To set initial state I used state tracking feature of connections in iptables, i.e. the following test:

-m state --state NEW -j CONNTRACK  --set-mark <initialstate>

finally, to halt machine, I set connection tracking state to special state in which no iptable rule will be triggered again.

So, let me show initial version of a shell script that makes this a bit "higher level". First, some initializations, i.e. tape and states definitions:

# Tape is a stream of IP packets belonging to a single TCP connection

TAPE="-s 192.168.0.1 -d 192.168.0.2 -p tcp --dport 80 --sport 10000"

# States, assigned arbitrarily integer values

STATE_A=1

STATE_B=2

STATE_C=3

# Halt state

HALT=4          # Halt state, no instruction will be executed in this state

# Tests when Turing machine is in a particular state

IN_STATE_A="-m connmark --mark $STATE_A"

IN_STATE_B="-m connmark --mark $STATE_B"

IN_STATE_C="-m connmark --mark $STATE_C"

# Actions to change a state of a Turing machine

SET_STATE_A="-j CONNAMRK --set-mark $STATE_A"

SET_STATE_B="-j CONNAMRK --set-mark $STATE_B"

SET_STATE_C="-j CONNAMRK --set-mark $STATE_C"

Next, few pseudo instruction:

INITIALIZE_STATE_A="-m state --state NEW --mark $STATE_A"

# Reading a symbol from a tape, i.e. packet

READ_SYMBOL_0="--mark 0"

READ_SYMBOL_1="--mark 1"

# Writing a symbol to a tape, i.e. packet

WRITE_SYMBOL_0="-j MARK --set-mark 0"

WRITE_SYMBOL_1="-j MARK --set-mark 1"

# Short-hand "pseudo-instruction" to add instruction to a Turing machine

ADD_TURING_INSTRUCTION="iptables -A INPUT $TAPE"

Finally, all the instructions:

# If in state A and symbol 0 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL0 $SET_STATE_B

# If in state A and symbol 0 was read write symbol 1 and go to state C

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL1 $SET_STATE_C

# If in state B and symbol 0 was read write symbol 0 and go to state A

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL0 $SET_STATE_A

# If in state B and symbol 1 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL1 $SET_STATE_B

# If in state C and symbol 0 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL0 $SET_STATE_B

# If in state C and symbol 1 was read write symbol 1 and halt

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL1 $HALT

# Initialize Turing machine

$ADD_TURING_INSTRUCTION $INITIALIZE_STATE_A

Note that I have to use two iptables commands in order to implement writing a symbol and transitioning to a new state. The reason is that I can have only one target per iptables command. Certainly, it could be hidden by making those variables and pseudo-instructions fancier, but, for now this will do...

This particular  Turing machine didn't require me to have transition to a new state without moving a tape. But, there is a solution for this too. All rules have to be placed in a single user-defined chain, and then when no tape movement is required just use -g (iptables' goto target) and start all rules from start. In efect, what will happen is that all the rules will be executed again on the same packet which means on the same cell. So elegant, isn't it? :)

Nastanak novca i dug...

Danas sam naletio na jedn zanimljiv intervju. Mislio sam da se radi o razjašnjavanju pojma duga države o kojemu se stalno priča, ali je na kraju ispalo da se radi o nečemu širemu, a uključuje između ostalog i pitanje kako je nastao novac.

U školi su nas učili kako je prvotni način trgovanja bila trampa te da je novac izmišljen kao posljedica neadekvatnosti trampe (Imaš kravu i trebaš moje piliće, ali meni krava ne treba. :)). Tek nakon što je izmišljen novac, dolazi do pojave posudbe i kreditiranja. Ta hipoteza o nastanku novca vuče se barem od Adama Smitha i njegovog rada Bogatstvo naroda.

Međutim, na stranici koju sam spomenuo na početku nalazi se intervju s Davidom Graeberom. Preporučio bih da ipak pogledate ukratko što Wikipedija kaže o njemu budući da mi se čini kako njegovi opći stavovi dosta utječu i na njegovo razmišljanje, ili obratno - svejedno. U tom intervjuu on tvrdi kako je to u stvari obrnut redoslijed, tj. prvo je nastala posudba i kreditiranje, potom novac, a kada bi se skršio monetarni sustav onda bi se pribjegavalo trampi. Kada ovako, kao laik, malo razmislim o tome, čini mi se vrlo logično. Na kraju krajeva, u Hrvatskoj su vrlo popularne kompenzacije ovih godina, a razlog za to je što financijski sustav baš ne funkcionira (opet, zaključujem to kao laik). No, čini mi se da je glavni problem kako bi se utvrdilo koja teza je točna u tome što se već u najstarijim pisanim zapisi koji sežu 3200 godina prije Nove ere i koji su nastali u Mezopotamiji nalaze tragovi novca i financijskog sustava. Prema tome, novac je nastao ranije i za to nema pisanih tragova.

U drugom dijelu intervjua naglasak je na trenutnoj dužničkoj situaciji u svijetu. Koliko god u Hrvatskoj mislili da se živi na kredit i da je to nečuveno, na zapadu izgleda nije ništa bolje, pogotovo u Americi. Jedna od stvari s kojom se slažem je da mi se čini sasvim prirodno da ljudi uvijek kukaju kako žive u najtežim vremenima, ali da je svako vrijeme teško na svoj način. Nadalje, po njemu, ciklusi dužničkih kriza su se stalno ponavljali, ali to su ciklusi koji traju po 500tinjak godina. No, u novije vrijeme ti ciklusi se skraćuju, a stare metode otpisivanja dugova se više ne mogu primijeniti iz različitih razloga.

Čitajući ovaj intervju saznao sam još podosta stvari, a to u stvari čini čitanje takvih tekstova isplativo. Prvo, za sociologa Marcela Maussa koji je napisao vrlo utjecajnu knjigu The Gift. Marcel Mauss u toj knjizi analizira što je moglo potaknuti razvoj novca ako to nije trampa te je po njegovoj tezi to bio poklon. Ako sam dobro shvatio, osnovna teza je da ako ja nekome poklonim nešto, onda taj netko se osjeća dužan meni vratiti. Naravno da to ne vrijedi za apsolutno svaku situaciju. Zanimljivost je i da se ta analiza proteže na otvoreni kod.

Zatim, tu su različite ekonomske teorije novca (commodity theory of money, monetary circuit theory, chartalist theory of money) i općenito problem teorije novca koji meni kao laiku izgleda nepostojeći, ali je stvaran i vrlo problematičan.

Za kraj, ima priličan broj komentara na kraju koje također treba pročitati kako bi se vidjela i druga strana (ako ju je tko iznio). Uglavnom, namjeravam to jednom...

CAs are broken... but... there may be a fix...

Everyone by now heard of security breach of DigiNotar. The Internet is full of stories about it! I won't go into details what happened. Instead, I'll try to pinpoint what actual problem is, and, based on that, I'll try to outline possible solution.

Let us start with the problem. The problem is that every single CA is actually single point of failure of the whole distributed system. Do you need fraudulent Google certificate? No problem, attack the weakest CA you can find, or try to attack more of them, and there you go.  Now, I can here you say: Remove weakest CA! Well, it's not so easy. Applying this rule recursively you'll end up with one, or no CAs at all. This is not a solution either. And this also adds another dimension to the problem, the less CAs the more fragile the Internet becomes because each CA is anyway highly likely target. And you know the main premise of security: You are never ever absolutely secure!

So, what is the solution? I believe that the solution is to keep the system as it is, but to introduce signatures from multiple CAs in a single certificate. This won't resolve the problem, but it will make life harder to hackers. Besides, absolute security doesn't exist, as I already mentioned.

From the implementation standpoint, it is possible to do this either by changing certificate structure, or to change implementations so that they can check multiple certificates. In case multiple certificates are used it's obviously necessary to have some common information that will allow all those certificates to be related.

Validity of certificate (or certificates) could be calculated probabilisticaly. Additionally,  some independent measure of correlation between CAs could be defined so that the validity of a single site that uses this system can be evaluated based on this correlation measure (meaning, the less correlated CAs signed the more valid it is).

Note that if a single CA goes into bankruptcy, or is removed from trusted CA list, doesn't mean that everyone has to issue a new certificate imediatelly.

I would say that CAs implemented this way would be somewhere between current CA system and PGP Web of Trust.