Subject: [http-auth] Concatenation is not injective

From: Watson Ladd <[email-masked]>
Date: Sun, 7 Dec 2014 17:26:56 -0800

Dear all,

HOBA computes a string which is signed by concatenating
nonce+origin+alg+kid+challenge, where nonce is picked by the UA, and
challenge by the server. Suppose we were to change this slightly by
reversing the challenge and the nonce. The resulting protocol would be
entirely insecure, as shown by the following, with S the server, M the
attacker, and B the client.

S->M sign "dog"+S
M->B sign "dogS"+M
B->M I signed "dogS"+M+"once"
M->B I signed "dog"+S+"Monce"

Is an attack like this possible on the current version? It depends on
the details of the encoding, but I think so: the intermediary makes
the challenge contain the entire origin+alg+kid+challenge received
from the server, and uses it as a nonce. Encoding may make this
impossible, but it's much easier to use an injective map from a
sequence of strings to a single string to eliminate this problem
entirely.

Sincerely,
Watson Ladd

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 08 Dec 2014 02:32:26 +0000

Hi Watson,

First, thanks. I'm very glad we're getting more scrutiny.
Esp when its comes with more crypto clue than I have.

On 08/12/14 01:26, Watson Ladd wrote:
> nonce+origin+alg+kid+challenge, 

Terminology-wise the above catenation is called HOBA-TBS in
the spec. (that's mentioned below). And we're ignoring the
optional realm input which is ok for this discussion I think.

> where nonce is picked by the UA, and

Let me first check if I'm getting the vulnerability and then
check if I'm understanding the suggested solution. Then I'll
say what I think is a plan.

So the vulnerability doesn't apply to HOBA as specified but
rather to another protocol (call it "not-quite-HOBA") that
is almost like HOBA but where the nonce and challenge inputs
to signing are swapped in the encoding. Is that what you mean?

The concern is that given such a vulnerability exists in
not-quite-HOBA, there could be some as-yet-unknown vulnerability
in HOBA as-specified that we might eliminate if we also eliminate
the vulnerability in not-quite-HOBA. Is that also right?

And your solution is to use f(HOBA-TBS) as input to signing
instead of HOBA-TBS, where f is some injective map. And
maybe where the inputs to f() aren't just the catenated
values, but each value as a separate input, so more like
f(nonce,origin,alg,kid,challenge) and not simply this:
f(nonce+origin+alg+kid+challenge).

Well, first, isn't f() = identity injective too? If so, then
I'm not sure what we're gaining really. And f() = sha256 or
any other well known cryptographic hash is not injective
I think, so I'm not sure what f() you'd suggest that's
different from the current encoding/ordering. (And where
that f() has been used in some standard somewhere and is
not such a novelty - I far prefer lack of novelty in stuff
like HOBA to be honest:-)

I guess we could have f() as "prepend length of the
overall, then hash" but I'm not sure even that would be
injective, nor am I sure it'd offer any benefit compared
to the current protocol that also doesn't suffer the same
problem posited for not-quite-HOBA. That is, such an f()
wouldn't help at all I think.

But maybe there is an f() that would be an improvement.

Absent a really better f(), I think noting the vulnerability
in  not-quite-HOBA is worthwhile and can do that - I recall
thinking about this some time ago, (*) and given that HOBA is
aiming for experimental status it's possible that it might
be revised in future so it'd be good to note this potential
(but not actual) vulnerability in that not-quite-HOBA
protocol.

Or, maybe you can suggest an f() that'd be a real improvement
on the current protocol? Or can we agree that just noting the
vulnerability in not-quite-HOBA is sufficient in this case?

Cheers,
S.

(*) I guess it's a good rule-of-thumb in protocol design to
provide the more local/trustworthy/more-quickly-changing
stuff first as input to any hashing. And in saying that I
do get that you don't like such rules of thumb and you're
probably correct in general:-)

> 
> Sincerely,
> Watson Ladd
> 
> _______________________________________________
> http-auth mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/http-auth
> 
>

---

From: Watson Ladd <[email-masked]>
Date: Sun, 7 Dec 2014 20:28:40 -0800

> to signing are swapped in the encoding. Is that what you mean?

So when I first wrote the email and the example, I thought HOBA would
be safe because of the order. Then I realized that doesn't matter,
midway through. If HOBA is not vulnerable, it's because of a detail in
the possible types of arguments, and not because it's a generically
secure mechanism that doesn't care about the format of the strings
used.

It's possible that implementations will be vulnerable because they
concatenate the nonce without checking its format for instance, even
if the protocol might be implementable securely.

> like HOBA to be honest:-)

Signature algorithms take strings, not tuples of strings. f is not,
and cannot, be the identity, but concatenation, which is not
injective: "CA"+"TMAN"="CAT"+"MAN". That's what it is in the current
draft, and the result is most likely a vulnerability. Almost certainly
someone will implement this draft without checking the nonce for
well-formedness, in which case there is *definitely* going to be a
problem.

> But maybe there is an f() that would be an improvement.

There is: Pick an injective function from sequences of strings to
strings. For instance one can take
f([]) = ""
| f([x:xs])=len(x)+":"+x+f(xs)

where len(x) is the base-10, ASCII representation of the length of x.
This is an injective function from sequences of strings to strings.

With this, in the analysis you don't need to worry about what the
tuple being input looks like, as you will never have a collision. This
is similar to the use of lengths of the message and associated data in
AEAD modes.

> probably correct in general:-)

You can do that, and make sure the encoding is injective at the same time.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 08 Dec 2014 09:53:49 +0000

Hiya,

> is similar to the use of lengths of the message and associated data in

Yeah, I kinda like that I have to say. Even if there's no real
attack against HOBA as-is, doing that seems like a good plan in
case the HOBA signature scheme/code ever gets re-used elsewhere,
and to make the analysis easier.

Let me go check stuff and get back but I'm warming to this idea.

S.

---

From: Derek Atkins <[email-masked]>
Date: Mon, 08 Dec 2014 09:07:38 -0500

> Let me go check stuff and get back but I'm warming to this idea.

I'll note that there are often attacks possible when you do pure
concatination of strings into a hash.  PGP had this problem, too, a long
long time ago because an attacker could choose where to split the hashed
values.

The fix is to include lengths in the concatination, or have explicit
field separators.

> S.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant