Bunch of UAV::Pilot Updates on CPAN

UAV::Pilot::Video::Ffmpeg v0.2, UAV::Pilot, UAV::Pilot::WumpusRover v0.2, and UAV::Pilot::WumpusRover::Server v0.2

These modules just got some Yak Shaving done. Fixed up their CHANGELOG, spammed license headers on everything, and added a test for POD errors.

UAV::Pilot v0.10

Fixed a regression bug (and added a test case) of FileDump taking a filehandle.

UAV::Pilot::Command will now call uav_module_quit() on the implementation libraries for cleanup purposes.

Same Yak Shaving as above.

UAV::Pilot::ARDrone v0.2

Added bin/ardrone_display_video.pl for processing the video data. This can either
be over STDIN, or in a raw filehandle. This is implemented in a way that should work for both
Unixy operating systems and Windows.

Added UAV::Pilot::ARDrone::Video::Stream and UAV::Pilot::ARDrone::Video::Fileno to support the above.

In the uav shell for ARDrone, there is a parameter you can pass to start_video. Calling it without a parameter has the video stream handled in an external process with the fileno() method, which keeps the stream latency down. Calling it with 1 will instead use a pipe, which has a small but often noticeable lag in the video output. Calling with 2 will use the old fashioned way, which does not open an external process. Using an external process tends to take advantage of multicore CPUs better.

Nav data now correctly parses roll/pitch/yaw. The SDL output was updated to accommodate the corrected values.

Same Yak Shaving as above.

Well, I Feel Stupid

Given that the AR.Drone’s control system sends roll/pitch/yaw parameters as floats between 1.0 and -1.0, I thought the navdata sent back things the same way. I was never getting the output I expected in the SDL nav window, though.

Then last night, I was comparing how NodeCopter parses the same nav packets and seeing completely different numbers. Turns out the AR.Drone sends back numbers in millidegrees instead.

I feel dumb for not noticing this before. OTOH, this is only “documented” in the AR.Drone source code. The actual docs tell you to look at the navdata in Wireshark and figure out the rest for yourself.

Corrections are now up on github. Should be a new release of UAV::Pilot distros coming up soon. These releases will cleanup quite a few details that I wanted to get done before YAPC, so we should be in good shape.

Hopefully, the TSA won’t bother me too much with an AR.Drone in my carry-on. Some people at my local hackerspace managed to get a whole Power Wheels Racer, including the battery, into their carry-on, so I think I’ll be good.

The Performance of Seperating Control and Video Display Processes in UAV::Pilot

I’ve been running some crude benchmarks of the UAV::Pilot video timing. As I went over in my last post, I’m planning on having the video be read from the network in one process, and have it piped out to another process for decoding and display.

I added logging statements that show the exact time (using Time::HiRes::gettimeofday()) that a video packet comes in, and then another log for when we display it on the SDL window.

The first benchmark used the existing uav_video_display that’s in the UAV::Pilot distribution, reading from the file ardrone_video_stream_dump.bin. This file is in the UAV::Pilot::ARDrone distribution and is a direct dump of the network stream from an AR.Drone’s h.264 video port. It’s primarily used to run some of the video parsing tests in that distro.

I found that on my laptop, there was a delay of 12.982ms between getting the video frame and actually displaying it. At 60fps, there is a delay of 16.667ms between each frame, so this seems quite acceptable. The AR.Drone only goes up to 30fps, anyway, but it’s nice to know we have some leeway for future UAVs.

I then implemented a new script in the UAV::Pilot::ARDrone distro that read the same video frames from STDIN. I had planned on doing this with the same file noted above, like this:

But this ended up displaying only the last frame of video.

My theory on why this happens is that we use AnyEvent for everything, including reading IO and telling SDL when to display a new window. Using cat like that, there’s always more data for the AnyEvent->io watcher to grab, so SDL never gets a chance until the pipe is out of data. At that point, it still has the last frame in memory, so that’s what it displays.

I tried playing around with dd instead of cat, but got the same results.

So I broke down and connected to the actual AR.Drone with nc:

Which did the trick. This does mean that the results are not directly comparable to each other. We can still run the numbers and make sure the delay remains insignificant, though.

And indeed it did. It averaged out to 13.025ms. That alleviates my concern that using a pipe would introduce a noticeable delay and things can go right ahead with this approach.

Thinking out Loud: Managing Video and Nav Display Together in UAV::Pilot

I’ve been going back into the various UAV::Pilot distros and trying to figure out how to best approach putting video and nav data together. Ideally, navigation would overlay information directly, with a standalone nav display perhaps being an option.

That doesn’t work, because the video uses a YUV overlay in SDL to spit all the pixels to screen at once. Because of whatever hardware magic SDL does to make this work, drawing on top of those pixels has a nasty flicker effect. SDL2 might solve this, but there hasn’t been much movement on the Perl bindings in a number of months.

Using OpenGL to use the YUV video data as a texture might also solve this, and I suspect it’s the way to go in the long term. Trouble is, Perl’s OpenGL docs are lacking. They seem to assume you already have a solid grounding in how to use OpenGL in C, and you just want to move over to Perl. I messed with OpenGL ES on Android (Java) a while back, but I’m more or less starting fresh. Still, working through an OpenGL book in C might be a good exercise, and then I can revisit this in Perl.

