Subject: [OAUTH-WG] draft-ietf-oauth-spop-04: a way of making code_challenge

From: takamichi saito <[email-masked]>
Date: Fri, 14 Nov 2014 10:28:23 +0900

Hi all,

I appreciate this idea, simple and powerful to achieve proof of possession.
But, I have some questions against the scheme.
Sorry if these ware already discussed.

I worry about using a hash function in simple way.
I mean, a simple use of random as code_verifier may cause that malicious client can have any code_verifier and code_challenge.
All combinations of random and its hash can be obtained, it may not be risk?

So, we should use:
S256 "code_challenge" = BASE64URL(SHA256("code_verifier" + “client ID”))
or
S256 "code_challenge" = BASE64URL(SHA256("code_verifier" + “client ID” + “server ID”))
Where, you know that client ID is client’s unique name.

Other problem is the following, using Nat’s slide:
http://www.slideshare.net/nat_sakimura/1112-spoppresso .

0.    Attacker prepares own code_verifier and code_challenge.
1.    replage legitimate challenge with malicious code_challenge.
5. Attacker can submits own code_verifier.

It may be out of the draft, I think.

Best regards,

;; takamixhi saito

---

From: John Bradley <[email-masked]>
Date: Thu, 13 Nov 2014 15:45:50 -1000

We have discussed it and that was in fact my original recommendation.   However I have been convinced that it adds complexity without any real improvement in security. 

The reality is that people don't bother with rainbow tables these days.  They calculate hashes on the fly faster than they can look them up.   If you are generating the hashes to find a collision then having fixed text that is known to the attacker won't help. 

It is better for people to have more entropy in the code verifier than to have a fixed block of text.   I want to avoid people using less bits of entropy because they think the hmac is adding something. 

I will come up with some text for the spec, as you are not the only person asking that question. 

The other issue is that the term HMAC is scary to developers and we want maximum adoption. 

John B. 

Sent from my iPhone

> On Nov 13, 2014, at 3:28 PM, takamichi saito <[email-masked]> wrote:
> 
> 
> Hi all,
> 
> _______________________________________________
> OAuth mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/oauth

---

From: Bill Mills <[email-masked]>
Date: Fri, 14 Nov 2014 01:55:53 +0000 (UTC)

The whole mechanism relies on the attacker not having access to the code_verifier or hash.  It's defending against the attacker getting the code via weakness in IPC or other such mechanism like URI handlers.  How many more bits is secure beyond 256 bits of entropy recommended?  If you want to make it longer then just make it longer, salting doesn't really help that much.
The original value or the hashed value *should* be protected by the transport security, and if it isn't then the attacker could be stealing the original credential used to authenticate anyway.

     On Thursday, November 13, 2014 5:40 PM, takamichi saito <[email-masked]> wrote:

Hi all,

So, we should use:

Best regards,

;; takamixhi saito

---

From: Nat Sakimura <[email-masked]>
Date: Fri, 14 Nov 2014 02:00:25 +0000

Regarding

> It may be out of the draft, I think.

I think this is out of scope.

On Fri Nov 14 2014 at 10:46:07 John Bradley <[email-masked]> wrote:

> We have discussed it and that was in fact my original recommendation.
>  However I have been convinced that it adds complexity without any real
> improvement in security.
>
> The reality is that people don't bother with rainbow tables these days.
> They calculate hashes on the fly faster than they can look them up.   If
> you are generating the hashes to find a collision then having fixed text
> that is known to the attacker won't help.
>
> It is better for people to have more entropy in the code verifier than to
> have a fixed block of text.   I want to avoid people using less bits of
> entropy because they think the hmac is adding something.
>
> > I mean, a simple use of random as code_verifier may cause that malicious
> client can have any code_verifier and code_challenge.

---

From: William Denniss <[email-masked]>
Date: Thu, 13 Nov 2014 18:09:58 -0800

> I think this is out of scope.

I agree that this is out of scope.

SPOP is designed to protect an interception of the OAuth code grant which
is a known risk on some mobile platforms. With the S256 transformation it
also protects against eavesdropping of the app-to-app communication channel.

>> > I mean, a simple use of random as code_verifier may cause that
>> malicious client can have any code_verifier and code_challenge.

---

From: takamichi saito <[email-masked]>
Date: Fri, 14 Nov 2014 12:03:19 +0900

Sorry for my poor english.

> We have discussed it and that was in fact my original recommendation.   However I have been convinced that it adds complexity without any real improvement in security. 

Really?
I think that there is same discussion in storing passwords with salt.
It seems to be dangerous to use hashes of fixed-range values.

> The reality is that people don't bother with rainbow tables these days.  They calculate hashes on the fly faster than they can look them up.   If you are generating the hashes to find a collision t…

How quick?
Since lifetime of the code_challenge is short, it can works effectively.

> It is better for people to have more entropy in the code verifier than to have a fixed block of text.   I want to avoid people using less bits of entropy because they think the hmac is adding somet…

I agree.
Then, we should add “client ID” in code_challenge.
We can get a few more entropy, since client ID is not fixed value.

> I will come up with some text for the spec, as you are not the only person asking that question. 

Thank you.

;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Fri, 14 Nov 2014 12:07:11 +0900

> The original value or the hashed value *should* be protected by the transport security, and if it isn't then the attacker could be stealing the original credential used to authenticate anyway.

Is it correct?
You mean that we don’t need to use hash itself? Only to use plain is enough?

;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Fri, 14 Nov 2014 12:13:26 +0900

> I think this is out of scope. 

I agree.
But we may need to add the scope or out of the scope.
There is no definition of "A malicious client” in Section 1 of the draft, isn’t it?
Many people can be led to misunderstand the scheme.

;; takamixhi saito

---

From: John Bradley <[email-masked]>
Date: Thu, 13 Nov 2014 17:37:04 -1000

If an attacker can intercept and modify requests, they have complete control.  Trying to protect OAuth at that point is probably not practical.   If you want that then we need a confidential client with tpm storage of key material and move to signed requests and responses.

