[Cryptography] How programming language design can help us write secure crypto code

Michael Kjörling michael at kjorling.se
Sat Oct 24 13:13:58 EDT 2015


On 24 Oct 2015 05:12 +0000, from pgut001 at cs.auckland.ac.nz (Peter Gutmann):
> Bertrand Mollinier Toublet <crypto-metzdowd at bmt-online.org> writes:
>
>> For that matter, I have the following program:
>> 
>> [...]
>> 
>> Which is yours, but in an actually compilable form.
>
> No it's not.  Go back to my posting and read what it says, specfically the
> fact that I point out that it uses argc to prevent the compiler from
> optimising the contents of the code away (again, hat tip to Alexander
> Cherepanov for providing the original).

Actually, it looks to me like Bertrand wasn't referring to your
program at all, but to Ray's.


>> I’ve seen a lot of high claims in this thread about how gcc is bent on
>> shooting your foot for you, with the full might of the language standard
>> behind it, but I’m not seeing it.
>
> If you still can't see what you've done wrong in your code based on my comment
> above, use gcc -S.

I did use gcc -S, with a version of Ray's code massaged into
compilable form (_very_ similar to the one Brent posted). I did again
now, with that posted by Bertrand.

Specifically, I ran the C-to-assembler transformation of Betrand's
code several times. Once with default optimizations ("gcc -Wall
-pedantic -S test.c"), once with no optimizations ("-O0" added), once
with few optimizations ("-O1"), once with some more optimizations
("-O2") and once with extreme optimizations ("-O3"), and looked at the
output assembler.

When running with the default settings, which [1] claims is -O0, the
output assembler looks like one would expect. Here is what gcc, with
optimizations disabled, has transformed the lines

    z = x + y;    /* undefined in case of overflow */
    if (z < 0){
        printf("overflow at line %d\n", __LINE__);
        exit(1);
    }
    printf("positive result is %d\n", z);

into:

.L3:
        movl    -8(%rbp), %eax
        movl    -4(%rbp), %edx
        addl    %edx, %eax
        movl    %eax, -12(%rbp)
        cmpl    $0, -12(%rbp)
        jns     .L4
        movl    $13, %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        movl    $1, %edi
        call    exit
.L4:
        movl    -12(%rbp), %eax
        movl    %eax, %esi
        movl    $.LC1, %edi
        movl    $0, %eax
        call    printf
        movl    $0, %eax
        leave

.LC0 refers to the "overflow" format string, and .LC1 refers to the
"positive result" format string.

Note that, just like one would expect, there is a "cmpl $0, ..." and
"jns" in there, to skip over the part that, if the value obtained by
adding the two (loaded into %eax and %edx right after the .L3 label)
is negative, prints the "overflow" message and exits.

And quite right, when I compile and link with no specific optimization
settings, my system too prints "overflow at line 13". Built with gcc
(Debian 4.7.2-5) 4.7.2 on an up-to-date Debian Wheezy. "diff" says the
output of running GCC with no -O parameter and with -O0 is identical.

By the time we move into -O1 territory, the assembler code looks
_vastly_ different, and indeed the compiler has determined that the
check is redundant and optimized out the whole thing, leaving us with
a program that unconditionally prints the "overflow" message. When
running with -O1, this is the _full_ assembler output that I get when
using the above compiler (note that -O1 specifies optimizations above
and beyond the default):

        .file   "test.c"
        .section        .rodata.str1.1,"aMS", at progbits,1
.LC0:
        .string "overflow at line %d\n"
        .text
        .globl  main
        .type   main, @function
main:
.LFB18:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $13, %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        movl    $1, %edi
        call    exit
        .cfi_endproc
.LFE18:
        .size   main, .-main
        .ident  "GCC: (Debian 4.7.2-5) 4.7.2"
        .section        .note.GNU-stack,"", at progbits

If I replace the rvalue for the y assignment with "INT_MAX - argc",
then compile with -O1, the compiler keeps the check and running the
program again quite rightly prints "overflow at line 13" because it
obviously cannot fully evaluate the expressions involved at compile
time.

If I add "volatile" to the variable declarations, as has been
suggested several times in this thread, but keep the original rvalue
expression, and recompile with -O3, I still get exactly the same
result: "overflow at line 13", because now I have _specifically_ told
the compiler that it cannot optimize out those accesses. The assembler
output in this case is significantly more difficult to follow at a
glance, but does refer to both string constants, and it has three
"testl"/"js" instruction pairs, seemingly corresponding to the three
comparison expressions in the C source code (testing x, y and z,
respectively, for less than 0).

Now. Is this a problem with the C language standard, with GCC, or is
it a problem with how people use GCC?

I think a case can be made for that, once you deviate from default
settings, the problem is no longer with the software, but with the
user, if those non-default settings have unintended consequences. I
also think a case can be made for that if the language provides a
means to do help the compiler understand which parts are critical (in
C's case, for example, the "volatile" keyword attached to a variable
declaration), and you don't use that, and you have told the compiler
to optimize, then if the compiler _can_ accurately determine the value
of an expression at compile time it is well within its right to do so
and optimize accordingly, even if the program otherwise would rely on
non-observable side effects of those operations.

The fact that a program _relies_ on _non-observable side effects_ is
something that _the programmer_ must take into consideration; it
cannot reasonably be the task of the compiler to know that one
_particular_ assignment of a value to a variable that is never read
again (and one that quite possibly goes out of scope immediately
afterwards) must not be optimized away.

This is why I think that a standardized way to tell the compiler
_that_ a particular chunk of code, perhaps at the function level,
_must not_ be optimized, would help a lot. (Would it completely
eliminate the problem? No, of course it would not. But it's a
low-cost, low-risk option that would seem to move us a great deal in
the right direction.) It would give an output from the compiler much
more like that obtained when running GCC with -O0, even when compiling
the whole package with say -O2 or -O3, without needing to compile
specific modules with separate settings (which would be brittle). When
running GCC with -O0, at least for this trivial program, we have
something that is pretty close to the "one to one mapping" between C
and assembler (or machine language) that I have discussed previously
in this thread: each C language expression maps to one or a set of
assembly operations, _and_ it's possible to look at the C code on one
side and the assembler code on the other, and directly map expressions
between them.

Or you could just mark the critical variables "volatile", forcing any
compliant compiler to always perform those accesses, even if they
appear to the optimizer as redundant.

 [1]: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

-- 
Michael Kjörling • https://michael.kjorling.semichael at kjorling.se
OpenPGP B501AC6429EF4514 https://michael.kjorling.se/public-keys/pgp
                 “People who think they know everything really annoy
                 those of us who know we don’t.” (Bjarne Stroustrup)


More information about the cryptography mailing list