Sunday 15 May 2016

How ECC-SHA-llent!

About a year ago, shortly after TI released the CC26xx family of chips, I published a rant about the differences between those chips and the CC2538. Among the things I discussed was the fact that TI have apparently removed advanced cryptographic hardware acceleration from the CC26xx (and subsequently CC13xx) products.

No SHA2, no ECC, only good-old AES...

It was not making sense! Why remove such a desirable feature???

CC26xxware to the rescue


At roughly the same time as the first CC26xx chips were released, TI also released a set of supporting libraries code-named CC26xxware. The Contiki OS has supported CC26xx-based boards since pretty-much day one and it pulls CC26xxware in as a git sub-module. At the time of release, CC26xxware was at revision 2.21.01.15600.

Come CC26xxware version 2.21.03.15980 and suddenly two new files appear: rom_crypto.h and rom_crypto.c. Uh-oh...

For the CC13xx family of chips, the respective support bundle is called CC13xxware and it features the same two files. TI originally distributed CC26xxware and CC13xxware as stand-alone downloads, but at some point they decided to stop doing so and they are now bundling them inside TI-RTOS.

Both xxwares are distributed under the terms of the 3-clause BSD license, which is an excellent choice!

Back to the point: So perhaps the chips do have crypto capability, only TI is not very forthcoming about it.

Let's have a closer look!

The ROM crypto API


If we look inside rom_crypto.h, we see the following function prototypes (Taken from CC26xxware version 2.23.01.16780, distributed with TI RTOS 2.16.00.08 - 25 Feb 2016):

extern void AES_ECB_EncryptData(uint8_t *text, uint16_t textLen, uint8_t *aesKey);
extern void AES_ECB_DecryptData(uint8_t *text, uint16_t textLen, uint8_t *aesKey);
extern int8_t AES_CCM_EncryptData(uint8_t encryptFlag, uint8_t MACLen, uint8_t *nonce,
                                  uint8_t *plainText, uint16_t textLen,
                                  uint8_t *addDataBuf, uint16_t addBufLen,
                                  uint8_t *aesKey, uint8_t *MAC, uint8_t ccmLVal);
extern int8_t AES_CCM_DecryptData(uint8_t decryptFlag, uint8_t MACLen, uint8_t *nonce,
                                  uint8_t *cipherText, uint16_t textLen,
                                  uint8_t *addDataBuf, uint16_t addBufLen,
                                  uint8_t *aesKey, uint8_t *MAC, uint8_t ccmLVal);
extern uint8_t AES_CTR_EncryptData(uint8_t *plainText, uint16_t textLen,
                                   uint8_t *aesKey, uint8_t *nonce,
                                   uint8_t *initVector);
extern uint8_t AES_CTR_DecryptData(uint8_t *cipherText, uint16_t textLen,
                                   uint8_t *aesKey, uint8_t *nonce,
                                   uint8_t *initVector);
