williamedwardscoder

[williamedwardscoder]

Slow database? It might not be your fault

<rant>

Okay, it usually is your fault. If you logged the SQL your ORM was generating, or saw how you are doing joins in code, or realised what that indexed UUID does to your insert rate etc you’d probably admit it was all your fault. And the fault of your tooling, of course.

In my experience, most databases are tiny.  Tiny tiny.  Tables with a few thousand rows.  If your web app is slow, its going to all be your fault.  Stop building something webscale with microservices and just get things done right there in your database instead.  Etc.

But, quite often, each company has one or two databases that have at least one or two large tables.  Tables with tens of millions of rows.  I work on databases with billions of rows.  They exist.  And that’s the kind of database where your database server is underserving you.  There could well be a metric ton of actual performance improvements that your database is leaving on the table. Areas where your database server hasn’t kept up with recent (as in the past 20 years) of regular improvements in how programs can work with the kernel, for example.

Over the years I’ve read some really promising papers that have speeded up databases.  But as far as I can tell, nothing ever happens.  What is going on?

For example, your database might be slow just because its making a lot of syscalls.  Back in 2010, experiments with syscall batching improved MySQL performance by 40% (and lots of other regular software by similar or better amounts!).   That was long before spectre patches made the costs of syscalls even higher.

So where are our batched syscalls?  I can’t see a downside to them.  Why isn’t linux offering them and glib using them, and everyone benefiting from them?  It’ll probably speed up your IDE and browser too.

Of course, your database might be slow just because you are using default settings.  The historic defaults for MySQL were horrid.  Pretty much the first thing any innodb user had to do was go increase the size of buffers and pools and various incantations they find by googling.  I haven’t investigated, but I’d guess that a lot of the performance claims I’ve heard about innodb on MySQL 8 is probably just sensible modern defaults.

I would hold tokudb up as being much better at the defaults.  That took over half your RAM, and deliberately left the other half to the operating system buffer cache.

That mention of the buffer cache brings me to another area your database could improve.  Historically, databases did ‘direct’ IO with the disks, bypassing the operating system.  These days, that is a metric ton of complexity for very questionable benefit.  Take tokudb again: that used normal buffered read writes to the file system and deliberately left the OS half the available RAM so the file system had somewhere to cache those pages.  It didn’t try and reimplement and outsmart the kernel.

This paid off handsomely for tokudb because they combined it with absolutely great compression.  It completely blows the two kinds of innodb compression right out of the water.  Well, in my tests, tokudb completely blows innodb right out of the water, but then teams who adopted it had to live with its incomplete implementation e.g. minimal support for foreign keys.  Things that have nothing to do with the storage, and only to do with how much integration boilerplate they wrote or didn’t write.  (tokudb is being end-of-lifed by percona; don’t use it for a new project 😞) 

However, even tokudb didn’t take the next step: they didn’t go to async IO.  I’ve poked around with async IO, both for networking and the file system, and found it to be a major improvement.  Think how quickly you could walk some tables by asking for pages breath-first and digging deeper as soon as the OS gets something back, rather than going through it depth-first and blocking, waiting for the next page to come back before you can proceed.

I’ve gone on enough about tokudb, which I admit I use extensively.  Tokutek went the patent route (no, it didn’t pay off for them) and Google released leveldb and Facebook adapted leveldb to become the MySQL MyRocks engine.  That’s all history now.

In the actual storage engines themselves there have been lots of advances.  Fractal Trees came along, then there was a SSTable+LSM renaissance, and just this week I heard about a fascinating paper on B+ + LSM beating SSTable+LSM. A user called Jules commented, wondered about B-epsilon trees instead of B+, and that got my brain going too.  There are lots of things you can imagine an LSM tree using instead of SSTable at each level.

But how invested is MyRocks in SSTable?  And will MyRocks ever close the performance gap between it and tokudb on the kind of workloads they are both good at?

Of course, what about Postgres?  TimescaleDB is a really interesting fork based on Postgres that has a ‘hypertable’ approach under the hood, with a table made from a collection of smaller, individually compressed tables.  In so many ways it sounds like tokudb, but with some extra finesse like storing the min/max values for columns in a segment uncompressed so the engine can check some constraints and often skip uncompressing a segment.

Timescaledb is interesting because its kind of merging the classic OLAP column-store with the classic OLTP row-store.  I want to know if TimescaleDB’s hypertable compression works for things that aren’t time-series too?  I’m thinking ‘if we claim our invoice line items are time-series data…’

Compression in Postgres is a sore subject, as is out-of-tree storage engines generally.  Saying the file system should do compression means nobody has big data in Postgres because which stable file system supports decent compression?  Postgres really needs to have built-in compression and really needs to go embrace the storage engines approach rather than keeping all the cool new stuff as second class citizens.

Of course, I fight the query planner all the time.  If, for example, you have a table partitioned by day and your query is for a time span that spans two or more partitions, then you probably get much faster results if you split that into n queries, each for a corresponding partition, and glue the results together client-side!  There was even a proxy called ShardQuery that did that.  Its crazy.  When people are making proxies in PHP to rewrite queries like that, it means the database itself is leaving a massive amount of performance on the table.

And of course, the client library you use to access the database can come in for a lot of blame too.  For example, when I profile my queries where I have lots of parameters, I find that the mysql jdbc drivers are generating a metric ton of garbage in their safe-string-split approach to prepared-query interpolation.  It shouldn’t be that my insert rate doubles when I do my hand-rolled string concatenation approach.  Oracle, stop generating garbage!

This doesn’t begin to touch on the fancy cloud service you are using to host your DB.  You’ll probably find that your laptop outperforms your average cloud DB server.  Between all the spectre patches (I really don’t want you to forget about the syscall-batching possibilities!) and how you have to mess around buying disk space to get IOPs and all kinds of nonsense, its likely that you really would be better off perforamnce-wise by leaving your dev laptop in a cabinet somewhere.

Crikey, what a lot of complaining!  But if you hear about some promising progress in speeding up databases, remember it's not realistic to hope the databases you use will ever see any kind of benefit from it.  The sad truth is, your database is still stuck in the 90s.  Async IO?  Huh no.  Compression?  Yeah right.  Syscalls?  Okay, that’s a Linux failing, but still!

Right now my hopes are on TimescaleDB.  I want to see how it copes with billions of rows of something that aren’t technically time-series.  That hybrid row and column approach just sounds so enticing.

Oh, and hopefully MyRocks2 might find something even better than SSTable for each tier?

But in the meantime, hopefully someone working on the Linux kernel will rediscover the batched syscalls idea…? ;)

[williamedwardscoder]

Faster searches with non-prefix fields in composite indices

Here’s a horrid hack or neat trick to work around a gaping inefficiency in the MySQL query planner:

Imagine you have a very large table and a composite index e.g. the fields A, B, C and D.

