[Cryptography] Pre-image security of SHA-256 reduced to 16 rounds

[John Kelsey]

On Jan 31, 2014, at 9:24 PM, Sergio Lerner <sergiolerner at pentatek.com> wrote:
...
[This first part is me asking a question]
>> If you only need a function that can't be inverted over a smallish state, you might want to look at block ciphers.  If you have a block cipher E(k,x), you can get a pretty good one-way function from 
>> 
>> F(k) = E(k,constant)
>> 
>> Finding k in this case equals recovering the key given a single known plaintext.  So it's hard to invert if the block cipher is strong.  
>> 
>> I suspect that AES with three rounds will give you more than 32 bits of security against inversion attacks with a single known plaintext. 
> Yes, but then I need a function with a very fast (or inexistent) key-schedule. Maybe XTEA.

AES has a relatively lightweight key schedule.  Twofish can be implemented so that it can change keys very quickly, too.  I believe quite a few of the recent lightweight block ciphers that have been proposed also have very lightweight key schedules, so they might be worth a look.  

...
>> If you need preimage resistance, but you are looking at a fairly small state, you might want to look at smaller variants of some hash functions.  There are smaller Keccak variants defined.  The 200-bit permutation version can give you more than 32 bits of preimage resistance with a 128-bit input size, and if you are only worried about a 32 bit security level, you probably can get away with a lot fewer rounds--maybe 8 or 10.  
> Where is this Keccak variant defined?

The Keccak SHA3 proposal includes scaled-down designs.  Basically, you can think of the full Keccak permutation as a 5x5 matrix of 64-bit words which gives a 1600-bit permutation.  And you can define a smaller permutation based on a smaller power of two word size.  So, the 200-bit permutation is defined by making it a 5x5 array of 8-bit words.  

They intended the scaled down versions both as toy versions of the hash functions to cryptanalyze, and as potentially useful algorithms for low-end environments.  

I think you could also define a scaled-down version of the JH permutation pretty easily.  I know Skein also defined a 256-bit wide version of their algorithm, but didn't propose it for standardization--that might be another place to look for relatively smaller hash functions that didn't have to haul around a thousand plus bits of state.   

--John