Author: spacekookie

GSoC 2018: qaul.net changes and experiences (final report)

Posted on by spacekookie

This is my final report for Google Summer of Code, working on the userspace, backend agnostic routing protocol for qaul.net. Or also entitled: how to not go about writing a userspace, backend agnostic routing protocol (in general).

The work that was done

If you’ve been reading my first three blog posts, you will know that we had some issues designing and coming up with plausible ways for such a routing core to interact with network layers. The biggest challenge is the removal of adhoc wifi mode from Android, thus requiring root as an app to provide our own kernel module for that. Before specifying what I would be working on this summer we had a very idealised view of what a routing protocol could depend on, making a lot of assumptions about the availability (aka connection reliability) and usability of WiFi Direct and were negatively surprised when we ran into various issues with both the WiFi direct standard.

Secondly, I built a prototype that uses bluetooth mesh networking to allow multiple phones to communicate which has given us much better results from the beginning. Connections are more stable, however their range is more limited than with WiFi. It does however come with the benefit of power saving.

These prototypes will serve as a good base to play around with larger networks and more devices but won’t end up being part of the qaul.net code base. The code written to remain in qaul.net is relatively little. There is the routing-core repository which provides a shim API between a generalized routing adapter and a generic network backend, that can either be bluetooth, wifi direct, even adhoc or ethernet. We ended up not focusing on this code very much because there were too many open questions about the technologies at hand to proceed with confidence.

The code for both prototypes is available here, the routing core shims can be found here

What wasn’t done

We didn’t end up writing a userspace, network agnostic routing protocol, of the likes of BATMAN V. This is very unfortunate and probably comes down to the fact that, when summer of code started, we only had theoretically worked with WiFi Direct before, making a lot of assumptions that were ultimately wrong (and based on the way adhoc works).

The next steps

We will proceed with bluetooth meshing as our primary network backend, where we still have to figure out a few questions about the captive portal functionality, how to subdivide a network into smaller chunks and how moving between subnetworks will work. Bluetooth meshing isn’t exactly made for what we’re trying to do but it’s a close approximation.

When it comes to the actual qaul.net code, we need to write a bluetooth mesh adapter which plugs into the routing core, at which point we can start testing the protocol layout that we designed and work on the actual routing heuristics. The work for this is largely done, based mostly on the BATMAN protocol documentation.

Acknowledgements

I want to thank the Freifunk organisation and community, my mentor Mathias who worked with me on figuring out how to get around the problems we encountered. We managed to get a good step closer to moving qaul.net away from adhoc networking, even though we didn’t reach all the goals we set out to. Finally, I would like to thank Google for the Summer of Code and its efforts during all these years and for its commitment to the development of open source software.

WiFi Direct and Bluetooth Meshing

Posted on by spacekookie

As hinted in my last blog article, for us to really be able to move forward we needed to do some experimentation with the new technologies we have to adapt. The primary candidate in the beginning of that phase was WiFi Direct, a type of WiFi mode setting which is an official standard published by the WiFi consortium which is meant to replace the ad-hoc wifi mode. But only partially: WiFi Direct was mostly designed to make integration with IoT products easier. As such, using it for the meshing applications is a bit outside of it’s primary use case. The idea behind it is to make two WiFi devices talk to each other without needing a router to be the middleman for negotiation and frequency selection. Even groups of devices are possible create, electing a group leader that then manages the group.

Unfortunately…that sounded a lot better in theory than it turned out to be in practice.

Also as hinted in my last blog post we built some little prototype applications to test WiFi direct between multiple devices and ran into some issues. The APIs that are provided by Android are okay to use, but not super convenient. But most of the issues come from bugs that we haven’t exactly been able to trace down yet. The system WiFi Direct interface (System Settings > WiFi > Advanced > WiFi Direct) detects all devices in the vicinity whereas our application, using the WiFi Direct interface in the Android SDK would sometimes (nondeterministically) fail to detect devices or open sessions between them. We also had some bad experience creating groups between the devices.

All in all…it was underwhelming. WiFi Direct really wasn’t meant to do the kind of networking we’re trying to do with it and even if we can figure out the bugs we encountered, there are other concerns to work out. Debugging these issues aren’t easy but there are a few things we can do. For one, there are other (open source) applications that exist (serbal, briar, …) that use this technology and we can study to see how they solved these issues. There is also the option of wireshark-ing packets that are being transmitted between the two devices to get a better understanding of where handshakes are going wrong. Simple debugging via Android/ Java debugger unfortunately hasn’t yielded many useful results.

