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

[Sergey Beryozkin <[e-mail]>]

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
On 19/11/14 13:17, John Bradley wrote:
> 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
>