Designing an offline authentication system

I have recently got to know of the igloohome digital lock. It is completely offline and connects to the app via bluetooth only. No internet connection. One of the most puzzling features is that the owner can remotely generate a PIN code, valid for a certain duration, and have it be effective immediately without even connecting to the lock to sync the PIN. I am not the only curious one, enough customers have asked and igloohome has written a post about it. However, the post skips over the technical details and only mentions that all required information is stored in the PIN code.

The engineering challenge is to encrypt a datetime (e.g. 9am 10 Dec 2017) and a duration (10 mins) and encode it in only 8 digits. Hashing is out of the question since the lock needs to be able to access the information in plaintext. An MRT ride later, I managed to come up with a way to do it.

Disclaimer

I do not own any igloohome products. I did not reverse engineer their product. I do not know if they are using a similar method or something totally different. This is how I would do it if I was tasked with such a challenge.

The architecture would be as such. PIN code generation will take place server side. The information will be encoded and encrypted on the server before being sent to the client. Client will share the encrypted PIN code with the guest who will type it into the lock. The hardware in the lock will handle the decryption and decoding. Hence, there is a lower probability of the algorithm being leaked due the reverse engineering of the client.

Encoding

The first problem is the encoding problem. With only 8 digits to play with, epoch time is out of the question. My solution involves using a modified version of epoch time, number of 5 minute block elapsed since Jan 1 2015 UTC. This is how I would encode the information.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    XYYYYYYZ

    X - Type of PIN code 
        0 - permanent PIN code
        1 - one time PIN code
        2 - duration PIN code (10 min)
        3 - duration PIN code (30 min)
        ...
        9 - duration PIN code (1 year)
    Y - Number of 5 minute block elapsed since Jan 1 2015 UTC (6 digits)
    Z - Checksum (modulus 9)

Thus an unencrypted duration PIN code which will work for 3 days from 9am 10 Dec 2017 UTC will look like 23094207. A 6 digit Y value will be able to encode up to 9 years before overflowing, which I believe is a reasonable lifetime for the lock.

Encryption

The next problem is encryption. Without encryption, it would be trivial to reverse engineer the algorithm. Unencrypted PIN code for 9.05am will look like 23094216, 9.15am will look like 23094234. Encryption is tough. AES would not work. Although encrypting a 64 bit input generates a 64 bit output, the output will contain 0x00-0xff which include letters, non printable characters. It may be tempting to cheat and use a simple substitution cipher, replace 2 with 7, 3 with 0 but it adds little to security if the encryption key is reused. I briefly considered storing a few MBs of random digits to be used as a one time pad on the device but such an encryption scheme would require the PIN code to be used in sequence.

What is required in this case is format-preserving encryption. There is not much literature on it out there and would require a decently skilled cryptographer to implement correctly. It would likely be a Feistal structure with a customized S-box for digits only.

I would propose 1 round of polynumeric substitution. Using the previous example, if the unencrypted PIN code is 23094207 and the substitution table below is the key, the encrypted PIN code after substitution will be 07599304. Of course, each lock should have its own unique substitution table generated during production and saved server side.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
                    Substitution
        1   2   3   4   5   6   7   8   9   0
    1   4   0*  1   3   9   2   8   7   5   6
    2   6   2   7*  1   3   9   4   0   5   8
Col 3   0   8   6   3   4   2   1   9   7   5*
No. 4   1   6   4   0   5   8   2   3   9*  7
    5   3   2   6   9*  7   5   8   4   0   1
    6   9   3*  6   2   5   0   1   4   7   8
    7   5   7   4   1   2   3   6   8   9   0*
    8   2   0   1   3   5   6   4*  8   9   7

Additional Notes

I am aware that the unencrypted PIN code need not be digits only. However, my reasoning for insisting on digits only is that it would be easier to encrypt a plaintext into a ciphertext with an equal or larger ciphertext space. If I used other character in the unencrypted PIN code, I will likely have compression issues at the encryption stage.

I have also considered cycling, which is basically AES encrypting multiple rounds until I encounter a ciphertext which is all digit only. Given that the AES can output 255 unique possibilities and there are only 10 digits, it might take quite a while.

There is no point performing multiple rounds of substitution and permutation, unless there are bit level operations, otherwise, it can be simplified into a single substitution table.

The blog post alluded to using time based security tokens to generate a one time password. I could not figure out how it will work out since the PIN codes have to work over a period of time. It is probably just an analogy for the public.