Code and Life

Programming, electronics and other cool tech stuff

Supported by

Supported by Picotech

Creating arbitrarily hard PBKDF2 keys with Bitcoin inspired difficulty factor

In recent years, the use of graphics processing units (GPUs) has led to the adoption of methods like PBKDF2 (Password-Based Key Derivation Function 2) for secure password storage. PBKDF2 is a key derivation function that is designed to be computationally expensive in order to slow down dictionary attacks and other brute force attacks on passwords. With the increase in processing power that GPUs provide, PBKDF2 has become a popular choice for password storage.

As the development of processing power continues to advance, it has become necessary to increase the number of iterations used in PBKDF2 in order to maintain a high level of security. With more iterations, it becomes even more difficult for an attacker to crack a password using brute force methods.

Recently, I had an idea. What if it were possible to run PBKDF2 arbitrarily long and print out points that match certain criteria? This could potentially provide an even higher level of security for password storage, as the number of iterations could be increased to levels that would make brute force attacks infeasible. It's an idea worth exploring and I'm excited to see what the future holds for PBKDF2 and other password security measures.

Bitcoin difficulty

One of the key features of the Bitcoin network is its use of difficulty to scale the hardness of block signing based on the number of computers that are currently mining. In other words, as more computers join the network and begin trying to solve the cryptographic puzzles required to add new blocks to the blockchain, the difficulty of these puzzles increases in order to maintain a consistent rate of block creation. This ensures that the network remains secure and resistant to attacks, even as the number of miners grows over time.

The basic idea behind this technique is fairly simple: by requiring that a certain number of zeros be added to the block hash, the complexity of the puzzle increases in powers of two. Every hash is essentially random, and modifying the hashed data by the tiniest bit results in a new hash. Every other hash ends in zero, and every other in one. With two zero bits, it's every 4th. To zero a full byte (8 bits) you already need 256 (2^8) tries. With three bytes, it's already close to 17 million.

Printing out PBKDF2 steps at deterministic points

Combining the two ideas is one way to deterministically create encryption keys of increasing difficulty:

  1. Start running PBKDF2 algorithm
  2. Once you have intermediate result U with 1 trailing zero byte, print out the key T
  3. Continue to run, next searching for U with 2 trailing zero bytes etc.

Modifying my previous PBKDF2 pseudo code, here's an example. As full byte zeroes get super hard very fast, I've chosen to print "as good as previous" solutions as well:

import hashlib

sha256 = lambda b: hashlib.sha256(b).digest()

def gethmac(key, content):
    ok, ik = (bytes(v ^ p for v in key.ljust(64, b'\0')) for p in (0x5c, 0x36))
    return sha256(ok + sha256(ik + content))

password = input('Enter password: ').encode()
salt = b'salt'

best = 0

U, T = salt+b'\x00\x00\x00\x01', bytes(64)
for it in range(iter):
    U = gethmac(pwd, U)
    T = bytes(a^b for a,b in zip(U,T))
    zeroes = 32 - len(U.rstrip(b'\0'))
    if zeroes >= best:
        print(f'{it}: {zeroes} zeroes ({U.hex()}), key {T.hex()}')
        best = zeroes

What is it good for?

You could use this for example to generate a local encryption key: Let the user enter a password, and run the algorithm until user runs out of patience, then use the last found key. If later the local key is lost, you can with same time find the correct encryption key (without trying all e.g. 10 million iterations).

Note: I am not a crypto expert, and this is more of a fun and educational thought exercise. You should probably not base a real world solution on this. :)