Infinite second

Turning on TLS is where you start, not where you finish

2008-08-23T15:19:00.000-07:00

Google making SSL changes, other sites quiet

How many sites other than Google (mis)use TLS in this way? Be afraid.

ratproxy unleashed

2008-07-01T17:29:00.000-07:00

Google just released their internal tool for passive web security assessment. While it has the unfortunate name ratproxy, it looks, frankly, badass. If you care about the security of your site (and even if you don't, your users probably do), you should consider making ratproxy a regular part of your secure development process.

What not to do, part 2

2008-06-15T20:30:00.000-07:00

As expected, there are many TLS sites using keys generated using the flawed, Ubuntu version of OpenSSL. Netcraft has the latest.

Selecting cryptographic key sizes

2008-06-12T11:33:00.000-07:00

Selecting cryptographic key sizes is a valuable reference for estimating the security margin for algorithms and key sizes and is deliciously applicable to TLS configuration choices.

A few tasty tidbits:

Does anyone seriously believe that published attacks represent the state of the art? It may safely be assumed that unpublished work is many years ahead of what the public at large gets to see: a public announcement that a system is broken provides at best a rather trivial upper bound – and a very simple-minded one, in our opinion – for the date that the system became vulnerable.

According to Table 1, 512-bit RSA keys should not have been used beyond 1986.

According to Table 1 usage of 768-bit RSA keys can no longer be recommended. Even in the cost-equivalent model 768-bit RSA keys will soon no longer offer security comparable to the security of the DES in 1982.

SNI is goodness

2008-06-12T10:16:00.000-07:00

SSL-enabled Name-based Apache Virtual Hosts with mod_gnutls.

I encourage you to try it out. I have no experience with mod_gnutls, but gnutls is top notch and 80% less code than mod_ssl is a good thing.

tls report goes geek hipster big time

2008-06-10T19:25:00.000-07:00

O'Reilly Radar post about us.

And this guy, too.

Vertebra == genius

2008-06-10T19:22:00.000-07:00

Vertebra is absolute genius. If the implementation is even half as spectacular as the concept, it will take over the planet and we will all worship it like a big golden calf written in Erlang and Ruby.

SSLv2 still considered harmful

2008-06-10T18:02:00.000-07:00

Some argue that, although it is deeply flawed, SSLv2 is better than nothing and some very old clients don't support anything better. This is true in the same way that a beautiful lie is better than an ugly truth. I'm an ugly truth kind of guy. What about you?

From 2005: SSL V2 SNAFU

No doubt, everyone is patched up by now and no other such vulnerabilities are present, waiting to be discovered. No doubt.

The excuses

2008-06-09T21:00:00.000-07:00

I got some feedback from someone responsible for security at a major site currently tracked in the TLS Report. They took issue with my methodology and gave what I can only describe as excuses for how they were choosing to configure their servers. His argument went something like this:

We support (several) export ciphers because we want to make sure everyone on every browser ever released can access our service. If users want to negotiate a strong cipher, they can! Also, we use a mediocre default cipher because stronger ciphers would be too slow.

Let's break this down:

1) Support for export ciphers

It's 2008. There is no good reason anymore to support export ciphers. If you insist on supporting export ciphers, at least alert users when such a weak cipher is negotiated. Heck, give them suggestions for upgrading to a better browser. Users see the little lock and they assume everything is locked down. They don't know the difference between DHE-RSA-AES256-SHA and EXP-RC2-CBC-MD5. You do.

2) Stronger ciphers are there if people want them

Browser vendors recognize they must support a huge variety of ciphers to deal with the huge variety of ciphers supported by servers. By default, they are almost all turned on. The result is obvious: regardless of the stronger ciphers that could be negotiated, the server default is what will be used. In order to get those stronger ciphers, users would either have to disable all the weaker ones, locking them out of numerous sites, or switch to a browser like Opera, that plays tricks to figure out the strongest available cipher on a server.

The power for this is almost entirely in the hands of the server operators. You know this. Use your power for niceness.

3) Stronger ciphers would be too slow

This is mostly true, although not always relevant. For pages that are not huge, the total processing is often dominated by the session setup. Public key crypto is extremely expensive. If you are spending most of your time on it, then moving to a stronger cipher may have no interesting impact on total performance. See this and this for some really interesting analysis.

The most important aspect of this response, however, is that it is free of any factual basis. Do the analysis, and make decisions based on the facts. If you collect statistics on the set of ciphers your customers' browsers are offering, and you see lots of folks who require export ciphers, figure out how to support them. If you don't see that sort of traffic, or not enough of it to keep supporting it, turn the export ciphers off. If you do performance analysis based on request traces to see the impact of, say, switching from RC4-SHA to AES128-SHA as your default cipher, and discover it would be hideously expensive to change, then don't. What you should not do is assert, without analysis, that these things are true (or false).

No excuses, y'all. As operators of TLS servers, you are the experts on which your users depend. Don't let them down.

What not to do

2008-05-15T20:14:00.000-07:00

I was discussing the following with a good friend of mine earlier and we are both confused about why it is not major news, getting flogged everywhere such geekery is common. This is one of the more egregious failures ever perpetrated.

Debian (and Ubuntu) OpenSSL stupidity.

This is why it is so important that you can't simply hack crypto together and cross your fingers. Some bright spark decided to comment out the source of entropy for the random number generator, so everything works fine, but the keys are no longer random and no longer from an enormous pool. Commented out not for a carefully considered engineering reason, but simply because it was generating errors from a code analysis tool. This is badness.

I won't get into a rant about how a proper development process could let this through and instead will offer these two tidbits. The first is a thread from 2003 regarding errors from Valgrind on this very line of code and exactly why they should be ignored. The second is the entry from the OpenSSL FAQ (added in September 2007) reiterating the point. This was a known issue with a known solution (ignore it).

