Introducing EuCrypt

EuCrypt is a self-contained library that Eulora server will use for its communication needs. EuCrypt has the following 5 main components:

  1. smg-comm – the implementation of the basic client-server communication protocol. This makes use of all the other components, namely:
  2. smg-serpent – the symmetric cipher that is used by smg-comm for everyday message exchanges between Eulora clients and server.
  3. smg-keccak – the implementation of the keccak function and sponge construction, used by smg-comm mainly as part of the data padding scheme.
  4. smg-rsa – the implementation of the RSA encryption algorithm using a source of true randomness and the sane-mpi implementation of big number arithmetics:
  5. sane-mpi – the implementation of big number arithmetics, as extracted from GnuPG 1.4.10 by Stanislav Datskovskiy.

The above structure is only meant to give you a high-level, top-down idea of what EuCrypt is made of. However, to actually understand EuCrypt at all1, you’ll need to read the code and discussion for each of the above components and so I will start from bottom-up with the code + discussion of sane-mpi and then proceed to add parts and pieces until we get the whole library. Note that some of the components above are bigger than others and therefore I will split the discussion of those in several installments, so expect overall more than 5 posts on this. Comments and questions are welcome at any time and on any of the parts, so don’t be shy.

Chapter 1: sane-mpi

This component is implemented in C and offers support for storing and working with arbitrary large integers (multi precision integers or MPIs as we’ll call them from now on). The code is rather messy but at the moment there isn’t really anything better available and as it stands, this sane-mpi is at least readable now – mainly through the efforts of Stanislav Datskovskiy who extracted it from the big ball of mess that is GnuPG 1.4.10. I’ve made only a small further snip to his version, discarding a set of methods for accessing specific parts of an MPI. While such methods could conceivably be useful at some point, the point is that EuCrypt at the moment does *not* need them and moreover the existing implementation was so ugly as to need a re-write in any case. In short those parts failed to be either useful or at the very least sane, so they are no more.

There are lots of very useful comments all through the code of sane-mpi so the best option is really to actually read each file, at least once. There’s no point in repeating those comments in here. I’ll focus instead on a few aspects that I think are most relevant to EuCrypt and its purpose.

First issue is related to how and where MPIs are stored, because EuCrypt uses MPIs for storing private RSA keys. In principle, sane-mpi offers methods for allocating secure memory for any given MPI (see secmem.c and memory.c). However, a correct description of the service is that sane-mpi will attempt to allocate secure memory, with results depending on the machine and operating system you are running it on.

Note also that it pays to be mindful when performing operations with MPIs that are a mix of secure and insecure since undesired leaks may happen at intermediate steps. Sane-mpi attempts to avoid this by allocating additional secure memory space for intermediate results when one of the operands is in secure memory (see for instance mpi_mul method in mpi-mul.c). However, this (among others) means also that a simple arithmetical operation involving 2 MPIs will actually differ in execution depending not only on the values of the 2 numbers but also on where they are each stored. Moreover, this sort of side-effect memory allocation happens in fact in more than one place in sane-mpi.

Second issue refers to the way in which MPI operations are implemented in sane-mpi. Essentially following the implementation of one single arithmetical operation is not always very straightforward as it can easily lead one through several files (even when leaving aside the side-effect memory allocation issues and focusing instead only on the actual operations performed). From the point of view of fully and comfortably holding sane-mpi in head, this is rather unfortunate but it is what it is.

Since EuCrypt uses by necessity not only the multiplication and exponentiation but also direct bit setting of MPIs, I’ll highlight mpi-bit.c as another file that should be studied in more detail. In particular, the method mpi_set_highbit can be confusing as it does a bit more than the name suggests: it sets the indicated bit but it ALSO clears all bits above the one indicated. Similarly, mpi_clear_highbit clears the indicated bit AND all bits above it. By contrast, mpi_set_bit and mpi_clear_bit are the more straightforward versions, simply setting or clearing, respectively, the indicated bit and nothing more.

To download, build and test sane-mpi as will be used in EuCrypt you will need:

If you need help with V, there are is a gentle introduction courtesy of Ben Vulpes.

In the next chapter I’ll proceed to introduce parts of EuCrypt’s own RSA that puts all this sane-mpi to some actual use. Stay tuned!



  1. Note that you will be effectively trusting this library with your data and money whenever you play Eulora so better understand it before playing the game. 

Categoria: Coding | Lasati un comentariu

RSS Subscribe to Ossasepia


Recent comments: