The Previous discussion can be found
[here]. Please continue the discussion now in this
DiscussionArea on this page below:
Where text has been copied here from email (with the senders permission) my apologies if I have messed up your formatting anywhere. Thanks. --DouglasReay
why have a sharedtext?
[
HalFinney] wrote: I don't see that sharedtext plays much of a role here. It is the 64 bits of usertext which is providing privacy. Everyone knows sharedtext so there is no particular advantage from it.
- DouglasReay wrote: If we just took the digest of a usertext the user could totally specify, they could spend years in advance finding 2 usertexts that gave the same digest.
- By including a sharedtext that includes information like the time, this makes it much much harder for the user to predict in advance what sharedtext they need to find usertexts for to give collisions. And even if they do find a collidng pair, it prevents re-use.
- [HalFinney] wrote: Okay, that's a good idea.
[PaulCrowley] wrote:
- The house publishes a list of parties (including itself)
- All parties privately choose a random seed
- All parties reveal a hash of their seed
- All parties except the house reveal their seeds
- The house hashes all seeds including its own in the order of the list published
- DouglasReay wrote: I'd prefer if people didn't have a completely free choice of random seed, to help prevent them using the birthday-party effect to pre-generate collisions
- [MoonShadow] wrote: Split step 4 up: make all revealing parties reveal their seeds one bit at a time (so everyone's bit 0 are known before any bit 1 are revealed, etc.) This forces you to commit to one of your many precalculated birthday seeds that all hash to the same thing before you know enough of anyone else's to be able to decide which one benefits you most. Hm. The house can still usefully precalculate hash collisions. Maybe use something more resistant to collisions than a crypto hash in order to commit to your seed? What is there? Sign your seed along with a load of salt and publish the signature? Paul, you suggested 160-bit seeds above to resist birthday attacks; how computationally hard is it to find two 160-bit strings that have the same MD5 hash?
- DouglasReay wrote: revealing the seeds one bit at a time sounds nice, but I'm not sure it could be done efficiently enough in practice over the internet between multiple players. It would certainly make tunneling over email problematic.
does it work?
[
HalFinney] wrote: Yes, I think it is fair (but it's not a
[shuffle]).
The consensus of the Cambridge University Computer Laboratory Security Group informal meeting seemed to agree. It was noted that once a host has the output they could use a fake user (in a multi-player game) to default if they thought the output bad for them, and that casinos who finished games as "fail" too frequently should be suspected.
which hash algorithm to use?
[
HalFinney] wrote: Should you negotiate a hash? I don't know what to say about hashes right now. I don't think negotiation is that good an idea for these kinds of protocols, but everything is up in the air at the moment. Most people that I've talked to think Tiger has had insufficient cryptanalysis to be trusted at this point, although it will probably start getting more attention now that so many hashes are in trouble.
- DouglasReay wrote: Points in favour of multiple hashes: Some people won't consider an algorithm unless it uses a known quantity such as MD5. Some people won't consider an algorithm unless is doesn't use MD5.
- DouglasReay wrote: Points against multiple hashes: i a 3 or more participant game Player 1 will want to verify that Player 2's revealed plaintext matches their previously revealed digest of it - which means that if Player 1 and the Host negotiate Algorithm X and Player 2 and the Host negotiate Algorithm Y, there is a problem.
best length for the plaintext?
[Vitenka] wrote: Given the posisble gains to a casino of cheating on, say, 1% of rolls to clients who connect fewer than a thousand times - which would be basically undetectable... How big would the hash have to be to make it unlikely that the cheating client doesn't find many clashes in the hash space?
- [PaulCrowley] wrote: The house seed must be 160-bits, to avoid key collision attacks. I'm not sure if all parties need 160 bit seeds, but I fear birthday attacks or similar on smaller seeds.
[
HalFinney] wrote: It's not clear to me from your description what exactly the input is to the hash function. I think it's the sharedtext concatenated with the usertext, where the usertext is basically a random 64 bit quantity. (In your
[sci.crypt posting] you said 1000 bits, which is more than necessary.) Then when they all open their inputs, you take the 64 bit usertexts modulo numberOfOutcomes
? to get the inputs which are all added up (again mod numberOfOutcomes
?) to get the result.
- [DouglasReay] wrote:
plaintext = sharedtext (250chars) string add to usertext (250chars) = 500chars where chars are hex (0123456789ABCDEF) carrying 4 bits info
[
HalFinney] wrote: I might go a little bigger than 64 bits here, but not as big as 1000. I think the crypt21 project I told you about used 160 bits. For the sizes, as I said above, somewhere between 64 and 1000 will be a good medium. I might go a little bigger than 160 if you really think this will be in use years from now. The next logical size would be either 192 or 256. I really don't think it matters much once you are in this range.
DouglasReay write: Someone at the Cambridge University Computer Laboratory Security Group suggested 150 bits should be sufficient. I think I'd like to see it larger than that, because making the usertext fixed length simplifies things, and I'd like to see it significantly larger (say 150 bits larger) than 55 factorial (52 card deck + 3 jokers).
Cryptographic Pseudo-Random Number Generators
[PaulCrowley] wrote:
- The house publishes a list of parties (including itself)
- The house hashes all seeds including its own in the order of the list published
- The result is used to key a CPRNG (say AES-192 in CTR mode)
- The rolls are generated using this CPRNG using standard algorithms for converting a random bitstream to fair dice rolls (or card selections or whatever)
- [DouglasReay] wrote: as opposed to taking the modulo of the inputs? Yes, that's possible. But I think one could do that anyway, as Fairdice uses a multiple precision integer maths library. So use fairdice to generated a big number, then host app can do what it wants with it, including using it as a key for a CPRNG.
shuffling
[
HalFinney] wrote: Card shuffling is a harder problem because the probabilities must change with every card, and some cards aren't shown to everyone. You might want to take a look at
[crypt21] which also has some code to implement fair dice rolling and card shuffling.
- [DouglasReay] wrote: Fairdice shuffles a deck by generating a random number then translating that to a particular deck. The casino tells each player what card they have as the desk is dealt. At the end of the game, the players can use the earlier revealed hashes to confirm the casino did use the fairly shuffeled deck.
- [HalFinney] wrote: Yes, that will work for a game like, say, blackjack, where all the players' cards are revealed.
- [DouglasReay] wrote: I have one participant (the casino or 'host') who does get to see all the cards. It is not symmertric.
- [HalFinney] wrote: Yes, the crypt21 card system is designed for games like poker where it is important that uncalled bluffs never get exposed, so that players don't learn more than they should about other players' bluffing strategy. It uses a very complicated (and slow) algorithm to shuffle the deck.
- The basic idea is to create an ElGamal public key whose private part is shared among all the players, then to encrypt the cards to that public key. To shuffle, each player in turn randomly permutes the cards and re-encrypts each one, then proves (this is the hard part) that they have behaved correctly. Then to expose a card the players cooperate to decrypt it.
- [DouglasReay] wrote: If you have a host who is acting as the dealer but not actually playing a hand themselves, and who is allowed to see the betting strategies, then could one do the shuffle as 52 seperate fairdice generations, and at the end of the game have the host reveal its usertexts only for those cards that got revealed during play?
- [HalFinney] wrote: Hmmm, I'd have to think about that. There might be a way to do it, but it's not clear. The problem is that some cards get revealed only to one player, and I can't see how to let the dealer show that he is behaving properly in the general case where there is partial information about the cards. If you have any ideas along this line I'd love to hear them.
- DouglasReay wrote: I put this problem to RossAnderson?, who thinks he has a way. Details may be forthcoming.
[PeterTaylor] observes that you don't need to do it 51 times for a deck of cards. You need to generate one integer in [0, 51!). That's about 220 bits, so if you're using a 256-bit hash it's just one exchange. The algorithm is just a base change. Divide by 51! to get a number in [0, 51], divide the remainder by 50!, etc. Then with your array arr, and an array deck containing the cards, for
(int i = 51; i >= 0; i--) swap(deck, i, arr[i]);
why publish digests?
[PaulCrowley] wrote:
- All parties choose a 160-bit random seed
- The "house" publishes the hash of its seed
- All parties reveal their seeds to the house
- The house publishes all seeds except its own
- At the end of the game, the house publishes its seed; all parties can verify that the rolls were generated fairly.
This assumes that the "house" is deterministic - ie it doesn't matter that the house gets to know the result of all random rolls at the start of the game, because they don't make any decisions.
- [PeterTaylor] wrote: You still need some way for the house to prove that the seeds it publishes are the seeds it was given.
- [DouglasReay] wrote: Why would it matter to a player who provided the other seeds? It only matters to a player that their seed is included. And since they will be able to recognise their own seed, no authentication is needed.
- [MoonShadow] wrote: It matters because a player could be colluding with the house - the house knows its own seed, so could pick one for the colluding player once it knows everyone else's and publish it when it's publishing the legitimate ones, and the player just say "yes, that's the one I picked". The trick is that you don't want it to be possible for any party to know everyone else's seed before publically committing to theirs.
- [DouglasReay] wrote: Signing won't stop that. A real person could still collaborate with the house. The only way is to use a two part protocol where everyone publishes a hash of their seed before anyone publishes their seed.
(your new thread here)
CategoryCryptography