Few days ago I’ve seen that one company is producing a strange kind of electronic door handles. Such devices could be unlocked by inputting a correct PIN code using a classical 10-digit keyboard. The solution is mainly suited for short-term apartment rentals in order to address the problem of key delivery - such rental company usually has from a few to several dozen of houses spread across the whole city or district. The company has the possibility to generate a PIN code for the customer and such code will only work from the day of arrival till the day of his departure. Moreover: the door handle doesn’t have any database of PIN codes and is not connected to the Internet/3G/WiFi/Bluetooth/anything.
How it can know that the particular PIN code is valid for today without performing an online check? A little bit of cryptography may be helpful here.
Implementation in Python
First, let’s convert regular dates into a single integer. My proposition is to count days since epoch, but it can be arbitrary unique representation:
import datetime def days_since_epoch(date): return (date - datetime.date(1970, 1, 1)).days
Now, we need to design a function
f(secret_key, date_from, date_to) -> pin_code, where
secret_key is some random
string of bytes, which is different for each door handle. Let’s just hash these three arguments together using SHA-1:
import struct import hashlib def make_code(secret_key, date_from, date_to): days_from = days_since_epoch(date_from) days_to = days_since_epoch(date_to) d_range = date_to - date_from packed_dates = struct.pack(">II", days_from, days_to) pin_raw = hashlib.sha1(packed_dates + secret_key).digest()
Now we have to do something in order to shorten the
pin_raw value, because nobody would like to enter such a long PIN
code. I would also like to encode it in such a way, to be able to deduce
d_range value from each PIN code. Let’s
rewrite our PIN code in the following form:
In order to fulfill the length constraint on PIN, we may define pin_raw_short as:
# 2^64 / 1639344 = 1.12525e+13, so we don't introduce a huge bias this way pin_raw_short = struct.unpack('>Q', pin_raw[:8]) % 1639344
This way the maximal value of
pin can be . For each PIN code
generate this way, it’s possible to extract
d_range parameter using equation:
d_range = pin mod 61
This information will be extremely useful in order to accelerate the PIN check process.
Now, how to check if a given PIN code is valid for current date?
def check_code(secret_key, pin): range_len = pin % 61 date_from = datetime.datetime.now().date() date_to = date_from + datetime.timedelta(days=range_len) for _ in range(range_len+1): iter_pin = make_code(secret_key, date_from, date_to) if pin == iter_pin: return True date_from = date_from - datetime.timedelta(days=1) date_to = date_to - datetime.timedelta(days=1) return False
So basically we extract the date range from the PIN code and check for all possible combinations of dates.
For instance, given
range_len = 3 and that the current date is
2017-12-10 the algorithm will check following codes:
make_code(secret_key, datetime.date(2017, 12, 10), datetime.date(2017, 12, 13)) make_code(secret_key, datetime.date(2017, 12, 9), datetime.date(2017, 12, 12)) make_code(secret_key, datetime.date(2017, 12, 8), datetime.date(2017, 12, 11)) make_code(secret_key, datetime.date(2017, 12, 7), datetime.date(2017, 12, 10))
If any of them will match the PIN code entered by the user, we will let him in.
Be aware that if
current_date == date_from or
current_date == date_to, we have to introduce some additional time constraints. E.g. “on the day of arrival, guest may only enter after 2 pm”.
I’m pretty not sure if there aren’t any flaws. Knowing the structure of the code, we would have to find at least one
valid PIN, where there are at most 61 valid PINs at the same time (for
d_range = 60). The
pin_raw_short may have
up to 1639344 different values, so the probability of correct guess is
Classical brute-force attack would be , because there are possible PINs and for a given date we have valid PINs at the same time.
Knowing few codes we could also try to brute-force
secret_key, but it would be quite hard to crack 16 byte random
Computing SHA-1 multiple times could be expensive on platforms like 8-bit AVR. For
d_range = 60 we would need to compute SHA-1 61 times in order to determine whether somebody is permitted to access or not. I’ve tested in practice that using SHA-1 hash implementation provided by AVR-Crypto-Lib it is possible to achieve 186 Hash/second rate for single block hashes on Atmega328@16MHz. This is quite okay, since theoretically we are able to check any PIN code within half of a second (don’t forget that we also perform some other operations than plain hashing).
PS. Later on I’ve realized that it’s better to replace SHA-1 with some faster MAC algorithm like SipHash. It will work much faster on a microprocessor and the output is only 8 bytes, so it’s possible to perform modulo natively without prior truncation.