ImperialViolet

Capability Python (06 Apr 2003)

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.

Defense Against Middleperson Attacks

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: m1
  • Bob's Move: m2
  • Alice's Public Key: PKA
  • Bob's Public Key: PKB
  • Random Nonces: n1 and n2
  • A Shared Integer: K

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

  • Message1 = (m1, PKA, n1)
  • Commitment1 = Hash(Message1)

Alice transmits Commitment1 and sleeps K seconds. Alice transmits a signed copy of Message1

After Bob receives Commitment1 he sleeps for K seconds. He then waits to receive the signed copy of Message1. Bob verifies that Message1 was signed by the included copy of PKA, and that Commitment1 is correct.

Bob quickly ponders his move and calculates:

  • Message2 = (m2, PKB, PKA, Message1, n2)

Bob signs Message2 and encrypts the signed copy with the PKA from Message1. He transmits this.

Alice receives the signed and encrypted Message2. If more than K seconds have passed since she send Message1 she aborts the game.

Otherwise, she decrypts Message2 and checks the signature against the included PKB and that her public key is correct.

Results

  • The person who knows the private key which matches public key PKB is also the person who made chess move m2.

    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 Message1 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 Commitment1 and Message1 before he can forward either to the grand-master.

    However, he has to get the reply back to Alice K seconds after send sends Message1, but the grand-master is waiting at least K seconds after he receives the altered Commitment1 from Bob.

  • The person who knows the private key which matches public key PKB signed Message2, so he knew the correct Alice public key and he knew Alice's original chess move.
  • Since Message2 was encrypted with Alice's real public key, it was not possible for anyone to read the contents of Message2.

Assumptions

  • K is great enough to ignore transmission times, and for Bob to consider his move
  • Everyone uses the same value for K
  • The public key cipher is secure and the hash is uninvertable.