Categories

[Little Brosers] New levels of exhaustion

Hello, I guess this might be one of the last post from me, if not the last. I am very tired and I have a lot of things to do before next week so I will keep it short. Here is what I’ve done this week:

 

Android GUI

 

A dedicated a few days to build a basic GUI for our Android messaging app. Nothing really fancy was done, but I do think what I have done will be decent enough for what we want. I used the base template which I adapted using Fragments. The UI is functional so unless I have some extra time before the end the only work done on it will be connecting it semantically to the rest of the application. It took more time than I anticipated because I had actually never done any Android before unless really really basic stuff, so I had to learn on the fly.

 

Merkle tree debugging and modifications

 

I worked on a modification of the core lib code of Antony, for it not to rely on pointers so much. This way, the merkle tree and the slot pool can be serialized either in a file (on Android native) or in the external flash (on the drop). It took a lot of time, but the tree and the slot pool can successfully be saved and restored in a file. We still need to do it for the external flash.

 

Signature Keystore

 

I had terrible flashbacks when the signature started to fail with Android KeyStore generated key pairs. I thought about the week and a half I lost in december on the RSA key generation. Fortunately, after removing a priority given to the SpongyCastle provider, everything worked.

 

Merkle tree diff implementation

 

I helped Antony write the C implementation of the merkle tree conparison. We are still looking for some pesky bugs, this will be priority number one for now since we absolutely need a working diff in C for the project to succeed. I really hope it will be done before tomorrow night because we still have to manage the proper implementations on both platform and connect the sotrage to the rest of the app.

 

I’m off to sleep now, dreaming about trees.

Guillaume

