Finite Field Arithmetic



Some source code for finite field arithmetic.


Montgomery Multiplication in Finite Fields
  • Montgomery Multiplication in the field GF(2^8) [Source Code]
  • Bit serial Montgomery Multiplication in the field GF(2^233) [Source Code]


Composite Field Isomorphisms

The AES s-box provides the non-linearity in the cipher. It is defined as follows: S(x) = xinv + A
  • A is a affine transformation.
  • xinv is the inverse of x in the finite field GF(2^8). This means that (xinv * x)mod P = 1, where P is the irreducible polynomial of the field. 
Finding xinv in hardware could have significant area requirement, so developers often use composite fields, which decomposes large arithmetic into smaller ones.  For instance a composite field for GF(2^8) is the field GF((2^4)^2), which breaks down 8 bit arithmetic to 4 bit arithmetic. The requirements is that such a composite field needs to be found.

The source code available here shows how a composite field can constructed [Source Code].
The algorithm is taken from Christoff Paar's PhD thesis.


ECC over Optimal Extension Fields (OEF)

OEF field arithmetic is implementation friendly on microprocessors. This code has an implementation of Elliptic curve cryptography over OEF [Source Code].
Three OEF fields are supported. Refer to the SEC X.2 recommendations.

bash terminal


  • To clear the scroll buffer completely  
tput reset



  • To change from one virtual terminal to another, you generally use shift+alt+Fx, where x is 1, 2, 3, .... On a system without graphics, you can also achieve this by the command line


chvt x
where x is 1,2,3, ...



Disable Hardware Prefetching in Intel Microprocessors

Prefetchers are built to predict the data that is going to be accessed by a program and automatically load the data into the cache memory, before the program actually requires it. Sometimes predictions can be woefully wrong, and affect the program's performance. So programmers need to test their programs with prefetching disabled.

There are two ways that prefetching can be disabled:

1. From the BIOS: On certain systems (mostly servers) the BIOS allows prefetching to be disabled. This is the easiest way to get the deed done.

