[Cryptography] Pre-image security of SHA-256 reduced to 16 rounds
crypto.jmk at gmail.com
Mon Feb 3 11:56:32 EST 2014
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.
More information about the cryptography