Imagine you have a query WHERE A = ? AND C = ?

MySQL will use the index to check all the values of A but dereference each row with the matching A before checking the C.

You can see what is happening using EXPLAIN SELECT by looking at the KEY and KEY_LEN columns: the index will be named the KEY (good so far!) and the KEY_LEN will be the max size of column A (ugh!). 

If you supply a dummy clause constraining B too then you can force MySQL to check the C constraint before it dereferences any rows: SELECT ... WHERE A = ? AND B != ? AND C = ? (where B can be checked against some value that it can’t possibly be).

You can confirm this is happening by looking that the EXPLAIN SELECT again: the KEY will still be the name of the index (if it isn’t, you can force the index to be used with a USE INDEX clause) and the KEY_LEN will now be the maximum length of the A, B and C fields combined.

You can even use this trick to get an index used even if the very first field in the composite index is not constrained, e.g. WHERE A != ? AND B = ?

This isn’t foolproof - you always need to benchmark with your database!  Using any index and the additional dereference cost compared to just doing a table scan in the first place assumes that the index is dramatically cheaper to walk and will dramatically reduce the number of rows that need to be dereferenced.  If only a tiny subset of the table needs to be dereferenced, the index will help; if a large proportion of the table is going to be dereferenced anyway then it’d be better to do a table scan from the get-go.

However, if you have very large tables and you have composite keys that cover your fields but which some of the composite keys unconstrained then its well worth evaluating this approach which, in the right circumstances, can give orders of magnitude improvements.

Why doesn’t MySQL use this trick internally?  Well, it should!  If its already decided to use a composite ordered index for some prefix of the constrained fields, then it should always check all constraints it can before dereferencing any actual rows. If MySQL used this trick you wouldn’t have to find some impossible value to fake a check against either.

Its a bit harder to say if it can work out when to use a composite index when there is no prefix at all.  And of course it doesn’t work with hash indices.

Does MariaDB use this trick internally automatically?  I don’t know but I doubt it.

Does PostgreSQL?  No idea.  Etc.

If you liked this you might like my recent stats on database compression or browse some of my earlier posts 

[williamedwardscoder]

Why I am excited about RocksDB

TL;DR RocksDB will probably supplant TokuDB as my go-to backend for bigger-than-RAM datasets

A long time ago something amazing happened in database storage engines.  Fractal Trees inventors spun off a company called Tokutek to productify them.

The resulting TokuDB storage engine ran rings around all other engines.  Now it did this in part because they smudged the integration a bit; running the Tokutek-packaged TokuDB always massively outperformed a generic TokuDB packaged by Percona or MariaDB because the tweak wasn’t just to the storage layer but also, I believe, to the way MySQL integrated with storage engines?

And, roughly at the same time, deep inside Google they combined Log Structured Merge (LSM) Trees with Sorted String Tables (SSTables).

Now if you draw FT and LSM on a white-board side-by side and step back and squint they are actually fairly similar.  The dominating thing is that layers are hierarchical - the storage has the same shape and the IO is fairly equivalent.

There’s this pattern emerging where Google publish some ground-breaking utility code (often after they’ve already started on its replacement internally, it seems) and Facebook iterate and maintain it.  LevelDB became RocksDB.  Snappy got FB sponsoring LZ4 ZStd etc perhaps?  And so on.

And so RocksDB emerges as a well-supported, stable but also constantly improving LSM+SSTable that has excellent compression too.  The thing to underline here is that RocksDB is not about to be abandoned and bitrot; instead, its only going to get better!

Tokutek did not get the big success it deserved in the DB world, and eventually got brought by Percona.  And the TokuDB packaged by Percona or MariaDB using the constraining MySQL storage engine interface was not as world-beating as that originally integrated by Tokutek.  TokuDB was still my preferred storage engine though.  (previously: Compressing MySQL stats).  One thing that is exciting though is that Percona may finally integrate faster UPSERT hints - about time!!

Facebook have already integrated RocksDB into MySQL as myrocks.io.  I haven’t used it.  What has got me excited though is that Percona seem to be packaging it up in Percona-Server too!  Here’s a nice set of slides from a talk I wished I could have watched: TokuDB vs MyRocks

There is another general pattern in the DB world today: swap out your storage engine for RocksDB!  Just yesterday we saw the stunning results Instagram got with Cassandra doing it.  Even MongoDB went that way, and once upon a time TokuMX was vying for that pie.

So TokuDB may still be better than RocksDB for all kinds of technical reasons, but in the end, backing RocksDB is going to be less pain and technical debt longer-term.  It might even support foreign keys and other stuff that TokuDB never got around to.

I am quite sad for Tokutek’s plight and legacy though.

Oh, and I wish someone would bite the bullet and overhaul the MySQL storage engine layer and add NOAR support everywhere and make it so that everyone can have faster MySQL.  Tokutek showed there’s still so much room for improvement.

[williamedwardscoder]

Compressing MySQL databases

TL;DR: use TokuDB.  Always.  It massively reduces storage requirements and is massively faster than InnoDB, even on low end hardware.  My tables were compressed to just 12% original size and that’s fairly typical.

A very simple structure:

CREATE TABLE test (      date DATE NOT NULL,      site VARCHAR(8) NOT NULL,      order_id VARCHAR(64) NOT NULL,      time TIME NOT NULL,      kind ENUM(...) NOT NULL,      account INTEGER,      user INTEGER,      client_price BIGINT,      supplier_id INTEGER,      supplier_cost BIGINT,      client_ref VARCHAR(32),      data JSON,      PRIMARY KEY (date, site, order_id),      INDEX (account, user, client_ref) ) DEFAULT CHARSET utf8 PARTITION BY RANGE (TO_DAYS(date)) ( ...

This system is using the RDBMS as a document store; the order items are being flattened into a document store (the ‘data’ field).

The ETL is upserting order events as they are processed, using multi-row INSERT INTO ... ON DUPLICATE KEY UPDATE ...

And I’ve been running performance tests with some real data.  27M rows of real data, all on the same day (so all in the same partition).  37M upsert statements inserting or updating those 27M rows, issued in batches of 1K-2K per multi-row statement.  This is enough rows to be able to get a grasp of upsert performance and extrapolate storage requirements.

The test box is an AWS t2.medium instance.  This is a very weak VM with 2 (virtual) CPUs and 4GB RAM.  Not normal DB fare, so performance beware.

The 27M rows take 10.48GB uncompressed.  It takes InnoDB 10 hours to load all the data.

In the old days, MySQL InnoDB offered ‘row_compression’.  This compresses individual rows.  This reduces disk requirements to 5.73GB (45% space saved).  So it halves the disk space!  Sadly, the test now took 15 hours instead of 10 hours.

More recently, MySQL introduced ‘table compression’.  (MariaDB also added it, calling it ‘page compression’; the CREATE TABLE syntax is infuriatingly slightly different).

Underneath, InnoDB is organized as ‘pages’.  This table compression intercepts these page reads and writes and, as pages are written to disk, they are individually compressed and written as a ‘sparse’ file.

As these InnoDB pages are larger than the file system pages, there is the opportunity for a ‘hole’ to be ‘punched’ in each InnoDB page.  Imagine an InnoDB page is 12KB, and the file system page size is 4KB.  The page may compress down to 1KB, meaning it only needs the first file system page (4KB),  and 8KB would be saved.  This example illustrates how wasteful this approach can be; there can still be a lot of slack in each page.  The total file-size as reported by ls is unchanged, but the actual used disk space (as shown by e.g. ls -s) is reduced.  Page compression compresses this table to 4.07GB (61% savings).  The bad news is that performance sinks awfully!  I aborted the run after 32 hours, as upsert speed had dropped to under 100 orders/sec.  I’ve seen this on MariaDB RDS and on my little t2.medium.  Its atrocious!

TokuDB is an alternative storage engine to InnoDB.  It is nicely packaged by Percona so its very straightforward to install.

TokuDB compresses databases with zlib by default.  It compresses pages, but doesn’t store them as sparse files; instead, the total file size you see on disk is the total file size.

TokuDB with zlib compresses to 1.45GB (86% savings)!  This is the same compression algorithm as InnoDB page compression and operating at much the same logical page level, but conferring much bigger savings because each ‘page’ is not rounded up to a multiple of the file system page size.

Because InnoDB puts the whole table (or, as in this case, partition) into a single file you cannot see how much of the storage is for the primary rows and how much is for secondary indexes.  TokuDB, however, has separate files for each index.  So in this case there are two files for the partition, and I can see that the 27M rows takes 1.02GB and the by-client index takes 0.44GB.

TokuDB allows you to specify other compression algorithms.  The weakest (thus fastest) is ‘snappy’, which is an LZ77 compressor without entropy coding.  It compresses to 2.31GB (78% savings; same ratio rows to index).

There is also QuickLZ (between snappy and zlib in CPU requirements; 1.95GB; 81% savings) and LZMA (stronger than zlib; 1.23GB; 88% savings!).

LZMA is a clear winner here.  What’s fascinating about the TokuDB though is not just its space-saving but also its performance: it takes just 2 hours to run my ETL and choice of compression algorithm has no noticeable effect on that!

Now the dire uncompressed InnoDB performance is perhaps the classic “InnoDB is not good with databases that don’t fit into RAM”.  I was using Percona packages so the defaults were not as mad as they used to be out-of-the-box with other linux sources, but I did up it to 2GB and a big log.  Configuring InnoDB optimally is like reading tea leaves and no amount of doing it makes me confident I’ve hit the sweat spot for any particular workload.  This upsert workload seems to be particularly stressful.  The t2.medium has two (virtual) CPUs, and as upsert performance dropped I saw ‘top’ reporting load average over 2.0 even though ETL was waiting on the DB.  Not good.

However the dire compressed InnoDB performance I saw repeated on a MariaDB RDS m4.2xlarge with the same data-set.  There’s something wrong with either InnoDB page compression, or with EBS spare file performance!

On the other hand, TokuDB shows how to do things properly!  The out-of-the-box defaults are very sane (it doesn’t use O_DIRECT; instead, it takes 50% to store uncompressed pages, and lets the OS cache the compressed pages in the normal file buffer cache.  Inspired!).  And the performance is just so stable!  On the t2.medium, which is a piddling little box, I saw 5000 orders/sec sustained throughout the entire run.

I think I’ve heard that TokuDB is marginally slower than (uncompressed) InnoDB on small tables.  And perhaps most users have small tables.  I don’t think there’s actually that measurable a gap when everything is tiny.  But the moment you go over a million rows or contemplate partitioning then I think TokuDB is the obvious choice.  In fact it would make a very good default.

Oh, and for kicks, try a COUNT(*) on a big InnoDB table.  And then go make a coffee!  TokuDB ... snap!  Not based on meta-data like MyIASM did neither; just so much faster.

TokuDB redefines what a ‘small’ database is.  It moves the goalposts.  It means I can build bigger systems without scaling sideways.  I don’t get why everyone still uses InnoDB ;)

[williamedwardscoder]

Linux on my MBP sucks

I was reading the excellent commentary on LWN and was compelled to record my own experience so far.

I’m one of those being driven away by Apple.  I’ve been a happy Linux user for the past 18 years, but up until now I’ve been keeping my work’s MBP a OSX zone because MBPs have infamous Linux support and I just didn’t want to spend time on it.

For work I have a MBP retina 15-inch, Early 2013, 16GB RAM and NVIDIA GeForce GT 650M.  Still quite good hardware, and the thing I most need for my job would be more RAM, so upgrading to a newer mac is not gonna help me.

The biggest fight has been with brew and macports and trying to get the ecosystem of tools and servers I need to work well with it.  Its Unixish enough to get things working but not without a constant friction.  I increasingly give up and run stuff like in VirtualBox, but have noticed a staggering performance penalty that is finally becoming unbearable.

So I bit the bullet and set about upgrading to Linux.

I used the OSX disk partition tool to carve off a big chunk of the SSD to dedicate to Linux.  I get the impression that it wasn’t just truncating the partitions and wasn’t about to lose any data, and that was reassuring.  I think it moved stuff around to fit the new partition bounds and free up the empty space.

The instructions I found for Arch Linux would be off-putting to dabblers, but I was undaunted and worked through them.  The instructions worked just fine with a Ubuntu net-install stick as I had a wired network cable to hand.  I don’t think you can get a wireless install to work.

The dual-boot aspect works well; by default it boots into Xubuntu (my desktop of choice), but if I hold down the ALT key when I hear the startup chime it gives me a boot menu that lets me boot into OSX.

The default video drivers don’t offer hardware acceleration.  Being Xubuntu, you can go enable non-free NVIDIA drivers to get hardware acceleration.  However, I found this drank battery like a hummer, so I had to immediately turn that off.

I’ve noticed the WiFi signal strength is much poorer than in OSX, and I have to move my laptop around to get a good enough signal at a distance.

There are three fundamental problems, however:

1) a Linux desktop on a retina screen is like a postage stamp!  I played around trying to set scaling and everything, but most programs do not honour those settings.  Its unusable.

2) the touchpad support sucks.  Really really sucks.  Its unusable too.  I tried changing settings and couldn’t get anything I’m happy with.

3) a long time ago when I upgraded the major version of OSX it offered to encrypt my file system and I chose to do it.  At the time I couldn’t think of any reasons why not, but now that I dual boot I can’t access my OSX partition from Linux.  I think I found a FUSE driver that promised to support Apple Core Storage encryption, but I haven’t been able to find it again and try it out.

Sadly, I now routinely hold down the ALT key as my MBP boots.

