[Cryptography] How to lock registers with GCC?

tpb-crypto at laposte.net tpb-crypto at laposte.net
Thu May 15 13:20:07 EDT 2014


Mods,

I know it is against the rules to write very long messages, but I'm merely reposting the messages you have pre-approved in order to answer them in bulk and keep things organized in this thread. So, it is one answer to all messages instead of one answer per message, which would be messy in this topic. Please, let us make an exception for this.


Below all messages, is my answer to them separated with this line:

+++++++++++++++++++++++++++++++

-------------------------------

> Message du 10/05/14 03:30
> De : "Tom Mitchell" 
> A : "Nemo" 
> Copie à : tpb-crypto at laposte.net, "cryptography at metzdowd.com" 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> On Fri, May 9, 2014 at 9:29 AM, Nemo  wrote:
> > tpb-crypto at laposte.net writes:
> >
> >> Is it possible to give a directive to GCC while compiling and/or does
> >> it support some macro/routine/directive/library/whatever, that would
> >> allow to load values into processor registers and then lock one or two
> >> registers, which would become unchangeable? Performance
> >> notwithstanding.
> >
> > GCC supports global register variables:
> >
> > http://gcc.gnu.org/onlinedocs/gcc/Global-Reg-Vars.html
> 
> Thanks for this link.... I did not know it existed.
> There is a nice long list of cautions so it looks
> as if a key is sizeof(register) it is possible.
> 
> Registers are rare enough that this is sort
> of going "up the down stair case" i.e. Easy except
> when class gets out.
> 
> 
> 
> 
> -- 
> T o m M i t c h e l l
> 

-------------------------------

> Message du 10/05/14 01:19
> De : "Steve Weis" 
> A : tpb-crypto at laposte.net
> Copie à : "cryptography" 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> On Thu, May 8, 2014 at 4:56 PM,  wrote:
> > I've been tinkering a while with GCC while trying to follow programming best practices for security, as some of you guys advocate.
> >
> > While making an encryption routine I stumbled upon the possibility of using a register to keep the key, while erasing it from memory.
> 
> Tresor uses this approach for the Linux kernel and keeps keys in debug
> registers:
> http://www1.informatik.uni-erlangen.de/tresor
> 
> This only protects against passive memory extraction attacks, like
> cold boot. It does not help if an active attacker can modify memory.
> 

-------------------------------

