Thomas Linder Puls: release

2019-03-12T16:13:53Z

release

← Older revision		Revision as of 18:13, 12 March 2019
Line 1:		Line 1:
	~~{{Template:NonReleased}}~~

	The basic problem is that user have a password, which the "system" must be able to validate, but which should be kept secret for '''''everybody''''' else.		The basic problem is that user have a password, which the "system" must be able to validate, but which should be kept secret for '''''everybody''''' else.

Thomas Linder Puls: initial version

2019-02-13T13:08:30Z

initial version

New page

{{Template:NonReleased}}

The basic problem is that user have a password, which the "system" must be able to validate, but which should be kept secret for '''''everybody''''' else.

=== Password Hash ===

The idea is to create a ''cryptographic hash'' of the password and save that in the "user dictionary".

<vip>
class predicates
password_hash : (string Password) -> string Hash.
clauses
password_hash(Password) = cryptography::<someSuitableHashFunction>(Password).
</vip>

To validate the password you hash again and compare the new hash to the stored hash:

<vip>
class predicates
password_validate (string Password, string Hash) determ.
clauses
password_validate(Password, Hash) :-
Hash = password_hash(PassWord).
</vip>

A ''cryptographic hash'' is a hash with the property that it is "hard" to come from the hash value back to the password or to find something else that gives the same hash value.

=== Rainbow table ===

However, this approach has the problem that you can create a so called [[wikipedia:Rainbow table|rainbow table]]: you take a huge amount of ''frequently used passwords'' and hash them with <vp>someSuitableHashFunction</vp> and then it is easy to come backwards for those frequently used passwords.

=== Salt ===

To avoid this you can make sure that the users password is not ''frequently use''. That is done by applying ''salt'' to the users passwords.

If the users password is <vp>"horse"</vp> then you actually hash <vp>"<salt>horse"</vp>, where <salt> is something strange, e.g. <vp>"Qa12#5ASGhorse"</vp> (this is the idea behind salting; in practice it is done in a slightly different way).

<vip>
class predicates
password_hash : (string Password, string Salt) -> string Hash.
clauses
password_hash(Password, Salt) = cryptography::<someSuitableHashFunction>(Hash, Salt).
</vip>

the same <vp>Salt</vp> should be used when validating the password:

<vip>
class predicates
password_validate (string Password, string Salt, string Hash) determ.
clauses
password_validate(Password, Salt, Hash) :-
Hash = password_hash(PassWord, Salt).
</vip>

In principle you can use the same salt each time, but if a hacker gets knowledge about the salt she can make a new rainbow table with that salt, and then we are back to square one.

Subsequently, it is recommended to use a new long random salt '''each''' time. This salt does however not need to be kept secret, but can be saved in the user dictionary
together with the password hash.

Here the combination of hash and salt is called a <vp>hashToken</vp>:

<vip>
domains
hashToken = hashToken(string Salt, string Hash).

class predicates
password_hash : (string Password) -> hashToken HashToken.
clauses
password_hash(Password) = hashToken{Salt, Hash} :-
Salt = generateRandomSalt(),
cryptography::<someSuitableHashFunction>(Hash, Salt).

class predicates
password_validate (string Password, hashToken HashToken) determ.
clauses
password_validate(Password, hashToken(Salt, Hash)) :-
Hash = cryptography::<someSuitableHashFunction>(PassWord, Salt).
</vip>

=== Algorithm ===

The last issue is the choice of <vp>someSuitableHashFunction</vp>. As already mentioned it must be difficult to come from hash to password. A consequence of this is (somewhat oddly) that it must take '''''long time''''' to calculate the hash of a password. Because if it is fast then it is also fast to create rainbow tables and the like. Notice however that the calculation must take long time for the hacker; it does not help that you have a hopeless implementation, if the hacker has a good implementation.

A problem in that context is that what is a suitably slow algorithm today may be too fast in some years.

As a consequence of this and probably also for many other reasons you will have to expect that you will have to change or adjust the algorithm as time passes.

Currently, various places on the net state that '''PBKDF2+SHA1+10.000''' is a good choice.

'''[[wikipedia:PBKDF2|PBKDF2]]''' is an algorithm that takes another algorithm hash <vp>H</vp> argument and makes <vp>N</vp> iterations using <vp>H</vp> in some way.

'''PBKDF2+SHA1+10.000''' means that <vp>H</vp> is the hash algorithm '''SHA1''' that <vp>N</vp> is '''10.000''' (i.e. that the algorithm makes 10.000 iterations).

The number 10.000 is assumed to be increased as computers becomes faster.

All in all, we '''''must''''' expect that we will have to adjust the algorithm as time goes by.

=== Solution ===