I cannot overstate this: leave crypto to the pros or become a pro yourself (I'm merely an interested amateur).

The thread.
The FAQ.

TLS Report beta

2008-05-15T18:53:00.000-07:00

The TLS Report is stable (give or take). I'll be migrating it to AWS soon, even though their report is not great. But, hey, could be worse!

TLS Report alpha

2008-04-30T20:03:00.000-07:00

The TLS Report is in alpha here. No promises on stability.

The TLS report is on the way!

2008-04-15T09:41:00.001-07:00

UPDATE: The production site can be found here.

My reporting tools are taking over! Well, taking over my free time. The TLS Report service will be online in a few weeks. In the mean time, here are some static pages showing the draft format. I switched to a very recent, non-OSX version of OpenSSL, as well, so there are some new ciphers shown (the coolest additions being the EC ciphers at Microsoft). The other, pleasant surprise of the past few days is the sudden, significant improvement of the configuration for www.paypal.com.

Amazon
Facebook
Microsoft
Thawte

Hard data!

2008-04-04T23:30:00.000-07:00

Just found this paper: Cryptographic Strength of SSL/TLS Servers: Current and Recent Practices. Looks like I'm not the first hound down this trail! Tons of great data in there.

Devilish details (more on my TLS config obsession)

2008-04-04T23:05:00.001-07:00

I updated the TLS tool to check the complete order of preference for all ciphers supported by a given server. While the good ones stayed darned good, the bad ones got even worse. Here are a couple of examples. Notice that, in both cases, the weakest, non-export ciphers are at the top, and there doesn't seem to be any sense to the ordering of the rest of the ciphers. In the case of Facebook, they even prefer several export-grade ciphers over those using ephemeral keying!

Facebook

test run at Sat Apr 05 11:32:09 -0700 2008

grade for www.facebook.com:443 is low

supported protocols for www.facebook.com:
-> SSLv3, TLSv1

default cipher for www.facebook.com:
-> RC4-MD5 TLSv1/SSLv3

server certificate strength is low
-> excessive certificate lifetime (Fri Sep 28 23:53:12 UTC 2007 to Tue Sep 28 23:53:12 UTC 2010)
-> MD5, RSAEncryption, 1024 bits
-> expires Tue Sep 28 23:53:12 UTC 2010

valid ciphers for www.facebook.com, in order of preference:
-> RC4-MD5 TLSv1/SSLv3
-> RC4-SHA TLSv1/SSLv3
-> AES128-SHA TLSv1/SSLv3
-> AES256-SHA TLSv1/SSLv3
-> DES-CBC3-SHA TLSv1/SSLv3
-> DES-CBC-SHA TLSv1/SSLv3
-> EXP-RC4-MD5 TLSv1/SSLv3
-> EXP-DES-CBC-SHA TLSv1/SSLv3
-> DHE-RSA-AES256-SHA TLSv1/SSLv3
-> EDH-RSA-DES-CBC3-SHA TLSv1/SSLv3
-> DHE-RSA-AES128-SHA TLSv1/SSLv3
-> EDH-RSA-DES-CBC-SHA TLSv1/SSLv3
-> EXP-EDH-RSA-DES-CBC-SHA TLSv1/SSLv3
-> EXP-RC2-CBC-MD5 TLSv1/SSLv3

Amazon

test run at Sat Apr 05 11:30:07 -0700 2008

grade for www.amazon.com:443 is low

supported protocols for www.amazon.com:
-> SSLv2, SSLv3, TLSv1

default cipher for www.amazon.com:
-> RC4-MD5 TLSv1/SSLv3

server certificate strength is low
-> SHA1, RSAEncryption, 1024 bits
-> expires Wed Sep 17 23:59:59 UTC 2008

valid ciphers for www.amazon.com, in order of preference:
-> RC4-MD5 TLSv1/SSLv3
-> RC4-MD5 SSLv2
-> RC4-SHA TLSv1/SSLv3
-> DES-CBC3-SHA TLSv1/SSLv3
-> AES256-SHA TLSv1/SSLv3
-> AES128-SHA TLSv1/SSLv3
-> DES-CBC-SHA TLSv1/SSLv3
-> EXP-RC4-MD5 TLSv1/SSLv3
-> EXP-RC4-MD5 SSLv2
-> EXP-DES-CBC-SHA TLSv1/SSLv3
-> EXP-RC2-CBC-MD5 TLSv1/SSLv3
-> EXP-RC2-CBC-MD5 SSLv2

Recommended SSLCipherSuite configurations for Apache

2008-03-29T18:07:00.000-07:00

UPDATE 2008-06-25: Here's my current recommendation (the rest is left for historical context).
SSLCipherSuite DHE-RSA-AES256-SHA:EDH-RSA-DES-CBC3-SHA:DHE-RSA-AES128-SHA: AES256-SHA:DES-CBC3-SHA:AES128-SHA:RC4-SHA

--

The completist (Thawte-style)

SSLCipherSuite DHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA:EDH-RSA-DES-CBC3-SHA: AES256-SHA:DES-CBC3-SHA:AES128-SHA:RC4-SHA:RC4-MD5

The minimalist (Microsoft-style)

SSLCipherSuite AES128-SHA:AES256-SHA:RC4-SHA:DES-CBC3-SHA:RC4-MD5

For the Comodo version of the minimalist, swap the order of the 2 AES ciphers.

UPDATE 2008-04-04: Slight change to the minimalist config based on more detailed results from the new tool. This also means that the Comodo config is not what is stated above, but is instead:

The descending minimalist (Comodo-style)

SSLCipherSuite AES256-SHA:AES128-SHA:DES-CBC3-SHA:RC4-SHA:RC4-MD5

SSL/TLS cipher selection, with examples and discussion

2008-03-29T16:41:00.000-07:00

The last post has examples of some TLS web server crypto configs, but I didn't explain them, particularly why some are better than others. Let's remedy that.

We'll start with some good ones (always start by examining properly packed parachutes!).

Thawte
The completist

grade for www.thawte.com is HIGH

negotiated cipher for www.thawte.com:
DHE-RSA-AES256-SHA
ephemeral keying -> 1024 bits [expires Sat Jan 17 23:59:59 UTC 2009]

valid ciphers for www.thawte.com:
DHE-RSA-AES256-SHA
AES256-SHA
EDH-RSA-DES-CBC3-SHA
DES-CBC3-SHA
DHE-RSA-AES128-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)

It is clear that a lot of thought went into the selection of these ciphers and their order of preference (this test only shows us the top choice of the server). Starting at the bottom we have the sole SSLv2 cipher for use by the crustiest old browsers. RC4-MD5 is the strongest, widely deployed, unencumbered SSLv2 cipher, so this is the best choice for backwards compatibility. Next there are 2 more RC4 ciphers (both MD5 versions likely come from the same config statement): the same as the bottom, but in TLSv1/SSLv3 guise, and a slightly improved version with SHA1. Again, these are great choices for balancing the minimum security supported against the need to support as many clients as possible.

The top 6 ciphers can be divided into 3 pairs, with each pair using a strong symmetric cipher with and without ephemeral keying. AES128 and Triple DES (the DES ciphers shown with 168 bit keys) are the most common, high strength, symmetric ciphers in modern browsers. The top cipher (DHE-RSA-AES256-SHA) is not only the strongest cipher you can reasonably expect browsers to support, it's also the most preferred cipher from this server. Although I'd like to see a 2048 bit server key to give a bit more strength to sessions not using the DH ciphers, this is a really clean config.

Great job, Thawte!

Microsoft
The minimalist

grade for www.microsoft.com is MEDIUM

negotiated cipher for www.microsoft.com:
AES128-SHA
server certificate strength is LOW -> 1024 bits [expires Wed Feb 11 18:25:18 UTC 2009]

valid ciphers for www.microsoft.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)

This config is very similar to the one from Thawte (great minds think alike?), with the elimination of the DH ciphers. One point of note is that they have chosen not to make the default cipher the strongest one available. This, again, is likely a conscious choice to balance compatibility, security, and performance. AES128-SHA is a very high security cipher, but it also has good performance on a variety of devices. A 2048 bit server key would make this a perfect, all-purpose config.

I haven't checked whether these ciphers are the defaults for IIS. If they are, even more credit to Microsoft for delivering a default security posture superior to many, competing products. Either way, good job!

As a side note, Comodo has a very good, very similar configuration, but the difference makes it less useful as an example.

UPDATE 2008-03-30: This is a really useful little post about IE ciphers. Good reading!

And now, some not so good ones.

Facebook
The kitchen sink

grade for www.facebook.com is LOW

negotiated cipher for www.facebook.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Tue Sep 28 23:53:12 UTC 2010]

valid ciphers for www.facebook.com:
DHE-RSA-AES256-SHA
AES256-SHA
EDH-RSA-DES-CBC3-SHA
DES-CBC3-SHA
DHE-RSA-AES128-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
EDH-RSA-DES-CBC-SHA
DES-CBC-SHA
EXP-EDH-RSA-DES-CBC-SHA
EXP-DES-CBC-SHA
EXP-RC2-CBC-MD5
EXP-RC2-CBC-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

Yikes! I have to think they didn't put much thought into this configuration. It looks like they either went with the Apache default config (which is a bloated mess), or just turned on almost every option and (mostly) called it a day. There is no good reason to include any export ciphers, much less lots of export ciphers (if anyone has solid data supporting or contradicting that assertion, I'd really love to see it). Those 56 bit DES ciphers are similarly antiquated and have no business in there.

The worst part is that, having thrown in every cipher they could find, they set the default to RC4-MD5, a medium security cipher. Facebook has chosen to take the same cipher our good examples above use as a last-ditch fallback for TLSv1/SSLv3 negotiation and made it their preferred cipher. Adding insult to injury is that 1024 bit server key.

