(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 <ve7...@ve7jtb.com
<mailto: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
<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 <mailto: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>
>>> <mailto: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>
>>> <mailto: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>
<mailto: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>__>
>>> > <mailto: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>>
>>> <mailto: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>>
>>> >
<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>>
<mailto: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>
>>> <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>>
<mailto: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>
>>> <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>
>>> <https://www.ietf.org/mailman/__listinfo/oauth
<https://www.ietf.org/mailman/listinfo/oauth>>
>>>
>>> _________________________________________________
>>> 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
<https://www.ietf.org/mailman/listinfo/oauth>
--
;; takamixhi saito
_______________________________________________
OAuth mailing list
OAuth@ietf.org
https://www.ietf.org/mailman/listinfo/oauth
