tribble.security
Class ZoidbergEHash

java.lang.Object
  extended byjava.security.MessageDigestSpi
      extended byjava.security.MessageDigest
          extended bytribble.security.ZoidbergEHash

public class ZoidbergEHash
extends java.security.MessageDigest

Zoidberg-C message digest (cryptographic hash). Computes a 160-bit (20-byte) message digest (a binary hash) from a series of input bytes.

The digest algorithm is designed to produce a unique hash vector for any given input byte stream, such that altering a single bit in the input stream results in a completely different hash value.

An input stream of bytes fed into the digest algorithm are hashed 16 bytes (128 bits) at a time. After all input bytes have been fed into the algorithm, the input is padded with a trailing count byte, and then enough zero bytes to make the total input length a multiple of 16 bytes (128 bits). The result of the digest algorithm is a 20-byte (160-bit) output byte vector.

This digest algorithm can be used as the basis of a digital signature scheme.

Note that none of these methods is synchronized.

Test Vectors

An empty input vector of zero bytes hashes to a message digest value of
+REDO {E0 47 A9 DC 13 99 0F A3 06 82 21 D8 7E BA 28 0B 44 17 9A 27}.

A single input byte of
{00}
hashes to a message digest value of
+REDO {C6 7F 21 C7 7A 7C 4C F1 F5 7F BB 96 B8 21 86 07 85 22 60 5D}.

A single input byte of
{01}
hashes to a message digest value of
+REDO {35 CB 1D 10 D4 2A 1E 49 43 69 9A DF 9F E4 66 F3 E2 B7 6A 22}.

Two input bytes of
{0D 0A}
hash to a message digest value of
+REDO {2D 22 DA B7 0C 7F C4 D7 E5 13 57 93 7C DD 4B 21 1C B1 24 2F}.

Four input bytes of
{01 02 03 04}
hash to a message digest value of
+REDO {76 C9 35 85 86 08 70 86 47 39 5C FE 4C 24 0C CC 4F BE 80 61}.

16 input bytes of
{01 02 03 04 01 02 03 04 01 02 03 04 01 02 03 04}
hash to a message digest value of
+REDO {B4 97 4B 0D 4B FF 28 94 C2 AA C8 43 F2 2B EC 4F 3E 45 25 43}.

16 input bytes of
{00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F}
hash to a message digest value of
+REDO {EB 6D 0C 0C 8E C5 B5 44 48 57 EC 73 63 3D 1E 1C 0E E8 30 26}.

16 input bytes of
{00 01 02 03 04 25 06 07 08 09 0A 0B 0C 0D 0E 0F}
hash to a message digest value of
+REDO {7E 03 5F 44 C8 F7 5A 07 E3 B5 08 F7 3D 50 1C EC D1 6B 0D EF}.

17 input bytes of
{00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 00}
hash to a message digest value of
+REDO {0D 90 9E CF F4 15 14 89 89 95 6D 0D 06 40 33 5E 8D 45 B1 B9}.

16 input bytes of
{44 61 76 69 64 20 52 2E 20 54 72 69 62 62 6C 65}
hash to a message digest value of
+REDO {76 8B 2B 77 37 53 72 89 7F 78 14 8F A3 57 12 CA 18 D7 AE 9A}.

Acknowledgments

This code is based on an original algorithm invented by David R. Tribble in March 2002.

License is granted to use this algorithm without fees or restrictions for all private and commercial uses.

Since:
2004-12-20
Version:
$Revision: 1.3 $ $Date: 2005/02/05 21:35:23 $
Author:
David R. Tribble (david@tribble.com).
Copyright ©2004 by David R. Tribble, all rights reserved.
Permission is granted to freely use and distribute this source code provided that the original copyright and authorship notices remain intact.
See Also:
ZoidbergAHash, MessageDigest

Constructor Summary
ZoidbergEHash()
          Constructor.
 
Method Summary
 java.lang.Object clone()
          Clone this message digest, making a copy of the contents accumulated up to this point.
 byte[] digest()
          Compute the final value of this message digest.
 byte[] digest(byte[] in)
          Hash an array of bytes, updating and computing the final message digest.
protected  byte[] engineDigest()
          Compute the final value of this message digest.
protected  int engineGetDigestLength()
          Retrieve the size, in bytes, of this message digest.
protected  void engineReset()
          Reset this message digest, clearing the results of any previously accumulated hashed input data.
protected  void engineUpdate(byte in)
          Hash a single byte, updating this message digest.
protected  void engineUpdate(byte[] in, int off, int len)
          Hash an array of bytes, updating this message digest.
protected  byte[] getBytes()
          Retrieve the output bytes of this message digest.
protected  int hashWords()
          Hash four 32-bit input words (128 bits), updating this message digest.
static void main(java.lang.String[] args)
          Test driver.
 void reset()
          Reset this message digest, clearing the results of any previously accumulated hashed input data.
 void update(byte in)
          Hash a single byte, updating this message digest.
 void update(byte[] in)
          Hash an array of bytes, updating this message digest.
 void update(byte[] in, int off, int len)
          Hash an array of bytes, updating this message digest.
 
Methods inherited from class java.security.MessageDigest
digest, getAlgorithm, getDigestLength, getInstance, getInstance, getInstance, getProvider, isEqual, toString
 
Methods inherited from class java.security.MessageDigestSpi
engineDigest
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ZoidbergEHash

public ZoidbergEHash()
Constructor.

Since:
1.1, 2004-12-20
Method Detail

main

public static void main(java.lang.String[] args)
Test driver.

Reads bytes from the standard input, hashes them, and then prints the resulting 160-bit (20-byte) hexadecimal hash vector.

Parameters:
args - Command line arguments. If specified, a message digest is computed from the first argument; otherwise the digest is computed from the bytes read from standard input.
Since:
1.1, 2004-12-20

reset

public void reset()
Reset this message digest, clearing the results of any previously accumulated hashed input data.

Since:
1.1, 2004-12-20

clone

public java.lang.Object clone()
Clone this message digest, making a copy of the contents accumulated up to this point.

A cloned copy of a message digest can be used to produce a partial message digest. Simply clone the message digest after the partial message contents have been fed into update(byte[]), and then call digest() on the clone. The original message digest object can then be used to continue hashing the rest of the message.

Since:
1.1, 2004-12-20

update

public void update(byte in)
Hash a single byte, updating this message digest.

Parameters:
in - A single byte of input data to hash.
Since:
1.1, 2004-12-20

update

public void update(byte[] in)
Hash an array of bytes, updating this message digest.

Parameters:
in - An array of data bytes to hash.
Since:
1.1, 2004-12-20

update

public void update(byte[] in,
                   int off,
                   int len)
Hash an array of bytes, updating this message digest.

Parameters:
in - An array of data bytes to hash.
off - The index of the first byte of array in to hash.
len - The number of bytes in array in to hash.
Since:
1.1, 2004-12-20

digest

public byte[] digest()
Compute the final value of this message digest.

Note that this also resets the hash vector of this message digest.

Returns:
A 160-bit (20-byte) array of bytes encoding the binary message digest.
Since:
1.1, 2004-12-20

digest

public byte[] digest(byte[] in)
Hash an array of bytes, updating and computing the final message digest.

Note that this also resets the hash vector of this message digest.

Parameters:
in - An array of data bytes to hash.
Returns:
A 160-bit (20-byte) array of bytes encoding the binary message digest.
Since:
1.1, 2004-12-20

engineReset

protected void engineReset()
Reset this message digest, clearing the results of any previously accumulated hashed input data.

Since:
1.1, 2004-12-20

engineGetDigestLength

protected int engineGetDigestLength()
Retrieve the size, in bytes, of this message digest.

Returns:
The number of bytes computed by this message digest, which is always 20 bytes (160 bits).
Since:
1.1, 2004-12-20

engineUpdate

protected void engineUpdate(byte in)
Hash a single byte, updating this message digest.

Parameters:
in - A single byte of input data to hash.
Since:
1.1, 2004-12-20

engineUpdate

protected void engineUpdate(byte[] in,
                            int off,
                            int len)
Hash an array of bytes, updating this message digest.

Parameters:
in - An array of data bytes to hash.
off - The index of the first byte of array in to hash.
len - The number of bytes in array in to hash.
Since:
1.1, 2004-12-20

engineDigest

protected byte[] engineDigest()
Compute the final value of this message digest.

