Responding to my entry yesterday about pokerbots, Jordan Lampe emails a report from the world of backgammon. Backgammon bots play at least as well as the best human players, and backgammon is often played for money, so the temptation to use bots in online play is definitely there.

Most people seem to be wary of this practice, and the following
countermeasures have been developed (not necessarily exclusive or all
used by the same person)

1) Don’t play for money; only play for fun
2) Play money only against people you know [well]
3) Against somebody who takes a long time after every move, you are
suspicious that they are plugging their moves into computers
4) At the end of the game, you can analyze your game with one of the
computer programs. It turns out that all the computers rate each
other’s play very highly, with an error rate of 0-1.5 “millipoints” per
move. If you get a rate of exactly 0 you can be dead certain they are
using the same computer program. Computers rate the best humans in the
world in the 3-4 range. In any case, if your opponent is using a
computer program to decide all his moves it is fairly easy to tell after
only a few games, and then avoid playing with that player any more.
5) Some players take the attitude, “if I lose, at least I’ll have
learned something” and therefore ignore if they are playing bots
6) Using a bot to help you win is, well, boring, and so it doesn’t
happen that much anyway

Having played a lot of poker and backgammon in my day, I suspect that distinguishing human play from computer play would be harder in poker than it is in backgammon. For one thing, in backgammon you always know what information your opponent had in choosing a certain move (both players have the same information at all times); but in poker you may never know what your opponent knew or believed at a particular point in time. Also, a good poker player is always trying to frustrate opponents’ attempts to build mental models of his decision processes; this type of misdirection, which a good bot will emulate by using randomized algorithms, will make it harder to distinguish similar styles of play.

Jordan identifies another factor that several poker players mentioned as well: the fact that most gambling income is made by separating weak players from their money. As long as there are enough “fish”, all of the sharks, whether human or not, will feast. When the stakes get high, the fish will be driven out; but at low stakes, good human players may still make money.

Computerized “bots” may be common in online poker games according to a Mike Brunker story at MSNBC.com. I have my doubts about the prevalence today of skillful, fully automated pokerbots, but there is an interesting story here nonetheless.

Most online casinos ban bots, but there is really no way to enforce such a rule. Already, many online players use electronic assistants that help them calculate odds, something that world-class players are adept at doing in their heads. Pokerbot technology will only advance, so that even if bots don’t outplay people now, they will eventually. (The claim, sometimes heard, that computers cannot understand bluffing in poker, is incorrect. Game theory can predict and explain bluffing behavior. A good pokerbot will bluff sometimes.)

Once bots are better than people, it’s hard to see why a rational person, with real money at stake, would fail to use a bot. Sure, watching your bot play is less fun than playing yourself; but losing to a bunch of bots isn’t much fun either. Old-fashioned human vs. human play will still be seen in very-low-stakes online games, where it’s not worth the trouble of deploying a bot, and in in-person games where the non-botness of players can be checked.

The online casinos are kidding themselves if they think they can enforce a no-bots rule. How can they tell what a player is doing in the privacy of his own home? Even if they can tell that a human’s hands are on the keyboard, how can they tell whether that human is getting advice from a bot?

The article discusses yet another unenforceable rule of online poker: the ban on collusion between players. If two or more players simply show each other their cards, they gain an advantage over the others at the table. There’s no way for an online casino to prevent players from conducting back-channel communications, so a ban on collusion is impossible to enforce.

By reiterating their anti-bot and anti-collusion rules, and by claiming to have mysterious enforcement mechanisms, online casinos may be able to stem the tide of cheating for a while. But eventually, bots and collusion will become the norm, and lone human players will be driven out of all but the lowest stakes games.

But there is another strategy. An online casino could encourage bots, and even set up bots-only games. The game would then become not a human vs. human card game but a human vs. human battle between bot designers for geekly mastery. I’ll bet there are plenty of programmers out there who would like to give it a try.

Kryptonite may stymie Superman, but apparently it’s not much of a barrier to bike thieves. Many press reports (e.g., Wired News, New York Times, Boston Globe) say that the supposedly super-strong Kryptonite bike locks can be opened by jamming the empty barrel of a Bic ballpoint pen into the lock and turning clockwise. Understandably, this news has spread like wildfire on the net, especially after someone posted a video of the Bic trick in action. A bike-store employee needed only five seconds to demonstrate the trick for the NYT reporter.

The Kryptonite company is now in a world of hurt. Not only is their reputation severely damaged, but they are on the hook for their anti-theft guarantee, which offers up to $3500 to anybody whose bike is stolen while protected by a Kryptonite lock. The company says it will offer an upgrade program for owners of the now-suspect locks.

As often happens in these sorts of stories, the triggering event was not the discovery of the Bic trick, which had apparently been known for some time among lock-picking geeks, but the diffusion of this knowledge to the general public. The likely tipping point was a mailing list message by Chris Brennan, who had his Kryptonite-protected bike stolen and shortly thereafter heard from a friend about the Bic trick.

I have no direct confirmation that people in the lock-picking community knew this before. All I have is the words of a talking head in the NYT article. [UPDATE (11 AM, Sept. 17): Chris at Mutatron points to a 1992 Usenet message describing a similar technique.] But if it is true that this information was known, then the folks at Kryptonite must have known about it too, which puts their decision to keep selling the locks, and promoting them as the safest thing around, in an even worse light, and quickens the pulses of product liability lawyers.

Whatever the facts turn out to be, this incident seems destined to be Exhibit 1 in the debate over disclosure of security flaws. So far, all we know for sure is that the market will punish Kryptonite for making security claims that turned out to be very wrong.

UPDATE (11:00 AM): The vulnerability here seems to apply to all locks that have the barrel-type lock and key used on most Kryptonite bike locks. It would also apply, for example, to the common Kensington-style laptop locks, and to the locks on some devices such as vending machines.

Adam Shostack points to a new paper by Peter Swire, entitled “A Model for When Disclosure Helps Security”. How, Swire asks, can we reconcile the pro-disclosure “no security by obscurity” stance of crypto weenies with the pro-secrecy, “loose lips sink ships” attitude of the military? Surely both communities understand their own problems; yet they come to different conclusions about the value of secrecy.

Swire argues that the answer lies in the differing characteristics of security problems. For example, when an attacker can cheaply probe a system to learn how it works, secrecy doesn’t help much; but when probing is impossible, expensive, or pointless, secrecy makes more sense.

This is a worthwhile discussion, but I think it slightly misses the point of the “no security by obscurity” principle. The point is not to avoid secrecy altogether; that would almost never be feasible. Instead, the point is to be very careful about what kind of secrecy you rely on.

“Security by obscurity” is really just a perjorative term for systems that violate Kerckhoffs’ Principle, which says that you should not rely on keeping an algorithm secret, but should only rely on keeping a numeric key secret. Keys make better secrets than algorithms do, for at least two reasons. First, it’s easy to use different keys in different times and places, thereby localizing the effect of lost secrets; but it’s hard to vary your algorithms. Second, if keys are generated randomly then we can quantify the effort required for an adversary to guess them; but we can’t predict how hard it will be for an adversary to guess which algorithm we’re using.

So cryptographers do believe in keeping secrets, but are very careful about which kinds of secrets they keep. True, the military’s secrets sometimes violate Kerckhoffs’ principle, but this is mainly because there is no alternative. After all, if you have to get a troopship safely across an ocean, you can’t just encrypt the ship under a secret key and beam it across the water. Your only choice is to rely on keeping the algorithm (i.e., the ship’s route) secret.

In the end, I think there’s less difference between the methods of cryptographers and the military than some people would think. Cryptographers have more options, so they can be pickier about which secrets to keep; but the military has to deal with the options it has.

Here’s the summary of events from last night’s work-in-progress session at the Crypto conference. [See previous entries for backstory.] (I’ve reordered the sequence of presentations to simplify the explanation.)

Antoine Joux re-announced the /msg02554.html">collision he had found in SHA-0.

One of the Chinese authors (Wang, Feng, Lai, and Yu) reported a family of collisions in MD5 (fixing the previous bug in their analysis), and also reported that their method can efficiently (2^40 hash steps) find a collision in SHA-0. This speaker received a standing ovation, from at least part of the audience, at the end of her talk.

Eli Biham announced new results in cryptanalyzing SHA-1, including a collision in a reduced-round version of SHA-1. The full SHA-1 algorithm does 80 rounds of scrambling. At present, Biham and Chen can break versions of SHA-1 that use up to about 40 rounds, and they seem confident that their attacks can be extended to more rounds. This is a significant advance, but it’s well short of the dramatic full break that was rumored.

Where does this leave us? MD5 is fatally wounded; its use will be phased out. SHA-1 is still alive but the vultures are circling. A gradual transition away from SHA-1 will now start. The first stage will be a debate about alternatives, leading (I hope) to a consensus among practicing cryptographers about what the substitute will be.