A little thought and planning would go a long way.

Bank of America
The heist

grade for www.bankofamerica.com is LOW

negotiated cipher for www.bankofamerica.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Sat Jan 17 23:59:59 UTC 2009]

valid ciphers for www.bankofamerica.com:
DES-CBC3-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA

It looks like someone spent a little time thinking about what to do here, and then decided on the wrong things. The 56 bit DES cipher serves no purpose, there are no AES-based ciphers, and the server default cipher is, as with Facebook, a medium security cipher best used as a fallback. Finally, they have the traditional, 1024 bit server key to round things out.

I'd like to say I expect better from a bank. Instead, all I can say is that I hope for better from a bank. I won't hold my breath.

Yes, gentle reader, the state of affairs in the rarefied world of SSL/TLS web server configuration is pretty rotten. I know we can do better than this. The problems are not technical, but social. Vendors must ship products with sane defaults. Companies who run secure web servers must take due care in configuring them. Customers of those companies should pressure them to fix things that are broken and then take their business elsewhere if problems persist.

setec astronomy

The sorry state of SSL/TLS operational best practice

2008-03-29T15:48:00.000-07:00

A recent discussion on the TLS Working Group list got me curious about how well folks are doing at configuring SSL/TLS on their "secure" web servers. I put together a simple tool to help answer the question, and the the results are pretty grim. Little adoption of the ciphers that use ephemeral keys, widespread use of known-bad export ciphers, almost universal use of 1024 bit RSA keys for server certificates, etc.

Without discussion, here are some results:

Amazon.com


grade for www.amazon.com is LOW

negotiated cipher for www.amazon.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Wed Sep 17 23:59:59 UTC 2008]

valid ciphers for www.amazon.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA
EXP-DES-CBC-SHA
EXP-RC2-CBC-MD5
EXP-RC2-CBC-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

Microsoft


grade for www.microsoft.com is MEDIUM

negotiated cipher for www.microsoft.com:
AES128-SHA
server certificate strength is LOW -> 1024 bits [expires Wed Feb 11 18:25:18 UTC 2009]

valid ciphers for www.microsoft.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)

Comodo


grade for www.comodo.com is MEDIUM

negotiated cipher for www.comodo.com:
AES256-SHA
server certificate strength is LOW -> 1024 bits [expires Mon Jun 28 23:59:59 UTC 2010]

valid ciphers for www.comodo.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)

PayPal


grade for www.paypal.com is LOW

negotiated cipher for www.paypal.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Thu Jan 29 23:59:59 UTC 2009]

valid ciphers for www.paypal.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA
EXP-DES-CBC-SHA
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

Facebook


grade for www.facebook.com is LOW

negotiated cipher for www.facebook.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Tue Sep 28 23:53:12 UTC 2010]

valid ciphers for www.facebook.com:
DHE-RSA-AES256-SHA
AES256-SHA
EDH-RSA-DES-CBC3-SHA
DES-CBC3-SHA
DHE-RSA-AES128-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
EDH-RSA-DES-CBC-SHA
DES-CBC-SHA
EXP-EDH-RSA-DES-CBC-SHA
EXP-DES-CBC-SHA
EXP-RC2-CBC-MD5
EXP-RC2-CBC-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

Thawte


grade for www.thawte.com is HIGH

negotiated cipher for www.thawte.com:
DHE-RSA-AES256-SHA
ephemeral keying -> 1024 bits [expires Sat Jan 17 23:59:59 UTC 2009]

valid ciphers for www.thawte.com:
DHE-RSA-AES256-SHA
AES256-SHA
EDH-RSA-DES-CBC3-SHA
DES-CBC3-SHA
DHE-RSA-AES128-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)

Verisign
Note: Verisign will not negotiate TLSv1


grade for www.verisign.com is LOW

