Niko's Project Corner

Hash-based commitment schemes without a computer

Description A few simple hash algorithms which provide some security
Languages Pseudo
Tags En­cryp­tion
Stack Over­flow
Duration Spring 2016
Modified 7th May 2016

An in­ter­est­ing ques­tion was posted to crypto.stack­ex­ "Is there a sim­ple hash func­tion that one can com­pute with­out a com­puter?" Here are three pro­posed al­go­rithms based on Zo­brist hash­ing, RC4 and A5/1. These should be reasonably secure even against attacks with a calculator, except the one based on Zobrist hashing (but I don't know how to prove or dis-prove this claim). These constructs are especially well suited for com­mit­ment schemes.

The first al­go­rithm is based on Zo­brist hash­ing, which is com­monly used at chess en­gi­nes and other sim­ilar ap­pli­ca­tions to im­ple­ment trans­po­si­tion ta­bles. It is based on pre-gen­er­at­ing ran­dom in­te­gers to a look-up table, and then se­lec­tively XORing them to­gether to cal­cu­late a hash. This con­struct has tun­able pa­ram­eters which al­low for a trade-off be­tween se­cu­rity and the ease of com­pu­ta­tion.

For rel­atively high se­cu­rity it is pro­posed to use 64 ran­dom 80-bit in­te­gers. At crypto.stack­ex­ I sug­gested to use 256-bit in­te­gers but it turns out you don't need so many bits to be al­most cer­tain to have all of them lin­early in­de­pen­dent on GF(2).

Based on sim­ula­tions (see Fig­ure 1 for de­tails) 80 × 64 bits has ap­prox­imately 1 : 280 - 63.8 = 1 : 216.2 ≈ 1 : 104.877 probability of having non-full rank. A random 64 × 64 matrix has a non-full rank with a probability of about 71.1%. Each additional bit drops this by 50%. The simplest way to generate this pool of random integers is to flip n coins 64 · 80 / n times, as you get 1 bit of randomness / coin / toss. This table needs to be published and/or communicated to the 2nd party in advance and can be used multiple times. Numbers are identified as r0 , r1 , ..., r63.

Figure 1: Like­li­hood of non-full rank ap­prox­imately halves when an ex­tra bit (row) is added.

Com­mit­ment to a yes/no an­swer and be en­coded as the par­ity of a bi­nary in­te­ger v = 2i0 + 2i1 + ... + 2in (where ij-1 < ij). It is suggested to generate first 63 bits by random and choose the final bit according to the desired commitment. Then calculate the 80-bit "committed value" c = ri0 ⊕ ri1 ⊕ ... ⊕ rin, which is communicated to the 2nd party.

Cal­cu­lat­ing the com­mit­ment value c from from a m-bit in­put value v is O(m) op­er­ation, but re­cov­er­ing v from c is O(m3) effort. Thus with sufficiently large m it takes "too much" effort to reverse the process without access to a programmable calculator. However it is trivial to do on any phone or laptop.

An al­ter­na­tive scheme is based on the well-known (and se­ri­ously flawed) RC4 stream ci­pher. On a set­ting with no ac­cess to a com­puter it should be suf­fi­cient to use less than 256 × 8 bits of state. As lit­tle as 32 or 64 in­te­gers could be suf­fi­cient against an at­tacker who does not pos­sess a cal­cu­la­tor, but I have no clue how to eval­uate this.

The al­go­rithm it­self is well-de­scribed on Wikipedia and its op­er­ations are shown in Fig­ure 2. It is a bit of an open ques­tion what is the best way of seed­ing the ini­tial state, how many of the ini­tial bits to skip and how many bits of out­put is needed for given se­cu­rity cri­te­ria. A sim­ple so­lu­tion is to use the stan­dard key-schedul­ing al­go­rithm, dis­card first 3 · n out­put bits (n be­ing the num­ber of in­ter­nal state num­bers) and then keep­ing the de­sired amount of out­put (like 80 or 128 bits) as the com­mit­ted value. Even with all the flaws of RC4-based hash­ing, with­out ac­cess to an com­puter it should be dif­fi­cult to re­cover the used key from this al­go­rithm's out­put.

Figure 2: RC4 steps from Wikipedia, just sum­ma­tion and ran­dom ac­cess to a small chunk of mem­ory.

The fi­nal pro­posed al­go­rithm is sim­ilar to RC4: A5/1 which used to en­crypt GMS traf­fic. It has 19 + 22 + 23 = 64 bits of state, so you'd ac­tu­ally just need 64 coins to rep­re­sent the state (heads vs. tails). It con­sist of only sim­ple op­er­ations but they are quite ver­bose to ex­ecute man­ually. Sug­gested pro­to­col is to com­mit to an ini­tial state, skip first 64 - 192 bits and pub­lish next 80 bits as the com­mit­ted value. Again it should be dif­fi­cult to re­cover the ini­tial state by only ob­serv­ing this out­put.

Figure 3: A5/1 steps from Wikipedia, con­sist­ing of only sim­ple XOR-op­er­ations and look-ups.

Related blog posts: