comparaisons en "temps constant"

Le
Manuel P
Bonjour,

Je m'interroge sur certaines des techniques proposées dans [1]. Un peu
de contexte : il s'agit d'éviter les fuites d'information par mesure du
temps d'exécution dans du code cryptographique, et ce qui me pose
particulièrement question est le fait de n'utiliser que des opérations
bit à bit plutôt que les opérateurs '==' et '!=' quand ils seraient
naturels. (Je n'ai par contre bien sûr aucun doute concernant le fait
d'éviter les sorties de boucles dépendant des données comme dans
l'exemple initial de memcmp().)

[1]: https://cryptocoding.net/index.php/Coding_rules#Solution

Pour commencer, j'ai l'impression qu'il y a des soucis potentiels/
théoriques de portabilité, par exemple :

/* Return 1 if condition is true, 0 otherwise */
int ct_isnonzero_u32(uint32_t x)
{
return (x|-x)>>31;
}

On va dire qu'on se limite aux plateformes où uint32_t existe, de toutes
façons si c'est pas le cas ça se verra vite à la compilation :)
Imaginons par contre que le compilo ait choisit des int de 64 bits. Sauf
erreur de ma part, x va être promu en int et, dans le cas x != 0, on se
retrouve à appliquer un décalage sur un négatif, ce qui est défini par
l'implémentation, et au moins une des options raisonnables pour une
implémentation (propager le bit de signe) ne donne pas le résultat
attendu (-1 au lieu de 1 si x != 0). (Par contre je ne vois pas d'UB.)

Il me semble que ce problème (tout théorique à ma connaissance) peut
être résolu en ajoutant un cast:

return (x | (uint32_t) -x) >> 31;

Est-ce que vous confirmez cette analyse ou j'ai manqué quelque chose ?

Par ailleurs, la raison souvent évoquée pour préférer ce genre de
construction à un simple return x != 0, est que certains compilos
risquent de générer un saut conditionnel, ce qu'on souhaite éviter. Bon.
En même temps, comme noté un peu plus bas sur la page citée, le compilo
fait bien ce qu'il veut, et il peut aussi bien générer une branche si on
écrit des opérations de bits, que ne pas en générer pour un '!='. De
fait, j'ai examiné l'assembleur produit par GCC et Clang (récents) avec
différents niveaux d'optimisation pour x86 et ARM (les deux seuls
assembleurs que je lis un peu) avec "return x != 0;" et il m'a paru
exempt de branches ou autre construction en temps non constant. Ce qui
bien sûr ne prouve rien, et je n'ai pas trouvé de résultats de test à
une échelle un peu plus grande.

Après, il semble en effet raisonnable de supposer que des opérations sur
les bits sont moins susceptibles d'être traduites en branches que des
opérateurs de comparaison, vu que pour ça il faut (1) que le compilo
"comprenne" ce qu'on fait et (2) qu'il décide qu'une branche est lq
meilleure façon d'exprimer ça. Si on utilise des opérateurs de
comparaison, la condition (1) est automatiquement rempile.

En même temps, en face de ce bénéfice potentiel, on a un coût qui lui
n'est pas du tout hypothétique en termes de lisibilité du code (voire de
risque de se planter en écrivant du code trop astucieux).

Bien sûr la seule solution sûre, c'est d'écrire les parties critiques en
assembleur directement, mais ça pose d'autres questions en termes du
nombre de plateformes à supporter et/ou de sécurité potentiellement
inégale suivant les plateformes.

Bref, vous en pensez quoi ? Dans les cas où l'assembleur n'est pas une
option, vous l'écririez comment, cette fonction isnonzero() ?

Merci d'avance pour vos remarques et conseils,
Manuel.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Samuel DEVULDER
Le #26343688
Le 13/03/2015 01:33, Manuel Pégourié-Gonnard a écrit :

Pour commencer, j'ai l'impression qu'il y a des soucis potentiels/
théoriques de portabilité, par exemple :

/* Return 1 if condition is true, 0 otherwise */
int ct_isnonzero_u32(uint32_t x)
{
return (x|-x)>>31;
}

On va dire qu'on se limite aux plateformes où uint32_t existe, de toutes
façons si c'est pas le cas ça se verra vite à la compilation :)



En fait le problème du code ci-dessus est qu'il ne marche que si x est
encodé en binaire *complément à deux*. Sur les machines binaires
*complément à un*, ca ne marche pas car ca retournera toujours 1 (-x et
~x sont identique dans cette représentation)