negotiated cipher for www.verisign.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Fri May 08 23:59:59 UTC 2009]

valid ciphers for www.verisign.com:
DES-CBC3-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA
EXP-RC2-CBC-MD5
EXP-RC2-CBC-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

Bank of America


grade for www.bankofamerica.com is LOW

negotiated cipher for www.bankofamerica.com:
RC4-MD5
server certificate strength is LOW -> 1024 bits [expires Sat Jan 17 23:59:59 UTC 2009]

valid ciphers for www.bankofamerica.com:
DES-CBC3-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA

GMail


grade for www.gmail.com is MEDIUM

negotiated cipher for www.gmail.com:
AES256-SHA
server certificate strength is LOW -> 1024 bits [expires Thu May 15 17:24:01 UTC 2008]

valid ciphers for www.gmail.com:
AES256-SHA
DES-CBC3-SHA
AES128-SHA
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
DES-CBC-SHA
EXP-DES-CBC-SHA
EXP-RC2-CBC-MD5
EXP-RC2-CBC-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

CIA


grade for www.cia.gov is LOW

negotiated cipher for www.cia.gov:
RC4-SHA
server certificate strength is LOW -> 1024 bits [expires Sat Feb 12 23:59:59 UTC 2011]

valid ciphers for www.cia.gov:
RC4-SHA
RC4-MD5
RC4-MD5 (SSLv2)
EXP-RC4-MD5
EXP-RC4-MD5 (SSLv2)

BigDecimal: mostly acceptable alternative to Float

2008-03-26T18:59:00.000-07:00

I forgot to mention in yesterday's extended whine about Ruby floating point that there is a package in the standard library called BigDecimal that is a mostly good alternative to the normal Float class. Here is the simplest way to use it:


require "bigdecimal"
require "bigdecimal/util"

The second line adds a new method, to_d, to String, Float, and Rational. Back to my annoying example of broken floating point math:


>> require "bigdecimal"
=> true
>> require "bigdecimal/util"
=> true
>> (9.54 / 0.001)
=> 9540.0
>> (9.54 / 0.001).to_i
=> 9539
>> (9.54 / 0.001).to_d.to_i
=> 9540

Well, almost. BigDecimal slows things down a bit compared to Float and the extra work (the remembering part, not the typing part) of adding to_d is effort that shouldn't be required. I should be clear here that I have no problem with BigDecimal itself. BigDecimal is extremely useful, as are the extended precision libraries for other languages. No, the problem remains that, even though the Ruby Core team could implement a reasonable compromise in Float so it behaves consistently, they refuse to.

rb_spread patch for Ruby 1.8.recent/1.9 and Spread 4.0

2008-03-26T00:03:00.000-07:00

Spread is a group communication system, developed at Johns Hopkins, based on Virtual Synchrony and Extended Virtual Synchrony. Lots of neat stuff therein. The Ruby API hasn't been updated since 2005, though, and will not compile against recent versions of Ruby 1.8 or 1.9, nor is it compatible with the 4.0 release of Spread.

I put together this patch to update the API to the current goodness and make the test and sample programs actually work. My apologies for not doing lots of #ifdefs to make it work with both Spread 3.x and 4.x. I have only tested this on OS X 10.5 on i386. Success or failure, please let me know your experiences on other platforms.

Floating point arithmetic, bug reports, and monkey patching

2008-03-25T23:03:00.000-07:00

It turns out that Barbie was right and math actually is hard. At least, math is hard if you adhere to IEEE floating point spec. C adheres to that spec. Languages built on C inherit that adherence and, even though they could fix some of the problems that come with it, they leave things broken.

In the case of Ruby, they also tell you there is no problem. And it is fixed in the next version. With this monkey patch. But I'm getting ahead of myself.

Here's Ruby (1.8.6 on OS X 10.5) in action:


>> (9.54 / 0.001)
=> 9540.0
>>

