Randomized hashing

[Peter Lebbing]

On 28/11/14 11:41, NdK wrote:
>> Oh, I agree, I already thought that might close any 'r'-swapping security
>> issues, if there would be any; just like you can include the hash
>> algorithm in the signature to prevent swapping it out for a weaker one. But when
>> swapping 'r''s does not actually create any security issues, it just makes
>> things needlessly complicated.
> I don't understand you.

I finally found the time to write this up. In part, it is a more elaborate
version of what Ingo Klöcker said in [1].

When you want to protect 'r' from modification, there are basically two ways to
do it. You can include 'r' in the hashed data, or in the signature.

I'll outline what an OpenPGP message might look like[2] with randomized hashing,
with a symbol prepended to each line that indicates whether that line is
unprotected, part of the hashed data or part of the RSA signature. A U means
Unprotected, an H means Hashed, an S means its part of the signature itself.

U One-pass Sig packet:
U     keyID 969E018FDE6CDCA1, sigclass "binary document",
U     digest randomized-SHA-1, pubkey RSA
U Randomized hashing specifier packet:
U     r = b299c230c293191bd900217ab0dc7aad
H Literal data packet:
H     This is the actual signed message.
H     It can go on for quite a while.
H     But I choose to end it here.
H Signature packet:
H     sigclass "binary document", pubkey RSA, digest randomized-SHA-1
H     Signature Creation Time subpacket:
H         Sig created 2014-12-13
U     Issuer subpacket:
U         Issuer key ID 969E018FDE6CDCA1
U     Begin of digest 49 1f
S     OpenPGP-RSA-randomized-SHA1-sign(r, <all data from H lines>)

Where OpenPGP-RSA-randomized-SHA1-sign is defined as (|| is concatenation):

OpenPGP-RSA-randomized-SHA1-sign(r, d):
H = SHA1(RMX(r, d || 0x04FF || len(d)))
m = 0x00 || 0x01 || 0xFF || ..   || 0xFF || 0x00 || 0x30 || 0x21 || 0x30 ||
    0x09 || 0x06 || 0x05 || 0x2B || 0x0E || 0x03 || 0x02 || 0x1A || 0x05 ||
    0x00 || 0x04 || 0x14 || H
return m**d (mod n)

** is exponentiation. So the signature is computed over the hash, and a constant
(which is padded with 0xFF's to make m the right size for an RSA signature).

The hash is computed over the RMX function.

The RMX function is rougly:

RMX(r, d0 || d1 || .. || dn) = r || d0 ^ r || d1 ^ r || .. || dn ^ r

^ is the xor operation here, not exponentiation. RMX is not exactly that, but
good enough for what I am trying to say. The point is, r is *included in the
hash*. That's what protects it from modification. The paper at [3] contains a
proof that it is intractable to modify r and get a message that hashes to the
same hash. This is not immediately apparent, but they prove it for hash
functions with the structure SHA-1 has.

'r' still needs to be passed to the recipient, but it needn't be protected
explicitly, since it is included in the hash anyway. In fact, it is pretty much
as if the "Randomized hashing specifier packet" I invented above wasn't of the
U(nprotected) type but of the H(ashed) type. It's just that it's solved at the
RMX level rather than the OpenPGP level.


The other way is also mentioned in the paper. I can't find the footnote you
mention; which paper were you looking at? The trade-off is that for that method,
the actual signing operation needs to be changed, which is the problem. The
advantage is that the rest of the message stays the same.

For OpenPGP One-pass-signature packets, this gets a bit silly. The purpose of
that is to start computing the hash while reading through the file the first
time. This becomes impossible with this method, so let's drop that packet,
pretend that it was never there in the first place, and we always needed two
passes. Pretend that we keep everything as it was, and only change the signing
operation.

H Literal data packet:
H     This is the actual signed message.
H     It can go on for quite a while.
H     But I choose to end it here.
H Signature packet:
H     sigclass "binary document", pubkey RSA, digest randomized-SHA-1
H     Signature Creation Time subpacket:
H         Sig created 2014-12-13
U     Issuer subpacket:
U         Issuer key ID 969E018FDE6CDCA1
U     Begin of digest 66 1a
S     OpenPGP-RSA-randomized-SHA1-sign(r, <all data from H lines>)

Now we define OpenPGP-RSA-randomized-SHA1-sign quite differently:

OpenPGP-RSA-randomized-SHA1-sign(r, d):
H = SHA1(H_r(r, d || 0x04FF || len(d)))
m = 0x00 || 0x01 || 0xFF || .. || 0xFF || 0x00 || some-new-ASN.1-specifier ||
    r    || H
return m**d (mod n)

H_r(r, d0 || d1 || .. || dn) = d0 ^ r || d1 ^ r || .. || dn ^ r

Now, r is included in the RSA signature itself. To get at it, the receiver
decodes the RSA message (raises it to the e-th power) and extracts r from it.
Then the receiver can start to compute the hash. The some-new-ASN.1-specifier is
a constant string specifying this new randomized-SHA1 scheme, because we changed
the message and can't give it the same identifier as we use for regular
RSA-with-SHA1.

In fact, they propose the latter variant, but with RMX instead of H_r, for those
cases where the message itself cannot be changed.

So that was what I was trying to say: you can include r in the hashed data, or
in the signature. They are not proposing to not protect r at all, they are
proposing you keep the signature algorithm as it is and include it in the hash.

HTH,

Peter.

[1] http://lists.gnupg.org/pipermail/gnupg-users/2014-November/051761.html
[2] This is probably not the best way to include 'r', but it illustrates the
method, rather than the actual OpenPGP packets defined.
[3] http://webee.technion.ac.il/~hugo/rhash/rhash.pdf

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at <http://digitalbrains.com/2012/openpgp-key-peter>