Clean C version? - Githubissues

I wanted to give Dilithium a try in an embedded environment. The github code is for Linux, with GCC directives and inline assembly code. The first try to compile it with a standard C99 compiler (and also under Windows with MS Visual Studio 2017) resulted in 535 compiler errors.

Is there a standard C version of Dilithium? Or Python, Java, Julia…, which I can easily turn to standard C?

Hi Laszlo,

The core reference implementation of Dilithium is quite portable C code. We do rely on a couple of implementation specific behaviors to write constant time code though. For example right shifts of signed integers are assumed to be arithmetic right shifts.

On the other hand the test programs test_dilithium, test_vectors and test_mul are not as portable. The reason they are not compatible with Windows and MSVC is that we do not support a Windows-compatible randombytes implementation and use inline assembly to access the time step counter (TSC). Also our AVX2 implementation is written for the Linux/MacOS calling convention and might not run correctly on Windows.

That being said testing Dilithium on Windows or another platform different to Linux and MacOS should be possible relatively easily by exchanging randombytes.c with a suitable implementation and rewriting test_dilithium.c to not use cpucycles.h.

Alternatively the NIST program PQCgenKATsign to generate the known answer tests might run on Windows as it is only using deterministic "randomness". I can not try this though as I don't have access to a Windows computer.

Hope this helps, Gregor

On 03.05.19 20:14, LaszloHars wrote:

I wanted to give Dilithium a try in an embedded environment. The github code is for Linux, with GCC directives and inline assembly code. The first try to compile it with a standard C99 compiler (and also under Windows with MS Visual Studio 2017) resulted in 535 compiler errors.

Is there a standard C version of Dilithium? Or Python, Java, Julia…, which I can easily turn to standard C?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pq-crystals/dilithium/issues/6, or mute the thread https://github.com/notifications/unsubscribe-auth/AHXVKDEKIHPUP3XSCYWUQBLPTR6J5ANCNFSM4HKV67SQ.

LaszloHars notifications@github.com wrote:

Dear Laszlo,

I wanted to give Dilithium a try in an embedded environment. The github code is for Linux, with GCC directives and inline assembly code. The first try to compile it with a standard C99 compiler (and also under Windows with MS Visual Studio 2017) resulted in 535 compiler errors.

That's a lot. Just to double-check, you took the code from

git clone https://github.com/pq-crystals/dilithium.git

and then ran

cd dilithium/ref && make

(or something similar that would compile that code)?

The code in the avx2 subdirectory is certainly not portable, but the ref code should be.

Is there a standard C version of Dilithium? Or Python, Java, Julia…, which I can easily turn to standard C?

Let me prioritize Dilithium for PQClean [1]. The goal of this framework is to provide precisely what you're looking for, so it would be a great test case for our framework as well to get Dilithium in and then see if that code works for you.

All the best,

Peter

[1] https://github.com/pqclean/pqclean

Thank all of you for the quick responses! In the mean time I managed to compile and run Dilithium in Visual Studio 2017, without errors. See below my notes. However, I was puzzled with the expression: -(signs & 1) & (1 ^ (Q - 1)) Not only it is incorrect by applying unary "-" to an unsigned expression, but why (1 ^ (Q - 1)) instead of Q?


DILITHIUM - Visual Studio 2017
==============================

The reference C implementation is https://github.com/pq-crystals/dilithium
It is written for GCC under Linux, and cannot be directly used elsewhere
    use of "__attribute__"
    #include <unistd.h>
    #include <sys/syscall.h>
    use of dynamically sized arrays (instead of malloc or static sizes)
    unary "-" for unsigned value
    Linux random function
    GCC-syntax assembly code for accessing system timer

There is an effort to collect clean implementations of the post-quantum schemes
that are in the NIST post-quantum project: https://github.com/pqclean/pqclean
    See the website of Douglas Stebila:  https://www.douglas.stebila.ca/
    Several KEM schemes are already implemented, including CRYSTALS/Kyber768
    Only one signature scheme (5/4/2019): sphincs-shake256-128f-simple

