Team:Davidson-Missouri Western/Our Models

From 2008.igem.org

Home	The Team	E. nigma Project	Parts Submitted to the Registry	Notebook

The Linear Model

The diagram illustrates how a simple hash function can be implemented in a Petri dish with E. coli. This simple linear model is the basis of all our other models

The gold-colored ovals represent bacterial colonies spotted on the plate.
The input message "CAB" is converted to a binary string
- Each digit in the string is encoded by the presence (1) or absence (0) of a signal molecule.
- The first binary digit in the string is used as the "key" at the top of the linear model.
- Remaining digits are shown in the blue drops to the left of the colonies.
Each colony computes an XOR of two inputs: one from the colony above, and one from the input digit to the left of the colony
The hash value is the output of the final colony

The Split Model

The Split model has a linear-type layout. There is a linear spoke for each bit of the key. Each bit of the key is XORed with the corresponding bit of the first letter of the message (converted into binary number). The result of that logic operation is itself a 1 or a 0. That number is Xored with the corresponding bit of the second letter of the message. This pattern continues until every bit of every character of the message has been XORed down the appropriate spoke. The resulting bits at the end of each spoke, combined in order produce the Hash Output Character.

This model is recommended if you're wishing to hash inputs where the probabilities of each character occurring are uniform. Therefore, for hashing aimed at password verifications, the Split model is highly recommended.

The Spoke Model

The Split Model also has a linear-type layout. There is a linear spoke for each bit of the key.

Because every letter has the same amount of bits in binary representation as the key, the number of overall bits in the message can be evenly divided by the number of bits in the key. Instead of all the first bits of each letter XORing down the first spoke (as happens in the Split Model), the Spoke Model organizes the bits to be Xored differently. Assume that there are n bits in the entire message and x bits in the key and each character in the message. Then the first (n/x) bits are XORed down the first spoke, the second (n/x) bits XORed down the second spoke, etc.

Also, as opposed to a strictly linear setup, the Spoke Model reverses the flow direction of the XOR gate on alternating lines of the setup. The resulting bits at the end of each spoke, combined in order produce the Hash Output Character.

Although not a very efficient hash model in practice, this model has some interesting fractal characteristics that are interesting to explore mathematically when analyzing this model.

The Net Model

The Net model has a cylindrical setup in which the inputs are set up in a circular fashion. After the message is converted into binary numbers, each bit in order fills rings of indicated order (clockwise). A minimum amount of ring layers must also be indicated. The layers will be first filled with the entire message and then with the message repeated until a full amount of places in each ring are filled with bits.

The bits are hashed with their neighbor. The result of that logic operation is XORed with the result of the logic operation of the neighboring 2 bits. This pattern continues until there are exactly as many bits for each ring as bits in each letter. Each of these bits is then XORed down each layer (as happens in the linear-type layout) with the top layer bits being XORed with the next level's corresponding bit, and then with that result being XORed with the next level's corresponding bit, until every ring has been XOred. The values remaining after the bottom ring has been XORed comprise the Hash Output Character.

This model is more flexible than the other models in that you can manipulate the ring length(number of values on each circle). The stack size is also variable, however this has no impact on the actual efficiency of the hash model, only the ease in which the biologist implements it. This is a good model and recommended for short-length messages, specifically those less than 8 characters long. The efficiency of this model increases with the increase of the ring length, however a ring length higher than 223 is not recommended(due to time issues).

The Twist Model

The Twist Model has the same cylindrical setup as the Net model, however it uses a shift element to increase the efficiency of the Model. After the message is converted into binary numbers, the first bits of each character in the message are organized in order of character occurrence in the message. These numbers are followed by the second bits of each character, and so forth until each bit of each letter has been incorporated into the order. This new string of values fills rings of indicated order (clockwise). A minimum amount of ring layers must also be indicated. The layers will be first filled with the entire message and then with the message repeated (with a shift of one letter). The first shift will move the first character of the original message to the end of the message and (with the second character now leading the message). This extra fill is continued until a full amount of places in each ring are filled with bits.

The XORing from this point on is identical to that of the Net Model.

The efficiency of this Model depends on the number of bits in each ring and the number of layers of rings. In general, the longer the message and the greater the ring length and number of layers, the better the Model.

The Workin' In, Workin' Out Model

The Workin' In, Workin' Out Model was an attempt to use the create a hash function, suitable to physically placing in a Petri dish, that would be difficult to create a collision with a given hash value. Because of the topology and interaction between certain nodes and the lack of interaction between others, it was thought that this hash function might perhaps be more difficult to decipher messages leading to the same hash value. It does satisfy most of the properties needed for a good hash function.

Home	The Team	E. nigma Project	Parts Submitted to the Registry	Notebook