Security, Part 1

As much as we'd like it to be true, security is not all about ciphers; it's also about physical security, the human factor, and an often overlooked area called side channels.

Physical Security

We all know that you need a password to keep a computer secure, right? But what happens when the hard drive is stolen? Your data can walk right out the door, that's what!

But even the transmission of secret keys and plain text is an issue. For instance, a keystroke logging program can easily intercept all the passwords you type. So you want to make sure that such a program never gets onto your computer.

With some cipher text, the more you get of it the easier it is to decode it. While this usually describes not-so-good security, things like feedback shift register xor cipher techniques are still employed in stream ciphers. To combat this, the feedback shift register must be re-initialized periodically to prevent the code from being broken. This is usually done by using a more secure encryption technique, like an RSA public-key cryptosystem.

But the best thing would be to make the transmission un-interceptable. This leads to the use of quantum key cryptography.

The Human Factor

The mobile computing revolution didn't invent the need for accessing your data externally, but it did make it a lot more common. So we use passwords to protect our data.

Passwords are secret keys that are possible to remember. But humans are frail and forgetful and so often they use passwords that are easy to guess. Ones they can't forget. Like 12345. I talk about just how insecure these kinds of passwords are in my first post on hackers.

But humans are always doing dumb, insecure things, like leaving doors unlocked or ajar, leaving a key under the flower pot, or leaving the keys to the car behind the visor. This kind of behavior happens out of force of habit to some people and represents a massive security breach.

But the most powerful kinds of attacks are called social engineering attacks.

Side Channels

This is the most interesting kind of insecurity, because it really describes an indirect attack.

One side channel is comprised of signals emanating from a device like an LCD screen. The video signals are generally leaked out and can be intercepted and reconstructed for spying on the device. For CRTs, a fellow named Wim Van Eck demonstrated in 1985 that he could display on a TV monitor the contents of a CRT screen, captured from hundreds of meters away, just by tuning into the video frequency emanations. The technique, known as Van Eck phreaking, can work on any display hardware.

When it comes to radio frequency (RF) emanations, a standard, known as TEMPEST since the 1960s, covers the techniques and methods used in shielding devices and components from being surveilled in this way.

Simple things like wi-fi are easily broken into, in a process called wardriving. There are published approaches for how to crack WEP and other security protocols used in wi-fi. But other methods can also be used to gain the password. Once the wi-fi is accessed, then anything transported on the wi-fi is also accessible. Google got in trouble for accessing wi-fi from their street view vehicles, but the fact is it is too easy to collect data in this manner. Thus, the mobile computing revolution introduces a whole new set of insecurities.

Another side channel concerned cryptography and this one is a doozy: just by observing the process that is encrypting or decrypting some data, you can infer information about, for instance, the size of the prime numbers used in an RSA public-key cryptosystem. If you can tell how long it takes to divide the public key by a secret key, you can infer some valuable information about the size and bitwise complexity of the secret key. If, when producing a prime number pair, you can determine how long it took to produce it, you can tell a bit about the algorithm used to produce them. Each bit of information is useful in chopping away at the space of all possible answers to the question of what the secret is.

The data you observe about the cryptography process can be power consumption, the timing, or really anything that can be measured externally. With a power consumption curve, you can do differential analysis to get really precise information about how big the multiply was, and even which parts of the multiply are more complicated than others.

And you can also measure thermal and acoustic signatures as well. For instance, by focusing an infrared camera at a chip during a certain computation, you can determine which parts of the chip are active and at what times.

Hackers, Part 6: Methods of Entry

I have often wondered how hackers gain control of your system when you are just browsing the web. It's actually an interesting process, and knowing about it can help you be aware of the threats.

Through the rabbit hole

In order to understand what's happening when you get infected by a virus or another sort of malware, it seems a bit like going through the rabbit hole. This is because computer programming can be a bit of a dark corridor to the average person. Perhaps it's a place they don't usually go.

Have you heard of compromised websites? Well, I was surprised to know that almost any website can be compromised through a number of techniques. The main thing needed is for the website to contain a link that directs you to another website. This can easily be done, for instance in an ad. But HTML code often contains SQL code in it, when a database access is done. This kind of code is susceptible to SQL injection exploits. Perhaps the hacker gains access to the website's administration via a cracked password or some other mistake in configuration.

