Subject: RE: [dhcwg] Re: DHCID and the use of MD5 [Re: Last Call: 'Resolution ofFQDN Conflicts among DHCP Clients' to Proposed Standard]

From: "Bernie Volz \(volz\)" <[email-masked]>
Date: Mon, 28 Nov 2005 17:13:09 -0500

[ Moderators note: Post was moderated, either because it was posted by
   a non-subscriber, or because it was over 20K.  
   With the massive amount of spam, it is easy to miss and therefore 
   delete relevant posts by non-subscribers. 
   Please fix your subscription addresses. ]

BTW, whatever algorithm you use (SHA-256 or even something much more
complex) is not going to help -- it may make the work someone has to do
a bit more involved, but it really doesn't make it impossible.

1. You always have a brute force attack. As you indicate, calculating
the hash based on the mac address is always going to be a possible
attack. And, 8000 is not 8-bits, but more like 13. But agreed that many
of the Ethernet OIDs are unlikely to be of much interest.

2. If the attacker is on the same network as the client at some point,
they can learn the identifier of the client (snoop DHCP and/or ARP
traffic). Once they have that, it is possible to query DNS for DHCID RRs
(query for the PTR, query for a DHCID RR for the name). Once you have
that, you use the name and client's identity and run it through the
algorithm and check for a match. If you looked up all 2^32 PTRs, you'd
be able to locate the client at other sites that use DHCP and export the
DHCID RR information. The number of PTRs you'd likely have to query is
much smaller than 2^32s.

You could target just some domains (network addresses) that you were
most interested in or where you suspect the client connects to the
network. Far reducing the number of queries needed.

- Bernie

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of Steven M. Bellovin
> Sent: Monday, November 28, 2005 11:49 AM
> To: Ted Lemon
> Cc: [email-masked]; [email-masked]; [email-masked]; 
> Pekka Savola; [email-masked]
> Subject: [dhcwg] Re: DHCID and the use of MD5 [Re: Last Call: 
> 'Resolution ofFQDN Conflicts among DHCP Clients' to Proposed 
> Standard] 
> 
> In message <[email-masked]>, Ted Lemon writes:
> >Making a hash function interchangeable in DHCID makes the 
> conflict detection 
> >algorithm hugely more complicated, and possibly not workable 
> at all.   Think 
> >about how that would work.
> >
> I confess that I don't see the problem.  The updater would do a DNS 
> query for DHCID RRs; it would be given all of the stored 
> records.  The 
> updater would then use local policy -- that is, an ordered list of 
> preferred hash functions -- until it found one that was in the 
> response.  That one would be used.  If no locally-known hash 
> functions 
> are in the list, it should behave as if there were no DHCID records 
> present for that name.  DNSSEC could protect against 
> downgrade attacks.
> (Speaking of which -- were I still AD, I'd ding this document for an
> inadequate Security Considerations section -- apart from the 
> lack of discussion of brute force attacks, you should cite 
> 3833 for DNS 
> attacks and explain what the risks are if someone can crack the hash 
> function by any means, including brute force or eavesdropping on the 
> wire or (perhaps) a misbehaving updater.)
> 
> If you don't agree, I'd strongly suggest using SHA-256 
> instead of MD5.  
> Yes, it's more expensive, but I doubt that that's a major hit on 
> overall system performance here.  It would also be useful to 
> include in 
> the document some discussion of upgrade strategy -- how would we ever 
> switch to a new hash function?  That's non-trivial even for protocols 
> designed for agility, as Eric Rescorla and I have shown.  No 
> matter how 
> it's done, this one is among the very hardest, since DNS 
> servers would 
> have to supply DHCID records for several hashes for a number of years.
> 
> 		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb
> 
> 
> 
> _______________________________________________
> dhcwg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/dhcwg
> 

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: "Bernie Volz \(volz\)" <[email-masked]>
Date: Mon, 28 Nov 2005 17:43:13 -0500

BTW: Just to be clear, the MD5 hash is calculated using both the client
identifier AND the domain name. But the domain name is known (it is the
entry under which the DHCID RR lives).

However, this means that the DHCID data for a client changes with its
name.

   The RDATA for all type codes other than 0xffff, which is reserved for
   future expansion, is formed by concatenating the two type bytes and a
   16-byte MD5 hash value.  The input to the hash function is defined to
   be:

       data = MD5(< identifier > < FQDN >)

   The FQDN is represented in the buffer in unambiguous canonical form
   as described in RFC 2535 [8], section 8.1.  The type code and the
   identifier are related as specified in Section 3.3: the type code
   describes the source of the identifier.

- Bernie

> Sent: Saturday, November 26, 2005 11:57 AM
> To: Pekka Savola
> Cc: [email-masked]; [email-masked]; [email-masked]; 
> [email-masked]
> In message <[email-masked]>, 
> Pekka Savola writes:
> >Hi,
> >
> >I'll break out the most substantial comments in separate messages..
> >
> >On Mon, 14 Nov 2005, The IESG wrote:
> >> The IESG has received a request from the Dynamic Host 
> Configuration WG to
> >> consider the following documents:
> >>
> >> - 'A DNS RR for Encoding DHCP Information (DHCID RR) '
> >>   <draft-ietf-dnsext-dhcid-rr-10.txt> as a Proposed Standard
> >> - 'Resolution of FQDN Conflicts among DHCP Clients '
> >>   <draft-ietf-dhc-ddns-resolution-10.txt> as a Proposed Standard
> >> - 'The DHCP Client FQDN Option '
> >>   <draft-ietf-dhc-fqdn-option-11.txt> as a Proposed Standard
> >> - 'The DHCPv6 Client FQDN Option '
> >>   <draft-ietf-dhc-dhcpv6-fqdn-03.txt> as a Proposed Standard
> >
> >I have only one major comment on DHCID on its use of MD5 as a 
> >glued-in hash-function.  The rest of the comments are rather 
> >straightforward.
> >
> >substantial
> >----------
> >
> >    In order to avoid exposing potentially sensitive identifying
> >    information, the data stored is the result of a one-way 
> MD5 [5] hash
> >    computation.  The hash includes information from the 
> DHCP client's
> >    REQUEST message as well as the domain name itself, so 
> that the data
> >    stored in the DHCID RR will be dependent on both the client
> >    identification used in the DHCP protocol interaction and 
> the domain
> >    name.  This means that the DHCID RDATA will vary if a 
> single client
> >    is associated over time with more than one name.  This makes it
> >    difficult to 'track' a client as it is associated with 
> various domain
> >    names.
> >
> >    The MD5 hash algorithm has been shown to be weaker than the SHA-1
> >    algorithm; it could therefore be argued that SHA-1 is a better
> >    choice.  However, SHA-1 is significantly slower than MD5.  A
> >    successful attack of MD5's weakness does not reveal the 
> original data
> >    that was used to generate the signature, but rather 
> provides a new
> >    set of input data that will produce the same signature.  
> Because we
> >    are using the MD5 hash to conceal the original data, the 
> fact that an
> >    attacker could produce a different plaintext resulting 
> in the same
> >    MD5 output is not significant concern.
> >
> >==> while the informatione exposure of someone cracking the MD5 hash 
> >is not too huge, I believe it is unacceptable to design new 
> protocols 
> >without the capability to switch the hash function as need be.  This 
> >could be achieved for example by reserving one additional byte from 
> >the start of the DHCID record to designate the hash function used. 
> >If you don't bother to define your own registry (for all of me, you 
> >could include MD5 there as well, but at least include SHA1 and 
> >preferably also SHA-256), you could possibly re-use 
> >http://www.iana.org/assignments/ds-rr-types or something like that.
> >
> >That way, we can introduce new hash functions in a backward 
> compatible 
> >manner later on, with no need to revamp the protocol.
> >
> >If we don't do this, we'll need to define DHCID2, DHCID3, .. etc. 
> >records further down in the future (w/ different hash functions) and 
> >make DHCP co-exist with all of them.  That's bound to cause a lot of 
> >protocol complexity, and I don't think we want to go there.
> 
> I agree with this comment.  The draft is wrong -- it asserts that a
> "successful attack of MD5's weakness does not reveal the 
> original data".
> That's an overassumption -- we have no idea what such an attack would 
> yield, since no such attack currently exists.
> 
> More generally...  The currently-known attacks on MD5 are collision 
> attacks: it's possible to generate two inputs that produce the same 
> hash value.  This scenario requires a preimage attack; none are known.
> It would not surprise me if someone were to develop one, but 
> until that 
> happens we can't speculate on its properties.  There are, 
> however, some 
> reasons for concern.  One of the options defined, the DHCPv4 Client 
> Identifier, probably doesn't have much entropy.  For example, a 
> suggestion in RFC 2132 says to use the ARP hardware type code and MAC 
> address.  There's exactly one interesting hardware type code for most
> users, and the high-order 3 bytes of the MAC address are the 
> manufacturer's ID, not many of which are actually used.  Given that 
> this is an 8-byte input string and that MD5 has an 8-byte 
> output, it is 
> plausible that comparatively few input strings hash to any 
> given output.
> If several of the input bytes are fixed, or at least 
> constrained, there 
> may be only one.  For that matter, that assumption alone may 
> lead to a 
> successful attack on MD5. 
> 
> In fact, the Security Considerations section should analyze the 
> (non-trivial) probability of a brute-force attack.  Again, 
> consider the 
> Client Identifier, which is likely 8 bytes long.  2 are fixed, and 
> hence irrelevant.  According to today's copy of
> http://standards.ieee.org/regauth/oui/oui.txt there are 8786 
> manufacturer IDs, or slightly more than 8 bits.  Effectively, though, 
> it's less, since the usage is very non-uniform.  Even if is uniform, 
> though, that field plus the unit identifier only total 
> slightly over 32 
> bits -- well within anyone's capabilities.
> 
> Most of this analysis applies to the other two options as well.
>