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

[takamichi saito <[e-mail]>]

(2014/11/18 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.

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.
> 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.

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'.
> 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 <[e-mail]
> <mailto:[e-mail]>> 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>
>
>     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
>     <[e-mail] <mailto:[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]>
>      >>> <mailto:[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]>
>      >>> <mailto:[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]>
>     <mailto:[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]>__>
>      >>>    > <mailto:[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]>>
>      >>>    <mailto:[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>>
>      >>>    >
>     <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]>>
>     <mailto:[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>
>      >>>    <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]>>
>     <mailto:[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>
>      >>>    <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>
>      >>>    <https://www.ietf.org/mailman/__listinfo/oauth
>     <https://www.ietf.org/mailman/listinfo/oauth>>
>      >>>
>      >>> _________________________________________________
>      >>> 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
>     <https://www.ietf.org/mailman/listinfo/oauth>
>


-- 
;; takamixhi saito