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

[John Bradley <[e-mail]>]

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 <[e-mail]> wrote:
> 
> 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:
>> (2014/11/18 13:54), Bill Mills 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 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.
>> 
> 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
>> 
>>> 
>>> On Monday, November 17, 2014 8:34 PM, takamichi saito
>>> <[e-mail]> wrote:
>>> (2014/11/18 13:17), Bill Mills wrote:
>>>> 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.
>>>> 
>>> 
>>> 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
>>>> number.
>>>> 
>>> 
>>> 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.
>>> 
>>> 
>>> 
>>>> Regards,
>>>> 
>>>> -bill
>>>> 
>>>> 
>>>> 
>>>> On Monday, November 17, 2014 7:27 PM, takamichi saito
>>>> <[e-mail]> wrote:
>>>> 
>>>> 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 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 <[e-mail]
>>>>>> <mailto:[e-mail]>> wrote:
>>>>>> 
>>>>>> 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 ...
>>>>>> 
>>>>>> 
>>>>>> On Mon Nov 17 2014 at 11:39:07 takamichi saito <[e-mail]
>>>>>> <mailto:[e-mail]>> wrote:
>>>>>> 
>>>>>> 
>>>>>> 
>>>>>>      (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.
>>>>>> 
>>>>>> 
>>>>>>      >
>>>>>>      >
>>>>>>      > On Thursday, November 13, 2014 7:07 PM, takamichi saito
>>>>>>      > <[e-mail] <mailto:[e-mail]>> wrote:
>>>>>>      >
>>>>>>      >
>>>>>>      > Sorry for my poor english.
>>>>>>      >
>>>>>>      >
>>>>>>      > 2014/11/14 10:55、Bill Mills <[e-mail]
>>>>>>      <mailto:[e-mail]>
>>>>>>      > <mailto:[e-mail]
>>>>>>      <mailto:[e-mail]>__>> のメール：
>>>>>>      >
>>>>>>      >  > 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?
>>>>>>      > You mean that we don’t need to use hash itself? Only to use
>>>>>>      plain is enough?
>>>>>>      >
>>>>>>      >
>>>>>>      >  >
>>>>>>      >  >
>>>>>>      >  >
>>>>>>      >  > On Thursday, November 13, 2014 5:40 PM, takamichi saito
>>>>>>      > <[e-mail] <mailto:[e-mail]>
>>>>>>      <mailto:[e-mail] <mailto:[e-mail]>>>
>>>>>> wrote:
>>>>>>      >  >
>>>>>>      >  >
>>>>>>      >  >
>>>>>>      >  > 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
>>>>>>      <http://www.slideshare.net/nat_sakimura/1112-spoppresso>
>>>>>>      > <http://www.slideshare.net/__nat_sakimura/1112-spoppresso
>>>>>>      <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
>>>>>>      >  >
>>>>>>      >  > _________________________________________________
>>>>>>      >  > OAuth mailing list
>>>>>>      >  > [e-mail] <mailto:[e-mail]>
>>>>>> <mailto:[e-mail]
>>>>>>      <mailto:[e-mail]>>
>>>>>>      >  > https://www.ietf.org/mailman/__listinfo/oauth
>>>>>>      <https://www.ietf.org/mailman/listinfo/oauth>
>>>>>>      >
>>>>>>      >  >
>>>>>>      >  >
>>>>>>      >
>>>>>>      >
>>>>>>      > ;; takamixhi saito
>>>>>>      >
>>>>>>      > _________________________________________________
>>>>>>      > OAuth mailing list
>>>>>>      > [e-mail] <mailto:[e-mail]> <mailto:[e-mail]
>>>>>>      <mailto:[e-mail]>>
>>>>>>      > https://www.ietf.org/mailman/__listinfo/oauth
>>>>>>      <https://www.ietf.org/mailman/listinfo/oauth>
>>>> 
>>>>>>      >
>>>>>>      >
>>>>>> 
>>>>>> 
>>>>>>      --
>>>>>>      ;; takamixhi saito
>>>>>> 
>>>>>>      _________________________________________________
>>>>>>      OAuth mailing list
>>>>>>    [e-mail] <mailto:[e-mail]>
>>>>>>    https://www.ietf.org/mailman/__listinfo/oauth
>>>>>>      <https://www.ietf.org/mailman/listinfo/oauth>
>>>>>> 
>>>>>> _______________________________________________
>>>>>> OAuth mailing list
>>>>>> [e-mail] <mailto:[e-mail]>
>>>>>> https://www.ietf.org/mailman/listinfo/oauth
>>>>> 
>>>> 
>>>> 
>>> 
>>> 
>> 
>> 
> 
> _______________________________________________
> OAuth mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/oauth