Pages

2014-01-11

mt-crypt - a simple stream cipher based on the Mersenne Twister PRNG

It's often said: "Anyone can write a crypto algorithm they can't break themselves". True enough, but that doesn't mean it should be forbidden to study or write crypto software because, well, one isn't an expert in studying or writing crypto software -- that would be a Catch-22 of sorts.

What's the entry point then, for someone who wants to understand? One learns by doing.

In light of the Snowden leaks of 2013 I think it's time that writing crypto became something to be encouraged rather than discouraged. Treating crypto software as a 'read-only' institution can't work -- we simply cannot trust a few blessed experts to write our crypto libraries and utilities for us. People outside of the shadowed halls of three-letter agencies must gain their own expertise, or at least become familiar enough with the concepts to ask intelligent questions, look for backdoors and weaknesses, try to apply new defenses to what should be private data, and just generally not be passive victims.

It has become more important than ever that there be a diversity of implementation, and that programmers who might have been hesitant before to write crypto programs start doing so.

I'm not saying one should apply any ol' system to important data. Algorithms must be carefully examined by many eyes to look for problems and determine the real security of any new system. But if everyone's afraid to write new systems, there won't be very much to examine, and not enough alternatives to keep those who would spy on us off-balance.

If the NSA's goal was/is to subvert the most prevalent cryptosystems, it makes sense to ensure there are no prevalent cryptosystems. We need to take the side of the mythical Hydra, whose winning strategy is to grow two heads for each one cut off, making things even harder for the attacker.

To do this, we all need to better understand just what strong crypto is and how to implement it so there are more choices for everyone to use, and no 'master key' -- no 'most popular solution' -- for those that would spy indiscriminately on us all by exploiting a single weakness. If the haystack cannot adequately hide the needle, we need to throw on a lot more hay, and add a few million more needles in there. If the opponent's resources are superior, an open battlefield no longer is tenable and we must use guerilla tactics -- divide and conquer, stay in small groups, change routines constantly.

[OK I'm done with the metaphors... and I'm probably on all the watch lists now :/]

With the above in mind, I started reading about alternative, non-NIST algorithms to see what's out there and how I might implement my own crypto utilities. I started out trying to implement a standard block cipher along the lines of DES or AES, trying to understand what S-boxes (substitution) and P-boxes (permutation/confusion) did, and how to use them.

Most block ciphers use multiple rounds of (S-box, P-box) manipulations, one followed by the other applied in multiple rounds with some sort of key schedule, to achieve an invertible transformation. Lots of arcane math goes into S-box design which made me a bit queasy.. I still need to learn a lot about that before I'm confident about designing such a thing.

Another big worry with block ciphers is the problem of padding. If you're trying to use a block cipher on files, or when encapsulating packets, the file as a whole, or each packet's payload, may not be a multiple of the blocksize; so the ciphertext must be padded somehow to be a multiple of the blocksize. There are 'padding oracle' attacks that make it dangerous to use block ciphers unless one understands the block padding issues completely. See here or here for some good explanations on how one can 'unzip' an encrypted CBC-mode block train if the padding scheme is known. Indeed, having any predetermined format or structure outside of the ciphertext itself can open things up to oracle attacks it seems.

So a stream cipher seems to be a safer entry point for learning and research for a would-be crypto programmer. A stream cipher doesn't encrypt a block at a time, rather it's a byte- or bit-oriented system that can handle arbitrary-length data. There is no concept of a blocksize, and thus no opportunity or temptation to introduce 'meta-data'. Usually this requires a 'cryptographically-secure PRNG' (pseudo-random number generator); that is, one that is very hard to predict so long as the seed (which is mathematically derived from the key) isn't known.

A cryptographic PRNG must meet a much higher standard for randomness and non-predictability than the 'usual' PRNGs used in standard libraries and games...

I knew of the Mersenne Twister (MT), a really good PRNG with an astoundingly huge period (2^19937-1). That sounded like a good candidate, but the literature says even that isn't cryptographically-secure enough, since despite a long period it still is subject to prediction attacks given enough PRNG output. The authors of MT wrote a paper addressing this, with an ingenious and simple scheme to harden the use of MT -- this consists of two things: a) a non-linear transformation on the PRNG output, and b) throwing away most bits of the PRNG output before combining with the plaintext. It would seem this makes it very hard indeed to know the state of the PRNG and to predict its output as used with a stream cipher.

A distinguisher is still plausible (see here), but no one has published a full-on key recovery attack as of yet and the researchers make no assertion that this is even possible from the distinguisher. The so-far-theoretical attack lets one determine that a stream of ciphertext likely is using Mersenne Twister as its underlying PRNG by observing 2^50 bits of contiguous ciphertext.

Now that's still a lot of data -- 2^47 bytes. Though some claim this cipher is 'broken' in the pure cryptographic sense, it seems it would be perfectly salvageable if one were to re-seed conservatively.

The idea would essentially be to re-seed on some interval between every 2^8 and 2^24 bits (2^16 to 2^32 bytes), based on the PRNG stream itself; thus a sort of (perfect-?)forward secrecy on the reseed schedule would be maintained (an attacker would need to first predict the MT output itself to know when the next re-seed would occur; but they shouldn't be able to do that, since the re-seeding would always occur at much less than 2^50 output bits).

The simplicity of the cryptMT stream cipher seems compelling unless someone proves otherwise and the authors' follow-up algorithm, crypMTv3, is much more complex from a design and code perspective (they focused on speed-ups for SIMD instruction sets, which is nice but I'd rather have a simpler algorithm). Crypto designers want security, but as we've learned from the recent Heartbleed fiasco, we also want simplicity of design. Complexity introduces the very real possibility of flaws that undo all other efforts.

[Note to self: the attack described in the above paper talks about LSBs of the 8 MSBs of the accum output. Perhaps some kind of xor-with-parity of the internal cryptMT accum value could further obfuscate the LSB to harden against this attack, or using multiple MT generators with divergent seeds and states, combining them via XOR, could make it infeasible to predict a single MT stream state?]