25 Aug 2004 Bram   » (Master)

SHA-1

There's rumor of a sha-1 break, related to a very confirmed break of sha-0. Fortunately the breaks are unlikely to lead to the construction of pre-images, so there's no need to panic just yet, even if the rumors prove true.

Which leads to the question, what should we do? First of all, there's no need to change algorithms just yet, although anyone designing a protocol might want to hold off a few months unless time isn't of the essense (and in software everything is always late, so it rarely is). With a hash length of 160 bits, and thus birthday attacks in 80 bits, sha-1 is due to expire in roughly two decades no matter what, so we should seriously consider using a hash function with a longer output. AES-128, which with a key and block size of 128 bits could easily survive past when moore's law runs out of gas.

Whatever happens, it would be a disaster for a multiplicity of hash functions to win out, since that would result in profound incompatibility. So the choice of successor to sha-1 shouldn't be taken lightly.

The clear political favorite is sha-256, which is unrelated to sha-1 in structure and hence not susceptible to the most recent attacks, and also has a 256 bit output to match aes's 128 bit key length. My only real complaint about sha-256 is that it's a different (and much less studied) cryptographic primitive than aes, thus providing two points of attack to our cryptographic systems rather than one. I would much prefer a hash function which is based on aes, such as whirlpool. Unfortunately whirlpool has a 512 bit output and about the performance of sha-512, at least on 32-bit systems. If there was a standardized aes-based hash which had an output of 256 bits and about the performance of sha-256 I'd recommend it unhesitatingly, but with the way things are now I'm torn.

If I had to put even money on it I'd bet on sha-256 winning, since that one already has considerable political oomph behind it, and noone has complained about potential weaknesses in it, and everybody agrees on the importance of a single standard.

Python Exception Assertions

I would like to be able to state in my Python code 'assert than exception spam would get caught somewhere in the current call stack by something other than a catch of general exception'. There are many bugs which this would catch easily which are very difficult to search for comprehensively using test code, and have caused me great pain in the past and probably will continue to do so in the future.

I mentioned this to Guido and he pointed out that the expressions stating what is to be caught aren't evaluated until an exception is actually thrown. This interesting piece of trivia indicates that the expressions would have to be evaluated at the time the assertion is made, which could be a little slow, but that doesn't invalidate the utility of the functionality I want.

Guido indicated that, although he doesn't disagree with the functionality I want, it would require a significant change to the Python VM which he doesn't expect anyone to be interested in doing. So if you want a Python core project which is technically challenging and, in my humble opinion, clearly very benificial I suggest adding this functionality. If you do, I will be eternally grateful.

Hex

After playing around with the hex code I gave in my last entry, I think I can finally explain some opening theory.

The first question is, if your first piece is in the center, why is it weak to put your second piece near it? The answer is somewhat indirect. If there were other pieces randomly scattered around the board, a piece close to the central one would be very powerful, but at the beginning of the game there are very few pieces around, so you have to think specifically about the pieces in play. When your opponent responds to your strong central move, he will do so in a place away from where you moved, and since your board coverage is poor from being so focused on one point, his move will be relatively strong. By spreading out your moves you prevent that.

So the second centralized move isn't weak, it's just that the responses it allows are strong. A very surprising thing about this observation is that it's made straightforwardly by increasing the ply of look-ahead, in fact 2 ply sees it just fine. I always assumed that the beginning of a hex game is very strategic and that increasing ply look-ahead wouldn't improve play any, since that's reserved for 'tactical' situations. Apparently that guess was completely wrong, but I still think that increasing ply doesn't improve play unless your board evaluation function isn't a piece of garbage, which I didn't have until now.

The second question is, why do the best hex players now play pieces so far away from the center for their opening move? The answer is related to the answer to the first question - if you place your first piece in the center, then any strong place to put your second piece will probably be close to it, which will be weak for the reason I gave above. I believe this would be seen by a four-ply look-ahead. Again, my guess that increasing the ply of a board evaluation function was completely off base.

So now at least I have an explanation of why early hex moves are the way they are, although I suspect I'll have a lot of difficulty applying this knowledge to make my play better.

Hex is the only game I know of where hypermodern theory has become the dominant one.

A good place to play hex is kurnik.

Boom-Boom

I came up with a new and improved board shape for playing boom-boom on. Start with a checkerboard of odd side length, with the corners colored black and alternating squares colored white. Make the white squares part of the 'real' board, and connect each of them to the four (or in the case of edges, two) other white squares they share a corner with. Next connect each of the edge pieces with the two edge pieces closest to it, so for example (6, 1) connects to (8, 1) and (4, 1). (My terminology counts the corner as (1, 1) not (0, 0).) Then remove (2, 1) and (1, 2) and replace them with a single piece at (1, 1) which is connected to (4, 1), (3, 2), (2, 3) and (1, 4).

This board is probably most interesting to play go on, since it makes each node have exactly four neigbors, thus having the 'borderless' property of circular go boards without being so difficult to print.

Boom-Boom

One of the big problems with boom-boom is that after each explosion new pieces wind up being placed in fairly 'random' places, which make the play extremely tactical, with not much advanced planning possible. This can be eliminated by making it so that when a piece explodes a piece remains on the original exploding spot. Although that results in more pieces to the side which caused the explosion, it doesn't really incentivize pointless exploding because the new group tends to get captured as a unit. But you do wind up with a question of where excess pieces propogate to, so that a single explosion doesn't propogate forever. This also leads to the funky-shaped board becoming pointless, since it was designed to make explosions happen more quickly.

A few more logical steps along those lines results in the following game, which can be easily played using a standard othello set.

Both players alternate placing pieces of their color. On a player's turn they have the option, instead of placing a new piece, of capturing a piece of the opponent's which borders on one of their own (for the purposes of this game 'bordering on' means sharing an edge or corner). When a piece is captured all of the pieces of the same color which border it are captured recursively, thus a very large group can be captured at once. The game ends when one player occupies the entire board.

Note that if white has pieces on (3, 3) and (3, 5) and black has pieces on (3, 2), (3, 4) and (3, 6) then if white captures (3, 4) than does not result in either (3, 2) or (3, 6) getting captured, although it would if there were black pieces on (4, 3) and (4, 5).

I'm not sure off the top of my head how to approach even very simple endgames of this game. Further experimentation is required.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!