Code with and without -std=c99 produces different results (UMAC AE implementation)

Question

Long (really long) story short - I use Ted Krovetz's implementation for calculating UMAC and for UMAC AE encryption (http://www.fastcrypto.org/).

When I compile my code (and/or the tests in umac.c) with -std=c99, the calculated UMAC is COMPLETELY different from the expected (and wrong). When I remove this option, everything works like a charm.

Any ideas what could cause this? And what I can do to check what happens and what produces the different results?

---

$ gcc --version
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

$ uname -a
xxx 3.13.0-43-generic #72-Ubuntu SMP .. x86_64 x86_64 x86_64 GNU/Linux

I don't use any other options - just with and without -std=c99.

---

A few more words:

I'll try to contact Ted Krovetz and ask him for this (it's probably some bug or something), BUT that's not the point. The question is a bit more general and this specific problem could be seen as example.

I ran valgrind - nothing special. Added -Wall and -Wextra - nothing again. Sounds like UB, but valgrind doesn't complain for anything.

The situation is very interesting, took me a lot of days and headaches to understand, that the problem is not in my code (I use this implementation for implementing a complex protocol), but in the algorithm and especially in this option. So I decided to ask for opinions.

This Can code that is valid in both C and C++ produce different behavior when compiled in each language? is not related at all, as we're talking about the same language here.
This Massive fprintf speed difference without "-std=c99" is close, but not enough..

---

EDIT

