Categories

[Little Brosers] Indeed, dealing with flash is lightning fast

Hello everyone !

 

Don’t ask me how, my brain seems to have enough battery life to keep writing posts here.

Let’s get to it, shall we?

 

First: The flash

Last week I left you with a code very approximative trying to stimulate the flash.

One week later, we fully control it. I just needed more of those sweet full sleeping night (and some ROSE Guru’s advice). After reading even more the datasheet and insulting my computer for no reason, I got it to work as expected. We can now, read/write in a page any amount of data up to a page size (528 bytes). Also, I tested the “super-duper amazing ultra low power mode” of the flash. Just kidding, just note that we are able to put the flash in its deepest power mode and wake it.

 

Second: We gotta make it fit in 64 ko

 

Indeed, our NRF52832 can only provide 64 ko of RAM. This few kilobytes are supposed to hold our Merkle tree and the slots. (c.f. older posts if you don’t know what ‘slots’ refers to). And let’s not forget all the crypto code as well as the RAM that BLE needs.

 

So, with Guillaume, we tried to reduce the size of our structures as much as we could. Choosing space-saving over run-time optimization. For instance, the width of a node’s children can be deduced from its ‘start’ and ‘end’ fields. Same for its depth in the tree. So yes, we reduced the size of our structures by removing as much ‘not so essential” fields as possible (which was previously stored in each node).

Also, we dramatically reduced the size and count of the messages that will be stored in a drop. Being optimistic, I would say that we could fit 1000 messages in a drop. We’ll see. The ideal would be to use a NRF52840 (which has way more RAM), but this SoC was not available to buy when we started the project, and still isn’t, I think.

 

Third: the diff

Ok, the rest of the week was dedicated to the diff. I you forgot what ‘diff’ means in our super fancy vocabulary, it means “comparing two Merkle trees and determining which messages those trees need to send to each other in order to be identical”.

This has been done in python by Guillaume at the beginning of the project. The thing is, he had not the RAM limitation that I encounter now with the Drop’s CPU. So with Guillaume we worked on translating his diff algorithm to C. I Started by implementing in C the stack he was using in python. Saturday, I spent the day connecting the diff code to the C++ simulation. And dude, that’s so satisfying. I can launch as many drops as I want now and ask them to launch a diff with another one. All of this being done in separated threads. Since I use UDP for emulating BLE communication, we can even launch one drop per terminal. It even should work for computers in the same local network.

 

Oh yes, and the best part is, I tried to keep the diff hardware independent. Indeed, at first we thought we would have to code a diff in Java for the Android part in addition of the C one. Mostly because of the difference between Drops and Android phones about BLE, events and interrupts. But since we now master the JNI and the Android NDK , my fellow mates only need to provide two C function pointers, one for sending, one for receiving. Those function need to be blocking, and write to/read from a byte array for which I will provide a size, that’s all. There is also a void* in the function signature, if the language which uses the diff needs to pass something to its send/recv functions. (I do for C++ simulation)

And finally, because unitary testing is always around the corner, we started today testing each part of the diff algorithm with Criterion. The diff is not fully functional yet, but it shouldn’t be long.

 

What’s next…?

Basically everything. I mean, there is only 4 days left. I still need to write code for the merge (not very complicated I think, the diff does all the handwork), the date shift, the flash monitor to know which page of the flash is dead or not and the battery monitor.

 

That is my program for the following days.

 

Have fun guys !

 

Antony

 

[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] The End is Near

Here I am, writing my last post in the logbook. Time passed quickly and right now we’re working around the clock to finish the project before Friday.

As far as I’m concerned, the certificate verification problem that I was stuck on 2 weeks ago was solved a long time ago. The authentication process on the drops is working like a charm, with the drop disconnecting if there is a problem with the user certificate or the challenge response.

On the Android side, I implemented the filters based on the networks we’re active in. Then the results are analysed to tell if we should connect to a drop or not. In addition to that, I have laid out the entire connection process on drop discovery, with stubs for the yet unwritten processes. I’m currently working on finishing the authentication process on the Android side. Challenging a drop and verifying its response, as well as responding to its challenge are working perfectly well. However, given that the user certificate is not yet ready, I’m putting that part on hold for now, and working on communicating with the server to obtain the user certificate on signup.

