Thursday, April 20, 2006

This week I've been mostly thinking about cryptograhpy..


At work I've been trying to make an VNC work using SSL connections. Fog Creek did it it their copilot software but the it looks quite hard to disentangle this from the other changes they have made. And it is useful when selling the idea of remote control to be able to tell people that they've got the same security levels as their internet banking uses. Or so marketting tells me.

Unfortunately while VNC works really well even over low bandwidth links without stuttering, when I use it with SSL I'm getting data stalls.

It is quite subtle because it the current implementation I have to use a special forwarding agent at our firewall. As a result I've been starring at the internals of openssl, packet traces and even schneier so I can spot any obvious goofs. (And yes I am stting TCP_NODELAY - which improves the responisveness but doesn't prevent stalls.).

Mental CCG

I said I got Schneier's AC out, while techincally true I hardly read it for the above although I did dip into to during the journey to work. I stumpled across the page on Mental Poker. Which given my current interest in CCGs, well l5r specifically - I started to think on whether the protocol could be used to play l5r.

My original conclusion was basically yes. In fact you don't even need to use a public key algorthim with the property:-


  Da(c) = Decryption of c using key a
  Db(c) = Decryption of c using key b
  Ea(c) = Encryption of c using key a
  Eb(c) = ENcryption of c using key b
which mental poker needs.

The reason for this is really simple, in most CCGs every body draws form there own deck. (Well in l5r decks as each player has two decks of at least n(=40 usually) cards).

Hence you end up with a protocol like this. I'm only going to show one half but you need to do the same again with Bob and Alice reversed for a two player game. You could extend it to n players but that starts to allow cheating by collusion.

  1. Alice creates a new private/public key pair for the game.
  2. Alice publishes the Public key, which she uses as an encryption key a.
  3. Alice creates one messge of the format Ea([CardId.RandomNo]) for each card in her deck. CardId here represents the name and other details of the card.
  4. Alice send this list of messages in a random order to the player on her left (Bob).
  5. Everytime Alice draws a card Bob choses a card at random, and tells Alice which one he picked. If this card is going into Alice's hand Bob rememebers Ea([CardId.RandomNo]) is in alice's hand.
  6. When Alice reveals a card from her hand She tells Bob Ea([CardId.RandomNo])=[CardId.RandomNo].
  7. Bob verifies that Ea([CardId.RandomNo]) should be in Alice hand (has he has seen everything going in and out of the hand in it's encrypted form. And can use Alices public key to also verify Ea([CardId.RandomNo])=[CardId.RandomNo]. This ensures Alice can only reveal cards from here hand the which Bob has chosen randomly out of here deck.
  8. Other cards can be revealled in a similiar way, although in the case of card which remain face down for all players Bob cannot reveal Ea([CardId.RandomNo]) else Alice would know what was on the face of the card. The is important for card facedown in provinces for example.
  9. If cards need to be reshuffled, all card which are being shuffled together are indicated to Alice (This card be shuffling a card in play back into the deck, or even facedown ninja) and she creates a new randomNo for each and passes back Ea([CardId.NewRandomNo]) for each card.
  10. Bob should probably remember the old and new sets of Ea([CardId.Nonce]) for verification later when Alice reveals here public key.
  11. At the end of the game either of the following needs to happen.
    • Alice reveals here private key and Bob verifies that all the assertions about sets of cards he has remember and the deck of cards is a legal deck. Bob must also do the same.
    • Alice and Bob collects their assertions including the orignal encrypted deck list, and his private key and information about who one. All of this in then sent signed and encrypted to the TO who verifies the assertions and that Alice hasn't changed decks between rounds.
Actually it would be possible for Bob to verfies then deck hasn't changed without the TOs help if the TO published a signed hash of the decklist. Bob can reconstruct the decklist if Alice reveals her private key. However if you not the TO only use is to help collect the results and verify a against cheating so Alice can do so without revealling the contents of her deck. Since it is obviously impossible without new some really clever crypto to verify a decks legality without seing it if Alice doesn't want to reveal here deck a TO is needed.

In my play experience I suspect most casual games players will be happy to reveal ther decks or take cheating on trust, in tournament there will prolly be a TO who is a trusted third party anyway.

Oh you might have noticed I orginally said the keys didn't need that special property. I was wrong because in l5r at least there is a action which allows a player to look at a certain number of facedown cards. These could be cards on the top of his opponents deck. Unfortunately his opponent doesn;' get to see this cards. So the Poker hand exchange protocol needs to be used exactly as normal here. Which means we end up having the quaratic residue leak problem documented here.

Open ID

I've sort of started as I said before playing with LJ as well as this blog. However it would be nice to offer my readers (assuming I have any) a consolidated feed. Unfortuanely since some parts of my LJ journal require you to be an authenicated person in f world that currently has some difficulties.

However I noticed that LJ talks about openId on it login page , that and the fact I used it and my LJ login to look a someone deadjournal journal page prodded me into digging around and finding some more out.

The OpenId specification turns out to be pretty open and the team is primarly concern in just getting it working which is good.

So given I know I can both this and my LJ blogs as RSS feeds, I might create another blog site but which just gets the approriate authorised feed for the approtiate LJ and this site and presents them as a single blog. The bad news is this is essentially a MIM authentication attack so the site might have to be primarily AJAX or worse a damn program you have to run on you on computer.

Some design is clearly required here. Of course I could move all my content off both blogs onto my own openId compliant blog. But I'm not sure whether my friends who are LJers could add me a friend with just a non-LJ openId -although I believe this will be the case in time.

Monday, April 17, 2006

Finding contentment....

It's odd I haven't really found much to post about in the last few weeks.

I really think I ought to update this more often. In the mean time I've got myself an LJ account so I can read friends locked posts. Apparently on LJ you can keep posts private for friends. I can understand why though.

Anyway I've hand a contented Easter, spending time with my SWMBO. Much domestic stuff has been done.

The domesic stuff left me in an odd nimd state, so searching through old project I pulled up an old piece of code which I wrote for DOS 'back in the day' as they say. Unfortunately the way it was structed push the limits of he compiler (TP7) I using back then.

About 4 years ago I tried to rewrite the code using 'STL-style' in C++ they I could continue trying to play wiht the new idea the code encapsulates.

Yes, I'm not telling you what it does.

When I first wrote the code I had problems with 'value<->instance' equavalence as I had used STL container to try to store instances. Which of course isn't really what the STL does , as the STL has value containers.

In the meantime I've gather quite a bit of experience and understanding of the STL . So I thought I'd tidy it up and see If I could get it working.

As I said this was an historic project so I discovered that the basic Makefile I had used didn't use -Wall , as a result I missed the function where I forgot to include 'return foo;' which TP didn't need. These days I tend to adapt Makefiles from my last project.

Of course it still doesn't work for some reason the following code doesn't work.

               foo::iterator   end=a.end();
               foo::iterator   point=a.begin();
               if (point == end ) { ... }
Why I'm not sure. I need to check the STL spec, or look for a bug elsewhere.