[Bug Smash] The Amnesiac ORAM: Fixing Oblivious RAM That Forgot Everything

This is a submission for DEV's Summer Bug Smash: Clear the Lineup powered by Sentry.

Project Overview

I've been working on Styx OS — a custom x86-64 microkernel I'm building completely from scratch. It handles everything from the bootloader up through a capability-based userspace. The whole philosophy behind Styx OS is that you shouldn't even trust your own hardware. So, it packs in features like FIDO2 pre-boot auth, TPM 2.0 attestation, and AES-256-XTS encrypted storage.

Recently, I decided to tackle an experimental feature: adapting PathORAM (Oblivious RAM) directly to physical USB storage.

Bug Fix or Performance Improvement

The Bug: The Amnesiac ORAM

So here's the idea behind PathORAM: even if your disk is completely encrypted, if an attacker can monitor which physical sectors you are reading and writing, they can still figure out what you're doing. PathORAM stops this by constantly shuffling data across the disk every single time you access it. To the outside world, your physical access pattern just looks like uniform, random noise.

I spent hours building the full algorithm. I had the position maps, the path eviction, stash management—everything. I wrote unit tests, and they all passed perfectly.

Then, I actually looked closely at my memory layout:

static oram_bucket_t oram_tree[ORAM_NUM_NODES];
static uint32_t      pos_map[ORAM_NUM_LEAVES];

Yep. The entire ORAM tree—the massive structure that was supposed to be shuffling encrypted blocks on my USB drive—was just a static array. Sitting in RAM. It wasn't touching my physical storage at all.

The math was beautiful, but the security? Non-existent. There was no USB bus involved, so there was no access pattern to hide. To make matters worse, because it was in RAM, every "securely stored" byte just vanished into the void the second I rebooted the machine. I had essentially built the world's most cryptographically complex volatile variable.

Code

To actually fix this, I had to rip out the in-RAM array entirely and wire every single read and write through my USB Mass Storage (usb_msc) driver so it mapped to physical Logical Block Addresses (LBAs).

You can check out the exact commit where I made the jump from RAM to physical disk here:
grsanudeep42-cmd/styxos commit adee0b7

Here is a look at the core diff:

--- a/kernel/oram.c
+++ b/kernel/oram.c
@@ -1,15 +1,22 @@
+/* USB sector layout for ORAM */
+#define ORAM_META_LBA    499U   /* single sector: magic + posmap header */
+#define ORAM_BASE_LBA    500U   /* start of tree: ORAM_NUM_NODES * ORAM_Z sectors */
+#define ORAM_POSMAP_LBA  1008U  /* position map: ORAM_NUM_LEAVES * 4 bytes */
+#define ORAM_MAGIC       0x4F52414DU  /* "ORAM" */
+
-static oram_bucket_t oram_tree[ORAM_NUM_NODES];
-static uint32_t      pos_map[ORAM_NUM_LEAVES];

+/* ── Physical USB I/O for ORAM ────────────────────────────────────────── */
+static void oram_read_block(uint32_t node, uint32_t slot, oram_block_t *out) {
+    uint32_t lba = ORAM_BASE_LBA + node * ORAM_Z + slot;
+    uint8_t  buf[512];
+    usb_msc_read_sector(lba, buf);
+    memcpy(out, buf, sizeof(oram_block_t));
+    g_oram_sector_reads++;
+}

+static void oram_write_block(uint32_t node, uint32_t slot, const oram_block_t *blk) {
+    uint32_t lba = ORAM_BASE_LBA + node * ORAM_Z + slot;
+    uint8_t  buf[512];
+    memset(buf, 0, 512);
+    memcpy(buf, blk, sizeof(oram_block_t));
+    usb_msc_write_sector(lba, buf);
+    g_oram_sector_writes++;
+}

My Improvements

Fixing this meant more than just swapping a RAM array for a disk write function. To make it survive a reboot and actually be secure, I had to completely overhaul the architecture:

1. Persistent Position Maps: The position map is now physically written to a dedicated USB sector (ORAM_POSMAP_LBA) after every access and reloaded when the OS boots. It finally remembers where it put things!
2. First-Boot Formatting: I added a startup check. If the kernel doesn't find the ORAM_MAGIC marker on the expected sector, it triggers a format phase—filling the disk sectors with dummy blocks and creating a fresh randomized position map.
3. CSPRNG Integration: I originally used a seeded LCG (lcg_rand()) for assigning leaves. But since that's deterministic, an attacker could guess the "random" leaf assignments and predict the access pattern. I swapped it out to use the kernel's cryptographically secure PRNG (csprng_u32()).

The Tradeoff:
To be completely honest, writing the position map to the USB drive on every single access is a massive I/O bottleneck. I prioritized absolute security and crash-consistency over raw speed. Journaling or batching these writes is the obvious next step, but for now, the bug is smashed and the data actually touches the metal.