Category: Geek stuff

If it involves physics, math, computer science, electronics or has general geek cachet, this is the place for it.

The P Versus NP Problem

There are some sorts of problems where it is relatively easy to check that a solution is correct, but hard to find that solution to begin with. For example, it is easy to check whether a large number is the product of two primes (429,496,729 = 19 X 22,605,091), but it is hard to find the factors of a large number. These problems are called ‘NP problems’ in mathematics, because they cannot be solved in polynomial time.

By a quirk of mathematics, if anyone ever comes up with an efficient way to solve one of these NP problems, the technique will be applicable to all such problems. That said, it may be the case that there is no efficient way to solve any of these problems. As such, whether all or none of them are efficiently soluble is an important question in mathematics.

The importance of the problem extends beyond the theoretical realm. For instance, the ‘traveling salesman’ problem is NP. There is a salesman who wants to visit X cities, with as little travel as possible. Finding the quickest route becomes dramatically more difficult as the number of cities increases. If someone could solve the P versus NP problem they could either help Fedex and UPS a lot (if an efficient solution to NP problems is found) or prove that their work will always be challenging (if it is proven that there are none).

This article provides more information on the P versus NP problem.

Ghost: Confessions of a Counterterrorism Agent

Purple grasses

I became aware of Fred Burton through the free weekly defence briefings put out by STRATFOR, his current employer. They stand out from other media reports, both as the result of the details they focus on and the thrust of their overall analysis. While I wouldn’t bet heavily on them being entirely correct, they do play a useful counterbalancing role when read alongside media stories that are generally rather similar.

Ghost describes Burton’s history with the Diplomatic Security Service (DSS) between 1986 and 1993, with an epilogue in 2004. Burton’s work involved collecting intelligence, investigating plots and attacks, protecting diplomats, and so forth. He goes into detail on several of the investigations he was involved in, including the assassination of Pakistani President Muhammad Zia-ul-Haq and the capture of Ramzi Yousef. He also describes some of the tactics and strategies employed by the DSS, as well as by other law enforcement and intelligence agencies. These include the operation of motorcades, cover techniques, and countersurveillance: a tactic he claims special credit for deploying in the protective services.

The book’s greatest strength lies in the details it includes, on everything from the character of different intelligence agencies to equipment used to various sorts of tradecraft. While the breathless descriptions can sometimes feel like the content of a mediocre spy novel, the detailed technical discussions offer insight into how clandestine services actually operate. Of course, it is virtually certain that security and secrecy led to parts of the book being incomplete or distorted. Still, it has a candid quality that makes it an engrossing read. One interesting perspective offered is on the connections between different states and terrorist groups: particularly the relationship between Iran and Hezbollah; between the Palestinian Liberation Organization (PLO), Yasser Arafat, and various terrorist groups; as well as the ways in which modern terrorist tactics evolved from those developed by Black September, the group that carried out the massacre at the 1972 Munich Olympics.

At times, the book’s language is overwrought, especially when Burton is discussing the innocence of the victims of terrorism and the ‘evil’ nature of those who commit it. His reflections on his own ethical thinking may be genuine, but seem somewhat hackneyed and unoriginal at the same time. He never portrays American intelligence or police services as having any flaws, with the exception of when bureaucrats get overly involved and stop brave and effective agents from doing their work well. No consideration is given to the abuses that can occur when effective oversight is not present. Burton is also unrelentingly hostile towards the media: accusing them of offering superficial analysis and being eager to divulge information that undermines the clandestine efforts of intelligence organizations. The book is also a bit too well sprinkled with cliches, such as decisions being made and information being assessed ‘above Burton’s pay grade.’ In general, Burton seems a bit too willing to assume that all US intelligence agents are working on the side of the angels and that oversight and accountability can only hamper their efforts.

One interesting passage mentions how little time was required to circumvent the encryption on Yousef’s laptop. This makes me wonder what sort of algorithm had been employed and how it was implemented, as well as the techniques used by those breaking the encryption. I suspect that the actual encryption algorithm is not what was overcome, at least not through some brute force means. It is far more likely that they were able to compromise the password by comprehensively searching through the data on hand, including temporary files and perhaps contents of RAM. It does you little good to have a hard drive encrypted with AES-256 if it is possible to recover or guess the key in a short span of time.