When you visit a compromised website, you don't really notice the intrusion. Actually it's supposed to be that way. They want to catch you unaware. So you will probably just see the website's normal content. But somewhere in the HTML stream, a malicious URL is included. This is what directs you to another website.

Wait: if it directs you to another website, then you should see your browser loading another page, right? No. Pointing you off to that website does not necessarily mean loading a page from that website. So you may not even notice anything at all. It can mean merely accessing a file at a specific URL in that website. But even accessing a single file can call for HTML code to be executed. Yes, before the file is loaded, special HTML code that verifies which kind of computer you are running and which OS version you are running gets executed first. This makes sure you are an intended victim: one with the vulnerability in question that is being exploited. And then a file is accessed, and loaded.

And Flash files are the most common kind of file that are chosen.

Flash: what's happning there?

The file being loaded is specially crafted to make use of a buffer overrun or another specific security hole in Flash Player. This is the kind of fault that seems to get patched nearly every month by Adobe. A recent update is a priority 1 (critical) security flaw, initially reported by MITRE. Apparently it's quite a problem. When logging into yahoo a while ago, I was prevented from doing so until I installed the most recent version of Flash Player.

However it happens, once you load this Flash file, the inevitable process of being infected with a virus has begun.

Eventually, an unsuspecting Windows XP user ends up downloading an EXE file which gets run and the virus is now installed.

When examining the SWF Flash files, it becomes clear that hackers like to obfuscate their code internally, usually by XORing parts of it with an 8-bit key. This renders plaintext unreadable to the casual observer. Or to anti-virus code that scans for dangerous items.

Steve Jobs, in April of 2010, noted that Adobe Flash Player was the number one reason for Macs crashing. Why is this?

One reason is that Flash allows code to be embedded into an animation file that gets run locally in your Flash cache folder. So just loading an animation file can cause actual code to be run! This code can be malware, of course. It can even be encrypted so it can't be detected by virus scanning software. And that presumes that the virus-scanning software even gets a look at that file.

Ah, but is this still true? Not exactly. Adobe has implemented a Protected View sandbox that prevents malware from being executed. But, as the recent security patch indicates, the wrinkles in this approach are still being ironed out. Still, it represents some progress.

It is well-documented that, in 2010, security experts denounced Flash.

And nearly every computer has it installed. So Adobe has had a lot to lose.

Adobe has updated Flash once again a few days ago, plugging memory leaks that get exploited so malware can insert their own code.

Building secure software

But, treating security flaws like a perception problem is really at the flawed center of a public relations way of dealing with security. Sandboxing approaches, internal file fuzzing, and white-box texting are the proper ways of dealing with such issues. Also, it is possible to hire a tiger team of professionals whose job it is to break the software in question and use it to compromise test websites. In other words, be the hacker. A regimen of code review is useful as well. Some would say absolutely necessary, particularly close to a release, when it is impossible for QA people to properly assess the security of the software. It is also necessary to have the latest in compilers as well. This means having a compiler that rigorously and continuously performs deep semantic analysis: tests for logical flaws that can lead to insecurities such as buffer overruns, enumerates and discovers cases that weren't handled, spots unlikely code scenarios, and so forth. People who program make mistakes all the time. It is unconscionable (and just plain stupid) to use a compiler that does not perform as many checks as possible.

When management doesn't embrace the methods of building secure software, then the users are the ones that lose. This is because the software's insecurities cause the users to be compromised. And then the software manufacturer loses as well. Because users won't buy it. These days, word spreads pretty fast about insecurity. It's all over the news. So, even in the case of Flash, where it is a significant part of the workflow of the web, this problem can lead to market share slippage and eventual replacement by transparent standard technologies, like HTML5.

For many years, Adobe treated the problem like a public relations problem. I speculate that is because they were concerned merely with getting releases out and reaping the revenue. In other words managers were concerned with making the quarterly revenue. Not with the future viability of their product.

Those who use secure software methodologies can see the forest for the trees. They know that sustainability is important. Perhaps the page has turned at Adobe.

Back to public relations. How should public relations work when dealing with perceptions of security failures? It's hopeless unless the company they are representing takes a proactive stance in preventing attacks to their security. When the hackers laugh at your security, you are going to be a big target, because the word will spread through the hacker community that you are a low-hanging fruit. Ripe for the picking. You get it.

Seven

