Team:Davidson-Missouri Western/Ideal Hash Function Characteristics

From 2008.igem.org

(Difference between revisions)

Revision as of 01:46, 30 October 2008

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

Overview

A cryptographic hash function takes as input a message or document of any size, and returns a fixed length hexadecimal string as output, called the hash value. The hash value is essentially the "signature" of the input document, and can be used to verify that a document has not been tampered with. The hash function should be sensitive to small perturbations in the input message, producing very different hash values for highly similar, but not identical, documents. This page describes the characteristics and ideal properties of a cryptographic hash function.

Characteristics

Reduces Text Down for Authentication

Not Reversible
- From any given output, it would be virtually impossible to work backwards to get the input.

Each Input Has Exactly One Output
- Each input will always hash to the same single output (a property of any function).

Arbitrary Input Length and Fixed Output Length
- Documents of unlimited length can be hashed and all documents should hash to outputs of equal (brief) length. Enables user to quickly detect document tampering and ensures hash values do not contain information about the length of the original document.

At Least One Collision
- A collision occurs when two inputs hash to the same output. Collisions ensure that each hash value does not correspond to a unique input (in other words, the function is not invertible).

Ideal Hash Function Properties

Minimal Collisions
- Although collisions are necessary, an ideal hash function will equally partition to all possible hash values.

Unpredictable Collisions
- If collisions are predictable, patterns that can define the function become apparent. Secure hash functions require a large number of deliberate attempts to create 2 colliding documents.

Real-Time Computation
- Hash value should be computed for a document in the time it takes to be transmitted.
- Speed of Spoke Test

Practical Applications

[http://gcat.davidson.edu/iGEM08/cryptography_graph.pdf International Call for a Better Hash]

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

@@ Line 6: / Line 6: @@
 !align="center"|[[Team:Davidson-Missouri_Western/Notebook|Notebook]]
 |}
+== '''Overview''' ==
+A cryptographic hash function takes as input a message or document of any size, and returns a fixed length hexadecimal string as output, called the '''hash value'''. The hash value is essentially the "signature" of the input document, and can be used to verify that a document has not been tampered with. The hash function should be sensitive to small perturbations in the input message, producing very different hash values for highly similar, but not identical, documents.  This page describes the characteristics and ideal properties of a cryptographic hash function.
-=='''To be functional, hash functions must have certain key properties.  These are listed and illustrated below.'''==
+=='''Characteristics'''==
-'''Reduces Text Down for Authentication'''
+* '''Reduces Text Down for Authentication'''
-[[Image:Slide01.jpg|350px]]
+[[Image:Slide01.jpg|350px|lalign="right"]]
-'''Not Reversible''' - From any given output, it would be virtually impossible to work backwards to get the input.
+* '''Not Reversible'''
+** From any given output, it would be virtually impossible to work backwards to get the input.
-'''Each Input Has Exactly One Output''' - One input will always hash to the same one output.
+* '''Each Input Has Exactly One Output'''
+** Each input will always hash to the same single output (a property of any function).
-'''Arbitrary Input Length and Fixed Output Length'''
+* '''Arbitrary Input Length and Fixed Output Length'''
-Documents of unlimited length can be hashed and all documents should hash to outputs of equal (brief) length. Enables user to detect authentication quickly and ensures hash values do not give info about length of original document.
+** Documents of unlimited length can be hashed and all documents should hash to outputs of equal (brief) length. Enables user to quickly detect document tampering and ensures hash values do not contain information about the length of the original document.
-'''At Least One Collision'''
+* '''At Least One Collision'''
-A collision occurs when two inputs hash to the same output. At least one collision is needed so that each input does not correspond to a unique hash output to assure the function is not reversible.
+** A collision occurs when two inputs hash to the same output. Collisions ensure that each hash value does not correspond to a unique input (in other words, the function is not invertible).
-'''Minimal Collisions'''
-Although at least one collision is needed, an ideal hash function will equally partition to all possible hash values.
+=='''Ideal Hash Function Properties'''==
+* '''Minimal Collisions'''
+** Although collisions are necessary, an ideal hash function will equally partition to all possible hash values.
 [[Image:Slide02.jpg|350px]]
-'''Unpredictable Collisions'''
+*'''Unpredictable Collisions'''
-If collisions are predictable, patterns that can define the function become apparent. (only secure if it takes more than 280 attempts to deliberately create 2 colliding documents).
+**If collisions are predictable, patterns that can define the function become apparent. Secure hash functions require a large number of deliberate attempts to create 2 colliding documents.
-'''Speedy'''
+*'''Real-Time Computation'''
-Tags document in the split-second it's electronically transmitted (Mackenzie)
+** Hash value should be computed for a document in the time it takes to be transmitted.
-[[Team:Davidson-Missouri_Western/Speed of Spoke Test|Speed of Spoke Test]]
+** [[Team:Davidson-Missouri_Western/Speed of Spoke Test|Speed of Spoke Test]]
 *[[Team:Davidson-Missouri_Western/Practical Applications|Practical Applications]]