3

Currently I'm analyzing the process of entropy generation of a Linux 64-bit kernel during system startup (for educational purpose). The system is hosted as/on a (64 bit) virtual machine (Xen domU). For a deep analysis, I'm tracking the state of relevant input parameters i.e. how those are processed. In function add_interrupt_randomness I found some code whose intention is not clear to me: The handling of cycles (value provided by CPU cycles counter) and now (jiffies). Both are unsigned 64 bit values, and processed as following:

c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
j_high = (sizeof(now) > 4) ? now >> 32 : 0;
fast_pool->pool[0] ^= cycles ^ j_high ^ irq;

So c_high/j_high (__u32) are assigned with the upper 32 bit of cycles/now and then assigned (after XOR) to the fast entropy pool. Hence a maximum variation of the values provided by c_high and j_high should be desirable?. But since c_high and j_high are based on cycles and now/jiffies, ,which are purely incremented variables, there is very little/no variation in the upper 32-bits as the traced values reveal:

Values in call no. 1 of add_interrupt_randomness:

cycles:0xFFFEA432A6C2CB89
c_high:0xFFFEA432
now_jiffies:0x00000000FFFEDB0A
j_high:0x00000000

Values in call no. 4265* of add_interrupt_randomness:

cycles:0xFFFEA43FBA85B313
c_high:0xFFFEA43F
now_jiffies:0x00000000FFFEE80C
j_high:0x00000000

*(startup is completed at this point)

During the system start add_interrupt_randomness is called 4265 times. The value of j_high is constantly 0x00000000, the value of c_high increments from 0xFFFEA432 to 0xFFFEA43F.
So my question is: why are the upper 32 bits processed instead of the lower, which would provide more randomness?

If interested: this is the complete definition of add_interrupt_randomness:

void add_interrupt_randomness(int irq, int irq_flags)
{
    struct entropy_store    *r;
    struct fast_pool    *fast_pool = this_cpu_ptr(&irq_randomness);
    struct pt_regs      *regs = get_irq_regs();
    unsigned long       now = jiffies;
    cycles_t        cycles = random_get_entropy();
    __u32           c_high, j_high;
    __u64           ip;
    unsigned long       seed;
    int         credit = 0;

    if (cycles == 0)
        cycles = get_reg(fast_pool, regs);
    c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
    j_high = (sizeof(now) > 4) ? now >> 32 : 0;
    fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
    fast_pool->pool[1] ^= now ^ c_high;
    ip = regs ? instruction_pointer(regs) : _RET_IP_;
    fast_pool->pool[2] ^= ip;
    fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
        get_reg(fast_pool, regs);

    fast_mix(fast_pool);
    add_interrupt_bench(cycles);

    if (!crng_ready()) {
        if ((fast_pool->count >= 64) &&
            crng_fast_load((char *) fast_pool->pool,
                   sizeof(fast_pool->pool))) {
            fast_pool->count = 0;
            fast_pool->last = now;
        }
        return;
    }

    if ((fast_pool->count < 64) &&
        !time_after(now, fast_pool->last + HZ))
        return;

    r = &input_pool;
    if (!spin_trylock(&r->lock))
        return;

    fast_pool->last = now;
    __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));

    /*
     * If we have architectural seed generator, produce a seed and
     * add it to the pool.  For the sake of paranoia don't let the
     * architectural seed generator dominate the input from the
     * interrupt noise.
     */
    if (arch_get_random_seed_long(&seed)) {
        __mix_pool_bytes(r, &seed, sizeof(seed));
        credit = 1;
    }
    spin_unlock(&r->lock);

    fast_pool->count = 0;

    /* award one bit for the contents of the fast pool */
    credit_entropy_bits(r, credit + 1);
}

from: https://elixir.bootlin.com/linux/v4.15.6/source/drivers/char/random.c#L1118

4

They are both processed.

Both cycles and now are mixed into the fast pool in their entirety. See the relevant lines:

fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
fast_pool->pool[1] ^= now ^ c_high;

In order to distribute randomness a bit, the number of CPU cycles* are mixed with the high bits of the number of jiffies, and the number of jiffies are mixed in with the high bits of the number of cycles. Even when this is happening, the full number of cycles and jiffies are inserted into the fast pool with the XOR operation. There is no c_low and j_low because those values are not lost. The low bits are added.

The fast pool is defined as:

struct fast_pool {
    __u32           pool[4];
    unsigned long   last;
    unsigned short  reg_idx;
    unsigned char   count;
};

The fast pool contains an array of four 32-bit values. The cycle counter, stored as cycles_t, may be a 64-bit value as it is defined as an unsigned long, so writing just the cycle counter to one of the pool elements will discard the high bits. This is not ideal, so the high bits are obtained separately and put in their own 32-bit integer which is then added to the pool on its own, in effect preserving the entire 64-bit value despite only being able to mix in 32-bits at a time. As you can see with the following two lines, if the two values already fit in a single 32-bit integer, the (non-existent) high 32 bits are set to 0:

c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
j_high = (sizeof(now) > 4) ? now >> 32 : 0;

The process is thus:

  1. If the variables are larger than 32 bits, save a copy of the high bits, otherwise set the copy to 0.
  2. Mix in the variables with the fast pool, discarding the high bits during integer conversion.
  3. Mix in the saved high bits, in effect "folding" the low and high bits into a single 32-bit integer.

* On some architectures, such as certain versions of MIPS, the cycle counter may not be available.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.