After my post on five-fold symmetry, I can hardly keep myself from writing about seven. It seems unlikely, but the number seven does have some surprising properties, which I will illustrate. For instance, despite being called an octave, the diatonic musical scale really consists of seven notes: C, D, E, F, G, A, and B. With a remarkable sense of synesthesia, some people like to think each note has a color to it. I have folded my concept of the colors of notes into a paper aperture for your amusement.

Musicians like Alexander Scriabin developed systems to assign colors to key signatures based on the circle of fifths. The famous Hungarian composer and piano virtuoso, Franz Liszt, had a famous quarrel with Russian composer Nikolai Rimsky-Korsakov about the colors of the various key signatures; they saw them quite differently.

Seven is an odd prime number. Because it divides evenly into 1001 (and 1001*999 is one less than one million) its reciprocal has a six-digit repeat block, and thus seven the first number to have a repeat block that has length equal to the number minus one. It is a noble prime.

999999 = 3*3*3*7*11*13*37

Note that 7 and 13 have six-digit reciprocals, but 7 is often associated with good luck and 13 is often associated with bad luck.

An odd, prime number like 7 would seem to be impossibly irregular until you try to lay out seven pennies upon the table, as I did when I was five or so. I was surprised that it made the most elegant, regular arrangement possible.

And the seven pennies introduced young me to hexagonal packing. You can see that seven hexagons can make a hexagonal cluster. This is because it is a hexagonal number. The numbers 1, 7, 19, 37, ... , expressed as

1 + 6*T(n)

(where T(n) is the nth triangular number), are called hexagonal numbers because they give the exact number of smaller hexagons that can be put together to form a larger hexagon.

The clusters themselves can be fitted together. into an elegant offset packing, here shown using my Tile Patterns application. And a little help from Painter.

When I constructed this tiling, I had to work it out by hand first before I could enter it properly into Tile Patterns.

Here is my sketch of this tiling, giving some indication of the way I wanted to see it. Perhaps if we had hexagonally-packed eyes like the honeybee, and saw everything in these patterns, we would make our homes like they make their honeycombs.

It is only because my eyes are not hexagonally packed, I know, that I couldn't quite get the proportions right.

The green dashed parallelogram shows the repeat block of the offset tile pattern. It is because I like to think in squares and cubes that I can see it.

Seven is an interesting number for cubes as well, because it is one less than the cube of two.

Here I have illustrated that concept for you. It's always easier to see it visually than to just read it, I think.

Put one cube in the missing corner and you can make a 2x2x2 block. Two cubed is eight. So this shows seven cubes. Plus, I like a good graphic!

When it comes to seven, we do spend a bit of time dancing around six and eight.

The first diagram I showed was a folded paper aperture with seven sides. Its outline is a seven-sided regular polygon, called a heptagon.

Connect the corners of a heptagon and you can make various forms of seven-pointed stars.

Many countries use five-, six-, seven-, and eight-pointed stars as their symbols. Normally there are the wide star and the thin star. The Sheriff's Badge symbol uses a seven-pointed star that's somewhere in-between the two.

Other than these I don't really know other ways that the seven-pointed star gets used. This illustration I have created is a mandala form. I have applied a little color so you can see the various shapes better.

Seven dots on a grid can be situated in several different ways. But if you look at seven as two times four minus one, then you can see how a corner of one square may be shared with the corner of another square.

Each number is unique and interesting. In music, there is more to seven than just the diatonic scale. There is also music that features seven beats per measure, like Money by Pink Floyd, Solsbury Hill by Peter Gabriel, and the final Precipitato from Prokofiev's Piano Sonata No. 7 in B-flat. When I get in a mood, I will use this time signature. Usually it is broken up into two-two-three.

Finally, did you know that graph theory is based upon Leonhard Euler's solution to the problem of the Seven Bridges of Königsberg? Walk through the city, crossing each of the seven bridges exactly once. Once again the number seven provokes thought. Euler abstracted the two sides of the river and the two islands into four nodes and the bridges were thus abstracted into the seven arcs between them. The number of arcs attached to each node is called the degree of the node. If a node has even degree, then any path can enter and leave the node in an equal pairing. But if a node has an odd degree, then either the path must start or end there. It is easy to see that if more then two nodes have odd degree it is impossible for a single path to traverse all nodes, using the arcs between them. This is because a path must have only two endpoints. Königsberg's graph has four nodes of odd degree. Thus no such walk can exist.

So the number seven was actually the doorway to graph theory in the eighteenth century!

Five-Fold Symmetry

Nature is replete with five-fold symmetry, thanks to five-petaled flowers. While most of the works of humankind are designed around 4-fold symmetry and the cube, we have always been interested in five-fold symmetry as well. It's just that it doesn't always work as well as four-fold symmetry.

Our obsession with the number five clearly comes from our own hands, since we have five fingers on each hand. Our expression of the interest with the number five comes in several forms, though. My favorite is the five-pointed star.

Knowledge of the dodecahedron, a platonic solid bounded by regular pentagons, was actually kept secret in the school of Pythagoras. They believed that the general populace was simply not ready for it.

The US military uses five-pointed stars to denote the highest ranks: admirals, generals, and commandants. The five-star symbol was created during World War II for Eisenhower and Nimitz.

I read once where a draftsman invented the symbol for the US Government. But I haven't been able to find this information since. His designs were very interesting, to say the least.

The military loves the pentagon as well, as evidenced by their construction of one of the world's largest buildings: the Pentagon. It is remarkable that General Leslie Groves oversaw its construction. Earlier, he was put in charge of the Manhattan Project. So he was also in charge of the construction of another of the world's largest buildings, at Oak Ridge, Tennessee, used for the processing of Uranium.

Nature likes five-fold symmetry in part because five is a Fibonacci number and nature favors them. When I was a kid, I used to read the Fibonacci Quarterly religiously. I was like that.

It is notable that most music is rooted to four beats per measure. Sometimes, as in a waltz, we use three or six beats per measure. But five (or ten) beats per measure is exceptionally rare, except in Jazz. The Dave Brubeck Quartet made this famous in their rendition of Take Five. You can also hear this uncommon beat in the catchy original Mission Impossible theme, written by Lalo Schifrin (where ten beats is broken into two 3s and two 2s).

For me, it is fun to see the way that pentagons, stars, and the rhomboids interact. You can make a rhombus with 72 and 108 degree angles. This is the one used to create the rhombic dodecahedron.

Put stars and pentagons together and they make an irregular tiling of the plane. The designs at Alhambra in Spain are great examples of the attempt to make a regular tiling from five-fold symmetry. But, if you only use pentagons, it really can't be done.

Here is a basic chart of how they fit together. The rhomboids trim out the design. Roger Penrose has constructed aperiodic tilings out of rhombuses, including the one I show here and also a sharper one with 36 degree angles in it. The golden section (1.6180334...) figures in all the shapes in one way or another. Quasicrystals can be made of these designs.

Try to put pentagons together and you will have little luck in creating a seamless gapless tiling.

Here I have succeeded in putting some together using a star as a root and some crowns to glue them together!

The problem with the tilings stems from the angle of a pentagon: 108 degrees. The wide rhombus has an acute angle of 72 degrees, the complement of 108 degrees. The sharp point of the star is 36 degrees. So this means you get some other obtuse angles in there are well: 144 degrees for the thin rhombus.

A ten-sided regular polygon has outside angles of 144 degrees, the complement of 36 degrees. You can put a crown, three pentagons, and two thin rhombuses together and make a ten-sided polygon.

This construction is often used in Penrose and Kepler tilings. Two such decagons can join and use a common thin rhombus.

As I said before, the problem is that the primary angle, 108 degrees, does not evenly divide 360 degrees and so there must be some left over. After putting three pentagons together, exactly 36 degrees are left over.

So you must also have a star, a thin rhombus, or a crown to make pentagons tile the plane properly. If you distort the pentagon, however, you can solve the problem entirely.

Here is the common way of doing this. It is a novel pattern, for sure! Notice the squat hexagons that intersect each other in perpendicular patterns.

This pattern has been used to create concrete tilings in real life! It's cool that tiling patterns have real-world uses. Of course they occur in crystals all the time and so patterns are automatically embedded in the real world all around us.

It is worthwhile to peruse the images of Alexander Braun, an explorer of pentagonal tiling.

Asteroids! The Not-So-Game.

Most of us noticed that a significant meteorite exploded and impacted near Chelyabinsk a few days ago. And also in the news is that asteroid DA14 flew by earth at a surface-to-surface distance of approximately two earth diameters. It does seem like a pretty big coincidence, doesn't it?

One article by a renowned physics professor cites this coincidence of having a 1:100,000,000 chance of happening. It's like we just won the lottery! But I don't think it's really cause to celebrate.

Firstly, I would say that this remarkable coincidence reveals that our way of computing the odds may not be as accurate as we hoped. Does this imply that such dangerous natural space objects are more common than we once believed? I would say no. It could, however, imply that they are more clustered than we previously thought.

Secondly, I would say that we have a ways to go to even detect the dangerous objects from space. Take the Chelyabinsk meteorite, for instance. We didn't even know it was coming until it hit the atmosphere at more than mach 50 (18 kilometers per second). Yes, it exploded with a half-megaton yield about 32.5 seconds later in a fireball easily visible from Chelyabinsk, a city of 1.1 million people. And then pieces of it hit areas near Lake Chebarkul another 5 seconds later.

Clearly we are going to need a bit of warning.

So, how lucky were we to even have seen the Chelyabinsk meteorite? First, it was a shallow entry, less than 20 degrees. This was lucky because it gave people a chance to photograph and video it. Put simply, this lengthened the time-span of the event. Second it was very near a highly-populated city. This meant that many people were able to capture the event. Third, it happened in Russia, where apparently most of the cars have dashboard cameras, due to prevalent issues with collisions and liability. This allowed us to have pictures and videos of the meteorite's reentry and explosion from many different angles. Fourth, it was large enough, apparently only about 15 meters in diameter to create an event that burned up in the atmosphere, creating a light show (and other not so good effects). But it wasn't large enough so most people who saw the event wouldn't have survived.

So we are very lucky that we saw it at all. It could have landed in Antarctica or the Pacific Ocean, and nobody would have seen it.

Unfortunately all these lucky reasons are also unlucky reasons for the people of Chelyabinsk. They noticed the flash outside and rushed to the windows to see a burning contrail, the remnants of the place where the meteorite, still traveling in excess of mach 20, had compressed the air so much that it turned atmosphere to plasma, igniting the bolide. A few seconds later the blast wave, caused by atmospheric overpressure of maybe 200 psi shattered the windows that they all flocked to. Causing a lot of injury from broken glass!

But it could have been worse. If the meteorite had had a steeper angle of entry then it could have hit the ground and exploded on contact, releasing all its kinetic energy at ground level instead of at an altitude of 30-50 km. Such an explosion could easily destroy even a large city. The heat of the blast and the overpressure wave would essentially flatten the city. It would be similar to a half-megaton nuclear weapon, but without the lingering radiation.

Actually the illustration at the top of this post gives an indication of what a large (0.2 km) meteorite would do when striking land from a very steep angle. It is shown at maybe one or two seconds after the impact. The amazing thing is that it would push out the air when it strikes, sending out a compression ring igniting the air: plasma. Instead of an explosion cloud, it would look more like many nuclear fireballs at the periphery as it found more oxygen as fuel. At this size, I presume the main strike wouldn't punch through the crust, but it would send ejecta (really pieces of itself) out, each one as large as a building. The plasma ring would propagate out at around mach 10, slowing to mach 5 at maybe a 4 km distance. This size meteorite on land would be a region killer with about a half-gigaton yield.

Yes, it can be much worse.

You know, I don't believe in coincidences, but when it comes to nature, I have an open mind. Still, even if the asteroid DA14 and the Chelyabinsk meteorite strike hadn't happened on the same day, we should still seriously consider the consequences of complacent belief that our luck will continue.

Yes, I'm advocating that we do something about the situation.

The main failure was the inability to predict that the asteroid would hit the Earth ahead of time. I believe it's a good idea to be able to track smaller near-Earth objects (NEOs) than our current plans would suggest. So, how many objects are capable of approaching Earth and have about the same size as the Chelyabinsk meteorite? About 250,000 (see this link for a table of population estimates).

And our current plans? The Spaceguard Survey's goal is to spot 90 percent of the NEOs greater than 1 kilometer in diameter. The George E. Brown, Jr. Near-Earth Object Survey's goal is to spot 90 percent of the NEOs greater than 140 meters in diameter.

Of course, neither of these two would have spotted the Chelyabinsk meteorite, since it is 1/10th the size of the smallest NEO found by the most accurate survey.

So much for the bit of warning.

Greatness

People who change the world for the better do so because they are led to do it by their conscience. Sometimes it's intuition of what the future should look like. Sometimes it's belief in enriching people's lives. Sometimes it's a feeling about what makes the best experience. Sometimes it's the sense that they are meant to do this.

Once in a generation

