The Frogbit Hash Function

Table of contents

Introduction

This document is a detailed procedural specification for the Frogbit hash function, with no attention paid to justification of the algorithm. The other document entitled "How the Frogbit is used in a hash function mode" gives explanations for the present specification.

Notational conventions

• All integers and counters are unsigned;
  
  
• X XOR Y represents the bit-wise "exclusive or" of integers X and Y expressed as a binary strings;
  
  
• X AND Y represents the bit-wise "and" of integers X and Y expressed as a binary strings;
  
  
• X>>>Y represents the integer X shifted to the right by Y binary positions, which is the same as the integer division of X by 2Y;
  
  
• X[] represents an array X of some fixed dimension;
  
  
• X[Y] represents the array indexing operation, referencing the Y'th item in the array, where the first array element is the 0'th one;
  
  
• X MOD Y represents the remainder of the integer X divided by the integer Y;
  
  
• d:3, d:2, d:1, and d:0 represent the bits of weight 8, 4, 2, and 1, respectively, of the binary representation of an integer d;
  
  
• "1F3A"H represents the integer 7994 expressed in the hexadecimal notation.

Overall Operation of the Frogbit Hash Function

The Frogbit hash function processes an arbitrary message of length up to 232 bits long. At the end of the message, a fixed length 160 bits hash code is available as a message fingerprint. Processing is done one bit at a time. Accordingly, the procedural specification is broken in four parts:

1. initialization procedure,
2. message bit procedure,
3. end of message procedure, and
4. hash code bit retrieval procedure ("hash retrieval procedure").

The initialization procedure is executed once at the beginning of the message. The message bit procedure is executed once for each bit of the message in sequence. The end of message procedure is executed once after all bits of the message has been processed. The hash retrieval procedure is executed 160 times after the end of message procedure.

Some "generic bit processing" is used for the message bit procedure and the end of message procedure.

Note:

The order of bit processing for messages structured in bytes is outside the scope of this specification. Nonetheless, the reader is reminded that serial network transmission occurs from the least significant bit to the most significant bit.

Internal Organization of the Frogbit Hash Function

To process a message, the Frogbit hash function uses

1. ten predefined pseudo-random generators ("generators"),
2. the core Frogbit algorithm, and
3. two Cipher Block Chaining processes ("CBC processes"), each one accumulating a portion of the message hash code (respectively the "main" CBC process and the "final" CBC process).

The ten generators are numbered from 0 to 9, from the "0'th generator" to the "9'th generator".

Note:

The generators are an adaptation of "twisted generalized feedback shift registers" (TGFSR, see Makoto Matsumoto and Yoshiharu Kurita, "Twisted GFSR Generators", ACM Transactions on Modeling and Computer Simulations, Vol. 2, No. 3, July 1992, pp 179-194). There are three changes from the original TGFSR proposal: 1) only the least significant bit of the generator output is used at each step, 2) the procedural steps 3 and 5 of the original TGFSR algorithm are reversed (as an inconsequential implementation optimization), and 3) two TGFSRs, using word sizes of respectively 8 bits and 7 bits, are interlaced in 16 bit binary variables and parameters.

According to the theory on pseudo-random generation, a TGFSR from which a single output bit is used at each step is strictly equivalent to a "linear feedback shift register" (LFSR) with a generating polynomial that is primitive, has a degree equal to the total TGFSR state bit count, and has a reasonable number of non-zero coefficients. In the present specification, these primitive polynomials have degrees 49 or 56, and from 11 to 23 non-zero coefficients.

State Variables

For each generator, the state information comprises

• a 32 bit counter K, and
• a state array X[] of integers 16 bits wide (the dimension of the array X[] is an implementation parameter L which is at least 7).

For the core Frogbit algorithm, the state information comprises

• a bit S
• a bit R
• a bit d:0, which is significant only if the bit R is 1,
• an integer D, which is in the range 0 to 9 inclusive, and
• an array T[] of integers which are in the range 0 to 9 inclusive (the dimension of the array T[] is 10).

For the main CBC process, the state information comprises

• an array C[] of bits (the dimension of C[] is 96),
• an index Y into the array C[].

For the final CBC process, the state information comprises

• an array F[] of bits (the dimension of F[] is 64),
• an index Z into the array F[].

For the hash retrieval procedure, the state information comprises

• an index W.

Fixed Parameters

For the i'th generator, the fixed parameters are

• an integer M, as follows:

       i       M
       0       1
       1       1
       2       3
       3       3
       4       4
       5       4
       6       5
       7       5
       8       6
       9       6,

