Subject: [http-auth] I-D Action: draft-ietf-httpauth-mutual-algo-00.txt

From: [email-masked]
Date: Fri, 04 Jul 2014 15:02:17 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
 This draft is a work item of the Hypertext Transfer Protocol Authentication Working Group of the IETF.

        Title           : Mutual Authentication Protocol for HTTP: KAM3-based Cryptographic Algorithms
        Authors         : Yutaka Oiwa
                          Hajime Watanabe
                          Hiromitsu Takagi
                          Kaoru Maeda
                          Tatsuya Hayashi
                          Yuichi Ioku
	Filename        : draft-ietf-httpauth-mutual-algo-00.txt
	Pages           : 15
	Date            : 2014-07-04

Abstract:
   This document specifies some cryptographic algorithms which will be
   used for the Mutual user authentication method for the Hyper-text
   Transport Protocol (HTTP).

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-httpauth-mutual-algo/

There's also a htmlized version available at:
http://tools.ietf.org/html/draft-ietf-httpauth-mutual-algo-00

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 5 Jul 2014 15:44:00 +0300

Section 2.3:

>   where S_c1 is a random number within range [1, r-1].  The value of
>   K_c1 MUST represent a valid curve point, and K_c1' SHALL NOT be 0_E.
>   The server MUST check this condition upon reception.

How this generalizes to non-cofactor-1 curves (those can be quite a bit
faster than cofactor-1 ones)?

Looking at the discrete-group algorithm, it generalizes as "valid point
with large prime dividing order".

So would:

The value of K_c1 MUST represent a valid curve point, and [h]*K_c1'
SHALL NOT be 0_E. The server MUST check this condition upon reception.

Work?

(0_E is the identity point, h is the curve cofactor.)

>   where S_s1 is a random number within range [1, r-1].  The value of
>   K_s1 MUST represent a valid curve point and satisfy [4] * P'(K_s1) <>
>   0_E. If this condition is not satisfied, the server MUST retry using
>   another value for S_s1.  The client MUST check this condition upon
>   reception.

Same here. 

Also where does that multiplier 4 in check come from? Attempt at 
supporing h>1 curves (except that some stuff in use has h=8)?

Should it be [h]*P'(K_s1) <> 0_E?

Section 2.2&2.3:

2.2 has:
> The value of K_s1 MUST satisfy 1 < K_s1 < q-1.  If this condition
> is not held, the server MUST retry using another value for S_s1.

And 2.3:
> The value of K_s1 MUST represent a valid curve point and satisfy
> [4] * P'(K_s1) <> 0_E. If this condition is not satisfied, the
> server MUST retry using another value for S_s1.

If K_c1 has certain relationship (extremely unlikely) with
J(pi), that will fail over and over again (no S_s1 works).

Values of S_s1 that don't work are AFAICT very rare anyway (making
failures be dominated by all sorts of calculation errors in K_s1).

-Ilari

---

From: Yutaka OIWA <[email-masked]>
Date: Fri, 18 Jul 2014 17:09:34 +0900

Dear Ilari,

Thank you very much for valuable comments.
We'd asked our cryptographer colleagues' assistance
for answering, and please forgive us that we needed
some time to prepare these answers.

BTW,

>>   where S_s1 is a random number within range [1, r-1].  The value of

It seems to work.  We need to modify some other parts of
documents (e.g. introducing the parameter h).
Original ISO specification also has a consideration for
non-cofactor-1 curves in the exactly same way.
I'd like to incorporate it in the next revision.

> Should it be [h]*P'(K_s1) <> 0_E?

It is copied from the original ISO specification, and
it seems to be corresponding to the DL-case checking
"[t]he value of K_s1 MUST satisfy 1 < K_s1 < q-1",
that is to check K_s1 is not equivalent to either 1 or -1.
For this purpose, it should at least be [2] * P'(K_s1) <> 0_E.
I don't have a strict idea on why this is 4 instead of 2, though.
Does anyone have idea on this?
(Our colleague currently considers this 4 as not related to
 the cofactor setting).