a+

sam.
Antoine Leca
Le #26343760
Le 13/03/2015 00:33Z, Manuel Pégourié-Gonnard écrivit :
On va dire qu'on se limite aux plateformes où uint32_t existe, de
toutes façons si c'est pas le cas ça se verra vite à la compilation
:)



Et les techniques pour éviter les fuites d'information en fonction du
temps d'exécution sur les PDP-10 ou les Univac avec des char de 9 bits,
je ne sais pas si c'est ce qui importe le plus...

/* Return 1 if condition is true, 0 otherwise */
int ct_isnonzero_u32(uint32_t x) { return (x|-x)>>31; }
Imaginons par contre que le compilo ait choisit des int de 64 bits.
[...] une des options raisonnables pour une implémentation (propager
le bit de signe) ne donne pas le résultat attendu



Bah, c'est comme d'habitude en fait. Tu rajoutes du code pour traiter un
(supposé) problème, et au passage tu rajoutes de bogues.

Là où c'est plus inquiétant, c'est qu'un texte de prescription sur la
sûreté (ou la sécurité) ne soit pas un tant soit peu sérieux sur ce
risque, alors que par exemple cela fait maintenant 18 ans que les RFC de
l'IETF doivent nécessairement inclure un alinéa sur l'impact prçu en
terme de sécurité des prescriptions du texte...

Mais comme dit le texte que tu cites:
The above measures are best effort [...]


Bien sûr la seule solution sûre, c'est d'écrire les parties critiques
en assembleur directement,



Même pas. Cf. Ken Thomson, "Reflection on trusting trust." Si tu ne fais
pas confiance au compilateur C, pourquoi diable devrais-tu faire
confiance à l'assembleur ?
Et si tu écris le programme toi-même en langage machine, et que tu le
programmes aux clés, qu'est-ce qui te dit que le micro-programme du
silicium ne va pas lui-même faire ses propres modifications, par exemple
réorganiser tes décalages soigneusement réarrangé, repérer que tout cela
revient à juste tester si x (OK, le registre 8) vaut ou pas zéro, et
reprogrammer par exemple en un saut prédictif au niveau de l'appel de
cette fonction ?
:-)

Antoine
Manuel P
Le #26343846
Le Fri, 13 Mar 2015 14:05:35 +0100, Antoine Leca a écrit :

Le 13/03/2015 00:33Z, Manuel Pégourié-Gonnard écrivit :
On va dire qu'on se limite aux plateformes où uint32_t existe, de
toutes façons si c'est pas le cas ça se verra vite à la compilation :)



Et les techniques pour éviter les fuites d'information en fonction du
temps d'exécution sur les PDP-10 ou les Univac avec des char de 9 bits,
je ne sais pas si c'est ce qui importe le plus...



Oui, tout à fait.

/* Return 1 if condition is true, 0 otherwise */
int ct_isnonzero_u32(uint32_t x) { return (x|-x)>>31; }
Imaginons par contre que le compilo ait choisit des int de 64 bits.
[...] une des options raisonnables pour une implémentation (propager le
bit de signe) ne donne pas le résultat attendu



Bah, c'est comme d'habitude en fait. Tu rajoutes du code pour traiter un
(supposé) problème, et au passage tu rajoutes de bogues.



C'est un peu l'impression que j'avais. Ceci dit, il me semble que les bogues
ici peuvent se régler, en castant -x vers uint32_t.

Après, la question que je me pose en dans ce cas, c'est

1. est-ce que les risques associés à == ou != sont réels ?
2. est-ce que le remplacer par des manipulations de bits réduit effectivement
le risque ?
3. est-que le jeu en vaut la chandelle quand on compare ça au risque
d'introduire de nouveaux problèmes ?

En fait, j'ai du mal à me faire une opinion sur les points 1 et 2, de
mon point de vue tant qu'aucune des personnes à qui j'en parle n'est
capable de me citer un cas concret de compilo qui génère une branche
avec == et pas avec une manip comme ci-dessus, on est plus dans le FUD
que dans une approche rationnelle.

Après, il y a un certain nombre de gens plus compétents que moi qui
militent pour le remplacement de == par des opération sur les bits, mais
l'argument d'autorité...

Là où c'est plus inquiétant, c'est qu'un texte de prescription sur la
sûreté (ou la sécurité) ne soit pas un tant soit peu sérieux sur ce
risque, alors que par exemple cela fait maintenant 18 ans que les RFC de
l'IETF doivent nécessairement inclure un alinéa sur l'impact prçu en
terme de sécurité des prescriptions du texte...