That is possible but is out of scope for this spec.

The none transform protects against an attacker who can only intercept the response. 
The S256 transform protects against an attacker that can observe the request perhaps via a log on the device (this has happened)  and intercept the response.

The code verifier is short lived as is the code so an attacker would have a short time to find a collision for the S256 hash.

There is no easy protection for an attacker who can modify requests.

The none transform protects against a common attack that is easy to perform on iOS and more difficult but possible on other platforms.  
The S256 transform provides additional protection for something going wrong in the OS and leaking the code_challange.
It may not be required in most cases, but in cases where it is you probably won't find out untill after the bad guys, so it is better to be safe than sorry for the overhead of a hash operation.

John B.

---

From: Bill Mills <[email-masked]>
Date: Fri, 14 Nov 2014 04:02:53 +0000 (UTC)

Yes, "plain" is actually sufficient.  The hashed value protects against disclosure/logging threats on the server auth server and proxies perhaps where the HTTPS is terminated somewhere other than the auth server itself, it's not actually required for the basic functionality/security of the mechanism. 

     On Thursday, November 13, 2014 7:07 PM, takamichi saito <[email-masked]> wrote:

Is it correct?

;; takamixhi saito

---

From: Bill Mills <[email-masked]>
Date: Fri, 14 Nov 2014 04:11:34 +0000 (UTC)

Adding client ID is no better than simply adding extra random bits, but 256 is a LOT.
Also remember that the server SHOULD:
-    only allowing a code to be tried once-    at a very minimum should have a severely limited number of tries for a code-    a short time window to use a code
Unless you can brute force 256 bits of (pseudo)random in under a minute or two the code is dead.  Guess wrong, the code should be dead/trash.

     On Thursday, November 13, 2014 7:03 PM, takamichi saito <[email-masked]> wrote:

Really?

How quick?

I agree.

Thank you.

;; takamixhi saito

---

From: John Bradley <[email-masked]>
Date: Thu, 13 Nov 2014 19:13:09 -1000

This blog post has some good background on why salting is no longer effective against brute force attacks.  
http://blog.ircmaxell.com/2011/08/rainbow-table-is-dead.html?m=1

More entropy in the secret is much more important.  

The code verifier should not be thought of as a password.  It needs to be a high entropy key. 

John B. 

Sent from my iPhone

> On Nov 13, 2014, at 6:11 PM, Bill Mills <[email-masked]> wrote:
> 
> -    only allowing a code to be tried once
> -    at a very minimum should have a severely limited number of tries for a code
> -    a short time window to use a code
>

---

From: takamichi saito <[email-masked]>
Date: Fri, 14 Nov 2014 18:39:43 +0900

> http://blog.ircmaxell.com/2011/08/rainbow-table-is-dead.html?m=1

It is basic knowledge as you know.
If I don’t misunderstand the article, the article doesn’t say so.

"That's why it's so important to use a unique salt for each stored password (it reduces the return on investment that the new rainbow table will provide)."

> The code verifier should not be thought of as a password.  It needs to be a high entropy key. 

I can’t understand your point, sorry.
Probably, you may mix some points.
I separate points:

1) against brute-force 
-> it should use iterations.

2) high entropy for the code verifier
-> it should use random generator such like Sandy Bridge's DRNG.
-> or using a longer code_verifier with more uniqueness.

3) against table, including rainbow
-> it should use salt-like string, i.e. adding client_ID 

for example of simple use of hashing:
 hash(1) = sip
 hash(2) = asi
 hash(3) = isd
 hash(4) = tt!
 hash(5) = ou?
  :
  :

 if we apply 1 to hash, we can get “sip" every time.
 Therefore, 
 if someone makes the table for the scheme, we can call SPOP table,
 every person can obtain legitimate code_verifier from any code_challenge.
 That’s my concern.

;; takamixhi saito

---

From: Nat Sakimura <[email-masked]>
Date: Fri, 14 Nov 2014 16:03:54 +0000

The code challenge is only one time use and has a short validity period. It
is not something that is going to be stored.

For (1), we could define such transformation, but at a later time, IMHO. We
are getting push back even for sha256 from developers. We need to balance
the benefit and adoption. BTW, what John mentioned as Brute Force attack is
not talking about this. See (3).

For (2), we plan to provide some guidance in the security consideration
section. We know too many developers use a bad source of random.

For (3), as I understand, the salting is to stretch the search space. In
your example, the original search space is very small. In such cases, I
understand the value of stretching. In SPOP's case, we are requiring the
original search space to be rather big. The incremental value from
stretching the space using a known value seems to be minimal, if at all. We
are recommending to use 256bit random. (Since we are SHA256ing, more bits
does not buy us much.) If we stretch the 256 bit random string with a salt
and then hash, the range of the mapping is still 256 bit space. John's
comment on brute force is actually talking about this. Now that the hashing
is so fast that it is faster than table lookup, attacker can effectively
create a table on-the-fly. Given that, prefixing with a known string does
not slow the search.

On Fri Nov 14 2014 at 18:40:08 takamichi saito <[email-masked]> wrote:

> "That's why it's so important to use a unique salt for each stored
> password (it reduces the return on investment that the new rainbow table
> will provide)."
>
> >
> >> Unless you can brute force 256 bits of (pseudo)random in under a minute
> or two the code is dead.  Guess wrong, the code should be dead/trash.
> >>
> >>
> >>
> >> > We have discussed it and that was in fact my original
> recommendation.  However I have been convinced that it adds complexity
> without any real improvement in security.
> >>
> >> Really?
> >> > The reality is that people don't bother with rainbow tables these
> days.  They calculate hashes on the fly faster than they can look them up.
> If you are generating the hashes to find a collision then having fixed text
> >> > It is better for people to have more entropy in the code verifier
> than to have a fixed block of text.  I want to avoid people using less bits
> of entropy because they think the hmac is adding something.
> >>
> >> I agree.

---