[williamedwardscoder]

My attack on the Enigma cipher machine

see also:

Enigma Machine on Paper and Python

Fast Enigma sim in C++

A brief history of the Enigma and the pre-war cracking of it

Enigma in a spreadsheet!

My favourite book was Fermat's Last Theorem by Simon Singh.  So when in 1999 I saw his new book - The Code Book - in shops I just had to buy it, despite it being incredibly expensive (for a very poor student like myself).  I then took my new prize procession with me expectantly on the summer holiday.  And when I reached the end of the book that I discovered it contained a Cipher Challenge!

I set about cracking the ciphers with gusto.  By chance I happened to have my 286 computer with me, and my hobby language of choice - Turbo Pascal 7. 

I think I skipped the ADFGVX cipher, so excited was I at the prospect of cracking the Enigma stage 8 of the contest.  Unfortunately, when I reached the Enigma, I was stumped.  I couldn't make any headway with simulating the Enigma.  I wrongly assumed that the message would begin with the message key encrypted with the day key twice.  But my biggest mistake was not understanding how rings affected things.  I didn't understand how rings affected things because The Code Book didn't actually explain them!  The book instructed the intrepid explorer to search the Internet for more details and I didn't take any heed of this because a) I couldn't imagine the book wouldn't actually give me everything I needed to crack the challenge, and b) I didn't have any Internet.  The Enigma I was trying to crack wasn't even an accurate Enigma.

So 17 years later I find myself on a whim tacking the Enigma once again.  And my computer is a bit faster too.  But I want to attack it my way, putting myself as much as possible in the shoes of my old self 17 years ago, only this time with Internet so I can double-check the correctness and completeness of my implementation of the Engima cipher machine.

This is my attack on the Enigma.  I will describe my attack on an M3 Enigma (used by the army and air force) and then I will generalize it to attack the M4 (used by the U-boats; what Alan Turing is famous for cracking).

The best way to understand how the Enigma works is to make one from paper, following instructions you find on the web.  Each time the user presses a key the key goes (via a plugboard) into the rightmost rotor.  Here is is translated to another letter and goes into the middle rotor where it gets translated again.  In then goes to the leftmost rotor where, after being translated again, it goes into a reflector.  The reflector sends it back into the leftmost rotor at another point, which translates it to another letter and sends it to the middle wheel and eventually back through the rightmost rotor and back through the plugboard to the lamp panel:

The rotors advance before each keypress, like the dials in odometer.  The rightmost rotor advances each keypress and notches on it advance the middle rotor once per full revolution.  The middle rotor also has notches on it and can knock the other wheels once each full revolution.

The Enigma has a lot of possible settings.

First, there are the combinations of 3 rotors and 1 reflector.  The M3 started with 3 rotors and two reflectors; then the Navy added 2 more, and the army followed suit, and then the navy upped it to 8.  There are 6 ways to order 3 rotors, 60 ways to pick from 5 rotors and 336 ways to pick from 8.  There were two reflectors to choose from.  So worst case 672 combinations of rotor and reflector.

Then each rotor has 26 possible starting positions (A through Z).  26 x 26 x 26 is 17,576.

Then the middle and right rotors have 26 possible ring positions, which affects when they ‘knock' the other rotors into rotating.  (The leftmost rotor has a ring too, but has no impact on encryption when its the leftmost ring.)  There are therefore 26 x 26 = 676 ring combinations.  However, as a slight detail, not all messages are long enough to cause the middle ring to knock and therefore the impact of the rings is a function of the length of the message.  To simplify things I am going to ignore this, meaning my attack is going to blindly iterate over equivalent rotor settings on short messages.

Finally, we have the plugboard.  Early on 6 pairs of letters were swapped and later this was changed to 10 pairs.  There are 100,391,791,500 ways to order 6 pairs and 150,738,274,937,250 ways to order 10.

So the early M3 Enigmas had:

2 x 6 x 17,576 x 676 x 100,391,791,500 = 14,313,511,465,501,248,000 keys

And the later M3s had:

2 x 336 x 17,576 x 676 x 150,738,274,937,250 = 1,203,537,298,065,206,936,832,000 keys

These are very very big numbers!  The earliest M3 is providing 64-bits key and the later M3s 80-bits.  (As usual, I find slightly different numbers quoted in various texts where e.g. the number of reflectors is disregarded.  Corrections welcome!)

The World War 2 attacks on the Enigma were very very very clever and, in hindsight, the Germans didn't understand the weaknesses nor make things as difficult for the allies as they could have.  The Germans considered the number of combinations as astronomically more than those massive numbers above because they didn’t realise that the rotor wirings were known to the allies.  The Poles correctly determined and guessed the wirings just by analyzing a manual a spy gave them.  Later, as more wheels were added, the allies set out to capture them by boarding captured boats and such.  This was despite the fact that they themselves captured the equivalent British TypeX cipher machine at Dunkirk.  Let this be a message to those relying on the obscurity of the algorithm itself! (When Admiral Dönitz commissioned the M4 Engima for his U-boat fleet, was he thinking there was a spy with access to the surface fleet day keys?)

The allies took advantage of the fact that messages were predictable and that the Enigma never ever encrypted a letter as itself.  This provided them with ‘cribs’ that dramatically cut down the search space.

However, my attack is thoroughly modern and uncunning.  I’m going to try and use computing brute force which, unavailable in World War 2, is now at my fingertips in my oldish slowish laptop!  What takes world-beating cleverness in the wartime can now be done by dumb repetition by a schoolboy-level-programmer in 2016! :)

So, if we get a computer to iterate over all the possible keys, how does it know which key is the correct one?  A human would have to know German and read each decrypt and see if it made sense.  A computer can look the decrypt up in a German dictionary and German grammar too.  Or we could short cut that and say that, if we have the key wrong, then the outcome should be seemingly random.  If the outcome isn't random, i.e. there's a very uneven distribution of letter frequencies, then its a good candidate decrypt for human intervention.

Having show you how big the numbers are, you can see how daunting a brute-force attack would be.  However, I'm going to disregard the plugboard.  If we disregard the plugboard then suddenly the numbers become much much smaller.

The thing about the plugboard is that it doesn't swap all the letters, and letters it doesn't swap have the usual frequency in the decrypt.  The swapped letters get garbled in the decrypt, but if sufficient letters go through ungarbled then the frequency counts of the letters should still be uneven enough to trigger it being treated as a candidate solution.  The job then becomes to discover a plugboard that makes sense of the garbled parts of the message.

In the Cipher Challenge, the Enigma stage 8 has the three rotors and the reflector specified.  These are actually the I, II and III rings and the B reflector.  We just don't know the order of the rotors nor the starting positions nor the rings.

1 x 6 x 17,576 x 676 = 71,288,256