When you find yourself in the presence of greatness, there is no way to ignore it. You are stricken by the clarity, the simplicity, and the inarguably correct statements. Their way of understanding is fresh and insightful. Imagine talking with a scientist or mathematician that changed the world: Euclid, Sir Isaac Newton, Karl Friedrich Gauss, Srinvasa Ramanujan, Nikola Tesla, or Albert Einstein! Imagine spending the afternoon in conversation with a great leader that forever changed the way society works, like King Solomon, Charlemagne, Emperor Augustus, or Abraham Lincoln. How I would like to sit and exchange musical ideas with a composer who forever changed the language of music such as Johann Sebastian Bach, Ludwig van Beethoven, John Lennon, or Paul McCartney (I still have that chance, since McCartney is still around!). And what could I do but sit in admiration at the brilliance of the artists and geniuses that forever affected style and ignited our imaginations, such as Leonardo da Vinci, Jan Vermeer, Vincent van Gogh, Pablo Picasso, or Maurits Cornelis Escher?

When I was an idealistic kid, I wondered about each of these people. I wondered what it would be like to be one of them. Was that even something I would want? How did they accomplish what they did? What sort of difficulties did they go through?

I had so many questions! And I was bursting with ideas also. How should I channel my creative energies? How would people look at my life's work?

It was an interesting motivation, to imagine myself in the shoes of someone great. Soon I forgot all about it, though, and immersed myself in number theory, computer programming, music, and analytic geometry.

I couldn't figure out how they did what they did. All I had was their work to look at. But, once exposed to it, I began to want to create my own music, write my own programs, investigate my own areas of mathematics. It was the start of a journey that I am still on today.

The weight

Talented people are also flawed. It's a bit like they carry the weight of their greatness that is always with them. This theme, with the ring of truth to it, has been expressed in fiction several times. For instance, Sir Arthur Conan Doyle's Sherlock Holmes, a beloved character adept at following clues and making deductions, was only the intense, enlightened sleuth when the game was afoot. During off times, he fell prey to cocaine addiction.

But is the theme of the tortured genius only around because it makes a better story? No.

Beethoven went deaf at the pinnacle of his fame. Einstein had his remorse at unleashing the atom and yet urged Roosevelt to build the atomic bomb. Van Gogh courted madness and tinnitus, even cutting off his ear. Newton's mother abandoned him, remarrying when he was only 3, which left him a furiously competitive, ruthless, and paranoid man who never had any romantic relationships of any kind. Ramanujan lived in squalor much of his life, starving at some points, and yet made discoveries of such genius that even today we are still struggling to decrypt them. When they tried to school him in modern mathematics, he spouted ideas at such a furious pace that it became useless to continue.

So let's look behind the curtain. What makes this happen?

Some people believe, once they have exerted great change on the world, that they deserve more than mere humans. This is a corrupting influence borne of pride, conceit, even megalomania. Such people may make great changes, but they are rarely truly great. This kind of flaw has brought us dictators, generals, and warriors.

Other people find, when they are working obsessively on a very hard project, that it is their destiny to solve the problem. Even that it is their duty to humanity to build it. I know that, once I am wrapped up in a problem, I often think of nothing else. It is this vacuum, however, that leads to the pathways of delusion. Still, you have to get your motivation from somewhere!

It's true that people can be driven to overcome their difficulties in life. If they are hurt by those around them, they might easily escape into a self-created world where they can feel comfortable. Such a world allows them to channel their genius. Or they might be disabled in some way. The compensating behavior for a disability can also become a framework for channeling their specific talents. This was certainly the case in Beethoven's career. In his silent world, he was no longer influenced by the local styles and instead created his own. Work can be a distraction from a painful existence. In Karl Friedrich Gauss' case, the death of his wife and son in 1809 led to a depression that he couldn't shake. Only his work could give him respite from the blackness.

Madness can be an influence that compels the genius to excel. There can be ideas in the head that are literally struggling to get out. Sometimes creation is the only therapy that helps. This was certainly the case with Vincent van Gogh. Nikola Tesla suffered from obsessive-compulsive disorder, finding it ever necessary to do things in threes and loathing to touch round objects.

Obsession can be a weight as well. Someone driven to solve a problem will exhibit behavior that is simply obsessive. This can drive them to forget about the responsibilities of life such as relationships, food, and sleep.

Producing greatness

To make a great thing is not just something that is done in a few minutes. The first thing you must do is to understand fully what the concept is for what you are making. And write it down. Clarify it. Make drawings. But never lose sight of what makes it great. Spend some time thinking about the concept. Figure out what its value is. Put the concept away and return to it later. It happens that the best things might come to you when you are driving, shaving, or even dreaming.

