[Cryptography] Simple non-invertible function?

Sandy Harris sandyinchina at gmail.com
Mon Sep 15 13:12:33 EDT 2014


I have been working on changes to the Linux random driver; there is
another thread here with a proposal. A very useful (I think essential)
component there would be a non-invertible function that is fairly
simple in terms of both computational cost and data requirements.
Suggestions?

The function I need must take some amount of data in and put the same
amount out. It could use some other data as well (block cipher rounds
keys, an array of constants in my current code, ...) but the
non-invertible property must not depend on that, only on the main
input data.

I currently use input data X and two constants B & D, all 128-bit.
   initialise output buffer from B
   mix in X using the finite field multiplication from
      AES GCM with multiplier D
   XOR D into the buffer
This is invertible if there has been a state compromise so the enemy
knows B & D. Is it enough to just change the XOR to use X instead of
D?

Preneel et al., in a paper on block-cipher-based hashes, prove that
encrypt(X,key) XOR X and various related structures are
non-invertible. Clearly that would work here but I'd prefer to avoid
the block cipher overhead if possible.

The world's simplest block cipher is just IDEA multiplication of
plaintext and key, and that could be made non-invertible with an XOR.
The small block size (16 bits) does not appear to matter in my
application and a transform that mixes those blocks could easily be
added just in case it does matter.

Is GCM(X, key) a block cipher in the sense that would make the Preneel
at al. proof apply to showing  GCM(X, key) XOR X is non-invertible?

Can anyone suggest a better way?


More information about the cryptography mailing list