Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3584 > unrolled thread

Crypto friendly optimization?

Back to article view | Back to comp.compilers

Contents

  Crypto friendly optimization? John R Levine <johnl@taugh.com> - 2024-08-24 17:14 -0400
    Re: Crypto friendly optimization? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-08-24 16:33 -0700
      Re: Crypto friendly optimization? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-08-24 20:55 -0700
      Re: Crypto friendly optimization? anton@mips.complang.tuwien.ac.at - 2024-08-25 16:06 +0000
        Re: Crypto friendly optimization? David Brown <david.brown@hesbynett.no> - 2024-08-25 21:12 +0200
        Re: Crypto friendly optimization? Philipp Klaus Krause <pkk@spth.de> - 2025-04-05 19:50 +0200
    Re: Crypto friendly optimization? Ian Lance Taylor <ianlancetaylor@gmail.com> - 2024-08-24 20:14 -0700
    Re: Crypto friendly optimization? David Brown <david.brown@hesbynett.no> - 2024-08-25 12:32 +0200

#3584 — Crypto friendly optimization?

On a cryptography list people were complaining that compiler optimizers
mess up their cryptographic code and make it insecure.  They try to write
code that runs in constant time, or that erases all the temporary storage,
but the compilers say oh, that's dead code, or oh, I can make this faster
with a few branches and the erases go away and the constatnt time isn't.

This 2018 paper from Cambridge discusses changes they made to Clang/LLVM
so they could tell the compiler what they wanted it to do.  Has there been
other work on this topic?

https://on.ft.com/3MjWez0

R's,
John

[toc] | [next] | [standalone]

#3585

John R Levine <johnl@taugh.com> writes:
> On a cryptography list people were complaining that compiler optimizers
> mess up their cryptographic code and make it insecure.  They try to write
> code that runs in constant time, or that erases all the temporary storage,
> but the compilers say oh, that's dead code, or oh, I can make this faster
> with a few branches and the erases go away and the constatnt time isn't.
>
> This 2018 paper from Cambridge discusses changes they made to Clang/LLVM
> so they could tell the compiler what they wanted it to do.  Has there been
> other work on this topic?
>
C23 will add the memset_explicit() function :

    The memset_explicit function copies the value of c (converted to an
    unsigned char) into each of the first n characters of the object
    pointed to by s. The purpose of this function is to make sensitive
    information stored in the object inaccessible.

I'm not aware of any current implementations that support it.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[C11 has memset_s() which seems more or less the same thing.

I put the wrong link in the previous message.  The paper is
here: https://ieeexplore.ieee.org/document/8406587 -John]

[toc] | [prev] | [next] | [standalone]

#3587

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
[...]
> C23 will add the memset_explicit() function :
[snip]
>
> [C11 has memset_s() which seems more or less the same thing.
> ...
> -John]

memset_s() is part of ISO C Annex K, which is optional.  glibc, for
example, doesn't currently provide either, though it does provide
explicit_bzero().

TLDR: There are currently several different C solutions with varying
levels of support.  Until then, a creepy maze of #ifdefs is probably
the best we can do.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#3589

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>John R Levine <johnl@taugh.com> writes:
>> On a cryptography list people were complaining that compiler optimizers
>> mess up their cryptographic code and make it insecure.  They try to write
>> code that runs in constant time, or that erases all the temporary storage,
>> but the compilers say oh, that's dead code, or oh, I can make this faster
>> with a few branches and the erases go away and the constatnt time isn't.
>>
>> This 2018 paper from Cambridge discusses changes they made to Clang/LLVM
>> so they could tell the compiler what they wanted it to do.  Has there been
>> other work on this topic?
>>
>C23 will add the memset_explicit() function :
>
>    The memset_explicit function copies the value of c (converted to an
>    unsigned char) into each of the first n characters of the object
>    pointed to by s. The purpose of this function is to make sensitive
>    information stored in the object inaccessible.
>
>I'm not aware of any current implementations that support it.

That's trivial:

void *memset_explicit( void *dest, int ch, size_t count )
{
  memset(dest, ch, count);
}

Yes, calls to such a memset_explicit() can be eliminated by an
adversarial compiler, but this makes such an implementation ideal for
such a compiler: there is nothing faster than an eliminated call, and
it satisfies the specification.  After all, if the data stored in the
area overwritten by memset_explicit is not accessible by a standard C
program without exercising undefined behaviour (a scenario ignored by
adversarial compilers), memset_explicit() does not change that, so an
adversarial compiler can "optimize" it away.  And if the memory is
accessible by a standard program, the compiler will not eliminate a
call to memset(), either.