To produce it may take many, many tries. I have mentioned before that a large fraction of things tried often must simply be thrown away. This is the way it is when I am solving an unbounded, difficult problem with no general closed-form solution. Examples of this are common.

When Thomas Alva Edison was working on the light bulb, he tried 2000 different materials before he settled on the carbon filament. Isaac Newton spent a laborious eighteen months working on his Principia, itself the result of a decade of thought. In it, he developed the infinitesimal calculus, laboriously rewriting it in standard geometrical terms so astronomers of his day could understand it.

When producing a great product sometimes the product is not the only thing you have to produce. It is clear in many cases that you have to build a whole system of capabilities for it to live in. A context of usefulness.

For Edison, it wasn't enough to create the light bulb. He also had to create a generator of electricity so there was an ecosystem to support it. When Newton was writing his Principia, he had to incorporate and prove the work of people before him, like Johannes Kepler, whose second law, shown above, had already been empirically verified.

For Steve Jobs, it wasn't enough to produce the iPod, iPhone and iPad. He also had to build the iTunes media store, the app store, and several other web services. These are considered to be essential to the success of the iDevices.

You learn things along the way to creating and perfecting it. Some aspects of your product don't even occur to you until it gets used.

This wasn't the case with Albert Einstein, whose General Theory of Relativity finally provided the framework that superseded Newton's physical laws. While it was introduced in 1915 and correctly accounted for the procession of Mercury's perihelion (part of its orbital mechanics), it wasn't until 1959 and later that a systematic series of precision test had verified many of its provisions.

Productizing greatness

Most inventions are not so theoretical. With these, you get a chance to make sure they are right. And the best inventions, the ones that really have an effect, are productized.

If you are making a product, decide what it is that you want this product to be. Do you want it to be the lowest price product so you can sell a lot of them? Or do you want it to enrich the life of the person who buys it? You must deeply care what happens after they buy the product. It's not about what they will do with the product. It's about what the product will do for them. You must understand how it will transform their lives. How will they feel about the product? You must find a way to own the customer because they believe that their life is better. What you don't want to happen is for the user to not care at all about the product. Then it will just sit in a drawer. Instead of being on their person at all times.

To ship a product without first perfecting it is not a good thing. So, when developing the product, use it for everything. Keep on improving it and its main modes of use. Make sure that everybody using the product will appreciate it as a fundamental advancement. Ensure that it will change their lives as well as the nature of all products that come after it.

Fearlessness

Great people don't fear change. They embrace it, right? No, that misses the point! You should realize it's much more than that.

Change is their most valuable tool. Let's look at a key example that is already changing things.

In the recent conference call, when asked about the iPad, which appears to be cannibalizing Mac sales, Apple's CEO Tim Cook said this:

We’ve learned over the years not to worry about cannibalization of our own products. It’s much better for us to do that than somebody else to do it. The far, far bigger opportunity here is the 80 million to 90 million PCs that are being sold per quarter. There’s still over 300 million PCs being bought per year, and I think a great number of those people would be much better off buying an iPad or a Mac. So that’s a much bigger opportunity for Apple, and instead of being focused on cannibalizing ourselves, I look at it much more that it’s an enormous incremental opportunity for us.

Instead of fearing the cannibalization effect, he is using the effect to gain entry into a larger market. He's seeing the forest for the trees. Disruption thus becomes a useful tool and a cantilever to huge potential growth.

Disruption is necessary for change. So, if you want to change the world, think about what comes next, and how that process of disruption will occur.

Hard Problems, Part 2

Some problems are hard nuts to crack. We have discussed this one before. Other problems are simply statically complex. As we will see, when things get hairy, there are still choices to make and techniques which work every time.

A statically complex problem has so many cases that it becomes daunting just to imagine a solution. This comes to mind because, of course, I am working on one of these problems right now. But I can't discuss it. Instead, we will look at another such problem and what it took to solve it.

In the 1980 I was working on a three-dimensional problem: rendering solid fractals. First Benoit Mandelbrot and then Loren Carpenter made famous the construction of mountains using fractal techniques. These were so-called plane-to-line functions, where the domain was a plane and the range was a line.

How to make nice fractals