Setup VS solution
-----------------
Start a new solution, as a Windows Console application

add all .c and .h files from dilithium-master/ref to the solution

add to the solution 4 files from the ref/test directory
    speed.h
    speed.c
    cpucycles.h
    cpucycles.c

remove from the solution the 3 conflicting files with main
    test_mul.c
    test_vectors.c
    PQCgenKAT_sign.c

remove randombytes from the solution (NOT NEEDED as rng.c has an implementation)
    randombytes.h
    randombytes.c
ToDo: add default implementation for the function randombytes to generate true random bytes

Code changes for VC
-------------------
replace cpucycle functions with dummy code instead of the unusable assembler code, returning 0 in:
    cpucycles.h
    cpucycles.c
ToDo: write code with valid Windows system calls for cpucycles

poly.h - line 9: remove __attribute__(...)

packing.c - line 264: unary "-" for unsigned value (error)
    - is not "(1 ^ (Q-1))" always Q, since Q is an odd prime???
    "(signs & 1)" is unsigned, it cannot have a unary "-". We may need type casts
    "(signs & 1) ? Q : 0" would not be constant time when compiled,
        but we don't know, what different versions of the compiler do with the original
        Only assembler could enforce constant time, but it is not portable

sign.c - line 79: the same as above

poly.c - line 364: (dynamic array size) buflen is a variable, not a constant
    change to unsigned char buf[((769 + STREAM128_BLOCKBYTES)/STREAM128_BLOCKBYTES)*STREAM128_BLOCKBYTES + 2];
       - line 449
    similar change to buf[buflen] by copying humangous expression into the length of buf[]
       - line 532
    similar change to buf[buflen+4]

replace #include "randombytes.h" with #include "rng.h"
    sign.c - line 5
    testdilithium.c - line 5

OpenSSL
-------
OpenSSL has to be set up and made known to Visual Studio

Failed:
    Copy all header files from openssl-master/include/openssl to a directory
        set Visual Studio to use the parent of this as include directory
    opensslconf.h is missing, it should be auto-generated by a Perl script. Need to install Perl...
    Tried to download a pre-generated Windows version from
    https://github.com/David-Reguera-Garcia-Dreg/Precompiled-OpenSSL-Windows/blob/master/openssl-1.1.0e-vs2012/include/openssl/opensslconf.h
        Fail: incompatible version, missing data

Worked:
    Install OpenSSL for Visual Studio 2017:
    1. Project -> Manage Nuget Packages
    2. In the Browse Tab search for 'openssl'
    3. Select openssl-vc141, and Install

Linker setup
------------
to fix linker errors: unresolved references to memcpy, memset...
    VC Debug Build SPECIFICS: add to
    properties->Linker->Input->Additional Dependencies
        vcruntime.lib
        ucrtd.lib
    (implicit:  kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib
                shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib)

At this point the code compiles w/o errors
but with warnings over type mismatches, unsafe intrinsic functions...

Debug runs
----------
No errors :)

reopened, asking for feedback (closed by accident)

The full context of this expression is

c->coeffs[b] = 1; c->coeffs[b] ^= -(signs & 1) & (1 ^ (Q-1));

It sets c->coeffs[b] to either 1 or Q-1, depending on the least significant bit of signs. This uses a standard technique in cryptographic code to select between two possibilities in constant time.

First, signs & 1 extracts the LSB. Then t = -(signs & 1) is 0 or -1 if the bit is 0 or 1, respectively. In the letter case t is the all ones bitstring in two's complement representation. It follows that c->coeffs[b] = 1 is XORed with 0 if t = 0, which leaves c->coeffs[b] = 1, or c->coeffs[b] = 1 is XORed with (1 ^ (Q-1)) resulting in 1 ^ (1 ^ (Q-1)) = (1 ^ 1) ^ (Q-1) = 0 ^ (Q-1) = Q-1.

On 04.05.19 23:18, LaszloHars wrote:

Thank for all of you for the quick responses! In the mean time I managed to compile Dilithium in Visual Studio 2017, without errors. See below my notes. I was puzzled with the expression: |-(signs & 1) & (1 ^ (Q - 1))| Not only it is incorrect by applying unary "-" to an unsigned expression, but what does it do?