En fait j'ai l'impression que le texte est sérieux en termes de sécurité
et qu'il introduit juste involontairement des problèmes de portabilité,
peut-être parce que c'est implicitement clair dans la tête de l'auteur
que les seules plateformes intéressantes sont celles où les int font au
plus 32 bits et sont représentés en complément à 2. Ce qui n'est pas
forcément très loin de ce qu'on disait plus haut sur le fait que les
plateformes où uint32_t n'existe pas ne nous intéresse pas beaucoup,
sauf que ça mériterait d'être explicité.

Bien sûr la seule solution sûre, c'est d'écrire les parties critiques
en assembleur directement,



Même pas. Cf. Ken Thomson, "Reflection on trusting trust." Si tu ne fais
pas confiance au compilateur C, pourquoi diable devrais-tu faire
confiance à l'assembleur ?



Je n'aurais pas du dire "sûre" sans préciser par rapport à quel risque.

J'envisageais ici uniquement le risque associé au fait que le compilo
est libre de traduire mon code C comme il veut tant qu'il respecte la
sémantique de la machine abstraite définie par le standard, y compris en
transformant du code apparemment exempt de saut conditionnels dépendants
d'une valeur secret en code qui en contient. Alors que l'assembleur, il
est vraiment pas censé fait ça.

Bien sûr tu as raison de préciser qu'en général ce n'est pas le seul
risque. Mais un problème à la fois, là je m'intéresser au fait que même
si je fais confiance au compilo pour faire son boulot, bah parmi les
choses qui sont son boulot, y'en a qui peuvent poser problème.

Et si tu écris le programme toi-même en langage machine, et que tu le
programmes aux clés, qu'est-ce qui te dit que le micro-programme du
silicium ne va pas lui-même faire ses propres modifications, par exemple
réorganiser tes décalages soigneusement réarrangé, repérer que tout cela
revient à juste tester si x (OK, le registre 8) vaut ou pas zéro, et
reprogrammer par exemple en un saut prédictif au niveau de l'appel de
cette fonction ?
:-)



Oui, si on va par là... :)

Manuel.
Manuel P
Le #26343853
[désolé pour la fausse réponse qui casse le fil, mais pour une raison qui
m'échappe le message de Samuel n'apparait pas sur le serveur que j'utilise, je
fais donc un copier-coller depuis google groups...]

Samuel DEVULDER a écrit :
Le 13/03/2015 01:33, Manuel Pégourié-Gonnard a écrit :

> Pour commencer, j'ai l'impression qu'il y a des soucis potentiels/
> théoriques de portabilité, par exemple :
>
> /* Return 1 if condition is true, 0 otherwise */
> int ct_isnonzero_u32(uint32_t x)
> {
> return (x|-x)>>31;
> }
>
> On va dire qu'on se limite aux plateformes où uint32_t existe, de toutes
> façons si c'est pas le cas ça se verra vite à la compilation :)

En fait le problème du code ci-dessus est qu'il ne marche que si x est
encodé en binaire *complément à deux*. Sur les machines binaires
*complément à un*, ca ne marche pas car ca retournera toujours 1 (-x et
~x sont identique dans cette représentation)



Ah oui, bien vu, j'avais totalement manqué ce problème des zéros
négatifs (qui se pose aussi en représentation signe-magnitude). Par
contre il me semble que ce problème disparait si on fait :

return ((uint32_t) x | (uint32_t) -x) >> 31;

vu que le cast produit un zéro non signé, et que même s'il était
converti ensuite en int, il ne pourrait plus produire un zéro négatif,
vu que la norme liste exhaustivement les sources potentielles de zéros
négatifs et que les conversions n'en font pas partie. Enfin sauf si j'ai
encore manqué quelque chose :)

Manuel.
Manuel P
Le #26343865
Le Fri, 13 Mar 2015 21:12:26 +0100, Manuel Pégourié-Gonnard a écrit :

> /* Return 1 if condition is true, 0 otherwise */
> int ct_isnonzero_u32(uint32_t x)
> {
> return (x|-x)>>31;
> }
>
En fait le problème du code ci-dessus est qu'il ne marche que si x est
encodé en binaire *complément à deux*. Sur les machines binaires
*complément à un*, ca ne marche pas car ca retournera toujours 1 (-x et
~x sont identique dans cette représentation)



