Elliott C. Back: In Aere Aedificare

Kottke just posted the infamous rope-burning interview problem, which is actually quite easy:

You are given two ropes and a lighter. This is the only equipment you can use. You are told that each of the two ropes has the following property: if you light one end of the rope, it will take exactly one hour to burn all the way to the other end. But it doesn’t have to burn at a uniform rate. In other words, half the rope may burn in the first five minutes, and then the other half would take 55 minutes. The rate at which the two ropes burn is not necessarily the same, so the second rope will also take an hour to burn from one end to the other, but may do it at some varying rate, which is not necessarily the same as the one for the first rope. Now you are asked to measure a period of 45 minutes. How will you do it?

The solution is the following:

• Light rope #1 at one end
• Light rope #2 at both ends
• When rope #2’s ends meet, light rope #1 at the other end. 30 minutes have been measured so far, leaving 30 minutes left on rope #1.
• When rope #1’s ends meet, fifteen minutes have been measured, for a total of 45 minutes.

A new attack on RSA called Simple Branch Prediction Analysis promises to reveal “almost all of the secret key bits” by executing a parallel spy process that only needs to watch a single execution of the RSA private key. Some more technical details show it to be a sophisticated, dangerous attack:

Namely, in the context of simple side-channel attacks, it is widely believed that equally balancing the operations after branches is a secure countermeasure against such simple attacks. Unfortunately, this is not true, as even such “balanced branch” implementations can be completely broken by our SBPA attacks. Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor.

If that weren’t bad enough, a rootkit now can be persisted in your PCI device. A paper called Implementing and Detecting a PCI Rootkit details how PCI cards execute bios code which can be flashed from the windows software if the user is running as an administrator. Combined with a remote exploit, this could lead to a remote rootkit injection. Also, given that PCI BIOS software is not verified in any way, the rootkit would difficult to detect.

For the cheapest airline fares and hot travel deals, try Farecast, now in private beta.

Imagine, for a moment, that you wanted to travel at the end of July from Seattle to PHX for a weeklong conference. You’d zip over to Farecast, and it would be able to tell you which airline were at their optimal prices at the time, and whether or not the price was likely to significantly change over the next few days. Here’s an example:

As you can see, it issues a recomendation for you to buy, followed by the degree of accuracy of the prediction, and a very pretty looking chart. How do they do it? On their technology page, they say:

We use data-mining algorithms to search for patterns, in the accumulated airfare data, which are associated with significant price changes. These patterns are represented and stored in models, and the models are then rigorously trained. Once created and trained, we use these models to predict the future. Then, new, current airfares can be scored by the model to answer the question, “Is the price going up or down in the future?”

In other words, they probably are training neural networks per route to learn seasonal patterns to pricing data, and then to keep them accurate, using feedback between their simulated passengers and what the next day actually becomes. Very cool, in my opinion. The only thing stopping me from using Farecast for buying airplane tickets now is that it only covers routes from Seattle, WA or Boston, MA. Since I live in neither location, it’s just a pretty toy.

I tried the Speakeasy bandwidth test utility and got some amazing results:

This is on a 1.2MB/s LAN connection over 54Mb/s wifi, which either makes the Cornell internet connection prescient (it can guess bits?) or Speakeasy’s tool completely wrong.

Update

Don’t post when you’re sleepy! 5600kbs = .7 MB/s, so this is within the range of what should be happening. We were getting weird results that morning in the 300kbs range, as well, which make me think it was on some kind of different scale, as that would have been really really slow…

CDFreaks makes the ridiculous claim that DRM shortens an mp3 player’s life by 25%, which I find silly. To that end, I am going to perform the following three tests on my new Creative Vision M mp3 player to give a factual refutation of this claim:

• Playing 1 ~4m mp3 file on loop until the device dies
• Playing 1 ~4m wma file on loop until the device dies
• Playing 1 ~4m wma DRM protected file on loop until the device dies

These tests will take a few days to complete. Here are the results:

• 11 hours 37 minutes (02/18/2006 2:11 PM to 1:48 AM)
• 10 hours 08 minutes (02/19/2006 2:38 PM to 12:46 AM)
• 8 hours 55 minutes (02/21/2006 8:50 AM to 5:45 PM)

Going from MP3 to WMA at the same bitrate costs you about 10% battery life. Going from unrestricted WMA to WMA protected by DRM costs another 10% battery life, or 2.7 hours compared to MP3–24% of the maximum possible.

However, I think the following chart, which compares the percent change between formats, to be more telling:

There are two disparate effects here:

1. WMA v.s. MP3
2. DRM v.s. Unrestricted Media

The results of this test show that

1. WMA uses battery 12% faster than MP3
2. DRM uses battery 12% faster than Unrestricted Media

The glaring error that the media made was to unfairly associate both factors (Format and DRM) with the issue of Digital Rights Management. When you look at the variables independently, it’s only half as bad as reported.

Related Stories:

• Engadget
• I-hacked
• Digg
• BoingBoing
• Inside Stretch
• /.