2018-02-08

Yo

Sometimes you just want to set something and forget it. Other times, you want to set something and get a notification when it finishes. There are a ton of different notification mechanisms that have been devised over the years, from email to pagers to texts to tweets.

And those are all fine, but they can be overkill. You may not even have a machine with access to a mail server if you are draconian about how you security partition your mail relays on your network. So I started playing with Yo.

Yo is a minimalist social media platform. It's Twitter without the tweets. It's a binary notification mechanism: you either get a "yo" or you don't. The content, and therefore the meaning, of the yo is left to your interpretation. This is perfect for our needs.

The Yo API is trivial and can be triggered with curl or any HTTP POST method-capable tool of your choice. On Windows, I like to use Powershell. If I have something I'm running on Windows and I just want to get a yo when it's done, I can do so with a Yo account, the API key, and some scripting:

# Convert Yo API key to a secure string object and save it to disk
$yo_file_name   = [System.IO.Path]::Combine(${Env:UserProfile}, 'Desktop', 'yo_key.xml')
$yo_target      = 'MY_YO_ACCOUNT'

$sec_str        = ConvertTo-SecureString -AsPlainText -Force -String 'YO_API_KEY_HERE'
Export-CliXml -InputObject $sec_str -Force -Encoding 'UTF8' -Path $yo_file_name

$yo_key_sec_str = Import-CliXml -Path (Get-Item -Path $yo_file_name).FullName
$yo_key_sec_ptr = [System.Runtime.InteropServices.Marshal]::SecureStringToBSTR($yo_key_sec_str)
$yo_key         = [System.Runtime.InteropServices.Marshal]::PtrToSTringBSTR($yo_key_sec_ptr)

$yo_send_properties = @{
  'Body'   = "api_token={0}&username={1}" -f ($yo_key, $yo_target);
  'Method' = 'POST';
  'Uri'    = 'http://api.justyo.co/yo/';
}
Clear-Variable -Name yo_key
[System.Runtime.InteropServices.Marshal]::ZeroFreeBSTR($yo_key_sec_ptr)

$err = $null
Do-Something -ErrorVariable err
if ([String]::IsNullOrEmpty($err)) {
  $yo_send_properties.Body += '&link=ok' # including a link is optional
} else {
  $yo_send_properties.Body += '&link=fail'
}
Invoke-RestMethod @yo_send_properties
Clear-Variable -Name yo_send_properties

Including a link (well, a "link") along with the yo isn't necessary — and potentially very un-yolike — but it lets me know if the thing I'm letting run succeeded or not. If I only want to know it's finished and I don't care about the result, or if there is no result to know, I could simply do the thing and then send the yo:

Do-Something
Invoke-RestMethod @yo_send_properties

If I want to run a program, it might look like this:

$proc = Start-Process -FilePath 'myprogram.exe' -ArgumentList $program_args -PassThru
$proc.WaitForExit()
Invoke-RestMethod @yo_send_properties

Yo is threatening to go offline soon if you don't join their Patreon, so this advice may be short-lived.

2018-02-05

ChaCha20 in Powershell

I couldn't sleep the other night so to pass the time, naturally, I wrote a ChaCha20 implementation in Powershell.

ChaCha20 is a variant of Salsa20 and promises better input diffusion and, in some cases, a speed improvment.

Given the Salsa20 Powershell implementation from last week year, you'd want to add a new ChaCha20 function:

Function ChaCha20-QuarterRound {
  Param(
    [Ref] $a,
    [Ref] $b,
    [Ref] $c,
    [Ref] $d
  )
  $a.Value = Salsa20-Sum $a.Value $b.Value; $d.Value = Salsa20-Rotate ($d.Value -bxor $a.Value) 16
  $c.Value = Salsa20-Sum $c.Value $d.Value; $b.Value = Salsa20-Rotate ($b.Value -bxor $c.Value) 12
  $a.Value = Salsa20-Sum $a.Value $b.Value; $d.Value = Salsa20-Rotate ($d.Value -bxor $a.Value) 8
  $c.Value = Salsa20-Sum $c.Value $d.Value; $b.Value = Salsa20-Rotate ($b.Value -bxor $c.Value) 7
}

and then edit your Salsa20-Core logic from this:


for ($i = $Rounds; $i -gt 0; $i-=2) {
  $x4  = $x4  -bxor (Salsa20-Rotate (Salsa20-Sum $x0  $x12) 7)
  $x8  = $x8  -bxor (Salsa20-Rotate (Salsa20-Sum $x4  $x0)  9)
  $x12 = $x12 -bxor (Salsa20-Rotate (Salsa20-Sum $x8  $x4)  13)
  $x0  = $x0  -bxor (Salsa20-Rotate (Salsa20-Sum $x12 $x8)  18)
  [...snip...]
  $x12 = $x12 -bxor (Salsa20-Rotate (Salsa20-Sum $x15 $x14) 7)
  $x13 = $x13 -bxor (Salsa20-Rotate (Salsa20-Sum $x12 $x15) 9)
  $x14 = $x14 -bxor (Salsa20-Rotate (Salsa20-Sum $x13 $x12) 13)
  $x15 = $x15 -bxor (Salsa20-Rotate (Salsa20-Sum $x14 $x13) 18)
}

to this:

for ($i = $Rounds; $i -gt 0; $i-=2) {
  ChaCha20-QuarterRound ([Ref]$x0) ([Ref]$x4) ([Ref]$x8)  ([Ref]$x12)
  ChaCha20-QuarterRound ([Ref]$x1) ([Ref]$x5) ([Ref]$x9)  ([Ref]$x13)
  ChaCha20-QuarterRound ([Ref]$x2) ([Ref]$x6) ([Ref]$x10) ([Ref]$x14)
  ChaCha20-QuarterRound ([Ref]$x3) ([Ref]$x7) ([Ref]$x11) ([Ref]$x15)
  ChaCha20-QuarterRound ([Ref]$x0) ([Ref]$x5) ([Ref]$x10) ([Ref]$x15)
  ChaCha20-QuarterRound ([Ref]$x1) ([Ref]$x6) ([Ref]$x11) ([Ref]$x12)
  ChaCha20-QuarterRound ([Ref]$x2) ([Ref]$x7) ([Ref]$x8)  ([Ref]$x13)
  ChaCha20-QuarterRound ([Ref]$x3) ([Ref]$x4) ([Ref]$x9)  ([Ref]$x14)
}

