# gcc constant time implemenation [closed]

I need to make the following function time constant - I have already removed if statements and have written it down to one line in the loop.

    /******************/
uint8_t dseed[54];  // only 0 and 1 like {0,1,0,1,1,1,0,0,1,0,...}
uint8_t fecb[256];
const unsigned char g[55] = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,...};
/******************/

memset(fecb,0,54*sizeof(uint8_t));
for (int i = 255; i >= 0; i--) {
int feedback = dseed[i] ^ fecb[53];
for (int j = 53; j > 0; j--){
fecb[j] = fecb[j - 1] ^ (feedback && g[j]);
}
fecb[0] = g[0] && feedback;
}


The code in my eyes looks constant time but when I measure it, it is not. Cycles vary between 165k and 185k.

The assembly code contains a conditional jump.

  for (int i = PARAM_K - 1; i >= 0; i--) {               //PARAM_K = 256
0xC0000556:   C5 04 3F 30  LEA       a4,0xFF
0xC000055A:   7B 00 00 4C  MOVH      d4,0xC000
> 0xC000059A:   B0 F4        ADD.A     a4,-0x1
> 0xC000059E:   FD 70 47 00  LOOP      a7,0xC000062C
> 0xC0000622:   B0 F4        ADD.A     a4,-0x1
> 0xC0000626:   FD 70 03 00  LOOP      a7,0xC000062C
> 0xC000062A:   3C BC        J         0xC00005A2
> 0xC000062C:   39 AF 37 00  LD.BU     d15,[a10]0x37
> 0xC0000630:   3C A1        J         0xC0000572
> 0xC0000632:   00 A0        DEBUG
> 0xC0000634:   3C D0        J         0xC00005D4

feedback = dseed[i] ^ fecb[LENGTH - PARAM_K - 1];        //LENGTH = 310
0xC0000572:   D9 AF 38 00  LEA       a15,[a10]0x38
0xC0000578:   08 05        LD.BU     d5,[a15]0x0
0xC000057A:   C5 0F 34 00  LEA       a15,0x34
0xC000057E:   C6 F5        XOR       d5,d15
0xC0000580:   DA 35        MOV       d15,0x35
0xC0000582:   DF 05 40 80  JNE       d5,0x0,0xC0000602  <----- JNE
> 0xC00005D4:   82 7F        MOV       d15,0x7                    |
> 0xC00005D6:   C5 0F 35 00  LEA       a15,0x35                   |
|
for (int j = LENGTH - PARAM_K - 1; j > 0; j--)        |
fecb[j] = fecb[j - 1] ^ (feedback && g[j]);       |
0xC0000586:   92 F2        ADD       d2,d15,-0x1                |
0xC0000588:   01 22 00 36  ADDSC.A   a3,a2,d2,0x0               |
0xC000058C:   14 33        LD.BU     d3,[a3]                    |
0xC000058E:   10 23        ADDSC.A   a3,a2,d15,0x0              |
0xC0000590:   02 2F        MOV       d15,d2                     |
0xC0000592:   34 33        ST.B      [a3],d3                    |
0xC0000594:   FC F9        LOOP      a15,0xC0000586             |
> 0xC0000602:   60 4E        MOV.A     a14,d4           <---------|
> 0xC0000604:   92 F3        ADD       d3,d15,-0x1
> 0xC0000606:   10 E6        ADDSC.A   a6,a14,d15,0x0
> 0xC0000608:   01 23 00 56  ADDSC.A   a5,a2,d3,0x0
> 0xC000060C:   10 23        ADDSC.A   a3,a2,d15,0x0
> 0xC000060E:   0C 60        LD.BU     d15,[a6]0x0
> 0xC0000610:   14 52        LD.BU     d2,[a5]
> 0xC0000612:   8B 0F 20 F2  NE        d15,d15,0x0
> 0xC0000616:   C6 2F        XOR       d15,d2
> 0xC0000618:   2C 30        ST.B      [a3]0x0,d15
> 0xC000061A:   02 3F        MOV       d15,d3
> 0xC000061C:   FC F3        LOOP      a15,0xC0000602

fecb[0] = g[0] && feedback;
0xC0000596:   8B 05 20 F2  NE        d15,d5,0x0
> 0xC000059C:   2C A2        ST.B      [a10]0x2,d15
> 0xC000061E:   8B 05 20 F2  NE        d15,d5,0x0
> 0xC0000624:   2C A2        ST.B      [a10]0x2,d15
}


Is this conditional jump responsible for the varying #cycles? ´

I already tried to compile this code snipped using __attribute__((optimize("O0"))), and I also tried volatile int feedback. Using the volatile keyword, this JNE disappears, but the code still isn't executed in constant time (because of stalls when writing/reading memory maybe?). Cycles vary between 215k and 235k using the volatile keyword.

Can this code efficiently made constant time? Is there some conditional branch I am missing?

Thank you for any help

• I'm not sure whether it will help, but have you tried unrolling the loop? – Mast Sep 27 '18 at 10:49
• no because, the value of "feedback" depends on "fecb" which is assigned in the inner for-loop, so i cannot unroll it right? and it will be 13500 or more lines :/ – jonnyx Sep 27 '18 at 10:59
• Not easily, but not impossible either. If it's really that critical to do optimize it might be worth a try. At the moment, I see a loop in a loop. That won't run in constant time. Take a good look at what constant time would mean. Since i is size(fecb) - 1 and j is size(dseed) - 1, execution time will be based on those sizes. – Mast Sep 27 '18 at 11:07
• Anyhow, the way your question is phrased, it asks for an explanation of your code. We don't do well with explanations of your code. You wrote it, you should know why it does what it does. If performance of your code is an issue, please describe in some detail what it's supposed to do so we can provide proper feedback on your approach. Please take a look at the help center. – Mast Sep 27 '18 at 11:11
• @firda, thank you!!!!!, I just checked and my code also runs through if using & instead of &&. then i checked the times - every run takes the same amount of cycles!! If you post an answer, I will accept it! Thank you – jonnyx Sep 27 '18 at 13:17

That appears to be crucial for the code: feedback && g[j] and g[0] && feedback.
• Note that feedback && g[j] and feedback & g[j] do not compute to the same value. A functional equivalent is !!feedback & !!g[j] is the same - but may not be time constant. IAC, unclear what functionality OP wants here. – chux - Reinstate Monica Sep 27 '18 at 21:03
• @chux: Given the comment // only 0 and 1 like {0,1,0,1,1,1,0,0,1,0,...} and other signs (fecb[0] = g[0] && feedback; and fecb[j] = fecb[j - 1] ^ (feedback && g[j]);), it was not unreasonable to assume all are indeed ones or zeroes. Anyway, the mixing of binary operators (^ instead of !=) with logical ones (&& vs. &) is indeed strange as well as the mixture of types (char, uint8_t, int). – user52292 Sep 27 '18 at 21:27
• Yes, using only 0 and 1 make a & b and a && b functionally the same. – chux - Reinstate Monica Sep 27 '18 at 21:35