• a coefficient array A[] (the dimension of A[] is 4), where A[0]=0, A[1]="5555"H AND A[3], A[2]="AAAA"H AND A[3], and A[3] is as follows:

       i       A[3]
       0       "9EC1"H
       1       "720F"H
       2       "9F56"H
       3       "713A"H
       4       "B44B"H
       5       "674A"H
       6       "9B52"H
       7       "61B9"H
       8       "9F56"H
       9       "713A"H, and

• fixed seed values for first 7 entries of the state array X[], as follows

i  seed values for first 7 entries of the state array X[]
0  "BE46"H, "B28A"H, "3503"H, "8DE5"H, "021C"H, "A474"H, "B14D"H
1  "4DDE"H, "3861"H, "2541"H, "6780"H, "3124"H, "5C50"H, "510C"H
2  "049F"H, "21DC"H, "9795"H, "05D9"H, "2E96"H, "22CA"H, "954D"H
3  "3ADB"H, "4348"H, "7DD4"H, "6A3E"H, "7CC3"H, "36E0"H, "394A"H
4  "163D"H, "2866"H, "90F0"H, "3CDC"H, "20F0"H, "851E"H, "B04A"H
5  "2B67"H, "7511"H, "3427"H, "4F89"H, "7B59"H, "5908"H, "29EE"H
6  "AFC8"H, "3205"H, "382F"H, "1323"H, "0CE7"H, "2E3C"H, "B82E"H
7  "411B"H, "7D86"H, "6997"H, "6D6C"H, "6908"H, "4AE2"H, "7E93"H
8  "08E1"H, "1718"H, "BD72"H, "2FB0"H, "8F63"H, "AA56"H, "1847"H
9  "055C"H, "7DB9"H, "7C3F"H, "1A56"H, "0F0F"H, "5A99"H, "5D17"H.

Note:

A tiny TGFSR generator was used to fill the above constants, using only the least significant bit of each step. Its parameters are w=8 (word size), n=2 (size of state array), m=1, and a="E7"H (from polynomial x8+x7+x6+x5+x2+x+1). Its initial state was set to "81"H, "81"H.

The tiny TGFSR generator output filled each of the above state arrays in sequence. For each array, the bits of even weight (20, 22, ...) are filled first and then the bits of odd weight (21, 23, ...) are filled in a second pass. Filling these bits starts with the least significant bit of the first word, and ends with the more significant bits of the last word. In this process, the following bits are skipped and set to zero: the bit of weight 215 in all words of arrays 1, 3, 5, 7, and 9, and also the bit of weight 214 in all words of arrays 0, 2, 4, 6, and 8.

In an implementation on an 8 bit processor, the TGFSR generators might be not interlaced, in which case the filling by the tiny TGFSR generator is more natural. The high bits that are skipped correspond to TGFSRs with a word size of 7 bits.

For the main CBC process, the fixed parameter is

• a fixed initialization vector for the array C[] of bits, as follows:

       bits of the initialization vector for the array C[]
       0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1,
       0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0,
       1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0,
       1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0,
       0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1,
       0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0.

Note:

The continuation of the tiny TGFSR generator output filled the above initialization vector.

Initialization Procedure

Each generator is initialized by setting the parameters as indicated above and letting K=6.

The core Frogbit algorithm is initialized by setting S=0, R=0, D=0, and T[i]=i for any i from 0 to 9 inclusive.

The main CBC process is initialized by setting the bit array C[] to the fixed initialization vector as indicated above, and by setting Y=0.

The final CBC process is initialized by setting Z=0.

The hash code bit retrieval procedure is initialized by setting W=0.

Generic Bit Procedure

In the generic bit procedure, a single one of the ten generators is exercised, and produces two pseudo-random bits, respectively represented by k1 and k2. The generator that is exercised is the D'th generator.

When a generator is exercised, the counter K is first incremented by 1, and then the following assignment is performed:

X[K MOD L]=       X[(K-7+M) MOD L]
            XOR  (X[(K-7)   MOD L] >>> 2)
            XOR A[X[(K-7)   MOD L] MOD 4],

and the bit k1 and k2 are set as follows:

k1= X[K MOD L] AND 1,
k2=(X[K MOD L] AND 2)>>>1.

Note:

The above procedural specification corresponds to the TGFSR parameters <w,n,m,a> listed below, respectively for k1 and k2 of each generator:

      Generator       Parameters for k1       Parameters for k2
          0           <7,7,1,"69"H>           <8,7,1,"B8"H>
          1           <8,7,1,"C3"H>           <7,7,1,"53"H>
          2           <7,7,3,"7E"H>           <8,7,3,"B1"H>
          3           <8,7,3,"D4"H>           <7,7,3,"47"H>
          4           <7,7,4,"69"H>           <8,7,4,"C3"H>
          5           <8,7,4,"B8"H>           <7,7,4,"53"H>
          6           <7,7,5,"5C"H>           <8,7,5,"B1"H>
          7           <8,7,5,"95"H>           <7,7,5,"4E"H>
          8           <7,7,6,"7E"H>           <8,7,6,"B1"H>
          9           <8,7,6,"D4"H>           <7,7,6,"47"H>

Then a boolean transformation of 6 bits of input into 7 bits of output occurs. The 6 bits of input are

• the pseudo-random bit k1,
• the pseudo-random bit k2,
• the generic input bit m,
• the core Frogbit state bit d:0,
• the core Frogbit state bit R,
• the core Frogbit state bit S,

and the 7 bits of output are

• an encrypted bit e,
• the bits d:3, d:2, d:1, d:0, the latter one being part of the updated core Frogbit state,
• the updated core Frogbit state bit R,
• the updated core Frogbit state bit S.

The boolean transformation is specified by the following table:

 <========= inputs ========>    <========== outputs ===========>
               <== state ==>                       <== state ==>
 k1   k2    m   d:0   R    S    e   d:3  d:2  d:1  d:0   R     S

 0     0    0   0/1   0    0    0    ?    ?    ?    0    1     0
 0     0    0   0/1   0    1    0    0    0    0    0    0     0
 0     0    0    0    1    0    0    0    1    1    0    0     0
 0     0    0    0    1    1    0    0    0    1    0    0     0
 0     0    0    1    1    0    0    1    0    0    0    0     0
 0     0    0    1    1    1    0    0    1    0    0    0     0
 0     0    1   0/1   0    0    1    0    0    0    0    0     1
 0     0    1   0/1   0    1    1    ?    ?    ?    0    1     1
 0     0    1    0    1    0    1    0    0    1    0    0     1
 0     0    1    0    1    1    1    0    1    1    0    0     1
 0     0    1    1    1    0    1    0    1    0    0    0     1
 0     0    1    1    1    1    1    1    0    0    0    0     1
 0     1    0   0/1   0    0    1    ?    ?    ?    1    1     0
 0     1    0   0/1   0    1    1    0    0    0    1    0     0
 0     1    0    0    1    0    1    0    1    1    1    0     0
 0     1    0    0    1    1    1    0    0    1    1    0     0
 0     1    0    1    1    0    1    1    0    0    1    0     0
 0     1    0    1    1    1    1    0    1    0    1    0     0
 0     1    1   0/1   0    0    0    0    0    0    1    0     1
 0     1    1   0/1   0    1    0    ?    ?    ?    1    1     1
 0     1    1    0    1    0    0    0    0    1    1    0     1
 0     1    1    0    1    1    0    0    1    1    1    0     1
 0     1    1    1    1    0    0    0    1    0    1    0     1
 0     1    1    1    1    1    0    1    0    0    1    0     1
 1     0    0   0/1   0    0    1    ?    ?    ?    0    1     0
 1     0    0   0/1   0    1    1    0    0    0    0    0     0
 1     0    0    0    1    0    1    0    1    1    0    0     0
 1     0    0    0    1    1    1    0    0    1    0    0     0
 1     0    0    1    1    0    1    1    0    0    0    0     0
 1     0    0    1    1    1    1    0    1    0    0    0     0
 1     0    1   0/1   0    0    0    0    0    0    0    0     1
 1     0    1   0/1   0    1    0    ?    ?    ?    0    1     1
 1     0    1    0    1    0    0    0    0    1    0    0     1
 1     0    1    0    1    1    0    0    1    1    0    0     1
 1     0    1    1    1    0    0    0    1    0    0    0     1
 1     0    1    1    1    1    0    1    0    0    0    0     1
 1     1    0   0/1   0    0    0    ?    ?    ?    1    1     0
 1     1    0   0/1   0    1    0    0    0    0    1    0     0
 1     1    0    0    1    0    0    0    1    1    1    0     0
 1     1    0    0    1    1    0    0    0    1    1    0     0
 1     1    0    1    1    0    0    1    0    0    1    0     0
 1     1    0    1    1    1    0    0    1    0    1    0     0
 1     1    1   0/1   0    0    1    0    0    0    1    0     1
 1     1    1   0/1   0    1    1    ?    ?    ?    1    1     1
 1     1    1    0    1    0    1    0    0    1    1    0     1
 1     1    1    0    1    1    1    0    1    1    1    0     1
 1     1    1    1    1    0    1    0    1    0    1    0     1
 1     1    1    1    1    1    1    1    0    0    1    0     1