(If anybody else wants to take up the OpenGL stuff, I would wholeheartedly endorse it.)

It would be nice if SDL let you create two separate windows in the same process, but it doesn’t seem to like that.

The trick that’s already implemented in the full releases is to take an SDL window and subdivide it into different drawing areas. This meant implementing a half-assed layout system. It also ended up breaking in the last release, as I called SDL::Video::update_rect() on the whole window, which caused nasty visual issues with the YUV overlay.

That part is fixed now by only updating parts of the layout that want to be updated. Now the problem is that displaying the nav and video together causes a half-second or so lag in the video. This is unacceptable in what should be a real-time output.

I think the way to go will be to fork() off and display the video and nav in separate processes. The central process will manage all incoming data from the video and nav network sockets, and then pipe it to its children. Then there are separate SDL windows in each process. The UAV::Pilot::SDL::Window interface (that half-assed layout system) will probably still be implemented, but will be effectively vestigial for now.

This might mean parsing the nav stream redundantly in both the master process and the nav process. There are still things in the master process that would need the nav data. But it’s probably not a big deal.

It’ll also mean all the video processing can be done on a separate CPU core, so that’s cool.

Another benefit: currently, closing the SDL window when using the uav shell will exit the whole shell. There are probably some SDL parameters I could play with to fix this, but with separate processes, this is no longer a problem.

Perl Encryption Primer: Passwords

We’ve covered most of the major building blocks of encryption and how you can use them in Perl. With those building blocks in mind, we can cover one of the most common uses of encryption that a programmer will encounter, which is how to handle passwords.

Password handling has a long history, most of it bleak. Many systems started without any passwords at all; keeping the computer physically locked in the room was considered good enough. As time went on, the machines got passwords, but CPU time was still expensive, and programmers hadn’t thought much about the security implications of storing passwords in plaintext. And that is what they did.

Still more time passes, and somebody figures that having a big database of passwords in plaintext isn’t such a good idea, so the crypt() function on Unix is used to encrypt things. This was originally based on DES (which, as we know from the block cipher post, is no longer good enough), and it truncates your password to 8 characters of 7-bits each. It then uses that password with a 12-bit salt to encrypt a string of all zeros.

What’s a salt? It’s a random value appended to the string, which should be unique for each user. We use these to thwart an attack called a Rainbow Table. Here, an attacker knows that you don’t use a salt, or knows the salt you use on all your passwords. With that information, the attacker can precompute a list of passwords and their assoicated hashes.

In the example below, we assume the same salt (“12345″) is used for crypt() (like much of the standard C library, this function is available to us directly in Perl). We start with the password “aaaaaaaa” and iterate through a few possibilities using the magic string mode of the ++ operator:

Combined with a dictionary of common passwords (and variations like “p4ssw0rD”), the attacker doesn’t need to brute force each password individually. They just need to match the hashed value to the plaintext value. With a bit of googling, you’re sure to find textfiles of precomputed Rainbow Tables, so the attacker doesn’t even have to do the hard part themselves.

Getting back to crypt(), we once again note that it forces an 8-character password of 7-bits per character (plain ASCII). This would be 8 * 7 = 56 bits, which is the DES key length. We already know that this is inadaquate against modern brute force attempts. On top of that, even security-concious users don’t use passwords with the entire ASCII range, and many applications will break if you tried (ever use a password with a vertical tab in it?). That puts further limits on the size of the search space.

In short, crypt() should be completely avoided.

The next generation used a cryptographic hash. The advantage of this method is that the original plaintext password can’t be feasibly recovered, even by the people who own the database or write all the code. (If a web site’s password recovery system ever emails you back your original plaintext password, that means they didn’t do it right.)

Doing things this way usually started with MD5:

As weaknesses in MD5 were exposed, things moved to SHA1 and others, but it was the same idea. When the user wants to be authenticated, we hash the provided password with the same salt (the part before the colon above) and check if we get the same value as our stored hash.

One weakness happens with Timing Attacks. With the standard string eq comparison (or equivilent in most other languages), a string is matched by going through character-by-character to see if each one matches in turn. It fails as soon as it hits a non-matching character.

This means that "aaaaab" eq "aaaaac" takes slightly longer to fail than "aaaaab" eq "aac". Mallory can use this slight difference in speed over many different requests to see if he’s getting closer to the right password, somewhat like the Mastermind game. This fail-fast property helps keep programs speedy, but it’s a problem here.

You might think that this difference in speed would be too small to be practical over the Internet, but in fact it was sucesssfully done against OAuth and OpenID.

Mallory’s attempt is complicated by salt and hashing, but making the system completely immune is not difficult, so why not just do it? Here’s how:

We start by checking that the strings are the same length. If we were matching plaintext passwords, this would tell Mallory that he needs a longer or shorter attempt. Note that hashed passwords of the same encoding type will always match in length.

Next, we split the strings into individual characters and iterate over them. With each loop iteration, we XOR the same location in the strings with each other. We then OR that with the current result. If this result ends up staying zero all the way to the end, the strings match.

So far, we know that we should use an irreversible method of encryption, we should use a salt from a cryptographic random source, and we should match the hashed strings in a way that does not fail-fast. Up until a few years ago, that would have protected you against any practical attack out there.

