[Little Brosers] Merkle Trees on Android

Hello everyone, this is going to be a long post since I have not posted in a while. I have been postponing in for to long now so let’s go, here is a summary of what I have done in the past weeks.


The joy of security libraries in Java/Android


What was done up to that point in the Android app in terms of encrypting messages was generating a random RSA key pair on startup and use it to encrypt/decrypt an arbitrary piece of data. While that was good enough at first, we obviously had to store that key pair. That’s when I decided to look at the Android Keystore. This is manipulated just like a Java keystore (a file to store secrets), but the access is provided and controlled the Android OS. The Android Keystore is the easiest and most secure way to store our RSA key pair. Quite quickly I found a way to generate a keypair in the Android Keystore, but for a reason that is still completely obscure to me, I could not decrypt data encrypted using this pair. I tried a lot of other things, but after around a week of tweaking, just when I started to lose hope of using the Android Keystore, I got it working thanks to an obscure post on stack overflow indicating that there was a bug in the AndroidKeystore provider and a workaround one was to be used for the type of RSA encoding we were looking for.

Overall the solution was working, but so much time was lost on this thing. That was also my first experience manipulating security libraries, and I found the documentation really lacking and most of the examples either not working or deprecated. Overall quite a frustrating experience, but I am glad I got it working.


Android Unit testing and User management


Once that Android Keystore thing was over, I decided to expand Chris’s work on the Message classes to add some User management. The difficulty was to ease the management of multiple networks at the same time in case the project would scale up. Each network is identified by a companyId (company owner of the network) and a networkId. After a lot of back and forth, I settled on a class design where there would be a HashMap of HashMap where companyIds and networkIds would point to a MainUser object. This MainUser represents the owner of the phone, and contains both private and public RSA/ECDSA keys. From this MainUser we can find its ContactUsers on the network indexed by their userIds. Such ContactUsers represent other users of the network, they therefore contain only public RSA/ECDSA keys. The next step was to incorporate it in Chris’s work on Message classes. While it was done I wrote unit tests to ensure the good behavior of all of it, like encrypting then decrypting a message, adding a MainUser to the HashMap, adding a ContactUser to a MainUser, trying to decrypt a message not adressed to us …


Merkle tree implementation


While I was busy with Android, Antony almost finished the Merkle Tree implementation. I reviewed the code, we improved it a bit, and then I looked at how Criterion works. Criterion is a really nice unit test library for C/C++ code. In less than an afternoon, we integrated its usage to our project structure and our CI. I then spent a few days writing tests for the Merkle Tree structure coherence. Thanks to these tests, we eliminated what we hope are the last few bugs in the Merkle Trees. One issue I encountered was that Antony’s code was written in a way where some hardcoding other than preprocessor maros was necessary if we decided to change the number of children per node on the Merkle Tree. While it was originally ok because it affected a single function in the code itself, it was also needed in every single test. Halfway through, we changed some of the code to reduce the hardcoding to a single macro definition, and made the tests and the rest of the code completely independent of the number of children.


Android execution


The last thing I have done was getting the Merkle tree code executed on Android. I spent a whole afternoon getting the code to correctly compile, but I have finally done it. It is now possible to generate the merkle tree on Android and add messages to it. The next step, what I am currently working on, is managing storage on the phone for messages. Indeed, the merkle tree code has a construction we named slot_pool, with a linked list to keep track of the messages, and it was designed with the external flash of the board in mind. What I need to do is find a way to associate an “address” in the C code to an “address” in the Android storage. This is still blurry as I am examining the possibilities. Hopefully it will be done and implemented by monday !


That is all, thank you for reading, and sorry for the huge gap since the last post, the next one won’t be as long I promise.

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>