Field slide attacks and how to avoid them.

[John Kelsey]

-----BEGIN PGP SIGNED MESSAGE-----

[ To: Perry's Crypto List ## Date: 09/08/01 07:35 pm ##
  Subject: Field slide attacks and how to avoid them. ]

Guys,

I've been noticing a lot of ways you can mess up a cryptographic
protocol due to the "sliding around" of fields within a signed or MACed
message.  The classic example of this is the old attack on PGP
fingerprints, which let you use some odd keysize, and thus get two
different keys (with different keysizes) with the same hash, without
breaking the hash function.  (The raw bits of the two keys are the same,
but the fields are broken up differently.)

The natural way to resist this is to ensure that all information used to
parse a hashed/MACed/signed message is included in the signature.  But I
was curious whether anyone knows of other standard, simple ways to deal
with this problem?

I came up with a couple of very simple ones, thinking about it for a few
minutes:

a.  Require all fields to include a prepended four-byte length.

b.  Hash each field independently, and instead of using
        hash(field1+field2+field3+...+fieldN)
use
        hash(hash(field1)+hash(field2)+...+hash(fieldN))

c.  Prepend a "map" of the fields as the first field in a signed or
hashed message.  Thus we authenticate
        hash(fieldMap + field1 + field2 + ... + fieldN)

As long as fieldMap has an unambiguous length, this is guaranteed to
prevent field sliding.  I imagine fieldMap as something like a sequence
of 32-bit integers, the first being a count of fields, the rest being
the offsets of each field.

d.  Encode the fields first, in such a way that there is a single
unambigous field separator between fields.  For example, use the simple
encoding rule that anytime three bytes of successive 0x00s are encoded,
we always insert a 0x01 byte next.  Use four successive 0x00 bytes as
the field separator.   The decoding rules work just the opposite:
Whenever we run into 0x00,0x00,0x00, if the next byte is 0x00, we've hit
a field separator; if it's a 0x01, we discard the 0x01 and continue
decoding.

Methods (b) and (d) are usable even when the fields are being fed into
the message on the fly.  It wouldn't be hard to do something a little
smarter with (d) to improve its efficiency, but this would only be very
important with very specific and weird messages.  (We might have to
worry about buffer-overrun attacks based on sending an all-zero message,
though.)  It might be useful to specify which field is which, as well,
though obviously there ought not to be any ambiguity in the protocol
about that.  (But it's the sort of thing that might slip in, especially
in a design with many optional fields....)  Both the fieldMap idea and
the encoding of fields idea can be adapted to deal with this in pretty
straightforward ways.

This is the kind of thing that someone must have already dealt with in
detail.  Any references?  Are any of these ideas useful?  There is
nothing very difficult about any of them, and it would be trivial to
come up with dozens of similar fixes.

Comments?

- --John Kelsey, kelsey.j at ix.netcom.com / jkelsey at certicom.com

-----BEGIN PGP SIGNATURE-----
Version: PGP 6.5.1 Int.

iQCVAwUBO5rWNiZv+/Ry/LrBAQGPjQP9E4jwDJobaoQiDEluI2vVn0Yn/1MSRr0m
uBME1StD+X3pds54gmuZRIEfUFWu9d1DaDhkQaGLWhkB0RlIb0bCW5p5vtTykDcI
orYSUHe83V3/3GhnIb/9Z5B4Ks6dnJuhUQ9R9KNjHuHE3EfLQiqxkZCI8tUEhgv7
yqhTPj9yXCg=
=TMyU
-----END PGP SIGNATURE-----




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