Monday, March 30, 2020

The Weird World of Cryptographic Programming Languages

In this post I will be showing programming languages that rely on self-encryption and what not to make programming in it as hard as possible.

First one: SHAFuck (Gregor Richards).

SHAFuck is a BrainFuck derivative that relies on the SHA1 hash of each 1024-bit chunk of the program data and executes the hash as code (I assume it runs the binary data of the hash through BinaryFuck)

Here's a program that prints "Hello, World!" (compressed through bzip2):

Second one: Malbolge (Ben Olmstead)

This one uses functions that ARX (add, rotate, XOR) ciphers use (such as Speck and Simon or hash functions such as Blake). In particular, it relies on the tritwise "crazy" operator instead of the bitwise XOR operator and also relies on tritwise rotations (yes, trit sounds wrong but just ask a French speaker what they think about the term "bits" for binary digits). Get ready, this language is named after the eighth circle of hell in Dante's Inferno. It took years before the first program was found by a computer program designed by Andrew Cooke. Nowadays programs generators exist (even online).

So how does it work? This was confusing to me at first but I think I understand it now.
Malbolge has 3 registers (a, c ,d). A is the accumulator, it is set to the value written by all write operations on memory and used for input/output. C is the instruction pointer. D is the data pointer.

Malbolge takes the code instruction [c], adds c to it and divides it by 94, the remainder is what is interpreted as an instruction. The rest are the instructions:

If the remainder is:
4 : Jump to instruction [d]. It copies the value [d] to c (note that c increments every instruction just like every programming language that goes left to right).

5 : Print the ascii value of a.

23 : Input a single ASCII character and store it in a.

39 : Tritwise rotates the value [d] by one trit, stores it in [d] and a.

40 : Copies the value [d] into d.

62 : Does the "crazy" operator with the value of [d] and the value of a. Stores at both [d] and a.

68 : Nop (no-operation).

81 : Halts the VM.

Any other value is also a no-op like 68.


The crazy operation is a logic gate: For example let me show you the logic gate XOR

      0  1
      _  _
0   |0  1
1   |1  0

Now for crazy:

      0  1  2
      _  _  _
0   |1  0  0
1   |1  0  2
2   |2  2  1

It encrypts the trits of the 2 ascii values. After every instruction, the value at [c] is replaced with itself modulo 94 and then encrypted as follows:

ORIGINAL:    !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
TRANSLATED:  5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@

Finally, after that is performed, c and d are incremented modulo 59049 and the execution cycle repeats.

Third one: Cryptoleq.

Subleq is a turing-complete function that runs as follows:
It's name is a shortened version of "SUBtract and branch if Less than or EQual to zero". This language has only one instruction making it an OISC. This is similar but it is cryptographic. Unlike other ones I discussed here, this one is quite fast (assuming you have the right hardware to execute this code) and generally subleq can run quite fast despite how hard it can be to code in at times. IBM made the IBM 1620, A great computer at the time (this was 1960, computers looked completely different, see the PDP-7 (what Unix was built on!). This was nicknamed CADET for "Computer with ADvanced Economic Technology" (although it jokingly can also be named "Can't Add, Doesn't Even Try"). Back on topic to Cryptoleq, it is a close relative to Subleq, where Subleq programs can run on Cryptoleq, making it backwards-compatible and also Turing-complete. I still haven't wrapped my head around how it works but there are a few resources on it: Esolang Wiki, the paper on it, Wikipedia, Github.

Fourth one: ROTFuck.

Back to BrainFuck derivatives, this one has the instructions rotated by one each time an instruction is called. It's more of a rotation cipher, ROT13-esque basic cipher you may have made then you were really young and just learned the Caesar Cipher, but still fun as it's a good challenge and also because of the fact that ARX architecture exists as I mentioned on the Malbolge paragraph. the instructions go as follows:

Since the "Hello, World!" program was never completed, I will now complete it.
Don't interpret this as BrainFuck. It will give you a lot of errors.

Thursday, March 26, 2020

An unexpected Tron-like CA with multiple states based off Cyclic Cellular Automata

I'm making this in my own CA program, Mucell. Mucell is an easy-to-use expansion of the CA program MJCell.

I was just fooling around with Margolus neighborhoods and Cyclic CA when I found this.

The rule in Moore neighborhoods is really chaotic and unstable (arguably the same with Margolus neighborhoods) but then I noticed something familiar. When running in a Margolus neighborhood it produced the same exact patterns as one block CA called Tron, made by Norman Margolus. It's quite simple: It inverts the block states (0 to 1, 1 to 0) if all states in the block are the same. It's a classic example of reversible cellular automata and chaos. See more on the wikipedia section on it here. Because of the fact that it inverts states every iteration, the backdrop is constantly changing from black to white which is seizure-inducing (see for yourself with (one of) these programs.) I accidentally found a solution to get rid of this effect by using multiple states and the following rule:

Each cell always increments by a value of 1 unless it is a 0. A cell that is 0 will increment only if it has a non-zero neighbor. When a cell's value reaches the maximum number of states, it is reset to 0 (in other words, all values are modulo the number of states).

The results from this rule looks like such:

(using Lenna as an example to show how chaotic patterns result)

Initial state:

After 1 iteration:

After 2 iterations:
Here's the CA on a single cell: (This is exactly how Tron behaves)

Monday, March 9, 2020

Cellular automata (and other chaotic systems) gallery, March 2020.

Combinations: A glider destroying what pattern was once there

Strange Attractors: Fractal Dream 3 (evolution of)

Stochastic Cellular Automata: Modelling Virus Spread (inspired by this video)

Langton's Ant: A colorful version of rule LLRR (visit here for the live version)

Hodgepodge Machine: Algae

Wednesday, February 19, 2020

Combinations Cellular automata

I thought up a 1D cellular automata that has a neighborhood size of 2 that checks odd/even indexed pairs, staring odd and returns any number smaller than the number of states (this is based on the rulestring). If the rulestring is (2^X) characters long, there are X+1 states. It doesn't look that interesting in 2 states except the fact that XOR (rule 6) makes a Sierpinski triangle.
The only other logic gate that has a 50/50 chance of returning a 1 or a 0 is XNOR. it did some sort of inverted Sierpinski triangle.
With only 2 states, we get only 16 rules, which gets boring. Up to 3 states, things get interesting.
I call this one the disfigured Sierpinki.
Looks like a bunch of stretched Sierpinski's.
Images by Jason Rampe, made in Visions of Chaos