Some background information:

In contract bridge, there are 0xAD55E315634DDA658BF49200 (just under 2^96) possible bridge deals. Since the 1990s, bridge deals for major tournaments were generated on PCs and dealt using dealing machines. Initially, the deals were generated using a PRNG with very low periods with dubious seeding (no CryptGenRandom back then and DOS was still widely used) and dealing algorithms that introduce bias with the modulo operator, which predictably caused problems when deals were found to be repeated.

This all changed around 1999 when Hans van Staveren released a program called Big Deal, documenting the issues with existing dealers and how Big Deal fixes them to ensure:

  1. The software should be able to generate every possible bridge deal, since that is also possible with manual dealing
  2. The software should generate every deal with the same probability, without being influenced by the board number, previous hands or any other circumstance
  3. It should be impossible to predict deals, even after having seen all other deals in the session

Big Deal's document acknowledges that it's use of the RIPEMD-160 as a CSPRNG runs into a Birthday Paradox issue: H( H(associated data) || 160 bit seed || 32 bit counter )

Which comes to my first question:

Could Big Deal have avoided the Birthday Paradox problem by loading H(associated data) XOR seed into the RIPEMD-160 state (instead of hashing them in) before hashing the 32 bit counter?

I am planning to propose the use of my modern re-implementation of Big Deal. In this implementation, I chose to use Gimli with a 256 bit seed and a 128 bit counter (actually, 2x 32 bit and 1x 64 bit counters). This is done simply by loading the 384 bit Gimli state with the 256 seed appended with the 128 bit counter. I run the Gimli permutation function and extract the first 96 bits of the new state. If the value >= 0xAD55E315634DDA658BF49200 I rerun the permutation again.

So here is my second question:

Are there any issues with the way I am using Gimli as a CSPRNG?

Thank you

  • 2
    $\begingroup$ My advice would be to use HMAC-DRBG (from 800-90A), based on HMAC-SHA512; the performance isn't as good as Gimli, however this application doesn't exactly need earth-shattering performance (and you'll be using a primitive in the way it was designed to be used). Gimli is probably "good enough", though, if you have your heart set on it... $\endgroup$
    – poncho
    Jun 9, 2020 at 20:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.