We need a convenient way for people to be able to join the network. We need to figure out a way to create a captive portal for people just connecting without the software. The handoff between a WiFi Direct network section and a legacy ad-hoc section that might be created between infrastructure nodes that don’t support WiFi Direct. The last week or so I’ve had my head in the WiFi Direct specification, trying to answer these questions. And while I think we have solved most problems, there’s still a few left to answer.

The second technology we are investigating to complement WiFi Direct wherever it isn’t applicable is Bluetooth P2P Meshing. In contrast to WiFi Direct, it was actually developed for devices to mesh with each other which makes the adaptation of it easier for us in the long run. So far we’ve only done some simple experiments with 2 devices (due to a lack of Android devices in one location 😉 ) but these have been a lot more promising than what WiFi Direct has offered.

The biggest take-away from the last 2 weeks of experimentation is that we can’t dedicate the routing core to a single networking backend.

In the design of the actual code interface that I’ve built in the first few weeks of GSoC this means that there are some adjustments to be made before writing more code. This includes being more generic when binding interfaces and allowing a client to use multiple backends at the same time. This was not intended to be used in the initial design. But for the time being those interfaces will simply be mocked by some stub methods or maybe a simple simulation so we can test the actual routing algorithms. This is an interesting challenge because so many parts of qaul.net will have to change in lockstep with each other to make it all work.

There are some corner cases to test when it comes to bluetooth mesh networking such as groups and how they handle devices joining in and out of them

Routing and WiFi experimentation

Posted on by spacekookie

The beginning of my work period was pretty busy, not always with Summer of Code things. My mentor math and I had already talked about a lot of the things that needed to happen in order to move qaul.net away from an OLSR based routing protocol and make it extendable as well.

As previously hinted, we are using Rust for the protocol implementation, allowing for easy integrating into the existing C code as well as giving us the option to bit-by-bit rewrite the entire software in Rust, a much more modern and forgiving language. The first thing I tackled was to design a common API for the qaul.net library (libqaul) to use to talk to any networking backend. The routing code holds the state of the network and allows the sending of direct and flooded messages into a network (regardless of implementation under the hood). But to do that we also had to define some common characteristics for nodes and messages.

In the end, a lot of the work was sitting down, going through old notes and determining what our protocol was supposed to do. We looked at existing protocols a lot, thinking about extendability and backwards compatibility. The protocol itself will be binary encoded, although not yet sure which format. There is msgpack, cpnproto/ protobuf as well as some Rust specifics (Rust Object Notation to mention one) to look at. But that shouldn’t actually matter for now. All the versioning and extend-ability are being done in the struct level of the protocol, meaning that we could even switch binary encoding half way through. Keeping the encoding and decoding written in Rust, this is actually incredibly easy with the `From` traits. But I digress…

The protocl we ended up designing can handle any type that already exists in qaul.net, as well as allows for custom user extentions – messages that have a type field and a random binary message payload which allows plugins on both sides to interact with it.

 

So…so far the routing core isn’t doing much routing. But that’s okay, that comes later 🙂 With the networking API in place, we actually have something what we’ve wanted for the last 2 years: a hardware abstraction over any networking backend. The API is implemented in Rust as a trait (think like a Java interface), which makes implementations and even implementation specific code very easy.

The next thing on our todo list is working out how WiFi direct behaves. This is kinda disconnected from the rest of the project, but it’s something that has to happen. For this purpose I’ve written a small demo app (still WIP at the time of this writing), which will let us explore the way that WiFi direct works, how to build mesh groups, etc. These experiments are still ongoing, and we hope to have something to show until the end of the week. I will probably publish a small article on my blog about it – check it out (if you’re reading this in the future 😉 )

All in all, the amount of code written in the first section of GSoC2018 is medium. We have however answered a lot of open questions, have a good plan on how to continue and hope to have more to show off by the time of the next evaluation.

If you’re curious about the progress being made, check out the github repository.

 

Until next time,
Katharina

Designing a userspace routing protocol for qaul.net

Posted on by spacekookie

Hi – my name is Katharina, I’m 24 years old and a computer science student at the HU-Berlin. I’ve done the GSoC2016 before for qaul.net and have been an active contributer for the past 2 years. This year I want to tackle something we’ve been postponing for a while…

