Re: Suggestion for an AES Based Hash Function



On Mar 27, 10:59 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
Spring is sprung and young people's thoughts turn to...  Well I am no
longer young so my thoughts have turned to hash functions.  Other
amateurs posting here seem to favour cyphers, I go for hash functions.

There are already a number of ways of turning a block cypher into a
hash function, Miyaguchi-Preneel and so forth.  However the problem is
that generally these methods are slow, requiring both a key schedule
and the required number of rounds for each hash block.  I was thinking
about ways to speed this process up.

Rather than trying to use a strong one-way compression function would
it be possible to use a weaker, and faster, compression function with
a strong one-way function added at the end of the hash as a final
computation?  With this structure the compression function would just
mix up and compress the incoming message and the one-way nature of the
hash would be added in the final processing stage.  The round function
would not be completely weak, but it would not be as cryptographically
strong as Miyaguchi-Preneel or whatever.

In order to deny an attacker, who has full control over the initial
message, the ability to fully control all of the internal state of the
cypher I have used two strategies.  Firstly I try to use the message
input in two different ways so that it is difficult for the attacker
to get the one message to do two different things.  Secondly I have
delayed allowing each incoming message block to impact half of the
state until the processing of the following block.  This means that
the attacker is working indirectly when trying to control that half of
the state.  It is impossible to prevent an attacker having some
control over the internal state of the hash.  The point is to minimise
what control is allowed.

I have used a fixed set of keys in two places.  This means that for
messages up to one block (after padding) the block cypher key schedule
need not be run at all.  For longer messages the key schedule will
have to be run at least once but less than once per block.

I have limited the design to hash lengths of 128, 256 and 512 bits.
It would not be difficult to extend the design for other hash lengths
if they were required.

My design goals were:

 - the compression function should emphasise mixing its inputs over
being one-way.

 - the state of the compression function should be twice the size of
the maximum hash.  (I had a reference for this, but I cannot now find
it.)

 - the final one-way function must emphasise being one-way over mixing
its inputs.

 - incoming message blocks must be used in more than one way to make
it more difficult for an attacker to influence the internal state.

 - delaying the impact of incoming message blocks on part of the
internal state.

 - the last compression function output needs to be well hidden by the
final one-way function so any attacker cannot determine the final
compression output from just the hash.

 - shorter hashes should not be truncations of the longer hashes.

 - the block cypher key schedule should be run less frequently than
once per block.

 - use elements of an existing block cypher: AES.

1 Inputs and Outputs

The two inputs are:

  L - the bit length of the hash.  This may be any one of 128, 256 or
512 bits.  Other values will cause the algorithm to fail.

  M - the message to be hashed.  The length of the message cannot
exceed 2**64 - 1 bits.  Messages that are too long will cause the
algorithm to fail.

The output is the L bit hash of the message.

2 Padding

The message will be divided into 512 bit blocks.  Padding will be as
for MD5: add a 1 bit, some zero bits and 64 bits giving the unpadded
bit size of the original input.  Enough zeros are included to pad to
the next 512 bit block boundary.  The padded message is divided into n
512 bit blocks: P1, P2, ... Pn.

3 Initial values

The algorithm uses an internal 1024 bit state divided into two 512
state blocks: S and R.  These are both initialised to all zeros: S0 =
0x000 ... 00, R0 = 0x000 ... 00

The key schedule uses a 256 bit key mask, KM.  This is initialised
using L, the hash length:

  L       KM
 ---------------------------
 128     0x01280128 ... 0128
 256     0x02560256 ... 0256
 512     0x05120512 ... 0512

Other possible values of L could be calculated similarly: zero extend
to four digits and treat the result as hexadecimal rather than
decimal, repeating 16 times to get a total of 256 bits.  Deriving the
key mask in this way ensures that each different length hash is its
own value and not simply a truncation of a longer hash.

4 Key Schedule

Keys are treated differently for the first and last runs of the
compression function.  In both these cases a fixed set of keys is
used.  At the start either the key is fixed, derived from the fixed S0
and R0 or else includes input from the initial message block.  This
last option hands control of the keys to an attacker.  The other two
options give an attacker knowledge of the keys but not control over
them.  Given that I use the generated keys over a number of rounds I
preferred to have the first round keys fixed and to start deriving
keys from input at the start of the second round.  The keys for the
final run are fixed in order to deny an attacker control over the keys
just before entry to the final one way function.  Fixed keys also mean
that a one block message never needs to run the key schedule at all as
it will always use the fixed keys.

4.1 Fixed Keys

These are used for round 1 of the compression function and for the
last round that mixes in the extra block.  There are eight of them,
derived from the key mask KM.

  KF1 = KM              eg 0x05120512 ... 0512
  KF2 = ~KF1            eg 0xFAEDFAED ... FAED
  KF3 = KF1 <<< 4       eg 0x51205120 ... 5120
  KF4 = ~KF3            eg 0xAEDFAEDF ... AEDF
  KF5 = KF3 <<< 4       eg 0x12051205 ... 1205
  KF6 = ~KF5            eg 0xEDFAEDFA ... EDFA
  KF7 = KF5 <<< 4       eg 0x20152051 ... 2051
  KF8 = ~ KF7           eg 0xDFAEDFAE ... DFAE

Here ~ is bitwise negation and <<< 4 is a left rotation by four bits.
Even numbered keys are the bitwise negation of the previous odd
numbered key.  Key 1 is the key mask, and each further odd numbered
key is the previous odd numbered key rotated left by four bits.

4.2 Variable Keys

The AES key schedule is used to generate a set of 14 round keys.
These are then used in different combinations to cover the next 14
blocks of the hash.  After 14 blocks a new set of round keys is
generated.  The key schedule will need to be run before processing the
second block and every fourteenth subsequent block.  The first block
uses the fixed keys.

Split the current S and R each into two halves and xor the four halves
together, then xor the result with the key mask.  The 256 bit result
is used as input to the AES key schedule for a 256 bit key, producing
14 128 bit round keys.  These are then shifted left by 8 positions so
that key 9 moves to position 1, key 10 moves to position 2 and so
forth until key 8 moves to position 14.  The result is the final list
of keys: RK1, RK2, ... RK14.

  (S-hi || S-lo) <- S
  (R-hi || R-lo) <- R
  temp[1 .. 14] <- ASE-256-KS(S-hi xor S-lo xor R-hi xor R-lo xor KM)
  RK[1 .. 14] <- (temp[9 .. 14] || temp[1 .. 8])

Each round of the compression function needs eight keys, so block 2 of
the hash will use keys 1 to 8; block 3 will use keys 2 to 9 and so on
with the numbering wrapping round to the start so block 14 will use
keys 14 to 7.

The AES key schedule returns its input at the start of the round keys.
The shift by eight keys avoids the input being used with the S and R
values used in its derivation.

5 Compression Function

As indicated above I have kept this pretty lightweight, doing enough
to mix the inputs up but not really thinking about making it one way.
The message block is mixed with only one half of the state (S) on its
first appearance.  When processing the next block the previous S is
mixed with R.  This delay makes it more difficult for an attacker to
modify R by changing the message.  Changes to R can only be made
inditectly by first changing S.

5.1 Inputs

  Pi - the i'th block of the padded message.  i = 1, ... n
  S(i-1), R(i-1) - the current state blocks.
  RKj ... RK(j+7) - eight round keys, where j = (i-1) mod 14 or else
for block 1 (i = 1) and the last run ( i = n+1) the eight fixed keys
are used.

5.2 Output

  S(i), R(i) - the new state blocks.

5.3 Compression Function Description

S and P, are xor'ed together to give the SP block.  The SP block and
the first four round keys are passed to the Mix() function which
outputs the M block which is then rotated left by one bit.  The final
output S block is SP xor M.

S and R are xor'ed together to give the RS block.  The RS block and
the last four round keys are passed to the Mix() function which
outputs the N.  The final output R block is RS xor N.

  // Calculate new S(i)
  SP <- S(i-1) xor Pi
  M <-  Mix(SP, RKj, RK(j+1), RK(j+2), RK(j+3))
  M <- M <<< 1
  S(i) <- SP xor M

  // Calculate new R(i)
  RS <- R(i-1) xor S(i-1)
  N <- Mix(RS, RKj+4, RK(j+5), RK(j+6), RK(j+7))
  R(i) <- RS xor N