You'd want do that, but you shouldn't. You should inline the work in the core directly for performance reasons. Also, the inputs are different as per page 5 of the paper and ChaCha20 flips the nonce and IV:

Salsa20:

void ECRYPT_ivsetup(ECRYPT_ctx *x,const u8 *iv)
{
  x->input[6] = U8TO32_LITTLE(iv + 0);
  x->input[7] = U8TO32_LITTLE(iv + 4);
  x->input[8] = 0;
  x->input[9] = 0;
}

ChaCha20:

void ECRYPT_ivsetup(ECRYPT_ctx *x,const u8 *iv)
{
  x->input[12] = 0;
  x->input[13] = 0;
  x->input[14] = U8TO32_LITTLE(iv + 0);
  x->input[15] = U8TO32_LITTLE(iv + 4);
}

The change from inputs 6,7,8,9 to 12,13,14,15 isn't critical if you read page 5. What's important is that the last two 32-bit values in Salsa20 (input[8] and input[9]) are the nonce (the zeroes), whereas in ChaCha20, they are the first (input[12] and input[13]).

The ChaCha20-Core function in Powershell is similar to the Salsa20-core:

Function ChaCha20-Core {
  Param(
    [Parameter(Mandatory=$True,Position=0)]
    [Byte[]] $k,
    [Parameter(Mandatory=$True,Position=1)]
    [Byte[]] $in,
    [Parameter(Mandatory=$False,Position=2)]
    [Byte] $Rounds = 20
  )

  [UInt32] $j0  = $x0  = Salsa20-LoadLittleEndian  $c[ 0..3]
  [UInt32] $j1  = $x1  = Salsa20-LoadLittleEndian  $c[ 4..7]
  [UInt32] $j2  = $x2  = Salsa20-LoadLittleEndian  $c[ 8..11]
  [UInt32] $j3  = $x3  = Salsa20-LoadLittleEndian  $c[12..15]
  [UInt32] $j4  = $x4  = Salsa20-LoadLittleEndian  $k[ 0..3]
  [UInt32] $j5  = $x5  = Salsa20-LoadLittleEndian  $k[ 4..7]
  [UInt32] $j6  = $x6  = Salsa20-LoadLittleEndian  $k[ 8..11]
  [UInt32] $j7  = $x7  = Salsa20-LoadLittleEndian  $k[12..15]
  [UInt32] $j8  = $x8  = Salsa20-LoadLittleEndian  $k[16..19]
  [UInt32] $j9  = $x9  = Salsa20-LoadLittleEndian  $k[20..23]
  [UInt32] $j10 = $x10 = Salsa20-LoadLittleEndian  $k[24..27]
  [UInt32] $j11 = $x11 = Salsa20-LoadLittleEndian  $k[28..31]
  [UInt32] $j12 = $x12 = Salsa20-LoadLittleEndian $in[0..3]
  [UInt32] $j13 = $x13 = Salsa20-LoadLittleEndian $in[4..7]
  [UInt32] $j14 = $x14 = Salsa20-LoadLittleEndian $in[8..11]
  [UInt32] $j15 = $x15 = Salsa20-LoadLittleEndian $in[12..15]

  for ($i = $Rounds; $i -gt 0; $i-=2) {
    $x0 = Salsa20-Sum $x0 $x4;   $x12 = Salsa20-Rotate ($x12 -bxor $x0)  16
    $x8 = Salsa20-Sum $x8 $x12;   $x4 = Salsa20-Rotate ($x4  -bxor $x8)  12
    $x0 = Salsa20-Sum $x0 $x4;   $x12 = Salsa20-Rotate ($x12 -bxor $x0)   8
    $x8 = Salsa20-Sum $x8 $x12;   $x4 = Salsa20-Rotate ($x4  -bxor $x8)   7

    $x1 = Salsa20-Sum $x1 $x5;   $x13 = Salsa20-Rotate ($x13 -bxor $x1)  16
    $x9 = Salsa20-Sum $x9 $x13;   $x5 = Salsa20-Rotate ($x5  -bxor $x9)  12
    $x1 = Salsa20-Sum $x1 $x5;   $x13 = Salsa20-Rotate ($x13 -bxor $x1)   8
    $x9 = Salsa20-Sum $x9 $x13;   $x5 = Salsa20-Rotate ($x5  -bxor $x9)   7

    $x2 = Salsa20-Sum $x2 $x6;   $x14 = Salsa20-Rotate ($x14 -bxor $x2)  16
    $x10 = Salsa20-Sum $x10 $x14; $x6 = Salsa20-Rotate ($x6  -bxor $x10) 12
    $x2 = Salsa20-Sum $x2 $x6;   $x14 = Salsa20-Rotate ($x14 -bxor $x2)   8
    $x10 = Salsa20-Sum $x10 $x14; $x6 = Salsa20-Rotate ($x6  -bxor $x10)  7

    $x3  = Salsa20-Sum $x3 $x7;  $x15 = Salsa20-Rotate ($x15 -bxor $x3)  16
    $x11 = Salsa20-Sum $x11 $x15; $x7 = Salsa20-Rotate ($x7  -bxor $x11) 12
    $x3  = Salsa20-Sum $x3 $x7;  $x15 = Salsa20-Rotate ($x15 -bxor $x3)   8
    $x11 = Salsa20-Sum $x11 $x15; $x7 = Salsa20-Rotate ($x7  -bxor $x11)  7

    $x0  = Salsa20-Sum $x0 $x5;  $x15 = Salsa20-Rotate ($x15 -bxor $x0)  16
    $x10 = Salsa20-Sum $x10 $x15; $x5 = Salsa20-Rotate ($x5  -bxor $x10) 12
    $x0  = Salsa20-Sum $x0 $x5;  $x15 = Salsa20-Rotate ($x15 -bxor $x0)   8
    $x10 = Salsa20-Sum $x10 $x15; $x5 = Salsa20-Rotate ($x5  -bxor $x10)  7

    $x1  = Salsa20-Sum $x1 $x6;  $x12 = Salsa20-Rotate ($x12 -bxor $x1)  16
    $x11 = Salsa20-Sum $x11 $x12; $x6 = Salsa20-Rotate ($x6  -bxor $x11) 12
    $x1  = Salsa20-Sum $x1 $x6;  $x12 = Salsa20-Rotate ($x12 -bxor $x1)   8
    $x11 = Salsa20-Sum $x1 $x12;  $x6 = Salsa20-Rotate ($x6  -bxor $x11)  7

    $x2 = Salsa20-Sum $x2 $x7;   $x13 = Salsa20-Rotate ($x13 -bxor $x2)  16
    $x8 = Salsa20-Sum $x8 $x13;   $x7 = Salsa20-Rotate ($x7  -bxor $x8)  12
    $x2 = Salsa20-Sum $x2 $x7;   $x13 = Salsa20-Rotate ($x13 -bxor $x2)   8
    $x8 = Salsa20-Sum $x8 $x13;   $x7 = Salsa20-Rotate ($x7  -bxor $x8)   7

    $x3 = Salsa20-Sum $x3 $x4;   $x14 = Salsa20-Rotate ($x14 -bxor $x3)  16
    $x9 = Salsa20-Sum $x9 $x14;   $x4 = Salsa20-Rotate ($x4  -bxor $x9)  12
    $x3 = Salsa20-Sum $x3 $x4;   $x14 = Salsa20-Rotate ($x14 -bxor $x3)   8
    $x9 = Salsa20-Sum $x9 $x14;   $x4 = Salsa20-Rotate ($x4  -bxor $x9)   7
  }

  $x0  = Salsa20-Sum $x0 $j0
  $x1  = Salsa20-Sum $x1 $j1
  $x2  = Salsa20-Sum $x2 $j2
  $x3  = Salsa20-Sum $x3 $j3
  $x4  = Salsa20-Sum $x4 $j4
  $x5  = Salsa20-Sum $x5 $j5
  $x6  = Salsa20-Sum $x6 $j6
  $x7  = Salsa20-Sum $x7 $j7
  $x8  = Salsa20-Sum $x8 $j8
  $x9  = Salsa20-Sum $x9 $j9
  $x10 = Salsa20-Sum $x10 $j10
  $x11 = Salsa20-Sum $x11 $j11
  $x12 = Salsa20-Sum $x12 $j12
  $x13 = Salsa20-Sum $x13 $j13
  $x14 = Salsa20-Sum $x14 $j14
  $x15 = Salsa20-Sum $x15 $j15

  $out = @()
  $out += Salsa20-StoreLittleEndian $x0
  $out += Salsa20-StoreLittleEndian $x1
  $out += Salsa20-StoreLittleEndian $x2
  $out += Salsa20-StoreLittleEndian $x3
  $out += Salsa20-StoreLittleEndian $x4
  $out += Salsa20-StoreLittleEndian $x5
  $out += Salsa20-StoreLittleEndian $x6
  $out += Salsa20-StoreLittleEndian $x7
  $out += Salsa20-StoreLittleEndian $x8
  $out += Salsa20-StoreLittleEndian $x9
  $out += Salsa20-StoreLittleEndian $x10
  $out += Salsa20-StoreLittleEndian $x11
  $out += Salsa20-StoreLittleEndian $x12
  $out += Salsa20-StoreLittleEndian $x13
  $out += Salsa20-StoreLittleEndian $x14
  $out += Salsa20-StoreLittleEndian $x15

  Return $out
}