Does it satisfy the purpose?  No, but it does wrt the C abstract
machine something that is equivalent (given the as-if rule and
assuming that no undefined behaviour is exercised) to the
specification, and that's the justification used for every misdeed of
adversarial compilers.

>[C11 has memset_s() which seems more or less the same thing.

Yes, someone told me that memset_s() is the solution to the problem of
clearing memory reliably.  Given that, why have they added
memset_explicit()?  The specification of memset_s() contains:

|Unlike memset, any call to the memset_s function shall be evaluated
|strictly according to the rules of the abstract machine as described
|in (5.1.2.3). That is, any call to the memset_s function shall assume
|that the memory indicated by s and n may be accessible in the future
|and thus must contain the values indicated by c.

In <2016Nov14.184256@mips.complang.tuwien.ac.at> I wrote about that:
|Now, everything else (including memset()) in the standard also is
|evaluated according to the rules of the abstract machine, and the
|"optimization" comes in afterwards, applies the as-if rule, and poof,
|memset() is gone, and so is memset_s().

Could it be that compilers do this with memset_s() and that's why C23
has added memset_explicit()?  And I expect that the same will happen
to memset_explicit(), too.

>I put the wrong link in the previous message.  The paper is
>here: https://ieeexplore.ieee.org/document/8406587 -John]

There was also a talk by Ilja van Sprundel at 35C3 about the problem
and he needed the full hour allocated to the talk.  The talk is called
"Memsad - why clearing memory is hard" and here are some links to it:

https://media.ccc.de/v/35c3-9788-memsad
https://www.youtube.com/watch?v=0WzjAKABSDk

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[This all seems directed to leaving stuff in memory.  Anyone done work
on constant-time code? -John]

[toc] | [prev] | [next] | [standalone]

#3590

On 25/08/2024 18:06, anton@mips.complang.tuwien.ac.at wrote:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

>> C23 will add the memset_explicit() function :
>>
>>     The memset_explicit function copies the value of c (converted to an
>>     unsigned char) into each of the first n characters of the object
>>     pointed to by s. The purpose of this function is to make sensitive
>>     information stored in the object inaccessible.
>>
>> I'm not aware of any current implementations that support it.
>
> That's trivial:
>
> void *memset_explicit( void *dest, int ch, size_t count )
> {
>    memset(dest, ch, count);
> }
>
> Yes, calls to such a memset_explicit() can be eliminated by an
> adversarial compiler, but this makes such an implementation ideal for
> such a compiler: there is nothing faster than an eliminated call, and
> it satisfies the specification.  After all, if the data stored in the
> area overwritten by memset_explicit is not accessible by a standard C
> program without exercising undefined behaviour (a scenario ignored by
> adversarial compilers), memset_explicit() does not change that, so an
> adversarial compiler can "optimize" it away.  And if the memory is
> accessible by a standard program, the compiler will not eliminate a
> call to memset(), either.
>
> Does it satisfy the purpose?  No, but it does wrt the C abstract
> machine something that is equivalent (given the as-if rule and
> assuming that no undefined behaviour is exercised) to the
> specification, and that's the justification used for every misdeed of
> adversarial compilers.

Did you bother to /read/ the C23 standard specification for
memset_explicit()?

The C23 standard explicitly says "The purpose of this function is to
make sensitive information stored in the object inaccessible" and "The
intention is that the memory store is always performed (i.e. never
elided), regardless of optimizations. This is in contrast to calls to
the memset function".

So no, your silly implementation is not sufficient.  It can be
implemented using volatile :

void *memset_explicit(void *s, int c, size_t n) {
	volatile unsigned char * p = s;
	while (n--) *p++ = c;
}

Or it can use "compiler magic", which makes sense for efficiency.

>
>> [C11 has memset_s() which seems more or less the same thing.
>
> Yes, someone told me that memset_s() is the solution to the problem of
> clearing memory reliably.  Given that, why have they added
> memset_explicit()?  The specification of memset_s() contains:
>
> |Unlike memset, any call to the memset_s function shall be evaluated
> |strictly according to the rules of the abstract machine as described
> |in (5.1.2.3). That is, any call to the memset_s function shall assume
> |that the memory indicated by s and n may be accessible in the future
> |and thus must contain the values indicated by c.
>
> In <2016Nov14.184256@mips.complang.tuwien.ac.at> I wrote about that:
> |Now, everything else (including memset()) in the standard also is
> |evaluated according to the rules of the abstract machine, and the
> |"optimization" comes in afterwards, applies the as-if rule, and poof,
> |memset() is gone, and so is memset_s().
>
> Could it be that compilers do this with memset_s() and that's why C23
> has added memset_explicit()?  And I expect that the same will happen
> to memset_explicit(), too.

No, it could /not/ be that.

The reality is that the "Annex K" functions have never been part of any
mainstream implementation.  They were an overly complicated attempted
solution for "safer" standard library functions that were supposed to
work by adding an extra unnecessary parameter that is, for most of the
Annex K functions, useless.  So compilers generally don't do /anything/
with "memset_s", because it doesn't exist in any but a very few standard
libraries.  But any compliant C implementation that supported the
function, would do so in the specified manner.


So memset_explicit() will be a good solution to the OP's problem, once
it becomes readily available.  memset_s() would also work, but be less
elegant, if anyone implemented it.  (memset_explit() has the big
advantage of not being optional in standard C23.)

(Of course as we all know, zeroing out temporary storage at this level
does not mean the sensitive data is removed from caches, backing memory,
swap space, or anything else - but that's another matter.)

[toc] | [prev] | [next] | [standalone]

#3640

Am 25.08.24 um 18:06 schrieb anton@mips.complang.tuwien.ac.at:
>> I'm not aware of any current implementations that support it.
>
> That's trivial:
>
> void *memset_explicit( void *dest, int ch, size_t count )
> {
>    memset(dest, ch, count);
> }

SDCC has had memset_explicit since SDCC 4.2.0 (released 2021), and this
is the implementation:

#include <string.h>

void *memset_explicit (void *s, int c, size_t n)
{
   return(memset(s, c, n));
}

Since SDCC does not have link-time optimization, and the implementation
resides in its own source file by itself, this is sufficient to ensure
that it does not get optimized out.

Philipp

[toc] | [prev] | [next] | [standalone]

#3586

For the Go programming language there has been discussion of adding a
secret.Do function, that invokes a function closure and, after it returns,
erases all memory that it allocated. The goal is better, though not perfect,
forward secrecy, so that people can't capture a key today and a conversation
today and, if they key becomes vulnerable, later use it to decrypt the
conversation. There is a lot of discussion at <https://go.dev/issue/21865>
with the output at
<https://github.com/golang/go/issues/21865#issuecomment-925310304>. This is
not yet implemented, but the current attempts require work in both the
compiler and the runtime library.

Related to that is a more speculative idea to enable ARM DIT/Intel DOIT mode
while executing a function. Discussion at <https://go.dev/issue/66450>.

But there is no special work in the Go compilers to ensure that code written
to execute in constant-time is not optimized to run in non-constant-time. It
would be interesting to hear about other work in that area.


Ian

[toc] | [prev] | [next] | [standalone]

#3588

On 24/08/2024 23:14, John R Levine wrote:
> On a cryptography list people were complaining that compiler optimizers
> mess up their cryptographic code and make it insecure.  They try to write
> code that runs in constant time, or that erases all the temporary storage,
> but the compilers say oh, that's dead code, or oh, I can make this faster
> with a few branches and the erases go away and the constatnt time isn't.
>
> This 2018 paper from Cambridge discusses changes they made to Clang/LLVM
> so they could tell the compiler what they wanted it to do.  Has there been
> other work on this topic?

There are all sorts of compiler flags, extensions and attributes in gcc
that can help here for security-critical code.  I don't know the details
for clang, but I believe there is a great deal of overlap with gcc here.



<https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html#index-fhardened>

Enables a lot of security-related flags to limit attacks.



Stack scrubbing in general is useful here:

<https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html>

There are type and function attributes that give more control over stack
scrubbing.


And inline assembly can be used to control effects.

#include <string.h>

extern void get_password(char * p);
extern void use_password(const char * p);

void unsafe(void) {
     char password[80];

     get_password(password);
     use_password(password);
     memset(password, 0, sizeof(password));
}

void safer(void) {
     char password[80];

     get_password(password);
     use_password(password);
     memset(password, 0, sizeof(password));
     __asm__ ("" : "+m" (password));
}

<https://godbolt.org/z/6vjeP8ac8>


These are, of course, compiler-specific.  But it covers gcc and clang,
and the inline assembly works for old and new versions (stack scrubbing
is a relatively new addition to the compilers).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web