From: takamichi saito <[email-masked]>
Date: Mon, 17 Nov 2014 11:27:53 +0900

(2014/11/15 1:03), Nat Sakimura wrote:
> The code challenge is only one time use and has a short validity period.
> It is not something that is going to be stored.
>
> For (1), we could define such transformation, but at a later time, IMHO.
> We are getting push back even for sha256 from developers. We need to
> balance the benefit and adoption. BTW, what John mentioned as Brute
> Force attack is not talking about this. See (3).
>
> For (3), as I understand, the salting is to stretch the search space.

Partially or almost No.
Space size is same, as we know.
We can have an unique searching space, if adding an unique fix value.

A)
S256 "code_challenge" = BASE64URL(SHA256("code_verifier"))

In this case of YOUR SCHEME, it is enough for the attacker to have "only 
one" combinaiton table of hashed and original.

B)
S256 "code_challenge" = BASE64URL(SHA256("code_verifier" + "client ID"))

in this case of YOUR SCHEME, attacker have to search the verifier within 
the unique fixed value "client ID".
The attacker have to search an unique searching space, since the 
attacker have to contain "client ID", which is using verification in the 
server.
It is constraint against the attacker.

It is big difference between A and B.

"So another method that attackers use is to steal the salt along with 
the hash, and then generate a new rainbow table for each salt. That's 
why it's so important to use a unique salt for each stored password (it 
reduces the return on investment that the new rainbow table will provide)."
wrtten in
http://blog.ircmaxell.com/2011/08/rainbow-table-is-dead.html?m=1

It is not something stored or password, but for searching in hash.

> In
> stretching the space using a known value seems to be minimal, if at all.
> We are recommending to use 256bit random. (Since we are SHA256ing, more
> bits does not buy us much.) If we stretch the 256 bit random string with
> a salt and then hash, the range of the mapping is still 256 bit space.
> John's comment on brute force is actually talking about this. Now that
> the hashing is so fast that it is faster than table lookup, attacker can
> effectively create a table on-the-fly. Given that, prefixing with a
> known string does not slow the search.

I agree that "The code challenge is only one time use and has a short 
validity period. " from the start, and I said so.
So, the attacker can not have "code_verifier" within the attack time.
"John's comment on brute force" is not my concern.
My concern is the above constraint against attacker.

>
> On Fri Nov 14 2014 at 18:40:08 takamichi saito <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>
>
>
>     2014/11/14 14:13、John Bradley <[email-masked]
>     <mailto:[email-masked]>> のメール：
>
>      > This blog post has some good background on why salting is no
>     longer effective against brute force attacks.
>      >
>     http://blog.ircmaxell.com/__2011/08/rainbow-table-is-dead.__html?m=1
>     <http://blog.ircmaxell.com/2011/08/rainbow-table-is-dead.html?m=1>
>
>     password (it reduces the return on investment that the new rainbow
>     table will provide)."
>
>      >
>      > On Nov 13, 2014, at 6:11 PM, Bill Mills <[email-masked]
>     <mailto:[email-masked]>> wrote:
>      >
>      >> Unless you can brute force 256 bits of (pseudo)random in under a
>     minute or two the code is dead.  Guess wrong, the code should be
>     dead/trash.
>      >>
>      >>
>      >>
>      >> On Thursday, November 13, 2014 7:03 PM, takamichi saito
>     <[email-masked] <mailto:[email-masked]>> wrote:
>      >>
>      >>
>      >> 2014/11/14 10:45、John Bradley <[email-masked]
>     <mailto:[email-masked]>> のメール：
>      >>
>     recommendation.  However I have been convinced that it adds
>     complexity without any real improvement in security.
>      >>
>      >> Really?
>      >> > The reality is that people don't bother with rainbow tables
>     these days.  They calculate hashes on the fly faster than they can
>     look them up.  If you are generating the hashes to find a collision
>     then having fixed text that is known to the attacker won't help.
>      >>
>      >> How quick?
>      >> > It is better for people to have more entropy in the code
>     verifier than to have a fixed block of text.  I want to avoid people
>     using less bits of entropy because they think the hmac is adding
>     something.
>      >>
>      >> I agree.
>      >> >> On Nov 13, 2014, at 3:28 PM, takamichi saito
>     <[email-masked] <mailto:[email-masked]>> wrote:
>      >> >>
>      >> >>
>      >> >> Hi all,
>      >> >>
>      >> >> I mean, a simple use of random as code_verifier may cause
>     that malicious client can have any code_verifier and code_challenge.
>      >> >> S256 "code_challenge" = BASE64URL(SHA256("code___verifier" +
>     “client ID”))
>      >> >> or
>      >> >> S256 "code_challenge" = BASE64URL(SHA256("code___verifier" +
>     “client ID” + “server ID”))
>      >> >> http://www.slideshare.net/nat___sakimura/1112-spoppresso
>     <http://www.slideshare.net/nat_sakimura/1112-spoppresso> .
>      >> >>
>      >> >> _________________________________________________
>      >> >> OAuth mailing list
>      >> >> [email-masked] <mailto:[email-masked]>
>      >> >> https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>
>      >>
>      >>
>      >>
>      >> ;; takamixhi saito
>      >>
>      >> _________________________________________________
>      >> OAuth mailing list
>      >> [email-masked] <mailto:[email-masked]>
>      >> https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>
>      >>
>      >>
>
>
>     ;; takamixhi saito
>
>     _________________________________________________
>     OAuth mailing list
>     [email-masked] <mailto:[email-masked]>
>     https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>
>

-- 
;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Mon, 17 Nov 2014 11:39:44 +0900

(2014/11/14 13:02), Bill Mills wrote:
> Yes, "plain" is actually sufficient.  The hashed value protects against
> disclosure/logging threats on the server auth server and proxies perhaps
> where the HTTPS is terminated somewhere other than the auth server
> itself, it's not actually required for the basic functionality/security
> of the mechanism.

In the threat model of the SPOP scheme, a wiretap is in it.

And more, the hash is not used to keep secretly in the sever/client.

> 2014/11/14 10:55、Bill Mills <[email-masked]
> <mailto:[email-masked]>> のメール：
>
>  > The whole mechanism relies on the attacker not having access to the
> code_verifier or hash.  It's defending against the attacker getting the
> code via weakness in IPC or other such mechanism like URI handlers.  How
> many more bits is secure beyond 256 bits of entropy recommended?  If you
> want to make it longer then just make it longer, salting doesn't really
> help that much.
>  >
>  > The original value or the hashed value *should* be protected by the
> transport security, and if it isn't then the attacker could be stealing
> the original credential used to authenticate anyway.
>  >
>
> Is it correct?
>  > On Thursday, November 13, 2014 5:40 PM, takamichi saito
>  > http://www.slideshare.net/nat_sakimura/1112-spoppresso
> <http://www.slideshare.net/nat_sakimura/1112-spoppresso>.
>  >

-- 
;; takamixhi saito

---

From: Nat Sakimura <[email-masked]>
Date: Mon, 17 Nov 2014 04:06:43 +0000

I am actually not convinced. Since the code verifier is 256bit random,
adding salt does not seem to help.
Salting definitely helps if len(password) << 256 bit, but ...

---

From: John Bradley <[email-masked]>
Date: Sun, 16 Nov 2014 23:33:17 -0500

The question is what is the attack.

Any salt added needs to be communicated from the client to the AS, so we must assume that the attacker has it.

The attacker can then a) create rainbow table using the client id or whatever is the known salt.  Yes the attacker  must create a new table per client.   
Salting is really only effective for low entropy passwords to try and slow down a rainbow table attack by making the input to the hash be higher than the that of the password on it's own.

Currently attackers can generate over 4Billion SHA256 hashes per second on a single GPU card.  (Thank you bitcoin) 

It is faster to generate the hashes than to look them up via a index. 

If you are generating the hash in real time salting provides no determent, as the salt is just included in the hash calculation.

If the code verifier was a password rather than a 256bit random key then a hash would add value against rainbow tables.

In reality finding a collision against a salted password is much easier using real time hash generation than by using rainbow tables. 

Using SHA256 with a short hash is not safe for passwords any more.   Something like PBES2 with at-least 200 rounds needs to be used, if you want have password files from being compromised quickly if disclosed.  (Yes I know people are not doing that,  and hence part of the reason why passwords are no longer secure)

More entropy in the code verifier adds to security eg moving to SHA512 and larger verifiers, but adding a salt to SHA256 is basically a no op when defending against modern attacks.

I did originally agree with your position and wanted to HMAC the client_id to defend against rainbow tables, however I am now convinced that the attack has moved on so that is no more efective than a plain hash over a random 256bit value.

John B.

