PBKDF2 makes passwords harder to crack

[atnbueno]

Hello everyone.

Short version: I've implemented PBKDF2 with AutoHotkey (using MS-CAPI for the HMACs). See the code below.

Longer version:
If you have ever worked with passwords you probably know you never should store them in plain text (or bad things can happen). A more subtle but common mistake is hash them with a common hash function (MD5, SHA-1, SHA-256, ...). The problem is that those functions are designed to be fast, which helps any potential attacker. The function I'm posting here, PBKDF2, is designed to be as slow as we want/need it.

I've used the example of password storing because it's easy to understand and it's a common use of PBKDF2 but, in fact, this function was designed to do something else called key stretching, which is to make cracking a weak password harder. It's used in Wi-Fi (WPA2), in software like TrueCrypt or 1Password, and in services like LastPass. It's built-in in .NET and PHP 5.5, and there are implementations in C, C#, Java, Perl, Python, JavaScript, ...

How to use it? You start with a password (that's the part you keep secret), pick a salt (ideally a random value, but in fact any unique value will do), and the length you want for your strengthened password (how many bytes long, esentially). Then you have to select a level of work to do: this is done selecting a hash function (originally SHA-1 but the code below offers a few additional alternatives) and the number of rounds to apply. More rounds means more time. Waiting almost a second to get the strengthened password is no big deal for the user, but it is for an attacker, who usually works at much higher speeds. A few examples:

• PBKDF2("potato2014", "DECAFC0FFE") This hashes the password and the salt 10000 times using SHA-1 (the default parameters) and outputs a 20-byte hex string (9DF9184E2922B10ABDC74DAACBC3EF004CF66512) in about .4 seconds in my computer. The function accepts either UTF-8-encoded strings or hex strings as password and salt.
• PBKDF2("potato2014", "DECAFC0FFE", 20000) This does the same but hashing 20000 times. The output is A814D2B10F9FAFCDF4603A051BE2F2DF486EE194 and it takes about .7 seconds
• PBKDF2("potato2014", "DECAFC0FFE", 20000, 0, "SHA256") This uses SHA-256, a slower hash. The output is the 32-byte string CE146AC5B2C16E5B3C6AF060A0BB19D40B379465D6CCCFDF9CBB37AF4CCA4C7B and it takes about .9 seconds. If you want another length, replace the zero with it.

Once you have the hex string you can use it as it is, or recode it with base64 or Ascii85 if you want a more compact representation. Another example is the following code that tests the function with the test vectors provided in RFC 6070:

Code: Select all

; AutoHotkey Version: AutoHotkey 1.1
; Language:           English
; Platform:           Win7 SP1
; Author:             Antonio Bueno <user atnbueno at Google's free e-mail service>
; Description:        Test vectors for PBKDF2-HMAC-SHA1 from RFC 6070
; Last Modification:  2014-05-03

#Include pbkdf2.ahk

test(nTest, sPassword, sSalt, nIterations, nLength, sExpected)
{
	t := A_TickCount
	MsgBox, % "Test #" nTest "`n`nOutput  = " PBKDF2(sPassword, sSalt, nIterations, nLength) "`n(Expected " sExpected ")`nTime ellapsed: " (A_TickCount - t) " ms"
}

; Test vectors from RFC 6070
test(1, "password", "salt", 1, 20, "0C60C80F961F0E71F3A9B524AF6012062FE037A6")
test(2, "password", "salt", 2, 20, "EA6C014DC72D6F8CCD1ED92ACE1D41F0D8DE8957")
test(3, "password", "salt", 4096, 20, "4B007901B765489ABEAD49D926F721D065A429C1")
MsgBox, 36, , % "Test #4 consist of millions of iterations and will take several minutes. Do you want to skip it?"
IfMsgBox No
	test(4, "password", "salt", 16777216, 20, "EEFE3D61CD4DA4E4E9945B3D6BA2158C2634E984")
test(5, "passwordPASSWORDpassword", "saltSALTsaltSALTsaltSALTsaltSALTsalt", 4096, 25, "3D2EEC4FE41C849B80C8D83662C0E44A8B291A964CF2F07038")
; 7061737300776F7264 = "pass\0word", 7361006C74 = "sa\0lt"
test(6, "7061737300776F7264", "7361006C74", 4096, 16, "56FA6AA75548099DCC37D7F03425E0C3")

The Code
The code below consists of a pair of functions: PBKDF2, used in the examples above, and RawPBKDF2, which is the one that actually does the job, but that works with binary buffers. For regular use you'll probably just need the first one. After these two functions there are three small auxiliary ones.

Code: Select all

; AutoHotkey Version: AutoHotkey 1.1
; Language:           English
; Platform:           Win7 SP1
; Author:             Antonio Bueno <user atnbueno at Google's free e-mail service>
; Description:        Implementation of PBKDF2 using MS-CAPI HMACs
; Last Modification:  2014-05-03

; Available hash algorithms and their length in bytes
aHashAlgid := {MD5: 0x8003, SHA1: 0x8004, SHA256: 0x800C, SHA384: 0x800D, SHA512: 0x800E}
aHashLength := {MD5: 16, SHA1: 20, SHA256: 32, SHA384: 48, SHA512: 64}

PBKDF2(sPassword, sSalt, nIterations = 10000, nLength = 0, sAlgo = "SHA1")
; Calculates PBKDF2 for a (password, salt) pair that can be either an UTF-8-encoded string or an hex
; string. Optional parameters are the number of iterations, the output length and the hash algorithm.
; It depends on the functions below (Wide2UTF8, Hex2Bin, RawPBKDF2, and Bin2Hex)
{
	global aHashAlgid, aHashLength
	; Basic error checking
	If (nIterations <= 0)
		Throw "PBKDF2 ERROR: Invalid number of iterations (" nIterations ")"
	If (aHashAlgid[sAlgo] = "")
		Throw "PBKDF2 ERROR: Unknown hash function (" sALgo ")"
	; Prepares parameters for RawPBKDF2
	If (nLength = 0)
		nLength := aHashLength[sAlgo]
	; sPassword and sSalt can be either an UTF-8-encoded string or an hex string
	If (!RegExMatch(sPassword, "i)^([0-9A-F][0-9A-F])+$"))
		nPassword := Wide2UTF8(sPassword, Password)
	else
		nPassword := Hex2Bin(sPassword, Password)
	If (!RegExMatch(sSalt, "i)^([0-9A-F][0-9A-F])+$"))
		nSalt := Wide2UTF8(sSalt, Salt)
	else
		nSalt := Hex2Bin(sSalt, Salt)
	; Calculates PBKDF2
	RawPBKDF2(Password, nPassword, Salt, nSalt, nIterations, Output, nLength, sAlgo)
	; Outputs result in hexadecimal format
	Return Bin2Hex(Output, nLength)
}
RawPBKDF2(ByRef Password, nPassword, ByRef Salt, nSalt, nIterations, ByRef Output, nOutput, sAlgo)
{
	global aHashAlgid, aHashLength
	; MS-CAPI constants used to do HMACs
	CALG_HMAC            := 0x8009
	CALG_RC2             := 0x6602
	CRYPT_IPSEC_HMAC_KEY := 0x0100
	CRYPT_VERIFYCONTEXT  := 0xF0000000
	CUR_BLOB_VERSION     := 0x02
	HP_HASHVAL           := 0x02
	HP_HMAC_INFO         := 0x05
	PLAINTEXTKEYBLOB     := 0x08
	PROV_RSA_FULL        := 0x01
	; Reserves memory for hashing and XORing and storing the final result
	VarSetCapacity(Hash, Ceil(aHashLength[sAlgo] / 8) * 8, 0)
	VarSetCapacity(XORSum, Ceil(aHashLength[sAlgo] / 8) * 8, 0)
	nBlockCount := Ceil(nOutput / aHashLength[sAlgo])
	VarSetCapacity(Output, aHashLength[sAlgo] * nBlockCount, 0)
	; If the output is not longer than the specified hash the following loop does a single iteration
	Loop % nBlockCount
	{
		; The block count must be stored as an INT32_BE (the expression below is OK up to a block count of 255)
		nHash := Hex2Bin(Bin2Hex(Salt, nSalt) "000000" Bin2Hex(Chr(A_Index), 1), Hash)
		VarSetCapacity(HmacInfo, 4 * A_PtrSize, 0) ; HMAC_INFO struct, see http://msdn.com/library/aa382480
		NumPut(aHashAlgid[sAlgo], HmacInfo, 0, "UInt") ; Selects hashing algorithm and default padding
		nKeyBlobSize := 12 + nPassword
		VarSetCapacity(keyBlob, nKeyBlobSize, 0) ; BLOBHEADER struct, see http://msdn.com/library/aa387453
		NumPut(PLAINTEXTKEYBLOB, keyBlob, 0, "Char") ; PLAINTEXTKEYBLOB struct, http://msdn.com/library/jj650836
		NumPut(CUR_BLOB_VERSION, keyBlob, 1, "Char")
		NumPut(CALG_RC2, keyBlob, 4, "UInt")
		NumPut(nPassword, keyBlob, 8, "Char")
		DllCall("RtlMoveMemory", "UInt", &keyBlob + 12, "UInt", &Password, "Int", nPassword) ; see http://msdn.com/library/ff562030
		; See steps at http://msdn.com/library/aa379863 and C++ example at http://msdn.com/library/aa382379
		DllCall("advapi32\CryptAcquireContext", "UIntP", hProv, "UInt", 0, "UInt", 0, "UInt", PROV_RSA_FULL, "UInt", CRYPT_VERIFYCONTEXT)
		DllCall("advapi32\CryptImportKey", "UInt", hProv, "UInt", &keyBlob, "UInt", nKeyBlobSize, "UInt", 0, "UInt", CRYPT_IPSEC_HMAC_KEY, "UIntP", hKey)
		; Iteration zero
		DllCall("advapi32\CryptCreateHash", "UInt", hProv, "UInt", CALG_HMAC, "UInt", hKey, "UInt", 0, "UIntP", hHmacHash)
		DllCall("advapi32\CryptSetHashParam", "UInt", hHmacHash, "UInt", HP_HMAC_INFO, "UInt", &HmacInfo, "UInt", 0)
		DllCall("advapi32\CryptHashData", "UInt", hHmacHash, "UInt", &Hash, "UInt", nHash, "UInt", 0)
		DllCall("advapi32\CryptGetHashParam", "UInt", hHmacHash, "UInt", HP_HASHVAL, "UInt", &XORSum, "UIntP", aHashLength[sAlgo], "UInt", 0)
		DllCall("advapi32\CryptDestroyHash", "UInt", hHmacHash)
		DllCall("RtlMoveMemory", "UInt", &Hash, "UInt", &XORSum, "Int", aHashLength[sAlgo]) ; See http://msdn.com/library/ff562030
		; End of iteration zero
		Loop % nIterations-1
		{
			DllCall("advapi32\CryptCreateHash", "UInt", hProv, "UInt", CALG_HMAC, "UInt", hKey, "UInt", 0, "UIntP", hHmacHash)
			DllCall("advapi32\CryptSetHashParam", "UInt", hHmacHash, "UInt", HP_HMAC_INFO, "UInt", &HmacInfo, "UInt", 0)
			DllCall("advapi32\CryptHashData", "UInt", hHmacHash, "UInt", &Hash, "UInt", aHashLength[sAlgo], "UInt", 0)
			DllCall("advapi32\CryptGetHashParam", "UInt", hHmacHash, "UInt", HP_HASHVAL, "UInt", &Hash, "UIntP", aHashLength[sAlgo], "UInt", 0)
			DllCall("advapi32\CryptDestroyHash", "UInt", hHmacHash)
			; XOR is done in 64-bit (8-byte) blocks (smaller blocks make the XORing significantly slower)
			Loop % Ceil(aHashLength[sAlgo] / 8)
			{
				nOffset := (A_Index - 1) * 8
				NumPut(NumGet(XORSum, nOffset, "Int64") ^ NumGet(Hash, nOffset, "Int64"), &XORSum, nOffset, "Int64")
			}
		}
		DllCall("advapi32\CryptDestroyKey", "UInt", hKey)
		DllCall("advapi32\CryptReleaseContext", "UInt", hProv, "UInt", 0)
		DllCall("RtlMoveMemory", "UInt", &Output+(A_Index-1)*aHashLength[sAlgo], "UInt", &XORSum, "Int", aHashLength[sAlgo])
	}
}
Wide2UTF8(sInput, ByRef Output)
{
	nOutputSize := StrPut(sInput, "UTF-8")
	VarSetCapacity(Output, nOutputSize)
	StrPut(sInput, &Output, nOutputSize, "UTF-8")
	Return nOutputSize-1
}
Bin2Hex(ByRef Input, nInput)
{
	sIntegerFormat := A_FormatInteger
	SetFormat Integer, H
	Loop % nInput
		sOutput .= SubStr(*(&Input + A_Index - 1) + 0x100, -1)
	SetFormat Integer, % sIntegerFormat
	Return sOutput
}
Hex2Bin(sInput, ByRef Output)
{
	VarSetCapacity(Output, StrLen(sInput) // 2)
	Loop % StrLen(sInput) // 2
		NumPut("0x" . SubStr(sInput, 2 * A_Index - 1, 2), Output, A_Index - 1, "Char")
	Return StrLen(sInput) // 2
}

I hope this code is useful to someone. Please let me know if you find any problems or think of improvements.


Regards,
Antonio

[Guest10]

is this to create strong passwords or test their strength?

[atnbueno]

It derives a strong password from a weak one.

The examples above use "potato2014", an extremely weak password. If you do PBKDF2("potato2014", "DECAFC0FFE", 20000, 32, "SHA256") you get the hex string CE146AC5B2C16E5B3C6AF060A0BB19D4 which you can use as password as is. You can recode it, for example, as Base64 to get a shorter and more diverse version: pQgyAKaw7rkafAuZYrKn.

If someone tries to crack that password (usually using dictionary and/or rule-based attacks), and assuming he has all the information needed (except, of course, "potato2014"), he has to do the 20000 rounds with SHA-256 for each and every one of his attempts. That’s quite a lot of work without highly specialized hardware.

More information:
Salted Password Hashing - Doing it Right
Speed Hashing

[ozzii]

I saw just one problem: remember CE146AC5B2C16E5B3C6AF060A0BB19D4 is harder than potato2014.

And type it on a phone, for example, is very long....
On Win OK, you can use the script but on a phone with your every day password for opening lastpass for example it's a PITA.

But I keep it, just in case

[atnbueno]

I personally use KeePass, an open source password manager, because of its flexibility, but at the cost of complexity (at least is more or less cross-platform). It's difficult (if not outright impossible) to find a flexible and simple solution to each and every possible password-related scenario.

Another scenario I've failed to comment is when you need not exactly a password, but a key (it's actually the origin of the function). If you want, for example, to encrypt some information in a script (either to store it or to send it somewhere), don't use potato2014, use CE146AC5B2C16E5B3C6AF060A0BB19D4 (or pQgyAKaw7rkafAuZYrKn). Your script only has to call PBKDF2 with the password you provide and you'll have the key in a moment. Anyone trying to break your encryption, better be patient

As for the remembering, I can only say correct horse battery staple

[ozzii]

Sorry my English is not so good.
So I have a little difficulties to understand how to do.
Can you give me an example of how to do to have back potato2014 when I put in a variable CE146AC5B2C16E5B3C6AF060A0BB19D4

Also I suppose that you have to have the right "salt" for having the right password back, right ?

For a better understanding. Can I use this in a script for not putting inside in a plain text a password for a FTP site ?

[atnbueno]

You can not get potato2014 from the output of this function (nor any other hashing function). Hashing is a one-way transformation. Particularly in cryptographic hashing functions, this is a desired property. This is much better explained that I could do here in the article I linked before.

The "right" salt, as you put it, is needed to get CE146AC5B2C16E5B3C6AF060A0BB19D4 from potato2014, not the other way around.

If you want something reversible you need a cipher, not a hash.

[ozzii]

Thanks for the explanation.

[mviens]

Antonio,

This is very nice and useful. Do you also have AHK code for a good (strong) cipher?

[atnbueno]

Hello Mike.

(sorry I didn't see your message before)

Check jNizM's excellent work with CNG (the succesor to CryptoAPI):
https://autohotkey.com/boards/viewtopic.php?f=6&t=23413

Regards,
Antonio

[mviens]

Thank you very much.