71M is a very small number for a modern computer.  My computer can, on a single core, iterate through all 71M possible rotor start positions and decrypt the message in under 10 minutes, using just one core.  I have four cores, so wall-clock time could be under 3 minutes, and this is a 2014 laptop.  (It would have been feasible - given days to weeks - to tackle this on a 286 too.  I would have optimised harder.)

To judge the randomness of the decrypt I just work out the frequency of the most common letter.  Here is the distribution for the Cipher Challenge text:

42 = 13 41 = 27 40 = 18 39 = 56 38 = 92 37 = 277 36 = 536 35 = 1132 34 = 3228 33 = 8697 32 = 21143 31 = 49767 30 = 115703 29 = 256947 28 = 550083 27 = 1124947 26 = 2194175 25 = 4036371 24 = 6904511 23 = 10651956 22 = 14097448 21 = 14880108 20 = 10951117 19 = 4615207 18 = 792354 17 = 32251 16 = 92

There are 367 characters in the message and there are 26 characters in the alphabet so the average would be 14.  Most of the decrypts are rather noisy.  Only a handful are not noisy and worthy of further consideration.   (In fact, most of these are actually duplicate results caused by the middle ring not rotating.  If we just greedily decrypt the highest candidates we happen hit the true solution immediately.)

This is the decrypt of the Cipher Challenge text, picking the rotor settings with highest maximum frequency in the decrypt, ignoring the plugboard:

VRAxKTZYIJgAwYKNJRAOIpKCOTxxAOMfQxDIMINZPOhSIStMCEJIxUEOVIEKMJgPd ETxFSOxYIAxLnMLTdEIrOOEsDKxWchRKJbULdaHHKEJWsstehIJdIxbHVIxNIAEAc hKVIYAIKAxIJtJIcLOxxIPxEFORIEHAxIHJAxHTrTIIZJTxzIrTPWNrGYIBJUZIEJ AZIEJXxMEThMUXNgPSUEGTrIIVEIsxMJWNenOdIcLRITdPNOZdSFxRTDOxIRDMVgM rxNIGJEIQxXWOYdBUxzWgrRAVPKXNgMJNIJxAchKMIAAIRKJJOLTAZIXZTwUKZxal XxrYDDDOSOMdEIxAchPEfOMIEWJUMLNJOOGxKrIMbO

The 91 lowercase letters are actually correct and the uppercase letters garbled, its just that at this point we don't know that.  We have to find a plugboard that turns this into German (where, as was the convention, X means space and XX means full stop).

Here are the frequencies in this decrypt:

A = 20, B = 5, C = 8, D = 16, E = 21, F = 5, G = 10 H = 13, I = 41, J = 22, K = 14, L = 8, M = 16, N = 13 O = 21, P = 9, Q = 2, R = 18, S = 10, T = 17, U = 8 V = 7, W = 9, X = 36, Y = 7, Z = 11

Now for some detective work.  Lets attack this manually by guessing.  We know that in German E is the most common letter (16%) followed by D, C and A (5%, 3%, 2% respectively).  However, this being Enigma plaintext, we expect X to be really common too.

We see in our decrypt that we have several X, several XX and no XXX, so we can guess that X is unplugged! If we replace the X with spaces, here's what we get:

VRA KTZYIJgAwYKNJRAOIpKCOT  AOMfQ DIMINZPOhSIStMCEJI UEOVIEKMJgPd ET FSO YIA LnMLTdEIrOOEsDK WchRKJbULdaHHKEJWsstehIJdI bHVI NIAEAc hKVIYAIKA IJtJIcLO  IP EFORIEHA IHJA HTrTIIZJT zIrTPWNrGYIBJUZIEJ AZIEJ  METhMU NgPSUEGTrIIVEIs MJWNenOdIcLRITdPNOZdSF RTDO IRDMVgM r NIGJEIQ  WOYdBU zWgrRAVPK NgMJNIJ AchKMIAAIRKJJOLTAZI ZTwUKZ al   rYDDDOSOMdEI AchPEfOMIEWJUMLNJOOG KrIMbO

The most common letter in our decrypt is I, so lets assume this is E.  If we set up the plugboard to swap E and I, lets see what we get:

VRA KTZAEJgAwYKN RAOEpKCOT  AOMfQ JeME ZPOhSeStMCiJe UiOVeiKMJgPd iT FSO YeA LnMLTdierOOisD  WchRKSbU daHHKiJWsstIheJde bHVe NeAIAc hKVeYAeKA eJtJecLO  eP iFOReiHA eHJA HTrTEeZJT zerTPWNrG eBJAZeiJ A eiJ  MiThMU TgrSUIGTrEeVIes MJWNenOdecLReTdPAAZdSF RTDO ERDMVgM r NeGJIeA UWO dBU zWgrMJVPK NgMJNeJ AchKMeAAeR JJOLTAZe ZTwUKZ al A rYDDKOSOMdie AchrifOMeiWhUMLNJOOG KrEMbO

The 150 lowercase letters are now correct, but we still don't know that.  We just think we are getting somewhere because we look at the frequencies E is now the most common:

A = 25, B = 5, C = 8, D = 14, E = 42, F = 5, G = 10 H = 14, I = 20, J = 21, K = 13, L = 7, M = 17, N = 10 O = 20, P = 7, Q = 1, R = 19, S = 11, T = 18, U = 8 V = 7, W = 9, X = 42, Y = 4, Z = 10

However, D is not looking so good.  We search now to see what D should be swapped with...

I searched in vain.  D isn't swapped with anything, its just that we are attacking the noise at this point.

My next idea was that SS ought occur in the output.  So far it occurs once.  The only other double letters that occur more often are two AAs and two OOs.  I speculated that A was swapped with S, meaning to try again with O swapped with S if I ended up getting stuck later.  Here is what A swapped with S looks like:

VRs KTesMJgswYrO RsOEpKCOT  sOMfQ JeME ZPOhaeAtMCiJe UiOVeiKMJgPd iT FAO Yes LnMLTdierOOiAD  ichRKabe daH KiJWAsOeheJde bHOe NesIsc hKMeYseKs eJtJecLO  eP iFOReiHs eHJs HerTEeZJT zerTPWerG eBJs eiJ s eiJ  MichMU TgraUIGTrEe Ies MJWNenOdecLReTdPssZdaF wTDO ERDMVge r NeGJIes UWO deU zMgrMJVeK NgeJNeJ schKMesseR JJOLTSZerO wiKZ SK s rYDDKOaO die schrifOzeiWhUM NJOOJ KrEibO

You can clearly see words popping out; my own eye is drawn to the “die” on the bottom line.  Other repeated words such as “EIJ” are shouting out for a J and N swap.

And so I attacked the plugboard manually, despite not knowing German.  I could have automated this, but I didn't need to.  The final text fell away before my eyes:

DAS LOESUNGSWORT IST PLUTO. STUFE NEUN ENTHAELT EINE MITTEILUNG DIE MIT DES ENTKODIERT IST. ICH HABE DAS LINKSSTEHENDE BYTE DES SCHLUESSELS ENTDECKT. ES IST EINS EINS ZERO EINS ZERO ZERO EINS EINS EINS. ICH PROGRAMMIERTE DES UND ENTDECKTE DASS DAS WORT DEB UGGER WENN ES MIT DEM ZUGRUNDELIEGENDEN SCHLUESSEL ENTKODIERT WIRD ALS RESULTAT DIE SCHRIFTZEICHEN UNTEN ERGIBT

The rotor order was III, II then I; the wheel positions were A, F and L and the rings were 26 and 1 respectively. The plugboard was EI AS NJ KL TO and UM.

Google translate tells me that:

THE SOLUTION WORD IS PLUTO. STAGE NINE CONTAINS A MESSAGE WITH THE ENTKODIERT IS. I HAVE THE LEFT STANDING BYTE OF THE KEY DISCOVERED. IT IS ONE ONE ZERO ONE ZERO ZERO ONE ONE ONE. I PROGRAM OF AND DISCOVERED THAT THE WORD DEBUGGER IF IT WITH THE UNDERLYING KEY ENTKODIERT IS AS A RESULT THE CHARACTERS BELOW SHOWS

Now to extend the attack against the M4 used by the U-boats:

The M4 had a two ‘greek' wheels which could be combined in one of 26 positions with two ‘thin' reflectors to make a composite reflector.  The M4 had the full 8 normal rotors to choose between too, so the total number of combinations without the 10 pair plugboard is:

2 x 26 x 26 x 336 x 17,576 x 676 = 5,397,376,438,272

That's actually a bit beyond where I want to be with my laptop in the summer!

However, lets look at how random messages are before they have entered the reflector.  Here are the frequencies for the Cipher Challenge text again, but counted before they enter the reflector:

36 = 156 35 = 1482 34 = 4706 33 = 11024 32 = 23400 31 = 49218 30 = 117182 29 = 252122 28 = 526396 27 = 1107028 26 = 2156674 25 = 3930160 24 = 6800664 23 = 10674482 22 = 14215630 21 = 15105272 20 = 10923458 19 = 4577118 18 = 783770 17 = 28210 16 = 104

Again a few combinations are far less random-seeming than the rest!  (In fact, the real solution is again top of the pile.)  The computer can focus on just the top candidates and crank through the 2 x 26 x 26 possible composite reflectors for each.

[williamedwardscoder]

A brief history of the Enigma and the pre-war cracking of it

A lot of people now think that Alan Turing cracked the Enigma.  A lot of people like to correct those people and say that it was the Poles who truly cracked the Enigma.  So we really need to correct everyone and set things straight, because it was far more nuanced than that, with far more people involved, and different versions of Enigma were cracked even earlier.  If you read enough about code breaking you end up with a fuzzy timeline in your head pieced together from all the various sources.  Here’s what I’ve osmosed:

During WWI the allies broke the German ciphers wide open.  And straight after the war various brits rather stupidly said so.  A young Winston Churchill was one of those to mention it.  Some Germans took notice.

In early post-WWI Germany a young engineer called  Arthur Scherbius invented the Enigma cipher machine.  It was expensive so didn’t get widely adopted.  It was available commercially although sales were weak, and the Italian navy (who were our allies during WWI) and the Swiss army brought it.  These early Enigma variants would be met during the Spanish revolution and WWII.  The German navy also brought and weakened this early Enigma too, but would supplant it with later variants before the war began.

In 1927 a brit called Hugh Foss did a cryptoanalysis and worked out how to break this early Enigma.  This early Enigma had no plugboard and a long string of countries would eventually break it on their own, including Poland, France and the United States.

One of the Germans who had taken heed of the allied boast of cracking their codes was Rudolph Schmidt.  When he became chief of staff to the signal corps he decided that the German army needed strong mechanical encryption.  The Enigma adopted by the German army was modified to include a plugboard and the wiring order of the keys also differed.  New rotors with different internal wiring were also used.

The very successful Rudolph Schmidt had an unsuccessful younger brother called Hans Thilo Schmidt.  Rudolph tried to help Hans by giving him a job but Hans resented Rudolph in particular and Germany in general enough that he decided to sell the secrets of the Enigma to the French.

The French were interested, but at that early time their cryptographers thought the Enigma unbreakable and shrugged their shoulders.  The French had a treaty so gave the info to their new allies the Poles.  The Poles, though, were acutely interested in breaking German comms and set about it with urgency.

The Poles were getting the actual day keys from Hans via the French, but they withheld them from their cryptographers.  Their cryptographers, particularly Marian Rejewski, not knowing the keys were actually known, set about cracking it from first principles and they succeeded!  Their attack was based upon the repetition of the message key at the start of each message.

During the Spanish civil war the brits, lead by the WWI veteran Dilly Knox, broke the early Enigma in use by the Condor Legion as Hugh Foss had laid out a decade earlier.

However, Dilly Knox thought the much more modern Enigma used by the German military at home was unbreakable.  Then, as war loomed, the Germans stopped repeating their message key at the start of each message and the Polish attack stopped working.  The Poles, in desperation, showed everything they had done to their allies France and Britain.  This was a revelation, and the most important thing was it showed that the Enigma had been beaten and made people seriously consider if it could be broken again.  Its all about mindset!

Dilly Knox was dying of cancer but continued to contribute massively in the early years of the war.  He worked on the Italian codes, which were still using the early Enigma, and he very finally broke the modified Abwehr Enigma, which was crucial to the success of the Double-Cross spy-turning system.

Dilly Knox made way for a new kind of cryptographer who had came from a mathematical background, including Alan Turing.  But Alan was not alone.

[williamedwardscoder]

Fast Enigma sim in C++

Following on from my Python Enigma cipher machine simulator, I re-wrote it in C++ for maximum speed.

The settings for each rotor - its start position and ring setting - can actually be combined into a single offset. This is perhaps why all the popular treatments of the subject just ignore the impact of the rings on the number of combinations. In truth, their impact is hard to explain. The rings change when rotors rotate, and do have an impact on the number of combinations, but many initial starting positions are equivilent for short messages because the rings cancel out the rotor start position and do not cause a rotation because the message is too short.

The M4 Enigma - as infamously used by the U-boats - is usually described as a 'four rotor' machine. And that's strictly true, I suppose, but I think I have a better way of describing it:

The M4 was a normal 3-rotor M3 Enigma chassis. A new 'thin' reflector design was developed that could take a new, thinner 'greek' non-rotating wheel. The thin greek wheel could be placed in any of 26 positions and clicked into the thin reflector. This could then be placed in the chassis in the normal reflector position.

So basically the M4 is an M3 Enigma with a configurable reflector.