Ah oui, bien vu, j'avais totalement manqué ce problème des zéros
négatifs (qui se pose aussi en représentation signe-magnitude).



Euh je reviens là-dessus... on est d'accord que le problème ne se pose
que si on a aussi des int plus larges que 32 bits ? Parce que sinon il
n'y pas de promotion de uint32_t vers un type signé, et du coup la
question de la représentation des entiers signés ne se pose pas.

return ((uint32_t) x | (uint32_t) -x) >> 31;



Euh... j'avais du perdre de vue un ou deux trucs quand j'ai écrit le
premier cast, parce que x est déjà un uint32_t ici...

Manuel.
Samuel DEVULDER
Le #26343882
Le 13/03/2015 21:12, Manuel Pégourié-Gonnard a écrit :
[désolé pour la fausse réponse qui casse le fil, mais pour une raison qui
m'échappe le message de Samuel n'apparait pas sur le serveur que j'utilise, je
fais donc un copier-coller depuis google groups...]



C'est parce que j'avais écrit une bêtise et que j'ai supprimé mon
message sitôt la bêtise identifiée, mais google-group semble ignorer les
cancels.

Quelle bêtise ? J'ai lu int32_t et pas uint32_t. Du coup mon argument
tombe à l'eau.

Cependant la question peut se poser de savoir quelle est la sémantique
formelle de -x quand x est unsigned. Pour moi ca fait un overflow.
Peut-être vaudrait-il mieux écrire "1u + ~x" à la place ?

Un point à noter: si on travaille en complément à deux on peut aussi se
passer du décalage à droite en écrivant: -(x|-x)

Pourquoi?

Si x!=0, on peut écrire x de la forme
x = bbbb..bb01..11 (b = bits quelconques)
-x = pppp..pb10..01 (p = inverse des bits b)
x|-x = 1111..1111..11
-(x|-x) = 0000..0000..01 = 1

Si x==0, il -x==0, (x|-x)==0, -(x|-x)==0.

Bref on a produit 1 ou 0 indépendamment du nombre de bits de x pourvu
qu'il ait une arithmétique en complément à deux.

a+

sam.
Manuel P
Le #26343893
Le Fri, 13 Mar 2015 23:48:51 +0100, Samuel DEVULDER a écrit :

Le 13/03/2015 21:12, Manuel Pégourié-Gonnard a écrit :
[désolé pour la fausse réponse qui casse le fil, mais pour une raison qui
m'échappe le message de Samuel n'apparait pas sur le serveur que j'utilise, je
fais donc un copier-coller depuis google groups...]



C'est parce que j'avais écrit une bêtise et que j'ai supprimé mon
message sitôt la bêtise identifiée, mais google-group semble ignorer les
cancels.



J'y ai pensé peu de temps après avoir posté, du coup c'était pas très
fin de ma part d'être allé repêcher ton message comme ça, désolé :(

Quelle bêtise ? J'ai lu int32_t et pas uint32_t. Du coup mon argument
tombe à l'eau.



Sauf si on aime couper les cheveux en seize et qu'on commence à
envisager des implémentations où int fait plus de 32 bits...

Cependant la question peut se poser de savoir quelle est la sémantique
formelle de -x quand x est unsigned. Pour moi ca fait un overflow.



Pour le coup, il me semble que la norme est sans ambiguité là-dessus
(6.2.5 9) :

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.

Un point à noter: si on travaille en complément à deux on peut aussi se
passer du décalage à droite en écrivant: -(x|-x)



Ça a l'air joli mais je relirai ça demain matin après avoir dormi :)

Manuel.
Manuel P
Le #26343895
Le Fri, 13 Mar 2015 20:41:21 +0100, Manuel Pégourié-Gonnard a écrit :

En fait, j'ai du mal à me faire une opinion sur les points 1 et 2, de
mon point de vue tant qu'aucune des personnes à qui j'en parle n'est
capable de me citer un cas concret de compilo qui génère une branche
avec == et pas avec une manip comme ci-dessus, on est plus dans le FUD
que dans une approche rationnelle.



Bon bah du coup je me suis sorti un peu les mains de poches et j'ai comparé
les deux fonctions suivantes avec ce que j'avais sous la main comme compilo
sur quelques plateformes courantes.

int inz_bits (uint32_t x) { return (x|-x)>>31; }
int inz_naive (uint32_t x) { return x != 0; }

Je parle pas tant d'assembleurs que ça, mais en m'appuyant sur le nombre de
labels pour détecter les branches, j'obtiens :