[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.

[Little Brosers] Exploring the GATT

This week, I have continued my exploration of the SDK and the softdevice. The reason I was not able to register a custom service last week has been found quite quickly: there was a variable in the config file of the SDK/softdevice which held the maximum number of vendor specific GATT service allowed. Running into this problem has made me correctly set up the debugging through RTT, and saved me a lot of headaches for the next obstacle. Once the variable for the maximum number of vendor specific GATT services was correctly set, the softdevice needed more space in memory. Thanks to the debugging messages, we were able to quickly identify the problem and modify the linker script to give more memory to the soft device. Without the precise debugging messages I wonder how much time I would have spent scratching my head trying to explain the crashes of the board.

 

The next thing I did was refactoring the monolithic main.c given as a template by the Nordic SDK to coherent small files. While quite simple in appearance, I have actually spent an entire afternoon doing it, figuring out the correct headers to include from the SDK, and having to change the structure in some cases. Since some definition macro from the SDK declared variables as static, but these variables were needed across multiple files. However this was not wasted time, as it made me more comfortable with the SDK.

 

The remainder of the week has been dedicated to adding characteristics to the GATT service, playing around with read and write rights, and then setting up a timer to transfer the temperature of the CPU automatically through a notify characteristic. This is almost done, and should be finished by tomorrow afternoon.

 

Next week, I want to focus on helping Antony writing the C implementation of our Merkle tree comparison protocol, and I also want to work on the bluetooth side of the Android app, expanding on Chris’s work. I also have some catch-up to do on the server code from Xavier that I have already started.

 

Cheers,

Guillaume

[Little Brosers] Getting to know the nordic SDK

C/Android integration

Since we arrived at a satisfying protocol for the Merkle tree part of the project, it was time to start thinking about its implementation. The first thing I have done this week is make sure we are able to integrate some C code into our Android application. That way, we can write the tree comparison implementation in a C library that we import in the app and we will not lose any time. It was quite straightforward, and despite some missing libraries on my fresh arch install I did not run into serious problems. What is done for now is a simple hello world, where one function acts as the interface using the JNI (Java Native Interface) and call a pure C function defined in a different file which returns a “hello world” c string. The JNI interface function gives this string as a Java string which is then displayed in the MainActivity view. Nothing fancy, but enough to be serene about our ability to integrate C code to our application. However I’m not particularly excited to dive into the JNI syntax for more complex interactions given the difficulty to find concise information about it.

Here is a preview of what it looks like:

JNIEXPORT jstring

JNICALL
Java_com_littlebrosers_drops_littlebrosers_MainActivity_helloWorld(JNIEnv *env, jobject this) {
  char *str = hello();
  return (*env)->NewStringUTF(env, str);
}

Not really sexy. Once that was done, we also had to build a new docker image for our CI since the rose one did not have the NDK (Native Development Kit) installed and it is necessary for compiling C code for Android. Fortunately that was done pretty quickly despite none of us being familiar with docker.

Playing around with the nRF-devkit

After that, I got to play around with the devkit and start to understand the Nordic SDK. Despite being a bit lost at first, I am starting to get the hang of it. Everything bluetooth related is hidden behind Nordic proprietary software called a softdevice, which we can only interact with through an API. That was a bit frustrating at first, but the Nordic tutorials are quite well made, and by going through the examples and learning to read their documentation, I am starting to understand how we are supposed to use the SDK. This is however still a work in progress. I understood how to modify the advertising data, but I am still struggling to add a custom service to the GATT, since the tutorials are made with an older version of the SDK than the one we use. I am currently trying to adapt the nordic services code given in examples to create a custom service, but this is taking time since I do not want to blindly copy anything. This time investment is worth it though, as I will be able to help the other members of the group when they will start to look into it.

That’s what my week has been about. I hope that either tonight or early next week I will be able to register a custom service for the GATT, so that I can continue by adding characteristics to it. Once the BLE technical part is done, we will be able to focus on implementing the Merkle tree comparison protocol in C and interface it with Android on one side, and the Nordic SDK on the other.

Cheers,

Guillaume

[Little Brosers] The tree comparison protocol

This week I am going to describe the tree comparison protocol that the drops will be using with the smartphones to determine which message is missing to each device.

 

As mentioned in one of my previous posts, the general idea is that each device has a local stack of operations to keep track of what is the next step. In each element of the stack, there are three informations:

  • The type of the operation: either transmission or reception
  • The type of the transmission (only useful for transmissions)
  • The node of the Merkle tree associated with the operation, which we will call the associated node

 

Here are the three different types of transmissions and their meanings:

  • C, for children: “The hash you sent me is not equal to the one I have, here are the hashes of the children”
  • E, for equal: “The hash you sent me is equal to the one I have, we are stopping here for this subtree”
  • B, for bucket: “The hash you sent me is not equal to the one I have but we are at the end of the subtree (bucket of message) so here are the UUIDs of the messages I have in this bucket”

 

The type of the message will obviously define what the payload contains. After an initialization where one device sends its root hash to the other, we enter the standard behaviour of the protocol which goes as follow:

 

While the device’s stack of operation is not empty, we pop the first operation and look at its type.

 

Transmission:

If the operation is a transmission, we look at the type and build the message payload:

  • C: The hashes of the children of the associated node, add a reception associated with each child to the stack
  • E: Empty payload
  • B: The UUIDs of the messages in the bucket of the associated node

 

Once the payload is formed, the transmission is sent to the other device

 

Reception:

If the operation is a reception, the device waits for the other device to send a message, then looks at its type and payload

  • C: Compares the hashes of the payload with the hashes of the children of the associated node. For each child, if the hash is equal add a transmission of type E associated with the child. If the hash is not equal, add a transmission associated with the child of type C (if the child is not a leaf) or of type B (if the child is a leaf)
  • E: Do nothing
  • B: Compare the UUIDs of the payload with the UUIDs of the bucket of the associated node. Detect which messages the device will have to send, and which messages the device will have to request.

 

This is what the python script simulates and the results have been pretty good so far, so we are pretty happy with that.

 

Next up is something quite different, I am going to catch up on the group’s work on Android and try to make the nrf52832 devkit dialog with the application. I also started to get myself into the Nordic SDK but this has proven to be quite difficult for now since there are a lot of librairies which are often not that great documented. Luckily there are a lot of examples si I am not completely lost.

 

Thank you for reading and see you next week !

Cheers,

Guillaume

[Little Brosers] Python script and CI

Hello there, this is Guillaume from the Little Brosers for my weekly post. This one is a little late because I am in Vienna since Friday and I could not find some time to write it down.

 

I have done two major things this week. First is finishing the python script started last week. It now generates a random pool of messages, simulates two devices taking random messages from this pool, build each device’s Merkle tree, and then simulates the tree comparison protocol. The result of this protocol is the listing of messages from the device and messages the device has to send. All my tests have been successful: each device identified correctly what message it is missing and what message it has to send, so it has been a relief.

 

I have not yet done extensive study of the number of transmission to find the most effective tree structure, but I most likely come to that later.

 

The second thing I have done this week is set up the CI with my group. We organized it in five stages:

  • Checking software version on the docker image
  • Linting of our code
  • Compilation
  • Semantic tests
  • Deployment

We have not yet written propoer semantic tests but it is going to come alongside our code for the project.

 

We also received the development kits from nordic, si I started working on it a little bit. Unfortunately, I am going to be quite busy this week so I am not sure how much I will be able to accomplish. For the moment I managed ot connect to the board through a gdb server. Nect will be making a led blink, and using the UART, then we’ll be ready to roll and start to implement our code.

 

I am looking forward to come back to Paris since there is a very active period ahead of us now that we can start the actual work to implement our ideas. I hope I will be able to start properly working on the dev board before I come back.

 

That’s all for now, thank you for reading.

Cheers,

Guillaume

[Little Brosers] Still working on the trees

Hello everyone this is Guillaume from the Little Brosers.

 

This week I’ve mostly continued last week’s work imagining the process of Merkle tree comparison.

 

The major progress has been figuring out the idea I think we are going to use behind the whole procedure. The difficulty is that there are two trees, on two devices that communicate via bluetooth, and we want to minimize the amount of transmission. The main idea is to go through the tree in a simili-depth first search. The first device sends its root hash, and if it is not equal, the second device sends the hash of its children. To keep track of the dialog progress, each device will have a local stack of operations representing whether he has to send or receive next and what he is supposed to send or to wait for. This is still a work in progress so I will not go into details.

 

To help us planning the key values of the tree we started working on a small python script to simulate a pool of random messages, put them randomly on two devices, build their trees. Next in line is implementing the protocol itself inside the script. Then we will be able to run quick simulations and keep track of the number of transmission needed to resolve the Merkle tree comparison.

 

This is mostly what my next week will be. I will also be reading resources on how to correctly set up CI for a project, and start to implement the solutions before we start pumping out code ! One thing I would also want to implement this week is a way to clone our wiki to a public location (most likely a github repo). Our project needs a lot of theoretical work, and the result of the work we’ve already done and the work to come is in the wiki, and making it available would be the easiest way to share our work.

 

That’s all for this week, thank you for reading.

Guillaume

[Little-Brosers] Merkle trees

Hello everyone, this is Guillaume from the Little Brosers group.

 

We started this week working collectively by trying to estimate the key numbers of our project like memory size of our data, average and peak consumption, the rates needed at various interfaces… I’m not going to lie, this was a bit puzzling since we have a huge chunk of theoretical work to do before being able to correctly evaluate these things. However, the fact that we tried meant that even though our evaluations have turned out to be mostly approximations, our vision of the projects greatly advanced. We were able to take the decisions concerning the cryptographic algorithms we are going to use, our preliminary message structure, and I then started the works on the Merkle tree.

 

The Merkle tree structure will define how a drop and a phone can efficiently identify the messages they are missing from each other.

For those not familiar with it, a Merkle tree is something quite simple yet efficient used for example in P2P protocols to easily identify which data chunk is missing from users. The way it works is the following: each leaf represents a data chunk hashed using one’s favorite hash function. Then, each node is built by hashing concatenation of the children’s hashes. Two parties can then quickly identify what piece of information they have in common and what piece of information differs by comparing their Merkle tree. The comparison stars by the root, and if it is different, the children of the root are then compared etc… The comparison of a branch stops when you find two equal hashes or you reach the leaf, identifying a data block you’re missing.

 

Most classical examples of Merkle trees are binary trees, however in our case the tree will be n-ary, where n will be defined by the max number of hashes we can send over bluetooth in a single message, for energy efficiency purposes. The hash are most likely going to be md5, therefore 16 bytes long. The values we found for the max bluetooth payload in 4.2 are around 200 bytes, however we do not know how our payload will be when we really get our hands on the actual PCB. While we are still looking into bluetooth specs to determine which n we are going to use, i took 4 as reasonable example to start working on it while the rest of the group can continue their research.

 

One of the challenges was that we want to build our Merkle tree around chronological ordering of messages, where each node represents a time frame. However, our system will most likely not even keep track of time since it would be a waste of energy. What we decided to do was to implement a certificate signed by the server and delivered daily to all users, most likely at the same time everyday, certifying the current time. When a user encounters a drop during handshake there will be a phase where each party agrees on what time is “now” and recalculate its Merkle tree if needed. That way, a drop will at most have to recalculate their Merkle tree once every 24 hours + every time they receive new messages.

 

Since the agreement of what is considered “now” is the only agreement between the two parties before comparing trees, the next challenge was to think of the actual Merkle tree model to be used. I will skip on the details since the model is still prone to change in the next few days, but hopefully my next week post will be done once the tree structure and comparison protocol is formalised. I will then explain the choices made and think worst case scenarios.

That is what my next week will be: formally put on paper what I am currently thinking the Merkle tree comparison process will be, as well as update the first draft of the Merkle tree model. Once it is done, I will try to formally prove that the algorithm does the work, and try to look into worst case scenarios to ensure the process will still be reasonable in unusual cases.

 

For the moment, here is the draft of how a Merkle tree will be built. The is a small mistake in the placement of Message 14. The +6/+12 node should not have been subdivided since there is only one message inside. Message 14 should have been put directly inside the node. The formal rules will be available on our wiki most likely during next week (I do not know if the readers outside of Telecom have acess to it though, if not and some people are interested we will find another solution).

 

 

Thanks for reading, cheers, and see you next week,

Guillaume

Little-Brosers Week 2: Walking into the unknown

Hello, this is the Little Brosers group. This will be the only post from our group this week as we have all worked collectively on the same subjects until now.

 

As you may have heard from other groups, the focus of this week was establishing PSSCs (Project Specific Success Criteria), cutting the big project into small digest pieces, and putting deadlines on them. We now have a better view of the road ahead of us, and it was both exciting and a little scary to quantify the amount of work this project will represent for the four of us.

 

We decide to class our PSSCs into four categories:

 

  • Algorithmic category, whose aim is to define precisely the protocol followed when a smartphone encounters a drop. The big steps are going to be the “handshake” and authentication, determining which message is missing to each entity, and finally the transfer of said messages.
  • Hardware dependant category, which regroups everything relating the PCB directly: schematics, test of each component, software closely related to hardware (OTA firmware update for example) …
  • Back-end category, which obviously concerns the main server which will act as our certification authority for users, our main tool to synchronize the dates of the drops and prevent a maximum amount of date cheating from users with malicious intents, and finally as a “main drop” connected to the internet to help synchronize messages.
  • App category, which is very important even though it is not the main focus of the project. These PSSCs will help ensure we do not forget to work on the specific aspects of a smartphone app while we are all very busy thinking about the rest.

 

Here is a link to the wiki of our repo, where you will find the exhaustive and up to date list of our PSSCs, which are obviously going to change in the next few days as we apply the feedback we’ve received after presenting them. You will also find a link to the presentation we gave on friday.

https://gitlab.telecom-paristech.fr/ROSE/2018/Little-Brosers/wikis/home

 

Next week, a few tasks await us. First, precising the theoric aspect of the exchange protocol between the drop and the smartphone. We are going to look for resources about hashing, Merkle trees and symmetrical/asymmetrical cryptography, and try to put on paper a first “pseudo-code” version of our protocol. Second, we are also going to have to put numbers on our needs for the project PCB, to further narrow down the component selection. In our case, we will have to find ways to discriminate the various BLE chips that we have spotted, as well as decide on what external flash we want. And last but not least, as mentioned earlier, we are also going to update the PSSCs to add a few things we have forgotten and correct a few mistakes in the planning.

 

Thank you all for reading, and see you next week !

The Little Brosers team