In general, the book is one I recommend. It has a good authentic feel to it and includes some unusual perspectives and operational details. Burton’s personal dedication, as well as that of the agents he serves with and admires, is both convincing and commendable.

WPA cracked in 60 seconds

WPA is a more secure encryption system for wireless networks than the older WEP system, which was notoriously vulnerable. Now, Japanese researchers have devised an attack that cracks WPA networks using the Temporal Key Integrity Protocol (TKIP) algorithm quickly and easily. So far, WPA2 and WPA using AES are not vulnerable to the attack. On past form, it seems likely that those will eventually become vulnerable to rapid compromise, as well.

The broader point this demonstrates is how attacks always get better and never get worse. As such, the longer any particular system has been deployed, the less likely it is to be secure. Threat analysis needs to be ongoing, and accompanied by the patching and replacement of vulnerable systems. Both because of improving computer power and new mathematical developments, this is especially true when it comes to cryptography. As MC Frontalot explains (in a song that references rainbow tables), “you can’t hide secrets from the future with math.”

Built-in antivirus for OS X

Rumours are circulating that Apple’s Snow Leopard OS will include antivirus capabilities. This is a welcome development. While OS X rightly has a good reputation for security, there is no commercial operating system that is immune from malware. In addition to malware that targets OS X itself, there are also exploits based around flash, Adobe PDFs, and even specific pieces of hardware.

Adding antivirus protection might be a bit of a public relations blow to Apple, which has cultivated a false sense that there is no malware that affects Macs. Nevertheless, it is a good security move. Indeed, the server version of OS X has included such capabilities for some time.

Building a camera system

Woman with flowers in her hair

I often get asked about what sort of photographic gear serious amateurs should buy. Normally, I direct them towards this excellent primer on building a digital SLR system, written by Philip Greenspun. It is, however, a bit on the long side. Here is a briefer encapsulation.

Brand

I would go with Canon or Nikon. This is mainly due to compatibility, both across a wide range of accessories (lenses, flashes, etc) and across long spans of time. Both companies make excellent gear that will be usable for decades. I happened to go with Canon and have always been happy with them.

There are other brands that have advantages (both in terms of price and features), but the market for Canon and Nikon related gear is broad and deep.

Sequence

This really depends on what sort of photography interests you most. Someone seriously into nature photography would skew their purchases towards telephoto gear, while someone looking to take informal shots in casual settings might go for fast primes. The basic sequence, however, looks something like this:

  1. Get a crop-sensor dSLR. These cost about $600-700 and are very capable cameras. One thing to remember, though, is that they will multiply the effective focal length of all your lenses by 1.6. As such, a 50mm lens on a crop sensor is akin to an 80mm lens on a film body or full-frame dSLR.
  2. Get a memory card, but don’t worry about filters and things unless you are going to be working in very wet or dusty places.
  3. Get a couple of batteries. You don’t want to find yourself in the middle of an excellent and unexpected photo session, but unable to snap any more shots.
  4. Buy the kit lens. It won’t be of great quality, but they are usually very cheap when bought with the camera body. They are also often the only way to get cheap wide angle capability for a dSLR.
  5. Buy a 50mm f/1.8 lens. These have great optical quality, can allow fast shutter speeds in dark circumstances, and can often be purchased for about $100. A 28mm or 35mm lens would more closely approximate a 50mm ‘normal’ lens on a film camera, but these tend to cost a lot more.
  6. Get a tripod. It’s not necessary for absolutely every kind of photography, but it is useful for most. It is also a good way to keep your camera stored in an accessible and highly visible place (which prompts me, at least, to go out shooting more often).
  7. Get a camera bag that works for you. This is a tricky process that usually takes some experimentation. You want something big enough to carry what you need, but not so big you can never take it anywhere. You also need to decide whether you prefer a shoulder bag (much more accessible), a backpack (more comfortable), or something else. When carrying around just one camera and lens, don’t bother with a camera bag. Just bring a plastic bag in case of rain. Having your camera stuffed a way in a bag when walking around will make you miss photos. Bags are for carrying extra gear, and providing protection in transit.