qaul.net is a communication app that’s based on Freifunk technologies (namely OLSR) which enables people with no access to the internet to communicate with each other easily, using the devices they already own (phones, tablets, laptops, etc) and without needing to be experts in networking technologies.

Unfortunately qaul.net has an issue, namely OLSR. The routing backend is based on manipulating kernel tables and as such needs to run in root-mode. Which isn’t possible on many devices (such as phones and tablets). Furthermore it makes heavy use of the WiFi adhoc mode which isn’t present anymore in modern phones and tablets, putting in another reason for users having to root their devices.

We want to change this to make installation easier (a simple .apk file could be dropped onto a normal phone) and support newer devices without having to install any kernel-level modules. So that’s the why. What about the how?

Well, that one is a little tricky to be honest. Large parts of the qaul.net core library are based on the fact that routing is handled externally and some parts of the code are even olsr-specific. There are three main parts to this challenge.

  1. Actually designing a resilient, delay-tolerant routing protocol
  2. Building a networking abstraction layer which can handle multiple backends (Adhoc, WiFi-direct, ethernet, etc)
  3. Integrating the new routing core into the rest of the library.

When it comes to designing the protocol we want to let BATMAN inspire us greatly. Each qaul.net node doesn’t need to know the entire topology of the network, only where to roughly send packages for them to be delivered. This also means we can build a delay tolerant system. This module (which I’ve called routing core for now) will be written in Rust, a low-level programming language which can integrate into the rest of the C source code easily, without being as low-level and feature-sparse as C itself. Developing it as a separate module with an API also means that we can take it out of the context of qaul.net and do experiments with it in different settings.

Building a networking abstraction API will require knowledge of different backends. For this we will do experiments with WiFi direct on Android (and maybe iOS if we find hardware) to see how it behaves, how we can build meshes with it, etc. There are a lot of open questions for this which will need to be answered but hopefully at the end of GSoC2018 we’ll have some answers and code to go along with it.

 

I’m excited to get working on this. It has been about two years in planning and with it we can make qaul.net more accessible to more people.

GSoC2016 Wrapping up: A crypto module for qaul.net

Posted on by spacekookie

The last weeks

So it’s been a summer. Wow. It was an amazing experience taking part in this project, I feel like I have learned a lot and I hope that my work will be useful to others.

I want to take this opportunity to highlight what I set out to do and what I achieved in the end. The last weeks were probably the most satisfying bit of the entire project as modules that I had written weeks prior were slotting together seemlessly and things suddently just started to work. At the same time they were also the most frustrating with my code having two bugs that took me almost 2 weeks to finally track down.

Most of my work can be found in this repository, on the qaul_crypto branch.