During last week, while implementing the authentication on Android, I realized that we couldn’t write more than 20 bytes (the default MTU size on the drop) to a characteristic, which was problematic given that we have much larger characteristics, like the challenge/response and the certificate. I solved this problem by increasing the MTU size on the drop to 214 and implementing long write operations, which allow Android to break the data into multiple packets that are sent sequentially to the drop. Upon reception the drop’s BLE stack asks for a memory block that will hold the temporary data, and then writes the whole data in the characteristic.

I hope you enjoyed reading my blog posts as much as  I enjoyed writing them, but now, I have to get back to work.

[Little Brosers] PCB, Images, hash digests and flash memory

Hello everyone,

 

This week, and particulary this week-end have been quite intense. Let’s sum it up.

PCB : First hands-on and testing

We received our PCBs this week ! It was awesome to see it, like, for real, not only on my screen. We spent a day testing each component and all went beautifully well. We had a software issue with the external flash’s pins but somme google research solved it. We forgot to configure the pin used for SPI’s CS, which is used for NFC by default. We juste had to declare a preprocessor constant to remove the NFC from this pin.

 

Some pics :

 

Banana for scale

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In case you wonder, our drop’s PCB roll very well and resists to battery pole inversion 🙂

Docker images

Finally, after weeks of procrastination about Docker, I finally took the time to make a precisely adapted image for each jobs of our CI. “Took the time” means 1 full night and one full day but at least we now have beautiful lightweight alpine/arch docker images for our jobs. Tests run way faster than before !

 

Hash digests

So, for the last weeks, I have been in charge of our merkle tree and for simplicity, I never implemented messages hash. I always used the first byte of the message’s payload to run our sub-sorting, first one being timestamp. Also I never took care of computing the nodes’s hash of our merkle tree. This was just not usefull for what I had to do.

However the project is progressing and we came to the point where we needed those hash digests. Thus during friday, I sat at a table with Chris and we reviewed together the hash code for the drop. At the end of the day, we ended up with the exact same code for computing code from simulation or from the drops. We just made sure to redirect the “#include”s to the appropriate header files.

This is going to be merged into master branch pretty soon.

 

External flash memory

Ok, this time, it’s simple : my whole week-end was dedicated to the external flash memory. Saturday I started from master with what Xavier had already written for it and started to build basic functions like a get_status() function allowing main() to read the status register of the flash and I spent the rest of the day reading the datasheet. Today was all about writing a full Little Brosers message to the flash. Knowing that a flash page is 528 bytes, we decided that our messaged would be 528 bytes long for the maximum length. The external flash memory has 8192 pages.

So to make a quick summuray of what I have learned:

The flash has two SRAM buffer of 528 bytes buffer. They are used to optimize writing and reading operation. In our case it is very usefull.

Indeed, the nrf52 SPI driver only allows SPI transfers up to 255 bytes(i.e. 251 bytes of payload, 4 bytes being used by the flash commandID and page/word address). We won’t be able to fill a full page with only one transfert, even if the flash allows it, the nrf doesn’t. I mean, we could force the sending of more than 255 bytes using nrf52’s SPI driver but it would require a heavy structure using nrf52’s timers and PPIs to make it possible. We don’t have time for such a complex thing. Instead, we chose the following procedure to write a msg in the page i using buffer1:

-> transform the message_t C struct into a byte array of size 528
-> write msg[0] to msg[250] in buffer1[0] for 251 bytes
-> write msg[251] to msg[501] in buffer1[251] for 251 bytes
-> write msg[502] to msg[527] in buffer1[501] for 26 bytes
-> push whole buffer1 to page i

 

The procedure for reading is quite similar except that we do not use the buffers. Indeed, we use the low power continuous array read on the page i three times (0->250, 251->501, 502->527).

 

It is 22h36 and for now, it “seems” that writing works fine, not so sure about reading. I’ll stop here for today, we’ll see tomorrow with a full night of recover. I’ll have to show it to my coworkers and see if they have any idea how to debug this part. I have to admit that it is not very easy since we still not fully master the NRF_LOG macro which is supposed to replace the usual printf() of the libc. It very often doesn’t actually print the characters I asked for; skipping some of them if the number of characters is too high. Even if I raise the RTT buffer size.

So for now, flash support is not reliable.

 

See you

 

Antony Lopez

[Little Brosers] DFU, Flash, and Heroku

Hello everyone. I’ve been working on various things for our project, here is a summary.

DFU

After struggling a lot, I succeeded performing a DFU in bootloader mode (in this mode, there is no app in the flash). Now I work on making a DFU in buttonless mode, where the DFU is performed with a GATT service with the application running.

