Tuesday, May 20, 2008

Alarming Open-Source Security Holes

How a programming error introduced profound security vulnerabilities in millions of computer systems.

By Simson Garfinkel

Back in May 2006, a few programmers working on an open-source security project made a whopper of a mistake. Last week, the full impact of that mistake was just beginning to dawn on security professionals around the world.

In technical terms, a programming error reduced the amount of entropy used to create the cryptographic keys in a piece of code called the OpenSSL library, which is used by programs like the Apache Web server, the SSH remote access program, the IPsec Virtual Private Network (VPN), secure e-mail programs, some software used for anonymously accessing the Internet, and so on.

In plainer language: after a week of analysis, we now know that two changed lines of code have created profound security vulnerabilities in at least four different open-source operating systems, 25 different application programs, and millions of individual computer systems on the Internet. And even though the vulnerability was discovered on May 13 and a patch has been distributed, installing the patch doesn't repair the damage to the compromised systems. What's even more alarming is that some computers may be compromised even though they aren't running the suspect code.

The reason that the patch doesn't fix the problem has to do with the specifics of the programmers' error. Modern computer systems employ large numbers to generate the keys that are used to encrypt and decrypt information sent over a network. Authorized users know the right key, so they don't have to guess it. Malevolent hackers don't know the right key. Normally, it would simply take too long to guess it by trying all possible keys--like, hundreds of billions of years too long.

But the security of the system turns upside down if the computer can only use a limited number of a million different keys. For the authorized user, the key looks good--the data gets encrypted. But the bad guy's software can quickly make and then try all possible keys for a specific computer. The error introduced two years ago makes cryptographic keys easy to guess.

The error doesn't give every computer the same cryptographic key--that would have been caught before now. Instead, it reduces the number of different keys that these Linux computers can generate to 32,767 different keys, depending on the computer's processor architecture, the size of the key, and the key type.

Less than a day after the vulnerability was announced, computer hacker HD Moore of the Metasploit project released a set of "toys" for cracking the keys of these poor Linux and Ubuntu computer systems. As of Sunday, Moore's website had downloadable files of precomputed keys, just to make it easier to identify vulnerable computer systems.

Unlike the common buffer overflow bug, which can be fixed by loading new software, keys created with the buggy software don't get better when the computer is patched: instead, new keys have to be generated and installed. Complicating the process is the fact that keys also need to be certified and distributed: the process is time consuming, complex, and error prone.

Nobody knows just how many systems are impacted by this problem, because cryptographic keys are portable: vulnerable keys could have been generated on a Debian system in one office and then installed on a server running Windows in another. Debian is a favored Linux distribution of many security professionals, and Ubuntu is one of the most popular Linux distributions for general use, so the reach of the problem could be quite widespread.

So how did the programmers make the mistake in the first place? Ironically, they were using an automated tool designed to catch the kinds of programming bugs that lead to security vulnerabilities. The tool, called Valgrind, discovered that the OpenSSL library was using a block of memory without initializing the memory to a known state--for example, setting the block's contents to be all zeros. Normally, it's a mistake to use memory without setting it to a known value. But in this case, that unknown state was being intentionally used by the OpenSSL library to help generate randomness.

The uninitialized memory wasn't the only source of randomness: OpenSSL also gets randomness from sources like mouse movements, keystroke timings, the arrival of packets at the network interface, and even microvariations in the speed of the computer's hard disk. But when the programmers saw the errors generated by Valgrind, they commented out the offending lines--and removed all the sources of randomness used to generate keys except for one, an integer called the process ID that can range from 0 to 32,767.

"Never fix a bug you don't understand!" raved OpenSSL developer Ben Laurie on his blog after the full extent of the error became known. Laurie blames the Debian developers for trying to fix the "bug" in the version of OpenSSL distributed with the Debian and Ubuntu operating systems, rather than sending the fix to the OpenSSL developers. "Had Debian done this in this case," he wrote, "we (the OpenSSL Team) would have fallen about laughing, and once we had got our breath back, told them what a terrible idea this was. But no, it seems that every vendor wants to 'add value' by getting in between the user of the software and its author."

