Categories

DFU

This week, I worked on the DFU (or Device firmware update) over BLE. I succeeded in doing a dfu with our firmware, now I need to automatise it.

How it works

To make a DFU, we need another application called the DFU bootloader, it does this:

  • Check if a valid app is present (it will check a crc32 checksum)
  • If it’s the case it will run it, unless someone is pressing on button 4 (of course we will change it)
  • If there is no valid app or someone is pressing on button 4, the bootloader will enter dfu mode and wait for a dfu signed packet (there is a public key somewhere in the bootloader code)
  • If nobody is doing a DFU, and there was a valid application, it will run it after a timeout
  • If someone is doing a DFU, it will write the new code to the flash, check the content, and run it.

So the steps to make it work are:

  • Compile the bootloader and flash it
  • Compile the firmware
  • Create a zip packet with nrfutil : nrfutil pkg generate –application _build/nrf52832_xxaa.bin app.zip –debug-mode –hw-version 52 –sd-req 0xFFFE –key-file bootloader/key
  • Send it to your phone, and start nrf connect, launch the dfu

The dfu took 30 seconds (our app is not stripped, so it should be 15 seconds actually),

The softdevice update took 1 min 30.

Now I need to make the CI create the zip package, with a good private key handling, and see how we will work locally (on our laptops) with it.

[Little Brosers] From Python to C

Soooooo… No joke this week, I’m almost gonna write an essai this time.

 

First step: Allocating memory for our Merkle tree

So, the first issue about implementing our Merkle tree structure using C is memory allocation.

A simple way would be to use recursive build function for each node and malloc() each of them. But, let’s remember that we will use this code on an embedded system. Dynamic allocation is not allowed.

So the first struggle was to find out how to staticaly allocate the space needed for our Merkle tree.

 

First I need to refresh your memory. Our Merkle tree is 4-ary balanced-ish. That is to say, each child of a node represents the time frame of the node divided by four. But this balanced time distribution rule is broken for the 4 first children of the tree, a.k.a. the root’s children. Those nodes have a an arbitrary part of the root’s time frame. This choice has been made because we think a lot of messages will be recent. Thus, the very last 24 hours will be more likely to contain messages than the last week.

To know when do we stop to split a node’s time frame, we have a constant in the code called BUCKET_SIZE. It gives the minimum time frame a node can represent. Thus, in this case, if the time frame width of a node divided by the number of children (4 here) is greater than BUCKET_SIZE, we split it. Otherwise, this node becomes a leaf.

Here is a basic representation:

So how do we statically allocate such a structure?

Several solutions were examined and to be short, the chosen one is the magic “python generated C header”.

In other terms, a python script included in our Makefile is called whenever the file containing our Merkle tree’s constants is modified and re-write a second header which only contains the size of our sub trees. This way we only have to include this generated header in our merkle_tree.c file and we know at compilation time the size needed for each subtree.

Oh and the sub trees are stored in C arrays.

 

Second step: Building the Merkle tree

Ok, now we know we have all the memory pre-allocated. The thing is…. we only have four dumb arrays. We need to turn this into a tree structure.

See below, we have 4 arrays of ‘node’ C structs and one node C stuct:

The sub trees are stored in their array in a Breadth First Search manner. The sizes of the arrays have been “#define” declared by the python script in a header.

The image above is a simplified representation of the sub trees and arrows are missing. Actually, There is also pointers to parent node.The job in this part has been to make sure each node C struct of the arrays is filled correctly and that each of its pointers is set.

For the curious ones, here is the content of a node C struct (for now):

struct node_t {
    uint64_t start;
    uint64_t end;
    uint32_t child_width;
    node_t *p_parent;
    node_t *p_children[LB_MT_NB_CHILDREN];
    uint16_t depth;
    uint16_t child_id;
    uint16_t array_id;

    slot_t *p_slots;
    uint8_t p_hash[SHA256_BLOCK_SIZE];
};

 

 

Third step: Attaching messages to leafs

We have now a Merkle tree structure we can explore without knowing it’s an array and just using the provided pointers in each node.