As tends to happen, something new came along. Graphics Processing Units were being used in more and more general computing tasks, and it was found that a GPU could be used to crack hashed passwords. The massive parallel processing speeds offered by GPUs allowed all our then-best schemes to fail.

The mistake we made is that general cryptographic hash algorithms are meant to be fast. Not so fast that they tradeoff security, but all things being equal, a fast algorithm is obviously better than a slow one. Trouble is, if it’s fast to hash a password on your end, it’s equally fast for an attacker to do it on their end.

We are saved here by the fact that a user logging in to a system generally doesn’t mind if it takes an extra second for that one request. But for an attacker making millions of attempts to brute force a password, that extra second adds up. Since we get to choose the algorithm, we should choose one that’s delibrately slow, perhaps one that we can tune to make slower as Moore’s law picks up.

This is where bcrypt comes in (so called because it’s a variation on the Blowfish block cipher). With bcrypt, there is a “cost” parameter that can be tuned upwards as Moore’s Law makes CPUs and GPUs faster. This parameter controls how many loops the algorithm will go through before producing the final output.

The advancements don’t stop with bcrypt, either. GPUs are good at raw processing, but terrible when moving things in and out of memory. So if you use an algorithm that forces you to move things in and out of memory a lot, Mallory can all but give up on cracking passwords with GPUs. This is what scrypt does. The algorithm is still a bit new and hasn’t been completely vetted yet by the cryptographic community, but it may become the new gold standard for storing passwords.

How should we implement all this? One observation from all the above is that for a few decades now, there’s been a war between new attacks and new ways to thwart attacks. We don’t appear to be anywhere near the end of it. That means we should code our apps in a way that can absorb a new algorithm easily. If tommorow morning, bcrypt turned out to be totally broken, you should be able to switch to scrypt in production by early that afternoon at the latest.

When we store the password, we need to store something that shows how it was encrypted. We then have a configuration value somewhere that lists the preferred encryption method for passwords. For algorithms that have cost parameters, like bcrypt and scrypt, we also need to encode that information and configure it alongside the encryption type.

Fortunately, Authen::Passphrase gets very close to doing everything right. Using a string representation based on RFC 2307, it encodes the encryption type, salt, any cost parameters, and encrypted string into a single compact value. The one thing it doesn’t do is match strings in a way that protects against timing attacks.

I also think it could benefit from a plugin system. The current implementation uses lexical hashes within the package to map encryption types to the implementing class, with no way of adding to those hashes outside of the lexical scope (at least, not that I’ve found). New encryption types could be added by CPAN dists more easily if there was a way to add new types dynamically. By breaking out existing classes into separate dists with a plugin system, it could also fix a criticism in one of its CPAN reviews, which is that it’s a maze of twisty dependencies.

Regardless of the above, this is still the best CPAN module I’ve found for storing passwords in Perl.

Let’s say we have a new user signed up with their passphrase in $passphrase. Do this:

We now save the $hashed_passphrase string into our user database.

Later, the user comes back and wants to login. With our stored encrypted password in $db_passphrase, and the incoming passphrase to be checked in $passphrase, we first check if the password matches. If it does, change the encryption if necessary:

That covers the technical end of things. What is sometimes overlooked in these articles is the political game. If you’re working on an existing system with an outdated password scheme, how do you convince your boss that this is important and needs to be fixed?

It’s common for managers to say “Well, that only matters if someone had already broken into our system, so we’ll just protect against that”. Now, you might recall our earlier discussion on security as a chain vs. security as layers. If you’re relying only on boarder firewalls to keep the evil out, then breaking just that firewall gets the attacker everything. If the attacker also has to contend with breaking an encrypted password database, you now have security in layers. Layers are Just Better.

Explaining this to the more clueless managers still won’t be enough, so instead, point out some high-profile breakins. Sony was broke into a while back, and it was found that their password database was in plaintext. Gawker also had a data breach, and their passwords were using the outdated crypt(). These are two well-known tech companies who were utterly embarrassed by their password handling practices.

Perhaps there were a few employees at both those companies who wanted to change things, and perhaps they were stopped by a manager who thought that a data breach would never happen to them.

Don’t let this be a reason for doing nothing, but given the sad state of the industry, I suspect that if you’re currently using salted passwords with SHA1, you’re ahead of far too many companies out there.

We’re almost finished with this series, but there is one more thing I’d like to discuss because there’s so much bad information out there: Quantum Computers and Quantum Encryption. That’ll be in the next post.

Perl Encryption Primer: Hashes

Hashes come in many different classes for different purposes, not all of them for encryption. What we refer to as hash datatypes in Perl uses a hash algorithm internally to map a lookup string to a memory location. This algorithm is faster and shorter than the ones we use for encryption. Other hashes protect data from accidental changes, such as CRC or Adler. These are often used in networking protocols or inside file formats to check that the data has remained intact. They rarely go over 32-bits in length, and won’t withstand an attacker deliberately trying to change the data.

The kind of hashes we’re interested in here are cryptographic strength, which are designed to stop such a deliberate attack. They also have an “avalanche effect”, where changing just one bit of input creates a completely different output. Finally, it has to be difficult to figure out the original data if you only have the hash.