The SP block is used in two different ways, once as input to the Mix()
function and once to xor with the output from Mix().  SP can be
completely determined by an attacker chosing Pi so by making X perform
two very different functions it makes it more difficult for the
attacker to fully determine the output S(i+1).  It is not possible to
avoid the attacker having some influence over S(i+1).  The treatment
of the RS block is similar though this is not so critical as it is
less easy for an attacker to fully control the inputs R and S.

The 1 bit rotation of M is to break up the alignment on byte
boundaries.

5.4 Mix Function

This takes AA (SP or RS) and four round keys as inputs.  It uses an
matrix of 16 AES round functions to mix the inputs so all the input
can influence all the output.

First the AA block is split into four 128 bit chunks: AAa, AAb, AAc,
AAd:

  (AAa || AAb || AAc || AAd) <- AA

Together with the four round keys these are input to the first four
AES round functions of the matrix.  The output from each AES round
function is passed to its neighbours to the right and to the lower
right with output from the fourth row being input to the top row of
the next column.

                 A            B            C
        +-----+  |   +-----+  |   +-----+  |   +-----+
 RKj ---|     |  +->-|     |  +->-|     |  +->-|     |
        | R11 |      | R12 |      | R13 |      | R14 |--> Ma
 AAa ---|     |--+->-|     |--+->-|     |--+->-|     |  
        +-----+  |   +-----+  |   +-----+  |   +-----+
                 |            |            |
        +-----+  |   +-----+  |   +-----+  |   +-----+
 RKj+1--|     |  +->-|     |  +->-|     |  +->-|     |
        | R21 |      | R22 |      | R23 |      | R24 |--> Mb
 AAb ---|     |--+->-|     |--+->-|     |--+->-|     |  
        +-----+  |   +-----+  |   +-----+  |   +-----+
                 |            |            |
        +-----+  |   +-----+  |   +-----+  |   +-----+
 RKj+2--|     |  +->-|     |  +->-|     |  +->-|     |
        | R31 |      | R32 |      | R33 |      | R34 |--> Mc
 AAc ---|     |--+->-|     |--+->-|     |--+->-|     |  
        +-----+  |   +-----+  |   +-----+  |   +-----+
                 |            |            |
        +-----+  |   +-----+  |   +-----+  |   +-----+
 RKj+3--|     |  +->-|     |  +->-|     |  +->-|     |
        | R41 |      | R42 |      | R43 |      | R44 |--> Md
 AAd ---|     |--+->-|     |--+->-|     |--+->-|     |  
        +-----+  |   +-----+  |   +-----+  |   +-----+
                 A            B            C              

Here the R## are standard AES round functions and A, B and C are link
labels indicating the transfer of output from row four into the input
of row one of the next column.  There are four 128 bit outputs: Ma,
Mb, Mc and Md.  These are concatenated to give the 512 bit output M.

  M <- (Ma || Mb || Mc || Md)

6 One Way Function

Having kept the compression function relatively lightweight, this one
is probably over-engineered.  However it will only be run once per
hash as opposed to many times for the compression fumction.

6.1 Inputs

S(n), R(n) - the state blocks output from the n'th compression
function.
L - the bit length of the required hash.
KM - the key mask.
KF[1 .. 8] - the fixed keys.

6.2 Output

Hash - the L bit hash of the message.

6.2 One Way Function Description

At this point the final message block Pn has only been mixed into S(n)
and not into R(n).  In order to mix the last message block properly a
further dummy block of all zeros is compressed, using the fixed keys.
The resulting values of R and S are concatenated and saved as RS-pre.
A 256 bit key is derived from RS-pre and KM.  RS-pre is encrypted
using AES-256 in counter mode giving RS-post.  RS-pre is shuffled
using RS-post, and RS-post is shuffled using the changed RS-pre.  The
actual hash values are derived by repeatedly xoring halves of the
final RS.

  // Compress Extra Block
  P = 0x000 ... 00
  (R(n_1), S(n+1)) <- Compress(R(n), S(n), P, KF[1 .. 8])

  // Encrypt
  RS-pre <- R(n+1) || S(n+1)
  (S-hi || S-lo) <- S(n+1)
  (R-hi || R-lo) <- R(n+1)
  key = (S-hi xor S-lo xor R-hi xor R-lo xor KM)
  IV = 0
  RS-post <- AES-256-CTR(key, IV, RS-pre)

  // Shuffle
  T <- shuffle RS-pre using RS-post
  RS-final <- shuffle RS-post using T

  // Return hash
  (lo || hi) <- RS-final  // Split into two 512 bit pieces
  H512 <- lo xor hi
  if (L = 512) return H512 as Hash
  (hi || lo) <- H512      // Split into two 256 bit pieces
  H256 = hi xor lo
  if (L = 256) return H256 as Hash
  (hi || lo) <- H256      // Split into two 128 bit pieces
  H128 = hi xor lo
  return H128 as Hash

