Message-ID: <5619A8E1.4000202@openwall.com>
Date: Sun, 11 Oct 2015 03:10:09 +0300
From: Alexander Cherepanov <ch3root@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Specification of a modular crypt format (2)

On 2015-10-09 16:55, Peter Gutmann wrote:
> [Several replies combined into one, since I'm not sure how on-topic it still
>   is :-)].
>
> Alexander Cherepanov <ch3root@...nwall.com> writes:
>
>> [ftrapv]
>>
>> Yes, a nice option. Beware though that it doesn't work in 64-bit mode for gcc
>> at least up to version 4.9:
>
> In any case the ftrapv behaviour (crash the program) is worse than useless,
> when you've got code that checks for overflows and handles them you want the
> checks to not be removed, not to be given the option to have your program
> crash.  So the difference between gcc and gcc -ftrapv is that the former
> produces braindamaged behaviour, the latter does the braindamage and then
> crashes your program as well.

-ftrapv is great for testing (e.g. under fuzzer) or for code which 
checks for overflows before operations and hence any overflow means a 
bug in the program. If you want wrapping use -fwrapv.

>> Maybe just fix bugs in the code?:-) Seriously, some recent tools make it
>> easier. First of all, run your test suite with valgrind, Address Sanitizer
>> and Undefined Behavior Sanitizer. Raise code coverage with a fuzzer (e.g.
>> American Fuzzy Lop) and, perhaps, KLEE.
>
> I already do all of that,

Are you sure? When I run testlib from cryptlib 3.4.3 compiled with '-m32 
-fsanitize=undefined' I get:

crypt/sha2.c:342:37: runtime error: left shift of 128 by 24 places 
cannot be represented in type 'int'
crypt/castenc.c:96:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/castenc.c:130:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5skey.c:117:11: runtime error: shift exponent 32 is too large 
for 32-bit type 'long unsigned int'
crypt/rc5enc.c:167:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:224:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:164:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:170:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:221:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:227:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:163:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:163:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:228:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:228:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/castenc.c:88:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/castenc.c:138:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:166:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:168:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
crypt/rc5enc.c:170:2: runtime error: shift exponent 32 is too large for 
32-bit type 'long unsigned int'
etc.

Or let's see how the overflow in the excerpt you posted can be caught. 
We don't have a test suite so let's use AFL to generate some samples. 
And we need a wrapper which reads a line from stdin in a string "str". Then:

1) compile with afl:

$afl-gcc -o gutmann_num gutmann_num.c

2) prepare input samples (any garbage will do in our case):

$ mkdir in
$ printf 0 > in/zero

3) run afl and wait for "cycles done" to become green (or at least 
blue), then Ctrl-C:

$ AFL_SKIP_CPUFREQ=1 afl-fuzz -i in -o out ./gutmann_num

(afl generates 25 samples in 10 minutes and after 25 minutes turns green 
due to not finding any more interesting samples);

4) compile with ubsan:

$ gcc -O2 -fsanitize=undefined -o gutmann_num_ubsan gutmann_num.c

5) run all samples found by afl against ubsan:

$ for file in out/queue/*; do echo "$file"; ./gutmann_num_ubsan < 
"$file"; done

get this:

[...]
out/queue/id:000018,src:000015,op:havoc,rep:2,+cov
gutmann_num.c:23:17: runtime error: signed integer overflow: 400040000 * 
10 cannot be represented in type 'int'
out/queue/id:000019,src:000015,op:havoc,rep:2
out/queue/id:000020,src:000015,op:havoc,rep:4,+cov
gutmann_num.c:23:17: runtime error: signed integer overflow: 2000000001 
* 10 cannot be represented in type 'int'
out/queue/id:000021,src:000007+000011,op:splice,rep:32
[...]

Easy, huh?

I've used gcc 4.9 here which doesn't have an option to crash on ubsan 
errors. With newer gcc or clang you can fuzz directly with ubsan.

> and also cppcheck, clang, Coverity, Klocwork,
> Prefast, and some others.  Problem is that (a) gcc breaks code faster and more
> effectively than any analyser can find things and (b) most developers don't do
> this, which means they can't even try to work around gcc's problems.  I hate
> to think how much code out there is broken by gcc, with no-one the wiser...

BTW, according to [1], "even gcc 2.95.3, released in 2001," will exploit 
UB of signed integer overflow for optimization, so it's not some recent 
problem. This blogpost also mentions an interesting option 
-Wstrict-overflow. With it, you can see at least some checks that gcc 
optimizes away.

[1] http://www.airs.com/blog/archives/120
[2] 
https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wstrict-overflow-420

>> Then use tools like Clang Static Analyser and cppcheck. Then proceed to
>> STACK[3], Frama-C etc.
>
> That really doesn't scale.  I already perform what I'm sure most developers
> would agree is an insane amount of analysis on my code, and still can't catch
> all the things that gcc does to it.  What's worse, no matter how much analysis
> I perform, I can never be sure that I've managed to counter all the things
> that gcc will end up doing to it.  I can't imagine that any project built
> under time/commercial pressures could afford to invest this amount of effort
> into fighting what gcc does to their code.
>
> (Some time ago, one of the leads at Coverity said at a talk that they invest
> something like 80% of their effort not into creating more code to find
> problems but doing things like getting rid of false positives due to warnings
> that are technically valid but that most people would agree are unnecessary.
> In other words they recognise that Doing the Right Thing helps users more than
> quoting dogma at them and breaking things like the gcc folks do.  Other
> vendors like Fortify handle this a bit differently, they rank things by
> severity but don't put so much effort into FP suppression, so when you look at
> the lower grades of warnings you get so many of them that you mostly end up
> just skipping them.  Not saying that this is necessarily a bad thing, but I
> prefer the Coverity approach to the Fortify one).

You seem to overly concentrate on static analysis. Perhaps try more 
dynamic analysis?

>> just start with the usual suspects
>
> Already doing that, but it's pretty sad that I need to add -fdont-break-my-code
> flags just to get the compiler to not break my code.  And just because you and
> I know that these flags exist doesn't mean that everyone else does, so they'll
> still get caught

What are alternatives? Not breaking _any_ code probably means that no 
changes in compilers are possible at all. If there is a buffer overflow 
in a program which happens not to touch anything important, should this 
program be kept working no matter what? There should be some formal 
description which you could rely on. Why there is no specification for 
such a variant of C?

The only specification that I know is C standards -- C89, C99, C11 
(modulo corrigenda etc.). And they are (un)surprisingly consistent -- 
you cannot overflow signed integers, you cannot dereference NULL, you 
cannot access objects as another type (with some exceptions), you cannot 
shift values by their width etc.

If you don't aim at standards-compliance your code is doomed to be 
broken by compilers.

In fact, there is some activity in this area -- [3][4]. But if you "have 
to support pretty much every compiler under the sun" it will not of much 
help to you even if these initiatives yield tangible results.

[3] https://www.cl.cam.ac.uk/~pes20/cerberus/
[4] http://blog.regehr.org/archives/1180

-- 
Alexander Cherepanov

Powered by blists - more mailing lists