These goals are complicated by something called The Birthday Problem. Let’s say you’re planning a party, and want to know how many people you need to invite to have a 50% chance of someone having the same birthday as you (assuming your friends all have evenly distributed birthdays throughout the year). If you work it all out, you’ll find that the answer is 253 people.

Let’s change the problem slightly. Instead of choosing a person ahead of time (yourself) to find a match, we want there to be a 50% chance of any two people sharing a birthday. In this case, we only need 23 people.

The difference of selecting a datapoint to match ahead of time, versus allowing any two datapoints to match, makes a huge difference. Hashes face the same difference in these two problems:

  1. Having a specific dataset, and wanting to find another document that matches its hash
  2. Finding any two datasets that match its hash

You may wonder if a 256-bit hash is just as hard to brute force as a 256-bit block cipher. Due to the Birthday Problem, we have to double the size; all else being equal, a 512-bit hash is equivalent to a 256-bit block cipher.

Cryptographic hashes have a number of failed attempts over the years. MD4 was published in 1990 as a 128-bit hash. It strongly influenced both MD5 (also 128-bit) and SHA1 (160-bit), which were also hugely popular for a number of years. MD4 has since been completely blown away as a viable hash algorithm. By the late 90s, MD5 had also been exposed as weak, and while it wasn’t as crushing as MD4, attacks were only going to get better. Cryptographers at that time tended to recommend SHA1.

Backing up a little bit, NIST had published SHA-1 as an official US government standard in 1993. Unlike the open contests that produced DES and AES, the algorithm was originally developed internally by the NSA. Although SHA1 is similar to MD5 and MD4, it contained a number of improvements that resisted attacks against its predecessors. While cryptographers are cautious about trusting the NSA, it held up to the best public scrutiny they could throw against it for many years.

That changed in 2005, when new attacks showed a weakness in SHA-1. This sent cryptographers scrambling for an alternative. As a stop-gap measure, the SHA-2 standards started to be recommended (which had already been published by NIST in 2001). SHA-2 is actually a group of algorithms that stretch from 224 to 512-bits.

There’s still some similarity to SHA-1 inside SHA-2. Since the whole family going back to MD4 has had problems, cryptographers were still nervous. So this time, NIST put out a public contest for a new hash function, which would become SHA-3. Unfortunately, these things take time, since the new algorithms have to be validated through several rounds of consideration, with papers published in cryptographic journals that analyze their security. By the end of 2010, five finalists were selected, and the winner was finally announced in 2012, which was Keccak.

In the meantime, cryptographers had still been chipping away at SHA-1 and 2. As the years of the NIST contest went by, nobody was making much progress on generalizing SHA-1 attacks to SHA-2. It seems that the initial paranoia over SHA-2 was unjustified (this time). Before the SHA-3 winner was announced, Bruce Schneier suggested that there be no award.

Regardless, we now have a bunch of new cryptographic hashes around, so if one of them goes down, we can hop to a new one. It’s good to have options.

CPAN has all of these available under the Digest:: namespace. Not all of the modules under there are cryptographic digests–Digest::CRC and Digest::Adler32 are two in particular. These have their place, but not in cryptography. Older algorithms like Digest::MD4 and Digest::MD5 are in there, too. Please, don’t use them for anything new, and strongly consider migrating anything old.

All the SHA-3 contest finalist ciphers–BLAKE, Grøstl, JH, Keccak and Skein–are all in there. Unlike what happened with AES/Rijndael in the Crypt:: namespace, Keccak is now available as Digest::SHA3.

Nearly everything in the Digest:: namespace has a consistent interface. There is a functional interface of [name]_[length]_[encoding]():

And an object oriented interface. In OO, the constructor is called with the hash size. You can then use add() or addfile() to add to the data that’s going to be hashed. These can be called multiple times to keep adding data. Finally, call digest(), hexdigest(), or b64digest() for the hash value in the encoding you want:

Note that as soon as you call for the digest, the internal state is flushed, so if you call it again, you’ll only hash what was added after the last call:

Cryptographic hashes find many uses in cryptography for verifying the integrity of data. One place where you shouldn’t be using them is for storing passwords. We’ll discuss why in the next post.

Perl Encryption Primer: Public Key Encryption

Using encryption to hide secret messages may be as old as written language. For nearly all of that time, these schemes had a fundamental flaw: how do you tell the right people how to decrypt without letting the wrong people know as well?

Military commanders throughout history would have loved a good answer to this question. It’s been less than a century since we found a satisfying answer.

Take two big prime numbers (which are numbers that have exactly two integers that will evenly divide it: 1 and themselves). Multiply them together. Knowing that number, can you figure out how to get the original two primes?

This is the Prime Number Factorization problem. We don’t actually know the answer to that question, but you probably can’t do it in a reasonable amount of time. Oh, sure, I can give you 15 and you’ll quickly give the answer of 5*3. But what about this one:

41202343698665954385553136533257594817981169984432798284545562643387644556
52484261980988704231618418792614202471888694925609317763750334211309823974
85150944909106910269861031862704114880866970564902903653658867433731720813
104105190864254793282601391257624033946373269391

There used to be a cash prize of $75,000 offered by RSA Labratories for figuring that one out.