2. Using MSR Registers: Model specific registers in Intel processors allow vital micro-architecture configurations in the processor to be viewed and modified.
I have a previous blog which shows how MSR registers can be accessed in a previous post (http://arbidprobramming.blogspot.in/2010/04/programming-intels-model-specific.html).

On an Intel i3, MSR 0x1a0 has 4 bits that deal with prefetching:
  • Bit 9: Hardware Prefetcher Disable
  • Bit 19: Adjacent Cache Line Prefetch Disable
  • Bit 37: DCU Prefetcher Disable
  • Bit 39: IP Prefetcher Disable
On AMD Family 10h processors, MSR 0xC0011022 bit 13 needs to be set to disable prefetching
 Setting any of these bits to 1 will disable that prefetcher.

However, from Nehalem onwards, Intel has disabled the option of controlling  prefetching from the MSRs, the BIOS seems to be the only way then. I'm not sure how prefetching can be disabled if the BIOS does not provide an option :(






Keeping Your Ubuntu Up-to-date

To automatically get your Ubuntu up-to-date with the latest upgrades, its a nice idea to place apt-get in crontab.

This can be done as follows:


1. sudo crontab -e
copy this into the file.

30 22   *   *   *    /update-script


2. sudo vim /update-script
and paste this in the file

echo "***************************************" >> /tmp/update.log
date >> /tmp/update.log
echo "......................................." >> /tmp/update.log
apt-get update >> /tmp/update.log
apt-get -y -q --force-yes upgrade >> /tmp/update.log



The first step adds an entry in crontab which will run a script called update-script every day at 10:30PM

The second step is to create the update-script which updates all software in your system. The log of the updates is appended in the file placed in /tmp/update.log.



Getting Started with Fiasco-UX on Ubuntu 10.04

Fiasco-UX is a port of Fiasco which can run as a user mode application in Ubuntu 10.04. That is to say, it does not require to be in privileged mode. It is an ideal way to start off working with L4/fiasco. This blog shows how to get it running on an Ubuntu machine on Intel Core 2 Duo.

1. Download l4re-core from this site: http://os.inf.tu-dresden.de/download/snapshots-oc/, and untar it of course. I have downloaded l4re-core-2012081219

2.  Run make setup and then make. Assuming you have a reasonably updated ubuntu 10.04, with gcc tools etc, there should not be any problem here. However it does take an awfully long time to build as a lot of other stuff too gets compiled, which is not needed for our work.

3. In the directory obj/fiasco/ux, run the following command
./fiasco -I ./irq0 -S ../../l4/x86/pkg/sigma0/server/src/OBJ-x86_586-l4f/sigma0 -R '../../l4/x86/pkg/moe/server/src/OBJ-x86_586-l4f/moe --init=rom/hello' -l ../../l4/x86/bin/x86_586/l4f/l4re -l ../../l4/x86/bin/x86_586/l4f/hello 
This should get your fiasco-UX rolling
---------------------------------------------------------------------------------------------------------------------------------


All About the Cache Memory in Linux

For Linux users, a lot of information about the cache memory is available in
the directory '/sys/devices/system/cpu/cpuX/cache', where 'X' is the core number (takes values 0,1,2,...).

Here I discuss the entries present in this and subdirectories.

1. indexN 
    - There can be several directories of the form index0, index1, index2, and so on. Each directory represents a cache that is visible from the cpu core (cpuX).

2. indexN/coherency_line_size
   - This contains the cache line size (generally 64 bytes)

3. indexN/level
   - Contains the cache level (ie. either 1 for L1, 2 for L2, or 3 for L3)

4. indexN/number_of_sets

5. indexN/shared_cpu_list
    - Contains the list of cpus that share this cache memory

6. indexN/shared_cpu_map
    - Contains a bitmap of the cpus that can access this cache memory

7. indexN/size

8. indexN/type
    - Can be either data, instruction, or unified.

9. indexN/ways_of_associativity
     

Get Your Program to Execute on a Specific CPU

Most systems these days have multiple cores.
In linux you can determine how many cores are present from
the following file

$ cat /proc/cpuinfo

Each core will have an entry and will be labeled starting from 0.
(in my quad core the core's are
processor 0, processor 1, processor 2, processor 3)

When you execute  a program it gets scheduled into any one of these
processors. In case you want to specify which processor you want your
program to run, then use the sched_setaffinity call.

A simple example for using this call is shown below:



int main(int argc, char **argv)
{
    unsigned long mask;
    mask = 0x2;
    if (sched_setaffinity(0, sizeof(mask), &mask) <0) {
        perror("sched_setaffinity");
    }
    sleep(1000);
}

You may have to include 'sched.h'  to get it to compile

The mask will tell which processors the program can execute in.
For example a mask of 0x2 (in binary : 0010) means processor 1.
Similary a mask of 0x1 (0001) means processor 0.

You can check which cpu is executing your program by
running top and then pressing 1.








Flush out an array from the cache on Intel Processors

The following C code flushes out the table from all caches. It works on Intel Core 2 Duo and above and doesn't work on Pentium 3. I haven't checked on Pentium 4.

#define CACHE_LINE_SIZE    64
unsigned char table[256];

void clean_tables()
{
    int i;
    for(i=0; i<256; i+=CACHE_LINE_SIZE){
        asm volatile("clflush (%0)" :: "r" (table+i));
    }
}

Disable interrupts from user space

Example Code





int main (int argc, char **argv)
{
    iopl(3);        // Go to the privileged level

    asm("cli");  // Disable interrupts

    /* Code goes here  (Make sure this part is as small as possible) */

    asm("sti");  // Enable interrupts
}


IMPORTANT: This code should be run with superuser privileges

The header file 'sys/io.h' must be included for iopl

Measuring Timing Accurately on Intel Processors

This blog shows how timing measurements for C code can be made accurately. The output is in clock cycles.


1. The timing is measured by using the 'RDTSC' instruction, which returns the processors timestamp value. This value is maintained in a register and incremented at every clock cycle.

2. However, due to the out-of-order execution of the processor, it is not certain when the RDTSC instruction is actually executed. Therefore, we flush the processor's pipeline before and after invoking RDTSC. This ensures that every measurement begins in the same state. The flushing of the pipeline is done by the CPUID instruction.

The code snippet:


unsigned int timestamp(void)
{
    unsigned int bottom;
    unsigned int top;
    asm volatile("xorl %%eax,%%eax\n cpuid \n" ::: "%eax", "%ebx", "%ecx", "%edx"); // flush pipeline
    asm volatile("rdtsc\n" : "=a" (bottom), "=d" (top) );                           // read rdtsc
    asm volatile("xorl %%eax,%%eax\n cpuid \n" ::: "%eax", "%ebx", "%ecx", "%edx"); // flush pipeline again
    return bottom;
}


int main()
{
    unsigned int t1, t2, to1, to2, tover;

    /* Measure the overhead first */ 
    to1 = timestamp();
    to2 = timestamp();
    tover = to2 - to1;
   

    t1 = timestamp();
    /**** Code to be measured goes here *****/
    t2 = timestamp();
    printf("Time Taken (in clock cycles) : %ul\n", (t2 - t1 - tover));
}

pfmon on Ubuntu 9.04

In this blog, I write about my experiences getting pfmon to run on my system (Intel Core 2 running Ubuntu 9.04).


1. The first step is to patch the kernel with perfmon2.
  • I First checked the most recent kernel patch that is supported by perfmon2. You will be able to find this in http://perfmon2.sourceforge.net. In my case it was 2.6.28 2nd release.
  • I installed the kernel (2.6.28) the old fashioned way (without git). I first installed the necessary packages required for building kernels, and then downloaded the kernel with instructions from https://help.ubuntu.com/community/Kernel/Compile.
  • I then patched the kernel with the perfmon2 patch I downloaded. Instructions for patching the kernel were from http://www.linuxheadquarters.com/howto/tuning/kernelpatch.shtml. There was a bit of a problem with the patching since I used a kernel from the Ubuntu distribution and not the original kernel.org kernel (for which the patch was made). These problems were easily rectified by manually (and carefully) patching the files which gave errors.
  • ... and rebooted  to the new kernel :)