|DILITHIUM - Visual Studio 2017 ============================== The reference C implementation is https://github.com/pq-crystals/dilithium It is written for GCC under Linux, and cannot be directly used elsewhere use of "attribute" #include #include <sys/syscall.h> use of dynamically sized arrays (instead of malloc or static sizes) unary "-" for unsigned value Linux random function GCC-syntax assembly code for accessing system timer There is an effort to collect clean implementations of the post-quantum schemes that are in the NIST post-quantum project: https://github.com/pqclean/pqclean See the website of Douglas Stebila: https://www.douglas.stebila.ca/ Several KEM schemes are already implemented, including CRYSTALS/Kyber768 Only one signature scheme (5/4/2019): sphincs-shake256-128f-simple Setup VS solution ----------------- Start a new Windows Console application add all .c and .h files from dilithium-master/ref to the project remove from the test project the 3 conflicting files with main test_mul.c test_vectors.c PQCgenKAT_sign.c remove the 2 files with unusable assembler code cpucycles.h cpucycles.c add to the solution test/speed.h test/speed.c Code changes for VC ------------------- delete from the project: randombytes.h randombytes.c NOT NEEDED as rng.c has an implementation ToDo: add default implementation for the function randombytes to generate true random bytes poly.h - line 9: remove attribute(...) packing.c - line 264: unary "-" for unsigned value (error) - is not "(1 ^ (Q-1))" always Q, since Q is an odd prime??? "(signs & 1)" is unsigned, it cannot have a unary "-". We may need type casts "(signs & 1) ? Q : 0" would not be constant time when compiled, but we don't know, what different versions of the compiler do with the original Only assembler could enforce constant time, but it is not portable sign.c - line 79: the same as above poly.c - line 364: (dynamic array size) buflen is a variable, not a constant change to unsigned char buf[((769 + STREAM128_BLOCKBYTES)/STREAM128_BLOCKBYTES)*STREAM128_BLOCKBYTES + 2]; - line 449 similar change to buf[buflen] by copying humangous expression into the length of buf[] - line 532 similar change to buf[buflen+4] testdilithium.c: add dummy function definitions {return 0;} for cpucycles_overhead() cpucycles_start() cpucycles_stop() remove #include "cpucycles.h" ToDo: add platform specific code for the timing functions above (do not remove #include "test/cpucycles.h" from poly.c fips202.c ) OpenSSL ------- OpenSSL has to be set up and made known to Visual Studio Failed: Copy all header files from openssl-master/include/openssl to a directory set Visual Studio to use the parent of this as include directory opensslconf.h is missing, it should be auto-generated by a Perl script. Need to install Perl... Tried to download a pre-generated Windows version from https://github.com/David-Reguera-Garcia-Dreg/Precompiled-OpenSSL-Windows/blob/master/openssl-1.1.0e-vs2012/include/openssl/opensslconf.h Fail: incompatible version, missing data Worked: Install OpenSSL for Visual Studio 2017: 1. Project -> Manage Nuget Packages 2. In the Browse Tab search for 'openssl' 3. Select openssl-vc141, and Install Linker setup ------------ linker errors: unresolved references to memcpy, memset... VC Debug Build specifics: add to properties->Linker->Input->Additional Dependencies vcruntime.lib ucrtd.lib (implicit: kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib) At this point the code compiles w/o errors but with warnings over type mismatches, unsafe intrinsic functions... |

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/pq-crystals/dilithium/issues/6#issuecomment-489366421, or mute the thread https://github.com/notifications/unsubscribe-auth/AHXVKDHXD72DQVHEXDIBKPLPTX4TJANCNFSM4HKV67SQ.

LaszloHars notifications@github.com wrote:

Thank for all of you for the quick responses! In the mean time I managed to compile Dilithium in Visual Studio 2017, without errors. See below my notes. I was puzzled with the expression: -(signs & 1) & (1 ^ (Q - 1)) Not only it is incorrect by applying unary "-" to an unsigned expression, but what does it do?

