Subject: Re: [apps-discuss] CRC vs check digit in draft-farrell-decade-ni

From: Stephen Farrell <[email-masked]>
Date: Tue, 1 May 2012 08:47:33 +0100

On 1 May 2012, at 03:17, "Manger, James H" <[email-masked]> wrote:

> A check digit would be more appropriate than an CRC for the human-readable format in "Naming Things with Hashes" <draft-farrell-decade-ni>. The draft currently has an optional 16-bit CRC, represented with 4 hex digits. CRCs are really designed for detecting bit errors (or bursts of bit errors). Check digits, on the other hand, are designed to detect human errors (changing digits, transposing digits etc). 1 or 2 check digits are sufficient, instead of 4 chars for a 16-bit CRC.
> 
> Most check digit algorithms work on decimal digits. This draft needs one for a string or at least for hex digits. Perhaps the Luhn mod N algorithm would be suitable <http://en.wikipedia.org/wiki/Luhn_mod_N_algorithm>? Using N=16 and calculating the checksum over just the hex digits of the hash should work well. Such a checksum doesn't "protect" the algorithm name, but it doesn't need to as there are only a handful of valid values anyway. Such a checksum would also ignore the case of hex digits. It doesn't change if you switch from an alg name to id (eg "sha-256-120" to "3").

Yeah that sounds good, I'll write up some text for it. Ari's the one who liked the crc but he's on vacation, so might take a few days to resolve.

> 
> P.S. The examples in draft 05 all look correct now.

Phew. I ended up adding a target to the Makefile to auto generate em since I'd mucked up so much:-)

Ta
S

> --
> James Manger

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 05 May 2012 18:16:28 +0100

Hi James,

> P.S. The examples in draft 05 all look correct now.

Well, let's see if I break 'em again:-)

People liked your idea of the Luhn checkdigit so if you're in the
mood to check if I've gone wrong again I'd really appreciate that.