2. The second step is to install libpfm and pfmon
  •  Although Ubuntu's package manager supported it. The versions of pfmon present in Ubuntu conflicted with the kernel patch I had installed. So when I ran the command
                   $ pfmon date
         I got the error

                     can't create perfmon context: Invalid argument(22)

  • I then realized that for the 2.6.28 patch, I needed libpfm 3.8 and pfmon 3.8. So I downloaded these from  http://perfmon2.sourceforge.net and installed them. First installed the libpfm and then the pfmon.
  • It now works :) :). The command '$pfmon date' gives
                     Wed Apr 28 13:53:52 IST 2010
                     760973 UNHALTED_CORE_CYCLES

Programming Intel's Model-Specific Registers (MSRs)


Model (or sometimes called Machine) Specific Registers (MSRs) are a useful tool during debugging to determine the working of the processor. They can also be used to control the functioning of the processor such as the working of the cache memories, branch prediction logic etc.


Accessing MSRs

To access the MSR registers, there are two requirements.
  1. The kernel must support it.
  2. A user space application must be required to communicate with the kernel
The MSR Driver
For the Linux kernel, a module msr is to be present.

To check if your kernel has MSR support built in :

            $ cat /boot/config-2.6.28-18-generic | grep MSR
               CONFIG_X86_MSR=m 

On my Ubuntu 9.04, the MSR is a module. I added it to
the kernel with the command:
            
           $ sudo modprobe msr

Inserting the module would create the device files /dev/cpu/_processor_number_/msr. There would be one msr device for each processor.

User Space Access (msr-tools)
msr-tools can be downloaded from the kernel.org site http://www.kernel.org/pub/linux/utils/cpu/msr-tools/msr-tools-1.1.2.tar.bz2. If you are using Ubuntu, msr-tools can be installed using the package manager.

msr-tools have two executables:
rdmsr : This is used to read an MSR register.

            $ sudo rdmsr 0x198 
               6160b2406000b24       

wrmsr : This is used to write to an MSR register
  
            $ sudo wrmsr 0x198 6160b2406000b24



The MSR Registers
The MSR registers for the Intel Processor is present in the Appendix B of Intel® 64 and IA-32 Architectures Software Developer's Manual Volume 3B: System Programming Guide



References
  1. http://blogs.koolwal.net/2009/09/19/howto-using-cpu-msr-tools-rdmsrwrmsr-in-debian-linux/

Followers