[https://jwt.io/ JWT (JSON Web Tokens)] does not deal with this problem, but we have used some of the ideas in this context.

A '''''Hash Token''''' consists of three components:

# A description of the algorithm and its parameters
# the salt
# the hash

Like in JWT the algorithm and its parameters are described as a JSON object:

{ "alg" : "PBKDF2", "hash" : "SHA1", "p2c" : 10000 }

The three components are [[wikipedia:Base64#URL applications|Base64 for URL]] encoded and combined with ".".

So a <vp>HashToken</vp> will look like this (the token does not have any line shifts, they are just inserted here for readability):

eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMjU2IiwicDJjIjoxMDAwMH0
.1xVFoIMO9C-u3O81CYoUxkV3KB_vAxUmMvrvTG9hHaM
.v9cZjPwtji27vjeCFj8SLwzkqWUDe9OmT9YC3sLOMps

# '''eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMjU2IiwicDJjIjoxMDAwMH0''' is the JSON object that describes the algorithm and its arguments (utf8 + base64 URL encoded)
# '''1xVFoIMO9C-u3O81CYoUxkV3KB_vAxUmMvrvTG9hHaM''' is the salt (base64 URL encoded)
# '''v9cZjPwtji27vjeCFj8SLwzkqWUDe9OmT9YC3sLOMps''' is the hash (base64 URL encoded)

The key point is that a <vp>HashToken</vp> contains all the information that is necessary to validate a password, even though you use different algorithms, parameters and random salt.

So a single predicate can validate passwords, even when algorithms and parameters changes, and different algorithms/parameters can also be mixed in a single user dictionary.

<vip>
predicates
password_validate : (string Password, string HashToken) determ.
</vip>

For now PFC supports PBKDF2 and main algorithm:

<vip>
predicates
password_pbkdf2 : (string Password, integer64 IterationCount = 10000, string HashAlgId = bcrypt_sha256_algorithm)
-> string HashToken.
</vip>

The actual hashing is performed by the default cryptography provider on the computer, and it has been validated that SHA1, SHA256, SHA384 and SHA512 can be used as hash algorithm.

=== Example ===

This little example:

<vip>
implement main
open core, stdio, bCrypt_native

clauses
run() :-
Password = "MySweetLittlePony",
FalsePassword = "MySweetLittleCat",
foreach HashAlgId in [bcrypt_sha1_algorithm, bcrypt_sha256_algorithm] do
writef("HashAlgId = %\n", HashAlgId),
test(Password, FalsePassword, HashAlgId),
test(Password, FalsePassword, HashAlgId)
end foreach.

class predicates
test : (string Password, string FalsePassword, string HashAlgId).
clauses
test(Password, FalsePassword, HashAlgId) :-
HashToken = cryptography::password_pbkdf2(Password, :HashAlgId = HashAlgId),
writef("%\n", HashToken),
validate(Password, HashToken),
validate(FalsePassword, HashToken),
nl.

class predicates
validate : (string Password, string HashToken).
clauses
validate(Password, HashToken) :-
Valid = if cryptography::password_validate(Password, HashToken) then "valid" else "invalid" end if,
writef("% is %\n", Password, Valid).

end implement main
</vip>

will produce output like this:

<pre>
HashAlgId = SHA1
eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMSIsInAyYyI6MTAwMDB9.AquRQqikdFLq3S70WbREu5MAqZY.KEbkIURoD_qiylq-TzH013RuW9U
MySweetLittlePony is valid
MySweetLittleCat is invalid

eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMSIsInAyYyI6MTAwMDB9._uLmvdiJWJXfoz15NTicjf4MjLU.7PeEqE9j6k9RF4bmLlLmFxjGaPE
MySweetLittlePony is valid
MySweetLittleCat is invalid

HashAlgId = SHA256
eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMjU2IiwicDJjIjoxMDAwMH0.9qs1jevgKywfXnaxW6rjlrgU1jTNQv8Kf5uAT0bWvzI.fGL9de1MaOImZDnDVSQk7eI0ORajAiDTwKBAt8pbHto
MySweetLittlePony is valid
MySweetLittleCat is invalid

eyJhbGciOiJQQktERjIiLCJoYXNoIjoiU0hBMjU2IiwicDJjIjoxMDAwMH0.skxJNq9rEWdCL88WATlHCMGs6aj4RXucLL0phLv6zNs.hG4xObaK4RnxrF6QX1_dABndhcnel4AuKEp32lqIvg4
MySweetLittlePony is valid
MySweetLittleCat is invalid
</pre>

The output is only "like" this because a random salt is generated each time <vp>password_pbkdf2</vp> is called.

The first part is the same when the algorithm (and parameters) is the same, and the length of the salt and the hash depends on the chosen algorithm.

[[Category:Tutorials|{{PAGENAME}}]]

Password Hashing - Revision history

Thomas Linder Puls: release

Thomas Linder Puls: initial version