# Time Locked Puzzles and Proof of Work

Jul 29, 2018 · 5 min read

So how might we a lock down a file for a given amount of time or make sure that someone does not get their present until their birthday? Well one way is to get others to do some work, that you know will be done within a certain amount of time. If I know it will take you one hour to cut the grass in your garden, before I give you your reward, I will hope you will not be able to do it quicker than one hour.

## Hashing

This method is defined .

One method is to get the receiver to perform some work to find the encryption key. For example if we wanted to lock it down for one hour we could take a seed value, and then continually hash it for a given amount of time that we thing the recipient would required to generate the same key. This would then generate the same key, if the sender and recipient share the number of iterations of the hash used. We can then tell the receiver the seed value and the number of iterations they must use in order to compute the key, along with the encrypted message. The receiver must then compute the key and prove their work.

The method, though, is not perfect as the cost of the operation will vary with the clock speed of the processor. We will not be able to compute in parallel as the hashing operations must be done one at a time. The other side will still have a cost in the computation. The following is a sample run for a time to compute the key of 0.25 seconds:

`Message:	The quick brown foxKeyseed:	12345Encryption key:		6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=Encrypted value:	gAAAAABbCdAfteG9dAUdmQgqHoY4hby9moK51-qYTRlYXpO7Ghbev6GqDFsadulgmZvgHVUv6mRwE9SRcbF2-UVnDW_KzJs7GHX9ffcZ-btIH-pKP5ubOSE=Decyption key:		6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=Decrypted value:	The quick brown foxKey time (secs):		0.25Iterations:		76109Time to encrypt: 0.724999904633Time to decrypt: 0.219000101089`

And here is some sample code. We use SHA-256 to hash the seed.

`import datetimeimport timeimport hashlibimport base64from cryptography.fernet import Fernetimport sysmessage="hello"keyseed = "12345"timeout=0.5def generate_by_time(seed, delta):    end = time.time() + delta.total_seconds()    h = hashlib.sha256(seed).digest()    iters = 0    while time.time() < end:    	h = hashlib.sha256(h).digest()        iters += 1    return base64.urlsafe_b64encode(h), itersdef generate_by_iters(seed, iters):    h = hashlib.sha256(seed).digest()    for x in xrange(iters):        h = hashlib.sha256(h).digest()    return base64.urlsafe_b64encode(h)def encrypt(keyseed, delta, message):    key, iterations = generate_by_time(keyseed, delta)    encrypted = Fernet(key).encrypt(message)    return iterations, encrypted,keydef decrypt(keyseed, iterations, encrypted):    key = generate_by_iters(keyseed, iterations)    decrypted = Fernet(key).decrypt(encrypted)    return decrypted,keyprint "Message:\t",messageprint "Keyseed:\t",keyseeddelta = datetime.timedelta(seconds=timeout)t1 = time.time()iters, encrypted,key = encrypt(keyseed, delta, message)print "\nEncryption key:\t\t",keyprint "Encrypted value:\t",encryptedt2 = time.time()decrypted,key = decrypt(keyseed, iters, encrypted)t3 = time.time()print "\nDecyption key:\t\t",keyprint "Decrypted value:\t",decryptedprint "\nKey time (secs):\t", timeoutprint "Iterations:\t\t", itersprint "\nTime to encrypt:", t2 - t1print "Time to decrypt:", t3 - t2`

In an extension to this, we could just define the hashed value, and let the receiver work out the number of times a seed value needs to be hashed to get the same value. In this case we search for a hashed version of the key .

## Squaring

This method is defined .

Ron Rivest [] defined a puzzle which was fairly easy to compute [O(log(n))] and more difficult to solve [O(n2)]. For this we create a random value (a) and then raise it to the power of 2^t, and where t is the difficulty level.

The method, as outlined by Rivest [] defines the usage of a squaring process which increases the work to compute the key.

Now let’s say that Bob wants to make sure that Alice cannot open a message within a given amount of time. Initially Bob starts with two prime numbers (p) and (q) and determines (n):

n=p×q

We can also calclate PHI as:

PHI=(p−1)×(q−1)

