[Cryptography] Simple non-invertible function?

[Sandy Harris]

On Fri, Sep 19, 2014 at 10:51 AM, Jerry Leichter <leichter at lrw.com> wrote:

> On Sep 18, 2014, at 12:13 PM, Sandy Harris <sandyinchina at gmail.com> wrote:

>>> 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.
>>
>> My current code uses idea_multiply(x, key) xor x which I think
>> is non-invertible. Then there's a GCM hash mixing step so I do
>> not think the 16-bit blocks are a problem.
>>
>> Comment?

> Please define "non-invertible".  F(x) = 0 is non-invertible - but likely not what you had in mind.  Presumably you mean something like a 1-1 function such that computing F(x) is easy but computing its inverse is hard - for some appropriate definition of "easy" and "hard".

Yes. The Preneel at al. paper classifying ways to use a block cipher
to build the compression function for a hash looks at an exhaustive
list of 64 possible constructions and says 12 are secure. A block
cipher must be invertible (given the key) but a hash compression
function should not be, so all the ones they consider secure are
non-invertible in the sense I mean.

For example, given a secure block cipher, encrypt( x, key) xor x
works. So does the construction used in Salsa or ChaCha: copy input
into temp[], mix temp[] thoroughly, add the result back into the input
to get the output.

>  The example you give is 1-1 and easy to compute, but the inverse isn't likely to be that hard, or we'd be using it in place of much more complex functions like the SHA's.

No, a hash needs lots of other properties: adequate bit length, good
mixing across that whole length, overall efficiency, resistance to
various attacks, ... You can get all those from a suitable choice of
hash algorithm or a block cipher used in a mode from Preneel at al.
but I'm not looking for them all, just the non-invertible property.

My context is that we have hashed a pool and want to use the resulting
data twice, once as feedback into the pool and once for output. The
two should be different so we need to apply some transform, use
untransformed data as the feedback and transformed data for output. We
have already paid the overheads of hashing, so we want a cheap
function here but it should be non-invertible.

My current code, different from what I posted earlier, is:

    /*
    create a temp[] value for use in generating output
    different from data used in feedback

    non-invertible encrypt(x, key) xor x transform
    (see Preneel, Govaerts & Vandewalle)
    "block cipher" is IDEA multiplication of input & key
    16-bit blocks here, so mixing is needed later
    */
    memcpy( temp, buffer, 16 ) ;
    idea128( temp, p->A ) ;
    xor128( temp, buffer ) ;

    /* feed untransformed result back into the pool */
    buffer2pool( p, buffer ) ;

    /*
    apply another hash step using different constants B, D
    and the transformed value in temp[]
    */
    memcpy( buffer, p->B, 16 ) ;
    addmul( (byte *) buffer, (byte *) temp, 16, (byte *) p->D) ;
    xor128( buffer, p->D ) ;
    zero128( temp ) ;

I suspect there is a better way to achieve my goal here, without the
cost of a full block cipher. However, I have not found one.