[dnssec-deployment] aug2004 CAM of interest?

[Scott Rose]

Standard Disclaimer:  Not a crypto-wonk, but work for the same agency that
has some.

I did some digging on the recent news about the hash collision problem.
First, an article from The Register:

http://www.theregister.co.uk/2004/08/19/hash_crypto/

with some links to a paper that details collisions found in MD4, MD5 and
other hash algos not used in DNSSEC.

The rumor has it that there is also a possible collision found in SHA-0:

http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.html

And this same technique was used to find a collision in SHA-1, but that is
unconfirmed.  The list of papers at Crypo '04 only gives this listing:

	Hash Collisions

	Near-Collisions of SHA-0
	Eli Biham and Rafi Chen

	Multicollisions in iterated hash functions. Application
	to cascaded constructions
	Antoine Joux

http://www.iacr.org/conferences/crypto2004/accepted.html

And the papers are no online on the conference site yet.  Didn't do that
hard of a search for the proceedings, but they will probably be available
soon if not now.

What does this all mean for DNSSEC?  These attacks seem more academic and
not possible in the real world now.  However, these breakthroughs sometimes
lead to other means of producing the same results more quickly.  One
collision in SHA-1 (if true) is not a major threat now.  It may also prove
impractical to get a collision that will cover a DNSSEC RRset that could be
used to successfully launch an spoofing attack.

At worst, this will cause a shift in the standard digital signature
algorithms used with other protocols, and cause DNSSEC to follow suit for
conformity.

Scott
****************************************
Scott Rose
Adv. Network Tech. Div., NIST
+1 301-975-8439

http://www-x.antd.nist.gov/dnssec/
****************************************


> -----Original Message-----
> From: DNSSEC deployment [mailto:dnssec-deployment at shinkuro.com]On Behalf
> Of Ólafur Guðmundsson
> Sent: Wednesday, August 18, 2004 9:28 AM
> To: DNSSEC deployment
> Cc: bmanning at vacation.karoshi.com
> Subject: Re: [dnssec-deployment] aug2004 CAM of interest?
>
>
> At 14:59 17/08/2004, bmanning at vacation.karoshi.com wrote:
>
> First my regrets for most likely not be able to attend
> the teleconference this week and definitely not next week.
>
>
>
>
> >communications fo the ACM.  aug2004, vol 47, no 8.
> >"Is Hierarchical Public-Key Certification the next target for hackers?"
> >         - Burnmister & Desmedt
> >
> >and there is the crypto/rump session tonight that will discuss if SHA
> >weaknesses are real.  (would be in-opportune if DNSSEC finally
> made it out
> >the door and SHA was shown to be vulnerable a few weeks/months later)
>
> In my book this is not a big worry, for the following reason, DNSSEC
> data signed is quite structured,
> <prefix> <dname> <dnsheader> <rdata> <dname> <dnsheader> <rdata> ...
>
>
> In order perform an attack on DNS via DIGEST collisions, the attacker
> needs to solve two hard problems,
>          Find collision in hash
>          Bin-pack collision into acceptable DNS records
>
> The second problem is identical to the bin-packing problem which is
> NP-complete so there is not that much to worry about yet.
>
> Reasoning:
> All the <dnames> are identical,
> <dnsheader> should be identical except for the RDatalen field, but
> an attacker could use the TTL field.
> In the <prefix> some fields are fixed others are open to use,
>          Signer, Type covered, Algorithm, Labels, and Keytag are fixed.
>          Original TTL is open for use
>          Signature Inception and Expiration time are open for use but
>                  in a restricted manner
> So the only field left for use is RDATA, but in most cases
> the attacker cares somewhat about it, ie. it wants to convey
> certain information to the target and be believed (say a specific
> DS record).
>
> They main way for an attacker is to add a number of extra
> garbage RR to the RRset to convey one new one. The most
> valuable attack is to introduce a new DS record at a delegation.
> To do that attacker has to use some of the existing DS records,
> add the new one she wants to be trusted, and some garbage ones
> to get the hash collision.
> I'm skeptical that the  collision attack is going to be capable of
> only flipping certain bits while leaving others unchanged.
>
>
>          Olafur
>
>
>
>
> #############################################################
> This message is sent to you because you are subscribed to
>   the mailing list <dnssec-deployment at shinkuro.com>.
> To unsubscribe, E-mail to: <dnssec-deployment-off at shinkuro.com>
> To switch to the DIGEST mode, E-mail to
> <dnssec-deployment-digest at shinkuro.com>
> To switch to the INDEX mode, E-mail to
> <dnssec-deployment-index at shinkuro.com>
> Send administrative queries to  <dnssec-deployment-request at shinkuro.com>
>
>