Tillsammans med Adam Dunkels har jag börjat titta lite försiktigt på att hitta en bättre generator för TCP-sekvensnummer till den miniskula TCP/IP-stacken uIP.

Adam Dunkels – pappa till uIP, bland annat.

Den nuvarande generatorn ger en monotont ökande sekvens som är lätt att prediktera. En ny generator skall ge en bra slumpmässig som inte är lätt (inte går) att prediktera. MEn samtidigt får storleken på stacken inte växa speciellt mycket och skall gå att implementera på en 8-bitars processor. Vidare får vi inte inför en massa nya krav på målsystemet, exempelvis tillgång till bra fysisk entropi. En icke-trivial kombination av krav.

Jag har tänkt, kladdat och sedan postat på Cryptography-listan och fått en del tips. Men jag (vi) tar med stor glädje emot mer klokskap. Här kommer därför min postning till listan. Läs, kommentera. Tack!

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 appreciated.

Thank you!
Joachim Strömbergson

References
—————

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

http://www.sics.se/~adam/uip/index.php/Main_Page

[1] R. Lawshae. Picking Electronic Locks Using TCP Sequence Prediction
http://www.defcon.org/images/defcon-17/dc-17-presentation/Ricky_Lawshae/defcon-17-ricky_lawshae-picking_electronic_locks-wp.pdf

[3] A. Francillon, C. Castelluccia. TinyRNG: A Cryptographic Random

Number Generator for Wireless Sensors Network Nodes

http://planete.inrialpes.fr/~ccastel/PAPERS/TinyRNG.pdf

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

http://www.cix.co.uk/~klockstone/xtea.pdf

[5] Wikipedia. Fortuna PRNG.

http://en.wikipedia.org/wiki/Fortuna_%28PRNG%29