Essere in grado di elaborare stringhe di lunghezza arbitraria senza perdere informazioni sulla loro lunghezza sembra essere molto difficile (cioè non vedo come farlo) a causa delle cache . Una stringa molto lunga, per definizione, occuperà molto spazio e pertanto la lettura della stringa comporterà un'interazione con le cache. L'accesso alla stringa dalla RAM attiverà i miss della cache e sfrutta anche altri elementi di dati dalla cache, influenzando il comportamento futuro del codice dell'applicazione. Una perdita di cache costa dozzine o anche centinaia di cicli di clock: è almeno dieci volte più visibile, dall'esterno, che una miserazione di ramo. Se ti preoccupi delle filiali, dovresti preoccuparti molto di più delle cache.

Tuttavia, possiamo imbrogliare con padding . Supponiamo che tu possa disporre che le due stringhe che vuoi confrontare siano scritte all'inizio di due grandi buffer di uguale grandezza pieni di zeri; inoltre, supponiamo che un byte di valore 0 non possa apparire in una stringa normale (ad esempio, queste sono stringhe C). Quindi tutto ciò che serve è fare un confronto senza perdite tra i due buffer , che hanno la stessa lunghezza. La lunghezza del buffer verrà persa, ma è un parametro fisso, costante e pubblicamente noto, quindi non è un problema.

Questo non risolve il problema; lo muove. Ora, devi assicurarti che qualunque cosa abbia prodotto le stringhe potrebbe scriverle nei buffer senza perdere le informazioni sulle dimensioni. In generale, non hai più stringhe . Hai valori binari di una determinata lunghezza fissa che copi con una grande memcpy() ; questi valori hanno solo una interpretazione delle stringhe in cui i byte sono considerati caratteri, fino al primo byte del valore zero.

Da un punto di vista più elevato, avere una "funzione di confronto delle stringhe sicure" è come portare un secchio a bordo del Titanic. Se il tuo codice gestisce dati segreti, allora tutto che fai con i dati è potenzialmente soggetto ad attacchi temporali. In generale, l'applicazione può essere di due tipi:

• Se la parte segreta solo è un singolo elemento crittografico e tutto il resto è pubblico, usare un po 'di primitive prive di perdite ha senso e migliorerà la sicurezza generale. Un classico esempio è una Autorità di certificazione , dove l'unica parte segreta è la chiave privata della CA; finché l'algoritmo della firma non perde segreti, l'intero sistema è robusto contro gli attacchi temporali. Allo stesso modo, un sito Web che esegue l'autenticazione basata su password ma che altrimenti contiene solo dati pubblici andrà bene.

• Se la segretezza è diffusa in tutto il sistema, ad esempio un sito Web che esegue l'autenticazione basata su password per consentire l'accesso ad alcuni dati riservati, la concentrazione sul confronto delle stringhe non raggiunge il punto. Il intero codice server deve essere reso privo di perdite, e questo è uno sforzo considerevolmente più difficile (e non sappiamo davvero come farlo).

In ogni caso, cercare di proteggere un dato pezzo di codice contro gli attacchi dei canali laterali diventa più difficile quando la lingua è più "di alto livello". Un linguaggio come PHP, con la sua gestione automatica della memoria (il garbage collector) e la gestione delle stringhe (la stringa è valori proprio come gli interi) non aiuta affatto. Questo è il motivo per cui devono essere fornite primitive di basso livello implementate in C (come una funzione di confronto di stringhe senza perdite), ma il problema è molto più ampio e comprende anche molto codice PHP.

Se si assume un avversario che può osservare i modelli di accesso alla memoria attraverso perdite di cache, allora è sciocco cercare di proteggere contro l'avversario che impara la lunghezza del segreto. Lo saprà sempre. L'unico modo per proteggersi da questo è garantire che si possa accedere oltre la fine della stringa senza segfaulting, cosa che quasi sicuramente non si può fare senza sovra-allocare ogni stringa nel linguaggio di programmazione.

Hai studiato le esigenze dei programmatori PHP che desiderano questa funzione?

Nelle applicazioni pratiche che riesco a pensare - verificando password, token di sessione, ecc. la stringa conosciuta sarebbe relativamente piccola, diciamo < 64 byte; all'interno di una riga della cache Intel. Quindi la tua implementazione banale non causerebbe in realtà pattern di accesso alla cache diversi.

Se hai davvero bisogno di confrontare le stringhe lunghe senza perdite di lunghezza, dovresti invece considerare il confronto degli hash.

Correggimi se ho torto (in risposta a Thomas, ma anche per rispondere in generale alla domanda originale), ma dovresti essere in grado di cercare controlli senza perdite con il tuo codice. In questo esempio, "noto" è un valore noto, che è stato pre-incorporato in un buffer, I.e. Se il valore conosciuto è "qwerty" e si consente una lunghezza massima di 64, allora "qwerty" è precompilato (inizializzato e memorizzato una sola volta al momento del caricamento) in un buffer di 64, che garantisce che i carichi di memoria siano sempre costanti senza dare nulla via). In questo caso sapremo solo se si trova nella cache o meno da una mancanza della cache. Replica del codice nel post originale.

int check(char *known, size_t known_len, char *unknown, size_t unknown_len, size_t max_len) {

size_t i;
int result = 0;

  // Constant time check, only gives away maximum length.
  if (unknown_len > max_len)
      return 0;

  // Will only give away the length of the attackers string, unless it was already too large (condition above).  Don't bother doing an extra memcpy on your known or the attackers.
  for (i = 0; i < unknown_len; i++) {
      result |= known[i] ^ unknown[i];
  }

  return result == 0 ? 1 : 0;
}

Semplicemente ...

... non confrontare le stringhe , confronta i loro hash !

Sì, intendo questo per la sicurezza temporale (l'effetto collaterale della sicurezza della password, lasciato da parte).

Che cosa fa

Quando confronti gli hash, non devi preoccuparti del seguito (che potrebbe non essere ovvio all'inizio)

• Il processo di hashing richiede più tempo, per stringhe più lunghe

  Perché? L'hash corretto che si sta confrontando l'input dell'utente è (ovviamente) di lunghezza fissa, l'unica informazione che un utente potrebbe ottenere è la durata del programma per hash il suo input (peggiore caso, questo potrebbe dare qualche suggerimento sull'algoritmo di hashing di underling, la cui segretezza non dovrebbe essere invocata comunque)

  L'unica eccezione è, se non è possibile memorizzare l'hash corretto da qualche parte. Dovendo prima calcolarlo, ovvero occuparsi direttamente della password , riporta nuovamente gli stessi problemi di password / lunghezza.

• Errori errati nella cache o errori di cache

  Ovviamente, come accennato in precedenza, l'hash corretto è sempre della stessa lunghezza, indipendentemente dalla durata della password corretta di un determinato utente.

Seriamente, questo semplice processo rende un problema banale da uno molto difficile.

Informazioni sulla potenza hash

Se stai utilizzando un processo di hashing debole (o uno con ridicola entropia), potresti considerare di controllare ulteriormente l'uguaglianza diretta delle password (dopo un risultato positivo dal confronto degli hash), per proteggerti dalle collisioni.

Ciò tuttavia perderà le informazioni sul tempo / richiederà più tempo, quando si verificherà una collisione.

Bottom-line: non usare algoritmi di hashing deboli, applicare un po 'di sale, e dovresti stare bene! ; -)