We need to flash the bootloader and the softdevice to make it work. When there is a reset, the bootloader checks the apps present in the internal flash, it computes their crc32 and compare it to the checksum stored in a special internal flash page named bootloader_settings_page. So now when we flash our app, we also need to write the good checksum in this place. The program nrfutil can generate a hex file (a text file, basically with a list of address and their data) with the content of the bootloader settings page, and we can juste merge it with the application with the nordic mergehex program to make it work. I still need to write a script for the merge, and also handle the keys in the CI (with a protected secret key).

Flash

I made a basic code that check if the SPI external flash (AT45DB321E) is present and stop the execution otherwise. For that I used the “Manufacturer and Device ID Read”, I just send an opcode, and the flash has to answer correctly 5 bytes. 

After having made a board configuration header, and after having received the drop boards, I tested it, but it was not working. The logic analyser showed that the CS pin was not working and was kept low. I tested it on a second Drop, and surprisingly, it started working for some times, and then failed. At this time I suspected a hardware problem, for example the flash receives too much voltage and is destroyed. Hopefully with the help of Antony, we realised that the CS pin was by default used for NFC, and unlike other GPIO pins, needed to be explicitly configured as GPIO. I think it works one time because there is an undefined behaviour if the CS wire is always kept low.

Heroku

We migrate the certification authority to Heroku because my 15€ router didn’t work correctly (after ~20 hours of up time, it wasn’t connected to the internet anymore, and I had to plug out and plug in the RJ45 wire, and it would work again).