Beyond this, the sequence really depends on what you plan to shoot. Some people might start with flash(es), some people might save their pennies for professional grade zoom lenses. Others might improve on their kit lens with consumer grade zooms (such as the reasonably high quality lenses that zoom from around 30mm to around 100mm and are available for under $500). Some people might assemble a collection of primes. Some people might save up to go straight to a full-frame body.

As someone who has tried a fair sampling of different kinds of photography, I would suggest that the following is a reasonable sequence:

  1. Consumer grade zoom (about 30mm to 100mm)
  2. Portable reflector (for portraits in sun)
  3. External flash and method for triggering it off-camera (either a cable or radio triggers)
  4. Light stand for flash and umbrella
  5. Second flash with triggering system
  6. Light stand for flash and umbrella
  7. Professional grade telephoto zoom (i.e 70-200mm)
  8. Professional grade wide angle zoom (i.e. 24-70mm)
  9. Wide angle prime lens (28mm or 35mm)
  10. Macro lens (85mm or 100mm)
  11. Full-frame dSLR body

You may want to sell the consumer zoom once you have professional grade ones, though it can be useful in situations where you need a wide range of focal lengths but can only bring one lens. If you never plan to get a full-frame dSLR, a professional grade wide angle zoom specific to crop sensor bodies might be a good idea.

Other options beyond this:

  • More flashes
  • Flash accessories (grids, snoots, softboxes, beauty dishes, gobos, etc)
  • Crazy nature lenses (i.e. 100-400mm)
  • Teleconverters (make any lens act like a longer one)
  • Fisheye lenses
  • A second body, so you can use two lenses without having to swap.

If you’ve worked your way through all of that, probably know a lot more about photography than I do. If you are in need of more distant horizons, there are two words to consider: medium format.

Ethics and autonomous robots in war

The increasing use of autonomous robots in warfare raises questions about how they can be used ethically and in concordance with international law on armed conflict. While unarmed robots like those used by bomb squads are ethically unproblematic, those with both weapons and an independent capability to make decisions about their use are quite different. This is especially true if they will be used in environments where civilians could be injured or killed.

The BBC has an article about some of the concerns that have been raised and issues that have been considered. In some ways, the trade-offs are similar to those with existing technologies. For instance, there is often a trade-off between how much risk an army exposes its own personnel to, and how effectively it can avoid causing civilian casualties.

How Americans spend their time

The New York Times has cooked up a neat interactive graphic on how Americans spend their time. It is broken up by hour of the day and by characteristics like employment status, race, and level of education.

Everyone devotes a surpising amount of time to TV and movies, especially compared to socializing. It is also interesting to see that those with advanced degrees seem to spend the largest share of their time traveling, though the graphic doesn’t make clear whether this is intra-city commuting, vacation travel, or both.

I found the graphic via Sightline Daily. There are some interesting observations there, such as: ” Just so, only five percent of men over 15 say they spend any time walking on a given day. Yet for most of human existence, walking was the only form of transportation available to the large bulk of humanity.”

A notebook to track organizational bugs

As someone who has come under three different major bureaucracies in the past eight years (and many different sub-elements of each one), I find a suggestion from Dame Julia Cleverdon, the chair of trustees for the UK’s Teach First program, to be an interesting one. She suggests that people joining new organizations should:

“keep a notebook and write down everything that strikes them as crazy in the first few months—because a year in, those things will seem normal. And two years in, when they have gained in experience and confidence, they should get that notebook out and start changing those things.”

It’s an approach that neatly balances the fact that people new to organizations probably think about them most creatively, while recognizing that experience is necessary to be influential and to be able to anticipate the full consequences of reforms.

High-speed stock trading

I had no idea stock markets operated so quickly now:

High-frequency traders may execute 1,000 trades per second; exchanges can process trades in less than 500 microseconds (or millionths of a second).

In addition to showing off just how blazingly fast financial transactions have become, this also demonstrates just how much more precise and reliable some networking hardware is, when compared to consumer stuff.

For the sake of comparison, I sent four packets from my home computer to the server that runs this site. It took them an average of 92 milliseconds to make the journey: 184 times longer than the rate at which exchanges can apparently process trades. Indeed, the difference between the quickest and the slowest packet to return was itself six times longer than the total processing time.

Clearly, those on dial-up connections need not apply.