In plainer English, you could create a mountain by making the height (z) a function of x and y. So, x and y are subdivided, and each time you subdivide, you add some random amount of z that depends upon the size of the x,y patch. In this way your mountain has a predictable fractal dimension. But now I would create such a thing by using Fourier transforms in the frequency domain: create a circular spot, transform it from the spatial domain to the frequency domain, randomize its phase, then transform it back into the spatial domain. This is shown in my blog post Textures, Part 2.

Once this technique is demonstrated, it becomes tempting to implement it. Which, of course, I did! I remember going to SIGgraph in 1980 and bringing a poster created at Calma on a Versatec raster plotter of some fractal mountains. Each facet was shaded using dither patterns, which I coded specifically for the poster. I presented it to Benoit Mandelbrot.

I'm sure Mandelbrot could've cared less about my rather amateurish fractal forgeries. There were so many people there, also. But I was undaunted and continued to play with fractals.

And so here comes the problem: what if you make a space-to-line function?

A space-to-line function is a function where w can be evaluated as a function of x, y, and z. Imagine that every point in space has a w value. And that w varies fractally. This construction can make clouds and rocks and all sorts of things!

So I decided to create a renderer that could display such a thing. The first way it could be displayed was simply to facet the zeroset of the surface, where w = 0. In a plane-to-line function, the zeroset z = 0 is simply a coastline. In a space-to-line function, the zeroset w = 0 is an actual surface of the object.

The problem can then be refined to this: how can you render the zeroset of the space-to-line function?

My answer to the problem was an early implementation of what is now called Marching Cubes. This technique was invented later by Lorensen and Cline and published in the 1987 SIGgraph proceedings. But I was using it in 1984. I won't say I invented it. Actually, it's a rather obvious solution.

My solution to the problem was to split the volume into small cubes. By evaluating the function for w at each corner of the cube, it will be found to be less than or equal to zero (a 0 bit) or greater than zero (a 1 bit). Since each cube has 8 corners, this was conveniently an 8-bit number.

Thus there were 256 cases to consider. That's a lot of cases, hence it was statically complex.

This is the first time I ever wrote a program to write the program to solve the problem. The program that generated the code for marching cubes was cloudtst.c, written in C on February 6, 1984, designed to run on a DEC VAX 11-780.

When a problem is this complex, it's hard to get every case right and consistent with every other case. This leads to the need to make sure each case is correct by having each case be generated by a program.

I categorized the eight bits into topological cases. And then I used the program to decide, for one of the 256 cases, which topological case it fell into. Then I mapped the solution for the topological case onto the 8-bit case.

Actually, the way I framed the problem was even more clever, since I allowed myself the luxury of subdividing a cube into 8 sub-cubes and faceting them. This meant that I could recursively subdivide the volume I was rendering, only subdividing it where it needed to be subdivided. This would minimize the total number of facets output and thus cut down on the time to render the fractal volume.

Code that writes code

It sounds a bit recursive, doesn't it? But there are several advantages to writing code that writes code. I will discuss them now.

The first and most obvious thing is this: if a program writes the code, then you won't have to. This is advantageous because there might be a lot of code to write. With a lot of complicated cases. And a program can make sure that each case is correct. So you won't have to. All you have to make sure of is that the program that analyzes the cases will get the right answer in each case.

The second advantage happens when you are generating a lower-level language. The program can see to all the details. This is useful when optimizing something. Lower-level languages are inherently more efficient because they are closer to the machine they run on. There is no hidden complexity. Each instruction is atomic. If you have to break each operation into smaller operations, the program can do it slavishly for you. This is the reason that people write compilers.

The third and most important advantage is also useful to you. To fix bugs, even those occurring in several cases, you only have to change the program that writes the code, not all the cases. This turns out to be characteristic of the code-writing-code process. Each bug in the generated code can be attacked one-by-one in the generating code. And eventually a perfectly correct program is the result. This can be done without tediously fixing each case in the generated code one at a time. Actually, many cases in the generated code can come from one part of the program, so a single bug fix in the generating program can fix several bugs in the generated program. This illustrates the power of this approach.

What language should you use? You have two choices to make. First, you choose a language to write the generating program in. This is usually a high-level language. One that you can work in with extreme freedom and ease. This can be something as utilitarian as C or ripe in data structures like C++. It can also be Python, a common choice nowadays. The second choice is the language used for the program you are generating. This should generally be chosen for its efficiency. Sometimes you do not have a choice. For instance, I have written code that generates programs in various forms of assembler, in C, in fragment shaders, and in OpenCL.