Well, that seems straightforward enough. 9540 is certainly the right answer. I need the integer representation, not the floating point version, though, so we'll just call the handy Float#to_i function:


>> (9.54 / 0.001).to_i
=> 9539
>>

Don't feel badly, I blinked several times and had a few more sips of beer before I realized what I was seeing. A second ago, the value was 9540, but now it is 9539. I'll just bang on it a bit to see what I've done wrong:


>> (9.54 / 0.001).to_s.to_i
=> 9540
>>

Yup. By converting the value to a String and then converting that String to an Integer we get the right value back. Sometimes Ruby admits to the underlying IEEE spec edge case, other times it hides it. Sadly, Python behaves similarly (though we are alerted to a problem immediately, rather than having it sneak up on us later):


>>> (9.54 / 0.001)
9539.9999999999982
>>>

Yikes! And, frowny face, the other trouble is here, too:


>>> str(9.54 / 0.001)
'9540.0'
>>> int(9.54 / 0.001)
9539
>>>

I wrote a simple C program to play directly with the underlying types. Here are two variants that illustrate the problem clearly:


#include 

int
main()
{
  double f = 9.54 / 0.001;

  printf("%f %i\n", f, (int)f);

  return 0;
}

$ ./test
9540.000000 9539
$

#include 

int
main()
{
  double f = 9.54 / 0.001;

  printf("%f %i\n", f, (int)(float)f);

  return 0;
}

$ ./test
9540.000000 9540
$

So, I filed a bug against Ruby. Turns out someone else filed a similar bug a few weeks ago. Both of our bugs were rejected on the grounds that things were working as they were supposed to. I continued to argue that, regardless of what the underlying data types are doing, Ruby could and should do better. We went back and forth a bit, and the Ruby gent finally noticed I filed the bug against 1.9.

Why does that matter? Well, it seems that, even though it totally, definitely, under no circumstances is a bug, they've added functionality to Float#round that, among other things, means it is possible to mostly work around the problem. You can now pass it an argument giving the rounding precision desired. So now we can do this (Ruby 1.9 on OS X 10.5):


irb(main):002:0> (9.54 / 0.001).round(2).to_i
=> 9540
irb(main):003:0>

Our grumpy Ruby Core gent was even kind enough to provide a monkey patch to Float to provide a truncate method that actually worked reliably:


class Float
  def truncate_rounding(figs)
    if figs > 0
      n = 10 ** figs
      (self * n).round / n
    else
      n = 10 ** -figs
      (self / n).round / 10 * (n * 10)
    end
  end
end

