Matyas–Meyer–Oseas for super-fast single-block hash function Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?

By single block hash function I mean one that hashes, say, 128 bits of input and produces 128 bits of output. I don't need variable or larger message sizes and if I did I'd use SHA-2, SHA-3, etc., but those are a lot slower for really short fixed length messages. Benchmarks show that this AES construction is more than 10X as fast for hashing single block length messages on a machine with AES-NI CPU extensions.

If I'm understanding Matyas–Meyer–Oseas, the hash function would consist of AES initialized with a static predefined key and then used to encrypt a single block of input ("ECB" mode). The result of encryption would then be XORed with the original block to produce an output hash. Further initialization of the cipher with subsequent blocks wouldn't be done since you're only hashing messages whose size is equal to the block size.

If you're curious the application would be Winternitz one-time signatures. Winternitz signatures involve a whole lot of iterative hashing of single block size messages. Preimage resistance is important so a good hash function is needed but for compact signatures you want to increase the height of the "columns" in the signature.
Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?


Mostly, yes.  It is one standard approach to convert a permutation into a one-way function (at fairly small expense).  It does have some odd properties (e.g. it's easy to find the fixed point, that is, the block that hashes to itself), but those are typically not a concern.


  If you're curious the application would be Winternitz one-time signatures.


That brings up some concerns.  For one, Winternitz one-time signatures consist of a series of $H(x)$ values, and you can forge if you can find any of the $x$ values.  You are using the exact same $H$ function for each iteration; what an attacker can do is compile the list of $H(x)$ values he's looking for, and compute $H(y)$ for various values of $y$; if it happens to match any of his target $H(x)$ values, he wins.  For example, if your signature consists of 34 Winternitz chains of length 255 each (that's 256 bits, plus checksum), then there are an expected 4000+ hashes that are potential targets [1]; that cuts your security by 12 bits.  This can be mitigated somewhat by using different AES keys for the different chains, but that's not free, and it only reduces the concern.

The existing proposals for doing Winternitz, such as XMSS or LMS, get around this by stirring in a different value for each Winternitz iteration (and so each $H$ invocation is distinct), and hence such multicollision attacks do not apply.

The other objection depends on why you're using a OTS (and not a more standard signature algorithm, such as RSA or E[Cd]DSA).  One potential reason is for Quantum Resistance; for that, 128 bits of hash output don't cut it.  Now, there are other potential reasons (e.g. your signer or your verifier has constrained resources), and so this objection might not apply.



[1]: Note: not only the hash that appear in the signature are potential targets, but any hash latter in the chain as well.