YAPC::NA 2014

The UAV::Pilot talk went well. It’s all up on YouTube already.

Hotel wifi is predictably shitty. Half the bandwidth is being used to stream everything to YouTube, and the rest of us are stuck with the leftovers. Hotels just don’t have networking staff who know what they’re doing on site.

I also helped out Steven Lembark with his “Getting Testy with Perl” talk. We spent the evening before hacking up a test script for the AR.Drone to integrate with his talk. Having a UAV takeoff and flip around sure is more interesting than your usual “check that the row went in the database” demo test.

One thing I found while working on that is that UAV::Pilot has a terrible interface for simple scripting. The ‘uav’ shell is fine for typing stuff out yourself, and the object interface is fine for big complicated things, but there’s a space in between that isn’t being served.

At the Hardware Hackathon, Robert Blackwell brought an iRobot Create. I quickly hacked together a UAV::Pilot interface for it using Robotics::IRobot.

Lastly, some maniac did this:

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.

Underappreciated Perl: Passing File Descriptors

Despite my previous benchmarks, copying the video data from the AR.Drone to another process via a pipe caused a small but perceptible delay in the output. Then I remembered an old Unix trick that we can use in Perl: passing file descriptors around as integers.

On Unix, filehandles are just integers. STDIN, STDOUT, and STDERR are respectively numbered 0, 1, and 2. Each filehandle you open after that is generally numbered sequentially. You may also remember that networking sockets are just filehandles, which is what makes this trick work for UAV::Pilot.

In Perl, filehandles can have a more complicated structure, especially with the PerlIO layer introduced in perl 5.8. Some of these are not true filehandles in the Unix sense. For instance, when you open against a scalar reference:

Regardless, actual files and networking sockets still have an underlying Unix file descriptor. We can get the integer with fileno():

We can then fork() off and exec() a new program, passing the file descriptor as an option. (Remember, system(), backticks, and open( ..., '|-' ) and such are just fancy ways of doing fork() and exec()). But there’s a problem, which is that Perl sets a close-on-exec flag on all filehandles by default.

This means we have to unset the flag before doing anything else:

(This part is not portable to Strawberry Perl on Windows. The error says that F_GETFD is not configured for this vender. I think the actual technique of passing file descriptor numbers is otherwise portable. Windows is more Unixy than it likes to admit.)

(Edit: This is all possible under Windows, but you need to use some native Win32 APIs to get it done. See this Perlmonks SoPW for details.)

Now we can fork() and exec(). We also set $SIG{CHLD} = 'IGNORE'; so we don’t have to manage zombie children.

Inside the target program, you have to change the integer back into Perl’s complex filehandle, which you can do with a funny looking open() call:

And now you can read from $in like just any other filehandle.

After doing this in UAV::Pilot, that small but perceptible delay went away.

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.