extern void ECC_initialize(uint32_t *pWorkzone);
extern uint8_t ECC_generateKey(uint32_t *randString, uint32_t *privateKey,
extern uint8_t ECC_ECDSA_sign(uint32_t *secretKey, uint32_t *text, uint32_t *randString,
                              uint32_t *sign1, uint32_t *sign2);
extern uint8_t ECC_ECDSA_verify(uint32_t *publicKey_x, uint32_t *publicKey_y,
                                uint32_t *text, uint32_t *sign1, uint32_t *sign2);
extern uint8_t ECC_ECDH_computeSharedSecret(uint32_t *privateKey,
                                            uint32_t *publicKey_x,
                                            uint32_t *publicKey_y,
                                            uint32_t *sharedSecret_x,
                                            uint32_t *sharedSecret_y);
extern uint8_t SHA256_runFullAlgorithm(SHA256_memory_t *memory, uint8_t *pBufIn,
                                       uint32_t bufLen, uint8_t *pBufOut);
extern uint8_t SHA256_initialize(SHA256_memory_t *workZone);
extern uint8_t SHA256_execute(SHA256_memory_t *config, uint8_t *pBufIn,
                              uint32_t bufLen);
extern uint8_t SHA256_output(SHA256_memory_t *memory, uint8_t *pBufOut);

So, what can these things do?


We can safely draw some conclusions here now, can't we? The chips can do:
  • SHA 256
  • ECDSA sign/verify
  • ECDH
  • AES CTR, ECB, CCM
But this is a ROM API. If you look at the corresponding .c file, you will see things in the lines of this (excerpt from the same TI-RTOS version):

typedef uint8_t(*ecdsa_sign_t)(uint32_t *, uint32_t *,uint32_t *, uint32_t *, uint32_t *);
ecdsa_sign_t ecc_ecdsa_sign = (ecdsa_sign_t)(0x10017969);

uint8_t
ECC_ECDSA_sign(uint32_t *secretKey, uint32_t *text, uint32_t *randString,
               uint32_t *sign1, uint32_t *sign2)
{
  return (uint8_t)ecc_ecdsa_sign((uint32_t*)secretKey, (uint32_t*)text, (uint32_t*)randString,
                                 (uint32_t*)sign1, (uint32_t*)sign2);
}

Thus, a call to ECC_ECDSA_sign() is fundamentally a jump to a pre-determined address in ROM through a function pointer. The same applies for ECDH and SHA functions. What we cannot know for certain until TI decides to tell us is what exactly happens under the hood at these addresses on ROM. Nothing stopping us from guessing though, and I can imagine two scenarios:
  • Either that address on ROM hosts a fully software-based implementation of ECDSA (or ECDH or SHA and so on)
  • Or that address in ROM hosts a driver for some undocumented hardware crypto engine.
If we look at the addresses on ROM a little more closely:

ecdsa_sign_t ecc_ecdsa_sign = (ecdsa_sign_t)(0x10017969);
ecdsa_verify_t ecc_ecdsa_verify = (ecdsa_verify_t)(0x10017b01);

Ergo, there is a gap of 0x10017b01 - 0x10017969 = 408 bytes there available for ecc_ecdsa_sign. Draw your own conclusions if you fancy doing so.

What we can also do is actually try to use those functions and benchmark them; this could provide more hints about whether we are looking at a hardware crypto engine.

A brief note about RNGs


In the CC26xx Technical Reference Manual [1], TI have boldly stated:
"The true random number generator (TRNG) module provides a true, nondeterministic noise source for the purpose of generating keys, initialization vectors (IVs), and other random number requirements. The TRNG is built on 24 ring oscillators that create unpredictable output to feed a complex nonlinear combinatorial circuit. That post-processing of the output data is required to obtain cryptographically secure random data."
TI don't normally make such claims lightly. For instance, the CC2538 User Guide [2] clearly classifies the respective RNG as a Pseudo-RNG and does not suggest that the module is suitable for crypto. In fact the document contains statements like:
"Randomness tests show good results for this module. However, a slight DC component exists."
and
"To fully qualify the random generator as true random, much more elaborate tests are required. Software packages that may be useful in this respect are available on the internet."
This is something I personally interpret as, "If you want to do crypto using this thing, do so at your own risk".

Final thoughts


During a recent e-mail exchange, a colleague of mine whom I respect immensely wrote to me something in the lines of "Why does the chip with all the crypto capability lack a cryptographically suitable RNG, whereas the chip that does have a cryptographically secure RNG has limited crypto capability?".

That was a very valid point and I suspect we have not heard the entire story yet.

What I have not yet had time to do is search around for more information on the hardware in places such as TI's E2E forum as well as on the wider internet. What I also want to do is have a closer look at TI-RTOS' sources and see how (and if) it uses those ROM functions. Doing so may reveal further hints...

References

[1] "CC26xx SimpleLinkTM Wireless MCU Technical Reference Manual", SWCU117D, February 2015 - Revised September 2015, [ pdf ]
[2] "CC2538 System-on-Chip Solution for 2.4-GHz IEEE 802.15.4 and ZigBee®/ZigBee IP® Applications", SWRU319C, April 2012 - Revised May 2013, [ pdf ]

Thursday 16 April 2015

To CC or not to CC

Earlier this year TI announced a new generation of wireless MCUs code-named CC26xx. This is a family of CM3-powered SoCs with varying 2.4GHz RF capabilities:
  • CC2630: IEEE 802.15.4
  • CC2640: BLE
  • CC2650: BLE and IEEE 802.15.4
If you read around the web, you may also get glimpses of a CC2610 and a CC2620.

The CC2650 is basically a superset of the CC2630 and the CC2640.

On the same day as the hardware announcement, TI also released a port of the Contiki OS for two CC2650-based boards:

This port supports all the cool stuff one can do with Contiki, but it also provides a first glimpse of BLE, which is not officially supported by the OS.

But... What about the CC2538?


One might think that this is a little too early, less than 2 years from the release of the CC2538. But are the two chips really competitors? Is the CC26xx meant to replace the CC2538? What are the key differences? These are the questions I'm pondering in this post, and I shall try to answer them by taking a deeper look at some of the features of the CC26xx and putting them side-by-side with its predecessor.

Oh and by the way, since we live in a capitalist, { disclaimer , indemnity }-fueled world, I must say that: "Naturally, this is just an overview, so if you want more details you should read the respective specs. Especially so if you are trying to choose between those two parts for a product."

Moving swiftly on...

Power management


A quick look at the two datasheets [1, 2] immediately reveals the ultra low-power nature of the CC26xx. Let's have a quick look side-by-side:


CC26xx CC2538
Test Condition Typ Typ Max Test Condition
Standby.
With RTC, CPU, RAM and (partial) register retention.
RCOSC_LF
1μA 1.3μA 2μA Power mode 2.
Digital regulator off
16-MHz RCOSC and 32-MHz crystal oscillator off
32.768-kHz XOSC, POR, and sleep timer active
RAM and register retention
Active.
Core running CoreMark (Peripherals inactive)
1.45 mA + 31 μA/MHz
( = 1.946mA at a theoretical 16MHz)
7mA Digital regulator on
16-MHz RCOSC running
No radio, crystals, or peripherals active.
CPU running at 16-MHz with flash access

Now those test conditions are obviously not identical, but they can still help us move forward. We see a difference under low power operation, we see a big difference while running. In fact, even configuring the CC26xx to fire on all cylinders (48MHz), its active consumption will be lower (2.938mA) than those 7mAs on the CC2538.

I've always been taking those datasheet values with a pinch of salt, since it's often difficult to understand the exact test conditions in terms of what was running and what was not.

What happens under the hood?

Power management, old style


Up to the CC2538 inclusive, TI's chips traditionally had preset "power modes" (I like calling them profiles). Those were built into the chip. For example, in the table above, we see that the datasheet mentions "Power Mode 2". In a nutshell, to enter a low power mode, one would roughly follow the steps below:
  1. Shut down / configure board peripherals (LEDs, sensors, etc)
  2. Select one of the pre-defined power modes by writing some hardware register
  3. Configure the chip for this power mode (e.g. wakeup sources)
  4. Enter this power mode
Let me emphasise this: The CC2538's PM2 is built into the chip itself, and so are the remaining power profiles (active, sleep, PM[0..3]).

Now this is very very simple to write software for, but it does have a problem: Imagine that you want to enter low-power operation and that you need some functionality X while operating in this low-power mode. You have a quick look at the device datasheet and you see that PM2 turns off feature X. Feature X is only available in PM1, which will result in a higher consumption. However, you do in fact really need feature X, so you are stuck with PM1. You are also stuck with all the other things that run (and draw current) while in PM1, even those that you couldn't care less about.

Power management, CC26xx-style


The CC26xx re-writes the textbook: It does not have pre-defined power modes. In the table above, we see the term "Standby", but this is not built into the chip, it is just a software-defined profile in TI-RTOS. The reality with the chip itself is a lot more flexible, which also makes it a lot more complex to write software for. Let's have an introductory look.

First things first, in typical CM3 fashion, at any give point in time the micro on the CC26xx can be in one of three states:
  1. Active / Running
  2. Sleeping
  3. Deep Sleeping
 The CC26xx digital power system is partitioned:
  • The CC26xx has two separate VDs: MCU and AON. The MCU VD can be turned off when we want to fully shut the chip down, but it will otherwise be on. AON is... well... AON.
  • Each VD is further partitioned into Power Domains (PDs). For example, the MCU VD has the following PDs:
    • MCU AON: This is in fact AON and cannot be turned off by software, except by turning off the entire MCU VD.
    • CPU
    • SYSBUS
    • VIMS
    • RFCORE
    • PERIPH
    • SERIAL
  • Each PD contains digital modules.
    • VIMS: Flash, cache and ROM
    • PERIPH: Supplies the DMA controller, Crypto engine, the TRNG, GPTs [3:0], GPIO, SSI1 and the I2S module
    • SERIAL: Supplies the UART, SSI0, I2C
  • Some of the modules have retention which can be enabled/disabled by software
  • Additionally, each of the  peripherals / modules has a clock gate and of course the module itself can also be enabled / disabled by software, as usual.
  • RAM is partitioned in 4 blocks, and each block can have its retention enabled or disabled
This drawing tries to capture the VD / PD / Module / Clock Gate logical structure:

    The SERIAL and PERIPH PDs can be turned on/off by software on demand.  For the CPU domain, we can request it to be off, but this will only happen when the CM3 drops to deep sleep. We can also request VIMS / SYSBUS on or off, but their behaviour depends on some additional factors and, generally speaking, we cannot explicitly force them on or off. For instance, SYSBUS will only actually turn off if neither the micro nor the RF are requesting access to it.

    While active, the chip can be supplied by a DC-DC or a Global LDO. When we drop to deep sleep, we can request a switch to a micro-LDO (uLDO), to reduce leakage.

    This system is very flexible and we can do various shenanigans. For example, we can do the following:
    • Configure the SSI0 clock to run while the CM3 is active, as well as during sleep and deep sleep.
    • Keep the SERIAL PD on (it's where SSI0 sits).
    • Disable all clocks under sleep and deep sleep for the remaining modules within SERIAL (e.g. for the UART).
    • Turn off PERIPH and RFCORE (this will turn off the RF as well as all modules within the PERIPH PD).
    • Request SYSBUS, VIMS and CPU PDs off. RFCORE is off, so SYSBUS will turn off when the MCU drops to deep sleep.
    • Request retention to be disabled for a part of our RAM (we have made sure there's nothing we need in there).
    • Disable VIMS and RFCORE retention.
    • Turn off the AUX PD within the AON VD (The AUX being a secondary, 16-bit sensor controller).
    • Drop to deep sleep.
    • Wait for SSI0 trigger to wake-up.
    This is merely an example. If we chose to do so, we can even leave RFCORE running and turn off everything else. We can pretty-much configure any combination we like (within some loose constraints of course).

    Unlike TI-RTOS, Contiki does not attempt to pre-define power profiles. Instead, it provides a set of helper functions that control the power down/up sequence and aim to help developers configure the state of the chip under low-power operation. In my humble opinion, CC26xx power mode support is the most mature power-related system among those present in the official Contiki source code repository.

    The CC26xx's power management features are described in greater detail in the CC26xx TRM [3].

    I love the CC2538, but - despite the complexity - the CC26xx wins.

    One RF to rule them all


    It only makes sense to compare the CC2538 with the CC2630 and the CC2650. The key difference here is that the CC2650 radio can operate in IEEE 802.15.4 as well as in BLE mode. Therefore, if for whatever reason you need to support both a 6LoWPAN / ZigBee and a BLE stack, you can do so without having to spin a dual-RF board. The CC2650 can do both with a single radio, albeit not simultaneously. The switching can be done on-demand and it is controlled by software.

    Controlling the Radio


    The CC2538 adopts a standard approach whereby the RF is controlled exclusively by hardware registers (In the region of ~70 documented in the user guide). The only thing that's perhaps worthy of a comment is that, even though the MCU is a 32bit one, the registers are 8bit-wide, with bits 31..8 being reserved. Makes me think that this radio has been used in a product powered by an 8bit micro in the past...

    The CC26xx adopts an entirely different approach. Reading the TRM, one can count fewer than 15 RF-related hardware registers, with another few power-related ones.

    The RF is a CM0-powered chip (also called a CPE), which communicates with the CM3 using a shared memory interface. The two chips can raise interrupts to one another. Software running on the CM3 passes commands to the CPE through a single register, called CMDR. The module responsible for the communication between the CM3 and the CPE is called "Radio Doorbell" (RFC_DBELL).

    Each command from the CM3 to the CPE can be of one among three types:
    • Direct Command
    • Immediate command
    • Radio Operation command
    Direct commands are very straightforward: The CM3 writes the command and its parameters directly to CMDR. The 16 high bits [31..16] represent the command ID, the following 14 bits [15..2] represent optional parameters, whereas the 2 least significant bits must be 01. An example of a direct command is CMD_ABORT, which will signal the CPE to abort any current ongoing operations immediately.

    Immediate commands and Radio Ops are more complicated. The command itself is represented by a data structure stored in the CM3's RAM, the chip's flash or the radio's RAM. The value written to CMDR is merely a pointer to this data structure. The CPE can tell that a command is an Immediate one or a Radio OP by inspecting the 2 least significant bits of CMDR, which for those commands must be clear. Therefore, the data structure representing those commands must be aligned on a 4-byte boundary.

    Immediate commands change or inspect the status of the radio and can be issued at any time, although some of them are only relevant when the radio is actually doing something. An example of an Immediate command is CMD_IEEE_CCA_REQ, which requests CCA and RSSI information.

    Radio Ops will access the actual radio hardware, to perform operations such as enter RX mode or TX a frame.

    Direct commands are basically Immediate commands that either don't need parameters at all, or that need parameters which can be accommodated within the space available in CMDR.

    A second hardware register, called CMDSTA, is used so that the CPE can communicate to the CM3 the status of the most recent command written to CMDR. The 8 least significant bits of CMDSTA represent the command's result, while the 24 most significant bits may contain command-specific signalling.

    Specifically for Radio Ops, the data structure representing the command has a status field, which is used by the CPE to inform about command execution status and is used in addition to the signalling via CMDSTA. Normally, CMDSTA will be updated immediately upon command reception (e.g. the command was successfully submitted for execution, or an error occurred), while the command's status field will keep getting updated over time as the command is being executed (e.g. "not started yet", "running", "done / complete" or "done / aborted").

    It certainly took me a while to get my head around this new way of working. From the CM3 developer's perspective, the CPE is a bit of a black box. You send commands to it and it does things. It's easy to tell what you think you asked the CPE to do. It's not always easy to tell what the CPE is actually doing. The API is very thorough in terms of sending commands to the CPE, but I find it lacking in terms of requesting status information. CMDSTA and the status field of Immediate commands and Radio Ops provides some information, but this information only relates to the most recent command sent (CMDSTA) or the respective Immediate command or Radio Op (command's status field). Thus, if you send a "Enter IEEE RX" command, you can then inspect the status field and see if the command is currently running. But if you do not send a command, then you have no way of knowing what the CPE is up to. For example, if you configure it to send ACKs for frames that pass frame filtering, it will every now and then interrupt RX mode, switch to TX, send the ACK, go back to RX. This happens without any commands sent from the CM3, so there is no status field to inspect. The API does not provide a "Are you currently in TX?" command, nor a "Have you started receiving a frame?" or "What is your current state?". Some (but not all) of those questions can be answered by inspecting interrupt flags, but the ability to directly enquire about those and other similar status updates would be nice to have in the API.

    Hardware crypto


    TI seem to have taken a step backwards on this front. The CC26xx only has an AES crypto engine (that can only do 128-bit AES). Nothing to write home about, this feature has been around since the CC2420 / CC2430 days.

    Conversely, the CC2538 provides hardware acceleration for AES-128 as well as 256, but it also provides acceleration for SHA2 and, optionally, PKA for ECC-128/256 and RSA.

    As IoT applications are gaining traction, hardware manufacturers, product developers, regulators, end-users and, generally speaking, all stakeholders are becoming more interested in security. The devices we are discussing here are very constrained and they cannot run the latest and greatest security-related technological advances. The RERUM EC-funded R&D project aims to tackle some of the security- and privacy-related challenges for Smart City applications. During the course of RERUM, Zolertia (one of the twelve consortium partners) developed the Re-Mote, a new hardware platform, which was designed by the requirements of the Use-Cases considered by the project. Zolertia, in collaboration with RERUM consortium partners, chose the CC2538 SoC to power the Re-Mote, partly due to its cryptography-related capability.

    I am sure TI had their reasons for taking this decision, and time will tell whether they were right or not.

    For the time being, the CC2538 wins. Hands down.

    USB


    The CC2430 was what got me involved with Contiki in the first place. The CC2530 and multicast support were the main reasons why I was invited to join the Contiki team of maintainers. Naturally, I feel emotionally attached with the CC2530, especially so with the almighty CC2531 USB dongle!

    The CC2530s are powered by 8051-based, 8-bit micros. I still think that the CC2530 is a great chip, but it does have two problems:
    • Harvard-based architecture: Very very simply speaking, this means our toolchain is not GCC-based. We use SDCC to build images, which is not a bad thing at all in itself, but SDCC does have a much smaller community. This means it doesn't evolve as quickly as GCC-based toolchains and the code optimisations it can do are nowhere near as sophisticated.
    • As I have said in various places, at various times (on occasion kicking and screaming), the 8051's stack is limited to 256 bytes, when building with SDCC at least. This is a big big problem. This renders the chip plain and simple unsuitable for Contiki and 6LoWPAN-networked applications. It would be possible to develop all those things in an 8051-friendly way, but when writing software for this chip one should implement some things in a different way than the way one would use for Von Neumann-based machines. Contiki is standards-compliant and cross-platform, therefore it is impossible to adopt 8051-friendly software design decisions for platform-independent code.
    Back on topic: Despite all of the above, the CC2531 does have this amazing feature: A USB controller. But for the limitations listed above, I would consider the USB dongle to be the perfect solution for 6LoWPAN border routers and dummy radios (SLIP radios using Contiki nomenclature). With Contiki, this functionality has been traditionally been achieved by UART-based solutions, and the interface between the border router and its host has always been a bottleneck.

    The CC2538 also has native USB support, but it doesn't suffer from any of the CC2530's limitations. It is high-time we replaced the CC2531 dongle by something newer, and I am hoping that someone will soon produce a CC2538-powered USB stick!

    In fact, I heard it through the grapevine that one is around the corner... It has a smaller form factor than the CC2531; I believe that the curved part at the right hand-side has cut lines and can be taken off. Button on the side seems like a great idea and it also has an epic LED that can turn pink!

    Reproduced with Zolertia's express permission

    The CC26xx does not feature a USB controller. This is probably not a huge deal for wireless applications. Depending on what one is trying to achieve, one can see the CC2538's USB as a useful feature, or one can see it as an unnecessary burden.

    Other noteworthy differences


    In the previous sections, I focused on the features that I consider to be key differentiating factors between the two chips. However, the CC2538 and the CC26xx have additional subtle (or not quite as subtle) differences. I am going to try to summarise them in the table below.

    CC26xx CC2538
    Key features
    Power management Advanced
    Flexible, but complex to harness
    Standard
    Not very flexible, but simple to implement
    RF
    • CC2630: 2.4GHz IEEE 802.15.4
    • CC2640: BLE
    • CC2650: 2.4GHz IEEE 802.15.4 and BLE
    Very few hardware registers
    Most operations use a new API
    2.4GHz IEEE 802.15.4
    Traditional approach based on H/W registers
    Crypto 128-bit AES
    • 128- and 256-bit AES
    • SHA2
    Optionally:
    • ECC 128/256
    • RSA
    USB Controller Nay Yay
    OS Support Both very-well supported by Contiki
    Features not discussed extensively
    MCU Speed Up to 48MHz Up to 32MHz
    RAM 20KB, all capable of retention
    (+8KB VIMS Cache +2KB on the AUX)
    16 or 32KB
    (16KB with retention in all PMs)
    Flash 128 KB 128, 256 or 512 KB
    UARTs 1 2
    SSIs 2 2
    I2Cs 1 1
    AUX 16-bit sensor controller with 2KB SRAM Nay
    RNG TRNG [1] PRNG
    I2S Yay Nay
    Can iron your shirts Nay Nay

     References

    [1] "CC2650 SimpleLinkTM Multistandard Wireless MCU", SWRS158, February 2015, [ pdf ]
    [2] "CC2538 Powerful Wireless Microcontroller System-On-Chip for 2.4-GHz IEEE 802.15.4, 6LoWPAN, and ZigBee® Applications", SWRS096D, December 2012 - Revised April 2015, [ pdf ]
    [3] "CC26xx SimpleLinkTM Wireless MCU Technical Reference Manual", SWCU117A, February 2015 - Revised March 2015, [ pdf ]

    Saturday 7 June 2014

    Anathema for my ears

    This post is not geeky and definitely not a rant. Far from!

    I have been a long standing fan of Anathema's. I remember listening to the Eternity album in a bar in Athens shortly after its release. I remember the guys sitting at the table next to me ranting "blergh, this is rubbish, they've gone too soft". I remember thinking "What the devil are these chaps talking about? This is brilliant! What's this band called???". I swiftly spent my hard-earned pocket money to buy Eternity on the very same day.

    Anathema then released "Alternative 4", but what really did it for me was when I saw them live at the Rodon Club in Athens shortly before the release of "Judgment". Surely, they played all the great stuff that they had already released, but they also gave us a sneak-peak of their upcoming release, by performing "Deep" and "Judgement".

    That was it. Helplessly, hopelessly and irrevocably in love with them.

    Fast forward 15 years, their style has changed a fair bit, but I'm still a huge fan and I've had the opportunity to see them live at Donington during the Download Festival 2010. I just found out about the upcoming release of their new "Distant Satellites" album. I pre-ordered it before I even listened to samples, which is exactly what I'm doing as I'm writing this post.

    First track starts playing, and ten seconds in I felt an irresistible urge to write this and to scream out loud that this is another bloody great piece of work. Now if you know me, you know that I am passionate about music, but never before have I been so excited by a new release to blog about it.

    If you like Anathema, do yourself a favour and buy Distant Satellites. If you've not heard of them before, do yourself a favour and listen to this.

    And I thought "Weather Systems" was great...

    Sunday 13 April 2014

    IPv6-in-IPv6 + HBHO Extension Headers: The answer to the ultimate question of RFC compliance, the universe, and everything

    So there is this person with whom I've been discussing Contiki/6LoWPAN-related topics for ages. However, due to the fact that he's based in the other side of the Atlantic, we'd not had a chance to meet in person before. IETF 89 took place in London this year, he was attending, it was an excellent opportunity to meet in person and I jumped on a train without hesitation.

    Himself, a bunch of other (IETF) IoT / Contiki enthusiasts and I met after the IETF and we went for dinner and a few drinks. Among them, a key player in IETF's ROLL WG. Naturally, lots of the conversation was on Contiki-related topics, and at some point we started discussing ROLL's protocols.

    Among other topics, we spoke about RPL (some pronounce it 'ripple') and MPL (some pronounce it 'mipple'). I emphatically recommended that, for obvious pronunciation-related reasons, they should refrain from using the acronym NPL for any of their subsequent protocols...

    Moving swiftly on...

    A little background


    Now that Contiki features its shiny support for 6LoWPAN multicast, I've been spending some of my spare time implementing the most recent version of the MPL ID (currently v08).

    Simple scenario: A 6LoWPAN connected to the rest of the Internet. For simplicity's (and my own sanity's) sake, let's for a second assume that the world suddenly woke up one day and IPv6 had been deployed globally. A host somewhere in the Internet sends a multicast datagram to a Global-Scope IPv6 address, and some nodes inside the 6LoWPAN are interested in this multicast group. Shimples!

    Or maybe it's not that simple. You see, MPL defines an IPv6 HBHO header, called the 'MPL Option', present in all MPL Data Messages. Why is that a problem? Well, it's a problem cause MPL only operates inside the 6LoWPAN, so if a multicast datagram originates from somewhere outside it, it won't have an MPL Option.

    Let's try to visualise this from a network layer perspective (omitting layer 2 and UDP headers for clarity). Observe how a multicast datagram originating at an Internet host will not have an MPL Option extension header in it (right). However, inside the 6LoWPAN, the MPL Option must be there (left).



    In the MPL draft, there is also a discussion about the Realm-Local multicast scope. This is a new scope, currently emerging as part of draft-ietf-6man-multicast-scopes (currently at v04). The relevance of the Realm-Local scope is not immediately obvious. Please bear with me...

    An example of a perfectly smooth conversation


    So there we were, eating dinner and generally having a blast, till I decided to mention the Realm-Local scope, which was when then things started going south... The conversation below was predominantly between myself and a person very active within IETF's ROLL WG. Let's call him "Him", to preserve anonymity, privacy etc.

    Me: Is Realm-Local moving forward? I'm planning to add support for it in Contiki since MPL uses it.
    Him: Yes, it's moving forward.
    Me: In practical terms, what's the difference between Realm-Local and... <blah blah>?
    Him: <Explanation>

    (so far so good)...

    An example of a conversation NOT to continue, cause it stops being perfectly smooth...


    Him (continues): Thus, when a multicast datagram enters the 6LoWPAN, the LBR is going to send it as Realm-Local.
    Me (dazed and confused):  Do you mean a datagram with a Global-Scope destination?
    Him: Yes.
    Me (dazed and confused): Eeeerm. What? Why would we change the destination address? Why not just forward it inside the 6LoWPAN with the same destination?
    Him: No no, you're not changing it. But the datagram doesn't have an MPL option.

    (Remember the image earlier. No MPL Option in the original datagram)

    Me: Why not just add the MPL option? (I should have known the answer but I didn't)
    Him: NO! You may not add extension headers en-route!
    Me: OK. Then what?
    Him: You encapsulate with IPv6-in-IPv6. The inner header stays as-is, the outer one uses Realm-Local destination.

    That was shock number one. Now to give credit where credit's due, the MPL ID is quite explicit about this scenario: "IPv6-in-IPv6 encapsulation MUST be used, hence the "I should have known" comment above.

    Let's try to expand the previous diagram to explain what I was thinking (top structure of network headers) and what "Him" was explaining (bottom).


    Fair enough, at the end of the day, as discussed in a previous post, Contiki currently doesn't implement either, so if we're gonna do it, we can always do it correctly right from the start... Or can we?

    But then I just had this Eureka moment: Haaaang on a minute. Wait wait wait. RPL also defines its own HBHO [RFC 6553] and the situation with incoming unicast datagrams is identical: They are not carrying the RPL HBHO.

    Therefore, I simply had to insist


    Me: Let's totally forget about multicast for a moment. Plain old unicast datagram sent from the internet. When the datagram is entering the 6LoWPAN, it needs the RPL HBHO and the border router adds it.
    Him: Noooope. You must do IPv6-in-IPv6

    Houston, we have a problem!


    Simply put, "Him" just told me we're not RFC-compliant... Once again, let's have a look at the usual diagram, this time modified for a unicast datagram entering the RPL network. Observe how I've replaced the MPL Option with the RPL Option.



    Despite the comedy value of the conversation, this last bit is an even more serious problem than the situation with MPL's HBHO. You see, we (Contiki) don't currently support incoming multicast datagrams, but we sure as hell support unicasts entering a RPL network. In a sense, it's better to not support a spec, than to support it in a non-compliant fashion. I like to think of Contiki as THE operating system for the IoT. Due to the embedded, super optimized way its TCP/IP stack has been implemented, I fear it would take a very considerable effort to implement IPv6-in-IPv6. Not to mention the code size and complexity increase.

    Me: Well, sorry, but IPv6-in-IPv6 with Contiki ain't gonna happen any time soon.

    I know that the people I was talking to can't be wrong about those things. Originally, I was hoping that they misunderstood the use-case I was trying to describe, or that I misunderstood what they were trying to explain to me.

    Nevertheless, the discussion prompted me to re-visit RFC 6553 (RPL Option), as well as draft-ietf-roll-trickle-mcast-08 (MPL's spec, including MPL Option). Having done so, it appears, dear reader, that they understood the question perfectly well and that I understood the answer perfectly well too...

    In other words, we just found out that Contiki is not as RFC Compliant as we might have liked it to be. If that's the case, we should probably open a bug in the issue tracker...

    Now blogs are about personal opinions are they not? Well, I know that this one is. Well, even though I'm a lot wiser now (thanks, "Him"), my personal opinion is not a lot different to what I said during the dinner in question:

    Me: Well, sorry, but IPv6-in-IPv6 with Contiki ain't gonna happen any time soon.

    The entire situation is a little bit of a mess. I can see why the RPL Option is useful. What I can't see is the need to over-complicate a spec that targets constrained environments, therefore also constrained nodes. RPL is becoming the de-facto standard for 6LoWPANs, and it's already complex enough. What I can't see is the need to harm it by introducing serious implications to its implementability for something that's no huge benefit.

    Happy coding!

    Saturday 12 April 2014

    Upstream Contiki goes multicast... More or less...

    After a fair bit of patience, my 6LoWPAN multicast implementation for Contiki has now been merged upstream. This is super cool, and I must admit I'm well chuffed!

    This means that now you can have a Contiki node join an IPv6 multicast group. You can then send a datagram to this multicast address from somewhere in the Internet, and the Contiki node will receive it. Right? Well, I'm afraid the answer is "No, not quite".

    You see, as I documented right from the start in Contiki's Pull Request #364, we currently only support multicast for traffic originating inside a 6LoWPAN and with a destination in the same 6LoWPAN. Multicast traffic cannot traverse the network's boundary in either direction.

    Within the 6LoWPAN, we currently have two options:
    1. Multicast group management with RPL in MOP3. Forwarding with SMRF (pronounced "Smurf"!) [1, 2]
    2. All multicast functionality with Trickle Multicast [3] (there is no group management as such). This is currently based on an old version of the MPL Internet Draft, which is why I'm intentionally using the name "Trickle Multicast" and not MPL.
    Thus, things inside the 6LoWPAN are pretty much sorted out. In order to be able to extend this functionality across the 6LoWPAN's boundary, we need a couple more components:
    • Some sort of mechanism to notify the outside world about group subscriptions of nodes inside the LoWPAN. This, in my humble opinion, can and should be done with MLD. As a Contiki contributor demonstrated recently, an embedded implementation of MLD won't be trouble in terms of code size and complexity.
    • The network's border router should be able to forward multicast traffic from the outside world to the 6LoWPAN and vice-versa. For reasons that I'm explaining in a separate post, this is not as straightforward as it may initially sound, and it's certainly more complex than simply forwarding an IPv6 datagram.
    • The network's border router should be able to conduct multicast routing on its internet-facing interfaces (in other words, outside the 6LoWPAN). The discussion of what protocols and mechanisms could be used for that is a wider topic on IPv6 multicasting and therefore out of scope of this post.
    I'll try to visualise this. Everything inside the dashed 6LoWPAN box is what we already have (points 1 and 2 above). We need more functionality on the BR in order to achieve the right-hand side of the figure, plus functionality to cross the 6LoWPANs boundary.
    R: A router somewhere in the Internet. BR: Our border router


    Naturally, all of the above is under the assumption of an IPv6-enabled Internet. But let's not discuss this right now.

    Thus, milestone achieved, but not quite there yet. Next up (in no particular order):
    • MPL implementation. This will update and eventually obsolete the current "Trickle Multicast" implementation.
    • Better forwarding in RPL MOP3 instances (I'm planning to publish this, so I'm not telling you how!)
    • MLD support
    Stay tuned

    References

    [1] G. Oikonomou, I. Phillips, T. Tryfonas, "IPv6 Multicast Forwarding in RPL-Based Wireless Sensor Networks", Wireless Personal Communications, Springer US, 73(3), pp. 1089-1116, 2013 [ doi ]
    [2] G. Oikonomou, I. Phillips, "Stateless Multicast Forwarding with RPL in 6LoWPAN Sensor Networks", in Proc. 2012 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops), Lugano, Switzerland, pp. 272-277, 2012 [ doi ]
    [3] J. Hui, R. Kelsey, "Multicast Forwarding Using Trickle", IETF Internet Draft (version 01) [ url ]

    Sunday 4 November 2012

    Contiki for the cc2531 USB Stick: At long last...

    As of a couple of days ago, the Contiki embedded Operating System for the Internet of Things will now run on TI's excellent cc2531 USB dongles (and by 'run' I mean 'properly, with USB support'). Currently, we can put the USB dongle in CDC-ACM mode but, with the backbone of the driver in place, I am hoping that support for other device classes will start appearing soon (I've already heard people mentioning HID and ECM).

    I successfully ran a 6LoWPAN border router on one of these little things and it's bloody fast, compared to standard UART-based approaches (e.g. a Sensinode n601 or a cc2530 EM on a SmartRF). Extremely unscientific tests show an average 30% RTT reduction when communicating (IPv6 ping) between the linux host and the USB stick. I'm sure I've saved those benchmarks somewhere...

    I also successfully ran a .15.4 sniffer on a USB stick. More on that in a future blog post, stay tuned!

    The USB code is largely based on a USB framework for ARM CPUs which pre-existed in the contiki source tree. Philippe Rétornaz (EPFL) made a bunch of adjustments to it so that it would play nicely with the cc2531. He also wrote the low level USB driver. I took all that and did a series of contikifications.

    The framework, driver etc are hosted in branch master of contiki's official github repo. If you are interested in further gory details, have a look at pull request #18 or commits 0e55eb0947..79cffa030f. As ever, in order to get proper 6LoWPAN functionality on those things without a gazillion crashes, you will need to use the cc-ports branch on contiki-sensinode.

    Some more information can be found on the contiki wiki, in the 8051-related pages (which I've only recently moved to the GitHub wiki over from the old location)

    As ever, feedback is invited and would be extremely appreciated.

    Monday 9 April 2012

    bibtexbrowser... Music for Publication Lists (Part II)

    Embed bibtexbrowser in your web page


    « Part I - A journey through the realms of boredom...

    In Part I of this post I shared my thoughts on personal publication lists and I documented my reasons for using Martin Monperrus' bibtexbrowser in my web page.

    The script is very simple to install and works off-the-shelf. However, with a bit of tweaking we can achieve better integration with the rest of our site. In this part, I shall share my experiences from customising it, hoping that it might help others who decide to use it.

    Modes

    We can run bibtexbrowser in 3 modes:
    • Stand Alone: When you directly invoke bibtexbrowser.php and let it generate an entire page. This will look like this or like this (frameset display).
    • Embedded: When you use it inside your own page and you get it to generate a section. A page like that can be seen here.
    • As a library: In this mode, it parses your bib DB and populates its data structures but it doesn't generate any HTML until you ask it to do so at a later stage. More on that later.

    Basic Configuration

    bibtexbrowser.php includes bibtexbrowser.local.php. This is your chance to override the default configuration and make local changes. So for example if you want to turn off Javascript progressive enhancement, you'd add the line below to your bibtexbrowser.local.php:
    define('BIBTEXBROWSER_USE_PROGRESSIVE_ENHANCEMENT',false);
    
    It's documented quite well here, so not a lot to say. It's being mentioned here cause we'll use it plenty later on.

    Embedded Mode

    This is also well documented in bibtexbrowser's page. Let's assume that you have a php script called pubs.php and you want to embed your publications list. You will do something like this:
    <?php
      $_GET['bib']='mybib.bib';
      $_GET['author']='Your Name';
      include( 'bibtexbrowser.php' );
    ?> 
    
    That's it. The only thing to do afterwards is write CSS styles to make the generated output looks like the rest of your page.

    Library Mode

    But in frameset mode there are great and handy authors, years, types and other menus on the left. Why can't I have them in embedded mode?

    If you browse through bibtexbrowser's code, you will see something about a 'New undocumented feature' (in version v20111211 this is near line 1746). In your embedding pubs.php script where you include bibtexbrowser, you can do this (notice line 1):
    $_GET['library']=1;
    $_GET['bib']='mybib.bib';
    $_GET['all']=1;
    include( 'bibtexbrowser.php' );
    /* We have included bibtexbrowser but it's not generated anything yet */
    
    setDB(); /* Read the bibliography and populate data structures */
    
    new IndependentYearMenu(); /* Generate the years menu */
    
    /* Do more stuff */
    
    new Dispatcher(); /* Generate bibtexbrowser HTML */
    
    This IndependentYearMenu() function generates the HTML for the year menu (it does, honest!). Remember, your bibtexbrowser.local.php is your friend. You can copy this function over from bibtexbrowser.php and modify it as you please. This is how I'm generating my custom authors menu:
    <?php
        class CustomAuthorsMenu {
            function CustomAuthorsMenu() {
                if (!isset($_GET[Q_DB])) {die('Did you forget to call setDB() before instantiating this class?');}
                $authorIndex = $_GET[Q_DB]->authorIndex();
                ?>
                <div id="authormenu" class="filterbox toolbox">
                    <div class="filterprop">
                        <a href="#authormenu" title="Expand/Collapse" onclick="toggle_toolbox('authorlist'); return false;">±</a>
                    </div>
                    <span class="this">Authors:</span>
                    <div class="filterlist" id="authorlist">
                        <?php
                        echo '<span><a '.makeHref(array(Q_AUTHOR=>'.*')).'>All</a></span>'."\n";
                        foreach($authorIndex as $author) {
                            echo '<span><a '.makeHref(array(Q_AUTHOR=>$author)).'>'.$author.'</a></span>'."\n";
                        }
                        ?>
                    </div>
                </div>
                <?php
            }
        }
    ?>
    
    Between setDB() and new Dispatcher() you can do whatever you like. So this is how I'm loading bibtexbrowser (in my pubs.php):
    <?php
        $_GET['library']=1;
        $_GET['bib']='geo.bib;authors.bib';
        $_GET['all']=1;
        include('bibtexbrowser.php');
    
        setDB();
    
        new CustomAuthorsMenu();
        new CustomYearMenu();
    ?>
    
    <div id="bodyText">
    
    <?php
        include('Template/conditions.php');
        new Dispatcher();
    ?>
    
    </div> 
    The process is similar for the years menu. The outcome can be seen here. Check out the author and year menus on the left.

    But, what about the search form?

    The form is generated by function searchView(), which doesn't get called in embedded mode. Similar process, we can copy it over to our pubs.php and modify it.
    <form action="?Academic" method="get">
        <div class="sortbox toolbox">
            <a href="#" onclick="toggle();return false;">Raw List / Grouped<br /></a>
            <a href="?Academic">By Type<br /></a>
            <a href="?Year">By Year<br /></a>
            <div class="search">
                <input type="text" name="search" class="input_box" id="searchtext"/>
                <input type="hidden" name="bib" value="geo.bib"/>
                <input type="submit" value="search" class="input_box"/>
            </div>
        </div>
    </form>
    
    Those of you who are observant will have noticed that, compared to the original:
    • I've replaced bibtexbrower's constants with hard-coded values. This is because I'm generating the form at the wrong position in the script, we can do it after including bibtexbrowser.php and keep the constants. I'll be changing that soon...
    • I'm putting the entire <div> inside the <form> and not the other way round. This is for XHTML 1.1 compliance. More on that later.

    Individual Publication Pages

    bibtexbrowser can also display an individual page for a publication, such as for example this one. If you look at this page's source, you will notice many lines like these:
    <meta name="DC.Title" content="A Model-driven Measurement Approach"/>
    <meta name="citation_title" content="A Model-driven Measurement Approach"/>
    
    These lines are my favorite bibtexbrowser feature: bibliographic metadata. The first one is Dublin Core, the second is google scholar metadata. The problem here is that if you run bibtexbrowser embedded, the script that generates the page's head is the embedding script, not bibtexbrowser. Bottom line, I advise against running individual pages embedded.

    An idea that I'm planning to have a stab at is to change the bibtexbrowser script so that when it encounters the argument key,  it will generate the metadata headers and COinS before bailing out. Then, the embedding script can call suitable methods, retrieve the values and add them to the generated page's head.

    XHTML 1.1

    bibtexbrowser generates valid XHTML 1.0 Transitional. That's great but that rest of my site is XHTML 1.1. If we try to validate the page as 1.1, we get the following error:

    Line X, Column Y: there is no attribute "name"
    <td class="bibref"><a name= " 2">

    The workaround to this one is simple, just change name="foo" to id="foo", like so:
    --- /Users/cexgo/Documents/spd.gr/bibtexbrowser.php.txt 2012-04-05 14:23:24.000000000 +0100
    +++ bibtexbrowser.php   2012-04-09 00:54:01.000000000 +0100
    @@ -1336,28 +1338,41 @@ class BibEntry {
       */
       function toTR() {
             echo '<tr class="bibline">';
    -        echo '<td  class="bibref"><a name="'.$this->getId().'"></a>['.$this->getAbbrv().']</td> ';
    +        echo '<td  class="bibref"><a id="id'.$this->getId().'"></a>['.$this->getAbbrv().']</td> ';
             echo '<td class="bibitem">';
             echo bib2html($this);
    
    We're not done yet. Even if the markup is valid XHTML 1.1, we need to make sure that page is served as such. When running in embedded more, things are easy since the headers are generated by our own script. In stand-alone mode though, this is what the server sends:
    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    <html xmlns="http://www.w3.org/1999/xhtml">
    <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
    
    We need to change the DOCTYPE and a few other bits and bobs. Although technically Content-type:text/html will work, according to the specs it may not be used and should be replaced by application/xhtml+xml. Here's how I've patched bibtexbrowser.php:
    --- /Users/cexgo/Documents/spd.gr/bibtexbrowser.php.txt 2012-04-05 14:23:24.000000000 +0100
    +++ bibtexbrowser.php   2012-04-09 00:54:01.000000000 +0100
    @@ -2878,13 +2916,13 @@ function HTMLWrapper(&$content,$metatags=array()/* an array name=>value*/) {
     
     // when we load a page with AJAX
     // the HTTP header is taken into account, not the <meta http-equiv>
    -header('Content-type: text/html; charset='.ENCODING);
    -echo '<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">'."\n";
    -
    +    header ("Content-Type:application/xhtml+xml; charset=utf-8");
    +    echo '<?xml version="1.0" encoding="UTF-8"?>'."\n"
     ?>
    -<html xmlns="http://www.w3.org/1999/xhtml">
    +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
    +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
     <head>
    -<meta http-equiv="Content-Type" content="text/html; charset=<?php echo ENCODING ?>"/>
    +<meta http-equiv="Content-Type" application/xhtml+xml; charset=UTF-8"/>
     <meta name="generator" content="bibtexbrowser v20111211" />
     <?php if ($content->getRSS()!='') echo '<link rel="alternate" type="application/rss+xml" title="RSS" href="'.$content->getRSS().'&amp;rss" />'; ?>
     <?php 
    
    A few more things to keep in mind. By default bibtexbrowser opens individual pages in the same window/tab. If you prefer using a new tab, you can override the default by adding this to your bibtexbrowser.local.php:
    define('BIBTEXBROWSER_BIB_IN_NEW_WINDOW',true);
    
    If you do that, you will find that some target="foo" will creep in the generated markup. The page will not validate against XHTML 1.1 with errors like this:

    Line X, Column Y: there is no attribute "target"
     …an</a>, George Oikonomou, "<a target= " _blank"

    I don't have a workaround for the target="_blank" thing since it's a feature that I'm never going to use, I just had to point it out since I noticed it. Lastly, keep in mind that the frameset version will not validate either, due to the differences in framing methods between XHTML 1.0 and 1.1. If you try to solve this, you are probably looking at quite a beast.

    Summary

    In order to better integrate bibtexbrowser with my publication list here, I made a few modifications and tweaks. I believe that bibtexbrowser is an excellent script. In this post I am sharing my observations, hoping to help those of you who want to exploit some of its cool features and who are curious enough to want to take things a few steps further than a vanilla installation.

    « Part I - A journey through the realms of boredom...