Here are my test results and what I do (the sources/headers are just downloaded, I don't change anything):

$ ll
total 176K
-rw-r----- 1 kk kk  63K Jan 20 11:00 rijndael-alg-fst.c
-rw-r----- 1 kk kk 2.0K Jan 20 11:00 rijndael-alg-fst.h
-rw-r----- 1 kk kk 3.4K Jan 20 11:00 umac_ae.h
-rw-r----- 1 kk kk  76K Jan 20 11:00 umac.c
-rw-r----- 1 kk kk 4.2K Jan 20 11:00 umac.h

$ gcc -c *.c

$ gcc *.o

$ ./a.out 
AES Test :::
Digest is       : 3AD78E726C1EC02B7EBFE92B23D9EC34
Digest should be: 3AD78E726C1EC02B7EBFE92B23D9EC34

UMAC Test :::
Msg           Should be        Is
---           ---------        --
'a' *     0 : 4D61E4F5AAB959C8 4D61E4F5AAB959C8
'a' *     3 : 67C1700CA30B532D 67C1700CA30B532D
'a' *  1024 : 05CB9405EC38D9F0 05CB9405EC38D9F0
'a' * 32768 : 048C543CB72443A4 048C543CB72443A4

Verifying consistancy of single- and multiple-call interfaces.
Done.

Authenticating       44 byte messages:  6.45 cpb.
Authenticating       64 byte messages:  4.18 cpb.
Authenticating      256 byte messages:  1.63 cpb.
Authenticating      512 byte messages:  1.20 cpb.
Authenticating      552 byte messages:  1.22 cpb.
Authenticating     1024 byte messages:  1.00 cpb.
Authenticating     1500 byte messages:  1.04 cpb.
Authenticating     8192 byte messages:  0.90 cpb.
Authenticating   262144 byte messages:  0.89 cpb.

UMAC-AE Tests :::
0 bytes ('abc' * 0):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : E8D1DAC3EA21E56D
3 bytes ('abc' * 1):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 6BEDBA31E074E2A4
48 bytes ('abc' * 16):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : A3F6069B913969DA
300 bytes ('abc' * 100):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : C5B7F3822179FC36
3000000 bytes ('abc' * 1000000):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : EE7F50FDDA60AA04
  16 bytes, 38.12 cpb
  32 bytes, 25.04 cpb
  64 bytes, 19.39 cpb
 128 bytes, 16.41 cpb
 256 bytes, 14.79 cpb
 512 bytes, 13.96 cpb
1024 bytes, 13.79 cpb
2048 bytes, 13.46 cpb
4096 bytes, 13.47 cpb










$ ll
total 176K
-rw-r----- 1 kk kk  63K Jan 20 11:00 rijndael-alg-fst.c
-rw-r----- 1 kk kk 2.0K Jan 20 11:00 rijndael-alg-fst.h
-rw-r----- 1 kk kk 3.4K Jan 20 11:00 umac_ae.h
-rw-r----- 1 kk kk  76K Jan 20 11:00 umac.c
-rw-r----- 1 kk kk 4.2K Jan 20 11:00 umac.h

$ gcc -std=c99 -c *.c 

$ gcc -std=c99 *.o

$ ./a.out 
AES Test :::
Digest is       : 3AD78E726C1EC02B7EBFE92B23D9EC34
Digest should be: 3AD78E726C1EC02B7EBFE92B23D9EC34

UMAC Test :::
Msg           Should be        Is
---           ---------        --
'a' *     0 : 4D61E4F5AAB959C8 9492DE86794C9F2B
'a' *     3 : 67C1700CA30B532D CF9505F52928360E
'a' *  1024 : 05CB9405EC38D9F0 9C48C0D4EFAFAA37
'a' * 32768 : 048C543CB72443A4 7F63C29BB54BB141

Verifying consistancy of single- and multiple-call interfaces.
Done.

Authenticating       44 byte messages:  7.91 cpb.
Authenticating       64 byte messages:  5.20 cpb.
Authenticating      256 byte messages:  3.03 cpb.
Authenticating      512 byte messages:  2.60 cpb.
Authenticating      552 byte messages:  2.71 cpb.
Authenticating     1024 byte messages:  2.41 cpb.
Authenticating     1500 byte messages:  2.43 cpb.
Authenticating     8192 byte messages:  2.27 cpb.
Authenticating   262144 byte messages:  2.23 cpb.

UMAC-AE Tests :::
0 bytes ('abc' * 0):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 899C50FD244BBA83
3 bytes ('abc' * 1):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 892D14F581A3A4DD
48 bytes ('abc' * 16):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 621AB4A63383F3C5
300 bytes ('abc' * 100):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 324BEF6489F57787
3000000 bytes ('abc' * 1000000):
Encrypt/decrypt match, tags match
Should be: 0000000000000000
Is       : 1A25FE3714C9345A
  16 bytes, 40.80 cpb
  32 bytes, 25.87 cpb
  64 bytes, 20.50 cpb
 128 bytes, 17.72 cpb
 256 bytes, 15.93 cpb
 512 bytes, 15.33 cpb
1024 bytes, 14.88 cpb
2048 bytes, 14.71 cpb
4096 bytes, 14.48 cpb

I just tested on another machine and it's the same as on mine.

Answer 1

Well, I figured it out. Still not sure how to fix it to be perfectly fine/portable, but I'll continue digging.

Long story short - it appeared to be platform specific, that's why most of you don't have this problem.
The issue is with determining the endianness.

---

Details:

After comparing the assembly outputs, there were some significant differences, which (almost automatically) excluded some problems with big constant interpretations and minor things like this.

Then I tried at higher level - the preprocessor output.

Finally, everything led to this piece of code in umac.c:

/* Message "words" are read from memory in an endian-specific manner.     */
/* For this implementation to behave correctly, __LITTLE_ENDIAN__ must    */
/* be set true if the host computer is little-endian.                     */

#ifndef __LITTLE_ENDIAN__
#if __i386__ || __alpha__ || _M_IX86 || __LITTLE_ENDIAN
#define __LITTLE_ENDIAN__ 1
#else
#define __LITTLE_ENDIAN__ 0
#endif
#endif

On my platform, __i386__, __alpha__ and _M_IX86 are not defined. The key is in __LITTLE_ENDIAN.

When compiled:

• with -std=c99: __LITTLE_ENDIAN is not defined => #define __LITTLE_ENDIAN__ 0.
• without -std=c99: __LITTLE_ENDIAN is defined => #define __LITTLE_ENDIAN__ 1.

Hardcoding #define __LITTLE_ENDIAN__ 1, everything starts working perfectly with and without -std=c99.

---

Conclusion: __LITTLE_ENDIAN is a gcc specific macro, which is used here for determining the endianness; it appeared, that -std=c99 affects this macro (it's not defined if the option is used), which leads to different(wrong) results.

---

EDIT
My current ("temporary") solution would be to update the problematic preprocessor if-statement. I know this is far from the best way to solve this, but detecting endianness appeared to be not that easy and far from trivial.

Runtime checks seem to be more reliable, BUT this would lead to more changes in the code, something I want to avoid. It looks like, the most "harmless" "solution" is to update and "fix" the current solution.

So, as I only need it (for now) to work with GCC, I did the following modification:

#ifndef __LITTLE_ENDIAN__
    #if __GNUC__
        #include <endian.h>
        #if __BYTE_ORDER == __LITTLE_ENDIAN
            #define __LITTLE_ENDIAN__ 1
        #elif __BYTE_ORDER == __BIG_ENDIAN
            #define __LITTLE_ENDIAN__ 0
        #else
            #error "Cannot determine endianness! Please update this macro!"
        #endif
    #elif __i386__ || __alpha__ || _M_IX86
        #define __LITTLE_ENDIAN__ 1
    #else
        #warning "Endianness cannot be determined for this platform; using big endian by default! Please be aware and update this macro!"
        #define __LITTLE_ENDIAN__ 0
    #endif
#endif

Answer 2

Sounds like UB,

It doesn't have to be. There are a couple of known differences that can cause the same program to be interpreted differently as C99 and as C90.

but valgrind doesn't complain for anything.

Valgrind does not even come close to warning for all undefined behaviors in either standard.

The first difference that comes to mind (but a good compiler would have emitted a warning) is the type of the integer constant 3000000000. With 32-bit int and 64-bit long, a C90 compiler types 3000000000 as an unsigned long. In C99, unsigned long is not in the list of types that integer constants without suffixes can have, so 3000000000 is typed as long long (signed).

Without looking, cryptographic code is likely to have lots of large integer constants, so this is one possibility.

Of course, there might be undefined behavior in the code interpreted as C90 or as C99, and then it would be excusable for a compiler to produce differing results in C90 and C99 modes. All I am saying is that there doesn't need to be.

Answer 3

This answer builds on Kiril Kirov's existing answer

Kiril has identified the problem that the system of preprocessor checks is failing to identify the existing platform:

#if __i386__ || __alpha__ || _M_IX86 || __LITTLE_ENDIAN
#define __LITTLE_ENDIAN__ 1
#else
#define __LITTLE_ENDIAN__ 0
#endif

Although the platform is little-endian, none of those identifiers are defined in gcc -std=c99 mode. So this is a problem with the quoted code here; the code needs to be updated to better identify whether it's a little-endian platform or not.

The first thing I would do is stop having a default case, so that if the platform is unrecognized then an error is generated instead of silently running wrongly:

#if __i386__ || __alpha__ || _M_IX86 || __LITTLE_ENDIAN
#define __LITTLE_ENDIAN__ 1
#elif __arm__  // etc.
#define __LITTLE_ENDIAN__ 0
#else
#error Unrecognized platform, please update this macro
#endif

The next step would be to actually detect correctly for what system you are on. Here is another thread on this topic.

One thing you can do is to issue gcc -std=c99 -dM -E - <<<'' which will cause gcc to output a list of all predefined macros in that mode; and then you can look for something useful. In my case it has:

#define __i386 1
#define __i686 1

so either of those could be used.

An alternative approach specifically for __LITTLE_ENDIAN__ is to detect it via preprocessor arithmetic, described here - although the first code sample on that page doesn't actually produce a preprocessing constant, so it wouldn't be usable as a condition for future preprocessor checks.

---

Having solved this specific problem, you should still try to find other instance of architecture problems in the same codebase. It looks like the author has cobbled together a few architecture macros he/she knew about. One conspicuous absence is _M_IX64 for example. It'd be wise to perhaps grep through the codebase for any other instances of _M_ or __i386__ and see if it is relying on those. If it is; then again perhaps try to abstract out that test into a macro that you have better control over.

Ideally you'd have all such macros defined in a single header for the whole codebase; and then the rest of the codebase just uses macros which have been defined in that header.