The boolean transformation updates the Frogbit state bits S, R, and d:0. The output bit e is the result of the generic bit processing. If the output bit R is 1, the generic bit processing is complete.

If the output bit R is 0, the Frogbit state integer D and array T[] are updated.

• The updated D is set as T[d] (this refers to the original T[] before the update process takes place), where d is an integer from 0 to 9 whose binary representation is the output bits d:3, d:2, d:1, and d:0.
• The updated T[] is a permutation of the original T[]. There are twenty possible permutations, and the choice is made based on the original D and the original Frogbit state bit S (before the boolean transformation takes place), according to the following table:

D S Permutation

0 1 temp=T[0]; T[0]=T[5]; T[5]=T[2]; T[2]=T[7]; T[7]=temp;
    temp=T[1]; T[1]=T[8]; T[8]=T[6]; T[6]=T[4]; T[4]=T[3]; T[3]=T[9];
    T[9]=temp;

0 1 temp=T[0]; T[0]=T[2]; T[2]=T[7]; T[7]=temp;
    temp=T[1]; T[1]=T[3]; T[3]=T[6]; T[6]=T[9]; T[9]=T[4]; T[4]=T[8];
    T[8]=T[5]; T[5]=temp;

1 0 temp=T[0]; T[0]=T[6]; T[6]=T[8]; T[8]=T[9]; T[9]=T[5]; T[5]=T[7];
    T[7]=T[1]; T[1]=temp;
    temp=T[2]; T[2]=T[4]; T[4]=T[3]; T[3]=temp;

1 1 temp=T[0]; T[0]=T[6]; T[6]=temp;
    temp=T[1]; T[1]=T[5]; T[5]=T[3]; T[3]=T[4]; T[4]=T[2]; T[2]=T[8];
    T[8]=T[7]; T[7]=T[9]; T[9]=temp;

2 0 temp=T[0]; T[0]=T[3]; T[3]=T[6]; T[6]=T[5]; T[5]=T[1]; T[1]=T[2];
    T[2]=temp;
    temp=T[4]; T[4]=T[8]; T[8]=T[7]; T[7]=T[9]; T[9]=temp;

2 0 temp=T[0]; T[0]=T[6]; T[6]=T[7]; T[7]=T[3]; T[3]=T[1]; T[1]=T[2];
    T[2]=T[9]; T[9]=temp;
    temp=T[4]; T[4]=T[5]; T[5]=T[8]; T[8]=temp;

2 1 temp=T[0]; T[0]=T[4]; T[4]=T[3]; T[3]=T[7]; T[7]=T[6]; T[6]=T[1];
    T[1]=T[8]; T[8]=T[5]; T[5]=temp;
    temp=T[2]; T[2]=T[9]; T[9]=temp;

3 0 temp=T[0]; T[0]=T[5]; T[5]=T[4]; T[4]=temp;
    temp=T[1]; T[1]=T[9]; T[9]=T[8]; T[8]=T[6]; T[6]=T[2]; T[2]=T[3];
    T[3]=T[7]; T[7]=temp;

4 0 temp=T[0]; T[0]=T[8]; T[8]=T[9]; T[9]=T[5]; T[5]=T[3]; T[3]=T[2];
    T[2]=T[1]; T[1]=temp;
    temp=T[4]; T[4]=T[6]; T[6]=T[7]; T[7]=temp;

4 1 temp=T[0]; T[0]=T[9]; T[9]=T[7]; T[7]=T[8]; T[8]=T[1]; T[1]=T[4];
    T[4]=T[2]; T[2]=T[6]; T[6]=temp;
    temp=T[3]; T[3]=T[5]; T[5]=temp;

5 0 temp=T[0]; T[0]=T[7]; T[7]=T[2]; T[2]=T[4]; T[4]=T[1]; T[1]=T[6];
    T[6]=T[5]; T[5]=T[9]; T[9]=temp;
    temp=T[3]; T[3]=T[8]; T[8]=temp;

5 1 temp=T[0]; T[0]=T[1]; T[1]=T[4]; T[4]=T[7]; T[7]=T[5]; T[5]=T[2];
    T[2]=T[8]; T[8]=T[3]; T[3]=temp;
    temp=T[6]; T[6]=T[9]; T[9]=temp;

6 0 temp=T[0]; T[0]=T[7]; T[7]=T[6]; T[6]=T[3]; T[3]=temp;
    temp=T[1]; T[1]=T[4]; T[4]=T[9]; T[9]=T[2]; T[2]=T[5]; T[5]=T[8];
    T[8]=temp;

