ImperialViolet

Zooko's blog had been down for a fair time as he changed hosting, so I only noticed today that he had started posting again.

Recently, he's been talking about adding capabilities to Python and, oddly enough, I was thinking about the exact same thing yesterday. If some of the introspection abilities of Python were limited, it would make a very effective capability language by using references as a capabilies. Thankfully, from following some of the links on the python-dev archives (below) it seems that a PEP is being worked on.

Once the language is limited, the standard library needs to be looked at. The Python people aren't going to accept the gutting of the library for the needs of capability freaks, so many of the modules will have to be proxied as they have dangerous functions (for example, taking a filename not a file handle).

Also, some of the standard functions (thinking of __repr__ here) leak a little too much information and could be trimmed without loss of useful funtionality. Leakage increases the bandwidth of side-channels. You can never be rid of side-channels, but you can stomp them as much as possible.

Zooko has also written a nice crypto paper. However, I had to scribble notes when reading it and hope that this version is a little easier to understand:

Defence Against Middleperson Attacks:

Zooko, <zooko AT zooko DOT com>

The Problem

Alice thinks she's pretty hot stuff, chess wise, and bets that no one can beat her in a game. Bob takes her up on this challenge and the game commences. Unknown to Alice, Bob is also playing a game against a chess grand-master. Whenever Bob gets a move from Alice, he plays that move against the grand-master and relays his response to Alice. The grand-master trounces Bob, and so, Bob trounces Alice. Bob wins the bet.

Somehow, Alice wishes to know that the identity of the person playing her matches a given public key. That way, if she encrypts prize to that key she knows that Bob cannot cheat her - the surprised grand-master would get the goodies.

The Solution

Dramatis Personae

Alice's Move: m₁
Bob's Move: m₂
Alice's Public Key: PK_A
Bob's Public Key: PK_B
Random Nonces: n₁ and n₂
A Shared Integer: K

Alice is ready to make the first move in the chess game. She calculates:

Message₁ = (m1, PK_A, n₁)
Commitment₁ = Hash(Message₁)

Alice transmits Commitment₁ and sleeps K seconds. Alice transmits a signed copy of Message₁

After Bob receives Commitment₁ he sleeps for K seconds. He then waits to receive the signed copy of Message₁. Bob verifies that Message₁ was signed by the included copy of PK_A, and that Commitment₁ is correct.

Bob quickly ponders his move and calculates:

Message₂ = (m₂, PK_B, PK_A, Message₁, n₂)

Bob signs Message₂ and encrypts the signed copy with the PK_A from Message₁. He transmits this.

Alice receives the signed and encrypted Message₂. If more than K seconds have passed since she send Message₁ she aborts the game.

Otherwise, she decrypts Message₂ and checks the signature against the included PK_B and that her public key is correct.

Results

The person who knows the private key which matches public key PK_B is also the person who made chess move m₂.

Consider the plight of Bob, who tries to play Alice against a grand-master (who also follows this protocol). Bob must alter the public key in Message₁ because the grand-master's reply is encrypted with it and Bob must substitute his key into the reply. Thus, Bob must wait for both Commitment₁ and Message₁ before he can forward either to the grand-master.

However, he has to get the reply back to Alice K seconds after send sends Message₁, but the grand-master is waiting at least K seconds after he receives the altered Commitment₁ from Bob.
The person who knows the private key which matches public key PK_B signed Message₂, so he knew the correct Alice public key and he knew Alice's original chess move.
Since Message₂ was encrypted with Alice's real public key, it was not possible for anyone to read the contents of Message₂.

Assumptions