3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Isn't the attack you describe for Winternitz mitigated by using a checksum? You structure it so that if any WOTS chain's value is incremented, the checksum is decremented. So there is no way to forge without having to compute at least one preimage -- that is find one value x for a known H(x). $\endgroup$
    – Adam Ierymenko
    Mar 8, 2018 at 21:34
  • $\begingroup$ Also in terms of post-quantum: let's say you have a quantum computer that can run Grover's algorithm and roughly halve your 128-bit hash to 64 bits. You still have 64 bits of security, which is not secure enough to remain secure forever but will take a considerable amount of time to brute force. The use case I have in mind doesn't require signatures to remain secure forever but only for -- say -- a few hours at most. (In practice it's generally a few minutes, but let's say 12 hours to give a hefty margin.) $\endgroup$
    – Adam Ierymenko
    Mar 8, 2018 at 21:36
  • $\begingroup$ If you're curious the application would be a block chain with a block rate of one block every 10-20 seconds, so after a minute or two a signature is permanently etched in stone within the chain and protected by much stronger (512-bit) hashes. Signatures need to protect transactions until they are committed to a block. $\endgroup$
    – Adam Ierymenko
    Mar 8, 2018 at 21:37
  • 1
    $\begingroup$ @AdamIerymenko: nope; what this attack is doing is looking for a preimage. The point is that you don't have a single target to be a preimage, you have lots of targets (and, yes, blocks in the 'public part' of the chain are also targets, if you can find alternate chains that end with that value) $\endgroup$
    – poncho
    Mar 8, 2018 at 21:43
  • 1
    $\begingroup$ @AdamIerymenko: actually, the attack can work like this; repeatedly compute $x = H(x)$ (and remember the previous 255 x's); if any of the values happen to be the same as any of the ones in the valid chain, you've found a (complete) valid chain for this digit, and so can set it to any value. It doesn't matter if that H(x) value is the one in the signature; any of the subsequent values would work (as the signature would still validate) $\endgroup$
    – poncho
    Mar 8, 2018 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.