Subject: Hash Collision Shield (subpacket def)

From: Rick van Rein <[email-masked]>
Date: Thu, 17 Feb 2005 17:46:29 +0100

Hello,

It's a bit of a long stretch perhaps...  but it is probably the simplest
thing we can do, and it is completely backward compatible.  Suggested
text fragments follow.

The problem of the fingerprints and other hard-coded SHA1 apps are not
solved by this, of course.

Should we add a remark about subliminal channels caused by incorporating
random bytes?

Cheers,
 -Rick

------------ 8< ------------ 8< ------------ 8< ------------ 8< ------------

   The value of the subpacket type octet may be:

       2 = signature creation time
...
       32 = embedded signature
       33 = hash collision shield

...

4.2.3.27. Hash Collision Shield

    (N random octets)

    Hash functions are important to digital signatures, and breaking them
    means breaking a signature schema.  The first collision against hashes
    is usually the collision attack, because these are computationally the
    least expensive form of attack.

    After a collision attack to a hash algorithm, the time to come up with
    an attack that can completely reverse a given hash value is incredibly
    long.  This means that shielding against collision attacks is a very
    practical method of prolonging the secure use of hash functions.  This
    is useful for applications such as timestamps and non-revocable
    signatures, because these may have to be valid for very long periods.

    An attacker could mount a collision attack by predicting the signature
    calculation and preparing two documents with colliding hash values.
    One document would be signed by someone other than the attacker, the
    other document would be exploited with that signature attached.

    Such attacks can be avoided if the signer makes the signing process
    unpredictable to the attacker.  The simples way to do that is to
    generate random octets per signature, under full control of the signer,
    and include them in the hashed subpackets of a signature packet.

    The number of random octets SHOULD match the length of the hash used in
    the signature.  This subpacket MUST NOT be flagged as critical and MAY
    remain without interpretation in the verification process.

---

From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2005 12:17:26 -0500

> Should we add a remark about subliminal channels caused by incorporating

I think we should not do this for several reasons, but those reasons
don't matter much: we already have signature notations.  If someone
wants to add arbitrary stuff in the middle of their signatures, they
can do that now.

David

---

From: Jon Callas <[email-masked]>
Date: Thu, 17 Feb 2005 18:23:03 -0800

> wants to add arbitrary stuff in the middle of their signatures, they

I agree completely. Notations are the way to do this.

However, I also think this is a very bad idea. We already have pulled 
things out of OpenPGP because they could be used for subliminal 
channels, and there are a lot of people who think that DSA is the work 
of Satan because it has random data and thus subliminal channels.

However, if someone wishes to add in extra random data, then a notation 
is a fine way to do it.

	Jon

---

From: Rick van Rein <[email-masked]>
Date: Fri, 18 Feb 2005 08:56:00 +0100

Hello,

Jon and David said a similar thing:

> >don't matter much: we already have signature notations.

Indeed, that would be the other way of doing it.  The likeliness of
implementations actually using it is less if they are not confronted with
the technique though.  Is it an idea to add a bit under the notation data
section instead?  I'm volunteering.

> channels,

This is definately the weak point of this strategy, as said in the header.
It applies equally to notation data encoding, of course.
But it it does seem to be the only way to make durable signatures.

Hal liked the idea but pointed out that collisions might have occurred
before the random data was hashed,  Actually that is such a strong downer
that I am now wondering what the added value of this approach would be.

> But we could specify it to work this way: we'd have a subpacket with
> the random data, and its meaning is that this stuff gets hashed first
> when we do the signature calculation.  We'd be changing the rules for
> how signatures are calculated.

I could never agree to such a strong break in compatibility; also
because it would be an optional extension and lead to less complete
implementations breaking on it.

Thanks,
 -Rick

---

From: Ian G <[email-masked]>
Date: Fri, 18 Feb 2005 16:05:08 +0000

>section instead?  I'm volunteering.

If there is a way to do it already, then that
would be better than any changes.  We have
tried (ok, some of have tried) to take a razor
to OpenPGP and cut off many bows and frills.
Adding another little feature without a clear
need faces an uphill battle.

Adding a note that a notation packet could
be used as an anti-collision technique seems
like a fine idea.  As it's somewhat forward
thinking, I'm not sure where it would go tho,
possibly in the last section of security oddments?

Also, there is a discussion going on here:

http://www.educatedguesswork.org/movabletype/archives/2005/02/next_steps_for_1.html

where Craig Hughes / Dan Simon claim that
introducting random hashing increases collision
resistence, but at the expense of decreasing
other forms of resistence.

>implementations breaking on it.

Yup!  It's really tough adding in little quirks
at this stage.

iang

-- 
News and views on what matters in finance+crypto:
        http://financialcryptography.com/