Thing is, nobody has mathematically proven that there isn’t a quick way of factoring primes. They’re part of a set of problems called “NP”. In these problems, I can give you a possible solution and you can quickly verify if it’s correct. If I offered you two prime numbers and said that they could be multiplied together to make the big composite number above, you would be able to do the multiplication yourself and check my claim. Problem is, it’s hard to get that potential answer without coming up with a bunch of guesses and trying each one–in other words, brute force.

The set of “P” problems are the ones where you can generate the answer in polynomial time (which is about as slow as you can get before the computational complexity gets to be too much). The set of “NP” problems are the ones where you can take a potential answer and check if it’s right in polynomial time. The big question of complexity theory is if P and NP are the same set.

There are many other such problems, some of which would be useful to solve. A salesman trying to find the fastest route between a bunch of different houses is an NP problem. Maximizing the storage space of a knapsack holding a bunch of items of different weights and values, up to a certain limit, is also in NP.

One of the interesting things about NP is that if you prove any one of those problems can be solved in polynomial time, you’ll be able to generalize that approach to solve them all. At the same time, there doesn’t seem to be any reason why P and NP should be separate. But they probably are. The reason is that we’ve been trying really, really hard on some of these problems for a long time, and nobody has managed to unify the two. In the last 40 years or so, there’s been the extra incentive of breaking tons of encryption algorithms, and nobody has cracked it in that time, either. If math worked on the a posteriori evidence-based system of science rather than a priori logical proofs, then P!=NP would have been declared true years ago. (I can’t do this subject justice beyond this tl;dr version, so read the link above.)

This is not so great news for the salesmen and mountaineers of the world, but it’s great news for cryptographers. If indeed P!=NP, then the RSA encryption algorithm is secure.

Now, remember that RSA has to deal specifically with prime numbers. Since we can’t use just any number like we can with block ciphers, we need a much longer key length. Keys of 2048-bits are common. 4096 and 8192-bit keys are not unheard of, but there is some debate about their necessity. RSA Labs tends to argue that 2048 is good enough for most uses. This is because as the keyspace rises, memory usage tends rise faster than Moore’s Law.

RSA isn’t the only form of public key crypto. DSA, Diffie-Hellman, and Elliptic Curves are also examples. You may have heard that Quantum Computers will one day destroy RSA’s security, and then the NSA will be able to steal all our credit card numbers so they can order a huge arsenal of Nerf guns off Amazon. We’ll talk about Quantum Computers in a future post, but suffice it to say for now, we have some options for replacing RSA and other public key crypto if it comes to it.

When a key is generated, you’ll get a number n, which is the composite of the two original primes. This forms part of both the public and private key. You also get a number e, which is in the public part of the key. Finally, number d is only in the private key. Each of these has a mathematical relation to each other that all comes together during key generation.

Let’s say Alice and Bob have each others’ public keys, and Alice would like to send a message M to Bob. Alice turns M into a straight integer m by some means. Alice then computes c = me mod n. Except this takes an awfully long time and smoke starts to come out of her computer.

The reason for this has nothing to do with the P=NP nonsense from above, and everything to do with the fact that nobody has a computer with a word size that can handle a 2048-bit number. You need a bigint library to handle a number like that, and bigint libraries are slow.

After airing out her house and buying a new computer, Alice tries again, only this time she does something clever. Instead of trying to encrypt a whole message with RSA, she’ll generate a fresh block cipher key, and use that to encrypt the message. Since the block cipher key isn’t any more than 256-bits long, encrypting just that with RSA is no big deal. She does that, appends it to the start of the block-cipher encrypted message, and sends it along to Bob.

(See why block ciphers are so important, despite the advent of public key crypto?)

One thing to note here is that the block cipher is now part of the security chain. If Mallory wants to break the message, he can choose either RSA or the block cipher, depending on which one he thinks will be easier. This ultimately means that Alice has to pick a good block cipher. And once again, she has to make sure those keys come from a good random number generator.

Bob gets the message and decrypts the block cipher key by doing cd mod m. He now has the block cipher key and, knowing which block cipher Alice used, can decrypt the whole message.

Bob now wants to send a message of his own to Alice, but wants to make sure Alice can trust that it’s him. After all, anybody with Alice’s public key could encrypt a message and send it to her. Bob also thought he saw Mallory sneaking around the email server yesterday, and something about that guy seems off.

Fortunately, RSA has a solution here, too. In addition to encryption, RSA can sign a message. Using his own private key, he uses the same formula used for encryption with the public key. Anybody with the public key would be able to decrypt this message. A valid decryption means that the message must have come from Bob, since he’s the only one who could have encrypted the message this way.

Bob does this. This causes his CPU to turn into smoke. After airing out his house and buying a new computer, he takes a cryptographic hash of the message, signs that, and sends it to Alice. (The cryptographic hash would probably be somewhere between 256 and 512 bits long. We’ll talk about them more in the next post.)

Now Alice can verify that the message did come from Bob. Or rather, she verifies that it was encrypted with the private key that matches her public key for Bob. Does she know that this key actually came from Bob?

If she got it from Bob in person, then that’s great. If she got it over the phone, it’s probably OK, but she can’t guarantee it (can Mallory impersonate voices?). If she got it over email a long time ago and has sent many encrypted messages back and forth with Bob since then, it’s probably OK, too, but maybe not.

This is the problem of trust. There have been three different widespread solutions to this problem over the years:

  • Alice knows somebody who knows somebody who knows Bob (the PGP solution)
  • Alice and Bob both trust a central authority to take care of keys (the SSL solution)
  • The first time they exchanged keys probably went OK (the SSH-in-practice solution)

In the early 90s, PGP came out with a web-of-trust system. It’s also used in GnuPG, which tends to be more common these days. It works like this: Alice meets Carol and exchanges key information. Carol seems pretty trustworthy, so Alice sets Carol’s key as being reliable in the key store. Carol also met with Bob and exchanged keys. Since Alice trusts Carol, Alice can also trust Bob. Of course, you don’t want to go through too many steps of trust, but with the Small World working in our favor, this can work out well as long as a lot of people are signing each others’ keys.

Trouble is, only us nerds want to sign each others’ keys. Seriously, there have been nerd parties just for this.

The next stab at the problem was SSL. Here, there’s a central party (called a “Certificate Authority” in SSL parlance) who everybody trusts. Alice and Bob and everybody else gives the CA their public key. The CA does some checks to see that Alice and Bob and everybody else are who they say they are, and then certifies that the key indeed belongs to this person. Your browser has a bunch of trusted CAs built in when you got it, so we avoid the nerd-party problem.

Trouble is, CAs do dumb things sometimes and don’t check a person’s identity very well. Cert authorities were being paid a lot of money to do a level of verification that could be done by a small shell script. When people realized this, the CAs started charging more money for “extended validation” certificates. In other words, to do the job they were supposed to be doing all along.

Those are the two most widespread solutions, but a third is done in practice by nearly everyone who uses ssh on a daily basis. When you first login to a server over ssh, you see a message like this:

Have you ever called up the sysadmin and asked if that fingerprint is correct? Admit it: you just typed ‘yes’ and got on with work. Dentists are paid to scold you when you don’t floss. Cryptographers are paid to scold you when you don’t check your SSH fingerprints. On the other hand, we’ve all been doing this for years and things seem to get along OK.

I won’t argue that this is at all good practice. I secretly wonder sometimes if the web-of-trust system could be revived using social networking and smartphones, where “friending” someone meant scanning the QR code containing their public key (answer: probably not; it’d just be us nerds using our highly secure social networking system to organize D&D get-togethers). But the “trust on first connection” system seems to work out.

Wasn’t this supposed to be a Perl encryption primer? Let’s do some Perl.

The GnuPG Perl module is directly based on GnuPG, which itself is an implementation of OpenPGP as standardized in RFC4880. The details of key generation, encryption, and signatures are done for you. Since it all works with the GnuPG executable, you can use the command line or graphic tools to manage your keys and web of trust.

We create a key with gen_key():

The public key itself will be encrypted with a passphrase. Any other tools you use with this key will ask for the same passphrase before they can do anything. Be sure to use something typeable that you can remember.

We can now save those public and private keys back to the GnuPG database:

Without the secret parameter, only public keys will be exported. Later on, we can import keys back with import_keys():

Now that we have our keys, we can encrypt a message in a file:

We assume here that a key matching the email ‘bob@example.com’ will be loaded. Despite the name, armor doesn’t provide any additional security; instead, it encodes the encrypted message in a variation of Base64. Pretty handy if you’re going to send the message over email or another system that tends to prefer text over binary. The sign parameter adds a cryptographic signature to the message in addition to encryption. Since we’re signing the message with our default key in addition to encrypting, we’ll need to set passphrase to the same value we used when we generated the key.

You can also do the signature alone with sign():

After this, file.txt.asc will be ready to send to Bob. Bob can now verify Alice’s signature with:

This method will croak if the signature is not valid.

When Bob gets an encrypted message from Alice, he can do:

Once again, we need to set passphrase to the value we used to generate the key.

There are alternatives to the GnuPG module in Perl, such as Crypt::OpenPGP, which follows a broadly similar interface. OpenSSL also implements things in its own way, which you can use with Crypt::OpenSSL::RSA. In fact, there’s a whole suite of modules under the Crypt::OpenSSL namespace.

Cryptography isn’t just about keeping secrets, though. There is also the matter of verifying the message. We’ll be covering that in the next post on Hashes.

Perl Encryption Primer: One Time Pads Are Too Awesome To Use

Part of my reason for writing this series is not just to provide a solid foundation in cryptography, but also to point out common bad advice. I ran into one such example on /r/bestof some months ago, and it’s stuck in my mind since then.

First, what is a One Time Pad? Start with a bunch of random numbers, which will be your key. Now use each byte of the key to modify each byte of the plaintext. There are a few different ways we could make that modification. Since we’re using a computer, the XOR operation makes a good choice.

What’s so special about XOR? It’s because it’s a reversible operation. Consider:

When we XOR a piece of data with a number, and then XOR the output with that same data, we get the original number. How can we use this for encryption? We’ll use a random number (which will form our key) and XOR that with the plaintext:

Let’s say Alice and Bob share a key, which is 172. Alice sends Bob the ciphertext 238. Bob knows to XOR this ciphertext with 172, which gets back the UTF-8 character for “B”. So congradulations to Alice and Bob–they’ve successfully sent the letter B to each other, and nobody else will ever know.

If Alice and Bob want to send a longer message while maintaining security, they’ll need a longer key. We’ll pretend that Alice and Bob only want to send plain ASCII messages, which means we only need to generate a key of 8 bits per character. They’ll want to send a 25 character message, so we ask Crypt::Random for 25 bytes of random data:

That big long number is now our key. We’ll now use the Crypt::OTP module to encrypt our plaintext message, and encoding the output in base64 so we don’t have issues with unprintable characters. We’re also dealing with a really big number, so we’ll need the help of Perl’s bigint library.

(The last ‘1’ parameter to OTP() tells Crypt::OTP to use the string as-is, rather than treating it as a filename.)

To decrypt, Bob undoes the base64 encoding and passes Crypt::OTP the same key:

Notice that unlike most every other algorithm you’ll find in the Crypt namespace, OTP does not have separate encrypt/decrypt subroutines. Since Crypt::OTP uses the XOR operation as we showed above, encryption and decryption use the same subroutine. It’s not strictly necessary to implement OTP this way–it could also be done with addition and subtraction–it’s just the common way to do it with computers.

Alice and Bob have now shared a very important secret about pies, which they can guarantee will never, ever be read by anyone else, provided they’ve taken all the right precautions. It turns out that those precautions are a daunting challenge, which we’ll get to in a moment. For now, let’s see why we can talk so absolutely about the security of OTP (at least in theory).

We’ll bring in another character that’s commonly used in these crypto stories, Mallory. Mallory is a bad guy trying to read or otherwise screw up messages sent by Alice and Bob. Mallory knows that the message is 25 bytes long, so he generates a bunch of 25 byte keys and what they would decrypt. He sees among the messages:

  • “The snipers are not ready”
  • “Imtrappedincinncinatiohio”
  • “Pecans taste horribleXXXX”

Ignoring any real-world context, each of these messages is equally likely. How can Mallory know which is correct? He can’t. He can brute-force a list of all 25 character ASCII messages, but will have no idea which is the right one. The right message will be in there, somewhere, but he has no reason to say it’s the right one.

As the last example shows, Alice and Bob could use padding to conceal the length of the right message, so Mallory only knows that the message is no more than 25 characters long.

Now that I’ve hyped up OTP as the ultimate encryption method, I want you to forget all about it for any purpose besides winning arguments on the Internet.

The problem comes in the provision we made earlier, that Alice and Bob have taken all the right precautions. It turns out that OTP is almost impossible to use in the real-world, for all sorts of technical and human issues. For these reasons, it is almost never used in practice. The theoretical advantages are a tempting siren song that we must ignore.

First, how does Alice transfer the initial key to Bob? If Alice can deliver it in person, that’s great, but if Alice and Bob and meet regularly and be sure of the security of the data being passed, why not pass the whole message? If Alice sends things by courier instead, Mallory could bribe the courier and copy the key.

If Alice encrypts the key with another cipher, we now run into the problem mentioned in the post on random numbers, which is building security in a chain. OTP is Perfectly Secure, and any other cipher will not be able to live up to that perfection. The other cipher is now part of your security chain; the key is no more secure than the cipher in question. So why not encrypt the message with that cipher instead?

(Key transfer is also a problem for block ciphers, but since their keys are fixed-length, they’re much easier to manage through other means. We’ll talk about transferring them around when we get to public key crypto.)

Let’s say that Alice and Bob have worked out all the issues with transferring the key. Things are going well for a while, but Alice notices that they’re almost to the end of the key. What to do?

The naive thing to do would be to reuse the key from the beginning. This is a mistake which makes it trivial for Mallory to break the key. Let’s say Alice uses the key 0xABCD with 0x1234, and later uses the same key for 0x5678. The results are:

Mallory isn’t quite sure what the first message had, but he’s pretty sure he knows what the second is. Knowing this, Mallory can XOR the second ciphertext with what he knows to be the plaintext, resulting in:

Which is the original key, which means Mallory can decrypt the first message, too! This is called a “known-plaintext” attack.

How would Mallory figure out the plaintext? There is invariably some underlying structure to the data being encrypted. English language text will have “the” appear quite often, among other things. A transaction to your bank might have the account information in the same location of a packet. Or Mallory could bribe a teller to get Alice’s bank account number.

It’s dangerous to assume that Mallory would have zero knowledge about what you’re sending, which is why cryptographers generally avoid algorithms with known-plaintext attacks. Since there are algorithms out there that don’t have this problem, why not use one of them?

So Alice and Bob have worked out the problems of transferring the key around, and they are hyper-paranoid about concealing anything that might lead to revealing the internal structure of the message. They’ve still forgotten something, which is how to generate the key in the first place.

Remember from the earlier discussion on random numbers that getting true randomness on computers is very hard. Getting really long strings of high-quality random numbers is even harder.

In Neal Stephenson’s book Cryptonomicon, a woman in WWII Britain is charged with generating random characters for use in OTP encryption. She is given one of those lottery machines with all the balls being blown around inside. Each ball has a letter on it, and she’s supposed to reach in, type the letter out on the ball, then stick it back in and draw another.