Since this is absolutely not a bug, the workaround (I can't call it a fix since it introduces problems with overflow) will no doubt remain a hack. A hack to make Float behave correctly. That's a darned shame, Ruby folks.

The developmental biology of infrastructure

2007-06-23T07:52:00.001-07:00

Biologically-inspired technologies have been a research topic for years, autonomic computing and epidemic protocols being a couple of examples. These techniques often have very attractive properties to go with their fun names: scaling, self-healing, resilience, blah, blah, blah. I think about infrastructure and have taken some different things from biology.

The unfortunately named Universal Genetic Code (UGC) and the other, extremely similar variants found in mitochondrial DNA and other small organisms, evolved. We're used to DNA being the stuff of evolution (RNA fans save your flame mails), so the code itself evolving is a bit of a brain bender. Think of it as meta-evolution.

The end of evolution for the UGC happened billions of years ago. Experts call this "early fixation.". The code itself is a marvel of efficiency. It resists exactly the sort of errors to which the transcription machinery is prone. When a transcription error gets through, chances are the erroneous amino acid will have properties similar enough to the correct one that there is little functional difference in the geometry of the final protein. We can appreciate just how spectacular it is because we can almost completely quantify its environment, something simply out of the question with complete organisms. Physics, chemistry, geometry.

The high school biology textbook version of how genes evolve goes something like this: mutation and crossover. Mostly crossover. Read chapters 5 through 7 for Monday.

Reality, as expected, is far richer. Enter Systems Biology and Evolutionary Developmental Biology (evodevo). I can't do justice to the topics in a blog post, but the important idea is this: genes change very slowly, while the gene regulation networks that control their expression are incredibly complex and evolve rapidly.

The bottom of the stack is ridiculously efficient, defined almost entirely by physical constraints, and completely static. Up a level we see simple, modular structures that can be assembled in a variety of ways, and that change very slowly. Finally, at the top, we see the incredible complexity and the roiling expression of evolutionary change.

UGC -> genes -> regulation networks
hardware infrastructure -> software infrastructure -> applications

A bit more about demand locality

2007-06-03T17:40:00.000-07:00

In my last post I focused on geography and culture/language as critical factors for demand locality. However, there are many other ways that demand locality manifests. One of the more subtle is organizational demand locality.

Organizational demand locality is the relative efficiency of carrying traffic entirely within the infrastructure of a single organization versus having to hand-off traffic to other organizations. Wireless carriers offering unlimited "on-net" airtime are exploiting organizational demand locality. Internet service providers spend a surprising amount of resources worrying about peering with each other (or refusing to).

Once again, the geographic/cultural demand locality plays a key role. In places with very high demand locality (Korea, Japan, etc.), the need for numerous, large links between organizations is minimized or avoided entirely. In places with low demand locality (again, I mean the US), peering becomes a constant source of friction with tier-1 ISPs requiring peering at multiple points across the country or not at all. Merging ISPs to raise organizational demand locality only gets you so far.

The applications have to change, not the infrastructure.

Global broadband

2007-05-20T14:11:00.000-07:00

I received an email this morning with a link to this article. There's nothing new or especially interesting in it, but it happened to intersect with some other, related ideas I've been pondering. There is a very wide gap between reality and perception of broadband penetration (the handful of comments under the linked article gives some flavor).

The reason for the disparity is, in part, found in this map. More evidence is here. The story these maps tell is of the business challenges to broadband in the US that are far less severe in other countries, if they exist at all: the physical geography, population distribution, and national or language barriers. The central concept here is demand locality, or how closely geographic locality matches traffic locality. More demand locality means easier deployment of faster and faster services.

Most countries with similar uniformity of language and culture are much smaller than the US and have many fewer population centers. Physical proximity and language/geographic barriers in such countries drive demand locality up and drive infrastructure costs down.

In the US we have dozens of high-density population centers spread across thousands of miles. Despite its wide variety of cultures and languages, the US is dominated by native English speakers who speak no other languages. This implies very high connectivity demands between widely dispersed points in the country. Demand locality is low, so infrastructure costs are high. Not surprisingly, the US has an average broadband speed of 1.9Mb/s.

South Korea is a great example of the rest of the world because it is geographically small, has one major population center, and there are no other Korean speaking countries with network infrastructure. Most sites of interest to South Koreans are inside South Korea, so most traffic in South Korea stays in South Korea. Delivering broadband to most of the population of South Korea means delivering it to Seoul and not worrying much about intra-country long-haul or inter-country connectivity. The result: average broadband speed in South Korea of 45Mb/s. Japan has similar advantages and averages 61Mb/s.

This seems to leave the US stuck in the broadband doldrums. Returning to the article at the top, no broadband initiative is going to change the demand locality. Changing the demand locality requires getting data and applications closer to users. That means building a lot of data centers and properly architecting applications to run in a lot of data centers spread far apart from each other. At that point, individual metro areas can be upgraded with extremely high-speed broadband without needing nearly as much long-haul capacity or worries about transcontinental latency.

Yevgeny Zamyatin

2006-09-06T15:07:00.000-07:00

"It is an error to divide people into the living and the dead: there are people who are dead-alive, and people who are alive-alive. The dead-alive also write, walk, speak, act. But they make no mistakes; only machines make no mistakes, and they produce only dead things. The alive-alive are constantly in error, in search, in questions, in torment."

-- We