I've added this text for the nih bit:

   The hash value is OPTIONALLY followed by a checkdigit.  The
   checkdigit MUST be calculated using Luhn's mod N algorithm (with
   N=16) as defined in [ISOIEC7812], (see also
   http://en.wikipedia.org/wiki/Luhn_mod_N_algorithm).  The input to the
   calculation is the ASCII-HEX encoded hash value (i.e. "val" in the
   ABNF production below).  This maps the ASCII-HEX so that
   '0'=0,...'9'=9,'a'=10,...'f'=15. None of the other fields are input
   when calculating the checkdigit.

And then using the python-stdnum package I get the following examples:

   +-------------------------------------------------------------------+
   | Human-readable form of a name for this key (truncated to 120 bits |
   | in length) with checksum:                                         |
   | nih:sha-256-120;53269057e12fe2b74ba07c892560a2;f                  |
   +-------------------------------------------------------------------+
   | Human-readable form of a name for this key (truncated to 32 bits  |
   | in length) with checksum:                                         |
   | nih:sha-256-32;53269057;b                                         |
   +-------------------------------------------------------------------+
   | Human-readable form using decimal presentation of the             |
   | algorithm ID (sha-256-120) with checksum:                         |
   | nih:3;53269057e12fe2b74ba07c892560a2;f                            |
   +-------------------------------------------------------------------+

Thanks in advance, if you've time,
Stephen.

---

From: "Manger, James H" <[email-masked]>
Date: Sun, 6 May 2012 21:40:55 +1000

>   when calculating the checkdigit.

This text look good, though it doesn't seem to mention the ";" between the hash value and the checksum. Perhaps it should start:
  "The hash value is OPTIONALLY followed by a semicolon then a checkdigit."

>   | nih:3;53269057e12fe2b74ba07c892560a2;f                            |

I concur with these checkdigit calculations.
(Curiously the 8 digits in the 32-bit example are all decimal digits (no a-f) - but I doubt that will confuse anyone)

--
James Manger

---

From: "Manger, James H" <[email-masked]>
Date: Sun, 6 May 2012 21:45:06 +1000

Section 2 "Basics" of draft-farrell-decade-ni-05 says "when a hash value is truncated the name MUST indicate this". But why?

It is easy to determine the amount of truncation (if any) from the length of the hash value in the 'ni' URI (or 'nih' URI or binary form). Instead of:

  nih:sha-256-32;53269057

why not use:

  nih:sha-256;53269057

The second form saves a few bytes, but more importantly it avoids the need to register a new algorithm name for every truncation length that could have any use. This is particularly important for the binary format that only has a 6-bit field (64 possibilities) to indicate the algorithm. 64 hash algs sounds ok; 64 hash/length pairs sounds quite limiting.

The truncation length in the alg name is not used to parse the URI (even in the binary format).

The one constraint the spec would need to state is that any truncation MUST be on a byte (8-bit) boundary (so you can calculate the truncation length from the number of base64url-chars in a 'ni' URI).

--
James Manger

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 06 May 2012 15:09:38 +0100

>   "The hash value is OPTIONALLY followed by a semicolon then a checkdigit."

Sure.

> (Curiously the 8 digits in the 32-bit example are all decimal digits (no a-f) - but I doubt that will confuse anyone)

Great,
S

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 06 May 2012 15:27:44 +0100

Hi James,

> The one constraint the spec would need to state is that any truncation MUST be on a byte (8-bit) boundary (so you can calculate the truncation length from the number of base64url-chars in a 'ni' UR…

I'm going to argue against that change for two
reasons.

First, if the name is received via a stream-cipher
protected channel then not having the length in the
alg might enable some truncation attacks. That's a
bit of a corner-case, but a real issue nonetheless.

Second, I prefer that there be fewer options overall,
compared to having more options, to encourage interop.
(Interop for these isn't hard though, which makes
this a less convincing argument for me.) IMO the
restricted space for binary format algs is therefore
a good thing.

So, I'd rather keep as-is in this respect.

Cheers,
S.

---

From: Anthony Bryan <[email-masked]>
Date: Sun, 6 May 2012 17:18:14 -0400

On Sun, May 6, 2012 at 7:45 AM, Manger, James H
<[email-masked]> wrote:
> The second form saves a few bytes, but more importantly it avoids the need to register a new algorithm name for every truncation length that could have any use.

that would mean you could also make use of the existing "Hash Function
Textual Names" registry

http://www.iana.org/assignments/hash-function-text-names/hash-function-text-names.xml

-- 
(( Anthony Bryan ... Metalink [ http://www.metalinker.org ]
  )) Easier, More Reliable, Self Healing Downloads

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 07 May 2012 01:16:28 +0100

Hi,

> http://www.iana.org/assignments/hash-function-text-names/hash-function-text-names.xml

That's true and would be an advantage. But IMO outweighed by
the security and interop downsides I mentioned before.

S

---

From: "Manger, James H" <[email-masked]>
Date: Mon, 7 May 2012 10:27:12 +1000

>> ...
>> Instead of:
>> ...

> bit of a corner-case, but a real issue nonetheless.

Yikes! Fix the "protected channel" so it actually gives you integrity, or don't rely on it for integrity.
Such an attack would also only work if the receiver accepted a short hash (that the attacker found a collision for) when the receiver should have confirmed the hash was crypto-strength. The receiver needs to be fixed (eg to require lengths over 120-bits). Putting lengths in alg names seems to be papering over much bigger underlying problems in this corner-case.

> restricted space for binary format algs is therefore

I have no problem with the draft recommending a few specific lengths (eg 32, 64, 96, 120, 128, 256 bits) if that encourages interop. My guess is you will get better interop without truncation lengths in names. It would encourage systems to be configured with min and/or max truncation lengths and interoperate with any length in that range (eg a SHA-256 has truncated to 160 bits). The current text means a SHA-256 hash truncated to 160 bits would be rejected simply because "SHA-256-160" is not explicitly listed.

> So, I'd rather keep as-is in this respect.

I would still rather ditch the truncation length from the alg names.

--
James Manger

---

From: Martin Thomson <[email-masked]>
Date: Mon, 7 May 2012 08:56:02 -0700

> I would still rather ditch the truncation length from the alg names.

I'm with James on this one.  Concerns about checking too-short hashes
don't seem so serious.  After all, the incentive is with the client to
check as much of the hash as they can.  Thus, the only concern is if
an attacker can force a shorter hash somehow.  The example of a
truncated stream cipher seems contrived to me.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 08 May 2012 10:44:38 +0100

> truncated stream cipher seems contrived to me.

Not to me.

I think that omitting the size would mean that anyone using
these would need to go think about potential truncation attacks,
and having to do that is bad, since most times they won't do
it at all and even if they do, those attacks, if they apply,
will be likely be very subtle. So even if you try figure it
out, you may not get the analysis right. Avoiding all that
is just better IMO.

I also think that limiting the available truncation options
will make it (a bit) more likely that people won't truncate
when they don't need to. Maybe the text on that ought be
tightened up though, e.g. to say that you SHOULD use full
length hashes unless you have a real reason why you need to
truncate. Happy to take suggestions there.

Additionally, if we took out the length then we'd have to
figure whether or not (or when, yuk) ni:///sha-256;abc is the
"same" as ni:///sha-256;abcdef and even if we declare that its
never the same, that's something people are liable to get
wrong, since sometimes both would actually refer to the same
thing. Yuk yuk yuk;-)

S.

---

From: "Manger, James H" <[email-masked]>
Date: Wed, 9 May 2012 11:02:14 +1000

>> I'm with James on this one.
>> ... The example of a truncated stream cipher seems contrived to me.

> out, you may not get the analysis right. Avoiding all that

I am trying to understand the truncation attacks you are concerned about. Would an example be an HTTPS web connection that abruptly stops mid stream? All the received TLS records are properly encrypted and have valid MACs. However, only half of the HTML page has been delivered: it might end "<script src='ni://example.com/sha-256;f4OxZX". Somewhere in the receiver's stack it knows truncation has occurred (the TLS and HTTP and layers didn't close properly), but the higher layer ignores that and interprets the content anyway. In this example, a browser (which is very lenient) accepts the incomplete <script> tag and acts on the wrong (truncated) URI.

The fault is not with the 'ni' URI. Solving this situation would require all protocols (not just 'ni' identifiers) to be "prefix-free" (eg no prefix of a protocol can be meaningful). That is not realistic.

An 'ni' URI can have query parameters. Couldn't a truncation attack strip those regardless of whether the hash length is in the alg name? Why isn't that a problem?

> wrong, since sometimes both would actually refer to the same

Implementations are just as likely to consider that the following are the "same":
  ni:///sha-256-32;abcdef
  ni:///sha-256-64;abcdefghijk

If a truncation attack really needs to be defended against, we should specify that the output length (and algorithm) are inputs to the hash. For example, Truncate_to_n(Hash(alg || n || content)).

--
James Manger

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 09 May 2012 12:56:29 +0100

Hiya,

I think the main thing to keep in mind is that we don't
want people to make the mistake of thinking two names are
the same when they aren't. In other words a name with a
32 bit truncated sha-256 hash is not the same as a name
with the full 256 bits of hash output, even if the hash
value for one is a prefix of that for the other.

The reason being that if an application treats those the
same then that'd open up a bunch of attacks. For example,
if I publish an object with the full hash, then I probably
(in general) don't want some other application to treat a
name with just the first 32 bits of that as referring to
the same thing, since the 32 bit name will have lots of
colliding objects. If this stuff gets used, there will
be many cases where names will occur more than once in
application protocols, and it'll be unpredictable which
instance of the name will be used for name-data integrity
checking. (Maybe we ought add a bit more security
considerations text to explain that better, suggestions
welcome.)

Now, IMO, the syntax we have makes that mistake less likely,
whereas your proposal makes it more likely to happen, due
to developer carelessness or misunderstanding.

We also have code [1] that implements the current syntax,
so for us at least, we'd want to see a benefit to switching,
and I only see a downside right now. That code is very
early, so it's not a major major deal, but I'd not want
to break stuff for fun, and given that we've implemented
this in a bunch of languages, it'd be a chunk of work.
(Developer enthusiasm, after many months of discussion
and ppt engineering lead to a burst of coding activity
resulting in c, ruby, java, php, python, clojure and a
few application examples, including wget and curl all
of which do the ni URI as per the current draft:-)

> The fault is not with the 'ni' URI. Solving this situation would require all protocols (not just 'ni' identifiers) to be "prefix-free" (eg no prefix of a protocol can be meaningful). That is not re…

Right. I did say its a corner case at best, but we don't know
what protocols will use these names. And maybe one of those will
allow truncation attacks. I'd really rather not have to think
about it. (Mind you, if the name is just sent encrypted in a
stream cipher without integrity, then swapping bits can also
switch sha-256-96 to sha-256-32 easily enough;-)

> An 'ni' URI can have query parameters. Couldn't a truncation attack strip those regardless of whether the hash length is in the alg name? Why isn't that a problem?

Whether that matters is down to the application protocol I
think. For the base spec, we just say that the names are
the same, iff the hash alg, length and value are the same.

>   ni:///sha-256-64;abcdefghijk

I guess I just disagree about that.

strncmp(a,b,min(len_a,len_b)) would not treat them as equal
with the current syntax but would with your suggestion.

> If a truncation attack really needs to be defended against, we should specify that the output length (and algorithm) are inputs to the hash. For example, Truncate_to_n(Hash(alg || n || content)).

We thought about that but didn't go for it, because it'd
easily get over complicated, e.g. you'd maybe want to also
include the query string, authority etc. and there didn't
seem to be much benefit from that level of complexity.
It'd also mean that you couldn't just create these
names for (large sets of) things for which you've already
calculated the hashes e.g. if you had a large image library
already using sha-256 hashes in their URLs then with
the above it'd not be possible to use the .well-known/ni
URL (and presumably an HTTP 30x re-direct) to de-reference
the name. Allowing that seems like a good thing.

Having said all that, if it turns out that you're right
and we're wrong, then it'd not be too hard to define and
register a new hash function that'd work as you suggest,
but I just don't see it being more useful right now and
do worry about it being less safe.

Cheers,
S.

[1] http://sourceforge.net/projects/netinf/