The present hypertext document gives explanations for the possible construction of hash functions from the core Frogbit algorithm. A complete detailed specification for such a hash function is given in another document entitled "The Frogbit Hash Function (procedural specification)".
The following notation will be useful to disclose the use of the
Frogbit algorithm for a hash function: let
ei=F(mi,Gi) and
Gi+1=F'(mi,Gi)
represent, respectively, the encryption
F() of cleartext message bit
mi (for
0<=i<n where
n is the message length) into the ciphertext bit
ei using the Frogbit state
Gi, and the internal Frogbit state transformation
F'() that occurs during this encryption step.
The CBC-MAC (Cipher Block Chaining-Message Authentication Code) method
can be adapted to the Frogbit algorithm. This method requires the
definition of a block size
b. Then, the functions
ei=F(mi,Gi) and
Gi+1=F'(mi,Gi)
are replaced by
ei=F(mi XOR
ei-b,Gi) and
Gi+1=F'(mi XOR
ei-b,Gi),
respectively. The bits
e-b,e-b+1,...,e-1
constitute an arbitrary
b bit initialization vector. Note that message padding to an exact
block boundary is not required by the bit-oriented Frogbit cipher. But the
last
b bits of the message deserve some special attention to prevent attacks
on the last bits of the message. This requires an extra block of
encrypted data at the end of the ciphertext, as in
en+i=F(en+i-b,Gn+i) and
Gn+i+1=F'(en+i-b,Gn+i), for
0<=i<b.
With the CBC-MAC method applied to the Frogbit cipher,
en,en+1,...,en+b-1
represents the CBC-MAC value.
The initial Frogbit state
G0 is a public parameter of the secure hash function. The final state
(notation
Gn+b) is encoded in the hash result, with only minor loss of information.
Then,
G0 and
Gn+b are the starting and ending points of a kind of random walk
influenced by the message contents. It is hard to find a collision, that is two
message substrings
mi,mi+1,...,mi+k-1 and
m'i,m'i+1,...,m'i+k-1
that start and end with the same pair of states
Gi and
Gi+k. The CBC processing coerces the substrings
ei,ei+1,...,ei+k-1 and
e'i,e'i+1,...,e'i+k-1.
Other public parameters are needed for the hash function, to describe the underlying pseudo-random sequences. In this context, the ten key streams turn into long, linearly independent, and constant binary strings; a pseudo-random generator is little more that a convenient specification tool (in theory, the complete sequences could be published). A distinctive characteristic of the Frogbit secure hash function is this stillness of the ten independent keystreams. This constant data is intrinsically part of the definition of the hash function. It should represent an important difficulty for cryptanalysis attempts at the Frogbit secure hash function.
The suggested hash algorithm comprises four sequences of Frogbit
processing: i) the CBC processing of the complete message, ii) a CBC
closing block processing, concluding with the relevant final state to be
encoded, iii) the CBC processing of this encoded final state, and iv)
another CBC closing block processing. The block size
b applicable to the message CBC processing need not be equal to the
block size
b' applicable to the final state CBC processing. The first two sequences
are represented with the notation introduced in the previous section
for the CBC processing:
ei=F(mi XOR
ei-b,Gi) and
Gi+1=F'(mi XOR
ei-b,Gi), for
0<=i<n,
en+i=F(en+i-b,Gn+i) and
Gn+i+1=F'(en+i-b,Gn+i), for
0<=i<b,
where the public initialization vector is
e-b,e-b+1,...,e-1.
Then, the final state is
Gn+b; it is encoded using
v bits, with the notation
g0,g1,...,gv-1
(the dimension
v is not a constant among different messages). The term encoding is to
be understood as usual in the field of computer science. In this
context, to encode a Frogbit state
Gi, it is sufficient to focus on the relative positions of each key
streams. The last two sequences are represented by:
en+b+i=F(gi XOR
en+b+i-b',Gn+b+i) and
Gn+b+i+1=F'(gi XOR
en+b+i-b',Gn+b+i) for
0<=i<v,
en+b+v+i=F(en+b+v+i-b',Gn+b+v+i) and
Gn+b+v+i+1=F'(en+b+v+i-b',Gn+b+v+i) for
0<=i<b'.
The hash function result is
en,en+1,...,en+b-1,en+b+v,en+b+v+1,...,en+b+v+b'-1,
which is the concatenation of two bit strings, the two closing blocks
respectively from the message CBC processing and the final state CBC
processing. Reasonable values for the block sizes may be cited as
b=96 and
b'=64.
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