[Cryptography] Simple non-invertible function?

Bill Stewart billstewart at pobox.com
Sat Sep 20 12:48:46 EDT 2014


At 08:15 PM 9/19/2014, John Gilmore wrote:
>I don't get this non-invertible thing [...]
>OK, so make a secure block cipher with a 16-bit block.  Do
>"encrypt(x, key) xor x".  Sandy says that this is somehow magically
>non-invertible, but if I just run it for every value of X (all
>65536 of them), I can build a table that DOES let me invert it.

Probably not, because there will be multiple values of x
that output the same value of "y = encrypt(x,key) xor x",
so there are some y that don't invert to a corresponding x,
and some that don't invert to a unique x, just multiple.
But there are also many values of y for which there's a unique x,
and many for which there may only be two or three.
(Also, of course, it's practical to do this for 16-bit blocks,
but not currently feasible for 128-bit.)

For a security application, the question becomes what you need it for,
and whether it's good enough to have a function for which you can
sometimes find single pre-images (or a small number of pre-images.)

Sandy said the function needed to have an output as long as the input;
otherwise you could just take some possibly-invertible mix function
such as a CRC and discard N bits, which would have an average of 2**N
input values matching each output.  (I suppose you could still do that
and zero-pad the last N bits, but that's pretty lame.)



More information about the cryptography mailing list