Time Locked Puzzles and Proof of Work

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 fox
Keyseed: 12345
Encryption key: 6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=
Encrypted value: gAAAAABbCdAfteG9dAUdmQgqHoY4hby9moK51-qYTRlYXpO7Ghbev6GqDFsadulgmZvgHVUv6mRwE9SRcbF2-UVnDW_KzJs7GHX9ffcZ-btIH-pKP5ubOSE=
Decyption key: 6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=
Decrypted value: The quick brown fox
Key time (secs): 0.25
Iterations: 76109
Time to encrypt: 0.724999904633
Time to decrypt: 0.219000101089

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

import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
import sys
message="hello"
keyseed = "12345"
timeout=0.5
def 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), iters
def 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,key
def decrypt(keyseed, iterations, encrypted):
key = generate_by_iters(keyseed, iterations)
decrypted = Fernet(key).decrypt(encrypted)
return decrypted,key
print "Message:\t",message
print "Keyseed:\t",keyseed
delta = datetime.timedelta(seconds=timeout)t1 = time.time()
iters, encrypted,key = encrypt(keyseed, delta, message)
print "\nEncryption key:\t\t",key
print "Encrypted value:\t",encrypted
t2 = time.time()
decrypted,key = decrypt(keyseed, iters, encrypted)
t3 = time.time()print "\nDecyption key:\t\t",key
print "Decrypted value:\t",decrypted
print "\nKey time (secs):\t", timeout
print "Iterations:\t\t", iters
print "\nTime to encrypt:", t2 - t1
print "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 fox
Keyseed: 12345
Key: WZRHGrsBESr8wYFZ9sx0tPURuZgG2lmzyvWpwXPKz8U=
Keyval: 40517827634140982427891826463487354397562163067645485726320510288945209855941
Bob sends this as the puzzle
N: 5808519655638548297258092061418259166774543092617038796300914729783059570485346403807454618287525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071410193718769033138895292899984621735782974450454023113374373918673037042253066818942089671557106505473585751547903422068492120948273678721315120463641764405010804880764577517991306650182004053654755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151394009348523859513336870704003245896134059043428841497988022873465729540129905401323861892790008954081042521197986890397363455472811639
a: 101
t: 1
CK: 40517827634140982427891826463487354397562163067645485726320510288945209866142
Encrypted: gAAAAABbCrlEUvLDQQX6gIiGqA81TTHzm5rD4Y6c4I5X5-qnkhGzqC8lOojkzmmy4cIJ3WXIn9aKO_5P3VY21ScNDf0wtOsTXo93-GbmwF6-_hBtyInh6g8=
Alice receives and now computesKey guess= 40517827634140982427891826463487354397562163067645485726320510288945209855941
Decrpyted: 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 seconds
t=16 0.208999872208 seconds
t=18 2.0 seconds
t=20 26.7730000019 seconds

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

import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
import sys
from base64 import b64decode
import struct
import random
message="hello"
keyseed = "12345"
a = random.randint(99999,999999)
t= 8
def tost(i):
result = []
while i:
result.append(chr(i&0xFF))
i >>= 8
result.reverse()
return ''.join(result)
print "Message:\t",message
print "Keyseed:\t",keyseed
p=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541
q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979
n = p*qPHI = (p-1)*(q-1)h = hashlib.sha256(keyseed).digest()
key=base64.urlsafe_b64encode(h)
encrypted = Fernet(key).encrypt(message)
print "Key:",key
keyval = int(b64decode(key).encode('hex'), 16)
print "Keyval:",keyval
CK = ((keyval) + a**(2**t)) % n
print "\n\nBob sends this as the puzzle"
print "N:\t",n
print "a:\t",a
print "t:\t",t
print "CK:\t",CK
print "Encrypted:\t",encrypted
print "\n\nAlice receives and now computes"t1 = time.time()Key = (CK - a**(2**t)) % n
t2 = time.time()
val=tost(Key)
Keyguess = base64.urlsafe_b64encode( val)
print "\nKey guess (int):",Key
print "Key guess:",Keyguess
decrypted = 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…

Prof Bill Buchanan OBE

Written by

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.

Prof Bill Buchanan OBE

Written by

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.

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store