Randomized hashing

NdK ndk.clanbo at gmail.com
Thu Nov 27 17:10:08 CET 2014

Il 27/11/2014 11:28, Peter Lebbing ha scritto:

[Resending to list]

> Perhaps I should add that it takes real research and formal proof to show that
> this randomized hashing doesn't add attack vectors, and I have been glossing
> over that. But that is because at a glance it looks like such research has been
> done. That doesn't mean it's a fact that there are no significant attack
> vectors, but it does give the scheme credibility.
Well, I'm no expert, but it gives me the feeling of being potentially
dangerous, since once the attacker have your signature for a document
  s=E(Prk, H(RMX(M,r))) , r
(note that r is not signed, as the rhash scheme suggests and the paper
confirms!) he *might* be able to calculate r' so that RMX(M',r') ==
RMX(M,r) then 'recycle' your signature for M'. Remember that RMX is
proposed to be a simple block-xor! For very short (less than a single
hash block) messages it's trivial, if I'm not badly mislead by the
graphic description in the site:
RMX(0, 1) == RMX(1, 0)

Citing from the paper: "RMX can be used with any hash-then-sign scheme
by replacing the digest H(m) in the original signature scheme with H(RM
X(r, m)). In this case, the salt r is generated for each signature by
the signer and transmitted to the verifier together with the message and
signature[1]" and the footnote [1] is "In contrast to a previous
proposal by the same authors, the salt r does not need to be included
under the signature." . I haven't yet found out why he changed his mind.
At a first glance, it would be safer to have r *inside* the signature.
This way the attacker couldn't change it. But maybe that exposes other

To me it appears that *any* encryption of the message before hashing
would lead to analogue security properties. Say you generate 'r' and use
it as 'session key' to block-encrypt M then sign the hash of encrypted M
(IMVHO it's better if the signature includes r too). Maybe it's just a
performance issue?

BTW, some smartcards want you to feed 'em the hash state and the last
block of data so they can calculate the last hashing step by themselves.
And IMVHO it's better if the padding is generated by the card, depending
on the operation being performed: while the op is anyway 'RSA encrypt',
the padding should be different if you're signing an hash or exchanging
a session key. Failing to let the card do the padding could lead to
exposure of the private key, IIRC.


More information about the Gnupg-users mailing list