6 1 temp=T[0]; T[0]=T[3]; T[3]=T[5]; T[5]=T[2]; T[2]=temp;
    temp=T[1]; T[1]=T[9]; T[9]=T[7]; T[7]=T[4]; T[4]=T[6]; T[6]=T[8];
    T[8]=temp;

7 0 temp=T[0]; T[0]=T[8]; T[8]=T[4]; T[4]=T[2]; T[2]=T[1]; T[1]=T[9];
    T[9]=T[3]; T[3]=temp;
    temp=T[5]; T[5]=T[7]; T[7]=T[6]; T[6]=temp;

7 1 temp=T[0]; T[0]=T[9]; T[9]=T[6]; T[6]=T[3]; T[3]=T[1]; T[1]=T[5];
    T[5]=temp;
    temp=T[2]; T[2]=T[4]; T[4]=T[7]; T[7]=T[8]; T[8]=temp;

8 0 temp=T[0]; T[0]=T[7]; T[7]=T[2]; T[2]=T[6]; T[6]=T[1]; T[1]=T[3];
    T[3]=T[9]; T[9]=T[8]; T[8]=temp;
    temp=T[4]; T[4]=T[5]; T[5]=temp;

8 1 temp=T[0]; T[0]=T[4]; T[4]=T[1]; T[1]=T[7]; T[7]=T[8]; T[8]=temp;
    temp=T[2]; T[2]=T[9]; T[9]=T[3]; T[3]=T[5]; T[5]=T[6]; T[6]=temp;

9 0 temp=T[0]; T[0]=T[2]; T[2]=T[3]; T[3]=T[8]; T[8]=temp;
    temp=T[1]; T[1]=T[7]; T[7]=T[5]; T[5]=T[6]; T[6]=T[4]; T[4]=T[9];
    T[9]=temp;

9 1 temp=T[0]; T[0]=T[1]; T[1]=T[6]; T[6]=T[7]; T[7]=T[3]; T[3]=T[4];
    T[4]=temp;
    temp=T[2]; T[2]=T[5]; T[5]=T[9]; T[9]=T[8]; T[8]=temp;

Message Bit Procedure

The message bit is exclusive-or'ed with the bit C[Y], and the result is passed as input to the generic bit processing. The output of the generic bit processing is stored in C[Y]. Then, Y is incremented "MOD 96", as in Y=(Y+1) mod 96.

End of Message Procedure

For the specification of the end of message procedure, a "final bit procedure" which takes one bit of input, is conveniently defined as follows:

The input bit is exclusive-or'ed with the bit F[Z], and the result is passed as input to the generic bit processing. The output of the generic bit processing is stored in F[Z]. Then, Z is incremented "MOD 64", as in Z=(Z+1) mod 64.

The end of message procedure is a sequence of operations. First, the following operation is repeated 32 times:

The bit C[Y] is passed as input to the generic bit processing. The output of the generic bit processing is stored in C[Y]. Then, Y is incremented "MOD 96", as in Y=(Y+1) mod 96.

Then, the following operation is repeated 64 times:

The bit C[Y] is passed as input to the generic bit processing. The output of the generic bit processing is stored in C[Y] and in F[Z]. Then, Y is incremented "MOD 96", as in Y=(Y+1) mod 96, and Z is incremented "MOD 64", as in Z=(Z+1) mod 64.

Then, a partial image of the current state is taken. This partial image consists of a copy of

• the bits S, R, and d:0,
• the integer D,
• the table T[], and
• the counter K for every generator.

Then, the image of the bit S is passed to the final bit procedure.

Then, the image of the bit R is passed to the final bit procedure.

Then, if the image of the bit R is 1, the image of the bit d:0 is passed to the final bit procedure.

Then, the 4 bits of the image of the integer D are passed to the final bit procedure, starting with the least significant one.

Then, for each image of the array element T[i] in sequence for i=0 to 9 inclusive, the 4 bits of this image of the integer T[i] are passed to the final bit procedure, starting with the least significant bit.

Then, for each i'th generator in sequence for i=0 to 9 inclusive, the 32 bits of the image of the counter K are first reduced by 6 and then passed to the final bit procedure, starting with the least significant bit.

Finally, the following operation is repeated 64 times:

The bit F[Z] is passed as input to the generic bit processing. The output of the generic bit processing is stored in F[Z]. Then, Z is incremented "MOD 64", as in Z=(Z+1) mod 64.

---

Hash Retrieval Procedure

If W<96, the bit C[(Y+W) MOD 96] is returned and W is incremented; otherwise, the bit F[(Z+W-96) MOD 64] is returned and W is incremented.

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900