I did some work on a different project, mildly related to qaul.net which might become useful soon.
Most of what I have done is backend work but there is an example application you can run. The source code compiles and has been tested under Linux (Ubuntu 14.04 and Fedora 24). By running the qaul-dbg binary (under src/client/dbg/qaul-dbg you will create two users (to emulate a communication between two nodes), add their public keys to a keystore and then exchange and verify a signed message. Feel free to play around with the code for this demo, that can be found under src/qaullib/qcry_wrapper.c.

In this final blog post I will talk a bit about what I have done, what it means for the project and how my ~2.2k lines of c-code contribution will affect the future of qaul.net.

What I have done

The basic idea behind my project was to provide a cryptography submodule to qaul.net to make it a safer and more verifiable place to communicate in. Part of that are of course ways to sign and verify messages but at the same time a core aspect of that are also user identities.

The two biggest parts of the crypto module are internally referenced as qcry_arbit and qcry_context. As I have already explained in previous blog posts, those are the Arbiter (which provides a static API to use in the rest of the library) and the Context which holds the actual “magic” of signatures, identities, keys and targets. In an earlier diagram there was a dispatcher. However due to testing the functions, it was deemed “overkill” and the functionality was integrated into the arbiter, meaning less abstraction layers and more flat code (which is always easier to understand and maintain).

With the arbiter in place it is now possible to create unique users with a unique fingerprint that can be shared on the network to identify people as well as sign and verify messages. What has also been done is provide new message types for OLSR (the routing protocoll used in qaul.net) to propagate this new information among nodes.

What I haven’t yet done

Unfortunately there were some delays due to problems with the main crypto library in use in the project as well as a few bugs that really slowed down progress in the last few weeks. Due to that the entire encryption part has been delayed. There are functions planned and partially provided to take care of these tasks however no code behind them yet to implement it.

The feature is currently in planning and will land in a later patch, probably after the initial merge of the module has gone through as there are a lot of things to be taken care of.

Current state

Initial User signup dialogue

As said above, it is currently possible to create users, sign and verify messages and to flood the users fingerprint as well as public key to other users. However this doesn’t address a few problems that we have had while integrating the arbiter API into the rest of libqaul. Due to technical limitations in the communication system it’s currently not possible to sign private messages. This is due to how the communication subsystem works; which is currently being redesigned from scratch.

This means that any merge that will go through now will need to be adjusted to work with a new communication backend in a few weeks. As such, it is a bit unclear when exactly and how the crypto code will be merged. I am looking forward to working with the team on resolving these issues. And am also looking forward to a new shiny communication backend. But for now it means that merging the code I’ve written for the Summer of Code might be difficult.

New message types were added as well to provide a way to exchange these new payloads (signatures, public keys, fingerprints, etc) without breaking backwards compatibility with older nodes. What happens is that new nodes send out both a new and an old hello message. Other new nodes ignore the old hello message and can address the new node via it’s fingerprint and use verifiable channels of communication while old nodes are oblivious to any change. Until they are updated 🙂

In conclusion

The Google Summer of Code brought qaul.net a very big step closer to being a more safe and secure place to communicate on. The crypto submodule is tested and easy to use. What might happen is that parts of the code get merged (the crypto submodule itself) without merging any of the code that hooks into the communication stack.

There are still things to be optimisised, probably some hidden bugs to be fixed and there definately is some work needed to make private messaging actually private.

This might be the end of the Summer of Code and a “final evaluation” for this part of the project but I am by no means done. I was interested in open source software before, wrote my own projects, contributed small chunks of code to other people. But this is the first time I have been deeply involved in a large community project and the first time I learned to deal with integrating with other peoples code. And it is very largely due to the Summer of Code, Freifunk and my mentor.

I had a lot of fun working on this project and I am looking forward to more contributions. Even if it was frustrating and very stressfuly at times I’m glad to have participated. The experience tought me a lot about communication in teams, software development and funnily enough signature alignments 🙂

Acknowledgements

First of all I want to thank my mentor Mathias Jud to have introduced me to qaul.net and the Google Summer of Code. I also want to thank him for his support and guidance with problems I had while interfacing the arbiter with the rest of libqaul.

In addition I want to thank saces, another member of the qaul.net team who helped me in resolving dependency issues as well as problems I caused in the build system which prevented my code from building on Windows (woops).

Lastly want to thank Freifunk for providing me with this opportunity as well as Google for organising and sponsoring the Summer of Code projects.

Provide a cryptographic implementation for Qaul.net – midtern update

Posted on by spacekookie

It’s been almost a month since official coding started for Google Summer of Code 2016. And it’s definately been an interesting experience.

When I was told to write this article some sugestions for content were “pictures” and to “provide links to prototypes”. Unfortunately with my subject (especially at this point in time) that’s not as easily possible and I’m not sure how many of you want to see source code in the form of glorious macros in a blog post.

But I will try 🙂

Qaul.net is building it’s crypto on a small, embeddable crypto library maintained and mostly developed by ARM called “mbedtls”. Unfortunately the project just went through some massive refactoring and the API has completely changed. Thus a lot of documentation online is out of date or just plain out doesn’t work. Most of my time so far I’ve spend crawling through the source code of the library components I need and learning how they link together in the background to understand which files I need to compile into the project and which are optional. The goal here is to make the end binary and the memory footprint of qaul.net as small (and as embeddable) as possible.

Next up was the general structure of the crypto module. In libqaul I added a new folder and thus function/ field namespace called “qcry” which is short for Qaul CRYpto. Following is a quick graphic of the layout of the module.

qaul crypto structure

All orange modules are part of the crypto-package, yellow modules show heavy modification to their code base where as grey modules will require very little modification. As you can see the crypto module is structured into five parts: Arbiter, Dispatcher, Context, Targets and Utilities. Following a quick description of what they do, if you’re interested in more in-depth documentation, check out my wiki.

  • Arbiter: Provides abstraction layer to the rest of libqaul and handles “disputes” between different threads or application states.
  • Dispatcher: Acts as a load balancer between the non-threadsafe functions of the crypto and the multithreaded environment of libqaul. Also optimises CPU overhead for context switching.
  • Contexts: Contains raw data for crypto tasks (private keys, mode of operation, targets, etc..). Is created by the arbiter but most handled by the dispatcher.
  • Targets: Contain data required for public key crypto. Mostly contains metadata and public keys of other users. Get created by the arbiter.
  • Utilities: Base64 encodings, hash functions, verifications, creating user avatars, lots of stateless functions that are used throughout libqaul go here.

One thing I have started to work on too (but haven’t gotten far enough yet to show something off in the UI) is user verification. So…users have private keys and with the fingerprint of that key it is possible to tell if they really are who they say they are. But how to communicate that to users? Showing people a long number is very unintuitive and will just cause people not to care.

So instead of a longer number (or maybe additionally), on a new user profile screen we will show an image generated from the username of the person, their fingerprint and a signature (public key encrypted with private key). This way users will be able to quickly see if the person they are talking to is who they say they are.

To do so there are several libraries:

 – https://github.com/Ansa89/identicon-c
 – https://github.com/stewartlord/identicon.js
 – https://github.com/spacekookie/librobohash (My C re-implementation of https://robohash.org)

 Which of these solutions will be used is not clear yet (Personally I like robots, who doesn’t like robots? Wink ). But that should give you an idea of what is to come in the UI department.

 Coming up in the next week is the arbiter and a rudimentary dispatcher. The arbiter needs to be hooked into the rest of libqaul and provide access to all the low level functions the crypto module provides. From there on out test with the rest of qaul.net can be conducted.

 I hope I didn’t ramble on for too long. And I’m looking forward to the next few weeks of coding.

 Cheers,
 spacekookie

Provide a cryptographic implementation for Qaul.net

Posted on by spacekookie

Hey there,

my name is Katharina (aka spacekookie) and I am one of the Google Summer of Code participants for Freifunk projects; qaul.net in particular.

I wanted to write up a short article on what it is I will be doing this summer, how I will do it and what I hope to achieve. This will be one of three articles published on this blog.

Qaul.net provides a mesh-wifi network for people to connect and share information to other people on the network. Like freifunk it uses the OLSR mesh routing library. But unlike freifunk it’s main goal isn’t to connect to the www-internet but rather create a network of it’s own on which people can communicate, share data and come together. No centralised infrastructure required.

Currently all traffic on qaul.net is sent in the clear which is…suboptimal. For one nothing said on the network is in any sense of the word “private”. On the other there is no way to verify identities. And that’s what my Summer of Code project is about.

The changes to the qaul.net code base required are quite extensive but with a bit of clever planning shouldn’t break too many things. The core thing required is an abstraction layer between user and network.

Currently a user gives their node a nickname and that’s then them. “Identify verification” (if you want to call it that Tongue Out) is done by checking IP addresses against nick-names. Man in the middle attacks are very easy in such a network and the only defense is the benevolence of its users.

What I thus plan to do is introduce an abstraction layer between a node, routing and what a user sees. A “user identity” which can be shared between different nodes (but doesn’t have to be), something that can be written to an addressbook and is later on verifiably the same and will make users aware if their are being man-in-the-middled, which is now much easier to verify.

In addition to that I plan to introduce asymmetric encryted messages, completely transparent to the user. While qaul.net can flood a message acress the network that should be seen by as many people as possible, there should be the ability for two people on the network to talk to each other without anybody else knowing what they’re talking about.

What’s planned is something that resembles PGP. A users identify will be their master-private key fingerprint. From that each node gets a subkey-pair (public and private). The public key will be flooded into the network for people to use to write messages to that node. The private will be unique to the node. And when sending messages to another person people can either choose “all” which means that the messages is encrypted against all (non-revoked) public keys of the target identity or choose a specific node to talk to. This implementation also allows for mailing list style group discussions.

 

Through Google Summer of Code I hope to become a regular contributer to qaul.net as I am a big fan of the project ideas. I also hope that my contributions will make it a much safer place to communicate and share information on.

As already mentioned I will be updating this blog two more times: one around the half-way point of the project and one as a wrap-up of how it all went.

If you’re interested in reading more of my insane ramblings about the project, maybe micro updates and what not, check out my personal blog https://spacekookie.de or go directly to the GSOC category.

 

Until another day,

Katharina/ spacekookie