Building a Truly Random Number Generator with Memristors and Gem5
In my previous post, I felt quite blocked by some limitations I encountered with simulating memristors in Gem5. I wasn’t able to find a real benefit to using memristors, at least in the way that I wanted and the way that Gem5 works.
Yet I still have research to do, and so I turned back towards academia to better understand what others have done. In particular, I began to read a lot of papers by Dr. Kvatinsky. He is a professor at the Israel Institute of Technology who has published extensively on memristors.
Often when I listen to music, I will go into the Spotify artist page and just listen to their entire discography. In this case, I went to Dr. Kvantinsky’s author page and downloaded all his papers.
He’s quite prolific, with 88 articles as a primary or secondary author. Admittedly I only had enough time to read 18 thoroughly. However, two of those papers sparked enough inspiration to move forward.
In particular, I was drawn to “Towards a memristive hardware secure hash function (MemHash)” published by both Leonid Azriel and Shahar Kvatinsky. In this paper, they propose using memristors as novel hashing hardware that can generate truly random numbers.
When I call Math.random() on a webpage, I do get a random number between 0 and 1. However, it is not truly random. It just appears random by running a function and incorporating some secret sauce that’s hard for someone to abuse. Memristors though, with each cell having unique and distinct microscopic material differences, can be used to incorporate randomness that an attacker cannot predict or clone.
Can I build my own truly random number generator using memristors? I’ll explain my research & development below.
Assembly Instructions
How should I start? Well I took a look at another paper: “STT-ANGIE: Asynchronous True Random Number GEnerator Using STT-MTJ”. The contents of the paper are a lot better than their attempts to create an acronym.
In this paper, Dr. Ben Perach and Kvatinsky (again) explain the basic circuit layout for a truly random number generator. The layout starts with a capacitor which gets charged up. Then the capactior discharges to N memristors, causing their resistance to change by an amount that is hard to predict (given the material imperfections). Finally, the values of those N memristors are read by N sense amplifiers and assigned a boolean TRUE/FALSE value. Then they can be concatenated together to form a single N-bit random number.
So there are three steps — three custom instructions that my CPU needs to perform to create a truly random number:
- Reset: Charge the capacitor to V_init
- Enable: Discharge the capacitor to N memristor cells
- Read: Use the amplifiers to determine which of the memory cells have been flipped
I can translate that into three instructions: trng.reset , trng.enable , and trng.read .
In my custom RISC-V toolchain, I have added those three to my riscv-op.c :
{"trng.reset",0, INSN_CLASS_I,"d,s,t",MATCH_TRNGRESET, MASK_TRNGRESET, match_opcode, 0 },
{"trng.enable",0, INSN_CLASS_I,"d,s,t",MATCH_TRNGENABLE, MASK_TRNGENABLE, match_opcode, 0 },
{"trng.read",0, INSN_CLASS_I,"d,s,t",MATCH_TRNGREAD, MASK_TRNGREAD, match_opcode, 0 },I need to determine the values of the MATCH_ and MASK_ . Since I’m using the same instruction format as before, the MASK_ values can all be the same. (Here I should acknowledge that I’m using the wrong instruction type, since reset and enable don’t actually need any parameters, and read only requires a destination register. But past experience made it easier to build the prototype.)
The MATCH_ values were configured to share almost all the same parameters as past instructions but with a one-off FUNCT7 so everything could be grouped together.
And so I can update riscv-op.h with my new values:
#define MATCH_TRNGRESET 0x8006027
#define MASK_TRNGRESET 0xfe00707f
#define MATCH_TRNGENABLE 0xA006027
#define MASK_TRNGENABLE 0xfe00707f
#define MATCH_TRNGREAD 0xC006027
#define MASK_TRNGREAD 0xfe00707f
// ...
DECLARE_INSN(trng_reset, MATCH_TRNGRESET, MASK_TRNGRESET)
DECLARE_INSN(trng_enable, MATCH_TRNGENABLE, MASK_TRNGENABLE)
DECLARE_INSN(trng_read, MATCH_TRNGREAD, MASK_TRNGREAD)Simulating RNGs
In my Gem5 decoder.isa , I added implementations for each instruction:
0x4: trng_reset({{
_sttMramTrng->reset();
}});
0x5: trng_enable({{
_sttMramTrng->enable();
}});
0x6: trng_read({{
Rd = _sttMramTrng->read();
}});I sought to formalize a lot of the behaviors by taking advantage of object-oriented programming. In previous work, I opened up bitfield.h and added new classes to represent each physical object.
static float C_HIGH = 20;
static float C_LOW = 0;
class Capacitor
{
public:
uint32_t farads;
float coulombs;
Capacitor() {
// Default
this->farads = 50;
}
Capacitor(uint32_t farads) {
this->farads = farads;
}
void setCapacitance(float coulombs) {
if (coulombs < C_LOW) {
this->coulombs = C_LOW;
} else if (coulombs > C_HIGH) {
this->coulombs = C_HIGH;
} else {
this->coulombs = coulombs;
}
}
void charge(float volts) {
// V = Q/C
// V*C = Q
this->setCapacitance(volts * this->farads);
}
float getVoltage() {
// V = Q/C
return this->coulombs / this->farads;
}
};
static uint32_t R_HIGH = 100000;
static uint32_t R_LOW = 1000;
class SttMtj
{
public:
uint32_t memristance;
uint32_t resistance;
SttMtj() {
// Default
this->memristance = 50;
}
SttMtj(uint32_t memristance) {
this->memristance = memristance;
}
void setResistance(uint32_t ohms) {
if (ohms < R_LOW) {
this->resistance = R_LOW;
} else if (ohms > R_HIGH) {
this->resistance = R_HIGH;
} else {
this->resistance = ohms;
}
}
void applyWrite(float volts) {
if (volts > 0) {
// Writing
uint32_t prob = rand() % 100;
if (prob < this->memristance) {
this->setResistance(R_HIGH);
} else {
this->setResistance(R_LOW);
}
}
}
bool read() {
uint32_t middleLine = (R_HIGH - R_LOW) / 2;
if (this->resistance > middleLine) {
return true;
}
return false;
}
};
static uint32_t memristances[] = {30, 40, 87, 70};
class SttMramTrng
{
public:
Capacitor cap;
SttMtj row[4]; // FIXME
uint32_t length;
SttMramTrng(uint32_t n) {
this->cap = Capacitor(50);
this->length = n;
for (uint32_t i = 0; i < n; i++) {
row[i] = SttMtj(memristances[i]);
}
}
void reset() {
this->cap.charge(5.0); // 5v
}
void enable() {
for (uint32_t i = 0; i < this->length; i++) {
this->row[i].applyWrite(5.0); // 5v
}
}
uint32_t read() {
uint32_t random = 0;
for (uint32_t i = 0; i < this->length; i++) {
// // Read each cell in a row to get final out.
random = random << 1;
if (this->row[i].read()) {
random |= 1;
}
}
return random;
}
};
static SttMramTrng __sttMramTrng(4);
constexpr SttMramTrng* _sttMramTrng = &__sttMramTrng;I hope you can understand what’s happening here. The capacitor charges up on reset. Then it writes that voltage to each memristor in our row (which has 4 memristors) by calling enable . Depending on the individual memristance, the resistance of each cell can be set to high or low resistance. Then the read method will combine everything into a single uint32_t .
I wrote a short program, trng.c , to demonstrate the behavior:
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
uint32_t truerandom(uint32_t* rng) {
bool p1 = 0;
bool p2 = 0;
asm volatile("trng.reset %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.enable %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.read %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
}
#define ITERATIONS 10
int main(void)
{
for (uint32_t i = 0; i < ITERATIONS; i++) {
uint32_t rng;
truerandom(&rng); // yo
printf("Iteration %i %i\n", i, rng);
}
return 0;
}The truerandom function defined here runs through each of the assembly calls and packages them into one function call. You can imagine that being part of a library that a developer would use.
Now let’s run it!
Iteration 0 3
Iteration 1 6
Iteration 2 7
Iteration 3 3
Iteration 4 7
Iteration 5 11
Iteration 6 7
Iteration 7 7
Iteration 8 11
Iteration 9 3Awesome! I’m getting random 4-bit numbers. Let’s run it again!
Iteration 0 3
Iteration 1 6
Iteration 2 7
Iteration 3 3
Iteration 4 7
Iteration 5 11
Iteration 6 7
Iteration 7 7
Iteration 8 11
Iteration 9 3Hmm. That doesn’t look too random. What’s going on?
I tried to debug by calling the C-lang rand() directly:
Iteration 0 1957747793
Iteration 1 1189641421
Iteration 2 2044897763
Iteration 3 1303455736
Iteration 4 336465782
Iteration 5 468703135
Iteration 6 1369133069
Iteration 7 1656478042
Iteration 8 608413784
Iteration 9 2038664370
...
Iteration 0 1957747793
Iteration 1 1189641421
Iteration 2 2044897763
Iteration 3 1303455736
Iteration 4 336465782
Iteration 5 468703135
Iteration 6 1369133069
Iteration 7 1656478042
Iteration 8 608413784
Iteration 9 2038664370Gem5 keeps generating the same numbers at the start of each run. I don’t think that’s supposed to happen.
A quick search landed me srand . Oh yeah, I should probably add a random seed before generating random numbers. The webpage suggested using srand(time(NULL)) since the number of milliseconds or microseconds will keep changing.
I updated my little program to print out some values:
srand(time(NULL));
printf("timeNull: %d\n", time(NULL));
/* srand example */
printf ("First number: %d\n", rand()%100);
printf ("Random number: %d\n", rand()%100);
srand(time(NULL));
printf ("Again the first number: %d\n", rand()%100);I got:
timeNull: 1000000000
First number: 51
Random number: 35
Again the first number: 51For some reason, the value of time(NUlL) is being fixed and I can’t get it to modify the seed in a non-determinstic way. Perhaps this is intentional, since Gem5 wants each simulation run to be identical. As such, I figured I should just move on to something more interesting.
Secure Enclave
Modern devices require security. Many have a “secure enclave” which can be used to run secure operations and store important secret keys out of the scope of a standard processor so that standard attacks won’t work.
When we talk about the Internet of Things (IoT), security is very important. You don’t want physical devices acting maliciously and causing real-world harm. However, these devices also have limited space and serious power constraints. Here is one domain where memristive hashing can be useful. These memory cells can be stacked more densely and use less power to perform operations. Since they are non-volatile, they’ll even work well in batteryless devices.
One basic task that a memristive security chip needs is the ability to hash and encrypt. While I was looking at existing security standards like FIDO, I didn’t have enough time in the last week to do a deep read. Instead, I settled for a simpler scrambler.
As all the hardware instructions have already been done, I don’t need to change much in Gem5 and wait half an hour for it to compile. All I did was make one simple change so that I use 16 memristors rather than just 4. This would enable me to generate 16-bit numbers, between 0 and 65536.
static float C_HIGH = 20;
static float C_LOW = 0;
class Capacitor
{
public:
uint32_t farads;
float coulombs;
Capacitor() {
// Default
this->farads = 50;
}
Capacitor(uint32_t farads) {
this->farads = farads;
}
void setCapacitance(float coulombs) {
if (coulombs < C_LOW) {
this->coulombs = C_LOW;
} else if (coulombs > C_HIGH) {
this->coulombs = C_HIGH;
} else {
this->coulombs = coulombs;
}
}
void charge(float volts) {
// V = Q/C
// V*C = Q
this->setCapacitance(volts * this->farads);
}
float getVoltage() {
// V = Q/C
return this->coulombs / this->farads;
}
};
static uint32_t R_HIGH = 100000;
static uint32_t R_LOW = 1000;
class SttMtj
{
public:
uint32_t memristance;
uint32_t resistance;
SttMtj() {
// Default
this->memristance = 50;
}
SttMtj(uint32_t memristance) {
this->memristance = memristance;
}
void setResistance(uint32_t ohms) {
if (ohms < R_LOW) {
this->resistance = R_LOW;
} else if (ohms > R_HIGH) {
this->resistance = R_HIGH;
} else {
this->resistance = ohms;
}
}
void applyWrite(float volts) {
if (volts > 0) {
// Writing
uint32_t prob = rand() % 100;
if (prob < this->memristance) {
this->setResistance(R_HIGH);
} else {
this->setResistance(R_LOW);
}
}
}
bool read() {
uint32_t middleLine = (R_HIGH - R_LOW) / 2;
if (this->resistance > middleLine) {
return true;
}
return false;
}
};
static uint32_t memristances[] = {
30, 40, 87, 70, 24, 13, 92, 51,
1, 68, 84, 22, 35, 18, 43, 77,
20, 30, 40,
};
#define MEMSIZE 16
class SttMramTrng
{
public:
Capacitor cap;
SttMtj row[MEMSIZE];
uint32_t length;
SttMramTrng(uint32_t n) {
this->cap = Capacitor(50);
this->length = n;
for (uint32_t i = 0; i < n; i++) {
row[i] = SttMtj(memristances[i]);
}
}
void reset() {
this->cap.charge(5.0); // 5v
}
void enable() {
for (uint32_t i = 0; i < this->length; i++) {
this->row[i].applyWrite(5.0); // 5v
}
}
uint32_t read() {
uint32_t random = 0;
for (uint32_t i = 0; i < this->length; i++) {
// // Read each cell in a row to get final out.
random = random << 1;
if (this->row[i].read()) {
random |= 1;
}
}
return random;
}
};
static SttMramTrng __sttMramTrng(MEMSIZE);
constexpr SttMramTrng* _sttMramTrng = &__sttMramTrng;Once this compiled, I was able to build my program.
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
char scrambleChars[] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', // 8
'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', // 16
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', // 24
'Y', 'Z', '0', '1', '2', '3', '4', '5', // 32
'6', '7', '8', '9', ' ', '-', '_', '=', // 40
'!', '?', '.', ',', '<', '>', '/', '@', // 48
'#', '$', '%', '^', '&', '*', '(', ')', // 56
'`', '~', '[', ']', '{', '}', '|', ':', // 64
};
uint32_t truerandom(uint32_t* rng) {
bool p1 = 0;
bool p2 = 0;
asm volatile("trng.reset %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.enable %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.read %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
}
void scramble(char msg[], char output[], uint32_t length) {
for (uint32_t i = 0; i < length; i++) {
uint32_t randIndex;
truerandom(&randIndex);
output[i] = scrambleChars[randIndex % 64];
printf("Scramble char %i: %c -> %c\n", i, msg[i], output[i]);
}
}
#define ITERATIONS 5
int main(void)
{
for (uint32_t i = 0; i < ITERATIONS; i++) {
uint32_t rng;
truerandom(&rng); // yo
printf("Iteration %i %i\n", i, rng);
}
char in[] = "Hello World";
char out[11];
scramble(in, out, 11);
printf("Scramble msg %s\n", out);
}I take the random numbers which are generated and use the modulus to pick a character from my character set. That allows me to scramble whatever input message I receive. Let’s run it!
Scramble char 0: H -> 9
Scramble char 1: e -> Z
Scramble char 2: l -> $
Scramble char 3: l -> ,
Scramble char 4: o -> 9
Scramble char 5: -> #
Scramble char 6: W -> ^
Scramble char 7: o -> ,
Scramble char 8: r -> 7
Scramble char 9: l -> V
Scramble char 10: d -> $
Scramble msg 9Z$,9#^,7V$For the input message “Hello World”, I get “9Z$,9#^,7V$”.
It should be noted this is not a bidirectional cipher. It can only go one way. The three “L”s in my message do not become a single character on the other side, and there are several “9”s which represent different characters. I don’t think it’d be possible to reverse this process and get “Hello World” back.
However, this can still be useful. A lot of hashes are one way, allowing us to take an insecure password and compare it against some stored hash before returning some secret value. So I wrote another function in my program which takes a user-input password and returns some secret value only if they guess the correct password. The secure enclave never stores this user-input password. It only knows a hash that, as we discussed before, cannot be easily cloned by an adversary.
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
char scrambleChars[] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', // 8
'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', // 16
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', // 24
'Y', 'Z', '0', '1', '2', '3', '4', '5', // 32
'6', '7', '8', '9', ' ', '-', '_', '=', // 40
'!', '?', '.', ',', '<', '>', '/', '@', // 48
'#', '$', '%', '^', '&', '*', '(', ')', // 56
'`', '~', '[', ']', '{', '}', '|', ':', // 64
};
uint32_t truerandom(uint32_t* rng) {
bool p1 = 0;
bool p2 = 0;
asm volatile("trng.reset %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.enable %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
asm volatile("trng.read %0, %1, %2\n":"=r"(*rng):"r"(p1),"r"(p2):);
}
void scramble(char msg[], char output[], uint32_t length) {
for (uint32_t i = 0; i < length; i++) {
uint32_t randIndex;
truerandom(&randIndex);
output[i] = scrambleChars[randIndex % 64];
printf("Scramble char %i: %c -> %c\n", i, msg[i], output[i]);
}
}
void getSecret(char msg[], char output[], uint32_t length) {
char hashedSecret[] = "96B(^7,7^?6";
char pwd[] = "MYPWD";
char noMatch[] = "ERROR";
if (strcmp(msg, hashedSecret) == 0) {
for (uint32_t i = 0; i < length; i++) {
output[i] = pwd[i];
}
} else {
// No match
for (uint32_t i = 0; i < length; i++) {
output[i] = noMatch[i];
}
}
}
#define ITERATIONS 5
int main(void)
{
for (uint32_t i = 0; i < ITERATIONS; i++) {
uint32_t rng;
truerandom(&rng); // yo
printf("Iteration %i %i\n", i, rng);
}
char in[] = "Hello World";
char out[11];
scramble(in, out, 11);
printf("Scramble msg %s\n", out);
char userInputPwd[] = "Hello World";
char hashInputPwd[11];
scramble(userInputPwd, hashInputPwd, 11);
char outputPwd[5];
getSecret(hashInputPwd, outputPwd, 5);
printf("Secure enclave returned: %s\n", outputPwd);
char userInputPwd2[] = "BadPassword";
char hashInputPwd2[11];
scramble(userInputPwd2, hashInputPwd2, 11);
char outputPwd2[5];
getSecret(hashInputPwd2, outputPwd2, 5);
printf("Secure enclave returned: %s\n", outputPwd2);
return 0;
}Now when I run my program, I get these results:
Iteration 0 12897
Iteration 1 31587
Iteration 2 45873
Iteration 3 45577
Iteration 4 31337
Scramble char 0: H -> 9
Scramble char 1: e -> Z
Scramble char 2: l -> $
Scramble char 3: l -> ,
Scramble char 4: o -> 9
Scramble char 5: -> #
Scramble char 6: W -> ^
Scramble char 7: o -> ,
Scramble char 8: r -> 7
Scramble char 9: l -> V
Scramble char 10: d -> $
Scramble msg 9Z$,9#^,7V$
Scramble char 0: H -> 9
Scramble char 1: e -> 6
Scramble char 2: l -> B
Scramble char 3: l -> (
Scramble char 4: o -> ^
Scramble char 5: -> 7
Scramble char 6: W -> ,
Scramble char 7: o -> 7
Scramble char 8: r -> ^
Scramble char 9: l -> ?
Scramble char 10: d -> 6
Secure enclave returned: MYPWD
Scramble char 0: B -> )
Scramble char 1: a -> ~
Scramble char 2: d -> 7
Scramble char 3: P -> ?
Scramble char 4: a -> $
Scramble char 5: s -> .
Scramble char 6: s -> 8
Scramble char 7: w -> !
Scramble char 8: o -> !
Scramble char 9: r -> ,
Scramble char 10: d -> 8
Secure enclave returned: ERROR
Exiting @ tick 5324111000 because exiting with last active thread contextYou can see that the secure enclave returns, upon the correct password, “MYPWD”. When a bad password or invalid input is sent, it returns “ERROR”.
Wrapping Up
I can, and probably should, wrap this up in some extra library finesse. I could return a data structure with a status field and error numbers. There’s a lot of software API design that goes into creating the best tools for software development.
Still, I hope this demonstrates a taste of what memristors can be used for. A larger secure enclave mechanism entirely built of memristors could store a bunch of keys through standard memory operations. Then, by taking advantage of in-memory computing, you can run hash operations with a limited amount of hardware all while reducing total area and power consumption.
Is this method totally secure? Maybe not. Perach discusses risks of magnetic attacks, and Azriel notes the “differential read scheme makes modeling attacks on MemHash unlikely” but not quite impossible. But my preliminary work suggests it might be a bit more secure than the current standard.
Future work, if this line of research makes sense, will probably investigate more realistic secure applications while also considering improvements to the underlying models.