It's longer than just calling ChaCha20-QuarterRound a few times, but the ChaCha20-QuarterRound method is about 23% slower, which is why I'm writing this. An initial test of these Powershell functions had the pass-by-reference method approximately 7% faster on one box and 5% slower on another for a 65,535-byte string. A lot of this is machine-dependent, I know, and I haven't even mentioned CPU statistics or cycle counts yet. I was originally planning on saying "Here ya go! Here's ChaCha20 in Powershell! Good luck, everybody!" and be on my way, but I noticed this -5 to +7% difference and wanted to figure out why. I got curious about how to measure performance between the two algorithms, and compare them against an AES-128 implemention. Performance measurement is hard, folks.

I took a swing at it, generating a few hundred strings of various lengths and measuring the total time taken to encrypt them. To minimize I/O as a bottleneck I eliminated any writing-to-disk. For simplicity, I kept everything linear and in memory. If you want to split work up into multiple cores, more power to you. (As a note, Salsa20 and its variants are great at parallelization. Since you can encrypt block n of your message without having to know anything about block n-1, you could take your message and key, divide the message by 64 bytes, and simultaneously encrypt those (message/64) blocks, say one per core, and stitch them back together again when they've all completed. But that's extra credit.)

A serious benchmark is probably — no, definitely — more work than this implementation merits, but I wrote a modest approximation. First, create a function to create strings:

Function New-String {
  Param(
    [UInt16] $Length = 16
  )
  [String] $out = ''

  for ($i = 0; $i -lt $Length; $i++) {
    $out += [Char] (Get-Random -Minimum 33 -Maximum 126)
  }
  Return $out
}

Then use that function to generate strings of given lengths and measure how long it take to encrypt them with Measure-Command:

$algos = @(' salsa', 'chacha', 'aes128')
$iter  = 100

