[Cryptography] XOR linked list & crypto

[Jon Callas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


> 
> More security through obscurity, no?
> 

No, it isn't security through obscurity.

Security through security is typically a shorthand for a claim that something is secure because the design of the system is unknown. The strong antithesis of security through obscurity is Kerckhoff's principle that the secrecy of a system should be minimized. In cryptography, we typically say that we want only the key to be secret.

This is just an obscure implementation, that isn't supported by dev tools, etc. If it had become fashionable, it might be normal to us. There's no reason why tools couldn't support it, or hardware couldn't support it or whatever.

There are a lot of reasons why we do lists using the naive implementation of having the "next" and "previous" slots in the object to be the absolute pointer of the elements in the list. For one thing, you can just go look at the memory and see where it is.

But there are plenty of places where lists were done differently, as well.

Assume a naive doubly-linked list where a data structure by convention has as its first two slots the next and previous pointer. Note that a solitary element really ought to have its next and previous pointer being the address of the element itself. We can define an operation INSQUE and REMQUE that insert and remove an element from the queue. Very simple, and very powerful.

But let's suppose you want to do this in shared memory -- where two processors share some but not all memory. Modern multi-CPU systems share all memory, and they number it the same. In our system, let's suppose we want to have a co-processor that does crypto, and the start of this shared section may not have the same base address.

You can easily modify the previous system to use the offset rather than the pointer.

So foo.next is not &bar, but it's (&foo - &bar). It's still pretty easy to work with because  instead of saying

next = foo.next

you just say

next = foo[foo.next]

(Or something equivalent. Strictly speaking in the pseudo-C I just wrote, I've implicitly assumed that all the pointers are (unsigned char *) and I really should have defined it to be &bar - &foo for the offset, or used "foo[-foo.next]" in my fetch function. I did all of that for naive readability)

And foo.previous gets handled similarly.

In my shared memory, I also want to have an interlock so that I don't get race conditions where both processors munge the things at the same time. I also really need to have separate ways to handle inserting and removing at the head and tail of the queue, as well. So I end up having INSQHI/REMQHI and INSQTI/REMQTI for handling these self-relative queues. And note that conveniently, the lone element has zeros in its default slots.

But -- there's no reason I have to use subtraction. I could use XOR. I can store &foo ^ &next for the next pointer and &foo ^ &prev pointer. I can even observe that if I store only one thing -- &next ^ &prev, then as long as I know &foo, I can collapse the two pointers into one.

It's just confusing, and long ago, we decided that understanding is worth spending the extra slot in the data structure. It's also slower to do, because you're always doing a lot of math whenever you play with an element.

But you could do the whole thing in hardware -- make instructions for INSQUE and REMQUE as well as the interlocked ones. People even did that long ago. But they didn't optimize it into the XOR because -- well, it's not worth it we all agreed.

	Jon



-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.3.0 (Build 9060)
Charset: us-ascii

wsBVAwUBVsYxBfD9H+HfsTZWAQjNpQf/Ym+0OG7LSx2EpIUkJvV2BwzkhysQ4xTN
MqSO5/HD2V5Iq5rOfI2pn/G0eoz2cvOKPxJHXw6gxY4y8c9qRADOqqW/fNDQQUT9
1JQWuFomY8H/zjyM+F9ikELSi/XnZRI4VMKvop2V7JFuvz4Mjs3EljINs+1g+t55
GCIUi+ILxAtRviZBA497odYXMOVKmrzAmm88otOakeYgAvZitm2I5EAcZ7B43LvT
jOYpCxySYjv15+TlAL1TLajJDuV+c1+qtxV/WJAIJBQcJcdx+zpXfsL/fkHK43UG
a3ULcA1Coxi2Gd0vIlr45y5ZbuM95QLop/mW3UPg1WQVEaqN+bHmRQ==
=BSZk
-----END PGP SIGNATURE-----