It's not incorrect, it's valid C and even one of the few things that are well-defined: for an unsigned integer x, -x is the integer that, when added to x, produces zero. In other words, what you get is the two's complement.

-(unsigned):

The 1999 C standard doesn't include an explicit statement and does not define the unary "-" behavior of unsigned types (section 6.5.3.3). The standard only says that some operators return values that depend on the internal representations of integers, and have implementation-defined and undefined aspects.

That is, we cannot rely on the behavior you are assuming. In fact, in certain platforms (processor, OS, compiler, libraries...) the code does not even compile (e.g. Windows, Visual Studio 2017). In other platforms the result is different.

The statement "for an unsigned integer x, -x is the integer that, when added to x, produces zero" is not proper. There may not be such a -x integer, or it depends on the platform. Furthermore, x is unsigned, -x is signed, so their addition is also undefined by C99.

Even if we only deal with processors of 2’s complement number representation, the CPU flags carry/overflow/negative/zero could be interpreted differently, which makes -x ambiguous. (A zero with a carry is zero or not?)

c->coeffs[b] ^= -(signs & 1) & (1 ^ (Q-1));

here (1 ^ (Q-1)) is always Q, if Q is odd. Q is a constant, therefore the expression is computed in compile time, and thus it can be replaced with just Q.

We used the construct of -(signs & 1) & ... in the 1960’s already, to avoid branches in the code. That is, this logic in machine code. It is not mainly a cryptographic technique.

Even if the platform makes -(unsigned) work as desired, (here the result is either 64 bits of 0s or 64 bits of 1s, so c->coeffs[b] will be XORed with 0 (no change) or XOR Q), we cannot assume that the C code translates to constant time machine code. The C standard does not make any claims about running time.

In general, C cannot assure constant execution time. Even if in a platform we get it, at the next compiler update we may not. To say nothing about other platforms. In my case, the final target can be a DSP with conditional instructions. The compiled machine code would have a comparison, a conditional reg = c->coeffs[b] ^ Q, and a few other operations. Will that be constant time?

On 05.05.19 13:49, LaszloHars wrote:

-(unsigned):

The 1999 C standard doesn't include an explicit statement and does not define the unary "-" behavior of unsigned types (section 6.5.3.3). The standard only says that some operators return values that depend on the internal representations of integers, and have implementation-defined and undefined aspects.

The standard says "the operand of the unary + or - operator shall have arithmetic type". This is further specified by "Integer and floating types are collectively called arithmetic types" and "the standard signed integer types and standard unsigned integer types are collectively called the standard integer types".

The statement "for an unsigned integer x, -x is the integer that, when added to x, produces zero" is not proper. There may not be such a -x integer, or it depends on the platform. Furthermore, x is unsigned, -x is signed, so their addition is also undefined by C99.

This statement is already in K&R C. The C99 standard says that "the result of the unary - operator is the negative of its (promoted) operand". There always exists an unsigned negative -x for every unsigned integer x because the C99 standard says "a computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type". So for x of type unsigned int, -x is really the negative of x modulo UINT_MAX + 1 and still of type unsigned int.

c->coeffs[b] ^= -(signs & 1) & (1 ^ (Q-1));

here (1 ^ (Q-1)) is always Q, if Q is odd. Q is a constant, therefore the expression is computed in compile time, and thus it can be replaced with just Q.

Sure, but writing 1 ^ (Q-1) makes it easier to understand what is going on here.

We used the construct of -(signs & 1) & ... in the 1960’s already, to avoid branches in the code. That is, this logic in machine code. It is not mainly a cryptographic technique.

I didn't say that it is mainly a cryptographic technique, just that it is a standard technique in crypto code.

Even if the platform makes -(unsigned) work as desired, (here the result is either 64 bits of 0s or 64 bits of 1s, so c->coeffs[b] will be XORed with 0 (no change) or XOR Q), we cannot assume that the C code translates to constant time machine code. The C standard does not make any claims about running time.