The extra compression block is to mix the last message block into
state block R.  AES and the two shuffles are used to obscure the final
values of R and S.  The shuffling and AES encryption allows RS-pre to
impact RS-final in two different ways making it more difficult for an
attacker to completely control the final hash output.

6.3 Shuffling

Shuffling uses the elements of one array to reorder the elements of
another array.  The instruction "shuffle A using B" uses a stable sort
of the elements of array B to determine an ordering, and then applies
that ordering to array A.  For example:

  A = 105, 104, 101, 101, 103

  B = 202, 204, 205, 201, 204

Using a stable sort for B gives 201, 202, 204, 204, 205 = B[3], B[0],
B[1], B[4], B[2].  Note that using a stable sort requires the ordering
of B[1] before B[4].  The ordering of the B array gives indexes 3, 0,
1, 4, 2 in order.  Rearranging A to this ordering gives A[3], A[0],
A[1], A[4], A[2] = 101, 105, 104, 103, 101.  Using a stable sort is
important to ensure that the ordering defined by the array is unique
and hence reproducible.

In this case the 1024 bit RS-pre and RS-post are to be considered as
arrays of 128 bytes for shuffling.  After shuffling they are to be
reassembled into blocks.  Byte 0 is at the high end and byte 63 at the
low end of the blocks.

7 Questions

 - is the basic idea of a weaker compression function with a stronger
one-way function at the end reasonable?

 - have I under-egged the compression function?  It would be possible
to double up the Mix() function for either S or R or both if required
at a cost in speed.

 - have I over-egged the one-way function?

 - am I right to use a double sized (1024 bit) internal state rather
than just a 512 bit internal state?

 - am I right to use fixed keys for the first block, given that I am
otherwise deriving the keys in part from the input?

 - am I right to use fixed keys to compress the extra block or should
I use normally derived variable keys?

 - any other obvious points I have missed.

8 Bloodsports

You can now all tear this latest idea to pieces. :)

rossum

You make fun of alot of issues here. A selected key string as part of
the relative input appears the design goal.

I would have just made a hidden key.

You take the input and schedule. Allowing the applied hash function.
A technically correct usage of the schedule was all in evidence.

Schedule was the hash's theorectical seqence of strings as a function
of the algorithm, and not a sequnece of algorithm content. Algorithm
in hash was to always be a selected number of the hash output, slected
by sequence location only. A input string was always therfor
unrelatable to the hash content.

A property of functional completeness was always a hash, making it
nontrivial to generate. A basic hash generator would enable common
people to cause new hash functions.

I will post the fourth hash function soon. It will simplify hash
creation fo the common man.
.



Relevant Pages

  • Suggestion for an AES Based Hash Function
    ... amateurs posting here seem to favour cyphers, I go for hash functions. ... Rather than trying to use a strong one-way compression function would ... The round function ... I have used a fixed set of keys in two places. ...
    (sci.crypt)
  • Re: sort unique
    ... given that a hash table is not ... IMO if the vendor's algorithm does something "obvious", ... function to eliminate keys that hash to the same bucket per some ... strings of random lengths, and two strings are ...
    (comp.lang.lisp)
  • Re: My First C# (warning - long post)
    ... defined as a COBOL structure of 8192 bytes (this is for ... Hashtables use two objects, one is a 'key' and the other a 'value'. ... but is for storing keys only. ... // Add some elements to the hash table. ...
    (comp.lang.cobol)
  • Re: Floats as keys in dict
    ... store the nodes I have in play as keys in a dict. ... the dict keys are then floats and I have to round the values ... give the same hash for two numbers that are "close enough" (e.g., ...
    (comp.lang.python)
  • Re: Dictionary Keys question
    ... keys are in numerical order. ... A hash is for quickly looking up data. ... complicated hash-function would be used, ... so strings don't end up in order. ...
    (comp.lang.python)