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

[Nat Sakimura <[e-mail]>]

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 <[e-mail]> 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.
>
>
> >
> > 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
> >>>
> >>
> >>
> >
> >
>
>
> --
> ;; takamixhi saito
>
> _______________________________________________
> OAuth mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/oauth
>