Boffin: Dump hardware number generators for encryption and instead look within

Chip timing could be as effective and harder to hack

man holding dice

Hardware-based random number generators (HWRNGs) for encryption could be superseded after a Philippines-based researcher found that side-channel measurement of the timing of CPU operations provide enough entropy to seed crypto systems with the necessary randomness.

In a paper presented on Saturday at the International Conference on Innovative Research in Science, Technology and Management (ICIRSTM) in Singapore, JV Roig, consulting director and software developer at Asia Pacific College (APC) in the Philippines, says that HWRNGs represent a natural target for subversion by national intelligence agencies due to their black-box nature.

Were a HWRNG to be designed to produce predictable (non-random) numbers, the resulting cryptography would be weak – a situation that numerous law enforcement agencies have sought or demanded.

Whether or not these devices have actually been compromised isn't the issue, Roig said in an email to The Register. "HWRNGs are, by nature, black boxes, unauditable, and untrustworthy, so they're out," he said.

The solution within

Roig's paper, "Stronger Cryptography For Every Device, Everywhere: A Side-Channel-Based Approach to Collecting Virtually Unlimited Entropy In Any CPU," claims that because no CPU has identical performance characteristics, true randomness is readily available.

"CPU execution time variance is the way forward, for all types of devices, from servers to IOT/embedded/appliances: run a trivial benchmark, time it, repeat," said Roig. "The accumulated timing info becomes your entropy, the source of your randomness."

He likens these measurements as flipping a coin multiple times to get enough bits of entropy, where each benchmark run counts as a flip. He calls the technique SideRand, and provides sample code written in C:

#include <stdio.h> 
#include <time.h> 
int main() {
  int i=0;
  int j=0;
  int samples = 256;
  int scale = 5000000;
  int val1 = 2585566630; 
  int val2 = 576722363; 
  int total = 0;
  double times[samples];

  for(i=0; i<samples; i++)
    {
      clock_t begin = clock();
      for(j=0; j<scale; j++)
      {
          total = val1 + val2;
      }
      clock_t end = clock();
      double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
      times[i] = time_spent;
      printf("%f\r\n", times[i]);
    }
    return 0; 
}

This code, straightforward enough to be easily auditable, should be suitable for older systems with microsecond-level clock precision. It accesses the system clock() function and collects timing information in an array.

The result is 256 timing value samples, which represent enough collected entropy to seed a cryptographically secure pseudo-random number generator (CSPRNG). The paper includes a variant algorithm for more modern systems capable of nanosecond-level precision.

Digital fingerprints

CPUs, Roig's paper explains, contain millions or billions of transistors, which have enough variation that no two chips perform identically. Chip designers may try to minimize transistor variances through guardbanding, but the situation has been getting worse over time, as noted last year in a paper by researchers at Lawrence Livermore National Laboratory.

Faced with this differences, chipmakers may resort to CPU binning – designating chips from the same batch with different characteristics as a different product lines, so they don't have to toss units that fall short of the spec.

Roig argues that the persistence of chip imperfections means timing measurements will be viable for the foreseeable future.

"Until we reach this level of technology, which does not seem to be on the horizon, and CPUs somehow revert back to having non-dynamic performance scaling features, the proposed side channel-based heuristic is likely to remain a good candidate for ubiquitous secure random number generation across all our CPU-powered devices," his paper says.

Timing measurements, Roig contends, can close the boot time entropy hole identified by Nadia Heninger and colleagues in 2012 and is simple enough to deter government agencies from trying to backdoor OS RNG seeding.

"This is how we can make sure every device, everywhere, has stronger cryptography," said Roig. ®

Sponsored: Becoming a Pragmatic Security Leader




Biting the hand that feeds IT © 1998–2019