Next we create an encryption key (K) and with a message (M) we encrypt:

Cm=Encrypt(K,M)

Next we select a random value (a) and a difficulty level (t), and compute a value of b which is added to the key (K):

CK=K+a^2{^t} (mod n)

Bob will then send {n,a,t,CK,Cm} to Alice, and get her to prove her work in order to decrypt the cipher message (Cm).

Alice then takes the values and computes the key with:

Key=CKa^2{^t} (mod n)

and which will have a workload dependent on the difficulty (t).

Bob, though, does not have the same workload at Alice, as he knows some or the original values. For him, he uses PHI to reduce the complexity:

ϵ=2^t (mod PHI)

And then the calculation of the value to find becomes:

b=a^e (mod n)

`Message:	The quick brown foxKeyseed:	12345Key: WZRHGrsBESr8wYFZ9sx0tPURuZgG2lmzyvWpwXPKz8U=Keyval: 40517827634140982427891826463487354397562163067645485726320510288945209855941Bob sends this as the puzzleN:	5808519655638548297258092061418259166774543092617038796300914729783059570485346403807454618287525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071410193718769033138895292899984621735782974450454023113374373918673037042253066818942089671557106505473585751547903422068492120948273678721315120463641764405010804880764577517991306650182004053654755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151394009348523859513336870704003245896134059043428841497988022873465729540129905401323861892790008954081042521197986890397363455472811639a:	101t:	1CK:	40517827634140982427891826463487354397562163067645485726320510288945209866142Encrypted:	gAAAAABbCrlEUvLDQQX6gIiGqA81TTHzm5rD4Y6c4I5X5-qnkhGzqC8lOojkzmmy4cIJ3WXIn9aKO_5P3VY21ScNDf0wtOsTXo93-GbmwF6-_hBtyInh6g8=Alice receives and now computesKey guess= 40517827634140982427891826463487354397562163067645485726320510288945209855941Decrpyted: The quick brown fox`

As an example, using a 3.5GHz Xeon process, we get the following timings to compute the work for Alice (with a=999):

`t=8     0.000999927520752 secondst=16    0.208999872208 secondst=18    2.0 secondst=20    26.7730000019 seconds`

And here is some sample code where we use SHA-256 to hash the seed:

`import datetimeimport timeimport hashlibimport base64from cryptography.fernet import Fernetimport sysfrom base64 import b64decodeimport structimport randommessage="hello"keyseed = "12345"a = random.randint(99999,999999)t= 8def tost(i):  result = []  while i:    result.append(chr(i&0xFF))    i >>= 8  result.reverse()  return ''.join(result)print "Message:\t",messageprint "Keyseed:\t",keyseedp=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979n = p*qPHI = (p-1)*(q-1)h = hashlib.sha256(keyseed).digest()key=base64.urlsafe_b64encode(h)encrypted = Fernet(key).encrypt(message)print "Key:",keykeyval = int(b64decode(key).encode('hex'), 16)print "Keyval:",keyvalCK = ((keyval) + a**(2**t)) % nprint "\n\nBob sends this as the puzzle"print "N:\t",nprint "a:\t",aprint "t:\t",tprint "CK:\t",CKprint "Encrypted:\t",encryptedprint "\n\nAlice receives and now computes"t1 = time.time()Key = (CK - a**(2**t)) % nt2 = time.time()val=tost(Key)Keyguess = base64.urlsafe_b64encode( val)print "\nKey guess (int):",Keyprint "Key guess:",Keyguessdecrypted = Fernet(Keyguess).decrypt(encrypted)print "Decrypted:",decrypted print "Time for Alice to compute:",t2-t1#print "\n\n--------Bob's calculation---------------------"#t1 = time.time()#eps = (2**t) % PHI#b =(a**eps) % n#t2 = time.time()#print "Bob\'s value", b#print "Time for Bob to compute:",t2-t1`

## Conclusions

Proof of work is one way to define a cost limit to those who might want to change something on a system. But, remember, work can be costly.

## ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Written by

## Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

## ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Written by

## Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

## ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

## Protection from Container Malware with Anthos

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface.

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox.

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic.

Get the Medium app