I wrote the fast Enigma sim to serve as a basis of a statistical attack on the Enigma. In fact, if you look at my test vectors, you'll notice one of them is Simon Singh's Cipher Challenge Enigma stage 8, which I cracked using my statistical attack! More on that in the next post :)

And here's the code. As you can see, the vast majority of the code is just test vectors to ensure its correctness:

[williamedwardscoder]

Enigma Machine on Paper and Python

(don't forget to also read: my attack on the Enigma cipher machine)

It turns out my kids have been sending each other secret messages, enciphered with a substitution cipher of their own invention!  They only let me see the secret key when I agreed to help them mix up a very complicated recipe for invisible ink:

This reawakened fond memories of a young me getting a good way through Simon Singh’s The Code Book cipher challenge :)  (Also, see the Enigma Spreadsheet my friend made a few years ago!)

So my mind raced considering how fast todays laptops can brute-force, say, Enigma?  Even non-brute-force attacks are on a different scale if you have a computer.  For example, with Enigma, can you ignore the plugboard and go through every combination of day and message key, using a histogram to spot possible text that you then attack as a substitution cipher?

First I needed an accurate Enigma simulator.  To be honest, I found most descriptions a bit light on detail.  But I quickly found a paper Enigma, which I made:

From this, I was able to create a Python Enigma machine!  Source available here:

Now to crack Simon Singh’s Cipher Challenge :)

[williamedwardscoder]

Dividing and conquering summation

Here’s a very simple function:

char foo(char a, char b, char c, char d) { return a + b + c + d; }

What do you think the optimal approach for adding four integers is?

One approach is to keep a running total and add each term in turn:

foo: addb %dil, %sil addb %dl, %sil addb %cl, %sil movsbl %sil, %eax retq

And that is exactly what Clang+LLVM 3.8 does!

When I encountered this I did a second take. The obvious way to get better instruction-level parallelism is to add a+b and add c+d, and then add the two partial sums. The CPU will be able to perform these adds in parallel because they do not depend on each other.

At this point I became very interested to know what other compilers do. I found an excellent online tool for showing what various compilers generate: godbolt the compiler explorer! https://gcc.godbolt.org/#

Here is what GCC does:

foo: leal (%rcx,%rdx), %eax addl %esi, %eax addl %edi, %eax ret

This is dividing and conquering the summation. Here's what Intel's ICC compiler does too:

foo: addl %esi, %edi addl %ecx, %edx addl %edx, %edi movl %edi, %eax ret

So how could I have possibly found such a blatant missed optimisation in LLVM??!!? I have asked my friendly x86 mega-expert and it will be interesting to hear what he thinks of the code various compilers generate!

[williamedwardscoder]

Duck typing

Old but great:

[williamedwardscoder]

Ludum Dare #35 Mosaic

Its becoming a Ludum Dare tradition that I make a mosaic for each competition. I didn’t enter this time, but I still made a nice mosaic:

[williamedwardscoder]

Securing the iPhone

The FBI want a backdoor on the iPhone and they are trying to force and shame Apple publicly into giving them one.

The phone they want Apple to decrypt was used by a San Bernardino terrorist.  Surely everyone is rooting for the FBI on this one?!  As long as the news focuses on that part, public sentiment will be firmly on the FBI’s side on this one... bad bad Apple!

Of course, its just an excuse.  Its a very transparent excuse, but only if you look past the shock awe headlines:

The San Bernardino terrorist had two phones.  He carefully completely destroyed his personal phone before the attacks.  The remaining phone is his work phone, owned by the government (he was their employee).  The FBI say they want to see correspondence the attacker made with his coworkers.  But they can already get that information from the coworkers phones etc.  Just a cursory glance dispels the importance of getting into this one phone the attacker didn’t deem worth destroying.

The White House went so far as to say that the FBI specifically didn’t want a ‘backdoor’, they just wanted access to this one iPhone.

There must be using their own definition of backdoor then!

The key problem here is twofold:

* that as soon as the precedence is set, law enforcement will be able to get all phones unlocked and for increasingly minor offenses.  Within a year or two, councils in England will be insisting phones are unlocked when investigating school catchment area cheating.

* that it will inevitably leak.  The Chinese have used lax law enforcement security to breach Google before, and they’ll do it again.  They will get hold of it. And so will the Russians and the North Koreans and even Uzbekistan in its international war on dissidents.  The Chinese will get similar privileged access to pretty much all phones anyway as they actually manufacture them, and the Russians and every other bad-guy nation state will get into everything too.  Its just a given.

Eventually, muggers will be unlocking phones before resale to scrape them for passwords and pin-codes and see if there’s any electronic wallet swipe payment thing they can empty.

Both these aspects scare the life out of me.  But its the second point that is being discussed least, so its lets extrapolate into how that affects our business interests all over the world:

When I’ve travelled on business I’ve taken care to use encryption.  I’ve never been stopped at a border, but many people have.  And when you are stopped, you sit in a little interview room for an hour or two (if you’re lucky) and then you are allowed on your way.  And you know that they are busy photocopying every piece of paper you have and imaging your hard-disks.

The US are one of the worst offenders of this, but you can expect the same treatment in whatever country has business interests in whatever it is you are working on.  US businesspeople traveling to China should take precautions.

It is not about terrorism and drug smuggling.  Its about blatant commercial espionage, blessed by the governments.

Its not enough now for Apple to refuse to do it.  The only way forward is for Apple to ensure it cannot do it on future Apple products.  And everyone else must lock down their phones too.

All phones need Apple-style secure enclave.  And we need it so you cannot flash phones whilst they are locked.

This will protect phones that are turned off.  As you cross borders, turn your phone off.

Additionally, good phones need a duress pin-code.  By having hidden volumes with trucrypt-inspired plausible deniability we can give some measure of protection against the $5 wrench attacks as you transit through a hostile countries...

[williamedwardscoder]

New Security through Technology

I was just reading this horrible story of digital harassment about a family whose life is ruined by internet trolls their ‘hacker’ son fell out with.  Its not the first such story, and it won’t be the last.  I think this horror will grow rather than abate as more and more kids discover the rush of invincibility from hurting people remotely.  The youth of the world is getting online...

I’m too grown up to understand lulz.  Seems so sad.  Pity the perpetrators.  But due to jurisdiction and anonymity, I would be surprised if they can be brought to task for their crimes.

Now on a technical note, the perpetrators often seem to exercise terrible trade craft.  They often seem to be able to be tracked down, which surprises me.

Bruce says “we need to figure out how to identify perpetrators like this without destroying Internet privacy in the process”.  Here’s how I think we can do that:

There are lots of balancing to be done here.  Privacy from whom?  Will banks start selling our purchase histories to data miners?

What I think we need instead is to move to a new age where technology brings authorization to our interactions.

In Sweden a new banking service called Swish is taking off.  Its just a mobile app that is connected to your bank account and makes it very easy to transfer money between people.  Its supported by all the main banks.  Its rightly popular in a country that is increasingly moving away from the anonymity of cash.

I think modern technology can make the world a better place.  The insecurity of phone calls and VOIP with caller-ID-spoofing, for example, can be tackled.  The insecurity of passwords and such can be tackled with 2FA etc.

When ordering a pizza (even when using a normal landline) an electronic payment for the pizza should be escrowed.  This payment-up-front can be anonymized to the recipient so they don’t get to see the bank details of the payer, but they do get certainty that its paid for.

And all phone calls over VOIP should be authenticated.  Again, the caller can be anonymized to the recipient, although perhaps not their general location, but the caller should know that the phone company knows who is placing the call,  and the recipient knows the general whereabouts of that user.

This means that pizza restaurants the world over can be skeptical when receiving an order to a local location from a phone abroad etc.

The general adoption of authentication can make twitter more sure who is posting etc too.

Such a system needs clear legislation to prevent data mining and to have clear liability and such.  The privacy of the customer has to be total.  In the same way we think it completely unethical for your bank to share your purchase history, or for your bank to give the government access without a warrant etc, we have to ensure that new systems don’t bring a default lack of privacy.

So, in general, as we move from classic VOIP towards, say, WebRTC, there is the opportunity for integrating authorization and authentication.  The caller picks authorization or authentication, and the callee understands the distinction when the answer.  This can be integrated with payments that provide authorization to the recipient and 2FA to authenticate the sender.

Its possible - I don’t think it probable, but its clearly technically possible - that such systems could also be built to work with reputation rather than identity, and anonymous payment systems such as bitcoin.  Perhaps the classic ‘bank’ doesn’t have to be in on the equation.  However, I think the reality is that it can be the banks and the big internet companies who make this possible and force penetration and adoption, and that’s still a much better world than where we are today.

Most of the world already has a phone.  Lets hope these phones can become safe secure authenticators.  Lets hope accounts and services stop being protected online by passwords!

This will place a higher bar on the lulz hackers.  They have to go after higher-value credentials and spend theirs or someone’s money to do these attacks, and take over people’s phones to make these swatting calls etc.

And I understand that the US is still a cash economy - I’ve visited a few times just not recently - but this will eventually change.  When it does, its a great opportunity to actually improve things but adding in authorization, where the recipient sees anonymity - protecting the customer’s privacy - whilst the bank requires authentication.

Here’s an old related blog post about someone whose 2FA was hacked.  Its a fun read.

[williamedwardscoder]

Where are all the Raspberry Pi robots?

My daughters are really into robots.  They love going to the science camps during school holidays and the highlight is always programming the lego mindstorm robots.

So I got all excited about getting them a robot for xmas, and so I went looking.  My friend Roy recently blogged about robots (hacking a Roomba! and Makeblock) and this really wetted my appetite :)

In the end I got them a SparkFun Redbot inventor kit.  Its an Arduino with line followers, whiskers, accelerometer for bump detection and magnetic wheel rotation counters.

But its really bugging me how limited the Arduino is!

Here’s the Raspberry Pi Zero that I read about recently:

The Arduino is a very expensive weakling!  Raspberry Pis are fast proper computers, roughly equiv to a laptop from just a few years ago.

All Raspberry Pis have good connectivity.  Those holes along the edge in that picture above are 27 GPIO!  All Raspberry Pis have staggering compute ability.  You could easily hook up the camera module, and even do live visual obstacle avoidance etc on the Pi.  Or stream the video over wifi to a computer if you want even more ooomph.  And the Raspberry Pi is affordable.  The Pi Zero is famously £5! 

So I went into this with the expectation that I’d get a Raspberry Pi for £5 and then pick up a robot chassis with motors and sensors that just slotted into the GPIO header.

And there simply aren’t any!  If you google for it sure there are very few home-build projects, but very little using the Raspberry Pi for any kind of roboting at all.  You can find a handful of images, and accounts of people trying it etc, but all the online retailers in my region there simply weren’t any!

I asked friends, some who have several Raspberry Pis...  Nobody had seen or heard of any Raspberry Pi robots.

People who use the Raspberry Pi seem to mostly use it as a cheap replacement for Apple TV.  Most Pis just languish unused, brought on a whim by a programmer with no real use for them... :(

This makes no sense to me.  I thought the Raspberry Pi was all about teaching, and imagined that every classroom would have Pi-based super-cheap robots for teaching programming...?

So I’ve gone spent easily 10x the money on an Arduino bot with 2KB RAM... :(

Now we’re quite excited about the redbot, and will be mastering mazes and things.  And hopefully get brave enough to mod it.

But I think that if it were a much more powerful computer, it would open up a whole new level of teaching, particularly using a camera sensor for driving.  Right now with the Arduino there are all kinds of platform limitations to work around and keep in mind that are just clutter and disengagement for the kids.

I might help the kids make proper robots etc.  Every programming father’s dream, right?  That’ll probably never happen, more fool me etc.  What I was expecting was that classrooms would be full of little Raspberry Pis being taught how to navigate mazes and stack blocks and things, and this just doesn’t seem to be happening :(

[williamedwardscoder]

Why Swift?

The programming blogosphere is chock full of hype with Apple open-sourcing their Swift language.

So is this exciting?  No, not really.  I can’t see what all the hype is about.

Swift is very much tied to Apple’s walled-garden of iOS app development.  Anyone developing for iPhone has to pick between anarchic Objective C and new shiny Swift.  Its a captive audience.  Its an audience unaffected by whether Swift is open-source or not.

Will Swift be used for anything else any time soon?  I think not.

If you’re developing for the server, are you going to adopt Swift?  For me, the fact that IBM is backing server-side Swift is all the death knell you need ;)

If you’re developing for the server you already have a myriad of languages to pick from.  From scripting languages like Ruby, Python and Javascript, to compiled languages like Java, C/C++ and Go, you have a full range.  If you want a ‘safer’ language you can go Haskell or Rust.  What is so compelling about adopting Swift on the server-side?   I can’t spot anything at all.

Swift on the server is going to be about as popular as C#.  Its a language you use if key parts of your project on other platforms are forced to use it.

I like how Swift reasons about integer overflow and nil.  I wish there was a ‘safe’ C.  But that’s not making me itching to go use Swift for server-side programming.

[williamedwardscoder]

Global Internet Experts Reveal Plan for More Secure, Reliable Wi-Fi Routers - and Internet

I’m not really a global internet expert, but I am one of the less notable signees:

http://www.businesswire.com/news/home/20151014005564/en#.Vh7BpxOqqko

I signed in a personal capacity.  Seems strange to see my name and address being sent off to the US government.  Surely if I was on any watch list before, I’m on the ‘too boring to watch’ list now :)

I don’t seem to do things I can share freely any more, so its nice to have something to post after all this time :)