Yes, we can never be certain that compiled C code is really constant-time without checking the assembler output of the compiler. But this can be done and there are even tools to automatically do it in many cases. Moreover, even though compilers are in principle allowed to do whatever they want that gives the correct semantics, we can make assumptions about what a reasonable compiler would do. With this argument it would basically be impossible to write crypto code in C.

By the way, this expression in the Dilithium code doesn't need to be constant-time. So if you prefer you are free to write c->coeffs[b] = (signs & 1) ? (Q-1) : 1 here.

Cheers, Gregor

The standard says "the operand of the unary + or - operator shall have arithmetic type".

It doesn't say anything about the result, does it?

a computation involving unsigned operands can never overflow... result that cannot be represented by the resulting unsigned integer type is reduced modulo...

True, you can interpret this for our case as saying that -x is an unsigned value (if x is), that is either 0 or 2**64-1. But it has been debated for 20 years, since there is no signed type of C to promote a _uint64, and so the mixed intermediate operations cannot be directly performed in the computer, they need some reasoning.

For a signed y the expression -y can overflow, thus -y does not always exist (y = -2**63). This represents a problem with the C99 standard. Defining -x needs promotions to a theoretical larger type, which C does not have, and the details are missing from the standard.

As a practical matter, VC, the compiler used the most often under Windows interprets the C99 statement differently. Everyone, who intends to write portable code has to be aware of this controversy, and avoid -x for unsigned x. You could also say that VC is not conformant to the standard, but it is only not conformant to your interpretation of the standard. We will have a never-ending religious war.

It is possible to disable the error checking of negated unsigned values in VC, which makes the original Dilithium expression to work. Still, it is bad practice to remove error checks and messages.

it would basically be impossible to write crypto code in C

Only: impossible to write portable crypto code in C, which runs in constant time. You can check the compiled code for constant time, but you should not tweak the C code to achieve it. Instead, leave it to the software implementer to write the critical parts in his assembler. Giving guidelines and suggestions is helpful. Making assumptions about future compilers or unknown platforms is dangerous.

you are free to write c->coeffs[b] = (signs & 1) ? (Q-1) : 1 here.

Maybe, but wouldn't it give different results from the original (c->coeffs[b] ^= -(signs & 1) & (1 ^ (Q-1)))? I would write: c->coeffs[b] ^= (signs & 1) ? Q : 0 or even if (signs & 1) {c->coeffs[b] ^= Q;}

LaszloHars notifications@github.com wrote:

There are, as far as I understand, three parts of the C99 standard that are relevant here: First, 6.2.5 C9 stating

"A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type."

What this is saying is that arithmetic on unsigned integers of N bits is by definition arithmetic modulo 2^N.

Now, what is the semantics of a unary minus? Well, 6.5.3.3 C3 says

"The result of the unary - operator is the negative of its (promoted) operand. The integer promotions are performed on the operand, and the result has the promoted type."

OK, so we do get the negative of the promoted type. What is this type? Well, 6.3.1.1 C2 says

"The following may be used in an expression wherever an int or unsigned int may be used:

An object or expression with an integer type whose integer conversion rank is less than the rank of int and unsigned int.
A bit-field of type _Bool, int, signed int, or unsigned int.

If an int can represent all values of the original type, the value is converted to an int ; otherwise, it is converted to an unsigned int.
These are called the integer promotions. All other types are unchanged by the integer promotions."

Now, uint64_t is mapped to either a "long unsigned int" or a "long long unsigned int" (and certainly not to something with a conversion rank lower than int), so the type promotion does not change the type. This means, that the unary minus simply computes the negative modulo 2^64 of the argument, which happens to be the two's complement.

The Microsoft compiler also translates this correctly, yet not without warnings (specifically, C4146). I'm assuming that there is some good reason behind this warning, which probably is along the lines of "typically, programmers who apply the unary minus to an unsigned type really mean something else, so this is a likely source of bugs". If you are concerned about this warning, then replacing -X by ~X+1 is totally fine, but you could argue what the more concise and idiomatic way is to express that you want the two's complement of a uint64_t.

pq-crystals / dilithium

Clean C version? #6