The next step is to find out which message has to be attached to which leaf. Also, the actual messages will be stored in external flash so we can’t “put” the message in the leaf structure. We will instead use structures called ‘slot’. Each slot can only correspond to one message and will have an integer which will correspond to the address of its message in the external flash. The only thing we will copy from the message is its time stamp, for convenience. This is what it looks like :

struct slot_t {
    slot_t *p_previous;
    slot_t *p_next;
    uint32_t msg_addr;
    uint32_t timestamp;
};

So each leaf will be able to have what we call a bucket, a.k.a. a linked list of slot_t C structs.

By the way, the slots are stored in a global array of slot_t. The array’s size is the max number of messages we can store in the external flash. We also have three global variables in the program of type slot_t* named begin_busyend_busy and begin_free. We will see that our array of slots can be seen as a pool of slots.

At startup, none of slots are used. Thus, we will attach the slots all together. Then will assign begin_free to the first slot of the array. Making begin_free the head of a linked list of ready-to-use slots.

During the tree building process, a slot will be detached from this linked list each time a message is being attached to a leaf’s bucket. The begin_busy and end_busy pointers will be set latter.

At the end of this process, each message will be attached to its slot. This slot will be placed in a leaf’s bucket following those rules:

  • When there is only one message belonging to a leaf’s time frame, the bucket of this leaf will be of size 1 and will contain this messages’s slot.
  • If several messages with different time stamps all belong to the same leaf, they will be attached to this leaf’s bucket. The bucket’s order will be based on the slots time stamps.
  • Finally, if several messages with the same time stamp all belong to the same leaf, the will be attached to this leaf’s bucket. We will not be able to order them by time stamp since their are equal. We will us their SHA256 instead.

Fourth step: Building our linked list of time-ordered messages

 

So now, we have a Merkle tree with (small) linked lists attached to its leafs. The only thing to do next is to attache all those linked lists together to have a long one. The begining and ending of this long list will be stored in the begin_busy and end_busy pointers. This long linked list will be used to travel across the messages list in an time ordered manner. Being able to doing so will be very useful because it allows us to not order the messages in the external flash.

 

What to do next ?

 

So yeah, it has been quit challenging to find an efficiente way to store and build this Merkle tree in C. I now understand why python is such an easy-to-prototype language.

 

Even if i have a some messages pools for which the tree building process succeed, I know for sure that it is not over yet. I found particular message pool which make crash my building process. So i might spend the following week fixing it.

 

By the way, there is still no automatic test using criterion in my code. I plan on adding some as soon as possible. For now I only use my eyes to read the text-representation of my tree and printf() error reporting in order to detect errors.

 

See you next week !

 

Antony Lopez

[Little Brosers] Who Are You?

Last week I mentioned that I will start working on the authentication part, however, there was a PSSC that needed to be closed fast so I worked on it for the most of the week. It was basically about making the drop able to read a message from a sequence of bytes and verify its signature. This was simple considering I did exactly the same thing in Java before but in a more complex way.

Besides that, I started working on the authentication service. I created a new GATT service and added characteristics associated with the data that will be exchanged. The drop will always request the user’s time certificate, and the certificate with his public key, both signed by our server. After that, it’s a challenge-response mechanism; the user sends a random number to the drop which the latter has to sign (to make sure it’s not a rogue drop), and vice-versa to authenticate the user. After this stage is passed, both parties can start the Merkle tree comparison and the message exchange.

For the moment, the service is up and running, and the characteristics available with the proper read/write permissions. The next step would be to work on the backend of this service, that is the challenge creation, response, and verification as well as the verification of the user and time certificates.

[Little Brosers] Tree best reasons to start working on our C library

Guess what, I spent less time finding this posts’s title joke than last week. I’m getting good at it !

 

Reason one: No-More-Windows

Let’s just say that designing our PCB using Windows 10 on my MacBook Pro (late 2011) was not the best time effective part of ROSE. More seriously, our PCB’s design is now over. I spent some time this week tweaking last details: adding the VIAs all over the board and designing the antenna to SoC track adapting its impedance to get the most out of our tiny little baby 2.4GHz antenna.

