Happy Feet!

Mumble, from Happy Feet, via YouTube.com

It seems obvious in retrospect. Look at the way penguins walk, then watch Happy Feet, and tap seems like the inevitable style for a dancing penguin.

But maybe that’s just because of the masterful dancing (via motion capture) by the amazingly talented Savion Glover (who was also co-choreographer). For any not familiar with him, Glover got his start on Broadway at age 11, appeared on Sesame Street in his teens, and was called “possibly the best tap dancer that ever lived”.

Right. Sure. Anyone can say stuff like that, but this quote was from the legendary tap dancer (and actor, and choreographer, and singer) Gregory Hines, who can safely be considered an expert in this area.

Happy Feet is about an emperor penguin called Mumble. While other emperor penguins sing to find mates, Mumble cannot sing, and is mocked for dancing instead. He is ostracized and eventually exiled, but ends up saving the day. Fun film, with a LOT of wonderful voice actors, and penguins singing and dancing. What’s not to like?

And that is how we get to encryption.

Cryptography is a complicated topic that I’ve touched on before, but there’s always another level, or some nuance to dig into.

But, wait! How did we get from dancing penguins to encryption?

Well, I wanted to talk about stream ciphers, and how they differ from block ciphers.

Uh, what ?

The specific stream cipher I wanted to look at is called ChaCha, and it’s derived from another one called Salsa20.

Groan.

To summarize (and simplify) the context, cryptography is generally broken into two main categories, “asymmetric” and “symmetric”. Asymmetric cryptography is based on a public/private “key pair”, where a “public” key is shared with everyone, and the “private” key is kept secure and used to prove identity. One common example of its use is for browsing via HTTPS, where asymmetric cryptography is used to establish a connection, which is used to “negotiate” a shared key for further communication, because asymmetric encryption is relatively slow and inefficient.

This shared key brings us to symmetric encryption, which can further be broken down into “block” ciphers and “stream” ciphers.

Block ciphers operate on fixed-length blocks of data, and “pad” any odd-sized blocks to ensure consistency and prevent “leakage” of information based on the size of the packets sent. In contrast, stream ciphers are used to generate a “pseudo-random” “key-stream”, which is combined with the data being sent via an “XOR” (exclusive OR) operation. This goes through the data and the key-stream bit-by-bit, resulting in a 1 if the bits are different, and 0 if the bits are the same. To return to the original value, just perform the same operation, using the same key-stream.

The beauty of this is that the XOR operation is extremely fast, efficient, and consistent (so no “side-channel” attacks based on how long the encryption takes), but the strength of the encryption is based almost entirely on the strength of the key-stream.

All of this is based on the only true “unbreakable” encryption scheme, the so-called “one-time pad”. This approach was described almost one hundred and fifty years ago, and involves using a randomly-determined stream of numbers, letters, (or bits), known as the “pad” which are combined with the message to be sent. This approach has been mathematically demonstrated to be truly “secure” in the cryptographic sense (ie, it cannot be broken via cryptographic means), but has several major challenges.

First, the pad must be as long (or longer) than the message. Easy enough for short messages, but this becomes more and more cumbersome as the length of the messages increase.

Second, the pad must be shared between the two parties, in a way which guarantees that it cannot be intercepted. Relatively easy for two people to meet in person and share a code-book (though not without other risks), but utterly impractical for the internet.

Third, the pad must be truly random. And while there are sources of “true” randomness, it can be challenging to “capture” it. One example of a true random number generator is Lavarand, which digitized the patterns inside an array of lava lamps. The numbers generated are truly random, but the process is slow and cannot be practically scaled.

So, one-time pads provide “perfect” security, but are utterly impractical for internet-scale communication. What to do?

What if we had a way to quickly generate large amounts of data which, while not truly random, are practically nearly impossible to predict by a third party?

This is where the concept of a pseudorandom number generator (PRNG) comes in. For illustration, what if we decided to use the digits of the number π (pi) as our pad? The number is not random, but would be easy to share between two parties, and unless someone knew we were using π (3.141592653589793238462643383279502884197169399375..., and so on), it might be sufficiently “random” for effective cryptography.

A PRNG is an algorithm for generating “a sequence of numbers whose properties approximate the properties of sequences of random numbers”, based on a set of mathematical criteria. But not all PRNGs are useful for cryptographic purposes, which leads to the concept of a “cryptographically secure pseudorandom number generator” (CSPRNG), which must meet a number of additional criteria.

Eventually, though, we arrive at a set of tools which can be used to reliably generate a pseudo-random key-stream, based on a shared “seed” value. After the seed is generated and shared – via asymmetric encryption – the cipher essentially behaves as a one-time pad.

The ChaCha stream cipher was developed in 2008, a few years after the closely-related Salsa20 cipher (2005). It is used frequently in mobile devices, has several versions (such as “ChaCha20” and “XChaCha20”), acts as a “pure” stream cipher (ie, encrypting data one bit at a time), and is sometimes preferred for this reason.

For comparison, AES (Advanced Encryption Standard) has a “block” mode which can be used to behave like a stream cipher, but does not encrypt one bit at a time. It also does not generally perform as well as ChaCha unless the system in question has dedicated “AES acceleration” features.

While AES certainly dominates as a block cipher, it is not necessarily optimized for stream use, and is generally more complicated to implement.

ChaCha is newer, simpler and faster to implement, doesn’t require specialized hardware for efficient performance, and is becoming very popular, particularly in mobile devices and less powerful processors.

For now, at least, ChaCha is popular, so we should all Dance Dance Dance!

Cheers!