The input is padded with a trailing count byte, and then enough zero bytes to make the total input length a multiple of 20 bytes (160 bits).

Note that this also resets the hash vector of this message digest.

Returns:
A 160-bit (20-byte) array of bytes encoding the binary message digest.
Since:
1.1, 2004-12-20

getBytes

protected byte[] getBytes()
Retrieve the output bytes of this message digest.

Note that the returned byte array will contain all zeros (0x00) if this message digest has not been updated with any data bytes or has been reset.

Returns:
An array of bytes encoding the 160-bit (20-byte) message digest.
Since:
1.1, 2004-12-20

hashWords

protected int hashWords()
Hash four 32-bit input words (128 bits), updating this message digest.

Algorithm

The hashing algorithm is a "braiding" of five 32-bit binary words, which comprise a total of 160 bits of the hash vector. The "braiding" refers to the way in which the words are permuted (rearranged). Between each permuting operation (Pi-phase), the input vector is combined with the output of the permutation, using exclusive-or (X-phase) and two's-complement addition (A-phase).

The I-phase spreads four 32-bit input words across the current 160-bit hash vector. The four 32-bit input words comprise the first four words of the input vector; the last word of the input vector is the sum of the squares of the four input words minus one (i.e., i4 = in0**2 + in1**2 + in2**2 + in3**2 - 1).

 I-phase:
  +-----+    +-----+    +-----+    +-----+
  | in0 |    | in1 |    | in2 |    | in3 |  Input words (128 bits)
  +-----+    +-----+    +-----+    +-----+
    :          :          :          :
    : :        : :        : :        : :
    :   :      :   :      :   :      :   :
    :  X**2    :  X**2    :  X**2    :  X**2    -1
    :    :     :    :     :    :     :    :      :
    :    :.... : ..ADD... : ..ADD... : ..ADD....ADD
    :          :          :          :           :
    :          :          :          :           :
  +-----+    +-----+    +-----+    +-----+    +-----+
  | i0  |    | i1  |    | i2  |    | i3  |    | i4  |  I (160 bits)
  +-----+    +-----+    +-----+    +-----+    +-----+
 

The H-phase adds the input vector words with the previous hash vector.

 H-phase:
  +-----+    +-----+    +-----+    +-----+    +-----+
  | i0  |    | i1  |    | i2  |    | i3  |    | i4  |  I0 (160 bits)
  +-----+    +-----+    +-----+    +-----+    +-----+
    :          :          :          :          :
    : +-----+  : +-----+  : +-----+  : +-----+  : +-----+
    : | h0  |  : | h1  |  : | h2  |  : | h3  |  : | h4  |  Hi-1
    : +-----+  : +-----+  : +-----+  : +-----+  : +-----+
    :     :    :     :    :     :    :     :    :     :
     :   :      :   :      :   :      :   :      :   :
      ADD        ADD        ADD        ADD        ADD
       :          :          :          :          :
    +-----+    +-----+    +-----+    +-----+    +-----+
    | i0  |    | i1  |    | i2  |    | i3  |    | i4  |  I1
    +-----+    +-----+    +-----+    +-----+    +-----+
 

