Attempts at finding a new TCP sequence generator for uIP

Joachim Strömbergson Joachim at
Fri May 7 17:33:02 EDT 2010


uIP [1] is a very compact TCP/IP stack for small, networked connected,
embedded devices. (The code size for uIP including TCP and ICMP on the
AVR processor is about 5 kBytes.)

Unfortunately, the TCP sequence number generator in uIP is a bit
simplistic - basically a monotonically increasing number. In order to
reduce the opportunities for TCP Spoofing (like this nice one [2]) we
are trying to implement a new TCP sequence number generator.

What we want to find is an algorithm that generates a good (secure) TCP
seq numbers, but use very little resources (on 8-bit computing devices).

We have done some preliminary investigations, have some rough ideas and
would really appreciate comments and suggestions from the enlightened
minds on this list.

As we see it, the two main problems to solve are:
(1) Find a secure PRNG algorithm that have as low implementation
complexity as possible.

(2) Add as little system/application requirements on entropy source and
persistent storage as possible.

Looking at TinyRNG [3] for example, it seems that a block cipher in CTR
mode (or OFB mode) should be sufficient. The question then is what block
cipher to use? The XTEA block cipher [4] is very compact, but would it
be a wise choice from a security perspective?

But what to feed the PRNG with? Looking again at TinyRNG, it uses a
simplistic version of the entropy accumulator from the Fortuna PRNG [5],
but with fewer and smaller pools. The pools are processed using a
CBC-MAC built around the same block cipher as used in the PRNG.

The combined storage for the pools as well as CBC-MAC state would
probably be acceptable for uIP. The question is if the pool feeding
operation as such adds operational requirements on uIP that makes it
harder to integrate?

A simpler scheme could be to feed the PRNG (CTR-mode) with entropy
used as part of Key and IV, that is not use a pool mechanism at all
and leave it to user application to provide entropy words when
performing a reseed. The Key (and IV?) would also consists of a
counter that is monotonically increased.

The problem with this (we guess) is that in order to ensure that KEY+IV
is never reused is to keep at least part of KEY or IV as a counter that
is stored in persistent memory and increased once (and stored) every
time reseed (or boot) is performed. (How bad from a security perspective
would this be? Compared to other TCP sequence generators?)

The current version of uIP places few (basically no) demands on the
system/application regarding physical resources (besides mem for code
and data) and does not use any persistent storage besides code memory.
It seems that any good sequence generator that are driven by physical
entropy and tries to avoid sequence repetition need to place additional
demands on the system. No?

This is basically as far as we have taken this. More or less a bit of
Googling, reading and attempts at thinking. The ambition is not to
invent something new and unproven but to adapt existing tech and ideas
that seem to work. But get it to work with the size, performance and API
constraints of uIP.

Any thoughts, comments, suggestions and pointers would be very greatly

Thank you!
Joachim Strömbergson

[1] A. Dunkels. uIP TCP/IP stack.

[1] R. Lawshae. Picking Electronic Locks Using TCP Sequence Prediction

[3] A. Francillon, C. Castelluccia. TinyRNG: A Cryptographic Random
    Number Generator for Wireless Sensors Network Nodes

[4] R. M. Needham, D. J. Wheeler. Tea extensions.

[5] Wikipedia. Fortuna PRNG.

Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
Kryptoblog - IT-säkerhet på svenska
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list