> Message du 09/05/14 18:29
> De : "Nemo" 
> A : tpb-crypto at laposte.net
> Copie à : cryptography at metzdowd.com
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> tpb-crypto at laposte.net writes:
> 
> > Is it possible to give a directive to GCC while compiling and/or does
> > it support some macro/routine/directive/library/whatever, that would
> > allow to load values into processor registers and then lock one or two
> > registers, which would become unchangeable? Performance
> > notwithstanding.
> 
> GCC supports global register variables:
> 
> http://gcc.gnu.org/onlinedocs/gcc/Global-Reg-Vars.html
> 
> "Defining a global register variable in a certain register reserves that
> register entirely for this use, at least within the current
> compilation. The register is not allocated for any other purpose in the
> functions in the current compilation, and is not saved and restored by
> these functions."
> 
> So this is a step towards what you want, provided you compile the entire
> application (including all libraries) with the same global declaration
> visible.
> 
> However, as others have pointed out, your next problem is the operating
> system. You would need to recompile the kernel with the same global
> declaration visible there, too, so that the kernel's own code would not
> use it. You would need to audit all of the assembly in the kernel to
> eliminate any uses there, too.
> 
> Obviously, you would need to modify the context switch machinery not to
> save and restore the register.
> 
> Finally, any other application running on the same core following a
> context switch might clobber the register... So you would either need to
> perform the same exercise for all applications on the system, or you
> would need to use the "CPU binding" machinery (see "numactl
> --physcpubind ..." for a starting point) to ensure your process and only
> your process runs on a certain core.
> 
> All of this just to ensure that someone with total access to your
> physical memory cannot steal your password. Is there anything else in
> memory that might be of interest to such an attacker?
> 
> I wonder, though... How many registers would it take, in principle, to
> encrypt/decrypt every memory access?
> 
> - Nemo
> https://self-evident.org/
> 

-------------------------------

> Message du 09/05/14 15:59
> De : "Lodewijk andré de la porte" 
> A : "Guus Sliepen" , "cryptography" 
> Copie à : 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> One might prevent the scheduler from kicking in for as long as the crypto
> program is running.
> 
> One may also use a minimalistic (read: raspberry/arduino) device to do the
> crypto. Then, too, is using registers a safer way of doing things.
> 
> Given OP is already poking through GCC I suspect the level of hardcoreness
> might be high enough to warrant the use of a minimalistic CPU as a
> coprocessor for crypto. This has other advantages too, the greatest being
> that the OS/Computer cannot access the crypto data or otherwise influence
> it's computation.
> 
> Of course, all depends on what's what.
> 
> You could recompile the whole OS without the use of some registers. You'd
> take a performance hit. Programs will still be able to access the sacred
> registers. You'd have to lift the crypto into the kernel to avoid regular
> programs doing it. Then the kernel can still f with you, but it can always
> f with you. (That's why microkernels are secretly better)
> 
> I am not hardcore enough to actually do these things (yet?).
> >
> [ (pas de nom de fichier) (0.2 Ko) ]

-------------------------------

> Message du 09/05/14 15:55
> De : "Jerry Leichter" 
> A : "tpb-crypto at laposte.net" 
> Copie à : "cryptography at metzdowd.com" 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> 
> > On May 8, 2014, at 7:56 PM, tpb-crypto at laposte.net wrote:
> > 
> > While making an encryption routine I stumbled upon the possibility of using a register to keep the key, while erasing it from memory.
> > 
> > By using assembly it is possible to keep that register unchanged and use others to do stuff. That would make easy to build routines, if not by the bare metal programming part, lol.
> > 
> > Is it possible to give a directive to GCC while compiling and/or does it support some macro/routine/directive/library/whatever, that would allow to load values into processor registers and then lock one or two registers, which would become unchangeable? 
> This used to be possible. I recall some experimental languages that generated C but somehow reserved a register. It may have been as simple as creating a fake target description for the back end that didn't know about one of the registers. Of course then you have to use assembler somehow to get at that register. Or it could have been so long ago that the compiler on question actually implemented the C register storage class in a simple and predictable fashion. 
> 
> I can't imagine any way to do this in an even vaguely portable fashion unless you specifically designed you compiler to allow it - unlikely as the demand is so limited. 
> 
> It's also not clear this will help you much. Any time the OS deschedules your process, it will spill the registers into memory - in fact, into memory you know nothing about and can't do anything with. 
> 
> People have played around with encryption kernel algorithms that keep all state in registers, but this only seems possible with complete control of the hardware - assembler code within the OS running on non-virtualized hardware. Might make sense for embedded code, maybe a hardware crypto module. 
> 
> -- Jerry

-------------------------------

> Message du 09/05/14 14:02
> De : "Guus Sliepen" 
> A : cryptography at metzdowd.com
> Copie à : 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> On Fri, May 09, 2014 at 01:56:40AM +0200, tpb-crypto at laposte.net wrote:
> 
> > While making an encryption routine I stumbled upon the possibility of using a register to keep the key, while erasing it from memory.
> 
> This would only work if you could convince all programs and the operating
> system itself to not use that register by changing the platform ABI. Otherwise,
> whenever your application calls a library routine or a context switch happens,
> that register will be saved on the stack and will thus end up in memory after
> all.
> 
> -- 
> Met vriendelijke groet / with kind regards,
> Guus Sliepen 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
> 

-------------------------------

> Message du 09/05/14 10:23
> De : "Tom Mitchell" 
> A : tpb-crypto at laposte.net
> Copie à : "cryptography at metzdowd.com" 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> On Thu, May 8, 2014 at 4:56 PM,  wrote:
> > People,
> >
> >
> > I've been tinkering a while with GCC while trying to follow programming best practices for security, as some of you guys advocate.
> >
> > While making an encryption routine I stumbled upon the possibility of using a register to keep the key, while erasing it from memory.
> ...
> 
> GCC flag... not that I know..
> 
> Not without rewriting the compiler and the ABI used by the compiler.
> 
> The issue is system and subroutine calling conventions.
> Since registers are scarce the compiler will want
> to use all of them that it can. See: register allocation
> http://en.wikipedia.org/wiki/Register_allocation
> and see "register spill compiler"
> http://on-demand.gputechconf.com/gtc-express/2011/presentations/register_spilling.pdf
> 
> A subroutine that you write might do what your want
> up to the point the system clock interrupts and a time
> slice happens.
> 
> It is interesting to note that an Application Binary Interface (ABI)
> often has the convention that the caller saves registers that it
> values (safer) other times the called code must save and restore
> registers that it might need (faster ish). Stack conventions are also
> important.
> 
> The first place to start is the GCC flag that causes the compiler
> to generate and save the assembly language text files. Inspect
> these files and the symbols generated by the code/compiler/assembler/linker
> 
> You can replace C code with assembly directives but portable code
> and assembler are in conflict.
> 
> 
> -- 
> T o m M i t c h e l l
> 

-------------------------------

> Message du 09/05/14 10:14
> De : "Adam Midvidy" 
> A : tpb-crypto at laposte.net
> Copie à : 
> Objet : Re: [Cryptography] How to lock registers with GCC?
>

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Have a look at Tilo Muller's TRESOR.
> 
> It stores AES keys in the x86 debug registers, enabling encryption to be
> performed without storing the keys in memory.
> 
> Paper:
> https://www.usenix.org/legacy/events/sec11/tech/full_papers/Muller.pdf
> Website: http://www1.informatik.uni-erlangen.de/tresor
> 
> Adam

+++++++++++++++++++++++++++++++

People,

I very much appreciated your support, you saved me many hours of research which I can dedicate to coding instead.

>hard core programming

No, I don't think that to mess with GCC you gotta be hardcore. But I'm commemorating 20 years of my first Hello World, so I wanted to take the rust away from my C skills and make something out of my +10 thousand hours of coding. Or what is the use of so many hours of coding when the world needs so much a rehaul in its basic routines?

No, I'm not a goder (a god-coder), I make many mistakes too because I can't deal with everything, all the time, get drunk, and still make things perfect. Maybe brain implants will help in the next ten years or so, but we need this stuff now.

To reach that goal of upgrading my internal routines, I started by researching about which books could make the top 20 most important books about crypto and good C coding to read them. I bought half-a-dozen already and I'm digesting their contents as of now.

What could be done to clean an inch of coding rust while helping the world:
- A simple proof-of-work routine to give the world a new toy. Another toy?
- Create a p2p network to compete with tor, i2p, retroshare, etc. Another p2p?
- Create a basic routine for crypto that could be useful to everyone to embed in the OS itself.

Although the third option exists (openssl modules for linux?) it is not a routine to rule them all, it is not a standard by a long shot.

I'm a fan of standards like Unix, Bitcoin and Bittorrent, which came out of necessity and were done to solve problems. Not to satisfy "stakeholders", like W3C pushing DRM to us right now and Mozilla falling for it, because "stakeholders".

Although respecting people and following academic standards is a good thing, we gotta go hands-on, we don't have time for stakeholders shit.

So, how about coding routines to propose a practical standard crypto for Operating Systems?


> Have a look at Tilo Muller's TRESOR.

Thank you, that is a step in the right direction. Developing further the idea I discovered that practically all generic processors made in the last decade have debug registers. Some assembly is necessary no doubt, but if it is simple and can be done once for entire families of processors, we are good to go for a year long project which we can call multi-platform.

I disagree with Mr. Müller on making it for Android though, because Android has got backdoors in its proprietary side-of-things already. It is interesting from a technical point of view, but uninteresting in practice (maybe that routine can roll in a cyanogen or Firefox OS? that would make it much interesting in practice).


> A subroutine that you write might do what your want
> up to the point the system clock interrupts and a time
> slice happens.

> It's also not clear this will help you much. Any time the OS deschedules your process, it will spill the registers into memory - in fact, into memory you know nothing about and can't do anything with. 

> One might prevent the scheduler from kicking in for as long as the crypto
> program is running.

> This only protects against passive memory extraction attacks, like
> cold boot. It does not help if an active attacker can modify memory.

My goal is to make something that is not easy to side-channel attack. Metaphorically, it doesn't matter how good is your crypto if one of your friends is a loose tongue. So, you can have the best crypto in the world, but what is it useful if you got a loose BIOS?

I'm a fan of simple things, instead of demanding my friends and family use the strongest crypto for e-mail or stuff like that, I created and offered to them one simple cool free e-mail service and jabber (paid by me) on which they all connect. We cut out the e-mails that we exchange from travelling through third party's networks and the server only sends e-mails to other starttls compatible third-party systems. If one email doesn't get to an incompatible host, tough luck. Problem solved for grandma and my nieces.

However, I still use another free service to talk with you guys because I wanna keep my real name out of this crypto mess, at least for now. I fear for my life while implementing something like this, some people will not be happy with it, at all.

The idea is to apply a similar principle from the e-mail experience, to the small scale of a motherboard. To kill most side-channels in one swift struck.


> You could recompile the whole OS without the use of some registers. You'd
> take a performance hit. Programs will still be able to access the sacred
> registers. You'd have to lift the crypto into the kernel to avoid regular
> programs doing it. Then the kernel can still f with you, but it can always
> f with you. (That's why microkernels are secretly better)

> GCC supports global register variables:
> 
> http://gcc.gnu.org/onlinedocs/gcc/Global-Reg-Vars.html

> Finally, any other application running on the same core following a
> context switch might clobber the register... So you would either need to
> perform the same exercise for all applications on the system, or you
> would need to use the "CPU binding" machinery (see "numactl
> --physcpubind ..." for a starting point) to ensure your process and only
> your process runs on a certain core.

You nailed it, now the toy programs and the p2p networks got a killall in my system. So, no matter how awkward, it is possible indeed to create a CPU-only encryption routine.

To help us, both ARM and MIPS have gone multicore. If somebody wants good crypto, sacrificing one core has become the possible price - and a cheap one - for the benefits it may entail.


So, with the info you guys got, we can theoretically now:
- Reserve one core for encryption routines in the OS level;
- Use debug registers to store the key, the key can use more than one register. This will allow us to exploit all the other registers still available to the core, thus not hitting performance issues. MIPS got three debug registers, that would give us 96 bit keys for the lowest-strenght symmetric routine that would work in all other processors;
- Use that core to encrypt the keys in memory for other routines by means of an optional new system call, thus helping to protect the entire system from things like heartbleed giving away private RSA keys;
- Use the idle time in that core to run a thread for a cryptographically secure pseudorandom number generator, like Fortuna and feed it to the OS. This would require a process scheduler exclusively for that core;
- The routine must be small enough to be entirely crammed into the CPU core cache, so it runs fast and you guys like fast stuff that I know. This would also reduce any memory leakage, side-channels and all the shebang;
- Use an open-source OS to create a kernel. Although I love Linux and have more experience coding for it, OpenBSD seems to be a project that would show much more receptivity to something like this. And when things are adopted by the OpenBSD team, everyone else follows because those guys are good. I hope they would catch my mistakes as a bonus;


I need to pick your guys brains on a few other issues, if you help me maybe this thing can become a reality in one year or so:
- Can we use numactl against all processors? How much universal is this thing? Ripping it apart to put it into an OpenBSD is a no-no because of its GPL license. Other suggestions besides begging the original goder for an exception?
- Are there GCC routines to determine how many cores a system has and how many registers of all types are available? Is there a library for that? Can we ask the OS itself at boot time? Because this critter would run in OS boot time, it creates a problem shell commands cannot solve for us, which is to identify what are the resources we messing with at the startup moment.
- Do you guys know any symmetric encryption routine that is quantum-breaking-proof and is compatible with OpenBSD license and offers good protection from as little as 96 bit keys or even less?
- What can we do with the libraries that weren't compiled to exclude a certain CPU core and registers? Is the OS process scheduler good enough to keep all programs from poking into that core? More suggestions to protect that core, please? Can we sandbox the entire kernel? lol
- Can you guys suggest a simple process scheduler routine to put in a single CPU core that is fast and battle-tested and compatible with OpenBSD license? My goal is to make it run as a one single process to use that core and slice it in threads. It must run at 100% if the pseudorandom is necessary like in servers, or just do its little job when called in cellphones, then it goes to sleep again.
- What common barebones multicore hardware should I buy (arm, mips, sparc, etc)? That are cheap enough for a poor coder to buy for peanuts, but are good enough to run OpenBSD to test this thing? I wanna make it multi-platform to the biggest possible measure.


Proprietary systems be damned, but if they want to implement it after we created the standard, good for them. The standard is not mine either, you guys will be invited to collaborate at the right moment, meanwhile we are merely working out together the possible technical barriers.

For the next two weeks I still have to work on a project that uses a cellphone to shutdown a laptop when the two are taken far enough away from each other by means of bluetooth parity, it is my priority at this moment.

So, my answering e-mails will be sloppy at best for the next two weeks, cause my brain is old and uses preemptive tasking schedule.

I'm also sorry for the sloppy English because I'm not a native speaker and this wall of text beat my entire vocabulary to a bloody pulp.


Thank you,
TPB


More information about the cryptography mailing list