The Long Tail of Life

In performing risk assessments we are often asked (or required) to make estimations of values. Typically once a risk is identified it needs to be rated for likelihood (how often) and severity (how bad). The ratings may be difficult to make in the absence of data or first-hand experience with the risk. We often therefore rely on “guesstimates”, calibrated against similar estimates by other colleagues or peers.

Here is a question to exercise your powers of estimation.

I recently came across an article by Carl Haub of the US Population Reference Bureau which seeks to answer the following question - How many people have ever lived? Put another way, over all time, how many people have been born? Haub says that he is asked this question frequently, and apparently there is something of an urban legend in population circles which maintains that 75% of all people who had lived were living in the 1970s. This figure sounds plausible to the lay person since we believe most aspects of the 20th century are characterised by exponential growth.

Haub sought to debunk this statement with an informed estimate. He observes that any estimate of the total number of people who have ever been born will depend basically on two factors: (1) the length of time humans are thought to have been on Earth and (2) the average size of the human population at different periods. Haub assumes that people appeared about 50,000 years ago, and from then till now he creates ten epochs (benchmarks) characterized by different birth rates

The period from 50,000 B.C. till 8,000 B.C., the dawn of agriculture, is a long struggle. Life expectancy at birth probably averaged only about 10 years for this period, and therefore most of human history. Infant mortality is thought to have been very high — perhaps 500 infant deaths per 1,000 births, or even higher. By 1 A.D. the population had risen to 300 million which represents results a meagre growth rate of only 0.0512 percent per year.

By 1650, world population rose to about 500 million, not a significant increase over the 1 A.D. estimate. Numbers were kept in check by the Black Plague which potentially killed 100 million people. By 1800 however, the world population had passed the 1 billion mark, and has increased rapidly to the current 6 or so billion.

The graph below shows another analysis which corroborates the estimates of Haub. The curve exhibits a long tail or power law with a steep increase in population from about the 18th century.

Looking at the curve above you may be tempted to believe the urban legend that 75% of all people ever born were in fact alive in the 70s. Haub in fact reports that in 2002 just under 6% of all people ever born were in fact living. Or put another way, approximately 106 billion people had been born over all time, of which 6 billion are currently living.

The key to this conclusion is the extremely high birth rate (80 per thousand) required to keep humans from becoming extinct between the period of 50,000 B.C. and 1 A.D. According to Haub there had been about 46 billion births by 1 A.D. but only a handful of people had survived. That is, the vast majority of people who have been born have also died.

How good was your estimate to the original question?

Interestingly, WolframAlpha returns the correct answer to the question. I was closer to 30% – 40% of all people being alive today, certainly no where near 6%.

Tipping the Long Black Tailed Swan

Here is an amusing graphic posted over at Paul Kredrosky's blog, which he credits to some people over at Wired as representing credibility versus time for some book-driven memes of recent note.

The Black Swan is currently enjoying a spike of notoriety, as we live through the sub-prime crisis, unpredictable in both its occurrence and impact. But once we recover, perhaps slowly, the dreaded low-probability high-impact event will recede from popular memory, as predicted by its author Taleb. But for the moment he is living out his dream as a public intellectual.

I would suggest that the curves for the Long Tail and the Tipping Point be exchanged, since I think the former has persisted longer in the common perception as the thesis is somewhat more compelling. The Tipping Point is more a clever retelling or repackaging of fad phenomena, while the Long Tail captures more of the current Zeitgeist. In short, Malcolm Gladwell had to write another book before Chris Anderson did. Both memes are now in decline, the Tipping Point from natural attention attrition while the Long Tail has been dealt several heavy body blows based on observed data. But more about that in another post.

Long Tail of Vulnerability for A5/1

Stream ciphers are a special class of cipher, often used for fast encryption of data streams such as dedicated network links or fax lines. Stream ciphers produce a key stream that is simply added (XOR-ed) with the data stream to produce ciphertext, and as such can achieve high encryption rates especially if implemented in hardware.

Below is a diagram of the A5/1 stream cipher, invented in 1987 to protect GSM voice and data traffic. A5/1 loads a 64-bit secret key into its 3 shift registers, which are then clocked and combined with a frame vector to produce an initial state. A5/1 is then clocked as required to produce keystream bits to encrypt the next 114 bit GSM frame.

For over 10 years theoretical attacks on A5/1 have been postulated that lower the cost of attack significantly over searching the 64-bit key space directly. Amongst cryptographers and mobile security people, A5/1 is considered to be insecure and its 64-bit key size woefully inadequate by today's standards.

In February David Hulton, director of applications for the high-performance computing company Pico, and Steve Muller, a researcher for mobile security firm CellCrypt, announced new results which claim that A5/1 keys can be recovered in 30 minutes for $1000. The attack is both passive (no network injection or basestation masquerading) and can be executed remotely (no proximity to the target device required). Further, Hulton & Muller (H&M) are patenting their optimizations and intend to sell an A5/1 key recovery tool commercially. Cell call snooping may soon be affordable by many groups and people, not just well-resourced intelligence agencies.

The attack is based on pre-computing rainbow tables that enable the direct "lookup" of A5/1 keys when indexed by a small amount of observed traffic (3 to 4 GSM frames). While it remains impractical to create a rainbow table that has one entry for each each of the possible 2^(64) A5/1 keys, H&M have devised a method that only requires a table of size 2^(58). Dedicated FPGA devices are currently being deployed to speed up the required rainbow table computations, and are expected to be completed by the end of March. By way of comparison, it is estimated that attempting the same computation on a lone PC would take 33 thousand years.

The resulting rainbow tables will be several terabytes in size, and will be made available to the public. H&M also intend to sell a fast cracking version of the software that can break GSM encryption in just 30 seconds, charging between $200,000 and $500,000 for this privilege. Perhaps they will also offer service of recovering of GSM keys based on submitted traffic samples, giving rise to a instance of cryptanalysis-as-a-service (CaaS).

While researchers and security professionals view the H&M approach as cheaper and more efficient than previous attacks, the attack itself comes as no surprise given the known weaknesses of A5/1. The practicality of the H&M approach should be the final piece of evidence to convince operators to move off A5/1 as a basis for secure and private for GSM communication. David Pringle, a spokesperson for the GSM Association (GSMA), has declined to comment on the H&M attack until further details are known.

A5/1 has operated unchanged for the last 21 years but it has now reached its cryptographic end-of-life, engulfed by the march of Moore's Law. However, the operational end-of-life of A5/1 may still be decades away as there are approximately 2 billion GSM subscribers, commanding about 80% of the global mobile market. This would be a tough product recall indeed. A5/1 is well-positioned to become the NT of the mobile crypto world, and I see the makings of a long tail of GSM vulnerability.

You can find the research used to produce this post as a FreeMind mindmap rendered into Flash here.

Related Posts

• Another crack at open Rainbow Tables for A5/1