The problem is that she speaks English, and an English speaker will tend towards preference for E’s and T’s, and not very many X’s and Z’s. So she often threw the X’s and Z’s back in when she thought she was seeing them too often, and maybe added an E or T when she thought there weren’t enough. This biased the random number generator, allowing a smart German cryptographer to break the whole British OTP system. (It should be noted that this is a fictional story based around actual events and cryptography.)

All cryptosystems need good random numbers, but most of them don’t need very many. AES will do fine with only 128 or 256 bits, and it’s safe(-ish) to reuse the same key. An 8,000 bit document encrypted OTP requires an 8,000 bit key, and you can never use those random bits again.

What it all comes down to is that OTPs should almost never be used. There is one notable exception, which we’ll cover when we get to quantum encryption. We also have good reason to think that 256-bit block ciphers are more than adequate no matter what improvements in conventional computing come down the pipeline (or 512-bits against quantum computers). We’ll see why in the next post on block ciphers.

Perl Encryption Primer: The Importance of Randomness

I’ll be doing a presentation for MadMongers in April on encryption in Perl, and I’m going to try something a little different. This series of blog entries will lay out a written primer on encryption in Perl, which will then form a condensed outline for the presentation. I feel the final presentation should have high-quality information, so hopefully anything I get wrong can be pointed out and corrected before then.

We’ll start with the most fundamental building block of encryption, which is random numbers. Now, a naive new programmer might jump right in and start calling rand():

The int truncates the decimals; it would otherwise return a float. The parameter to rand() tells it the maximum number, which is 1 by default. The code above will return a number between 0 and 10,000.

Here, we already hit two different hidden snags:

  1. Random numbers are surprisingly difficult to do right
  2. Computers are deterministic machines. You can’t get much randomness out of determinism.

The rand() function starts with a seed. You can put in your own seed with srand(), or you can start out with the seed Perl gives you by default. The means Perl uses to get that initial seed is actually quite complicated; look at util.c and search for the function “Perl_seed” for the gory details.

Notably, if we put in our own seed, call rand() a few times, and then do it again, we’ll get the same output:

Same pattern each time! This means that an attacker doesn’t need to know the output of rand(). They just need to know what srand() input you started with. Let’s say you give srand() a 32-bit input. You then use that generate a 128-bit key for a cipher. This means that your cipher doesn’t have 128-bits of security; the attacker only needs to brute force the 32-bits that you put into srand(), which is a far easier task.

This brings us to an important consideration in security, which is building things in chains versus building things in layers. A chain is only as secure as its weakest link. In the above, the 128-bit block cipher only had 32-bits of security, because srand() was part of its chain.

Building in layers is more like a castle. Breaching the outer wall doesn’t mean you’ve breached the inner walls. Breaching the inner walls still leaves you the Keep to deal with. The Keep may also be built of narrow, maze-like hallways with the defenders attacking from above. This is defense-in-depth. We won’t be explicitly covering building in layers in this post, but it’s good to keep this in mind when building security systems.

For this and other reasons, rand() is not the right choice for a cryptographic-strength random number generator.

There are random number generators that can take a longer seed, but this leads to another question: where did you get the seed from? If it’s a timestamp, the attacker may be able to make a rough guess of the time period when you first generated that key. That could easily end up with even less than 232 possibilities (as in the case of 32-bits of randomness). Whatever else you use, can you be confident that an attacker can’t narrow down the input seed?

We end up needing to be really careful about where we get our random numbers. Since computers are such deterministic machines, we need a source that is somehow external to the computer.

Preferably, all computers would come with a special piece of hardware. Intel and AMD both used to put one in their chipsets (i8xx and 76x-based motherboards, respectively), but these fell into disuse. The VIA PadLock Security Engine also has a hardware RNG on their CPUs. Intel has also returned the hardware RNGs with RdRand on IA-64 CPUs.

If you don’t have a specific CPU, then there are also ways to add hardware for generating RNGs. LavaRnd was a project that used a web cam in a dark environment to pick up on cosmic background radiation, which can be used for randomness. Sadly, the project hasn’t been updated in quite some time. There are a number of other hardware RNGs to purchase, ranging from cheap to very expensive. I would urge careful research before buying any of them.

If we can’t buy hardware, then there’s an option to take randomness from the world around the computer. Consider that there is a slight variation between the timing of your keystrokes and mouse movements. By having the OS kernel listen in on this data, a random number generator can use this as input. This and a few other things is what the Linux /dev/random driver does. Similar techniques are used on Windows, Mac, and most everything else.

One problem with this approach is headless servers. Since they rarely have keyboard or mouse in use, the few remaining sources might not be enough. /dev/random will block until it gets more random numbers. /dev/urandom will continue onward using lower-quality sources, which isn’t what we want, either. This is where proper hardware random number generators come into play.

No matter what OS you use, Crypt::Random is the Perl module to use. This will use /dev/random on systems that have it, and the userspace Entropy Gathering Daemon on systems that don’t. It’s easy to use:

The Size parameter is the number of random bits to generate, and Strength set to 1 says that we won’t fallback to less-secure alternative.

Next post will be on One Time Pads, which is an encryption algorithm so good that we can never use it.