Oh and, I forgot to mention the number one killer feature of this board : There will be the following text engraved in it: “Little Brosers ROSE 2018”. Wow. So fancy. Much professional.

Reason two: Winter is coming, the end of ROSE too

My dear fellows know as much as me how reassuring the countdown of this blog’s welcome page is. Or is it?

Regarding our project, we were building tiny parts of the project until now and some start to interact. (mostly Android and nrf52 bluetooth stack for now)

Our merkle tree implementation and the “diff-like” algorithm written in python by Guillaume are functional but need to be translated to some more optimized C code. This is what I started to do this week and what will fill the next ones.

There is some big issues about how we will allocate the memory for the merkle tree and how we will link it to the messages stored in the external flash. For now, we need to validate the diff-like algorithm in order to test it with the bluetooth stack.Thus, we will simply dynamically allocate the merkle tree. This is still a big chunk of work to do. Of course we will switch to a static allocation later in the project.

Reason tree: Credibility

I just needed three elements to make my joke.

See you next week !

Antony Lopez

[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] Messages Done

Last week I was in the middle of finishing the message structure, parsing and encoding, on the Android side in Java. I’m pleased to announce that the mobile app can now properly encrypt and sign a clear text message and transform it into an array of bytes that will be sent over BLE, as well as parse that raw message and transform it back into the clear text message. This means that for the moment my work in the Android part is over.

Besides that, I started working with the Nordic development kit, by trying to understand the examples provided, and how everything works. During that time I also managed to implement our advertising protocol on the devkits, which means that now, they are advertising themselves are proper drops from the Little Brosers network! In a nutshell, I implement the protocol described in one of my previous posts [Little Brosers] Being Heard.

Next Steps

The next step for me would be working on the authentication aspect of our protocol (which will be slightly modified) using a GATT service.

[Little Brosers] Grounded in a tear drop shape

Ok so… Apart from spending 10 minutes to find a joke for this post’s title, I have well progressed on my Little Brosers tasks.

 

As I said in my previous post, this week as been all about PCBs. First some practice on the PCB design software and those 3 last days were dedicated to the drops’s schematic and PCB.

I’m happy to present you the very first version of our drop’s PCB :

 

To be honest, this is not fully ready yet. On tomorrow class I’ll improve the ground plan exclusion to shape it as a “U” letter.

Also I have to add some fixation holes and two targets for the component placing machine.

The round shape is mostly aesthetic. Since our product is called a “dead drop”, it seemed logical to make round.  It also reduces the size of the PCB since our biggest component is the round shaped battery holder. You can’t see it on the preview image but it is basically the same size than the PCB.

 

Cheers

Antony Lopez

[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] Messages

This week I’ve worked extensively on the generation and parsing of messages in the mobile app. While I was planning on getting started with BLE on the devkit, I had to take care of this PSSC first.

Message Structure

The idea is to define a structure for the messages that will be handled in the app, as well as the interface with the raw messages that will be exchanged over BLE. In order to do that I implemented this kind of structure:

Raw message represents a message as a sequence of bytes that are exchanged over BLE. GenericMessage is the Java representation of any message object that has a header, payload and signature. It takes care of going to and from a raw message. After a message is parsed and transformed into a GenericMessage, its type is checked and then an object with the corresponding message type is created and handled by the app. For the moment we only have one type of messages, which is EncryptedTextMessage.

We put time and effort into this one in order to make it as simple as possible to add other message types in the future without having to rewrite the app’s code. A more detailed description is available in our wiki Java message structure.

Crypto

Another big aspect of generating messages is taking care of the cryptographic aspects, which are signature and encryption. I’m working closely with one of my teammates who’s handling the back-end side of our system (server and certificate authority) in order to be able to generate properly encrypted and signed messages as soon as possible.

Little Brosers ID

We also chose our 4-byte Little Brosers ID that will help us identify BLE advertising messages that come from our Drops. I won’t reveal what it is but I’ll only say that it has something to do with initials 😉

 

For Next Week

I plan on having working messages before the end of the week. I’m also hoping to start working on the devkit to implement our protocol over BLE (as described in a previous post).

[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