> On Nov 16, 2014, at 11:06 PM, Nat Sakimura <[email-masked]> wrote:
> 
> I am actually not convinced. Since the code verifier is 256bit random, adding salt does not seem to help. 
> On Mon Nov 17 2014 at 11:39:07 takamichi saito <[email-masked] <mailto:[email-masked]>> wrote:
> 
> 
> > On Thursday, November 13, 2014 7:07 PM, takamichi saito
> > 2014/11/14 10:55、Bill Mills <[email-masked] <mailto:[email-masked]>
> > <mailto:[email-masked] <mailto:[email-masked]>>> のメール：
> >
> > <[email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
> >  >
> >  >
> >  >
> >  > Hi all,
> >  >
> >  > http://www.slideshare.net/nat_sakimura/1112-spoppresso <http://www.slideshare.net/nat_sakimura/1112-spoppresso>
> > <http://www.slideshare.net/nat_sakimura/1112-spoppresso <http://www.slideshare.net/nat_sakimura/1112-spoppresso>>.
> >  >
> >  > [email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>
> >  > https://www.ietf.org/mailman/listinfo/oauth <https://www.ietf.org/mailman/listinfo/oauth>
> >
> >  >
> >  >
> >
> >
> > ;; takamixhi saito
> >
> > [email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>
> > https://www.ietf.org/mailman/listinfo/oauth <https://www.ietf.org/mailman/listinfo/oauth>
> >
> >
> 
> 
> --
> ;; takamixhi saito
> 
> https://www.ietf.org/mailman/listinfo/oauth <https://www.ietf.org/mailman/listinfo/oauth>

---

From: takamichi saito <[email-masked]>
Date: Tue, 18 Nov 2014 12:27:28 +0900

I agree that GPU can/may find the value on the fly.
But, it can not find it within the session.
The draft idea is enough against the attack with GPU.

On the other, the draft idea provide ONLY one combination of hash and 
its plain. The attacker can prepare THE COMBINATION to success the attack.

Adding client_ID or server_ID separate the searching space.
Then the attacker have to find the value in each case for the attack.
(The reason was said before.)

(2014/11/17 13:33), John Bradley wrote:
> The attacker can then a) create rainbow table using the client id or
> whatever is the known salt.  Yes the attacker  must create a new table
> per client.
> Salting is really only effective for low entropy passwords to try and
> slow down a rainbow table attack by making the input to the hash be
> higher than the that of the password on it's own.
>
> Currently attackers can generate over 4Billion SHA256 hashes per second
> on a single GPU card.  (Thank you bitcoin)
>
> If you are generating the hash in real time salting provides no
> determent, as the salt is just included in the hash calculation.
>
> If the code verifier was a password rather than a 256bit random key then
> a hash would add value against rainbow tables.
>
> In reality finding a collision against a salted password is much easier
> using real time hash generation than by using rainbow tables.
>
> Using SHA256 with a short hash is not safe for passwords any more.
> Something like PBES2 with at-least 200 rounds needs to be used, if you
> want have password files from being compromised quickly if disclosed.
>   (Yes I know people are not doing that,  and hence part of the reason
> why passwords are no longer secure)
>
> More entropy in the code verifier adds to security eg moving to SHA512
> and larger verifiers, but adding a salt to SHA256 is basically a no op
> when defending against modern attacks.
>
> I did originally agree with your position and wanted to HMAC the
> client_id to defend against rainbow tables, however I am now convinced
> that the attack has moved on so that is no more efective than a plain
> hash over a random 256bit value.
>
> John B.
>
>> On Nov 16, 2014, at 11:06 PM, Nat Sakimura <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>>     <mailto:[email-masked]>
>>     > <mailto:[email-masked]
>>     <mailto:[email-masked]>__>> のメール：
>>     >
>>     > <[email-masked] <mailto:[email-masked]>
>>     <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>>     >  >
>>     >  >
>>     >  >
>>     >  > Hi all,
>>     >  >
>>     >  > All combinations of random and its hash can be obtained, it
>>     may not
>>     > be risk?
>>     >  >
>>     >  > So, we should use:
>>     <http://www.slideshare.net/nat_sakimura/1112-spoppresso>
>>     > <http://www.slideshare.net/__nat_sakimura/1112-spoppresso
>>     <http://www.slideshare.net/nat_sakimura/1112-spoppresso>>.
>>     >  >

-- 
;; takamixhi saito

---

From: Bill Mills <[email-masked]>
Date: Tue, 18 Nov 2014 04:17:07 +0000 (UTC)

Again, the only value of including client ID or any other value in this case is to increase the number of bits of entropy in the value being hashed. Using client ID is only useful if it's actually got decent entropy in it, if it's just a version number then or a server name or address it adds very little.

Yes, salting is valuable for passwords which have very low entropy.  But as has been discussed it adds little in this case.  Your arguments are correct for passwords but not for 256 bits of random number.

Regards,

-bill 

On Monday, November 17, 2014 7:27 PM, takamichi saito <[email-masked]> wrote:

-- 
;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Tue, 18 Nov 2014 13:34:23 +0900

> Again, the only value of including client ID or any other value in this case is to increase the number of bits of entropy in the value being hashed. Using client ID is only useful if it's actually…

Client_ID is not for adding entropy.
Again, Client_ID is separating the attacker's searching space.

> Yes, salting is valuable for passwords which have very low entropy.  But as has been discussed it adds little in this case.  Your arguments are correct for passwords but not for 256 bits of random…

I agree that human-made password is low entropy.
As I say, adding Client_ID can force the attacker has to search the 
value in each attack.
If the attacker uses GPU, he can not get the value within the session.

I never confuse about password in these discussions.

-- 
;; takamixhi saito

---

From: Bill Mills <[email-masked]>
Date: Tue, 18 Nov 2014 04:54:18 +0000 (UTC)

There will be no rainbow table for 256bits of search space.  Suppose then that clientID has 256 possible values.  How does salting with client ID do anything more than making the search space 264 bits?

You keep saying that a salt is better than just adding entropy, but never actually justifying it.

On Monday, November 17, 2014 8:34 PM, takamichi saito <[email-masked]> wrote:

-- 
;; takamixhi saito

---

From: John Bradley <[email-masked]>
Date: Tue, 18 Nov 2014 00:33:08 -0500

I think where we are differing is that you think looking up a precomputed plain based on a indexed hash across some sort of media can be done faster than 3 Giga SHA256 Hash/s.
on a small system http://thepasswordproject.com/oclhashcat_benchmarking 

I don't think the largest disk arrays can keep up with that.

Do you have some evidence that shows that precomputing hashes would be an effective attack against 256 bits of entropy.   I agree that it would be agains the 40 ish bits of entropy in a password.

The likely mitigation is using PBKDF2 or BCrypt rather than SHA256, but that would slow adoption and can be added later.

John B.

My contention is that it can't 
> On Nov 17, 2014, at 10:27 PM, takamichi saito <[email-masked]> wrote:
> 
> 
> On the other, the draft idea provide ONLY one combination of hash and its plain. The attacker can prepare THE COMBINATION to success the attack.
>

---

From: Nat Sakimura <[email-masked]>
Date: Tue, 18 Nov 2014 08:08:21 +0000

The code verifier is 256 bit high entropy cryptographic random.

Let D:= {d | all possible 256 bit random}. This is the set of all possible
code verifiers.
Let S be SHA256 function.
Then, set of all possible code challenge corresponding to D, which is
denoted by R, is defined as:
S:D->R.
Note that D=R.
Rainbow table attack is to prepare a mapping table enumerating d∈D to r∈R
and look up the value of ri=code_challenge to find the corresponding di,
the code_verifier.
Let such table to be expressed by T.
Salting is creating a string d'=s||d where '||' is the concatenation
operator and s is a string of length > 0.
Let D':={any d'}.
Let R'=S(D').
Note that by the nature of S, R'=R=D.

Suppose the attacker who has T but does not have the corresponding salted
table T' observed the code_challenge r'.
He can still look up r' from T and find the corresponding value for the
code_verifier, v, in it.
Note v!=d', but S(v)=S(d'). (At this point, we have found a weak collision
in S!)
Then, the client can send v as the code_verifier to the server and still
the verification at the server succeeds.
i.e., salting did not make it harder for the attack to succeed.

