Implementazione di un ordinamento, tipo di attacco resistente alla cache in C

Question

Declinazione di responsabilità: Sono consapevole che l'implementazione della propria crittografia è una pessima idea. Questo fa parte di una tesi di master, il codice non verrà utilizzato nella pratica.

Come parte di un algoritmo crittografico più grande, ho bisogno di ordinare una matrice di lunghezza costante (piccola, 24 per essere precisi), senza perdite di informazioni sul contenuto di questo array. Per quanto ne so (si prega di correggermi se questi non sono sufficienti a prevenire temporizzazione e di cache attacchi), questo significa:

1. L'ordinamento deve essere eseguito nella stessa quantità di cicli in termini di lunghezza della matrice, indipendentemente dai valori particolari della matrice
2. l'ordinamento non dovrebbe diramare o memoria ad accesso a seconda delle particolari valori dell'array

esistono tali implementazioni? In caso contrario, ci sono buone risorse su questo tipo di programmazione?

Per essere onesti, sto persino lottando con il sottoprogetto più semplice, vale a dire trovare il valore più piccolo di un array.

double arr[24]; // some input 
double min = DBL_MAX; 

int i; 
for (i = 0; i < 24; ++i) { 
    if (arr[i] < min) { 
     min = arr[i]; 
    } 
} 

Sarebbe l'aggiunta di un else con un incarico fittizio essere sufficiente per rendere i tempi di sicurezza? In tal caso, come faccio a garantire che il compilatore (GCC nel mio caso) non annulli il mio duro lavoro? Sarebbe suscettibile agli attacchi della cache?

Answer 1

Utilizzare una rete di ordinamento, una serie di confronti e scambi.

La chiamata di scambio non deve dipendere dal confronto. Deve essere implementato in modo da eseguire la stessa quantità di istruzioni, indipendentemente dal risultato del confronto.

Ti piace questa:

void swap(int* a , int* b , bool c) 
{ 
    const int min = c ? b : a; 
    const int max = c ? a : b; 
    *a = min; 
    *b = max; 
} 

swap(&array[0] , &array[1] , array[0] > array[1]); 

poi trovare il rete di ordinamento e utilizzare swap. Qui è un generatore che fa per voi: http://pages.ripco.net/~jgamble/nw.html

Esempio 4 elementi, i numeri sono indici di array, generati dal link:

SWAP(0, 1); 
SWAP(2, 3); 
SWAP(0, 2); 
SWAP(1, 3); 
SWAP(1, 2); 

Answer 2

Un molto banale, costante di tempo (ma anche altamente in-efficiente) genere ad

• avere uno src e arrivo matrice
• per ciascun elemento della filtrate) matrice di destinazione (, scorrere la matrice sorgente completo per trovare l'elemento che appartiene exa solo in questa posizione.

Nessuna interruzione anticipata, (quasi) tempismo costante, non dipendente dalla ordinamento parziale della sorgente.

Answer 3

Questo è un ordinamento di bolle molto stupido che in realtà funziona e non si dirama o modifica il comportamento di accesso alla memoria a seconda dei dati di input. Non sono sicuro che questo possa essere inserito in un altro algoritmo di ordinamento, hanno bisogno dei loro confronti separati dagli swap, ma forse è possibile, lavorarci adesso.

#include <stdint.h> 

static void 
cmp_and_swap(uint32_t *ap, uint32_t *bp) 
{ 
     uint32_t a = *ap; 
     uint32_t b = *bp; 
     int64_t c = (int64_t)a - (int64_t)b; 
     uint32_t sign = ((uint64_t)c >> 63); 
     uint32_t min = a * sign + b * (sign^1); 
     uint32_t max = b * sign + a * (sign^1); 
     *ap = min; 
     *bp = max; 
} 

void 
timing_sort(uint32_t *arr, int n) 
{ 
     int i, j; 
     for (i = n - 1; i >= 0; i--) { 
       for (j = 0; j < i; j++) { 
         cmp_and_swap(&arr[j], &arr[j + 1]); 
       } 
     } 
} 

La funzione cmp_and_swap compila a (versione di Apple LLVM 7.3.0 (clang-703.0.29), compilato con -O3):

_cmp_and_swap: 
00000001000009e0  pushq %rbp 
00000001000009e1  movq %rsp, %rbp 
00000001000009e4  movl (%rdi), %r8d 
00000001000009e7  movl (%rsi), %r9d 
00000001000009ea  movq %r8, %rdx 
00000001000009ed  subq %r9, %rdx 
00000001000009f0  shrq $0x3f, %rdx 
00000001000009f4  movl %edx, %r10d 
00000001000009f7  negl %r10d 
00000001000009fa  orl  $-0x2, %edx 
00000001000009fd  incl %edx 
00000001000009ff  movl %r9d, %ecx 
0000000100000a02  andl %edx, %ecx 
0000000100000a04  andl %r8d, %edx 
0000000100000a07  movl %r8d, %eax 
0000000100000a0a  andl %r10d, %eax 
0000000100000a0d  addl %eax, %ecx 
0000000100000a0f  andl %r9d, %r10d 
0000000100000a12  addl %r10d, %edx 
0000000100000a15  movl %ecx, (%rdi) 
0000000100000a17  movl %edx, (%rsi) 
0000000100000a19  popq %rbp 
0000000100000a1a  retq 
0000000100000a1b  nopl (%rax,%rax) 

Solo accessi alla memoria sono la lettura e la scrittura della matrice , niente rami. Il compilatore ha capito cosa effettivamente fa la moltiplicazione, in realtà abbastanza intelligente, ma non ha usato i rami per quello.

I cast per int64_t sono necessari per evitare overflow. Sono abbastanza sicuro che possa essere scritto più pulito.

Come richiesto, ecco una funzione di confronto per il doppio:

void 
cmp_and_swap(double *ap, double *bp) 
{ 
     double a = *ap; 
     double b = *bp; 
     int sign = signbit(a - b); 
     double min = a * sign + b * (sign^1); 
     double max = b * sign + a * (sign^1); 
     *ap = min; 
     *bp = max; 
} 

codice compilato è senza rami e non cambia modello di accesso alla memoria a seconda dei dati di input.