The heroku migration was not so easy, the reason was that heroku has ephemeral filesystems, it was generating the keys at each app startup (often in the free version of Heroku). So I put all the keys in environnement variables. Heroku also doesn’t provide database, I need to find a free MongoDB Heroku plugin to make it work, and Heroku ask for your CB even if it’s free. I updated the continuous deployment, it is now easier (I was doing a git filter-branch to keep only the ca folder history before) and use a ruby util named dpl (https://github.com/travis-ci/dpl).

I also put the Heroku API_KEY  as a protected secret variable in GitLab (Accessible only in the master branch, otherwise my coworkers could just write a CI script “echo $API_KEY” in one of their branch and would be able to steal the API_KEY).

[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] That Key

This is an update on the authentication service I’m still working on. Yesterday I managed to parse the user certificate in DER format and extract interesting fields, such as the validity dates, username, public key and signature. However, in trying to bring it together with the rest of the service, in other words using the parsed public key to verify the challenge response, I ran into a bit of a problem. Upon further investigation (and to spare you the unnecessary details) I realized that if I try to compute the public key from a private one with the nRF crypto library, the output is different than the public key obtained with OpenSSL.

I spent all afternoon working on this so it’s a fresh issue right now. I read somewhere that endianness may be causing this, but my first tests didn’t show any promise there. If you have any ideas or suggestions I’m all ears!

Other than that, I still have to include the server’s public key in the code to test the certificate’s signature. I also have to transform the dates that I parsed into a more convenient format that we can use to compare to the date provided in the time certificate (which we still haven’t touched yet).

[Little Brosers] Memory management issues

OK, first, happy new year ! Hope you all had great holida… come on, it’s ROSE’s logbook 😉

So for the last two weeks, I kept working one our lovely merkle tree and all the code it implies.

Interactivity

Indeed, first week was about adding interactivity to the simulation. Thus I added a shell to our simulation program as well as a thread per Device. “Device” is a c++ class wrapping the Little Brosers API which is supposed to emulate a running drop/phone.

Also I added basic C++ TCP server/client to the drops. Allowing them to communicate whenever main’s thread asks them to interact with each other. For now they are only able to ping the other. But I will use this communication channel to implement the diff-like. Indeed, until now, all the code I wrote could be tested without the presence of another Device. All was creating a merkle tree and adding messages to it. No interaction.

In total this interactivity implies 2 threads per Device(one for its “main” thread, another one for the tcp) and one for the main().

Rolling memory

So, while my merkle tree building process was believed to be fully terminated, I noticed yersterday a BIG issue. First some context:

In Guillaume’s Python script, the messages where dynamically allocated whenever it was necessary. Embedded C code does not allow this.

Also, in python, the messages were directly accessible. In our drops, the will be stored in the external flash memory.

Thus, I had to creat a C structure called a “slot pool” :

#define LB_NB_MAX_MSGS 50

typedef struct lb_bucket_slot lb_bucket_slot;
struct lb_bucket_slot {
    lb_bucket_slot *p_previous;
    lb_bucket_slot *p_next;
    message_t *p_msg;
    uint32_t timestamp;
    uint8_t p_hash[MESSAGE_SIGNATURE_SIZE];
};


typedef struct {
    // The + 1 is used to ease the memory management when all slots are full
    lb_bucket_slot slots[LB_NB_MAX_MSGS + 1];
    lb_bucket_slot *begin_busy;
    lb_bucket_slot *begin_free;
    size_t nb_free;
} lb_slot_pool;

As you ca see, a slot_pool is a big array of slots. A slot is a simple structure meant to represent in RAM one particular message stored in the external flash, with a copy of the message’s time stamp and signature for ease-of-use reasons.

So this pool has a limited capacity. Its capacity will eventually be the number of messages we can fit in our external memory. But for now, during simulation, we can choose any size. Here it is 50.

The thing is, what to do when we run out of free slots? Well, we are supposed to free the one referring to the oldest message. This feature was badly implemented by…. me. So i spent the whole day of yesterday re-thinking the management of this pool. And during the process, re-writing the merkle tree build process.

 

Now everything works fine. The slot pool size can be from 1 to +infinite. And whenever a pool of messages is submitted to this merkle tree, it will only keep the newest it can store.

I reviewed the entire code with Guillaume today and we found some edge-cases in the merkle tree build process that wear treated before yesterday (with the bad memory implementation) but not today. However, those cases are easy to solve with the new memory model. In this specific case, I clearly saw that a CI with unitary tests would have noticed me that the merkle tree build process of my new memory management forgot some edge cases that the previous model took care of.So now and more than ever, we realy need to write tests for this whole merkle tree thing. Don’t worry, Guillaume should be on it as I am writing this post.

 

See you next week !

 

Antony Lopez

[Little Brosers] Authentication

I want to start this logbook entry by wishing everyone a merry Christmas and happy holidays!

Now let me give you an update on the authentication service. Last week I told you that I started working on it, and that the service, as well as its characteristics, were up and running. Since that time I have implemented and tested the challenge generation, response and verification on the devkit. But before doing that, I wrote a few wrapper functions for the existing crypto and hashing functions in the SDK just to make our lives a little easier. Now let’s talk about the challenge/response mechanism.

The idea is to use a random number generator for the challenge. That number is placed in the corresponding characteristic that’s available as read-only to the connected client. The client then has to read that number, sign it and write the signature in the corresponding write-only characteristic. The drop then read that signature and verifies the signature based on the public key given in the user certificate.
And vice versa, when the client sends a challenge to the drop, it writes a randomly generated number in the proper characteristics that the drop will read and sign. The signature is placed in a read-only characteristic that the client will read, and verify to make sure the self proclaimed drop is indeed a real one.

Which leaves me with the last 2 bricks of this task, processing the user and time certificates. Our backend server currently generates a x509 PEM certificate per user, and the drop has to parse and verify the contents and validity of the certificate to allow the user to exchange messages with it. I’m just starting to look at this type of certificate, its format and the data it can hold. For the moment I haven’t done a lot of research, so I’m still not sure if I’ll have to do the parsing manually or use an existing library for that. Either way, I should get back to work…

[Little Brosers] Decorating my very own Christmas Merkle tree

Ho Ho Ho !

Guess who’s putting messages instead of presents at the foot of it’s Christmas Merkle tree ?

Ok so last week I wrote you a whole essai about how I planned to manage messages relatively to the drop’s Merkle tree, and how to build this tree.

Here is a simplistic summary:

Merkle tree ? Again?

Yes, this week I kept on testing my Merkle tree build process. I also tested the function allowing to insert new messages in a tree already containing messages. It may not seem that complicated, but I had to make sure to take into account every single case of insertion and not break my structure. And believe me, there is quite a lot. Don’t forget we have two sorting levels.

There is still no unitary test. But fear not, it’s coming soon ! With Guillaume, we agreed that he should be in charge of reviewing my code and writing the tests for it (see? I told you 😉 )

The reason for that is the following: Guillaume wrote the prototype python code for the Merkle tree and for our diff-like algorithm for comparing trees of two drops. We will see if I respected his vision of the whole process.

 

What’s comming for me?

Next step is writing the diff-like algorithm in C. However to write and test this, I am using a C++ simulation environment emulating the existence of two drops and their interaction. It kept me busy for the last three days, I am still building it before diving into the diff-like algorithm.

For now the drops C++ objects share the same thread. I’m thinking about giving each “virtual” drop its own.

 

That’s all for me,

 

Merry Christmas !

 

Antony Lopez