. = no branch = good
X = branch = bad

Clang 3.5 GCC 4.9 armcc 5.03

bits naive bits naive bits naive
0123sz 0123sz 0123s 0123s 0123st 0123st
armv6 ...... ...... ..... ..... ...... XX....
armv6m ...... XXXXXX ..... ..... ...... XXXXXX
armv7a ...... ...... ..... ..... ...... XX....
armv7m ...... ...... ..... ..... ...... XXXXX.
armv8a ...... ...... ..... .....
i686 ...... ...... ..... .....
mips ...... ...... ..... .....
mips64 ...... ...... ..... .....
ppc ...... ......
ppc64 ...... X.....
sparc ...... XXXXXX
sparc64 ...... ...... ..... .....
x86_64 ...... ...... ..... .....

Bon du coup pour cette fonction, en effet il faut préferer la version
qui utilise des opérations sur les bits si on veut éviter les fuites.

Manuel.

PS : https://github.com/mpg/ct pour les scripts utilisés. (Pour passer de la
pile de fichiers .s au tableau ci-dessus, par contre, le script est entre la
chaise et le clavier...)
espie
Le #26343925
Grosso-modo, la plupart de ces trucs reviennent a remplacer des trucs clairs par des equivalents
obfuscated qui font la meme chose.

En tant qu'auteur de compilo, je verrais ca comme un challenge: qu'est-ce qu'il faut que je
rajoute dans mon compilateur pour optimiser ces trucs quand meme ? :p

Apres, de toutes facons, un fabricant de processeur est deja en train de faire des trucs qui vont
limiter ce genre de choses. En fait, ce dont tu aurais besoin pour reparer VRAIMENT ca, ca serait
d'une sorte de micro-timer, ou tu pourrais dire "demerde-toi pour que ca prenne autant de temps
que ca, exactement, quelles que soient les instructions executees".

Sinon, cette histoire de timing constant, c'est perdu d'avance. Tu peux au plus y arriver avec
une implementation donnee sur une generation de processeur donnee...
Manuel P
Le #26343947
Le Sat, 14 Mar 2015 09:55:37 +0000, Marc Espie a écrit :

Grosso-modo, la plupart de ces trucs reviennent a remplacer des trucs
clairs par des equivalents obfuscated qui font la meme chose.



Ouais, totalement.

En tant qu'auteur de compilo, je verrais ca comme un challenge:
qu'est-ce qu'il faut que je rajoute dans mon compilateur pour
optimiser ces trucs quand meme ? :p



:D J'espère quand même qu'ils le feront pas exprès pour embêter les
utilisateurs, mais effectivement je m'attends à ce que ce genre
d'obfuscation marche de moins en moins.

Apres, de toutes facons, un fabricant de processeur est deja en train
de faire des trucs qui vont limiter ce genre de choses.



Tu penses à un truc en particulier ?

En fait, ce
dont tu aurais besoin pour reparer VRAIMENT ca, ca serait d'une sorte
de micro-timer, ou tu pourrais dire "demerde-toi pour que ca prenne
autant de temps que ca, exactement, quelles que soient les
instructions executees".



Si on ne considère que le timing, oui. Mais il y a d'autres vecteurs de
fuites (puissance, champ magnétique, etc) par rapport auxquels il est
souhaitable (même si pas suffisant) d'avoir un chemin d'exécution
constant.

En fait, ce que j'aimerais, c'est un pragma qui permette de dire au
compilo que dans telle portion du code il s'abtient d'introduire des
branches. Allez, rêvons un peu, même qu'il remplace les branches par une
construction équivalente sans branche, c'est le genre de truc qu'il
pourrait probablement faire mieux que moi, et puis comme ça je peux
continuer à écrire du code lisible, je préfère.

À défaut, pouvoir lui dire qu'il fait exactement ce que je veux, et ça
existe dans certains compilos, ça s'appelle __asm volatile, mais ça pose
des petits soucis de portabilité :)

Sinon, cette histoire de timing constant, c'est perdu d'avance. Tu
peux au plus y arriver avec une implementation donnee sur une
generation de processeur donnee...



Je crois que c'est comme ça que ça va finir : une version générique du
code pour tout le monde, et des versions pour certains processeurs
offrant un niveau de garantie plus élevé. Après tout, c'est déjà le
genre de trucs qu'on doit souvent faire pour la performance, alors
autant le faire pour la sécurité aussi.

Manuel.
Publicité
Poster une réponse
Anonyme