An algorithm for offline electronic rental door lock
Post
Cancel

# An algorithm for offline electronic rental door lock

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:

1 2 3 4 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:

1 2 3 4 5 6 7 8 9 10 11 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:

$\text{pin} = \text{pin_raw_short} \cdot 61 + \text{d_range} \\\\ \text{pin} \in [0, 10^8-1] \\\\ \text{d_range} \in [1, 60]$

In order to fulfill the length constraint on PIN, we may define pin_raw_short as:

1 2 # 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 $$1639343 \cdot 61 + 60 = 99999922 < 10^8 - 1$$. For each PIN code generate this way, it’s possible to extract d_range parameter using equation:

1 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?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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:

1 2 3 4 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”.

# Summary: Security-point-of-view

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 $$\mathbb{P}(A) = \frac{61}{1639344} \approx 3.721 \cdot 10^{-5}$$.

Classical brute-force attack would be $$\mathbb{P}(B) = \frac{\frac{60 \cdot 61}{2}}{10^8} = \frac{1829}{100000000} = 1.829 \cdot 10^{-5}$$, because there are $$10^8$$ possible PINs and for a given date we have $$2 + 3 + ... + 61 = 1829$$ 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 value.

# Summary: Hardware-point-of-view

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.