Subject: [Cfrg] Cryptographic hashes in URNs (was: Comments on draft-thiemann-cbuid-urn-00)

From: Benja Fallenstein <[email-masked]>
Date: Wed, 16 Jul 2003 00:57:12 +0200

Hi all,

This is a discussion about the registration of a URN namespace based on 
cryptographic hashes, i.e., a namespace of octet streams as identified 
by their hashes.

Some security-related issues have (unsurprisingly) turned up, so I'm now 
cross-posting to three mailing lists--

- urn-nid (technical discussion of URN namespace registrations)
- p2p-hackers (because one important user base would be the p2p community)
- the IRTF crypto forum (to pick their minds about the security issues).

I think it's appropriate in all three, but please stay strictly on topic :-)

Justin Chapweske wrote:
 > [Peter Thiemann wrote: -bf]
>> Well, I'm pretty sure that the URN scheme should *not* fix one
>> particular hash function. Instead, it should be extensible so that it
>> does not become obsolete just because a hash function is broken or
>> somebody discovers a new super-safe or super-efficient hash function.

[Later in the mail, Peter even suggested a registry for hash functions.]

> I actually disagree.  In order to avoid chosen-algorithm attacks,
 > the set of standardized hashes should be kept very small and directly
 > under the control of the IETF and at the guidance of the CFRG.

I agree; if we have a urn:hash: namespace or similar, the list of 
allowable hash functions should be fixed in the namespace registration, 
and only be changeable by going through the RFC process.

Regarding chosen-algorithm attacks, we have to keep in mind what our 
adversary model is. It should be noted that the hash function is picked 
by the person publishing a URN, not by the person a file is downloaded 
from. An attack using a hash collision would still be possible, but it 
would go more like this:

- Find a hash collision, H = h(x) = h(y), x != y.
- Use x to obtain some form of a "good rating" on H; this could include 
something like having an independent, widely trusted entity publish H as 
the hash of some good data, or even obtaining a signature on H.
- Make y available for download with H as its id.

If the URN is published by someone else than the adversary, the 
adversary doesn't get to choose the algorithm.

 > By having it as a top level URN scheme such as urn:sha1, implementors
 > will tend to focus on the algorithm itself rather than the notion
 > of generic hash-based naming.

Maybe you're right. OTOH this doesn't generalize to using combinations 
of hash functions (more on this below).

> We must avoid having a generic hash name space that allows developers
 > to add new hashes willy-nilly.  I believe that many non crypto-savvy
 > developers would tend to support every algorithm specified in the
 > name space without understanding that by supporting multiple agorithms
 > you introduce a weakest-link condition.

These are separate issues. Having developers add non-standard hash 
functions seems like a really bad idea. Supporting every function in the 
namespace registration may be a bad idea, but do you trust 
non-crypto-savvy developers to make a sensible *choice* of which 
algorithms to support (assuming that there *are* namespaces for 
different functions, including maybe md5 for backward compatibility).

It should also be noted that the spec can try to educate those people 
that do read it. Of course there are always those that never read the 
spec, just use what the others use.

> Also, for reasons of interoperability, it would be useful if the number
 > of different URNs be kept small.

I agree, but what about developers who don't want to use e.g. SHA1 for 
technical reasons? (In particular hash size; possibly also backwards 
compatibility, especially if they have a running system they want to 
augment with URNs.) Well, maybe such developers aren't plentiful; 
anybody know any? (Not sure how on-topic this is for CFRG tho.)

 > A large number of the P2P developers have agreed upon SHA1 for the time
 > being, which could potentially enable very simple interoperability
> between these systems.

True, but there are also the two technical points against using SHA1 alone:

- Many systems today use hash trees for multisource downloading. (Of 
course you can use a SHA1 hash tree, but that obviously doesn't give you 
the interoperability with plain SHA1 systems.)
- Using just one function makes repair after the function is broken much 
more difficult (again, more below).

> I also think some mechanism should be introduced to deprecate hash schemes
 > over time.  So while urn:md5 would be a decent name space to add for
 > compatibility with existing MD5-based applications, such a scheme 
should be
 > immediately denoted as being deprecated to avoid having new applications
 > adopt MD5.

Agreed.

