On 2014/11/18, at 17:08, Nat Sakimura wrote:
> 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.
>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.
> 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 <ve7...@ve7jtb.com> 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
>
> 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 <sa...@cs.meiji.ac.jp> 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 <sakim...@gmail.com
> >>> <mailto:sakim...@gmail.com>> 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 <sa...@cs.meiji.ac.jp
> >>> <mailto:sa...@cs.meiji.ac.jp>> 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
> >>> > <sa...@cs.meiji.ac.jp <mailto:sa...@cs.meiji.ac.jp>> wrote:
> >>> >
> >>> >
> >>> > Sorry for my poor english.
> >>> >
> >>> >
> >>> > 2014/11/14 10:55、Bill Mills <wmills_92...@yahoo.com
> >>> <mailto:wmills_92...@yahoo.com>
> >>> > <mailto:wmills_92...@yahoo.com
> >>> <mailto:wmills_92...@yahoo.com>__>> のメール：
> >>> >
> >>> > > 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
> >>> > <sa...@cs.meiji.ac.jp <mailto:sa...@cs.meiji.ac.jp>
> >>> <mailto:sa...@cs.meiji.ac.jp <mailto:sa...@cs.meiji.ac.jp>>> 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
> >>> > > OAuth@ietf.org <mailto:OAuth@ietf.org> <mailto:OAuth@ietf.org
> >>> <mailto:OAuth@ietf.org>>
> >>> > > https://www.ietf.org/mailman/__listinfo/oauth
> >>> <https://www.ietf.org/mailman/listinfo/oauth>
> >>> >
> >>> > >
> >>> > >
> >>> >
> >>> >
> >>> > ;; takamixhi saito
> >>> >
> >>> > _________________________________________________
> >>> > OAuth mailing list
> >>> > OAuth@ietf.org <mailto:OAuth@ietf.org> <mailto:OAuth@ietf.org
> >>> <mailto:OAuth@ietf.org>>
> >>> > https://www.ietf.org/mailman/__listinfo/oauth
> >>> <https://www.ietf.org/mailman/listinfo/oauth>
> >>> >
> >>> >
> >>>
> >>>
> >>> --
> >>> ;; takamixhi saito
> >>>
> >>> _________________________________________________
> >>> OAuth mailing list
> >>> OAuth@ietf.org <mailto:OAuth@ietf.org>
> >>> https://www.ietf.org/mailman/__listinfo/oauth
> >>> <https://www.ietf.org/mailman/listinfo/oauth>
> >>>
> >>> _______________________________________________
> >>> OAuth mailing list
> >>> OAuth@ietf.org <mailto:OAuth@ietf.org>
> >>> https://www.ietf.org/mailman/listinfo/oauth
> >>
> >
> >
> > --
> > ;; takamixhi saito
> >
> > _______________________________________________
> > OAuth mailing list
> > OAuth@ietf.org
> > https://www.ietf.org/mailman/listinfo/oauth
>
> _______________________________________________
> OAuth mailing list
> OAuth@ietf.org
> https://www.ietf.org/mailman/listinfo/oauth
;; takamixhi saito
_______________________________________________
OAuth mailing list
OAuth@ietf.org
https://www.ietf.org/mailman/listinfo/oauth