You could also argue that by salting, the search space become larger.
However, this is true if D is a strict subset of D' because then S(D) will
be a strict subset of S(D'). However, due to the definition of D,
S(D)=S(D').

Finally, let us take a substantially smaller subset C of D as the domain of
S. Let C' be the set of x||c where x is a salt and c is an element of C.
Suppose that C was known by the attacker and the attacker has created the
corresponding table Tc. This is typically the case when the distribution of
d is not uniform and skewed, such as often used passwords. In this case,
salting used to help as calculating new hash from C' was typically slower
than reading out Tc. This holds true as long as the speed of lookup of the
256bit value from the table is faster than calculating a S(c'). This,
unfortunately is no longer true as John has pointed out [1]. But again,
this become irrelevant when C=D.

[1] Use of PBES2 with increasing n is an attempt to keep this (lookup time)
< (calcluation time) formula.

Best,

Nat

On Tue Nov 18 2014 at 14:34:03 John Bradley <[email-masked]> wrote:

> I think where we are differing is that you think looking up a precomputed
> plain based on a indexed hash across some sort of media can be done faster
> than 3 Giga SHA256 Hash/s.
> Do you have some evidence that shows that precomputing hashes would be an
> effective attack against 256 bits of entropy.   I agree that it would be
> agains the 40 ish bits of entropy in a password.
>
> The likely mitigation is using PBKDF2 or BCrypt rather than SHA256, but
> that would slow adoption and can be added later.
>
> John B.
>
>
>
>

---

From: Bill Mills <[email-masked]>
Date: Tue, 18 Nov 2014 16:33:10 +0000 (UTC)

In this case it ceaper to add bits than use soemthing like BCrypt.

On Monday, November 17, 2014 9:33 PM, John Bradley <[email-masked]> wrote:
I think where we are differing is that you think looking up a precomputed plain based on a indexed hash across some sort of media can be done faster than 3 Giga SHA256 Hash/s.
on a small system http://thepasswordproject.com/oclhashcat_benchmarking 

John B.

---

From: John Bradley <[email-masked]>
Date: Tue, 18 Nov 2014 11:42:22 -0500

Yes SHA512 or even a left half SHA512 slows the attacker significantly over SHA256 as that alg has had a lot of ASIC optimization.    

I personally think that SHA256 for a short lived token is still good for a while. 

Sent from my iPhone

> On Nov 18, 2014, at 11:33 AM, Bill Mills <[email-masked]> wrote:
>

---

From: takamichi saito <[email-masked]>
Date: Wed, 19 Nov 2014 14:04:22 +0900

(2014/11/18 17:08), Nat Sakimura wrote:
> Let D:= {d | all possible 256 bit random}. This is the set of all
> possible code verifiers.

Mathematically, it is not correct.
Depeding on the mathetical definition of D, D is quite larger than R.
Then we can not write D=R.

> Rainbow table attack is to prepare a mapping table enumerating d∈D to
> r∈R and look up the value of ri=code_challenge to find the corresponding
> di, the code_verifier.

Mathematically, it is not correct.
It is confused with a bijective function.
Hash is not injective but a surjective function.

That's why adding client_ID gets effect.

The following is happened with no-injective but a surjective function, 
e.g. hash function.
hash( 12345 | "client_ID" ) = 4567
hash( 789 ) = 4567

Even if cryptographical hash has the property `second preimage 
resistance', the collision can be happened.

Again,
adding client_ID is NOT only for expanding the searching space.
It is a constraing against an attacker to search the code_verifier.

>
> Suppose the attacker who has T but does not have the corresponding
> salted table T' observed the code_challenge r'.
> Note v!=d', but S(v)=S(d'). (At this point, we have found a weak
> collision in S!)
> However, this is true if D is a strict subset of D' because then S(D)
> will be a strict subset of S(D'). However, due to the definition of D,
> S(D)=S(D').
>
> Finally, let us take a substantially smaller subset C of D as the domain
> of S. Let C' be the set of x||c where x is a salt and c is an element of C.
> Suppose that C was known by the attacker and the attacker has created
> the corresponding table Tc. This is typically the case when the
> distribution of d is not uniform and skewed, such as often used
> passwords. In this case, salting used to help as calculating new hash
> from C' was typically slower than reading out Tc. This holds true as
> long as the speed of lookup of the 256bit value from the table is faster
> than calculating a S(c'). This, unfortunately is no longer true as John
> has pointed out [1]. But again, this become irrelevant when C=D.
>
> [1] Use of PBES2 with increasing n is an attempt to keep this (lookup
> time) < (calcluation time) formula.
>
> Best,
>
> Nat
>
> On Tue Nov 18 2014 at 14:34:03 John Bradley <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     I think where we are differing is that you think looking up a
>     precomputed plain based on a indexed hash across some sort of media
>     can be done faster than 3 Giga SHA256 Hash/s.
>     on a small system
>     http://thepasswordproject.com/__oclhashcat_benchmarking
>     <http://thepasswordproject.com/oclhashcat_benchmarking>
>
>     Do you have some evidence that shows that precomputing hashes would
>     be an effective attack against 256 bits of entropy.   I agree that
>     it would be agains the 40 ish bits of entropy in a password.
>
>     The likely mitigation is using PBKDF2 or BCrypt rather than SHA256,
>     but that would slow adoption and can be added later.
>
>     John B.
>
>
>
>
>      > On Nov 17, 2014, at 10:27 PM, takamichi saito
>      > On the other, the draft idea provide ONLY one combination of hash
>     and its plain. The attacker can prepare THE COMBINATION to success
>     the attack.
>      >
>      >> Any salt added needs to be communicated from the client to the
>     AS, so we
>      >> must assume that the attacker has it.
>      >>
>     <mailto:[email-masked]>
>      >>> <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>      >>>
>      >>> On Mon Nov 17 2014 at 11:39:07 takamichi saito
>      >>>    > Yes, "plain" is actually sufficient.  The hashed value
>     protects
>      >>>    against
>      >>>    > disclosure/logging threats on the server auth server and
>     proxies
>      >>>    perhaps
>     <mailto:[email-masked]>__>
>      >>>    > <mailto:[email-masked] <mailto:[email-masked]>
>     <mailto:[email-masked]>__>__>> のメール：
>      >>>    >
>      >>>    >  > The whole mechanism relies on the attacker not having
>     access
>      >>>    to the
>      >>>    > want to make it longer then just make it longer, salting
>     doesn't
>      >>>    really
>      >>>    > help that much.
>      >>>    >  >
>      >>>    >  > The original value or the hashed value *should* be
>     protected
>      >>>    by the
>     <mailto:[email-masked] <mailto:[email-masked]>>
>      >>>    <mailto:[email-masked] <mailto:[email-masked]>
>     <mailto:[email-masked] <mailto:[email-masked]>>>__> wrote:
>      >>>    >  >
>      >>>    >  >
>      >>>    >  >
>      >>>    >  > Hi all,
>      >>>    >  >
>      >>>    >  > I appreciate this idea, simple and powerful to achieve
>     proof of
>      >>>    > possession.
>      >>>    >  > S256 "code_challenge" =
>     BASE64URL(SHA256("code_____verifier" +
>      >>>    “client ID”))
>      >>>    >  > or
>      >>>    >  > S256 "code_challenge" =
>     BASE64URL(SHA256("code_____verifier" +
>      >>>    “client
>      >>>    > ID” + “server ID”))
>     http://www.slideshare.net/nat_____sakimura/1112-spoppresso
>     <http://www.slideshare.net/nat___sakimura/1112-spoppresso>
>     <http://www.slideshare.net/nat_sakimura/1112-spoppresso>>
>      >>>    >
>     <http://www.slideshare.net/____nat_sakimura/1112-spoppresso
>     <http://www.slideshare.net/__nat_sakimura/1112-spoppresso>
>     <http://www.slideshare.net/nat_sakimura/1112-spoppresso>>>__.
>      >>>    >  >
>      >>>    >  > ___________________________________________________
>      >>>    >  > OAuth mailing list
>     <mailto:[email-masked] <mailto:[email-masked]>>
>     <mailto:[email-masked] <mailto:[email-masked]>
>      >>>    <mailto:[email-masked] <mailto:[email-masked]>>>
>      >>>    >  > https://www.ietf.org/mailman/____listinfo/oauth
>     <https://www.ietf.org/mailman/__listinfo/oauth>
>      >>>    <https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>>
>      >>>    >
>      >>>    >  >
>      >>>    >  >
>      >>>    >
>      >>>    >
>      >>>    > ;; takamixhi saito
>      >>>    >
>      >>>    > ___________________________________________________
>      >>>    > OAuth mailing list
>     <mailto:[email-masked] <mailto:[email-masked]>>
>     <mailto:[email-masked] <mailto:[email-masked]>
>      >>>    <mailto:[email-masked] <mailto:[email-masked]>>>
>      >>>    > https://www.ietf.org/mailman/____listinfo/oauth
>     <https://www.ietf.org/mailman/__listinfo/oauth>
>      >>>    <https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>>
>      >>>    >
>      >>>    >
>      >>>
>      >>>
>      >>>    --
>      >>>    ;; takamixhi saito
>      >>>
>      >>>    ___________________________________________________
>      >>>    OAuth mailing list
>      >>> https://www.ietf.org/mailman/____listinfo/oauth
>     <https://www.ietf.org/mailman/__listinfo/oauth>
>      >>>    <https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>>
>      >>>

-- 
;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Wed, 19 Nov 2014 14:43:21 +0900

> You keep saying that a salt is better than just adding entropy, but never actually justifying it.

Adding client_ID is not only for like adding password's salt.
Adding client_ID is not same as adding password's salt in this context.

-- 
;; takamixhi saito

---

From: Sergey Beryozkin <[email-masked]>
Date: Wed, 19 Nov 2014 10:01:15 +0100

Hi

Apologies for getting into this thread (I do not understand most of the 
mathematics at this stage :)),
On 19/11/14 06:43, takamichi saito wrote:
>> There will be no rainbow table for 256bits of search space.  Suppose
>> then that clientID has 256 possible values.  How does salting with
>> client ID do anything more than making the search space 264 bits?
>>
You've mentioned it would separate a search space, but as far as I 
understand that would require a client to randomly add either its 
client_id or server_id to the signature function. If it is only adding a 
client id then it sounds like a salt. Is that right ? I think I can 
understand that.
The question is, where is a 'server_id' coming from and how a server 
would know that the signature was calculated with a client_id or 
server_id added in ?

Sorry if it is all just the noise...

Thanks, Sergey
>>> Again, the only value of including client ID or any other value in
>>> this case is to increase the number of bits of entropy in the value
>>> being hashed. Using client ID is only useful if it's actually got
>>> decent entropy in it, if it's just a version number then or a server
>>> name or address it adds very little.
>>>
>>
>>> Yes, salting is valuable for passwords which have very low entropy.
>>> But as has been discussed it adds little in this case.  Your
>>> arguments are correct for passwords but not for 256 bits of random
>>> number.
>>>
>>
>>>> Any salt added needs to be communicated from the client to the AS,
>>>> so we
>>>>> BASE64URL(SHA256("code___verifier" +
>>>>>       “client ID”))
>>>>>       >  > or
>>>>>       >  > S256 "code_challenge" =
>>>>> BASE64URL(SHA256("code___verifier" +
>>>>>       “client
>>>>>       > ID” + “server ID”))

---

From: Nat Sakimura <[email-masked]>
Date: Wed, 19 Nov 2014 09:40:53 +0000

Yes, S() is surjection. Specifically, it is defined over X:={x | len(x) =<
2^64 -1}, and the range is R.  R is included in X. However, in SPOP's case,
the Domain is constrained to D, which is equal to R. That's what I was
explaining. Then, I have defined a rainbow table T:D->R and demonstrated
that salt actually does not help.

Nat

On Wed Nov 19 2014 at 14:43:40 takamichi saito <[email-masked]> wrote:

> then that clientID has 256 possible values.  How does salting with client
> ID do anything more than making the search space 264 bits?
> >
> >> Again, the only value of including client ID or any other value in this
> case is to increase the number of bits of entropy in the value being
> hashed. Using client ID is only useful if it's actually got decent entropy
> in it, if it's just a version number then or a server name or address it
> adds very little.
> >>
> >
> But as has been discussed it adds little in this case.  Your arguments are
> correct for passwords but not for 256 bits of random number.
> >>
> >
> >>> Any salt added needs to be communicated from the client to the AS, so
> we
> that
> >>>>       >  > [email-masked] <mailto:[email-masked]> <mailto:
> [email-masked]
> >>>>       <mailto:[email-masked]>>

---

From: John Bradley <[email-masked]>
Date: Wed, 19 Nov 2014 07:17:10 -0500

Hi Sergey,

If we change from a SHA256 function over the code_verifier to a SHA256 over the concatenation of the code_verifier and client_id, that would be defined in the spec.
We would not do both, and the salt would not be a real random.   There would be many instances of a client all using the same salt value.

The client_id is sent in both the request to the authorization endpoint and the token endpoint and is validated by having a registered redirect_uri.

The question is if doing that adds any net security given the likely attacks. 

I originally proposed using a SHA256 HMAC of the client)id in one of the first drafts.   (effectively the same as a hash of the concatenation of the two values)

That was taken out as being too complicated for developers based on feedback.

The compromise was a simple SHA256 hash of the code verifier.   This allowed Google and others to support this transform as Mandatory to Implement on the server.

I have been convinced that as long as the code_verifier as enough entropy (256bits) using the HMAC didn't add enough security to warrant the additional concatenation step.

In the theoretical yes splitting the search space by adding a salt is better than not if the attacker is using precomputed values, and is a wash if the attacker can compute hashes useng the salt in real time as fast or faster than using a lookup.

The only downside to using a salt is that people may elect to reduce the size of code_verifier because they feel the salt is providing some security.

If the client uses a 128bit random  for code verifier and a fixed 128bit client_id to produce a 256bit has that would be significantly less secure than using using a 256bit code_verifier if the attacker is using oclhashcat with GPU.  http://hashcat.net/oclhashcat/

If we do go back to effectively doing a HMAC then we do need to be careful that people don't reduce the entropy of code_verifyer.

John B.

> On Nov 19, 2014, at 4:01 AM, Sergey Beryozkin <[email-masked]> wrote:
> 
> Hi
> 
> Apologies for getting into this thread (I do not understand most of the mathematics at this stage :)),
> You've mentioned it would separate a search space, but as far as I understand that would require a client to randomly add either its client_id or server_id to the signature function. If it is only adding a client id then it sounds like a salt. Is that right ? I think I can understand that.
> The question is, where is a 'server_id' coming from and how a server would know that the signature was calculated with a client_id or server_id added in ?
>

---

From: Sergey Beryozkin <[email-masked]>
Date: Wed, 19 Nov 2014 14:47:24 +0100

Hi John

Thanks for going over it again and explaining it all so nicely, even I 
do understand it now (I'd like to think so :-)) why using a client id as 
a salt does not add much to the signature strength.
I thought the idea was consider to introduce some extra randomization, 
where say even multiple clients with the same id can sometimes use a 
server id as opposed to a client id to add to the signature function 
input. May be I've misunderstood.
It's been an interesting thread to watch for sure :-)

Many thanks, Sergey

---

From: takamichi saito <[email-masked]>
Date: Wed, 19 Nov 2014 23:39:11 +0900

On 2014/11/18, at 17:08, Nat Sakimura wrote:

> Let D:= {d | all possible 256 bit random}. This is the set of all possible code verifiers. 
> Then, set of all possible code challenge corresponding to D, which is denoted by R, is defined as: 
> S:D->R. 
> Note that D=R. 
> Rainbow table attack is to prepare a mapping table enumerating d∈D to r∈R and look up the value of ri=code_challenge to find the corresponding di, the code_verifier. 
> Salting is creating a string d'=s||d where '||' is the concatenation operator and s is a string of length > 0. 
> Let D':={any d'}. 
> Let R'=S(D'). 
> Suppose the attacker who has T but does not have the corresponding salted table T' observed the code_challenge r'. 
> He can still look up r' from T and find the corresponding value for the code_verifier, v, in it. 
> Note v!=d', but S(v)=S(d'). (At this point, we have found a weak collision in S!) 
> Then, the client can send v as the code_verifier to the server and still the verification at the server succeeds. 

From the view point of the definition of the scheme, this point is incorrect and a big mistake.
The server should not accept v where v!=d', but S(v)=S(d') .
The server should accept v where v!=d', but S(v || client_id) = S(d') .
That's why the attacker must be under the stronger constraint.

When the server verifies code_verifier, 
the server should check the below equality:
code_challenge = base64url(sha256( "server's received value" || client_id))

it should not check:
code_challenge = base64url(sha256("server's received value"))

These ware said before.

Moreover, even if code_verifier has low entropy, 
the situation must be better rather than worse in this case.

> You could also argue that by salting, the search space become larger. However, this is true if D is a strict subset of D' because then S(D) will be a strict subset of S(D'). However, due to the definition of D, S(D)=S(D'). 
> 
> Finally, let us take a substantially smaller subset C of D as the domain of S. Let C' be the set of x||c where x is a salt and c is an element of C. 
> Suppose that C was known by the attacker and the attacker has created the corresponding table Tc. This is typically the case when the distribution of d is not uniform and skewed, such as often used passwords. In this case, salting used to help as calculating new hash from C' was typically slower than reading out Tc. This holds true as long as the speed of lookup of the 256bit value from the table is faster than calculating a S(c'). This, unfortunately is no longer true as John has pointed out [1]. But again, this become irrelevant when C=D. 
> 
> [1] Use of PBES2 with increasing n is an attempt to keep this (lookup time) < (calcluation time) formula.
> 
> Best, 
> 
> Nat
> 

;; takamixhi saito

---

From: takamichi saito <[email-masked]>
Date: Wed, 19 Nov 2014 23:56:46 +0900

> You've mentioned it would separate a search space, but as far as I understand that would require a client to randomly add either its client_id or server_id to the signature function. If it is only…

Adding client_id or server_id is not only for expanding	the searching space in case of attacking hash,
but also for separating the space each session.
This is protocol, we do not talk about cracking password.
Therefore, the attacker should overcome the server's verification.
Moreover,
to find v where v!=d', but S(v)=S(d') is general,
but to find v where v!=d', but S(v || client_id) = S(d') is unique to the session.
Then, the attacker find it in each session.
It can separate the space.

;; takamixhi saito