>>     BF> I would suggest adding the ability to use more than one hash function
>>     BF> in the same URN.
>>
>>     BF> The syntax could look for example like this:
>>
>>     BF>      urn:cbuid:md5.sha1:<md5-hash>.<sha1-hash>
>>
>> That sounds like a good proposal to me, it gives you increased
>> confidence and robustness virtually for free. I'll put a concrete
>> syntax proposal at the end of this message.
> 
> I don't believe this is a good idea from a security perspective.  I fear that
 > most implementors would only verify one of the hashes, and unless 
they make a
 > judicious choice about the hash to verify, they are again opening 
themselves to
 > a chosen-algorithm attack.  Otherwise, implementors w/o the proper 
context to
 > decide which hash is the strongest are forced to verify both hashes, 
which will
 > cut their hashing performance roughly in half.
 >
> Zooko, do you have any thoughts on this?  These seem like the types of attacks
 > that you've spent a lot of time thinking about.

Zooko replied:
> I *have* thought about this issue.  The short of it is: I'm not sure how to do 
> it right, so I'm not going to do it.

(I understand this as: "I'm not going to use more than a single hash 
function in the id.")

> For example, what should the required/allowed behavior be when one of the 
> hashes fails to match and the matches?  Are implementors required to check all 
> hashes that are included?

My take on this is: Generally, yes.

If you don't, you open yourself to a very similar attack to the one I 
described above regarding chosen-message attacks. Assume that two hash 
functions, g(.) and h(.) are in use.

- Create a URN containing g(x), h(y) for x != y.
- Using x, obtain an endorsement for the URN from someone who verifies 
only g(.).
- Use the endorsement to "sell" y to someone who verifies only h(.).

Yes, verifying only one of the two hashes takes longer. Well, verifying 
one hash takes longer than verifying zero hashes; let's specify a system 
without this kind of security holes.

I think that using a URN which includes two hashes should be read as a 
statement by the URN's creator that they think verifying two hashes is 
reasonable. If you don't agree with them, don't resolve their URN in the 
first place...

(I don't see why Justin thinks that verifying only one hash would 
introduce chosen-algorithm attacks, though. Assume that a verifier is 
capable of verifying both g(.) and h(.), but verifies only g(.), which 
happens to be insecure. I think it is reasonable to think that the 
verifier would also accept a URN including *only* a g(.) hash; thus, the 
double hash isn't necessary for the attack. And if the developer of the 
verifier knew that g(.) was insecure, surely they wouldn't make their 
program verify only g(.) in the first place. Maybe someone can enlighten 
me on chosen-algorithm attacks made possible by using two functions.)

The one exception I would make to having to verify both hashes is when 
the verifier doesn't have an implementation of both hash functions. In 
these cases, I would say that an implementation MAY reject the URN, but 
if it does not, it SHOULD provide an indication to the user that the 
verifier cannot guarantee that everybody else will see the same file 
behind this URN as given. The verifier could also provide an alternative 
URN where this *can* be guaranteed (i.e., one containing only one hash).

> I suspect that there might be a way to do secure, smooth, backwards-
> compatible upgrade past certain kinds of hash algorithm breakages.  However, 
> I haven't seen a complete description of how it would work.

Ok. I assume that you mean, a way to continue to use identifiers even 
after the hash functions used in these identifiers are all broken.

For the following, you have to have a secure timestamping service. 
Assume that your identifiers include two hashes, using g(.) and h(.). 
Assume that g(.) is broken, but h(.) still works. Assume that you have 
decided upon a new hash function, i(.), which you will in the future use 
together with h(.). For every file x where you have the contents, not 
just the hash, you can:

- Compute h(x) and i(x).
- Timestamp the statement: "H = h(x) and I = i(x) are hashes of the same 
file."

Now suppose that h(.) is broken, but i(.) still works. Assume that you 
have an old-style identifier containing g(x) and h(x). Assume that you 
have downloaded y, an alleged copy of x; you want to verify it against 
the identifier containing G = g(x) and H2 = h(x). You have the timestamp 
certificate of the above statement.

You now verify that g(y) = G; h(y) = H = H2; and i(y) = I.

If this holds, you can be sure that y = x. Proof: Assume that y != x. We 
know that h(y) = h(x). That's not something big; at the time of 
verification, we know ways of computing collisions for h(.).

However, the timestamped statement contains I = i(y). At the time of 
verification, it is believed that nobody can obtain hash collisions on 
i(.). Therefore, at the time of verification, the adversary must have 
used y to compute i(y), or, alternatively, created a timestamp for every 
possible value of i(.). Since timestamping involves hashing, creating a 
timestamp for every possible value of i(.) requires at least as much 
computing power as mounting a birthday attack on the function used, 
which is held to be impossible. Thus, someone has intentionally 
associated h(x) with i(y), and thus y.

To know that it makes sense to associate h(x) with y, the person must 
have known, at the time, that h(x) = h(y).

Therefore, if y != x, then someone must have known that h(x) = h(y), 
**at a time where no way to compute a hash collision on h(.) was known, 
yet**. This is held to be impossible; thus, y = x, q.e.d.

Does this satisfy you?

Note that you cannot use the above in a system using only one hash 
function-- because once your hash function breaks, your timestamps, 
using that hash function, break as well! At every time, you need at 
least one hash function that remains unbroken.

I should also note that the above idea is patented in the US and 
probably elsewhere. However, patents expire (this one in the 2010s, I 
think), and this is long-term thinking.

> (The algorithm-negotiation features of SSL/TLS might be considered an example 
> of what *not* to do, and in any case they cannot be carried over to this 
> application since they are interactive.)

Yup and yup. (Some protocols may use hash URNs as return values and may 
include algorithm negotiation, but that would be a security issue with 
those protocols, not with the hash URN spec.)

We can of course use a different URN namespace identifier for each hash 
function, i.e.,

     urn:sha1:...

A point in favor of this would be that people use it already.

I'm not sure how this interacts with using different hashes in a single 
URN, though. I think there should be a method to do so, in order to 
enable the lifetime extension as described above, and in order to 
combine 'industry standard' SHA-1 hashes with a tree hash that enables 
multisource downloading.

I think that the specification should probably say that an 
implementation must check all hashes, except at explicit user 
discretion. I think that if an an application does check all hashes, 
there are no security considerations with using more than one hash. OTOH 
there are security benefits-- if only that birthday attacks become 
harder to mount because of the additional bits.

The question then is, if we allow e.g. {sha1,sha256,tiger} each by 
itself, do we also allow every possible combination of the above? Or do 
we limit ourselves to a specified set of combinations, e.g. sha1+tiger 
but not sha1+sha256?

I believe that there is no security gain from allowing the former but 
disallowing the latter. OTOH I could easily imagine that if sha1+tiger 
is popular, some people would like to use sha1+tiger+sha256 for added 
security.

There is the issue of having less URNs per resource, of course, which is 
outside the security domain I think. I'm not sure how much a concern 
this is... opinions?

If we allow all possible subsets, using URN namespace names becomes 
problematic; we'd have to register

     urn:sha1:...
     urn:sha256:...
     urn:tiger:...
     urn:sha1+sha256:...
     urn:sha1+tiger:...
     urn:sha256+tiger:...
     urn:sha1+sha256+tiger:...

(urks). Or, we'd have to do something like, use urn:sha1:... for just 
one hash but urn:hashes:sha1+sha256:... for more than one hash. Then, 
we'd only have to register

     urn:sha1:...
     urn:sha256:...
     urn:tiger:...
     urn:hashes:...

Opinions?

Thanks,
- Benja

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Justin Chapweske <[email-masked]>
Date: Tue, 15 Jul 2003 19:13:16 -0500

> more difficult (again, more below).

As they are defined today 
(http://open-content.net/specs/draft-jchapweske-thex-02.html), the tree 
hashes are parametizable to allow different file segment (leaf) sizes to 
be specified.  IFAIK other traditional digest algorithms are set in 
stone, allowing no parameterization(?).

If appropriate, I would be interested in certain hash tree forms being 
validated and standardized as normal digest functions.  This would allow 
hash tree forms to be incorporated into existing standards that rely on 
a normal digest function.

In regards to using multiple functions, most current systems that output 
multiple functions simply output them as multiple seperate pieces of 
metadata.  For instance, a system could output something like the following:

X-Content-URN: urn:sha1:FAB6CX2GZSWOOWCPXXBYSFBUSN4LIGTF
X-Content-URN: urn:tree:tiger:3FOBMWPE2JED5DUN2VA6J7DGSNJNJILE4HRF6SQ

I believe that in many systems the hashes will simply be treated as 
pieces of meta-data that are used to verify the integrity of a file. 
Just because they contain 'urn' in them doesn't mean that they have to 
be used as identifiers.  So, if you look at it from the meta-data 
perspective, I think its natural to use multiple independant hashes 
rather them glomming them all together.

> me on chosen-algorithm attacks made possible by using two functions.)

My point is subtle and perhaps irrelevant, but let me try to clarify:

When I see something like:

urn:hash:sha1.md5:<foo>

This implies to me that I am obligated (not sure to whom) to verify both 
hashes.  I believe these semantics are reasonable, however you will find 
very few developers will be willing to follow these semantics and verify 
both hashes.

However, when I see something like:

X-Content-URN: urn:md5:42J46YB3Y3OLLFYL52B4LNDE34
X-Content-URN: urn:sha1:FAB6CX2GZSWOOWCPXXBYSFBUSN4LIGTF
X-Content-URN: urn:tree:tiger:3FOBMWPE2JED5DUN2VA6J7DGSNJNJILE4HRF6SQ
X-Content-URN: urn:crc32:<foo>

This implies to me that I should apply some sort of ranking between the 
algorithms and not use any that are below my standards.  If I am not 
confident about any single hash, I am free to verify multiple of them.

Obviously from a technical perspective, both approaches are the same, it 
just seems to me that the first approach invites developers to defy the 
semantics, while the second approach is likely to be a healthier approach.

I am not a developer psychologist, so I'm very open to other viewpoints 
on this.

-- 
Justin Chapweske, Onion Networks
http://onionnetworks.com/

---

From: Benja Fallenstein <[email-masked]>
Date: Wed, 16 Jul 2003 03:02:25 +0200

Hi,

> a normal digest function.

Seems appropriate to me.

> rather them glomming them all together.

Well, I use them as context-less names that resolve to something; and 
you simply cannot give two different URNs in one <a href="...">. If you 
use them as metadata about a different resource, then I agree you don't 
need to put different hashes into a single URN.

(OTOH, if you go the other way around, and want to give RDF metadata 
about a resource identified by a hash-URN-- e.g., ratings or 
locations--, there are good reasons for using a URN with more than one 
hash again, so that the resource name you store information about 
doesn't need to become invalid if one hash function is broken.)

>> verifier would also accept a URN including *only* a g(.) hash; thus, 
>> the double hash isn't necessary for the attack. And if the developer 
>> of the verifier knew that g(.) was insecure, surely they wouldn't make 
>> their program verify only g(.) in the first place. Maybe someone can 
>> enlighten me on chosen-algorithm attacks made possible by using two 
>> functions.)
> 

I dunno... if the spec explains how this is a security leak, and the 
developers still do it, I think there's little I can do...

> confident about any single hash, I am free to verify multiple of them.

I would actually agree with your assessments of the meaning of both 
statements -- the first implies you have to verify both, the second 
implies you have to verify as many as you deem necessary.

So your point is: Because many developers will-- maybe-- use the second 
kind of semantics always, having the form aiming for the first kind of 
semantics is futile.

I need the first kind of semantics, though, if I want to use hash URNs 
as reliable, trusted, *context-less* identifiers. (I.e., without being 
able to give more than one URN in an <a href>.) I think having a way to 
convey these semantics would be good, even if some people will implement 
it in an insecure way.

Seems to me like this is generally useful where people use URNs for 
identifiers. I mean, when I post a URN in a forum, giving two URNs seems 
less practical and posting a number of URNs and saying "Download as many 
of these as you need to meet your security requirements, and verify that 
they are all equal" seems weird. :-) You should click on it and your 
software should handle the rest.

My current thinking is that if the spec explains in which way verifying 
only one hash is a security leak, and if developers still do it, then 
it's an issue between the developers and their users-- if the users and 
developers are willing to accept the security leak of having somebody 
recommend a URN they haven't fully checked, then that's their problem, 
I'd think.

- Benja

---

From: Carl Ellison <[email-masked]>
Date: Wed, 16 Jul 2003 08:06:07 -0700

Benja,

	I apparently don't know the rules for URN formation.  I thought it
was completely free after the "urn:".  Is that not true?

	I'm skipping most of this conversation, to comment on a single point
at the end..

	Is urn:sha1:dRDPBgZzTFq7Jl2Q2N/YNghcfj8= not now legal?

At 12:57 AM 7/16/2003 +0200, Benja Fallenstein wrote:
>(urks). Or, we'd have to do something like, use urn:sha1:... for
>just  one hash but urn:hashes:sha1+sha256:... for more than one
>hash. Then,  we'd only have to register
>
>     urn:sha1:...
>     urn:sha256:...
>     urn:tiger:...
>     urn:hashes:...
>
>Opinions?

When you combine hash functions, you need to specify the combining
function also.  I assume you were assuming mere concatenation, here. 
It's often more than that.  So, the concatenation function would have
to be listed also.

My personal preference is for anyone who wants to do this to declare
a new hash function name and define it as the particular combination
function of the particular other hash functions, but use that new
hash function name in things like the URN construct.  We've seen a
couple of these, but not very many and I don't see a reason to
encourage people to do this kind of concatenation.

 - Carl

+--------------------------------------------------------+
|Carl Ellison      Intel R & D       E: [email-masked] |
|2111 NE 25th Ave                    T: +1-503-264-2900  |
|Hillsboro OR 97124                  F: +1-503-264-3375  |
|PGP Key ID: 0xFE5AF240                                  |
|  1FDB 2770 08D7 8540 E157  AAB4 CC6A 0466 FE5A F240    |
+--------------------------------------------------------+

---

From: Benja Fallenstein <[email-masked]>
Date: Wed, 16 Jul 2003 17:35:50 +0200

Hi Carl,

> was completely free after the "urn:".  Is that not true?

No. After the "urn:" comes a "namespace identifier," a colon, and a 
"namespace-specific string," i.e.

     urn:<namespace id>:<namespace-specific string>

Assignment of namespace ids is a manged process, i.e., you cannot just 
create your own, you have to register it with the IETF. Normally this 
requires an RFC. The namespace registration explains how the 
namespace-specific string is interpreted.

For more info, see RFCs 2141 and 3406. The official registry of 
namespace ids is at:

     http://www.iana.org/assignments/urn-namespaces

> 	Is urn:sha1:dRDPBgZzTFq7Jl2Q2N/YNghcfj8= not now legal?

No, since there is no registered 'sha1' namespace.

>>    urn:sha1+sha256+tiger:...
[...]
> It's often more than that.  So, the concatenation function would have

Hm, can you explain what else would be needed? Do we really need other 
combinations than concatenation in URNs-- what would be the 
applications? (I'm not familiar with other ways in which you would want 
to combine hash functions.)

> encourage people to do this kind of concatenation.

Hm. Maybe you're right. My one point against this would be that if you use

     urn:sha1.tigertree:...

it's easier for a developer who supports only SHA-1 to realize that they 
can provide at least partial verification than it is if you use

     urn:bitprint:...

and define 'bitprint' as, 'SHA-1 concatenated with a Tiger tree-hash.'

But I think I'd be fine with the latter, if it is consensus.

- Benja

---

From: Justin Chapweske <[email-masked]>
Date: Wed, 16 Jul 2003 12:12:39 -0500

> 	Is urn:sha1:dRDPBgZzTFq7Jl2Q2N/YNghcfj8= not now legal?

The sha1 urn scheme is not yet registered, but its de facto usage 
utilizes a Base32 encoding, not Base64.

---

From: Benja Fallenstein <[email-masked]>
Date: Wed, 16 Jul 2003 19:32:35 +0200

Hi Zooko,

Zooko wrote:
> Coincidentally, there is an active (and contentious) discussion of 
> cryptography-based naming at the "cryptography" mailing list.
> 
> Three different concrete proposals, including one already deployed and one 
> newly announced, have been mentioned.

Is there an archive?

> [email-masked]

"subscribe cryptography" gives:
**** subscribe: unknown list 'cryptography'.

- Benja

---

From: "Zooko" <[email-masked]>
Date: 16 Jul 2003 13:25:48 -0400

---

From: Dirk-Willem van Gulik <[email-masked]>
Date: Sun, 20 Jul 2003 20:48:30 +0200 (CEST)

> 	Is urn:sha1:dRDPBgZzTFq7Jl2Q2N/YNghcfj8= not now legal?

Until there is a registered URN namespace/authority called 'sha1' - nope.

You could use x-sha1 - but that is kind of frowned upon.

> >     urn:sha1+sha256+tiger:...

Or regigster

	urn:assortedhashes:....
or
	urn:hash:....

and write an RFC which would document that it has to have the
shape:

	urn:hash:[a-z\+]+:<base32string>

And then in that RFC either define all of the above; or devise a scheme
by which additional A+B+C's can be added to that block.

Obviously in the above replace s/hash/by-whatever/ you want.

Dw.

---

From: Michael Mealling <[email-masked]>
Date: 20 Jul 2003 18:35:10 -0400

> was completely free after the "urn:".  Is that not true?

Essentially, yes. There are syntactic restrictions that exist for all
URIs but that's fairly generic. URNs still have to be persistent so you
can put things like domain-names in there unless you time/date stamp
them....

-Michael Mealling