# Conceal time-based GUIDs with an affine-cipher?

I'd like to create a custom type of sortable GUID by concatenating an 8-byte nanosecond timestamp, 6 random bytes, a 1-byte node number, and a 1-byte counter. But, such a precise timestamp can be used to enact very effective side-channel attacks if it can be related to the execution time of other cryptographic operations being done on the same system. It'd be ideal to conceal them in some invertible way, which is efficient, and where the concealed values maintain uniqueness.

Does the following operation securely conceal the GUIDs if an arbitrary amount of them are concealed in this way?

$$c \space \oplus \space ((a \cdot g_i \space + \space b) \mod \space p)$$

$$g_i$$ is a GUID interpreted as a positive big-endian integer

$$p = 2^{128} - 159 \space$$ (the largest 128-bit prime)

$$a$$ and $$b$$ are randomly selected constant positive integers $$< p$$

and, $$c$$ is a randomly selected constant non-negative integer $$< 2^{128}$$

Any insight or suggestions would be much appreciated!

• Is the goal of an adversary to find the whole of the $g_i$, knowing some (like 48 to 80) out of their 128 bits at fixed known positions, the matching $c\,\oplus\,((a\cdot g_i\,+\,b)\bmod p)$, and $p$?
– fgrieu
Commented Feb 16, 2023 at 6:40
• It's really just the lower 30 bits of the timestamp which should remain indeterminable, because timing knowledge with precision of about second is tolerable. Starting indexing at 0, those would be the 33rd most significant bit to the 63rd, of $g_i$. It would be ideal, but not crucial, if the least significant 16 bits of $g_i$ (the node number & counter) also remain indeterminable. Commented Feb 16, 2023 at 11:26
• @fgrieu: Yes, exactly. Commented Feb 16, 2023 at 15:51

I am Mallet. And I know the system.

Let's assume I can provoke transactions at ~ one-second intervals, and observe the resulting GUID integers. So that's $$g_i$$ incrementing at $$10^9 \pm \epsilon$$, pretty regular.

Now suppose I provoke the system-under-test at ~ two-second intervals, and then larger ones.

Some of my samples will exactly match $$10^9$$ seconds. Despite the XOR, I believe a pattern will fall out of the observations, revealing the constants, even $$c$$.

This is a little like Alvin Fernald inspecting a large number of retail tags in a department store and inferring the date and wholesale price fields.

Just use AES on GUIDs as they go out the door, storing them in an RDBMS. Then when you see them again, it's an easy indexed lookup to recover the timestamp. Postgres does a nice job of storing them in binary form.

Of course, if you're doing that you might as well have just sent random bits out the door, knowing that the index will order them nicely when they return to the roost. You can even precompute a bunch of GUIDs spaced at regular intervals, and peel them off as you need them, ignoring any that happened to expire.

What you really want is an ordering relationship.

The existing setup has a global variable: a clock that is NTP synchronized.

Discard that, in favor of a global counter. Increment it by some random draw from a Poisson process. (Yes, you will have to choose a $$\lambda$$ value.) Now Eve can see the happens-before relationship between GUIDs. Is that bad in your use case? There is (almost) no information about "delta time between transactions" revealed over short timescales.

You may wish to obscure your system's transaction rate. For example it may peak near lunch time and go quiescent at midnight. So pick some hourly rate that exceeds the actual peak, and ensure that the counter keeps up with that, even in the absence of real transactions arriving.

The handler of a transaction can either produce or consume a GUID that it is sending out the door. It focuses on the transaction, while another thread on a separate core worries about GUID bookkeeping and persistence. Given an in-memory queue it's easy for plodding throughput-oriented bookkeeping to keep up with bursty latency-sensitive transaction handling. Just keep a few extras in the FIFO queue, use double-buffering, whatever.

If the handler produces fresh GUIDs, enqueuing them in a queue with sufficient capacity, then the bookkeeper simply reads and persists them.

If the consumer consumes GUIDs from a fixed-capacity queue, the bookkeeper is always enqueuing another or blocked awaiting capacity. You might possibly care to discard "stale" ones after an idle stretch, or inject heart-beat transactions.

Kafka or the various Message Queue systems let the bookkeeper reside on a nearby host.

There's many options for persistence, so your use case will dictate the choice. You can use central or clustered Redis, in-core or with a disk log. There's SQL and NoSQL. Or fall back to the venerable filesystem.

In a similar "sharing work across threads" vein, AES is not expensive, it won't cost you latency! It will cost a background worker CPU cycles to fill a buffer with encryptions of some counter value, but then reading and XORing those bytes costs the transaction handler almost nothing, right? Just don't let the buffer run dry and you're OK. If you like, write 1 or 2 gig to the filesystem, and mmap() that file.

You have plenty of bits for collision resistance. If strict happens-before relationships are important to you, then you might want to allocate some bits for a guid-producer-id, e.g. {P1, P2, ..., Pn}. Then you can only do causality comparisons among GUIDs that came from the same producer. The nanosecond-timestamp scheme would be stuck with this, too, and we might talk about {C1, C2, ..., Cn} for the clock IDs. NTP is very nice, but there will still be some amount of skew which is trouble for causality inference.

• Thanks, @J_H! Because the timestamp is placed in the positions of most significant bits, an increment of a second translates to about $~10^{28} + \epsilon$. It seems $\epsilon$ here would be rather large, since both the nanosecond timestamp precision & 6 random bytes reduces the probability of provoking a precise $g_i$ interval. Then it's still unclear how the tester would determine the tests which successfully achieved the desired intervals. Commented Feb 16, 2023 at 12:13
• Sigh. I'm considering AES. But under test, AES is more than an order of magnitude slower. I'd also have to use a constant IV to maintain the desired uniqueness property of the permutation, the security properties of which is difficult to determine. Random bits, even uuid4s or Poisson selections, are of course good solutions which provide statistical collision resistance. That's simple enough. But the goal is to guarantee that no collisions will occur. That's why this dubious kind of permutation is being considered, because I know it produces unique outputs for all unique inputs < ~$2^{128}$ Commented Feb 16, 2023 at 12:47
• I really like the idea to precompute a cache of GUIDs. However, let's say the cache is drawn from so quickly that it becomes empty. Then there'd either be a wait time to refill the cache, or a new GUID can be created to side-step the wait time. In both cases, the GUIDs will still wind up having a create-time so close to the execution of the code calling for a GUID as to inherit the same vulnerabilities. Incrementing a global counter by a randomized, but uniform amount does seem like a good idea. There's synchronization & persistence overhead, but maybe that's suitable. I'll think on that. Commented Feb 16, 2023 at 13:15