Perhaps more disconcerting, though, is what this story tells us about the security of open-source software--and perhaps about the security of software in general. One developer (who I've been asked not to single out) noticed a problem, proposed a fix, and got the fix approved by a small number of people who didn't really understand the implications of what was being suggested. The result: communications that should have been cryptographically protected between millions of computer systems all over the world weren't really protected at all. Two years ago, Steve Gibson, a highly respected security consultant, alleged that a significant bug found in some Microsoft software had more in common with a programmer trying to create an intentional "back door" than with yet another Microsoft coding error.

The Debian OpenSSL randomness error was almost certainly an innocent mistake. But what if a country like China or Russia wanted to intentionally introduce secret vulnerabilities into our open-source software? Well concealed, such vulnerabilities might lay hidden for years.

One thing is for sure: we should expect to discover more of these vulnerabilities as time goes on.

Simson Garfinkel is an associate professor at the naval postgraduate school in Monterey, CA, and a fellow at the Center for Research and Computation and Society at Harvard University.

DNA Sequencing in a Snap

An innnovative approach could target hard-to-sequence areas.

By Emily Singer

A novel sequencing technology being developed by a Massachusetts startup allows scientists to take photographs of the sequence of a DNA molecule. William Glover, president of ZS Genetics, based in North Reading, MA, says that his approach will allow scientists to read long stretches of DNA, enabling the sequencing of hard-to-read areas, such as highly repetitive regions in plants and some parts of the human genome. Longer sequences also allow scientists to distinguish between maternal and paternal chromosomes, which might have important diagnostic applications.

Scientists at a recent sequencing conference in San Diego--where details of the technology were presented for the first time--were intrigued by the approach because it is totally different than even the newest methods on the market. "It's surprising and potentially very powerful," says Vladimir Benes, head of the Genomics Core Facility at the European Molecular Biology Laboratory, in Germany.

The cost of DNA sequencing has plummeted since a working draft of the human genome was completed in 2001. Most of the newest technologies currently in use generate very short sequences, about 30 to 150 base pairs, which are then stitched together with special software. But this method doesn't always capture all the information in the genome, and some parts of the genome are difficult to sequence this way, says Glover.

Seeing the sequence: This image shows a cluster of DNA molecules (black strands) that have been synthesized using bases that are specially labeled to be visible under an electron microscope. Scientists are using this technique to develop a novel sequencing technology.
Credit: ZS Genetics

ZS Genetics is a relative newcomer to the field and uses an approach vastly different than any other: electron microscopy. Glover predicts that by next year, the company's technology will be able to generate readable lengths of DNA that are thousands of base pairs long, and he believes that ZS Genetics' sequencing method will improve by a factor of 10 in the next couple of years, making the pieces even easier to assemble. The company was recently accepted as one of the teams in the Archon X Prize for Genomics, a $10 million award for the first privately funded team that can sequence 100 human genomes in 10 days.

"Any technology that can bring the read length to the 1,000 base-pairs range will definitely, at least for de novo sequencing, represent a major breakthrough," says Benes. He says that the approach might be particularly useful for sequencing the genomes of plants, which often have highly complex genomes littered with repetitive sequences that are difficult to assemble computationally.

At a width of 2.2 nanometers, DNA is invisible under an average light microscope.

But electron microscopes, which detect the difference in charge between atoms, have a subnanometer resolution. While the sequence of natural DNA lacks enough contrast to be resolved with electron microscopy, Glover and his colleagues developed a novel labeling system to make the molecules more visible.

Researchers synthesize a new complementary strand of the molecule to be sequenced using bases--the letters that make up DNA--labeled with iodine and bromine. The labeled bases appear as either large or small dots under the electron microscope, allowing scientists to read the sequence. (Three different labels will be required to read the sequence of the four bases found in DNA. Three of the bases will have different labels; the fourth will simply remain unlabeled.)

The substrate on which the newly labeled molecules are imaged is made using semiconductor fabrication techniques. Scientists generate silicon wafers with an 11-nanometer-thick window, which is thin enough for the electron beam of the microscope to discern the DNA molecule from the substrate. ZS Genetics is also working on making even thinner wafers to boost resolution of the image.

DNA has a tendency to curl up into a tangled mass, so one of the biggest challenges has been untangling that ball into linear strands that can be read. Researchers first flow fluid through a microfluidic device with tiny channels. That device fits on top of the DNA-coated wafer. The force of the flow stretches the DNA molecules, which then stick to the silicon. An electron beam is shot through the wafer, and a camera captures the image from the other side. "The wafer is the major proprietary consumable," says Glover. "It will be dirt cheap."

When stretched, the DNA looks like a ladder with the bases forming the rungs. So far, the company has released images of a 23-kilobase piece of DNA using a single type of labeled base. Glover says that he and his team have also done multilabel sequencing, although he declined to give additional details.

Still, the technology has a ways to go before it's market ready. "Lots of proof of principle methods can work in R&D, but bringing it to [market] is not trivial," says Benes. Glover aims to have a prototype this summer that scientists can test, and a faster commercial system next year. He adds that because most of the system relies on existing technologies, it will be easy and inexpensive to upgrade the system with new cameras and software.

Longer reads will allow scientists to look at collections of genetic variations that have been inherited together, known as haplotypes. This kind of analysis can determine if a particular genetic variation has been passed down from the individual's mother or father. Recent research suggests that in some cases, maternal or paternal inheritance can impact the severity of the disease, a phenomenon that may be more common than previously thought.

Friday, May 16, 2008

A Faster, More Energy-Efficient GPS

New software could help make location-aware devices ubiquitous.

By Kate Greene

If you want to add location information to pictures today, it's a fairly tedious process. Many people manually annotate their pictures after they've uploaded them to a computer. And while some high-end cameras come equipped with a Global Positioning System (GPS) chip that captures the location information, this extra hardware is slow and can drain battery power. Now Geotate, a U.K.-based spinoff of Philips Research, thinks that it can make GPS faster and more energy efficient in any device.

As more people take pictures on digital cameras, there's a growing interest in making sure that those pictures are geotagged. When pictures contain location information, they could be easier to sort in personal photo software like iPhoto. And if geotagged pictures are uploaded to a photo-sharing site, such as Flickr, then others can benefit from the information when, say, planning a vacation. Right now, only a small fraction of photos contain any information about where they were taken.

To be sure, Geotate isn't the only company trying to make geotagging more common. Eye-Fi announced this week that it will sell a memory card for cameras that can automatically and wirelessly upload geotagged photos to a computer or photo-sharing site. Eye-Fi's technology differs from Geotate's in that it approximates a camera's location from the local Wi-Fi routers--information that's accessed via Skyhook Wireless's extensive database of Wi-Fi hot spots covering 70 percent of the United States.

Tag, you’re it: This GPS device from Geotate, attached to the top of the camera, can capture just enough data from GPS satellites that the location of the device can be determined when the pictures are uploaded to a computer. By not processing the satellite data on a specialized GPS chip, Geotate’s approach saves time and battery power.
Credit: Geotate

Since Geotate's approach doesn't require a Wi-Fi signal, it's practical in more-remote locations. However, it falls short in major urban areas, where GPS signals tend to get blocked by tall buildings. Ultimately, the best geotagging results would come from a combination of services that use a variety of location-tracking technologies, suggests Alexandre Bayen, a professor of civil and environmental engineering at the University of California, Berkeley.

The basic idea behind Geotate's approach, called Capture and Process, is to collect only a small amount of information from the GPS satellites that help determine location, explains Chris Marshall, the company's CTO. And instead of processing this information on a GPS chip within a gadget, it's processed, with the help of software developed at the company, on a computer when the photos are uploaded. "If you can do the processing in software," says Marshall, "then you don't need a dedicated chip."

Traditional GPS systems require a lot of electronics, including amplifiers, filters, an antenna, and a processing chip. A GPS-enabled device listens to signals, which contain orbit information, from the GPS satellites. Using this information, the device can calculate the distance between itself and the satellite, and from that determine where it is. But it can take 30 seconds for a satellite to stream its position to a GPS receiver. And only after the GPS system decodes the orbit information from four satellites can it calculate the location--a process that requires the processor to churn through a relatively large amount of data.

Geotate's approach is a redesign of the system that loses the processor. Instead, the hardware simply captures a small sample--200 milliseconds worth--of satellite orbit information and it stores it in memory. When a person uploads her pictures to a computer, the accompanying GPS data is used to calculate location information by employing the computer's processor and by querying Geotate's database of historic satellite positioning. The process requires only 10 millijoules of energy at the time the picture is taken, says Geotate's Marshall, which is about one-hundredth of the energy used in a traditional GPS system.

While the company doesn't provide any specific hardware, it is working with personal electronics companies to incorporate the approach in cameras. But ultimately, Geotate's product is the GPS processing software and the database used to locate the satellites after the fact. Marshall says that he expects Capture and Process add-ons for cameras to be available by the end of the year.

Bayen suspects that geotagging photos and other objects will start to be more popular in the coming years as people get more used to location-based services and location-aware devices such as the iPhone. It's unclear if Geotate's approach will be widely adopted in the industry, but it is approaching the industry wisely by attempting to solve energy-efficiency problems. In order to get more people to geotag their photos, says Bayen, the location technology needs to not drain the battery.

Tuesday, May 13, 2008

Returning to the Moon

New technologies on NASA's next lunar spacecraft will collect information to make human exploration safer.

By Brittany Sauser

NASA's next lunar orbiter will launch later this year, the first step in an ambitious plan to return humans to the Moon--and send them on to Mars. The spacecraft, called the Lunar Reconnaissance Orbiter (LRO), will use new technology to make precise maps of the Moon's surface, to search for resources such as ice, and to assess the threat that radiation in the environment could pose for humans.

LRO is the most advanced lunar satellite NASA has built, says Richard Vondrak, the project scientist for LRO, who adds that it will provide information that would have been impossible to collect a few decades ago. "We are surveying the Moon in more detail than any other celestial body for the benefit of all countries, including China, Japan, and India, who have said they have ambitions to put people on the Moon in the next 10 to 20 years," adds David Smith, a NASA scientist working on LRO.

LRO is part of NASA's Vision for Space Exploration, a program intended to, among other things, answer fundamental questions of physics, search for extraterrestrial life, and seek new resources, such as power sources, for Earth. The program calls for humans to return to the Moon. But before that happens, says Vondrak, it's necessary to understand much more about the Moon's surface radiation and topography.

"During Apollo, there were a number of near-fatal mistakes," says Smith. "We did not land on a flat surface, and there were boulders everywhere, which could have damaged the vehicle and prevented a return to Earth. Safety standards today would not have allowed Apollo."

The Apollo manned-spacecraft program shut down in 1975, and it was not until the 1990s that the United States sent more satellites to orbit the Moon--Clementine and the Lunar Prospector, which spent months orbiting the Moon and sending back data. Clementine was a joint project between the U.S. Department of Defense and NASA that also tested new ballistic technologies; the U.S. has launched no other lunar probes since.

LRO will collect more data with greater precision so that scientists can find safe and resource-rich landing sites and design systems appropriate for the lunar environment, says Vondrak.

Moonbound: The Lunar Reconnaissance Orbiter (above) will orbit and survey the Moon, providing greater detail about its surface and environment than any previous satellite has. One of two new instruments onboard the spacecraft will be the lunar orbiter laser altimeter (bottom), which will send out five laser beams 28 times per second to map the surface of the moon. Very short pulses of laser light are emitted through the narrow silver cone attached to the instrument’s optical assembly (gold-colored box). The large cone collects the laser light that is reflected back from the lunar surface.
Credit: NASA

LRO will collect more data with greater precision so that scientists can find safe and resource-rich landing sites and design systems appropriate for the lunar environment, says Vondrak.

LRO will orbit the Moon for one year at an altitude of 50 kilometers. Previous U.S. satellites maintained an altitude of approximately 100 to 200 kilometers, as have those sent by other countries, like China's Chang'e 1 and Japan's Kaguya, both launched in 2007. Orbiting at a lower altitude allows the spacecraft to get a closer view of the Moon, enabling the craft to obtain higher-resolution images, very detailed maps, and more-accurate temperature measurements, says Vondrak.

The lunar orbiter is equipped with six novel instruments, two of which will be making their space debuts: a cosmic-ray telescope, which will measure the effects that lunar radiation would have on humans, and a laser altimeter, which will make maps of the surface of the Moon.

The cosmic-ray telescope, called Crater, is a new kind of sensor developed by MIT, Boston University, the University of Tennessee at Knoxville, and the Aerospace Corporation. It can measure the radiation environment, not just in space, but also as it would be experienced by astronauts on the surface on a day-to-day basis. "By characterizing the radiation, we can build better shielding on spacecraft so that astronauts can survive long trips to the Moon and Mars," says Justin Kasper, a staff astrophysicist at the Harvard-Smithsonian Center for Astrophysics and the project scientist for Crater.

The human body responds to radiation in different ways, depending on the intensity, duration, and composition of the radioactive particles. The two things that scientists are most worried about are acute radiation poisoning from, for example, a solar flare, and long-term exposure to galactic cosmic rays, which can increase the risk of cancer. "In all cases, the danger is that ionizing radiation [high-energy, charged particles] can break the atomic bonds in DNA and damage cells and tissue," says Kasper.

The radiation detector consists of a series of silicon semiconductors, each about 35 millimeters in diameter and one millimeter tall. In between the pieces of silicon, the scientists have inserted large blocks of material called tissue-equivalent plastic. "The blocks are waxy and look like giant black crayons but have the same chemical composition as human tissue," says Kasper.

So while the silicon gauges the energy and composition of particles as they come flying through the detector (a proven technique for measuring radiation), the plastic is used to measure their biological effects. Previously, data from radiation detectors was sent back to Earth, where scientists attempted to calculate the effect that the measured radiation would have on humans. The plastic material provides a direct and more-accurate measurement of what radiation is like at different depths of human tissue, says Kasper.

The second instrument making its first spaceflight is the lunar orbiter laser altimeter (LOLA), developed by engineers at NASA Goddard Space Flight Center. It uses laser light to measure the distance between the spacecraft and the surface of the Moon. "It is going to measure that distance very precisely, to about 10 centimeters, and it will make measurements 28 times per second," says NASA's Smith, who is also the principal investigator for LOLA. Unlike current instruments, which send out a single laser beam at low repetitions, the new altimeter sends out five focused beams of laser light that are reflected back and received by five separate detectors, for a total of 140 measurements per second.

This allows scientists to make a high-density, very precise map of the shape of the lunar surface. "We can determine the altitude and slope of different spots on the Moon as well as the roughness of the terrain," says Smith. "We can also learn about the properties of the surface--for example, the shape of craters and their depth and size." The end goal is to identify the best spot, preferably flat, for a large lander to touch down and for astronauts to make a base.

Crater and LOLA will be accompanied on the lunar orbiter by four other instruments that will be imaging and mapping the Moon, measuring surface temperatures to identify potential ice deposits, and searching for hydrogen in the lunar polar regions. All the data will be continuously sent back to Earth for analysis.

"LRO is the first of our exploration missions for a return to the Moon and will have a significant impact on future human spaceflight," says Vondrak

Oil

The $200 barrel of oil?

May 7th 2008
From Economist.com

OIL briefly reached another record on Tuesday May 6th as West Texas Intermediate traded at over $122 a barrel for the first time. Ten years ago a barrel fetched around $15. The feeble dollar, soaring demand and supply constraints have all helped to push up prices by 25% in the past four months alone. And there is little sign of respite for worried governments and consumers. This week Goldman Sachs, a bank, predicted that oil could reach $200 a barrel before the end of the year.

Corbis

Neuer Standard für IP-Protokoll

Das Internet braucht neue Hausnummern

DruckenVersendenSpeichernVorherige Seite

Jeder Rechner hat seine eigene IP-Adresse

06. Mai 2008 Langsam, aber unausweichlich wird es eng im Internet. Das für den Datenverkehr im Netz grundlegende Internet-Protokoll ermöglicht 3,7 Milliarden Adressen - bei einer Weltbevölkerung von 6,7 Milliarden sind das deutlich zu wenig. In dieser Woche wollen rund 200 Teilnehmer einer Fachkonferenz in Potsdam die Lösung für das Problem vorantreiben: IPv6 hat mit 340 Sextillionen Adressen praktisch unendlich viel Platz.

Dieses Internet-Protokoll in der Version 6 sei schon fast zehn Jahre alt, erklärt Konferenzleiter Christoph Meinel. „Man hat sich damals hingesetzt und gefragt: Wie machen wir es richtig?“ Denn bereits Mitte der 90er Jahre erkannte man die Mängel der Version 4 des Internet-Protokolls - vor allem die begrenzte Verfügbarkeit von Adressen, in der Fachsprache als Adressraum bezeichnet.

Danach sei IPv6 aber nicht richtig in die Gänge gekommen, erklärt Meinel, der das Hasso-Plattner-Institut (HPI) an der Universität Potsdam leitet. Vor allem in den Vereinigten Staaten hielt sich die Begeisterung in Grenzen - die dort eingerichteten Netze verfügen ja auch über etwa 74 Prozent aller derzeit vergebenen IP-Adressen. Für China und andere asiatischen Ländern sei der Druck der Adressenknappheit aber sehr viel stärker, erklärt Meinel. Daher werde IPv6 dort sehr viel massiver vorangetrieben.

Netzanbindung für Geräte aller Art

„Inzwischen kommt auch in den USA und bei uns Bewegung hinein“, sagt Meinel. Als treibende Kräfte nennt er den Trend zum „Internet der Dinge“, also der Netzanbindung von elektronischen Geräten aller Art vom Stromzähler bis zum Kühlschrank. Interessant ist das neue Protokoll auch für mobile Anwendungen. Für Handys und andere mobile Geräte gebe es bislang keine feste IP-Adresse, erklärt der Informatiker. Das erschwert die Entwicklung von Web-Anwendungen, die ein Gerät gezielt ansprechen müssen. „Das wird alles mit IPv6 möglich“, sagt Meinel.

Der Umstellungsprozess wird schrittweise vor sich gehen und betrifft alle Netzanbieter und -nutzer, auch den Endanwender. „Die meisten Provider beschäftigen sich noch nicht genug mit IPv6“, sagt Frank Orlowski vom Internet-Austauschknoten DE-CIX in Frankfurt am Main. „Je früher man damit anfängt, umso besser.“ Es dürfe keine Torschlusspanik aufkommen, aber „irgendwann gibt es nichts mehr, was noch an Adressräumen verteilt werden kann“. Immerhin nutzen nach Angaben Orlowskis bereits 70 bis 80 Provider der 240 am DE-CIX angeschlossenen Netze das neue Internet-Protokoll.

Der Netz-Experte erwartet, dass es eine Übergangszeit geben wird, in der beide Protokolle parallel verwendet werden können. „Irgendwann wird man dann aber das alte Netz abschalten“, erklärt Orlowski. „Das wird ein Prozess sein, der mehrere Jahre in Anspruch nimmt.“ Die Schätzungen für den Zeitpunkt, zu dem es keine freien IP-Adressen mehr geben wird, reichen je nach Szenario von 2010 bis 2012.

Abschied von dynamischen Adressen

Auch der Potsdamer Informatik-Professor Meinel sieht keinen Grund für Panik: „Es ist nicht so, dass plötzlich alles schwarz wird für die, die nicht umgestellt haben.“ Schließlich gibt es auch die als „Tunneling“ bezeichneten Möglichkeiten, Daten des einen Protokolls so zu transportieren, dass sie von einem anderen Protokoll verstanden werden. Allerdings könnte es dabei zu gewissen Leistungseinbußen kommen.

Die Umstellung ist auf Seiten der Provider mit Investitionen in neue Hardware verbunden - die neuen Router müssen dann schließlich mit IPv6 umgehen können. Meinel erwartet aber, dass dies im Rahmen der ohnehin üblichen Erneuerung von Geräten ablaufen kann. Auch der DSL-Router für das drahtlose WLAN-Netz daheim muss dann IPv6 verstehen können, aber Meinel sieht in der Bereitstellung der entsprechenden Geräte kein großes Hindernis: „IPv6 soll nicht teuer werden.“

„Never touch a running system“

Für gewichtiger hält der HPI-Direktor die Sorgen nach dem Motto „Never touch a running system“. Mancher werde sagen: „Mein Internet funktioniert doch.“ Solche Bedenken müssten mit einer breiten Aufklärung über die Vorteile überwunden werden, meint Meinel.

Bei IPv6 werden keine dynamischen IP-Adressen mehr zugewiesen, wie es bei der Einwahl ins Netz mit einem Modem oder auch bei den meisten DSL-Verbindungen der Fall ist. Feste IP-Adressen haben den Vorteil, dass man einen eigenen Web-Server betreiben kann, der auch ohne Anmeldung einer Domain, also einer Internet-Adresse nach dem Muster meineDomain.de, immer unter der gleichen Ziffern-Adresse erreichbar ist. Andererseits erhöht eine dynamische, also sich immer wieder ändernde IP-Adresse auch den Schutz der Privatsphäre. Der Informatiker Meinel aber sieht in den dynamischen Adressen nur einen Notbehelf der IPv4-Ära: „Eigentlich sollten Datenschutz und Sicherheit auf anderen Methoden beruhen.“

Internet-Protokoll (IP)

Das Internet-Protokoll (IP) ist ein zentraler Standard für die Selbstorganisation des weltweiten Datennetzes. Es ermöglicht eine eindeutige Identifizierung für jedes an das Internet angeschlossene Gerät.

Bisher gilt im Netz Version 4 des Internet-Protokolls: IPv4 wurde bereits 1981 festgelegt. Es legt die Adressen in einem Datenblock mit einer Länge von 32 Bit ab: Vier Folgen von maximal drei Ziffern zwischen 0 und 255, die durch Punkte abgetrennt werden. Damit sind 4,3 Milliarden Internet-Adressen möglich, von denen allerdings 600 Millionen reserviert sind, so dass nur 3,7 Milliarden übrig bleiben.

Sehr viel mehr Platz bietet Version 6: IPv6 vergrößert den Datenblock auf 128 Bit, was mehr als 340 Sextillionen Adressen ermöglicht, aufgeteilt in acht Zahlenblöcken. Diese werden nicht in Dezimalziffern, sondern in hexadezimaler Schreibweise notiert, also in einem 16er Zahlensystem mit den zusätzlichen Buchstaben a bis f. IPv6 wurde im Dezember 1998 als Standard verankert, bis heute aber erst ansatzweise umgesetzt.

Friday, May 02, 2008

South Korea begins imports of biotech corn because of shortage of conventional grain

By Associated Press

Major South Korean corn processors have begun importing genetically modified varieties of the crop because of shortages of conventional corn on the world market since China began limiting its exports, officials said Friday.

About 63,000 tons of genetically modified U.S. corn arrived in South Korea on Thursday, the first large-scale imports for human consumption since the government began regulating biotech crops in 2001.

Four major South Korean companies, which make up about 90 percent of the corn processing market, had refrained from importing such corn because of negative perceptions among consumers of genetically modified organisms, or GMOs.

But now they say they cannot help but import GMO corn.

''China has stopped exports, while European countries are sweeping off non-GMO corn from Latin American nations,'' said Yoo Chang-kyu, an official with the Korea Corn Processing Association, the business lobby for the four companies. ''We don't have any other options.''

The companies use corn to produce corn starch, a key ingredient in cookies, beverages, ice cream and other foods.

Environmental and consumer groups protested the import of biotech corn, calling it ''monster food.''

''The safety of genetically modified corn has not been fully verified,'' they said in a joint statement. ''If food is made with it, the health of our nation's people can be threatened.''

On Thursday, activists held a protest at the port of Ulsan, where the GMO corn arrived, Yonhap news agency reported.

South Korea imported about 10.5 million tons of corn last year, with 8.2 million tons intended for animal feed and 2.3 million tons for human consumption, according to the Agriculture Ministry.

About half of the amount for human consumption was imported from China, 30 percent from the United States and the remainder from Brazil and other Latin American nations, it said.

China began limiting corn exports last year to avoid domestic shortages.

Local newspapers said the four Korean companies are expected to import about 1.3 million tons of GMO corn this year.

But Yoo, of the corn processing association, said the amount is likely to be less than that considering the expected backlash from consumers. He provided no exact estimate.

Yoo said the price of non-GMO corn has more than doubled to about US$360 per ton since 2006.

South Korea enforced a regulation in 2001 that calls for the labeling of products that contain GMOs.

Although no GMO corn had been imported in large amounts since then, about 70 percent of the country's soybean imports are genetically modified, according to the Korea Food and Drug Administration.

Electric Cars Primer

http://www.technologyreview.com/read_article.aspx?ch=specialsections&sc=batteries&id=20651&a=

All of Inflation’s Little Parts

http://www.nytimes.com/interactive/2008/05/03/business/20080403_SPENDING_GRAPHIC.html

Ölpreis klettert über 120 Dollar

von Tobias Bayer (Frankfurt)

Förderausfälle in Nigeria und erfreuliche US-Konjunkturdaten haben den Ölpreis erstmals über 120 $ gehievt. Analysten rechnen damit, dass sich die Rally kurzfristig fortsetzt.

n New York verteuerte sich Rohöl der Sorte West Texas Intermediate zur Lieferung im Juni auf 120,21 $ je Barrel (entspricht 159 Litern). Das entspricht einem Tagesanstieg von knapp 4 $.

Die Rally des Ölpreises hält zur Zeit ungebremst an. Auf Jahressicht legte er um 93 Prozent zu. Befeuert wird die Hausse von der Angst vor künftigen Knappheiten, tatsächlichen Versorgungsstörungen und dem wachsenden Interesse der Finanzwelt an Rohstoffen als Vermögensklasse, die einen Schutz vor dem Dollar-Verfall und Inflation bietet. So hat der Greenback gegenüber der dem Euro in den vergangenen zwölf Monaten um 14 Prozent abgewertet. Nach Schätzungen haben Anleger derzeit 225 Mrd. $ in Rohstoffen investiert. Allein im ersten Quartal stieg das Engagement um 30 Mrd. $.

Einkaufsmanagerindex stützt Ölpreis

Alles schaut auf Nigeria: Das afrikanische Land ist bestimmend für den Ölpreis

Für den Preisanstieg am Montag ausschlaggebend waren Nachrichten vom Wochenende aus Nigeria. Demnach haben militante Rebellen ein Transportsystem angegriffen und Royal Dutch Shell dazu gezwungen, den Ausstoß zu reduzieren. Preistreibend wirkte zudem der US-Einkaufsmanagerindex für den Dienstleistungssektor. Im April stieg der Konjunkturindikator unerwartet von 49,6 auf 52 an. Ein Wert über 50 signalisiert Wachstum. Händler sehen sich deshalb bestärkt darin, dass es um die Wirtschaft der USA nun doch nicht so schlimm bestellt ist wie angenommen. Die Vereinigten Staaten sind der größte Verbraucher der Welt. Im Februar fiel die Ölnachfrage um sieben Prozent - das ist der größte Einbruch seit Dezember 2001.

Eugen Weinberg, Rohstoffanalyst der Commerzbank, rechnet mit Blick auf die spekulativen Kaufpositionen mit einem weiteren Preisanstieg. "Angeführt von der Preisschwäche Anfang letzte Woche sind die Netto-Long-Positionen der Großanleger bei Rohöl um 17.000 Kontrakte zurückgekommen und liegen bei 53.300 Kontrakten. Dies lässt noch viel Spielraum nach oben und macht weitere Steigerungen wahrscheinlich", schreibt Weinberg in einem Researchbericht.

Microsoft and Yahoo!

Microsoft throws in the towel

May 4th 2008
From Economist.com

The software giant withdraws its bid for Yahoo!

HE build up had all the atmosphere of one of boxing’s bigger bouts. But three months after Microsoft laid down the challenge, it elected to walk away from its takeover bout for Yahoo!. On Saturday May 3rd the software giant laid down its gloves, despite expectations of a hostile contest. One last attempt to improve the deal had failed. Microsoft said that it had raised its $44.6 billion bid by $5 billion, but that as Yahoo! was holding out for a bigger purse it would walk away. Failing to buy Yahoo! leaves Microsoft well short in its bid to go after the ultimate champion of the internet: Google.

Microsoft and Yahoo! are a distant second and third in the lucrative business of web search and related advertising. The idea of combining was to challenge the clear leader, Google. Microsoft wanted Yahoo! in order to add critical mass to Microsoft's own advertising platform, to make it more competitive. But Yahoo! was not keen to join the effort to become an advertising counterweight to Google. Jerry Yang, Yahoo!’s founder, had no wish to see the company he created swallowed up by Microsoft. Last year, in an effort to revive his former giant of the web, he resumed his role as chief executive and from that position tried to ward off an offer that he reckoned “substantially undervalues” the company.

These efforts set off a string of shifting alliances, rumour, claim and counterclaim that offered a variety of permutations of tie-ups between big internet firms. Yahoo! has been aiming to compete with Google for years, but without success. Under assault from Microsoft, Yahoo! has hinted that it might give up and, in effect, piggy-back on Google's superiority in order to boost its own profits and persuade shareholders not to sell to Microsoft. Yahoo! ran a limited trial in which it allowed Google to place text advertisements on Yahoo!'s search pages in America. Rumours circulate still that it wants to extend this arrangement. Moreover, other rumours suggest that Yahoo! has been discussing a merger with Time Warner’s internet arm, AOL.

As Yahoo! threw up its defences, Microsoft also became the subject of rumours. One suggested that Microsoft might team up with News Corporation, an old-media heavyweight controlled by Rupert Murdoch, a wily new-media operator too. The pair were said to be considering a joint bid for Yahoo!. Yet previously Mr Murdoch had been mooted as a “white knight” to save Yahoo! from Microsoft’s clutches. He, probably wisely, decided to avoid involvement in a bidding war against an opponent with deep-pockets.

In the end Steve Ballmer, Microsoft’s chief executive, said that Yahoo!’s determination to pursue closer ties with Google, even as takeover talks progressed, were reason enough to drop the takeover offer. For its part Yahoo! reckoned that the prospects of closer advertising ties with Google justified a much higher price than Microsoft was prepared to pay. Mr Ballmer said Microsoft was reluctant to launch a hostile bid as the firm was unwilling to get involved in a protracted fight for the support of Yahoo!’s shareholders. There was also concern that that Yahoo! might make matters more difficult in the meantime: it has already introduced some “poison pills” including an expensive buyout for any worker sacked by a buyer.

Microsoft has lost out and may now look elsewhere to take the fight to Google. Yet there are few obvious targets that would give it the boost that Yahoo! offers, although AOL is a possibility. Yahoo!’s shareholders also stand to lose heavily. Shareholders may not take kindly to a boss who has turned down a fair offer for the company—although Microsoft may yet return to the fray and bid for Yahoo! at a later date. Amid all the dissatisfaction that the fight did not reach a conclusion one winner stands out. Google still has no worthy competitor to challenge for its title as heavyweight champion of the internet.

Pursuing the Next Level of Artificial Intelligence

Jim Wilson/The New York Times

Daphne Koller’s award-winning work in artificial intelligence has had commercial impact.

By JOHN MARKOFF

Published: May 3, 2008

PALO ALTO, Calif. — Like a good gambler, Daphne Koller, a researcher at Stanford whose work has led to advances in artificial intelligence, sees the world as a web of probabilities.

There is, however, nothing uncertain about her impact.

A mathematical theoretician, she has made contributions in areas like robotics and biology. Her biggest accomplishment — and at age 39, she is expected to make more — is creating a set of computational tools for artificial intelligence that can be used by scientists and engineers to do things like predict traffic jams, improve machine vision and understand the way cancer spreads.

Ms. Koller’s work, building on an 18th-century theorem about probability, has already had an important commercial impact, and her colleagues say that will grow in the coming decade. Her techniques have been used to improve computer vision systems and in understanding natural language, and in the future they are expected to lead to an improved generation of Web search.

“She’s on the bleeding edge of the leading edge,” said Gary Bradski, a machine vision researcher at Willow Garage, a robotics start-up firm in Menlo Park, Calif.

Ms. Koller was honored last week with a new computer sciences award sponsored by the Association for Computing Machinery and the Infosys Foundation, the philanthropic arm of the Indian computer services firm Infosys.

The award to Ms. Koller, with a prize of $150,000, is viewed by scientists and industry executives as validating her research, which has helped transform artificial intelligence from science fiction and speculation into an engineering discipline that is creating an array of intelligent machines and systems. It is not the first such recognition; in 2004, Ms. Koller received a $500,000 MacArthur Fellowship.

Ms. Koller is part of a revival of interest in artificial intelligence. After three decades of disappointments, artificial intelligence researchers are making progress. Recent developments made possible spam filters, Microsoft’s new ClearFlow traffic maps and the driverless robotic cars that Stanford teams have built for competitions sponsored by the Defense Advanced Research Projects Agency.

Since arriving at Stanford as a professor in 1995, Ms. Koller has led a group of researchers who have reinvented the discipline of artificial intelligence. Pioneered during the 1960s, the field was originally dominated by efforts to build reasoning systems from logic and rules. Judea Pearl, a computer scientist at the University of California, Los Angeles, had a decade earlier advanced statistical techniques that relied on repeated measurements of real-world phenomena.

Called the Bayesian approach, it centers on a formula for updating the probabilities of events based on repeated observations. The Bayes rule, named for the 18th-century mathematician Thomas Bayes, describes how to transform a current assumption about an event into a revised, more accurate assumption after observing further evidence.

Ms. Koller has led research that has greatly increased the scope of existing Bayesian-related software. “When I started in the mid- to late 1980s, there was a sense that numbers didn’t belong in A.I.,” she said in a recent interview. “People didn’t think in numbers, so why should computers use numbers?”

Ms. Koller is beginning to apply her algorithms more generally to help scientists discern patterns in vast collections of data.

“The world is noisy and messy,” Ms. Koller said. “You need to deal with the noise and uncertainty.”

That philosophy has led her to do research in game theory and artificial intelligence, and more recently in molecular biology.

Her tools led to a new type of cancer gene map based on examining the behavior of a large number of genes that are active in a variety of tumors. From the research, scientists were able to develop a new explanation of how breast tumors spread into bone.

One potentially promising area to apply Ms. Koller’s theoretical work will be the emerging field of information extraction, which could be applied to Web searches. Web pages would be read by software systems that could organize the information and effectively understand unstructured text.

“Daphne is one of the most passionate researchers in the A.I. community,” said Eric Horvitz, a Microsoft researcher and president of the Association for the Advancement of Artificial Intelligence. “After being immersed for a few years with the computational challenges of decoding regulatory genomics, she confided her excitement to me, saying something like, ‘I think I’ve become a biologist — I mean a real biologist — and it’s fabulous.’ ”

To that end, Ms. Koller is spending a sabbatical doing research with biologists at the University of California, San Francisco. Because biology is increasingly computational, her expertise is vital in gaining deeper understanding of cellular processes.

Ms. Koller grew up in an academic family in Israel, the daughter of a botanist and an English professor. While her father spent a year at Stanford in 1981 when she was 12, she began programming on a Radio Shack PC that she shared with another student.

When her family returned to Israel the next year, she told her father, the botanist, that she was bored with high school and wanted to pursue something more stimulating in college. After half a year, she persuaded him to let her enter Hebrew University, where she studied computer science and mathematics.

By 17, she was teaching a database course at the university. The next year she received her master’s degree and then joined the Israeli Army before coming to the United States to study for a Ph.D. at Stanford.

She didn’t spend her time looking at a computer monitor. “I find it distressing that the view of the field is that you sit in your office by yourself surrounded by old pizza boxes and cans of Coke, hacking away at the bowels of the Windows operating system,” she said. “I spend most of my time thinking about things like how does a cell work or how do we understand images in the world around us?”

In recent years, many of her graduate students have gone to work at Google. However she tries to persuade undergraduates to stay in academia and not rush off to become software engineers at start-up companies.

She acknowledges that the allure of Silicon Valley riches can be seductive. “My husband still berates me for not having jumped on the Google bandwagon at the beginning,” she said. Still, she insists she does not regret her decision to stay in academia. “I like the freedom to explore the things I care about,” she said.

Larry Page on how to change the world

Breakthrough ideas are around the corner, says the Google co-founder. But most of us are failing to take a chance on them.

By Andy Serwer, managing editor

(Fortune Magazine) -- As president of Google, Larry Page has pushed his people to take risks that have led to hot new applications like Gmail and Google Maps. Lately he has been thinking far outside the walls of his company. Page sees a world of opportunity - in areas ranging from energy to safer cars. But he also sees a world of timidity; not enough people, he worries, are willing to place the big bets that could make a difference in meeting humanity's biggest challenges.

In these edited excerpts from an interview with Fortune managing editor Andy Serwer at Google's (GOOG, Fortune 500) headquarters in Mountain View, Calif., Page offers his views on innovation, change, fear - and why he is, all things considered, an optimist.

What are you thinking about these days?

If you ask an economist what's driven economic growth, it's been major advances in things that mattered - the mechanization of farming, mass manufacturing, things like that. The problem is, our society is not organized around doing that. People are not working on things that could have that kind of influence. We forget that it really does matter that we don't have to carry our water; it's not that much fun to walk miles and miles to try to find water and then carry it back under human power. And our ability to generate clean, accessible water is based on basic technologies: Do we have energy? Can we make things? My argument is that people aren't thinking that way.

Instead, it's sort of like "We are captives of the world, and whatever happens, happens." That's not the case at all. It really matters whether people are working on generating clean energy or improving transportation or making the Internet work better and all those things. And small groups of people can have a really huge impact.

How can we increase the number of people doing such work?

There are a number of barriers in place. Let me give an example. In our first founders' letter in 2004, we talked about the risk profile with respect to doing new innovations. We said we would do some things that would have only a 10% chance of making $1 billion over the long term. But we don't put many people on those things; 90% work on everything else. So that's not a big risk. And if you look at where many of our new features come from, it's from these riskier investments.

Even when we started Google, we thought, "Oh, we might fail," and we almost didn't do it. The reason we started is that Stanford said, "You guys can come back and finish your Ph.D.s if you don't succeed." Probably that one decision caused Google to be created. It's not clear we would have done it otherwise. We had all this internal risk we had just invented. It's not that we were going to starve or not get jobs or not have a good life or whatever, but you have this fear of failing and of doing something new, which is very natural. In order to do stuff that matters, you need to overcome that.

Are there mechanisms that society, government, or companies can put into place?

Absolutely - look at Silicon Valley, which has been the premier place in the world to do things like that. There's been a lot of money available and a lot of people encouraging other people to take risks. I don't know that we would have done it had we been in a different environment.

On the one hand you're saying it's a problem. On the other, you're saying it's being done.

I don't think it's black-and-white like that. The question is, How many people are working on things that can move the needle on the economy or on people's quality of life? Look, 40,000 people a year are killed in the U.S. in auto accidents. Who's going to make that number zero or very, very small? There are people working on it.

What are they doing?

Working on making cars automated. You can already see the technology going into some cars. Infiniti just released a car that will kick you back in if you are driving out of the lane, which is a large source of accidents. So you're saving lives, and the technology is not that costly. But the number of people willing to work on stuff like that is very, very, very small.

Why is that?

Honestly, I'm a little baffled. But my own experience within Google is that it's hard to get people to work on those kinds of things because of the personal risk they feel they're taking. Also, people don't have the right training. If you say you want to automate cars and save people's lives, the skills you need for that aren't taught in any particular discipline. I know - I was interested in working on automating cars when I was a Ph.D. student in 1995.

Is the problem that people are risk-averse?

That's part of the problem, but I think that can be overcome with education and environment and infrastructure. My experience is that when people are trying to do ambitious things, they're all worried about failing when they start. But all sorts of interesting things spin out that are of huge economic value. Also, in these kinds of projects, you get to work with the best people and have a very interesting time. They're not really taking a risk, but they feel like they are.

As a public company, you have an obligation to shareholders. How does that come into play when you start designating resources to speculative projects?

In practice that's not an issue. I've told the whole company repeatedly I want people to work on artificial intelligence - so we end up with five people working on it. Guess what? That's not a major expense. There's a reason we talk about 70/20/10, where 70% of our resources are spent in our core business and 10% end up in unrelated projects, like energy or whatever. [The other 20% goes to projects adjacent to the core business.] Actually, it's a struggle to get it to even be 10%. People might think we're wasting money or whatever. But that's where all our new stuff has come from.

Isn't this easier to do at a place like Google than, say, at older Fortune 500 companies?

Many leaders of big organizations, I think, don't believe that change is possible. But if you look at history, things do change, and if your business is static, you're likely to have issues. Look at the auto industry: It took the Japanese to convince people you can have a reliable car. Then they started pushing the product cycles shorter and shorter. Instead of making a car in five years, they made them in one year or two years. That's a big change.

And then there are things like Moore's Law [that the number of transistors on a chip will double about every two years]. People think Moore's Law is a description of what happened. But Moore's Law actually caused people to do the right thing. Everyone was organized about it - making things better quickly.

So if there were Moore's Laws applicable to other businesses or products, people would organize to fulfill that point?

Yes, yes. Different things get solved for different reasons. Obviously you're not going to get Moore's Law performance for cars - you're not just moving information around. With cars, you have physical constraints.

Do you have other examples where innovative leadership could move the needle?

I think there are a lot of areas. You can be a bit of a detective and ask, What are the industries where things haven't changed much in 50 years? We've been looking a little at geothermal power. And you start thinking about it, and you say, Well, a couple of miles under this spot or almost any other place in the world, it's pretty darn hot. How hard should it be to dig a really deep hole? We've been drilling for a long time, mostly for oil - and oil's expensive. If you want to move heat around, you need bigger holes. The technology just hasn't been developed for extracting heat. I imagine there's pretty good odds that's possible.

Solar thermal's another area we've been working on; the numbers there are just astounding. In Southern California or Nevada, on a day with an average amount of sun, you can generate 800 megawatts on one square mile. And 800 megawatts is actually a lot. A nuclear plant is about 2,000 megawatts.

The amount of land that's required to power the entire U.S. with electricity is something like 100 miles by 100 miles. So you say, "What do I need to do to generate that power?" You could buy solar cells. The problem is, at today's solar prices you'd need trillions of dollars to generate all the electricity in the U.S. Then you say, "Well, how much do mirrors cost?" And it turns out you can buy pieces of glass and a mirror and you can cover those areas for not that much money. Somehow the world is not doing a good job of making this stuff available. As a society, on the larger questions we have, we're not making reasonable progress.

So you think that geothermal and solar thermal could solve our energy problems?

Yeah, probably either one could generate all the energy we need. There's no discipline to actually do this stuff, and you can also see this vested interest, risk-averse behavior, plus a lack of creativity. It sort of conspires. It's also a timeliness thing; everyone said Sam Walton was crazy to build big stores in small towns. Almost everyone who has had an idea that's somewhat revolutionary or wildly successful was first told they're insane.

Whose obligation is it to make this kind of change happen? Is it Google's? The government's? Stanford's? Kleiner Perkins'?

I think it's everybody who cares about making progress in the world. Let's say there are 10,000 people working on these things. If we make that 100,000, we'll probably get 10 times the progress.

And then you compare it with the number of engineers at Exxon (XOM, Fortune 500) and Chevron (CVX, Fortune 500) and ConocoPhillips (COP, Fortune 500) who are trying to squeeze the last drop of oil out of somewhere, and all the science brainpower that's going to that. It's totally disproportionate to the return that they could get elsewhere.

What kind of background do you think is required to push these kinds of changes?

I think you need an engineering education where you can evaluate the alternatives. For example, are fuel cells a reasonable way to go or not? For that, you need a pretty general engineering and scientific education, which is not traditionally what happens. That's not how I was trained. I was trained as a computer engineer. So I understand how to build computers, how to make software. I've learned on my own a lot of other things. If you look at the people who have high impact, they have pretty general knowledge. They don't have a really narrowly focused education.

You also need some leadership skills. You don't want to be Tesla. He was one of the greatest inventors, but it's a sad, sad story. He couldn't commercialize anything, he could barely fund his own research. You'd want to be more like Edison. If you invent something, that doesn't necessarily help anybody. You've got to actually get it into the world; you've got to produce, make money doing it so you can fund it.

Are you consciously hiring people who can look at these issues?

Those people don't really exist. You can't hire them. People usually have careers where they stay in pretty fixed areas.

Some of the VCs are forced to be a little more general in how they evaluate things, and that's been good. But they still go wrong. Look at VC investment in clean energy. What caused that to happen was two things: the price of oil going up and global warning. It's mostly the price of oil going up.

But think about it. Most of the money is going into companies that will produce electricity - and the price of electricity is based on the price of coal, which hasn't changed. So the question is, Why didn't we do all this investment 10 years ago? That was a huge mistake. It's obviously easier if oil's more expensive, but there's no particularly good reason we didn't do a lot of it sooner.

Are you more or less optimistic about the future than you were three years ago?

I'm hugely more optimistic because now we have a conceptualization of the problems that makes some degree of sense to a fair number of people. Look at the things we worry about - poverty, global warming, people dying in accidents. And look at the things that drive people's basic level of happiness - safety and opportunity for their kids, plus basic things like health and shelter. I think our ability to achieve these things on a large scale for many people in the world is improving.

Jia Lynn Yang contributed to this article.

Math : Google Labs Problems

Math : Google Labs Problems

Author: Marcus Kazmierczak

Created On: July 29th, 2004

A mysterious billboard appeared on 101-southbound which I passed each day to work. The billboard said:

{ the first 10-digit prime in consecutive digits of e }.com

I passed by the billboard numerous times before I realized it wasn't an advertisement for a company, it wasn't touting some servers new ability, it was actually a question. A problem to be solved. As I've shown before I'm always up for a good problem, I got right on it.

Problem #1

My first intrepretation of the problem was to find the first 10-digit prime, the first being 1,000,000,007 and the next being 1,000,000,009 and seeing if they are in e. So I've already created a few primes scripts before but not up to 10-digits, so I modified it a touch and started that cranking out some big primes.

Now as I started to think about it more I realized that this intrepretation doesn't make sense, since it is wholly dependent on the length of e that you are using to check. It's possible you can extend e long enough to have any 10-digit prime show up.

Well, I had left my big prime number generator cranking and it turned out 105 million prime numbers, up to 2.1 billion. This file of consecutive primes ended up being 1 gig! This took about 4-hours on an Opteron 64-bit 2ghz box. Thankfully I wouldn't need it.

So on to the second, and real intrepretation, of the question, take 10-digit chunks of e, starting at the beginning and check if those are prime. This turns out to be a much easier problem.

Now, the largest number it could be is 9,999,999,999, so the largest prime we need to check is the square root of that, which is roughly 100,000. Now the list of primes up to 100,000 is quick and easy to generate. [again previous scripts]

So grabbing the first ~2,500 digits of e, from this site [nasa.gov], I was guessing 2,500 would be enough. I could always go back for more. Moving them onto one line for ease of use I ended up with this file [e.0]

I wrote this script [util_chunkify.py] to chunkify it into 10-digit pieces that are possibly primes, stripping out digits that end with an even number or 5. This left me with the following file [e.10digit.chunks] So I then wrote a script which reads in the primes from this file [primes.sm] and puts them in an array. This is what is used to check if our 10-digit e-chunks are prime, using this script [checke.py]

Here are the first ten, the first one of course is the correct answer:

1. 7427466391
2. 7413596629
3. 6059563073
4. 3490763233
5. 2988075319
6. 1573834187
7. 7021540891
8. 5408914993
9. 6480016847
10. 9920695517

So going to: http://www.7427466391.com/ brings up a second problem.

Problem #2

Here's the second problem:

f(1) = 7182818284
f(2) = 8182845904
f(3) = 8747135266
f(4) = 7427466391
f(5) = ???

First Idea
The first thought was to solve it using a 3rd degree polynomial which will give us an equation which will fit the four points and we can plug in the 5th value, 5, and get the answer. After struggling with Excel, which could graph and forecast the polynomial and even give us an equation it would not give us the forecasted value. dumb. Abandoning Excel, since it's equation wasn't even all that accurate.

Using: a * x^3 + b * x^2 + c * x + d = y Gives us the following 4-equations and 4-unknowns:

1a +	1b +	1c +	d =	7182818284
8a +	4b +	2c +	d =	8182845904
27a +	9b +	3c +	d =	8747135266
64a +	16b +	4c +	d =	7427466391

This solves to:

a =	-241369996.5
b =	1230350850
c =	-1001434954.5
d =	7195272385

Plugging into the above for f(5) = 2775619365

Testing this does not work, but since this section was labeled, First Idea, you should of seen that it would've been wrong.

Second Idea
After giving up the the polynomial fit and looking at the numbers a little more the first number looked very much like the beginning of e. It turns out to be the first segment of e and the other numbers also are all segments of e. They looked like this:

    
2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391
7182818284
 8182845904
                   8747135266
                                                                                               7427466391

The first number mapped to the 2 spot of e, the 2nd number to the 6th spot, the 3rd number to the 24th spot and the 4th number to the 100th spot. This gave me the new functions:

f(1) = 2
f(2) = 6
f(3) = 24
f(4) = 100

Numerous attempts were made to try to figure out a patern here, which turns out to be very close to a factorial series,

f(x) = (x+1)!

but not quite, the 100 would need to be 120. After awhile looking at this it was abandoned and back to the original numbers.

f(1) = 7182818284
f(2) = 8182845904
f(3) = 8747135266
f(4) = 7427466391
f(5) = ???

Trying out various things on them, the following turned up which seemed a little too coincendental to be a coincendence:

7+1+8+2+8+1+8+2+8+4 = 49
8+1+8+2+8+4+5+9+0+4 = 49
8+7+4+7+1+3+5+2+6+6 = 49
7+4+2+7+4+6+6+3+9+1 = 49

So a quick script [sum_checke.py] to check if these are the first 4 values of 10-digit chunks of e that sum to 49, which they turned out to be. The script turned up:

1. 7182818284
2. 8182845904
3. 8747135266
4. 7427466391
5. 5966290435
6. 2952605956
7. 0753907774
8. 0777449920
9. 3069697720
10. 1252389784

The 5th one being the correct answer.

Folllowing the directions, it turned out to be a recruitment tool for Google Labs, looking for the best and brightest. It was pretty fun and good idea for them. Unfortunately, their search engine is too good and anyone can look up answers to them, so I'm not sure how valid of a test it is. I did send them the link to my resume, encoded of course.

Calculating e

I felt like it was cheating downloading some one else's calculated digits of e. So using the formula:

e = 1/0! + 1/1! + 1/2! + 1/3! + 1/4! + ... 1/N!

I wrote the following script, calc_e.py to calculate the digits of e, the script uses the GMP libraries for precision.

May/June 2008

An Electrifying Startup

A new lithium-ion battery from A123 Systems could help electric cars and hybrids come to dominate the roads.

By Kevin Bullis

It is the quickest electric motorcycle in the world. On a popular YouTube video, the black dragster cycle nearly disappears in a cloud of smoke as the driver does a "burn-out," spinning the back wheel to heat it up. As the smoke drifts away, the driver settles into position and hits a switch, and the bike surges forward, accelerating to 60 miles per hour in less than a second. Seven seconds later it crosses the quarter-mile mark at 168 miles per hour--quick enough to compete with gas-powered dragsters.

What powers the "Killacycle" is a novel lithium-ion battery developed by A123 Systems, a startup in Watertown, MA--one of a handful of companies working on similar technology. The company's batteries store more than twice as much energy as nickel-metal hydride batteries, the type used in today's hybrid cars, while delivering the bursts of power necessary for high performance. A radically modified version of the lithium-ion batteries used in portable electronics, the technology could jump-start the long-sputtering electric-vehicle market, which today represents a tiny fraction of 1 percent of vehicle sales in the United States. A123's batteries in particular have attracted the interest of General Motors, which is testing them as a way to power the Volt, an electric car with a gasoline generator; the vehicle is expected to go into mass production as early as 2010.

Side Impact: A battery designed by A123 Systems for GM’s Volt electric vehicle can survive a crushing safety test. The high-velocity impact could have caused other lithium-ion batteries to overheat and catch fire. Credit: Porter Gifford

Multimedia • Learn how different kinds of hybrids work using this interactive primer. Yet-Ming Chiang discusses his new lithium-ion battery electrode.

Reporter's Notebook: Kevin Bullis

In the past, automakers have blamed electric vehicles' poor sales on their lead-acid or nickel-metal hydride batteries, which were so heavy that they limited the vehicles' range and so bulky that they took up trunk space. While conventional lithium-ion batteries are much lighter and more compact, they're not cost effective for electric vehicles. That's partly because they use lithium cobalt oxide electrodes, which can be unstable: batteries based on them wear out after a couple of years and can burst into flame if punctured, crushed, overcharged, or overheated. Some auto­makers have tried to engineer their way around these problems, but the results have been expensive.

A123's batteries could finally make lithium-ion technology practical for the auto industry. Instead of cobalt oxide, they use an electrode material made from nanoparticles of lithium iron phosphate modified with trace metals. The resulting batteries are unlikely to catch fire, even if crushed in an accident. They are also much hardier than conventional lithium-ion batteries: A123 predicts that they will last longer than the typical lifetime of a car.

The battery's promise has made A123 one of the best-funded technology startups in the country, with $148 million in venture capital investments so far. With the funding, A123 has been pursuing an ambitious business plan that calls for it to do everything from perfecting the material to manufacturing batteries and selling them to customers in the auto and power-tool industries.

The A123 batteries for GM's Volt store enough energy for 40 miles of driving, enough to cover daily commutes. (On longer trips, the small gasoline engine would kick in to recharge the battery, extending the range to more than 400 miles.) GM plans to sell the vehicles for around $30,000 to $35,000; the company thinks it can sell hundreds of thousands at that price in the first several years, and J. D. Power and Associates estimates that GM will sell nearly 300,000 by 2014.

Materials Matter
In early 2001, a 26-year-old Venezuelan entrepreneur named Ric Fulop walked into the office of Yet-Ming Chiang, a professor of materials science at MIT, without an appointment. "He just showed up and knocked on the door," recalls Chiang. Fulop, who had already founded three venture­-backed companies, wanted help starting a battery company, and he knew that Chiang was conducting battery research involving nanotechnology. Chiang himself had cofounded a successful startup in the late 1980s, but he spent most of his time researching nanotechnology and the chemistry of advanced ceramics.

By the fall, Fulop and Chiang, along with Bart Riley, an engineer Chiang knew from his previous venture, had cofounded A123 Systems. The plan was to commercialize one of Chiang's more radical ideas: materials that, when stirred together, would spontaneously assemble to form a working battery. The process promised to multiply energy storage capacity while lowering manufacturing costs.

Chiang's big idea turned out to be a hit with investors. By the end of 2001, a first round of funding had brought in $8.3 million from various venture capital firms. Motorola and Qualcomm, intrigued by the prospect of better batteries for portable electronics, soon added $4 million. But it quickly became clear that a commercial self-assembling battery was years away from reality. The technology "was still pretty rudimentary," Chiang says.

In early 2002, however, Chiang made a surprising discovery that would completely change the company's direction. He had begun to work with lithium iron phosphate, which is nontoxic, safe, and inexpensive, unlike the materials used in other lithium-ion batteries. But it appeared to have some serious drawbacks. It stores less energy than lithium cobalt oxide, the electrode material in conventional lithium-ion batteries, so it seemed unsuitable for use in portable electronics, where energy storage is paramount. Also, it charges and discharges slowly, ruling out its use in high-power applications such as hybrid electric vehicles; even for fully electric cars, which use many more battery cells than hybrids, the material couldn't deliver enough power.

So Chiang started to modify it by adding trace amounts of metals. Soon the material was discharging power at relatively high rates. In mid-2002, he flew to Monterey, CA, to present his findings at a conference. While he was there, a graduate student back at MIT continued running tests. By the time ­Chiang was scheduled to talk, the material was performing at rates four times those he had come to announce. "At that point, we knew we had something special," he says.

Eventually, Chiang would demonstrate that the material could deliver bursts of electricity at 10 times the rate of those used in conventional lithium-ion batteries. After studying the high-­performing material in detail, he determined that it owed its power both to the size of the particles he'd used (less than 100 nanometers) and to the addition of the extra metals. The combination of those factors, he says, causes a fundamental difference in the way the atoms that make up the material rearrange themselves when they receive and release a charge.

Packed Up: A123’s battery cells (above) have been integrated into a T-shaped pack engineered by the German firm Continental. Credit: Porter Gifford

In all lithium-ion batteries, electricity is generated when lithium ions shuttle between two electrodes while electrons travel through an external circuit. In Chiang's early experiments with lithium iron phosphate, the parts of the material that contained lithium would separate from those that didn't as the lithium ions moved in and out of an electrode. That changed the crystalline structure of the material, and its performance deteriorated. But, ­Chiang discovered, when the particles of lithium iron phosphate are small enough--and the electrode has been modified, or "doped," through the addition of other metals--the material's crystalline structure changes far less. As a result, the lithium ions can move in and out faster, without degrading the material. Altogether, Chiang found that the modified material charged and discharged faster than ordinary lithium iron phosphate, and it lasted longer, too.

Extraordinary though the new battery material seemed to be, ­Chiang realized immediately that it wasn't ideal for portable electronics. There didn't seem to be a ready market for light, compact batteries that delivered large bursts of power. Hybrid vehicles, a natural fit, were only beginning to appear on the market. What Chiang didn't know was that a major power-tool company was working quietly on a new generation of cordless tools, and it was having trouble finding a battery that would meet its needs.

Powerful Start
In 2003, representatives of Black and Decker met with Fulop and A123's CEO, Dave Vieau, and told them that they wanted to make cordless power tools that would perform better than tools plugged in to the wall. A123's material seemed like a perfect fit. In short bursts, it can deliver more power than a household circuit. And it had other features that would be attractive on a construction site. It could be recharged quickly (to 80 percent of capacity in 12 minutes or less), and unlike batteries made with lithium cobalt oxide, it could survive harsh treatment without catching fire.

That, at least, was the theory. When Fulop and Vieau first met with Black and Decker, they had only a model of a battery cell, half a gram of material, and a PowerPoint presentation. What Black and Decker needed was a company that could produce millions of batteries. "There was a lot of emphasis on the material, but what we had to learn how to do is to engineer the complete cell," Chiang says.

Within a year of signing its initial agreement with Black and Decker, however, A123 had produced a commercially feasible battery. By November 2005, its first products were coming off assembly lines in Asia. In less than three years, the company went from building a demonstration battery the size of a coin to building 50-meter-long coating machines and 28,000-square-meter factories run by hundreds of employees. By 2006, customers were buying its batteries in a new line of professional tools sold by Black and Decker. In short order, A123 was manufacturing batteries at the rate of millions a year.

German built: The T-shaped pack (above) holds A123's battery cells. GM is testing the pack under simulated driving conditions before bolting it into an electric-vehicle prototype.
Credit: Courtesy of General Motors

Charging Up Cars
Meanwhile, GM was rethinking its technology strategy as Toyota began to dominate the hybrid-vehicle business. A hybrid uses a battery only part of the time, relying on a gasoline engine for much of its power. GM decided to develop a car that would allow its customers to stop using gasoline entirely for most daily driving. But to pull it off, the automaker needed a high-performance, reliable battery. And for that it turned to A123.

GM knew that it wanted to use lithium-ion batteries because of their storage capacity, says Denise Gray, GM's director of energy storage systems. But it also knew that existing technology wouldn't do the trick. Though a lithium-ion laptop battery might survive 500 complete charge-and-discharge cycles before its capacity fades, no car owner wants to buy a new battery every 18 months. According to A123's projections, however, its batteries should be able to deliver more than 15 years' worth of daily charges. And in addition to being safer than other lithium-ion batteries, A123's operate at a lower temperature, which makes it simpler to pack hundreds of them together into a large battery pack, Gray says.

Where A123's power-tool batteries are cylindrical, the battery it developed for the Volt is flat, to save space and more efficiently dissipate heat. The cells have been assembled into complete battery packs, which are T-shaped and nearly two meters long. This spring, the batteries will be bolted into vehicle prototypes for road testing. And later this year, A123 plans to increase production of the batteries to meet anticipated demand. The first cars powered by A123 technology could be rolling off assembly lines in 2010. (GM is also testing batteries from another company, and may use batteries from either or both companies.)

If the Volt is popular, electric cars could finally start to take off--and that could reduce greenhouse-gas emissions and petroleum consumption. A recent study by the Electric Power Research Institute and the Natural Resources Defense Council suggests that electric vehicles similar to GM's car could eliminate billions of tons of greenhouse-gas emissions between 2010 and 2050. A study by General Electric indicates that if half the vehicles on the road in 2030 are electric-powered, petroleum consumption in the United States will shrink by six million barrels a day.

And batteries like A123's could have repercussions far beyond the Volt. Even cars with internal-combustion engines are being engineered to rely more on electricity: the simplest examples involve batteries recharged by souped-up alternators that would allow a car to shut off its engine when it approaches a stoplight and restart when the driver hits the accelerator. In conventional hybrids, versions of A123's batteries can deliver as much power as nickel-metal hydride batteries at one-fifth the weight. The new batteries could also benefit plug-in hybrids, which can be recharged from a standard electrical outlet. Indeed, A123's batteries may be used in a plug-in version of the Saturn Vue hybrid SUV that's due out in 2010.

Whatever their design, future cars will be likely to rely much more on electricity. "We're not there yet," Chiang says. "There aren't Volts all over the place. But the potential to have a big impact, both on the oil supply issue and greenhouse gases--I didn't imagine that we'd be able to do that. Certainly not when I started working on batteries."

Kevin Bullis is TR's Nanotechnology and Materials science Editor.