The R, P, X, Q, and A phases are then repeated 5 times, intermixing the contents of the input vector with the hash vector. The final result of the five rounds is the output hash vector.

 R-phase:
  +-----+ +-----+ +-----+ +-----+ +-----+
  | i0  | | i1  | | i2  | | i3  | | i4  |  Ii
  +-----+ +-----+ +-----+ +-----+ +-----+
     :       :       :       :       :
  ROR(17) ROR(5)  ROR(25) ROR(13) ROR(29)
     :       :       :       :       :
  +-----+ +-----+ +-----+ +-----+ +-----+
  | r0  | | r1  | | r2  | | r3  | | r4  |  Ri
  +-----+ +-----+ +-----+ +-----+ +-----+

 P-phase:
  +-----+ +-----+ +-----+ +-----+ +-----+
  | r0  | | r1  | | r2  | | r3  | | r4  |  Ri
  +-----+ +-----+ +-----+ +-----+ +-----+
     :       :       :       :       :
      :     :         :     :        :
       :   :           :   :         :
        : :             : :          :
         :               :           :
        : :             : :          :
       :   :           :   :         :
      :     :         :     :        :
     :       :       :       :       :
  +-----+ +-----+ +-----+ +-----+ +-----+
  | p0  | | p1  | | p2  | | p3  | | p4  |  Pi
  +-----+ +-----+ +-----+ +-----+ +-----+

 X-phase:
      +-----+    +-----+    +-----+    +-----+    +-----+
      | p0  |    | p1  |    | p2  |    | p3  |    | p4  |  Pi
      +-----+    +-----+    +-----+    +-----+    +-----+
          :          :          :          :          :
  +-----+ :  +-----+ :  +-----+ :  +-----+ :  +-----+ :
  | i0  | :  | i1  | :  | i2  | :  | i3  | :  | i4  | :  Ii
  +-----+ :  +-----+ :  +-----+ :  +-----+ :  +-----+ :
    :     :    :     :    :     :    :     :    :     :
    :    NEG   :     :    :     :    :     :    :     :
    :     :    :     :    :     :    :     :    :     :
     :   :      :   :      :   :      :   :      :   :
      XOR        XOR        XOR        XOR        XOR
       :          :          :          :          :
    +-----+    +-----+    +-----+    +-----+    +-----+
    | x0  |    | x1  |    | x2  |    | x3  |    | x4  |  Xi
    +-----+    +-----+    +-----+    +-----+    +-----+

 Q-phase:
  +-----+ +-----+ +-----+ +-----+ +-----+
  | x0  | | x1  | | x2  | | x3  | | x4  |  Xi
  +-----+ +-----+ +-----+ +-----+ +-----+
     :       :       :       :       :
     :        :     :         :     :
     :         :   :           :   :
     :          : :             : :
     :           :               :
     :          : :             : :
     :         :   :           :   :
     :        :     :         :     :
     :       :       :       :       :
  +-----+ +-----+ +-----+ +-----+ +-----+
  | q0  | | q1  | | q2  | | q3  | | q4  |  Qi
  +-----+ +-----+ +-----+ +-----+ +-----+

 A-phase:
      +-----+    +-----+    +-----+    +-----+    +-----+
      | q0  |    | q1  |    | q2  |    | q3  |    | q4  |  Qi
      +-----+    +-----+    +-----+    +-----+    +-----+
          :          :          :          :          :
  +-----+ :  +-----+ :  +-----+ :  +-----+ :  +-----+ :
  | i0  | :  | i1  | :  | i2  | :  | i3  | :  | i4  | :  Ii
  +-----+ :  +-----+ :  +-----+ :  +-----+ :  +-----+ :
    :     :    :     :    :     :    :     :    :     :
     :   :      :   :      :   :      :   :      :   :
      ADD        ADD        ADD        ADD        ADD
       :          :          :          :          :
    +-----+    +-----+    +-----+    +-----+    +-----+
    | i0  |    | i1  |    | i2  |    | i3  |    | i4  |  Ii+1
    +-----+    +-----+    +-----+    +-----+    +-----+
 

The output vector of each round becomes the input vector of the next round.

The output vector of the last round is the output of the hash, i.e., the message digest.

    +-----+    +-----+    +-----+    +-----+    +-----+
    | i0  |    | i1  |    | i2  |    | i3  |    | i4  |  I5
    +-----+    +-----+    +-----+    +-----+    +-----+
       :          :          :          :          :
    +-----+    +-----+    +-----+    +-----+    +-----+
    | h0  |    | h1  |    | h2  |    | h3  |    | h4  |  Hi+1, O
    +-----+    +-----+    +-----+    +-----+    +-----+
 

The P and Q phases permute the 5 words of the hash vector in the following braiding pattern (which repeats every 5 iterations):

     0.  A B C D E
     1.  B A D C E   P  iteration 1
     2.  B D A E C   Q
     3.  D B E A C   P  iteration 2
     4.  D E B C A   Q
     5.  E D C B A   P  iteration 3
     6.  E C D A B   Q
     7.  C E A D B   P  iteration 4
     8.  C A E B D   Q
     9.  A C B E D   P  iteration 5
    10.  A B C D E   Q
 

Returns:
The first 32 bits of the resulting updated hash vector.
Since:
1.1, 2004-12-20