:LENLOOP for ($len = 256; $len -lt [Math]::Pow(2,16); $len *= 2) {
  $avg  = New-Object -TypeName Double[] $algos.Length
  $min  = New-Object -TypeName Double[] $algos.Length
  $max  = New-Object -TypeName Double[] $algos.Length

  for ($i = 0; $i -lt $min.Length; $i++) { $min[$i] = [Double]::MaxValue }

  :DOLOOP for ($i = 1; $i -le $iter; $i++) {
    $s = New-String -Length $len

    $x = Measure-Command { Set-Salsa20String -String $s }
    $avg[0] += ($x.TotalSeconds - $avg[0]) / $i
    if ($min[0] -gt $x.TotalSeconds) { $min[0] = $x.TotalSeconds }
    if ($max[0] -lt $x.TotalSeconds) { $max[0] = $x.TotalSeconds }

    $x = Measure-Command { Set-ChaCha20String -String $s }
    $avg[1] += ($x.TotalSeconds - $avg[1]) / $i
    if ($min[1] -gt $x.TotalSeconds) { $min[1] = $x.TotalSeconds }
    if ($max[1] -lt $x.TotalSeconds) { $max[1] = $x.TotalSeconds }

    $x = Measure-Command { Set-AESString -String $s }
    $avg[2] += ($x.TotalSeconds - $avg[2]) / $i
    if ($min[2] -gt $x.TotalSeconds) { $min[2] = $x.TotalSeconds }
    if ($max[2] -lt $x.TotalSeconds) { $max[2] = $x.TotalSeconds }
  }
}

Kick this off with some log lines thrown in and look at the results:

$out = ''
:OUTLOOP for ($i = 0; $i -lt $algos.Length; $i++) {
  $throughput = $len / $avg[$i]
  $ratio      = $avg[$i] / $avg[0]
  
  $out += (Get-Date).ToString('yyyy-MM-dd HH:mm:ss.ffffff')
  $out += " {0}"            -f ($algos[$i])
  $out += " strlen={0}"     -f ($len)
  $out += " iter={0}"       -f ($iter)
  $out += " min={0:0.000}s" -f ($min[$i])
  $out += " max={0:0.000}s" -f ($max[$i])
  $out += " avg={0:0.000}s" -f ($avg[$i])
  $out += " {0:0.000}b/s"   -f ($throughput)
  $out += " ({0:0.000}x)"   -f ($ratio)
  $out += "`n"
}
Write-Host $out

Eventually, you start to see (approximately) how fast these Powershell-only encryption algorithms are. They are certainly not as fast as C natively compiled to your exact architecture, but if you're administratively prohibited from using Real Encryption, you have to make due with the best you've got. I wanted to know string length, string count, minimum and maximum encryption times, the mean, and approximate throughput in bytes per second.

For each string length, I used the Salsa20 average as my baseline (so Salsa20's average speed difference is by definition always 1.000x) to determine if ChaCha20 was faster or slower, and by how much:

salsa strlen=256 iter=100 min=0.226s max=0.405s avg=0.279s 918.348b/s (1.000x)
chacha strlen=256 iter=100 min=0.232s max=0.452s avg=0.283s 904.866b/s (1.015x)
aes128 strlen=256 iter=100 min=23.673s max=30.619s avg=27.547s 9.293b/s (98.821x)

 salsa strlen=512 iter=100 min=0.467s max=0.806s avg=0.527s 971.958b/s (1.000x)
chacha strlen=512 iter=100 min=0.465s max=0.825s avg=0.529s 966.959b/s (1.005x)
aes128 strlen=512 iter=100 min=47.188s max=61.495s avg=51.975s 9.851b/s (98.666x)

OK, that gives us an idea of how the two algorithms work. ChaCha20 is about 1% slower over 100 different encryptions. Using the ChaCha20-QuarterRound version of the script, the ChaCha20 numbers are very different:

salsa strlen=256 iter=100 min=0.221s max=0.357s avg=0.236s 1084.247b/s (1.000x)
chacha strlen=256 iter=100 min=0.273s max=0.435s avg=0.290s 883.173b/s (1.228x)
aes128 strlen=256 iter=100 min=23.035s max=24.718s avg=23.626s 10.835b/s (100.065x)

Hence why I say that the shorter, sweeter, pass-by-reference version of ChaCha20 is about 23% slower. I ran the tests repeatedly across a number of different string lengths and got similar results. I'm bad at computers, so I don't really know why it's worse, but it is. Profiling says so:

salsa strlen=512 iter=100 min=0.452s max=0.704s avg=0.479s 1069.053b/s (1.00x)
chacha strlen=512 iter=100 min=0.556s max=0.842s avg=0.585s 875.259b/s (1.22x)
aes128 strlen=512 iter=100 min=46.737s max=49.244s avg=47.843s 10.702b/s (99.90x)

 salsa strlen=1024 iter=100 min=0.949s max=1.436s avg=1.001s 1023.088b/s (1.00x)
chacha strlen=1024 iter=100 min=1.162s max=1.740s avg=1.222s 837.759b/s (1.22x)
aes128 strlen=1024 iter=100 min=97.043s max=108.716s avg=98.242s 10.423b/s (98.15x)

 salsa strlen=2048 iter=100 min=1.926s max=2.791s avg=2.042s 1002.976b/s (1.00x)
chacha strlen=2048 iter=100 min=2.355s max=3.964s avg=2.482s 825.099b/s (1.22x)
aes128 strlen=2048 iter=100 min=191.266s max=217.787s avg=195.406s 10.481b/s (95.70x)

So I ran the numbers on all of the different algorithms and it looks pretty straight-forward. On my test box, Salsa20 and the non-PBR ChaCha20 version do about 1 KiB/s of data. AES-128 handles about 10 B/s. This makes the Latin dance algorithms roughly two orders of magnitude faster, which is nice.

A picture is worth a thousand words, so I graphed it out (string length is the X-axis, maximum encryption time encountered for that length, in seconds, is the Y-axis):



You have to zoom in to the tail end of the graph to even see a very narrow difference between Salsa20 and ChaCha20, with ChaCha20 just slightly, slightly faster than Salsa20. They're pretty much indistinguishable in terms of overall performance, even at tens-of-thousands-of-character-length strings.

"Where's AES in all of this?" you ask. Same numbers, same graph, but with AES added:



AES isn't even in the same ballpark.

2018-01-22

Gwaelin is Optional

After watching a 27-minute speedrun of Dragon Warrior during AGDQ 2018, I was filled with a mix of nostalgia and jealousy.

After all, I did spend about 3 months playing that game on the original NES console. Not just 3 months of calendar time even. 3 months like if you measured it with a chess clock. I spent an unfathomable amount of time invested in that game and that was including the extensive notes and maps that came inside a valuable-beyond-measure explorer's handbook that was given to me by the person who lent me the game. When I learned that the stock game itself did not include these guides and maps and that a player was expected to just explore the world and figure these things out on their own I was shocked.

I was probably 10.

How in the hell are you supposed to find Garinham? People tell you you need to go to Garinham, but the forever-pacing townsfolk are very frugal with their directions and it's not like this kingdom has ever heard of roads or road signs. They just post people at the front of the town to welcome visitors and tell them where they are like some kind of fantasy world version of Lot. Often with a comparable amount of capering.

In college when game emulators started becoming prevalent I found "NESticle", an unfortunately-named NES emulator and, somewhere I don't recall anymore, a ROM of Dragon Warrior. It remains my one go-to NES game that I always keep around for reliving the glory days of my 8-bit childhood. I fostered a constant urge to trawl the in-game continents taking screenshots every few steps and somehow compositing them together into an enormous world map graphic I could reference for... for what? I don't know. Maybe to protect the nonexistent unwary who didn't have the luxury of a guidebook like I did.

I'd largely forgotten about the seemingly endless amount of time I put into Dragon Warrior until seeing the speedrun, a complex masterpiece of careful planning and timing to control the game's builtin random encounter mechanism to avoid nearly all enemies except metal slimes and to kill those slimes in the first hit.

If your blood is starting to boil by learning this, you remember as well as I do.

Technology is a wonderful thing. If I'd put immeasurable hours into the game back when you couldn't scumsave before every dungeon crawl, imagine what's possible when you can checkpoint with a keystroke. I upgraded to FCEUX as my emulator of choice. It's free, it's stable under WINE, and it allows you to hex edit the game. With these points in mind, the fastest way I've found to complete the game is as follows:

Start a new quest. Enter your name and choose "Fast" as your dialogue speed.

After King Lorik gives you your quest, open the hex editor and make the following edits:

0xBB: FF ; set XP   to 65,280
0xBC: 06 ; set gold to 6
0xBE: FF ; best weapon, armor, and shield
0xBF: 01 ; 1 Magic Key (game "limit" == 6)
0xC1: 0E ; equip Rainbow Drop

Leave Tantagel Castle and find a slime. Entering the combat screen will automatically recalculate your level to 29 based on your XP. Fight or run from the slime. Walk to Brecconary. Spend the night at the inn for 6 gold to fully replenish HP and MP.

Cast REPEL to save time while traveling, walk to Charlock Castle and use Rainbow Drop at the strait.

Navigate to the Dragonlord using the dungeon pattern you memorized when you were 11. You can complete this within the duration of one RADIANT spell. Cast HEALMORE before speaking to him. Reject his offer. After defeating the Dragonlord, cast RETURN and enter Tantagel Castle. Speak to King Lorik.

There are plenty of hacking guides that give more detail if you want to learn more about how the game works internally. I find this endlessly fascinating, and not just because a random number generator entertained and perplexed me for months on end. Twiddling five bytes breaks the game and makes winning trivial.

Take that, childhood.

P.S. The only thing that really makes me angry about any of this is that I never played without a fighter's ring, unknowing that the fighter's ring literally doesn't do anything to your stats and it takes up an otherwise-valuable equipment slot.

2018-01-14

Installing ZFS on Devuan (Again)

We've already made a systemd-free Linux server with ZFS-on-root, so let's have some fun. Typically I like to build a system with the tools of that system: use a Mint LiveCD to install Mint, Ubuntu to install Ubuntu, and so on, but it's not strictly necessary.

In particular, you can use an Ubuntu 16.04-based LiveCD with built-in ZFS support to save yourself from having to compile ZFS kernel modules twice. At the end of the day, your machine will have Devuan on it, even if you entirely installed and configured it from inside an Ubuntu or Mint session.

Here's a remix of how to build a Devuan system using a Linux Mint 18.x LiveCD and a decent network connection. Unlike the previous howto, this one will combine the stable and unstable Devuan package repositories. The advantage of doing this is a system with a modern Linux kernel and a newer version of the ZFS modules.

This is slightly more advanced than the previous howto, but don't worry. You should be a pro at this by now, and we're not going to be doing anything too terribly different here in terms of the core concepts you've already mastered. We'll be making a new LUKS container, we'll be putting ZFS on the container, installing an OS onto ZFS, and finally configuring the bootloader to decrypt and mount it. Easy peasy.

First, fetch the Linux Mint 18.x ISO and boot your machine. I like using linuxmint-18.3-xfce-64bit.iso, but use what you like. Start a terminal and become root and install the two packages you need to continue:

sudo su
killall light-locker # no screens shall be saved
apt update
apt install -y zfsutils-linux debootstrap

Partition your disk and create a LUKS container for it. This howto assumes your disk is /dev/sda and you're putting one partition on it. Your actual mileage may vary.

CRYPTNAME=cryptroot
DEVICE=/dev/sda
PARTITIONNUMBER=1
PART=${DEVICE}${PARTITIONNUMBER}

wipefs --force --all ${DEVICE}
dd if=/dev/zero of=${DEVICE} bs=1M count=2

/sbin/parted --script --align opt ${DEVICE} mklabel msdos
/sbin/parted --script --align opt ${DEVICE} mkpart pri 1MiB 100%
/sbin/parted --script --align opt ${DEVICE} set ${PARTITIONNUMBER} boot on
/sbin/parted --script --align opt ${DEVICE} p

cryptsetup luksFormat -h sha512 ${PART}
cryptsetup luksOpen ${PART} ${CRYPTNAME}

Check that you have a /dev/mapper/cryptroot LUKS container and note its UUID value:

cryptsetup luksDump ${PART}
blkid -o export ${PART} | grep -E '^UUID='

Create your zpool.

ZPOOLNAME=zroot
ZROOTDATASETNAME=jessie
CRYPTNAME=cryptroot
VDEV=/dev/mapper/${CRYPTNAME}
TARGET=/mnt

# /sbin/modprobe zfs # skip this if ZFS is not a kernel module (Ubuntu 16.04+)
/sbin/zpool create -f \
  -R ${TARGET} \
  -O mountpoint=none \
  -O atime=off \
  -O compression=lz4 \
  -O normalization=formD \
  -o ashift=12 \
  ${ZPOOLNAME} ${VDEV}

/sbin/zfs create -o canmount=off        ${ZPOOLNAME}/root
/sbin/zfs create -o mountpoint=/        ${ZPOOLNAME}/root/${ZROOTDATASETNAME}
/sbin/zfs create -o mountpoint=/boot    ${ZPOOLNAME}/boot
/sbin/zfs create -o mountpoint=/home    ${ZPOOLNAME}/home
/sbin/zfs create -o mountpoint=/var     ${ZPOOLNAME}/var
/sbin/zfs create -o mountpoint=/var/log ${ZPOOLNAME}/var/log

/sbin/zpool set bootfs=${ZPOOLNAME}/root/${ZROOTDATASETNAME} ${ZPOOLNAME}

Install your OS. We use debootstrap here, and we leverage a couple of bonus packages we want with --include. You could really go overboard here and install the kitchen sink. I prefer to keep --include lean (but not too lean) and add what I need later.

ARCH=amd64
BRANCH=jessie
TARGET=/mnt
# HTTPS works here but not for apt
MIRROR=https://auto.mirror.devuan.org/merged
PKGS=console-setup,cryptsetup,kbd,locales,tmux,openssh-client

/usr/sbin/debootstrap \
  --arch=${ARCH} \
  --include=${PKGS} \
  ${BRANCH} \
  ${TARGET} \
  ${MIRROR}

N.B.: I have not had much luck with a reliable way to intelligently install packages with respect to their dependencies other than debootstrap and the apt family of tools. apt, apt-get, aptitude, and their ilk expect a network connection to find and fetch packages. This makes, say, downloading a set of .DEB files to a local file share and then saying "go install these before I turn your network interface on" a problem. I've done experimentation with a number of tools that are ultimately unsatisfying: multistrap and gdebi come to mind. If you only want to install Devuan once, go and make your bespoke debootstrap --include as long as you want. I like to keep the fetched packages around, un-bootstrapped in a tarball, to help me create reproducibly similar systems. You can do this with the --foreign argument, with the cost of needing to chroot to the new system-to-be and run debootstrap, locally, a second time. Doing so is outside the scope of this howto, but it can be done.

When the base system has installed successfully, put your new fstab in place. For example:

# cat /mnt/etc/fstab
/dev/mapper/cryptroot /        zfs defaults,noatime 0 0
zroot/boot            /boot    zfs defaults,noatime 0 0
zroot/home            /home    zfs defaults,noatime 0 0
zroot/var             /var     zfs defaults,noatime 0 0
zroot/var/log         /var/log zfs defaults,noatime 0 0

Other important files that need to be updated:

echo myhostname > /mnt/etc/hostname
echo en_US.UTF-8 UTF-8 > /mnt/etc/locale.gen
echo 127.0.0.1 myhostname >> /mnt/etc/hosts
ln -sf /proc/self/mounts /mnt/etc/mtab

Set your network config. This howto assumes DHCP for simplicity. Linux networking is terrible, so I chattr the interfaces file to keep it from being molested by something well-meaning but misguided that wants to make sure my minimalist server OS can connect to a coffeeshop wifi access point if one appears, because apparently there could someday be a Starbucks that opens up inside a datacenter. I do this to /etc/resolv.conf, too.

echo auto eth0 >> /mnt/etc/network/interfaces
echo iface eth0 inet dhcp >> /mnt/etc/network/interfaces
chattr +i /mnt/etc/network/interfaces

Add some mountpoints into your /mnt:

for i in /dev /dev/pts /proc /sys; do mount -B $i /mnt$i; done

Create a key for your bootloader to use to unlock the LUKS container.

TARGET=/mnt
KEYDIR=${TARGET}/boot
DEVICE=/dev/sda
PARTITIONNUMBER=1
PART=${DEVICE}${PARTITIONNUMBER}
INITRAMFSHOOKSDIR=${TARGET}/etc/initramfs-tools/hooks
KEYFILE=rootkey.bin

openssl rand -out ${KEYDIR}/${KEYFILE} 2048 # you can always use dd here too
chmod 0 ${KEYDIR}/${KEYFILE}
cryptsetup luksAddKey ${PART} ${KEYDIR}/${KEYFILE}

mkdir -p ${INITRAMFSHOOKSDIR}
echo "cp -p /boot/${KEYFILE} \"\${DESTDIR}\"" > ${INITRAMFSHOOKSDIR}/crypto_keyfile
chmod +x ${INITRAMFSHOOKSDIR}/crypto_keyfile

chroot into your system and configure it. tmux or GNU screen would be useful here, hence why I put tmux in the debootstrap. Some of the following steps can be done while you're waiting for things to compile.

chroot /mnt

Set up your apt repos. Make sure you have the Devuan unstable branch, "ceres", and it should include at least the "main" and "contrib" categories. Debian refugees may recall that their unstable branch is "sid", so there may be a period of adjustment re-learning that sid is now ceres.

cd /etc/apt
cp -p sources.list sources.list.orig
vi sources.list # do your editing here
# cat sources.list
deb http://auto.mirror.devuan.org/merged jessie main
deb http://auto.mirror.devuan.org/merged ceres main contrib

Get the Devuan repo key. It is absent from your new system because you didn't use a Devuan installation medium. You could get this key from the Devuan LiveCD in /usr/share/keyrings, but I'll show you how to do it by hand here:

gpg --verbose --keyserver=pgp.mit.edu --recv-key 94532124541922FB
gpg --verbose --export --armor --output=./devuan_jessie.key 94532124541922FB
apt-key add ./devuan_jessie.key

Now you can begin to customize your packages. At minimum, we'll be installing a compiler, a kernel, a bootloader, and some kernel modules. If your architecture isn't AMD64, adjust it accordingly.

apt update
apt install -y build-essential
apt install -y -t ceres linux-image-amd64
apt install -y -t ceres linux-headers-amd64

I find that when mixing stable and unstable repos, meaning both jessie and ceres, the newer package usually wins. If that's the case, then the -t ceres argument isn't strictly necessary. I like to include it anyway for clarity. I want the latest kernel and kernel headers the repo has to offer.

Install ZFS. This can take a while.

DEBIAN_FRONTEND=noninteractive
export DEBIAN_FRONTEND
time apt install -y -t ceres zfs-dkms

Create a password for root. Pick a time zone and a locale. I typically like to do this in another tmux window while ZFS builds.

passwd
passwd -u root
dpkg-reconfigure tzdata
locale-gen

When ZFS finishes installing, continue by adding a ZFS-aware initramfs

apt install -y -t ceres zfs-initramfs grub-pc

Configure GRUB and prep your initramfs. The UUID value you created at the beginning will be important here. As an example, this howto assumes your UUID is 9862499a-80b0-459d-9a86-5f2ddbe0464c. Replace this value with your real UUID. If your LUKS container is named something other than cryptroot, adjust that, too.

blkid -o export /dev/sda1 | grep -E '^UUID='
vi /etc/crypttab
cat /etc/crypttab
cryptroot UUID=9862499a-80b0-459d-9a86-5f2ddbe0464c /rootkey.bin luks,keyscript=/bin/cat

Make sure /etc/default/grub contains the following:

GRUB_CMDLINE_LINUX_DEFAULT="boot=zfs"
GRUB_CMDLINE_LINUX="cryptdevice=UUID=9862499a-80b0-459d-9a86-5f2ddbe0464c:cryptroot"
GRUB_ENABLE_CRYPTODISK=y

Test if GRUB can detect your ZFS dataset.

grub-probe /

If the result isn't "zfs", something is wrong. Do not continue until the problem is fixed.

Create a new initramfs. Recent updates may have precluded the need to symlink /dev/mapper/cryptroot to /dev/cryptroot; your actual mileage may vary.

ln -sf /dev/mapper/cryptroot /dev
update-initramfs -u -k all

Update GRUB and install the GRUB bootloader.

update-grub
grub-install /dev/sda

If the result is "Installation finished. No error reported." you can proceed.

Disable log compression for /var/log. Since you're already using lz4 compression on the zpool, further per-file compression is, in general, unhelpful.

for file in /etc/logrotate.d/* ; do
  if grep -Eq "(^|[^#y])compress" "$file" ; then
    sed -i -r "s/(^|[^#y])(compress)/\1#\2/" "$file"
  fi
done

When the system is configured how you want it, exit the chroot.

exit

Unmount your mountpoints, change your non-root datasets' mountpoint to "legacy", and export the zpool.

for i in sys proc dev/pts dev
do
  umount /mnt/$i
done

/sbin/zfs unmount -a

for dataset in boot home var/log var
do
  /sbin/zfs set mountpoint=legacy zroot/${dataset}
done

/sbin/zpool export -a

Finally, stop the machine, eject the LiveCD, and boot off of the disk. You will be prompted to unlock the LUKS container with a password, and from there the boot process should continue without further prompting.

Login as root. Add a swap device zvol.

ZPOOLNAME=zroot
SWAPNAME=swap
DEVICENAME=/dev/zvol/${ZPOOLNAME}/${SWAPNAME}

/sbin/zfs create -V 128M -b $(getconf PAGESIZE) \
  -o compression=zle \
  -o logbias=throughput \
  -o sync=always \
  -o primarycache=metadata \
  -o secondarycache=none \
  -o com.sun:auto-snapshot=false \
${ZPOOLNAME}/${SWAPNAME}

mkswap -f ${DEVICENAME}
echo ${DEVICENAME} none swap defaults 0 0 >> /etc/fstab
swapon -av

If you ever find yourself adding another kernel to the system, linux-image-A.B.C-D-amd64 for example, make sure you add linux-headers-A.B.C-D-amd64 as well. Adding the corresponding kernel headers should, in theory, run /etc/kernel/header_postinst.d/dkms and build the necessary ZFS kernel modules for the new kernel automatically. Always be cautious when and how you update your kernel.

2017-12-30

A "review" of Jeff VanderMeer - Acceptance

Said you took a big trip, said you moved away
Happened oh so quietly they say
— David Bowie, "Everyone Says Hi"

If I told you it was a love story, you wouldn't believe me.

English is a funny thing. We have one word for love, and we use it in multiple contexts to cover a range of similar but definitely distinct feelings. The ancient Greeks famously had multiple words for love: eros versus agape, for example: romantic love versus divine love. You do not express your love for your significant other the same way you express your love for God, or at least perhaps you shouldn't. Serious theologians probably don't endorse that sort of rapturous exaltation towards the Almighty. Philia is yet another word for a different kind of love, hence the city named Philadelphia: literally, "City of brotherly love".

Apocalypse Now parallels to The Odyssey aside, I never did well in the classics, so I cannot decide if this love story is philia, brotherly love, or storge, familial love. But it's a love story, not-so-plain and not-so-simple, and told over a number of years. The core of the mystery is largely irrelevant, which is a gobsmacker of a shift in focus when we started this whole shebang with a tower that grew down. Whereas the first book was a mystery experienced by the biologist, and the second book a condemnation of the bureaucratic mediocrity of Control's complete lack thereof, the third book is an altogether new beast and one that is hard to describe.

Said you sailed a big ship, said you sailed away
Didn't know the right thing to say

If the first book is an account of someone who will distance herself from any and all obstacles in her singular purpose and her drive, not always alone but always and forever independent, then this book is the collection of multiple interwoven people and perspectives as their stories combine. As Thomas Pynchon puts it, "[T]his is not a disentanglement from, but a progressive knotting into—". I'd be lying if I told you Acceptance answers your every lingering question. Area X is not that simple, and I don't believe it will ever divulge its secrets. Maybe that was never the point.

Whereas Annihilation and Authority were single-source narratives, Acceptance does away with that structure and instead tells each chapter from a single person's point of view. This is a popular writing style nowadays, and I blame George R. R. Martin. My seething anger at the relative obscurity of Hugh Howey's amazing Wool (a nearly perfect book) notwithstanding, when the "one narrator per chapter" formula works, it works well. Acceptance is a collection of individual characters' experiences, both before and after, well, you know. I hesitate to go into detail here, because the unreal enigma that surrounds and pervades Area X is broken into two major epochs that define three distinct (if not amorphous) time periods: the before, the during, and the, y'know... after.

Should've took a picture, something I could keep
Buy a little frame, something cheap

I wonder sometimes what it would be like to live through something like the Star Trek: The Next Generation episode "A Matter of Time", in which a man from the future time travels to the past to observe the crew of the starship Enterprise for what he states will be a historical event on a planet, and I don't need to look this up, called "Penthara IV". If you knew ahead of time that shit was going to get real, what would you do differently? Jeff VanderMeer puts a very humanizing touch on these moments in Acceptance, writing not just scenes set in the past, but scenes where characters reflect upon their pasts, too. And those moments are earnest and real: no one says "I'm going to be a hero today", they just go about their lives like normal people, feeling annoyed or irritated by minor inconveniences, or thinking fondly throughout the day of their significant others. These are perfectly average people racing headlong into perfectly abnormal circumstances and they have no clue what is about to transpire. Acceptance is simultaneously the documentation of their banal experiences pre-Y'Know and the in situ accounts of their actions post-Y'Know and it's jarring and intimate and wonderful. Each page is a person's thought process wherein you the omniscient reader can say, "If. You. Only. Knew...."

I'd love to get a letter
Like to know what's what

If I told you it was a love story, you wouldn't believe me.

I wouldn't believe me either. "Where lies the strangling fruit that came from the hand of the sinner I shall bring forth the seeds of the dead to share with the worms" is definitely NOT the kind of thing to write onto a heart-shaped notecard and tuck into a box of chocolates to give your sweetie on Valentine's Day. But I've already established that we're not dealing with eros here and there are many ways to say I love you. Acceptance is a meditation on that kind of love and loss, the kind that's felt at arm's length, or over the span of miles, or of decades.

The book is not so much a story of explanation, or exploration, or even of redemption, than it is of coming to terms with the unalterable events of the past, both of the factual historical events that a newspaper would publish, and of your words and deeds mired in the ignorance of your youth. Everyone handles regret differently.

Some people tenaciously hold onto the belief that it could have been changed and concretely focus on a moment, or a conversation, or an abstract idea like terroir that reinforces in their own mind the notion that all could have been or still be made right.

Others simply persist, doggedly moving forward onto their next goal. Or else they may stay rooted in one place awaiting a sign or a revelation.

And others simply breeze about, figuratively above it all, gaining a bird's eye view, remembering their mistakes, reflecting upon them and finally, formally, making peace with themselves.

The biologist dismissively shares her dreams of a creature in the first pages of Annihilation and the lighthouse keeper has staggering visions of piles upon piles of field journals in Acceptance. VanderMeer bends his trilogy around on itself, forming a loose circle. Or maybe it's a spiral, its helix linking back to itself almost like a DNA molecule of relationships that line up and lock together like nucleotides: the lighthouse keeper and the kid. The S&SB. The biologist and her owl. Control and his dumbass infatuation with Ghost Bird. Area X may be the thing that they have in common, but Area X is not the thing that connects them to each other, even when time and space may break them apart. Each is one half of a whole, and that other half is irreplaceable and permanent. A half's loss of the other half is the loss of the cohesive whole, a loss that is felt forever.

I have rarely been moved by the loss of a bird more intensely than in Acceptance and as a kid I once killed a blue jay with a BB gun just because I could. Compared to that, I think Acceptance is coming in second here. Everyone forges their own path in the face of regret, either going around it, or over it, or tunneling through it and maybe, hopefully, coming out the other side. The Southern Reach trilogy is a love story, a long and weird correspondence whose final love letter is long delayed and circuitously delivered and touching and sweet.

Perhaps the real lesson to learn about regret isn't about ignoring it or letting it gnaw away at you, but about trying to use it to learn and grow and yes, to accept it for what it is. Sometimes a mystery can't be solved, sometimes there are no real heroes. Acceptance is exactly what it says it is. You can dote on the particulars of the past forever if you want and try to comprehend the why of it all. Or you can figure out what you want to do with what limited resources you have left and hurry up and start doing it.

Don't stay in a bad place
Where they don't care how you are
Everyone says hi
Everyone says hi
Everyone says hi


Final thoughts: Jeff VanderMeer can spin a compelling yarn, but only under a certain narrow construct. If he strays beyond his area of expertise, he fails. It's a razor's edge between droll minutiae inside the mind of a loathsome one-dimensional character that bores like a hand drill into your skull and lavish, detailed meditations on the microcosms of the natural world whose rich and sensual descriptions border upon the pornographic. He built a world that is weird and wonderful and scary and, above all, enticing. Area X: it's not so nice a place to visit, and you definitely don't want to live there, but you may not have a choice. This trilogy would definitely be better as single book, which you can actually buy, but lord almighty the second act is a total drag. If you want to stop after the first story, you can still walk away satisfied. If you want to complete the circle, insomuch as one ever can inside an impossible non-Euclidean bubble that defies the laws of physics, you can proceed, with caution. Extreme caution.