CONNOTECH Experts-conseils Inc.

The Frogbit Data Integrity Algorithm

(Main Web Page)

Table of Contents

What is the Frogbit data integrity algorithm?

It is a unique proposal for a new design of cryptographic data integrity algorithm. There is a core Frogbit algorithm which is described in several ways:

• The mathematical notation, which is the reference specification. The other descriptions of the core Frogbit algorithm use the design parameter n set to 2.
  
  
• The source code program. The program listing "A" is the straightforward way of programming the core Frogbit algorithm. Using optimization techniques for the subprograms encipher_bit and decipher_bit of program listing "A", it is possible to replace many operations and jumps with a single table-lookup operation. This gives the program listing "B". The program listing "C" illustrates the construction of the lookup table used in the program listing "B".
  
  
• Hardware implementation. A hardware implementation of the core Frogbit algorithm is shown in two figures, respectively for hardware encryption and hardware decryption. A boolean logic table specifies the details of the "run length logic" shown in these figures.
  
  
• Numerical example.

But the reader deserves some explanations, see the text on the rationales of the core Frogbit data integrity algorithm. For the study and cryptanalysis attempts at the core Frogbit algorithm, there is the Frogbit demonstration and challenge program.

What are the variants of the Frogbit algorithm?

There are many ways in which the core Frogbit algorithm may be turned into a practical cryptographic primitive. Since ten independent pseudo-random generators are involved, there is ample room for detailed design variations (see for instance the next question). In encryption applications, the Frogbit algorithm facilitates stream cipher key management with message salting. More generally, the notion of cryptographic "modes of operation" is beneficially transposed to the Frogbit algorithm. It even opens the door to a hash function construction. This has been turned into a detailed proposal for a Frogbit secure (?) hash function that is presented as a challenge to cryptanalysis.

Semi-proprietary cryptographic algorithm: a useful heresy?

In academic cryptography, it is an heresy to suggest the use of a proprietary algorithms. Yet, there is always a need to secure some top-level key within a system or application. For instance, the public key of a top-level certification authority must be protected against modification in an Internet browser software application. Within the confine of a system, if there is no anti-tamper memory device and it is impractical to require the entry of secret password upon activation of the system, it may be unavoidable to use some more or less proprietary scheme. The single role devoted to a proprietary scheme should be to make sure the contents of a configuration file remains under the control of a given software application module. For more discussion on the rationale for proprietary algorithms, see the text about A case for semi-proprietary cryptographic algorithms. With its malleability, the core Frogbit algorithm is a good starting point for semi-proprietary algorithms. See the document entitled "The Frogbit Semi-Proprietary Scheme" for instructions on using this scheme.

Is the Frogbit algorithm patented?

There are pending patents in Canada and in the United States for the Frogbit algorithm. The Canadian patent application has been laid open to the public, while the US patent application is patrially disclosed here.

Cautionary notice

The disclosure of the Frogbit algorithm, including the specification of the Frogbit hash function, is intended primarily to promote progress in the science of cryptography. Neither Thierry Moreau nor CONNOTECH Experts-conseils Inc. make representation for the commercial or other production use of the Frogbit algorithm. In any event, the reader should be aware that statutory regulations in his/her respective jurisdiction may apply to systems, equipment, assemblies, components, and software, as the case may be, that would embed the frogbit cryptographic data integrity algorithm. Professional legal advice may be required.

Small history

The Frogbit data integrity algorithm has been invented in March 1996 by Thierry Moreau as an attempt to provide cryptographic data integrity protection from stream ciphers. Patent protection has been sought for this invention prior to its disclosure in a conference in June 1996 (the "Extended Workshop on Pseudorandom Number Generation", held at University of Montreal). The release of the Frogbit web page occured in May 1997.

An academic article has been submitted to an scientific periodical having an editorial policy oriented towards strongly theoretical contributions. The academic article was first revised to put it in a format more suitable for editorial processing. Even then, anonymous "peer reviewers" rejected the article submission, partly due to a mismatch between the nature of the contribution and the editorial policy, and partly as a matter of presentation style. An intriguing comment from one reviewer is that the "key storage box can be hacked." One may wonders whether the reviewer forgot the very nature of secret key ciphers (keys must be somewhere), or if this comment applies to the proposed Frogbit hash construction. With the ease of publication using the Internet, and with the effectiveness of publication through the Canadian patent system, the academic publication route was then abandonned.

Otherwise, a few sci.crypt (popular Internet newsgroup that discusses cryptography) participants were directed to the Frogbit web pages because they were looking for practical schemes to restrict the contents of a data file to a single executable program. At least one these participants expressed satisfaction with the Frogbit proposal.

Getting valuable feedback for a cipher proposal is a perillous exercise, and it shouldn't be too worrysome that so little feedback can be reported about the Frogbit algorithm.

As of July 1999, the Frogbit algorithm remains an unique contribution to the field of secret cipher designs. The unusual definition of data integrity and the Frogbit unusual construction might have some theoretical interest. The Frogbit algorithm is still seen as a reasonable starting point for the creation of semi-proprietary ciphers, in situations where secret key cipher performance is not an issue.

What does "Frogbit" mean?

The name Frogbit comes from a drifting aquatic plant, Hydrocharis morsus-ranae, Linnaeus. Like the implications of the new algorithm, the reasons for the name Frogbit are endless:

• The "drifting" characteristic of the algorithm is found in the key source specification, whith its ten pseudo-random streams. The Frogbit algorithm can be viewed as a "stream" cipher variant.
  
  
• Alternatively, the ten pseudo-random generators can be viewed as leapfroging each other in steps of two bit positions.
  
  
• There is an allusion to "meandering" crypto policy of the Canadian government, the Hydrocharis morsus-ranae, Linnaeus having been inadvertently released in the wilderness of North America by an agency of the Canadian government (actually a nature museum), and slowly spreading in the St-Lawrence river bassin. The plant originates from Europe.
  
  
• In winter 1996, while Thierry Moreau was inventing the algorithm, he was anticipating the spring time when he would go canoeing with his five boys in the marshes of the Ottawa river, at Plaisance, Qc, where the real Frogbit is common.
  
  
• The real Frogbit got its common english name from its floating leaves that are the size of a frog byte (but actually frogs don't eat frogbit leaves). The same etymology gave the plant's scientific name, and its french name, "mors grenouillette", pronounced more or less "mar granou-yet."
  
  
• On the sociological perspective, political correctness put aside, the Frogbit inventor is a french-speaking canadian, thus he could be nicknamed "frog" by some members of the Canadian society's other solitude.
  
  
• The name just sounds well.

But there is no implied claim that the algorithm is a "leapfrog" in any respect, because there is no path along which immediate technological superiority could be asserted (as would be the case if the performance characterisitc of the algorithm was outstanding). Nonetheless, the Frogbit could be a breakthrough by opening new directions of research in cryptology.

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