> failures be dominated by all sorts of calculation errors in K_s1).

I'd like to answer this in a separate mail.

-- 
Yutaka OIWA, Ph.D.                 Leader, System Life-cycle Research Group
                               Research Institute for Secure Systems (RISEC)
     National Institute of Advanced Industrial Science and Technology (AIST)
                       Mail addresses: <[email-masked]>, <[email-masked]>
OpenPGP: id[440546B5] fp[7C9F 723A 7559 3246 229D  3139 8677 9BD2 4405 46B5]

---

From: Yutaka OIWA <[email-masked]>
Date: Fri, 18 Jul 2014 17:31:09 +0900

Dear Ilari,

> failures be dominated by all sorts of calculation errors in K_s1).

I've checked and analyzed our current draft and original ISO specification.
Current our specification is exactly corresponding to the
original spec in this aspect.

However, as you have mentioned,

If (J(pi) + [t_1] * K_c1') = 0_E or similar, the K_s1 will always be 0_E,
regardless of the choice of S_s1.
The value t_1 is also derived from K_c1 using a hash function.
If this happens, it causes a denial-of-service condition on server-side.
It depends on how J(pi) is stored in the server-side.

If J(pi) is computed on server-side from the plain-text password pi,
finding S_c1 which causes this problem is pretty hard.
It can be done off-line by clients, but it requires brute-force search on
the whole candidates of S_c1.

However, if J(pi) is provided from client-side, it is easy to cause
the problematic condition, by
 * choose an arbitrary S_c1 randomly,
 * compute J as -([t_1] * K_c1'), and send it to server as J(pi),
 * talk to server with per-determined S_c1.
The similar problem also exists in DL setting.
Verifying whether J is valid (correctly derived from some
plain-text password pi) is impossible.

Could someone double-check my observations above?

The fix is quite easy in one of two ways:
 * check that [4] * (J(pi) + [t_1] * K_c1') <> 0_E upon
    reception of K_c1, or
 * limit number of retries of S_s1 selection (to some small numbers).
In either ways, if the client is not malicious, possibility of
invoking this condition accidentally is cryptographically negligible.
I'll incorporate one of these additional checks into the next revision.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 18 Jul 2014 14:20:27 +0300

On Fri, Jul 18, 2014 at 05:09:34PM +0900, Yutaka OIWA wrote:

Looks like there are unstated assumptions:
- q for discrete groups has to be safe prime.
- r for elliptic curve has to be prime (hr = #E).

All the groups defined in -00 do satisfy these conditions.

> (Our colleague currently considers this 4 as not related to

It seems to me that if h=1, then [4] * X = 0_E iff X = 0_E.

And if h=2, then [4] * X = 0_E iff [2] * X = 0_E.

Regarding the 4, maybe its origin can be traced to some standards
specifying h to be 1, 2 or 4.

> The similar problem also exists in DL setting.

Yeah, forgot about that.

> plain-text password pi) is impossible.

Doing ZKP for discrete logarithm is presumably not practical, due
to extra values incurred.

> I'll incorporate one of these additional checks into the next revision.

Actually, given that r is prime, it seems to me that:

[h] * (J(pi) + [t_1] * K_c1') <> 0_E
<=>
[h] * [S_s1] * (J(pi) + [t_1] * K_c1') <> 0_E

(scalar multiplication commutes and Z_r is a field).

So one would never need to retry.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Fri, 18 Jul 2014 12:43:50 -0400

Dear authors:

The algorithms in the draft seem to be based on the Augmented PAKE 
protocol, but differ in various aspects (e.g., hash function definition, 
details of cryptographic operation). Thus, it is not a priori clear 
whether the results in the AugPAKE paper apply here. If there is a 
technical write-up that analyzes the cryptographic properties of this 
(specific) protocol in detail that would be great.

Best regards, Rene

On 7/4/2014 6:02 PM, [email-masked] wrote:
> _______________________________________________
> http-auth mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/http-auth

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 20 Jul 2014 04:29:38 +0300

> (scalar multiplication commutes and Z_r is a field).

Seems like following assumptions are sufficient for proving
this:

A) Base field of E is finite, and
B) r=|<G>| is prime, and
C) #E <> 0 (mod r^2)

In practice, these are always true in ECC.

-Ilari

---

From: Yutaka OIWA <[email-masked]>
Date: Sun, 20 Jul 2014 10:42:45 +0900

Hello from Narita,

Thank you.  I don't know why the original ISO spec says about retry only
for this point,
and it seems to be good to revise the clause by our own investigation, also
considering the possible DoS.
Please wait a while for new draft.

-- 
Yutaka OIWA <[email-masked]> on mobile

---

From: Yutaka OIWA <[email-masked]>
Date: Tue, 22 Jul 2014 05:40:15 +0900

Dear Ilari and all httpauth WG people,

I've prepared a candidate for next revision of the draft available at
the following location:
https://www.rcis.aist.go.jp/special/MutualAuth/files/spec/draft-ietf-httpauth-mutual-algo-00.1.txt

This incorporates updates from the discussions and suggestions in this thread.
I'm currently self-reviewing again about the changes.
(Final question in my mind: is is safe to reject "seems to be invalid"
K_c1 immediately? Isn't it leaking some information to the client?
If you have any idea, I appreciate it.)
I will soon submit it as revision -01.

Thank you really for valuable suggestions and discussions.

---

From: Yutaka OIWA <[email-masked]>
Date: Wed, 23 Jul 2014 22:18:23 +0900

Dear Rene,

this protocol is based on KAM3 of ISO/IEC 11770-4:2006.
ISO-spec says it is also called {DL, EC}APKAS-AMP in
IEEE P1363.2, proposed by T. Kwon.

There seems to be several literature written by the original
author.
http://www.isoc.org/isoc/conferences/ndss/01/papers/kwon.pdf
seems to be the most "academic" paper with analysis
to (some older revision of) this primitive, and there are also
several revisions submitted to P1363.
http://grouper.ieee.org/groups/1363/passwdPK/contributions/ampsummary.pdf
http://grouper.ieee.org/groups/1363/passwdPK/contributions/amp_final_revision.pdf
http://dasan.sejong.ac.kr/~tkwon/research/ampsummary2.pdf

I hope these will be helpful for reviewing and analyzing the proposal.

Using some other Augmented PAKE primitives with
my Mutual base proposal (draft-ietf-httpauth-mutual)
is easy in general.

2014-07-19 1:43 GMT+09:00 Rene Struik <[email-masked]>:
> Dear authors:
>
> The algorithms in the draft seem to be based on the Augmented PAKE protocol,
> but differ in various aspects (e.g., hash function definition, details of
> cryptographic operation). Thus, it is not a priori clear whether the results
> in the AugPAKE paper apply here. If there is a technical write-up that
> analyzes the cryptographic properties of this (specific) protocol in detail
> that would be great.
>
> Best regards, Rene
>
>
>>   This draft is a work item of the Hypertext Transfer Protocol
>> Authentication Working Group of the IETF.
>>

---

From: Rene Struik <[email-masked]>
Date: Wed, 23 Jul 2014 22:47:37 -0400

Hi Oiwa:

Thanks for the references. I gave this a brief look (sorry - no time yet 
to study this in full detail). Wouldn't the security rely on the strong 
Diffie-Hellman assumption, similar to the AugPAKE scheme? It may help to 
briefly explain differences between this protocol and the AugPAKE 
protocol, both from protocol and security perspective. If you could 
indicate why the scalar factor (S_{c1}+t2) is included in the formula at 
the end of Section 2 of draft-ietf-httpauth-mutual-algo-00 that would be 
great. This factor seems to increase the online computational cost on 
the server's side by one full fixed point scalar multiplication and it 
would be good to appreciate the rationale for this.

I have an agenda conflict tomorrow am, but will try and be at part of 
the httpauth session, so as to appreciate your draft better.

Best regards, Rene